Mean-Field Analysis for Learning Subspace-Sparse Polynomials with Gaussian Input
Authors: Ziang Chen
Rong Ge
Venue: NeurIPS 2024 poster (2024)
Keywords: Subspace-sparse polynomial
merged-staircase property
algebraic independence
mean-field analysis
stochastic gradient descent
Primary area: learning_theory

Abstract: In this work, we study the mean-field flow for learning subspace-sparse polynomials using stochastic gradient descent and two-layer neural networks, where the input distribution is standard Gaussian and the output only depends on the projection of the input onto a low-dimensional subspace. We establish a necessary condition for SGD-learnability, involving both the characteristics of the target function and the expressiveness of the activation function. In addition, we prove that the condition is almost sufficient, in the sense that a condition slightly stronger than the necessary condition can guarantee the exponential decay of the loss functional to zero.

Mean-Field Analysis for Learning Subspace-Sparse Polynomials with Gaussian Input
Ziang Chen
Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 ziang@mit.co t. edu
Rong Ge
Department of Computer Science and Department of Mathematics
Duke University
Durham, NC 27708 ronggeecs duke. edu
Abstract
In this work, we study the mean-field flow for learning subspace-sparse polynomials using stochastic gradient descent and two-layer neural networks, where the input distribution is standard Gaussian and the output only depends on the projection of the input onto a low-dimensional subspace. We establish necessary condition for SGD-learabilityy involving both the characteristics of the target function and the expressiveness of the activation function. In addition, we prove that the condition is almost sufficient, in the sense that a condition slightly stronger than the necessary condition can guarantee the exponential decay of the loss functional zero.
Introduction
Neural Networks (NNs) powerful in practice to approximate mappings certain data structures, such as Convectional Neural Networks (CNNs) for image data, Graph Neural Networks (GNNs) for graph data, and Recurrent Neural Networks (RNNs) for sequential data, stimulating numerous breakthroughs in application of machine learning in many branches of science, engineering, etc. The surprising performance of neural networks is often explained by arguing that neural networks automatically learns useful representations of the data. However, how simple training procedures such stochastic gradient descent (SGD) extract features remains major open problem.
Optimization of neural networks has received lots of attention. For simpler networks such as linear neural networks, local minima also globally optimal [4 15 17]. However, this is not true for nonlinear networks even depth 2 [23]. Neural Tangent Kernel (NTK, [4]
12 [3) is a line of work that establishes strong convergence results for wide neural networks. However, in the NTK regime, neural network is equivalent to a kernel, which cannot learn useful features based on the target function. Such limitation prevents neural networks in NTK regime from efficiently learning even simple single index models
28
As alternative, the behavior of SGD can also be understood via mean-field analysis, for both two-layer neural networks [9] 19 20 22 24 25 and multi-layer neural networks [1] Neural networks in the mean-field regime have the potential to do feature learning, Recently, || showed an interesting setup where a two-layer neural network can learn representations if the target func- tion satisfies merged-staircass, property. More precisely, considers sparse polynomial
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

i.c., polynomial f R + E defined on the hypercube ie. f() = (z1z)) (((z)) where 2, = (Iz) I is an unknown subset of {1, 2............. ........................ d3 with | = p. and h" {-1.1) R is a function on the subset of coordinates in T. Theey prove that a condition called the merged-staircase property necessary and in some sense sufficient for learning such f using SGD and two-layer neural networks. The merged-stairease property proposed in [ states that all monomials of h" can be ordered such that each monomial contains at most one 2; that does not appear in any previous monomial. For example, h (=) = 2 + 21 + 21 22 satisfies the merged-staircass property while (=(2)) = ž1 + ž 22 does not. Results on similar structures can also be found in [3] The work 2 proposes the concept of leap complexity and generalizes the results in [1] to larger family of sparse polynomials.
(x))
In this work, we consider "subspace-sparse" polynomial that is more general. Concretely, let (x) = h²(=) h" (x()), where V a subspace of RRd with dim(V) = p < d, av is the orthogonal projection of onto the subspace V, and h" V - R is an underlying polynomial map. In other words, the sparsity in the sense that (xx only depends on the projection of the input E Rd in a -wwdimeesiooal subspace. Throughout this paper, the input data distribution is the standard d-dimensional normal distribution, i.e., x ~ ~O. Ia), which is rotation invaariant in the sense that Ox ~ (0, Ia) for any orthogonal matrix O E RRdxd Similar volation-imvarinnnbasi---ffe settings are also considered in some recent studies, including
10
Our contribution and related works Our first contribution is a basis-free necessary condition for SGD-Icarnaillity. More specially, we propose the reflective property of the underlying polynomial h" V + R with respect to some subspace S C V. which also involves the expressiveness of the activation function. We prove that as long as the reflective property is satisfied with respect to nontrivial S. the training dynamics cannot learn any information about the behavior of h² on (see Theorem 3.4). Therefore the loss functional will be bounded away from 0 during the whole training procedure.
One key point is that our reflective property precisely characterizes the necessary expressiveness of the activation function. If the activation function is expressive enough, the reflective property equivalently recovers a necessary condition characterized by isoLeap [2] that is the maximal leap complexity over all orthonormal basis and can be viewed as basis-free generalization of the merged- staircase property. This also indicates that our necessary condition is bit weaker. Other related rotation-invarinn conditions in the previous literature include leap exponent/index X 10, subspace conditioning [10] and even- -ven-symmetric directions [I]. The analysis in [10 11 is for training the first layer for finitely many iterations with fixed second- and [8] studies the joint learning dynamics where they assume that for any fixed first layer, the optimal parameters in second layer can be found efficiently and reformulate the loss as a function the first layer. Differently and more generally, our analysis for the necessary condition does not require specific learning strategies and works for any learning rates satisfying some mild conditions.
Our second contribution is a sufficient condition for SGD-Icarnablityy that is also basis-free and is slightly stronger than the necessary condition. In particular, we show that if the training dynamics cannot be trapped in any proper subspace of V, then one can choose the initial parameter distribution and the learning rate such that the loss functional decays to zero exponentially fast with dimension- free rates (see Theorem 4.3p. Our training strategy is inspired by [1] with the difference that we take the average of p independent training trajectories, which can lift some linear independence property required for polynomials on hypercube to algebraic independence in the general polynomial setting.
Technical challenges It may seem simple leave the standard basis and generalize the results of [ to learn subspaces, because SGD itself is independent of the basis, and we can consider a symmetric Gaussian input distribution. However, there some significant barriers that motivated our training process. The condition and the analysis in 2 rely on an orthonormal basis of the input space Rd. This is natural for polynomials on the hypercube (-1,1] but not for general polynomials on Rdd Particularly, their theory does not work for Gaussian input data ~ (0, La), which is probably the most common distribution in data science, unless an orthonormal basis of IR is specified and V is known to be spanned by p elements the basis. In this work, we consider a more general setting in which specifying a basis is not required and the space V can be any p-dimensional subspace of Rdd This setting is consistent with the iotation-invarian property of ((, La) and introduces more difficulties since less knowledge of V is available prior to training.

---

Organization The rest of this paper will be organized as follows. We introduce some preliminaries on mean-field dynamics in Section 2 The basis- free necessary and sufficient conditions for SGD- learnability are discussed in Section 3 and Section 4 respectively. We conclude in Section
2 Preliminaries on Mean-Field Dynamics
The mean-field dynamics describes the limiting behavior of the training procedure when the step- size/learning rate converges to zero, i.e., the evolution of neuron converges to the solution of differential equation with continuous time, and when the number of neurons converges to infinity, ie.. the empirical distribution of all neurons converges to some limiting probability distribution. For two-layer neural networks, some quantitative results are established in [20] that characterize the distance between the SGD trajectory and the mean-field evolution flow, and these results further improved as dimension- in [19]. Such results suggest that analyzing the mean mean-field -feld flow is sufficient for understanding the SGD trajectory in some settings. In this section, briefly review the setup of two-layer neural networks, SGD, and their mean-field versions, following 19 20
Two-layer neural network and SGD
The two-layer neural network is of the following form:
[N; θ)
N (2; 0.)
(wo w/)x),
(2.1)
where N is the number of neurons, O = (0 0 with 0g (a,, wy) E Rd+11 is the set of parameters, and IR R is the activation functions with r(x; () ar(w" T x)) for (a, w). Then the task is to find some parameter é such that the fz-distance between f and fsN is minimized:
min Ex(+)
N(0... [15*(x) JNN(E; 0)
(2.2)
2
In practice, a widely used algorithm for solving (2.2 is the stochastic gradient descent (SGD) that iterates as
(k+1) -
0
7 +
0(1)))
Vor(Zz;0
(2.3)
where 2g. k k= 1,2.... are the i.i.d. samples drawn from (0, Id) and (A) diag(
(k)
7/0 Ia) N
(1)
O is the stepsize or the learning rate. In this paper, we only consider the one-pass model with each data point being used exactly once, following [19].
Mean-field dynamics
One can generalize 2.1 to an indinite-width two-layer neural network:
(xx == f T(æ; T((=; (()))) f ao ao x)p(da, dw),
where P P(R4+1) is probability measure the parameter space Rd+1, and generalize the [1^(()) - INN(:; mI]]
loss/energy functional (2.2) to
E()) 1 BonA(O.L)
We will use P(X) to denote the collection of probability measures on space X throughout this paper. The limiting behavior of the SGD trajectory (2.3) when (M) + 0 and N - oo can be described by the following mean-field dynamics:
{ Tepe = V (ME))))
(2.4)
Pp 10 Po,
where E(!) (1), B((+1)x(d+D) with (a 2 0 and E.. 2 0 being the learning
rates and
p(0;p) a [UNN( (*)) Tx)]
One can also write (00: p) as
-10:))=v() + U(0,0')
3

---

where
v(0) - = [x)) x)] and U(0,0' - aa'E, Em [o(w s)o((w)) [<x'((xx)]]
(2.5)
The PDE 2.4 is understood in the weak sense, i.e. Pr. is solution to 2..4 if and only if pi p== po
and
|| |-8 Van (E(t) p: O, nn E (RR (0, +00)),
where C (Rd+1 x (0, +oo)) is the collection of all smooth and compactly supported functions on Rd+1, x (0, +oo). It can also be computed that the energy functional is non-increasing along P::
d dt E(pi) -- - / (0: ((tea(e))))(((VVooo(((e(eee ((t)) - O.
V
(2.6)
There have been standard results in the existing literature that provide dimension-free bounds for the distance between the empirical distribution of the parameters generalized by (2.3) and the solution to (.4 For the simplicity of reading, we will not present those results and the proof; interested readers are referred to [19]. In the rest of this paper, we will focus on the analysis of (2.4) and briefly discuss the sample complexity results implied by our mean-field analysis.
3 Necessary Condition for SGD-Learnabiliy
This section introduces a condition that can prevent SGD from recovering all information about f", or in other words, prevent the loss functional {pe) decaying to value sufficiently close to O.
3.1 Reflective Property
Before rigorously presenting our main theorem, we state the assumptions used in this section.
Assumption 3.1. Assume that the followings hold:
(i) The activation function o R + R is twice continuously differentiable with [[]]l S Ko. |o'lL S. Ka, and [[")) I Ko for some constant K, > O.
(ii) The learning rates Ew Ew
R220 - T satisfy that [IEalle=<<>o)) Kg and 11 (Boo)) S Kg for some constant Ke > 0. Furthermore, &a and Ewr are Lipschitz continuous with fo f (a(t)dt = +00 and Ju f (v)(t) = +oc.
(iii The initialization is po Pa pw such that Pa is symmetric and is supported in [-Kps ps Kol for some constant K,- > O.
In Assumption 3.1 the Condition (i) is satisfied by some commonly used activation functions, such as or (z) - and (xx) = cos(x), and is required for establishing the existence and uniqueness of the solution to 2.4g. The Condition (ii) and (iii) are also standard and easy to satisfy in practice.
Remark 3.2. The symmetry of Pr, implies that fNw(æ; Po) = O. Therefore, the initial loss (po) = where xv = = ~ (O, Iv), can be viewed as constant depending only on ht' and p. independent of d. Noticing also the decay property (.6). the loss any time i can be bounded as Eppt) S E(po) = 1
2 R. (xx)²) j { (1"x)) = [1
The main goal of this section is to generalize the merged-staireass property in basis-free setting for general polynomials. Without a standard basis, it is hard to talk about having a "staircase" of monomials. Even with a fixed basis, it is still nontrial to define the merged-staieee staircase property for general polynomials since the analysis in [I] highly depends on 2; = 1 that is only true for polynomials on the hypercube. Instead, we use the observation that when a function does not satisfy the merged staircase property, it implies that two of the variables will behave the same in the training dynamics. Such a symmetry can be generalized to the basis-fred setting for general polynomials and summarize this as the following reflective property:

---

Definition 3.3 (Reflective property), Let S C V C BA be subspace V... V. We say that the underlying polynomial h- V + R. satisfies the reflective property with respect to the subspace S and the activation function if
E (o [x)(z) (u u T 25) 2s] O, PP (2) and z = = (2), with P'g V + S being the orthogonal projection from
(3.1)
where 28- V onto S.
The reflective property defined above is closely related the merged- stairccae property in [. Let us illustrate the intuition using a simple example. Consider V = I2 and (z) = 21 + 21 22.... Then h" does not satisfy the merged-staircas property since 2 =2-3 involves two new coordinates that do not appear in the first monomial 21. In our setting, this h satisfies the reflective with respect to S span e2, 63), where e; is the vector in R$ with the i-th entry being and other entries being O. More specifically, for z = (21, 22 23), one has that 2ş (0, 22: 23) and 25 = (21, 0, 0). Thus, one has for any E IR and E V that o' (u + v 25) is independent of 22, F3 and that
Ex 22 [h* (z)a' (u + v 2$) 2s] = (u uu+uTzn 2अ) E 2s [[0, 21 + 21 2123 + =12223)
00,
which leads to G.I.. One can see from this example that satisfying the reflective property with respect to a nontrivial subspace S C V is in the same spirit as not satisfying the merged-staircase property. Furthermore, the reflective property is cotation-invariann meaning that using different orthonormal basis does not change the property. In this sense, our proposed condition is more general than that in []] We also remark that there have been other e.g.,
conditions generalizing [Л] see
Another comment is that the reflective property (3.1) depends on the activation function while conditions in previous works [2 & IO, II] are all defined for the target function f or ht itself. There does exist a variant of our reflective property that is independent of o', namely,
E2g=w((011s) [h" (=)=s] = 0, Z
(3.2)
which actually implies 3.1. But these two conditions are different: h²(2)) 21 + 21 21 22 does not satisfy (3.2) but still satisfies (3.I) if (5) = Ç. We use (3.I) with o' because we want to emphasize that the SGD learnability depends the activation function σ.. If a is less expressive, then SGD may not learn the target function even if h² itself satisfies the merged-staireeee
property. Typically people use activation functions that are expressive enough, for which (3.1) and (3.2) are similar. In addition, it can be verified that (3.2) with some nontrivial S is equivalent to Leape))( 2 2 that means h² V + R does not satisfy the merged-stairease property for some orthonormal basis of V 22, and the idea of leaps is used in 8 [0] We include the proof of equivalence in Appendix [.
Our main result in this section is that the reflective property with nontrivial S would lead to a positive lower bound of (ppt) along the training dynamics, which provides a necessary condition for the SGD-learnability and is formally stated follows.
Theorem 3.4. Suppose that Assumption 3.1 holds with pw ~ NO, La). and that h² : V - R satisfies the reflective property with respect to some subspace S C V and activation function a. Then for any T >0 0, there exists a constant C > O depending only on p. lt", Ka. Kg, Kp, and T, such that
1 inf E(p)) 2 EE-NNOO.V [Ih(2)) - hig (25) d2//²
C
(3.3)
OS1ST
where lig, (=+) = Ezy (=)). In particular, if he (2) is not independent of as, then for any T > O. there exists d(T) > 0 depending only on P. hi, Ka, Kg, Kr, and T, such that for any d >>>>> d(T), we have
1 2 E [In (2) hig (c$)) >
E(pi) 2 inf 0S1ST
(3.4)
It is worth remarking that in Theorem 3.4 the training time T is constant independent of the dimension d. If a longer d-dependent training beyond a constant time is allowed, then Ep:)) might be reasonably small even if the necessary condition is not satisfied, see e.g. 18 26).
In Appendix B.2
we include a brief discussion of the sample complexity result of SGD implied
by Theorem 3.4 In particular, SGD with (d) samples cannot recover f" reliably if the refelctive
5

---

property holds, which is consistent with observations in previous works such as 1 21. We also remark that our result in Theorem 1.40reem..4j established for the mean-field dynamics corresponding the one-pass SGD (2.3) any may not apply for other variants of SGD. In particular, some recent works 1 16 prove that multi-pass SGD with batch-reuse mechanism can learn some target functions
with fewer samples than one-pass SGD.
3.2 Proof Sketch for Theorem 3.4
To prove Theorem 3.4 the main intuition is that under some mild assumptions, if (3.1) is satisfied and the initial distribution Po is supported in {(a, w) E Rd+1 -wg = 0}, where w's is the orthogonal projection of w E TRd onto S, then A: is supported in {(a, w) E [ ws = 03 for all 2 0. This means that the trained neural network fNN pt) learns no information about æıs, the orthogonal projection of x E IRd onto S, and hence cannot approximate (a) = h" (zv) with arbitrarily small error if h² (2) is dependent on 2g. We formulate this observation in the following theorem.
Theorem 3.5. Suppose that Assumption 3.1 hold and let pt be the solution to (244. Let S C R be
subspace with the projection map Ps IR + S that maps (a, w) to ws. If (Ps)# = ōg, where 5g is the delta measure on S and
By (x) (w (TTT))) x5)=ss O, VWERS,
(3.5)
where zड = Zg. then it holds for any t 0 that
(Ps) = 8s.
(3.6)
Here, the delta measure 65 on is probability measure on S such that for any continuous and compactly supported function şo S - IR, it holds that ʃs ( = (()). In Theorem the condition (3.5) is stated in terms of f*. We will show later that it is closely related to and actually implied by (3.). via a decomposition w x5 w. (x xv) + w (xv Is), with w (æ vv) and w² (av rs) corresponding to and v 23 in 3.1.. respectively. The main idea in the proof of Theorem 3.5 is to construct flow P.. in the space P(R x St), where S is the orthogonal complement of S in IR, and then show that P. de x 8g is the solution to (2.4). More specifically, the flow P. is constructed as the solution the following evolution equation in P(I S-):
O:p: V (pr((tVV,
(3.7)
0+ i+l = Po:
d and where Āo E P(RR x 111) satisfies Pa Po x 8s, 0 0= (a, ws) {(t) = diag(Ea (t), (t)(ss)))
((::p) = alFex [(nn((at:)) - S (1)) a ((w5) T r5)] = v() + f (0(0,0)))(0 )(dd))
with
fNN(E3: = f ao ((w3) 2 p(da dw
f
and
(0)= (x) ((w3) ( aa 'E, lo ((w3) T 25) a ((ww))) x+)]]
The detailed proof will be presented in Appendix A.I
In practice, both V and S are unknown and it is nontrivial to choose an initialization Po supported in (aa, w) TRo+1 wis = 0}. However, one can set Pa = Pa X Pw with Per ~ NN _ Ta) and this can make the marginal distribution of po on S very close to the the delta measure ós if >>> p = di) 2 dim(S), which fits the setting of subspace-sparse polynomials. Rigorously, we have the following theorem stating dimension-free stability with respect to initial distribution, with the proof deferred to Appendix A.2
Theorem 3.6. Suppose that Assumption 3.1 holds for both po and po. Let Pt solve dep: = V (pr((t) 2 (0: Pc)) and let Pt solve orp, =Vo (p.E(t)V (0; p.)). Then for any T E (0, +00), there exists constant C, > 0 depending only on p. ht,, Ka. Kę, Kp, and T, such that
sup Ez [[NN(x - fim(2; | < C, (po. 0stST
(3.8)
where W2(-.-) is the 2- Wasserstein metric.
Based on Theorem 3.5 and Theorem 3.6, Theorem 3.4 can be proved by some straightforward computation, for which the details can be found in Appendix A.3

---

Algorithm 1 Training strategy
Set the initial distribution as Po Pa dgu, where Pa U[- and óga the delta measure R..
2: Set (4) = 0 and (1) - for 0 S S T, and train the neural network with activation function
a. Denote by (a, (e(a,))) 0 < S ' the trajectory of single partiele that starts at (a, 0).
3: Repeat Step for p times independently and obtain p copies of parameters at T, say (as, w(a;) 7))
with a, [[[[1, 1]), i 1, ..
T)) Train the neural 4: Reset pr the distribution of (0, u(a1, ail......... ap. (o,
network with Ea (1) 1, Em = 0, and new activation function o(C) (1 + ()", where n de for 2 starting at pr.
4 Sufficient Condition for SGD-Learnabilit
In this section, we propose a sufficient condition and a training strategy that can guarantee the exponential decay of (pt) with constants independent of the dimension d.
4.1 Training Procedure and Convergence Guarantee
We prove in Section 3 that if the trained parameters always stay in proper subspace {(a, w) Rd+1, Wg = 0}, then [NN(2; Pt) cannot learn all information about f or ht, Ideally, one would expect the negation to be a sufficient condition for the SGD-learnailitty i.e., the existence of a choice of learning rates and initial distribution that guarantees Iim E(t)) with dimension-free rate. This almost true but we need a slightly stronger condition due to technical issues. More specifically, we need that the Taylor's expansion of some dynamics (not the dynamics itself) is not trapped in any proper subspace.
Assumption 4.1. Consider the following flow wy (1) in V: di (t) = E., (z)o (1) [)), vv (0) O.
(4.1)
We assume that for some E N_, the Taylor's expansion up to s-th order of úvv (t) at t is not contained in any proper subspace V..
Assumption 4.1 aims state the same observation as the merged-staircase property in (1. As simple example, if V = Rp and h (z) = 21 + 21 + 22 + +... + 22 ........ 2p which satisfies the merged-stairease property, then it can be computed that the leading order terms of the coordinates of (I) are given by 0212, cg(2"
Gp1" 1.P"- with nonzero constants 6,,
if a E (R) (P) (0) are all nonzero (see Proposition 33 in (]). This 2 is satisfied for this example. We provide further
with s = 2p-1 and (0)) (2)
(0)
is to say that Assumption 4.1 with
characterization of Assumption 4.1 by verifying it in a more general setting in Appendix D.I
We also remark that the Taylor's 's expansion of the flow (v)()) (t) that solves (4.1 depends only on the h* and o (1) (0), of (²)) (O),..., (0). We require some additional regularity assumption on higher-order derivatives of aT
Assumption 4.2. Assume that satisfies E CL+11 (R) and a, o" o((+)) deg( (f) deg(h") and being the positive integer in Assumption 4.1
(R), where
L = 2sm (?++)) with
Our proposed training strategy is stated in Algorithm | The training strategy is inspired by the two-stage strategy proposed in [1 that trains the parameters w with fixed a for E 00, T] and then trains the parameter with fixed w and perturbed activation function for L > T. Several important modifications are made since we consider general polynomials, rather than polynomials on hypercubes as in [I] In particular,
We need to repeat Step 2 (training w) for p times and use their average as the initialization of training while this step only needs to be done once in I. The reason is that the space of polynomials on the hypereube ( [=1]² is essentially a linear space with dimension 2P. However, the space of general polynomials V is an Rlalgebra that is also linear
7

---

space but is of infinite dimension. Therefore, to make the kernel matrix in training non-degenerate. we require some algebraic independence which can be guaranteed by u(a1,.... Ap: ()
و w(a;; (), 0 < 1 < T, though linear independence suffices for [.. Let us also emphasize that each run of Step 2 involves training interacting particle system instead of training a single particle.
In Step 4, we use a new activation function (C) (1 + ()" that a polynomial of the same degree as f and h". The reason is still that we work with the space general polynomials whose dimension as a linear space is infinite. Thus, we need the specific form (() (1 + ()ah to guarantee the trained neural network [NN( pt) is polynomial with degree at most n = deg( = deg(h"). ) As a comparison, in the setting [,, all functions on {=1]e can be understood polynomial, and no specific format of the new activation function is needed.
Our main theorem in this section is follows, stating that the loss functional E(p) can decay to 0 exponentially fast, with rates independent of the dimension d.
Theorem 4.3, Suppose that Assumption 4.1 and 4.2 hold and let pt. be the flow generated by Algorithm 7 There exist constants C1, C2 > 0 depending on ht, o. n, such that
{p:) < C1 exp(- 4120.
Let us also remark that is possible to use the original dynamics dy defined in (4.1 when we state Assumption 4.1 which can actually imply its Taylor's expansion up some order is not trapped in any proper subspace of if we further assume tyy (t) is analytic. We choose to directly use Taylor's expansion in Assumption 4. since we want to avoid the additional analytic assumption
and to emphasize that the constants C1, C2 in Theorem 4.3 depend on the order 8 of the Tayler's expansion satisfying Assumption 4.1
Discussion about the sample complexity implied by Theorem 4.3 suggesting that (dd samples suffices for SGD to learn f reliably if conditions in Theorem 4.3 true. This is also consistent with previous works such as (
is included in Appendix D.2
4.2 Proof Sketch for Theorem
To prove Theorem 4.3 we follow the same general strategy as [Л] though some technical analysis is significantly different due to the inntation-invariant setting. The main goal here is to show before Step 4, the algorithm already learned a diverse set of features. After that, note that Step 4 in Algorithm essentially a convex/quadratic optimization problem (since we only train a and set Eu (t) = 0). In addition, thanks the new activation function (C) (1+ ()", one only needs consider Pv,,, that is the space of of all polynomials on with degree at most n. = deg(h") = deg(f The dimension of Pv,n as a linear space is (*+)). Let P1, PP(.....P(".)) be the orthonormal basis of Pv,, with input 2 NO, Iv) and define the kernel matrix
Ki,, (t) Ba......p [E..s/ [ps, (=)o(((a))) (0 2))( Ap,t)) (p:
(4.2)
where (C) = (1+E5 E)m, (ai..... ap) ~ u([-1,1P)) S i1, 12 S ("+t), and S S T. As long as this kernel matrix is non-degenerate, we know that the loss functional is strongly convex with respect to the parameters in the second layer when fixing the first layer, and thus, it can be computed straightforwardly that the loss decays to 0 exponentially fast for > T, leading to the desired convergence rate in Theorem 4.3] see Appendix C.3 for details. Thus, the main part in the proof of Theorem 4.3 is to establish the non-degeneracy of the kernel matrix.
Proposition 4.4. Suppose that Assumption 4.1 and 4.2 hold. There exist constants C,T > depending on h², n,n.P.S s, such that
Amin (E(()) > Ct (nttt
VOSIST,
(4.3)
where )min((((t) is the smallest eigenvalue of KCt)).
In the rest of this subsection, we sketch the main ideas in the proof of Proposition 4.4 with the details of the proof being deferred to Appendix C
We first show that w w(a,, t) and u(ai....... aps t) can be
8

---

approximated well by zi t) and =pt)) and 01..... respectively. This approximation step follows 1 closely and is analyzed detailedly in Appendix Therefore, give positive lower bound of Amin (AC(t), one only needs to show the non-degeneracy of the matrix M(a,) () (((""))((**"" with
w(a,,t) t) that are polynomials in ag
Mi,iz = Ez [pi, (2)ō(((ai))) (ū(aig: ():aai..))))))))))))))) T)==)
where a1. ......,,........................ a(m)))))))))))) ((m)o)) degeneracy can implied by
and a E IP for i ("....(("p?) Intuitively, this non-
span { Ap. ()Tz) 2): a1, a2 .2......... ap 1-11, = Pv.::
which is true (a ap, t), S S p are R-algebraically independent polynomials in a1, (Q.............................. Op. where ūü is the i-th coefficient of i under some basis of V, and algebraic independence can be obtained from linear independence by taking the average of independent copies. illustrate this intuition with bit more detail.
Algebraic independence of ü, With Assumption 4.1 1 (a, t). (a, wi (a, t) can be proved as R-linnar independent polynomials in E I. Then one can apply the following theorem to boost the linear independence of úù, whose constant term is zero since initialization in training is set as Po Pa x 0ga, to the algebraic independence of úi..
Theorem 4.5. Let U1, 12,..... E RR[a] be Re-inearly independent polynomials with the constant terms being zero. Then (11 (a1) ...... (ap))) (vp((1)) (() +..... +... uppopp R[a1, a2...., Up) are R-algebraically independent.
The proof of Theorem 4.5 is deferred to Appendix C.2 and is based the celebrated Jacobian criterion stated as follows.
Theorem 4.6 (Jacobian criterion pendent and only if
U1 U2,....
Up E Raa,, a2..... , apl are R-algebraically inde-
801
0v1
Øai
dez
Dap
8ea
882
Bay
Bag
Dap
det
Svp
Oue
B0j
Bog
8ag
is nonzero polynomial in R[ay, a.,...,......................... apl.
Non-degeneracy of M(, With the observation that span ()( Py, (see
Lemma C.13), we define another matrix X(q) E ( ((*t))x(**)) via
X (q) = Eg [pr. (2) (2)0()
where q (q1. ... Ct........... in q of the form
(...).))))))))))))))))))))))))) ((tt)) with qi E V, and prove that det (q)) is non-zero polynomial
(utp)
det(X (())
Σ
Σ
Xjq
1=1
05
0
Sn
E=1
where qi is understood as a (coefficient) vector RP associated with a fixed orthonormal basis of V and ji..j2. ................................ j(mtr)) with j, Nº. Then setting q a(a,, leads
(ntp)
n+p X₁
(a,
Σ
Σ
a(a [-1
II
0. Sn
To prove that det(M (M, 1)) is non-zero polynomial in a, i.e., Ma, 1) non-degenerate, we use the following lemma linking algebraic independence back to linear independence.

---

Lemma 4.7. Suppose that U2..... Up E R. Rl(1, 42,.... ......, apl are R-algebraicalty independent. For any m 2 L, the following polynomials in (a.. a....... am (R")") are Il-linearly independent
TR
II 1=1
v(ai",
[all Sn, Asism,
where v (U1, U2 ........ Up).
The proof of Lemma 4.7 and some other related analysis are deferred Appendix
C33
5 Conclusion and Discussions
In this work, we generalize the merged -tarreest property in [ to basis-free version and establish necessary condition for learning subspace- sparee polynomial on Gaussian input with arbitrarily small error. Moreover, we prove the exponential decay property of the loss functional under sufficient condition that is slightly stronger than the necessary one. The bounds and rates are all dimension-free Our work provides some understanding of the mean-field dynamics, though its general behavior extremely difficult to characterize due to the non-convexity of the loss functional.
Let us also make some comments on limitations and future directions. Firstly, there is still a gap between the necessary condition and the sufficient condition, which is basically from the fact that the sufficient condition is built on the Taylor's expansion of the flow (4.1). One future research question whether we can fill the gap by considering the original flow (4.1) rather than its Taylor's s expansion. Secondly, Algorithm | repeats training w for times and takes the average of parameters, which different from the usual strategy for training neural networks. This step used to guarantee the algebraic independence. We conjecture that this step can be removed since the general algebraic independence too strong when we have some preknowledge on the degree of f* or h", which deserves future research.
Acknowledgments and Disclosure of Funding
The work of R. Ge supported by NSF Award DMS-2031849 and CCF-1845171 (CAREER). We thank Joan Bruna for helpful comments and discussion.
References
[1] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The seerged-staircas property: necessary and nearly sufficient condition for SGD learning of sparse functions two-layer neural networks. In Conference on Learning Theory, pages 4782-4887 PMLR, 2022.
[2] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. SGD learning on neural net- works: eapp complexity and saddle-to-saddll dynamics. In The Thirly Sixth Annual Conference on Learning Theory, pages 2552-2623. PMLR, 2023.
[3] Emmanuel Abbe, Enric Boix-Adsera Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems, 34:26989-22 27002, 2021.
[4] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- prramtatettriiitinnnn In International conference on machine learning, pages 242-252. PMLR, 2019.
[5] Dyego Araújo, Roberto Oliveira, and Daniel Yukimura. A mean-field limit for certain deep 2019.
neural networks. arXiv preprint
[6] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows SGD learn high-dimensional multi-index functions. arXiv preprint arXiv:2405. 15459, 2024.
[7] Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. Information and Computation, 222:2-19, 2013.
10

---

[8] Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien. On learning Gaussian multi-index models with gradient flow. arXiv preprint arXiv:2310.19793, 2023.
[9] Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
[10] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step time. In NeurIPS 2023 Workshop on Mathematics of Modern Machine Learning, 2023.
[11] Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborova, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. In Forty-first first-firtt International Conference on Machine Learning. 2024.
[12] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
[13] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[14] Kenji Kawaguchi. Deep learning without poor local minima. Advances in neural information processing systems, 29, 2016.
[15] Kenji Kawaguchi and Yoshua Bengio. Depth with nonlinearity creates no bad local minima in resnets. Neural Networks, 1 118:167-1744 2019.
[16] Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low- dimensional polynomials with SGD near the information-theare limit. arXiv preprint arXiv:2406.0/55 2024.
[17] Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. arXiv preprint 172.v=1702.08580, 2017.
[18] Arvind Mahankali, Haochen Zhang, Kefan Dong, Margalit Glasgow, and Tengyu Ma. Beyond NTK with vanilla gradient descent: mean-field analysis of neural networks with polynomial width, samples, and time. Advances in Neural Information Processing Systems, 36, 2024.
[19] Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464. PMLR, 2019.
[20] 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- E7671, 2018.
[21] Phan-Minh Nguyen. Mean field limit of the learning dynamics of multilayer neural networks. arXiv preprini /902.000002028888 2019.
[22] Grant Rotskoff and Eric Vanden-Eijnden. Trainability and accuracy of artificial neural networks: An interacting particle system approach. Communications on Pure and Applied Mathematics, 75(9):1889-199 1935, 2022.
[23] Itay Safran and Ohad Shamir. Spurious local minima common in two-layer ReLU neural networks. In International conference on machine learning, pages 4433-4441. PMLR, 2018.
[24] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 130(3):1820-188) 2020.
[25] Justin Sirignnno and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal Applied Mathematics, 80(2):225-752, 2020.
11

---

[26] Taiji Suzuki, Denny Wu, Kazusato Oko, and Atsushi Nitanda. Feature learning via mean mean-field langevin dynamics: classifying sparse parities and beyond. Advances in Neural Information Processing Systems, 36, 2024.
[27] Alain-Sol Sznitman. Topics in propagation of chaos. Lecture notes in mathematics, pages 165 255,25,,150 1991.
[28] Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for under- standing neural networks. Advances in Neural Information Processing Systems, 32, 2019.
12

---

A
Proofs for Section 3
This section collects the proofs of Theorem 3.5 Theorem 3.6 and Theorem 3.4
A.1 Proof of Theorem 3.5
Existence and uniqueness of solutions 2.4) Before proving Theorem 3.5
let remark on the
existence and uniqueness of solution to the mean-field dynamics (2.4). According to Remark 7.1 in
20 and Theorem 1.1 in [27]. the PDE (2.4) admits unique solution if Assumption 3.1 (ii) holds and both (() and V VoU(0, 0*) are bounded and Lipschitz continous. Here we recall that V and U are defined in (2.5). With Assumption 3.1 and (ii).
hard verify the boundedness and Lipschitz continuity of (0) and VOU 0*) by noticing that any finite-order moment of N La)
finite.
Since (Ps) = os. the initial distribution Po can be decomposed as Āo òs. where Po E P(R )* Consider the following evolution equation (3.7) in P(R x S By the discussion at the beginning of Section A..I we know that Pt the unique solution to (2.4) Similar arguments also leads to the existence and uniquess of the solution to (3.7)
Proof of Theorem 3.5
We will show that the solution
2.4 must be of the form
Pt P. x 6s,
(A.1)
where Å solves (.7). and this decomposition can immediatel imply (.6). By the uniquess of the solution, it suffices to verify that Pt Pt x 65 is a solution to (.4 It follows directly from A.1 that
(v)(x:pt) = (NN(1; x 6s) fNN("):
and hence that
0. 0. pt) 0, (0: if if 0.
(A.2)
We also have that
((: = aE [(faN(2: pr) - o' x))Ss
w
aE [fNn(as: Pc) - (x)) of ((ws) 255 25
(A.3)
Vug (0:
wg = 0. In addition, it holds also for wz = 0 that o' (w x)xss
V wg (0; p.) alE,2 p:) - f (z))
.IE,, : p:)o'' ((w3) T -ラ3) xs aE,, [f (z)o' ((wz) 23) øs]
(A.4)
= 0, where used Ens [xs] 0 and 3.5
Combining
A.2
A.3
and
A.4 we have for any
E C (Rd+1 x (0, +oo)) C.2 R
X S
x S x (0, +oo)) that
ʃf (-8n Von (E()) p:)) p (dB)dtt
-]lʃ (- (- (- (-0m((,))+ 0,4(0 + (t) wy woniiiinn000 n(,0)) V W0; +tv Vus pi) (dds)
V
= -sʃ (- (. - 0.4(0
+tv
क(0: pr (dā)
= -/ʃ -- V 0,t) = -0,
where the last equality holds by applying the test function 7(,0,,) E C St (0,+000) +20)) to
3.7 The proof is hence completed.
0
13

---

A.2 Proof of Theorem 3.6
The proof Theorem 3.6 uses some ideas from the proof of Theorem 16 in [ Similar ideas also exist in earlier works (see e.g., [99 20)).
Lemma A.1. Suppose that Assumption 3.1 holds and let Pt solve
2.4
Then for any t > 0, pt is
supported in {0 (a, w) gd+1 |a| K + K [Ih" (z)
t).
Proof. The particle dynamics for az associated with (2.4 is given by
d di ar (t)LE [U
which implies that
dt S KeKo EE [JNN( - & KgKK((2(00)) Ke K2 (1)
Therefore, one has lael S |aol Eg hh (2)12) 1/2 which completes the proof.
Lemma A.2. Suppose that Assumption 3.1 holds for both Po and po- Let solve 0.p: = V (o Pc)) and let Pe solve pept Ve (orE(t)Vo pe)). For any coupling "/o T(po Po). let E [ptt, Ps) be the associated coupling during the evolution and define
A(t) = // (1a-af 2 +1| - x||3) ro re(0, d8).
Then it holds for any 0 S < T that
Ex [[ Pt) - fuu(:; Po]c]] & C,a(t),
(A.5)
and
d
dt A(t) S CaA(t),
(A.6)
where Cy and Ca are constants depending only p. h²,, Ka. Kg, K and T.
Proof of Theorem 3.6 Let Cy and Co be the constants in Lemma A.2 coupling to (po, Po) such that
For any e > 0, there exists a
/f (la 10--a" al2 2 w|
dō) < W. 70) +
Define 7/ L'(pe p.) and (tt in Lemma A.2
According A.6 and the Grönwall's inequality,
holds that
(t) < Cst S (W2 Đu) + +c) Cst VOS+ST,
which combined with A.5 yields that
sup E, [[fww(=:)) - (n)(;;p)))) < (W (po- Po) + +c) CyeCaT. 051ST
Then we can conclude (38) be setting e - 0 and C. = CST
Corollary A.3. Under the same setting as in Theorem 3.6 one has
|E(p)) E(p)) (C.E, [lh (x) 1/2 Wz(Po. ōo) + C. (po.Po) Po).
sup ostsT
(A.7)
2
Proof. It can be computed that
E(p:) -E [IC - + ((NN(=:p)) fNN(L:: 13]
=E(Ø-) E, (UNN((;;))) (T)) (x)(2;p))))
1 + BB [[FNN(I:PL) fAN(L; P1
2
14

---

which implies that
[E(p)) -((i)) SBx - ( E ( - [NN(1;; (e)(
sup oSiST
2 [IINN(I::E)) (N:((:
S (C,BBzy [1^ 1/2 W2(p0, + (..
where we used Theorem 3.6 and Remark 3.2
Proof of Lemma A.2 We first prove (A.5) It can be computed that
f noqw' T x))x(d() - -f
f āoo(a= x))p(dd))
[[NN(T;P)) [NN(1;
[f((a- (aaa-))o(uu a
x))a dd) + 11/ (o(w x) - o(w o())x)) Nh (10, dB)
and hence that
Ex [IANN(T: - (NN((::
[/f(a- ())w") (d0 d0)
|//| ā -) -
<2E,
2
o(w x)) n (d00 d0)
We then bound the two terms above as follows:
Ex [1] (a a)o(w" T 2)0(dd, dô)
S K2 // la- ( d0) s (2A(t),
and
Ex |./ à (o(w (T) olw² ((T))))) 74 (d0, d0)
SK3 (Kt V2KcKoE(pu) (22) 2 Ex |/// [(w 1(w- w) w) a1 dā) 2
1/2 r)² /f Ex [K[ の)) T xx1 (d0 d0)
SK3 K2 + KKKK,
K3 K2 + KrK, F. [=] 1/2
1/2 1/²)²
2 /// ||00 ( .d)
<K² K + KeK,E, [1]] 1/2))² A(t),
where we used Lemma A.I and (w- - w) T ~ NN0, || - 31²) if ~ (O, Ia). Then we
can conclude A.5 with Cj K3 K2 K + Ke Kg ||A (z) 1/2)) by combining all
estimations above.
We then head into the proof of (A.6), for which we need the particle dynamics
d: a; (t)EE [(fN pc) (z))
dt a = Et)E [fNN - (z))
-
and
z Wi En.
pt) (f de ii = R.. (JSN (x) (z)) (w)) x)a)
d
The distance between the particle dynamics can be decomposed
d ā, dt
< Kg TE [(]NN(3)))) (2x(
dt
(A.8)
+ Ke EL [[/NN p.) - ( -o x))]
15

---

and
W4 th d
W2 dt iis) )
d
dt
<gg (a. Ex [( pa) - (1)) (m)) x>) - wx)) T x]]
(A.9)
+ K Bu [[/>n(<;; Pe) - [NN(:; Pi)) (w) xu - wx) [x]]
+ Ke 0z [(fNN(z;;))))) ōt) (x)) (d'(w) x) d' d' x)) (w) - Ta]
Therefore, it can be computed that
d dt || a - (l0re d0)
d /[ |a: ãzl 2 (d(00 d6o)
di
2 // (a: - ā
d
at dl a Tol ro(dBo, d0o)
dl
/ʃ 1at äel 10 (dfld dbon) +
d at
d ār
7o(d0o, doo)
dt
dt
A.N
(1) - 2K K² // By (1 pa) - (uN(;; p=)1 (o(00 d0o)
+ k2 // By
(1w w)) Tx:]] x=]] 2 Pold0o, dBo)
A3
(tt) 2K
+ +2K2 //
Es [IANN(=;;)) (x)))-((w w8r) Txl ro(d0.. dto)
S A(t 2,,()
+ +2Kē /1 15 (())) Ex [[(e, - -wt) (T))TT 7o (dlo. d0o)
// | wi Yo dBo)
$ A()) KK E
< + 2K (=)]²) A(1),
where we used Remark 3322 and that
d
// || 1ww-w0 (100 d0)
dt
d
// ||w| - T 11: 7o(000, d0o)
dt
2 /ʃ We Ti, d
d ūi no po(dOo d0o)
Wt
J
dl
2K Ko /1 |uo- -ūrl Trl.Ez [[NN((=;))) - (x)) (( - Tarl ro(doo, ddo)
KKgKa //
|āel - E. [[Nx(1;)))) - (r)) ((w, - w.) T [e]] vo (d00, d0o)
2KgKo /1 |arl-EE Er [[ANN(1:P:) - fx)) (wwe - -bx)] Tx x=l"] yo (ddo.. dōu)
/1 lac- -áel Es [Ih' (=) 1/2 E. |[( - / |] 1/2
< 2K
7o (d00, dōb)
2KcKo /
1 | (C) R. [[ w.:) xx 2
1/2
70 d00 dìa)
-2KgKo // [ārl E. [ (=)
E
(w= w)) T x01
1/2
2a (dbb, d0a)
16

---

2 2KgK, 111 (2)181111 /f la: la--as azl ||w wr. (dl0o c06)
1/2 T) (C, // 1wu, wollro(cd0g) d00)
2K [K + Kx
2Kg Ko (Ko + By [|,* (2)l² 1/2 T) B [I^(())]] 1/2
/1 V3lluz m 20 dd0o d0o)
I Kg [ (x) 1/2 + Ko K, + KeKoEE [1h (x)13) r) ((22((1)
= -233KKK Kp + Kg E, | (2) T E. (2) 1/2 A(t),
where we used Remark 3.2 (A.5) Lemma A.1 and (w - Therefore, we can conclude that
()- か) T NV ||0 m No)
d A(1) di
d
/ʃ |a vn-a@2((d0,dd
+ d di
/f - (d00 < CaD(I),
di
where
Ca CA =1 2K? + K2 /1 (ov)
+ Ke | [1)) 1/2 +2g ( (Kp + KgKoBs (x)) T) 0//2
+ +2V3Kg Ko (K, Ke [1 [=)(3)]]] 1/2 T) E. [1'(())]] 1/2
This proves A.6
A.3
Proof of Theorem 3.4
The proof of Theorem 3.4 is based on Theorem 3.5 and Theorem 3.6
Proof of Theorem
3.4 Let Ps : R++1 + S be the projection in Theorem 3.5 and let P/S = Ia+1
Ps. Let P. solve
2.4 with Āo = PT x 6g. It is clear that (Ps) P = òs. In addition, with the decomposition = œ1 + 222 + 13 where œ1 = _ = x xV, = Iv as. and 23 = are
independent Gaussian random variables, we have for any w E IRd that
Ez [5'(z) (w x5)) æs] En, Emg. [[
+ )a) (w 21 + w x22 x3) 0,
where used 3.1 Then according Theorem 3.5 for any 0 that (Ps)# ōs. which implies that fNN 2) Pt) is constant function in as for any fixed zg. giving a lowerbound on its loss:
E(p))
Ep [I]s* (x) - faN(2;; p.)1
2
E
Exs [[l)(()) - fNN(2; ][]]
2
Eng Exs [llf"(()) (f
2
1
E.g [Ess [|] (z) his [1]
2
E, [1]A* (z) high (25) 1{
2
where 28 Py 23 = zs, and h (2$)) Ezg [h (2)].
Now we show the actual flow is not very different. For Pu = Pa x Pwe with Pwr ~ NNO, Ia) and io = PSPPPP Pw x dg. it can estimated that
(po Po) 5 dim S p
17

---

Then applying Corollary A.3 we can conclude for any T > 0 that
inf {
2
inf ((p)) (C.Ea [IM (=) 1/2
W2(Po, Po) 3
C, (po, Pb)
0StST
0S1ST
B. | (2) h (zs || (pC,Ez R, (=) 1/2
pCs
d1/
2d
where C. 0 the constant in Theorem 3.6 depending only on p, h², Ka Kg, K and T. Therefore, we can obtain (3.3) and (3.4) immediately.
B Further Discussion and Characterization of the Reflective Property and Theorem 3.4
B.1
Equivalence between (3.2 and iso).eap(h")
We prove the following equivalence where isoLeap(h") is the isotropic leap complexity defined in Appendix B.2].
Proposition B.1. For any polynomial h" V - R. then it satisfies 3.2 with some nontrivial subspace S c V if and only if ifsspc)))(h") 2 2.
Proof. Without loss of generality, we assume that IR. Suppose that isoLeap(h"") 2 2, which means that the leap complexity of h" (as defined in 2 Definition 1J) is greater than for some orthonormal basis of V. We can assume that the basis {e1, C2,.... Cp), where ey is the vector in Rº with the j-th entry being 1 and other entries being O. Denote the Hermite decomposition of h" as
171
P He c II 1=1
h (²())
Σ
(n
(B.1)
where C2...., Cm are nonzero coefficients, 01, 02,,.... am are pairwise distinct elements in Nº with a=(i) being the j-th entry of ag and Hes is the k-th order Hermite polynomial. Since the leap complexity of h* is at least two, the following is true after applying some permutation on ",2....,m.. There exists some my (1,2,..., - 1), such that it holds for any {m1 + 1, 1....,m that
Σ JEJmy
a,(i)22
(B.2)
where
Jm, = (1,2, ..1,,.....p) a.( ViE (1,2..,....
Thus, by the orthogonality of Hermite polynomials, we have for i {m1 1,..., m) that
E2
2j
II 1=1
He He (e..,)(()))) = Vj E Jmy
The above also holds for i E 2 mi by the definition of Jmy Therefore, can conclude that
E Bh (=)=s] = 0, =
ie., 3.2 holds, for = span (c, : Jm, }. Moreover, S is nontrivial since B.2 implies Jm, is not empty.
On the other hand, suppose that 3.2 is satisfied with some nontrivial subspace S C V that can be assumed as S ((I).... Epp 0, 0) : .1,..., Apr E RR with S pt S p. We still consider
Hermite decomposition as in (B.l and rewrite as
h² (2) = Σ
He (e
1=1
18

---

where 22.2..... Smz are nonzero coefficients, ai.......... dm are pairwise distinct elements in Noi, and h1, hy...., Nm, are nonzero polynomials defined on Re-v Then it follows from (32 that
m2
Pr We 0,
2pp B()0.11)) [z, He (ea)))(())))
II
j'=1d''
for any j E (1,2,... ,I) and Spttl &p E I. which implies that
Σa,0'+ 11, ViE m22).
Therefore, the leap complexity of ht is at least 2 with respect to this basis, which leads to isoLeap(h") > 2.
B.2 Diseretization Results Implied by Theorem 3.4
We discuss the sample complexity result of SGD implied by Theorem 3.4 in this subsection. Recall that there have been standard dimension-free results for bounding the distance between SGD and the mean-field dynamics; see e.g.. [9]. So the result in this subsection somehow a direct corollary. However, one needs make minor modifications guarantee that all boundedness assumptions in [19] are satisfied.
Given constant Cj > 0, define
(x) = sign(f"(()) (zn()
(B.3)
which is bounded with 1f (x)] S Cj. One observation is that the subspace-sparse structure of f implies that for any 5 0, there exists dimension-free constant C. depending on h" and ā such that Eo. fr (x) P] < 8. The associated mean-field fieldfied dynamics is
0. Vo (DE(()Voo()))))))
(B.4)
( = Po:
where the learning rate E(t) = diag(Ea (t), Ev (t) and the initialization po are shared with (.4). and
(0; p) a alE.
[
- - oww (T)))
The corresponding SGD is given by
e(t++1) = k + (M) (f*(xx) fuN(=x:0 (OT (1))), i= 1,,,..,,
(B.5)
(8) Ia) > is the learning rate with where N the number of neurons and (() = diag(1 (k) Ye
(k) (kee) and
Suppose that assumptions made Theorem 3.4 hold and fix > Using similar analysis in Appendix A.2 one can conclude that for any ò > 0, there exists dimension-free constant C² such that
sup (p:)) - { 6.
0StST
Applying Theorem 3.4 and [19 Theorem 1], conclude that for any μ (0, 1), there exists dimension-free constants No, do, Ce, such that for any N 2 Ng and d 2 dg, the following holds with probability least y for any S a+ :
(x) R BenA [I*(=)) - hT2 (=s) ) > 0. kE(O.T/<<n
inf
we further assume that N (ed)), this indicates that SGD as B.5) cannot learn the subspace- sparse polynomial fr within finite time horizon and with ((d) samples/data points.
19

---

C Proofs for Section
C.1 Approximation of w(a, by Polynomials
This subsection follows [ closely to approximate and analyze the behavior of w(a, f) for <t
with (t) = and a (t) = The dynamics single particle starting at = (a,0) 0) E Rd+ can be described by the following ODE:
di u(a t) alE ()) no(a, 0) = 0,
(C.1)
where
ga,, t) = f [NN(2;
the residual. The first observation is that
Fx [ (x)) T xv )ut] Exv
11" (xv ( (vv) ) [at] 0, V E
By Theorem 3.5 we have that is supported in {aa w) wa = 0]. and hence that
wa = 0, TO
We then analyze the behaviour of wv (a, (a, Let (ei, f.,..... tp) be orthonormal basis of V and denote w, w 6; and 2; x e, for any w, Id and (1.2....,PP)
By Assumption 4.2 it holds that
d' (w(a,t)Tx) = m1 +
mc+1 Σ
(wla, (TTT))Tx)))))) x) + O ((w(a, (TTx))
(C.2)
with my (0) and then an approximated solution to (by polynomial expansion with high-order terms omitted) can be written as
m((a,))= Σ Qus((aa Isisp,
ISJSL
where Q(t) is given by Q(0) and the following dynamics:
(t) = E., [2,g(( (z, t)ml),
d (t) Ez zzg(a,
m
Σ
Σ
II a.
22jss L.
1!
15h
Spii
+i=j--o==
(C.3)
Let us remark that even if every single ú,,a, t) depends on the basis {ei, ep, the linear combination
( t) = Σ (a,
(C.4)
is basis-independent. To this, let (t(t) Rdd be the j-th column of Q(t) and it holds that
(t) = Eg [xg(x, t)mil. d da
d de (t) = Ex xg(2 ( t)
m++1
Σ
II
a
The distance between wy (a, 1) and w. (a, 1) for E 7 can be bounded as follows.
Proposition C.1. Suppose that Assumption 4.2 holds. Then
[w, t) (. t) +( Vie 21. .p).
(C.5)
We need the following two lemmas to prove Proposition C.I
20

---

Lemma C.2. For any E f1,2... p) and (1. L}, it holds that Q1y O(e).
(C.6)
Proof. The non non-increasing property of the energy functional implies that (p:) Ex (2,,g(( t)] & (=) (a, po) E. +00.
Then (C.6 be proved by induction. For j 1, it follows from the boundedness of
d (t)
[2, t)mm] |ma EE, [=f] (x)1g(x, 1/2
dt
that Qi.e = ( Consider any < j v and assume that Qiy O(1")) holds for any 1 S i
S and s j < j. Then one has that
d
(t)
dt
1)
1/2
Ex 1)13
Er
m4+1
Σ
Σ
II
Vi... (t)
I!
1=1
Si Sp Sphtt
+
=0(--1))
which implies that (t)(t) Ott).
Lemma C.3. Suppose that Assumption 4.2 holds. We have for all E (1,2....,p)) that
w,(a, t) O(aatt).
(C.7)
Proof. There exists a constant C > 0 and open subset A C {w E Rd 4 = 0} containing 0,
such that
Ez [x,g(z,t)o (w" =)] sc
V A t 0, ie {1,2, ...
p).
Thus, we have
i Ōt
(a, S |a).
long w(a, t) does not leave A. This implies
C.7
Now we can proceed to prove Proposition C.
Proof of Proposition
C.I
Set w (a, = 0. It can be estimated for any E {1,2, ......P) that
0
w. ( (a, t) - aE 12g(1,t) m1
mi+1
(w a, t) (TTz)))) x))
Ot
!!
<
Σ
ety(t)a aE x1g(I,t)
+
m++1
Σ
Σ
(vs(t)a'x
dt
!!
ISJSL
Σ
Φ. F (ig(x,
M441
Σ
Σ
II
Qu.s (1)),
LH1SILL 1+1
14h
S -
Σ L415/4M-141
la/5
27
1/2
Ellg(r, t) E.
Zi
m4+1
Σ
Σ
II
Qu. (t)x:.
Ki Sp Jj jjjj-sss
21

---

=O[[a = -+)
which combined with (C.2 yields that
wi wa 1) (;(at) t)
01
① (a,t)t w; (a,t)
L-1
mi+1
(u((a,tTTa) Ta){ )
ab
mi +
1=1
(ig(I,t)
+
m++1 (T((a
|aE
[aig(a, (z,
t)]l () o (lal+ti64)
<
Eg
Taa g(x, t) Σ
m++1
(ww(a, 2) (0(a, b>>9)/
+ + (lal+t264)
!!
i=
=0
[wi(a, ti t)| + 0 (1a)
Then one can conclude CC5) from Gronwall's inequality.
Even if ((, t) approximates w(a, E) using polynomial expansion, the coefficients Qtt) are still very difficult to analyze. Thus, we follow [I] to consider the following dynamics that is obtained by replacing ((x, = (*x) fNN(:; Pr) by (x) in
w (a, Σ (is())a ie (1,2....,,PI ,p}
(C.8)
18i5L
where @(1) is given by 2(0) and d
áe (t) = [x fr (x)ml),
L-1
il
d ae (t) = Ey xaf"
mi+1
Σ Σ
(1
SSjST.
II
15h
(C.9)
Similar to ai(a, t), the linear combination úbaa t) defined as
(a t) = Σ (a,
1=1
also independent of the orthogonal basis {e1, le..e,....,.e. ept. Q(t) can be understood clearly as follows.
Proposition C.4. For any (1.2....,p)) and j E {1,2,... ...., L.), there exists constant (r.j depending only on is and a, such that
(z,(1) = Hitt.
(C.10)
Proof. The proof straightforward by induction on j.
The next proposition quantifies the distance between Q(t) and Q(t). Proposition C.5. It holds for any E {1, p} and E (1, L} that
[t) (t)((t) 01
(C.11)
22

---

We need the following lemma for the proof of Proposition C.5 Lemma C.6. It holds that
Ex px) O(t).
(C.12)
Proof. Noticing that [N; Po) = O by the symmetry of Pa. one has that [NN(2;; Pb) [NN( pe) [NN(
/ (a(w(a, t)(x) - -o(0) Pa(da)
/
my
(w(a,t) 1)) + O ((w(a, ((x((at)T)))(1)) 2)) (da).
!!
and hence by Lemma C.3 and w (a, 1) = 0 that
Ex
[[ vr [x]]
which implies CC.12
Proof of Proposition C.5
We prove C.I1 by introduction on j. For j = 1, one has
d (t) Q.. fN, P:) pm)m [mal [Ea[²)) BellfNN p:) Ot),
dt
which leads to (Qi,, (t) Qiee (t)l O(t)) Then consider 2 j L and assume that (1)) (1) (11'+11)) holds for s j <. can be estimated that
d (t)
d 2is (t)
dt dt
Ez
aig(a, 1)
mi+1
Σ
Σ
II
I!
mml
15h
+j
4-1
-E,
m1+1
Σ
Σ
Il
Vun. (t)
Spntt - -
Zt
BeINN(IiPp)
mi-1
Σ
Σ
II
Quas (f)xs,
!!
1i Sp
-
[ Q (t)
-E,
xif" (I)
M111
Σ
Σ
II Qunss (t) Di.
Ki di Sp Hi
Ez
Zi
ZifNN(I,
m4-1
Σ
Σ
!!
Spjr
+j=
Fef (x) Ex
mi+1
Σ
Σ
I!
1sh
I
(Bngtt the + O(t++t))
II
ge. tdo
Di
-O(P),
where we used Lemma C.6
Then one conclude
[.Il
23

---

C.2 From Linear Independence to Algebraic Independence
We prove Theorem 4.5 in this subsection.
Definition C.7 (Algebraic independence). Let V1, U2....., Um E [R(a, 02......pp 0pp be polynomials say that U1, .2..... Um are algebraically independent if for any nonzero + R.
in a1 a1,02,... .2.............................. Up. polynomial F m
F(v1 ((Vi(a1,00 4g, (p)))) Lemma C.8. If U1 .2.....9 E R|aa are R-linearly independent, then
.p..... ..... Um (01, 0.,...... ................................ (p)) + R[a1, 12:11,2.......... ,
vi(a1) 02(01)
vi(az) v2(a2)
vi
u2(ap)
det
(C.13)
(p(a1) u2(22)
mp(ap)
a non-zero polynomial IR [Raa 02 a2....,,p)) apl.
Proof. Let n, be the smallest degree of nonzero monomials of 2 and let G₁ be the accociated coefficient for = 1.2..... p. Without loss of generality, we assume that ng < nı < ... < ny permutations). The polynomial defined in
(otherwise
row reductions (C.13) consists of monomials of degree least n1 + R2 + .... + sum of monomials with degree being n1 n2 .... + ny is nonzero, which is true since
perform
np. So it suffices to prove that the
c1aj" c20 n2
T1 C
C1O
0
02
C2
D2
C2 R2
01
02
det
C102 Cp det
Cpa1
Up
Cpa2
Cyap" Tip
a1
02
Op
is nonzero as generalized Vandermonde matrix.
Proof of Theorem 4.3 Since UI, 02....y Up R be R-linearly independent with the constant terms being zero, we can see that v1. 12 r2....., up IR are also R-linearly independent. Noticing that
- (oi((a) + v;((2) + ... =;((p))) = of((), Dag
a
1
P
one can conclude that (v1 (a1) + ... (ap))...., ( (1) +... E R[aa,,.................... app are
R B--algebraically independent by using Theorem 4.6 and Lemma C.8
C.3 Proofs of Proposition 4.4 and Theorem
Some ideas in this subsection from [T) but the proofs significantly different since need to show the algebraic independence to obtain a non-degenerate kernel, as discussed in Section
Lemma C.9. Suppose that Assumption 4.1 holds with N4. There exists some orthonormal basis {ei, ..,..., 3 of V such that the coefficients qi,j, 1 < < p. j < L in (C.10) satisfies
82
8p I 8,
(C.14)
where
= min(j
ã. + 0},
= 1,2 .p.
Proof. Let (ty((t) be the dynamics defined in can be seen that the Taylor's expansion of (t) at f. = 0 up to s-th order is given by
P
where Qiy and Tie are as in C.9 and According to Assumption 4.1 the matrix (1r.)ssss is of full-row-rank. One can thus perform the QR decomposition, equivalently choose some orthogonal basis, to obtain C.14
D
24

---

In the rest of this subsection, we will always denote = ($1, 82,
sp) and
u(a ao 8) (w(a1, t) + w 1) + wap: t)),
p
i(a1....... Op. t) = (ι(a1, t) + # 1) +... ni (app t)),
p
a(ai...... ........... ap.
(w(a), ( + +... (ap: t)),
fort E [], where w(a, t), (a, t). and ((, t) are defined in Recall that P1.P2...--
and C.8). respectively.
P((==)) P1.P22---PP(p-77 are the orthonormal basis of Pv.n with input ~ (0, Iv), where
Pv.. is the collection of all polynomials on with degrec at most n deg(A") df
Proposition 4.4 aims to bound from below the smallest eigenvalue of the kernel matrix 4.2 definition restated as follows
whose
K, (t) Ea, Ea.,... EZ,..' [po, (2)))(((())....... Op, (p.tt) t)
(),,, (2))l)
where d(5) = (1 + E)", (a1......a,) ap) u([-1, 1).), and 1 s i1. $ (" To do this, we define
three (2+tt) (u+t)) matrices
(t) E Em, ap Ea
[E,,' (2) 22)(((()) an 22))), (z))]]
and
Min.s Ez [pt (2) a12 2)]
Minis 1) = Ez [pi, (2) a1g 1) =)]
where [2, a2 a a()to) and a; E IRP for 1,2, ..... P7
Lemma C.10. It holds that
n+p
det (e
Σ
Σ
hyelill bill
(C.15)
1=1
where (j1.Ja.....scp with j. Nº for 1,2, .... (MtP)), hy is a constant depending on h" and a, and a represents the product of entrywise powers.
Proof. The result follows directly from Proposition C.4 Lemma C.11. It holds that
(+tp))
deu(M 1)) = Σ Σ
(y(()a))
1=1
with
(t( llöl (11l++)
Proof. The result follows directly from Proposition C.4 and Proposition C.5 Lemma C.12. For any m e one has that
span 2) : E V TP P
(C.16)
where 1pby Vm is the collection of all homogeneous polynomials in E V with degree m.
Proof. Without loss of generality, we assume that V = IRP and prove the result by induction on
(.166 clearly true for p = Then we consider p 2 and assume that (C.66) holds for p and
any
25

---

to For any 2 E R", we denote that (92.....,9p 9p) and 2 = (22,...,,,
22)) Let to. t,...., fm E R be
distinct. Then it follows from the invertibility of (t,) Josissm and
(1021 + x) (1121 + 7 m)
Σ m0 1 ()
1 m)m=
(f,,21 + 2)
Dimo (T) en 2 (q 2)m-3
to
m
(q 2)m m
t1
(T) 21 ( 2) m
tm
(m) 21
that
=
2)m E span {rr 2)th :r RR),
V i E {0, :0..,...,m3 m..
Then using the induction hypothesis that (C.16) true for and i, 0, m., one conclude that (C.16) is also true for and m.
Lemma C.13. For (E) (1 + e)", one has that
span (ō(g z) q : Pv...
Proof. One can still assume that V distinct tu, ti....,tt E R. Then
RP without loss of generality, Consider any q Rp and any
(((tog) T2) T((t1g)
(6( 2) C1 2)
t CT
()
((((ng)T2)
E (g4 2)
Im
(1) 2)m
Note that the matrix (t) (e))snn is invertible when to, t....., by are distinct. Therefore, one can conclude that
(q Tx)2)² E span {a(r 2) : ( VIERD, Osisn,
which combined with Lemma C.12 implies that
Pv. D span (ā 2) : R2)
P + Pv. 3 p PV
which completes the proof.
Proof of Lemma 4.7 We prove the result by induction. When m = 1, the result follows directly from the R-algebraic independence of v1, U2...., , Up. Now assume that the result is true for m 1 and consider the case of m. Suppose that
0=
Σ
X I v(aj"")
Σ
Σ
X, II v(ay)d) I=1
v(am)
ji....mm
1=1
jm
ji...am
By the R-algebraic independence of U2 Up, one must have
m
Σ Ji
X II v(a)) =
jim
which then leads to X₃ = 0, Vj by the induction hypothesis.
Lemma C.14. Suppose that Assumption 4.1 and 4.2 hold and let by be the coefficient of den (e((Ma. ())
(C.15). Then there exists some i [j. j
_ j(nto) with [|:]]] S sn(n+t)) such that hg +
26

---

Proof. Let x(q) R (()))) be defined as
Xa (q) = Es [pt, (2)o
where q = (q1, Q2........ (......,.(())))) ((zz)) with qi E V. Then det (e)()())) a polynomial q of the form
det(X
Σ
Xjq'
(C.17)
where we understand qi as a (coefficient) vector R' associated with fixed orthonormal basis {ei, E21,e2...... Ep) of V that satisfies Lemma C.9 By Lemma C.13 there exists some such that (q 2), (( ( form a basis of Pv,.. which implies that
/ 0 for this q. Thus, (C.17) is non-zero polynomial in q. Let ($1, 82,..., collect all indices 8; from Lemma
C.9 Denote
+ p
S -imin
j:: x 0
1ill S nn isis
and
n + p) p
Js
j
ji S, X3 00 0, os |i:ll S 1si5
Then we have that
det(M t)) = det (x (ā(a), t), ū(a2, f), a( (99())))
Xj
ú(a
1=1
1=1
(") 1y)
Xj
(at, 1)2t O(15+1).
JEJs
where 0g (a t) (ú2.., (at, t),................ 0p.s, (at, t)) and úi (a), ... ap. t) Ei-n G1,, t t % col-
lects the leading order terms of út (ai..., ap, l). According to Assumption C.9 Lemma 4.7 we have that
Theorem 4.5) and
Σx
II
ag (a,, t)² #0,
jEJs
which provides at least one non-zero term in (a, t)) whose degree in t is
n + p
S
S sm
p
This completes the proof.
Proof of Proposition 4.4
According to Lemma C.14 there exist some with [|5i] S sn sn(")))
such
that hg # According to Lemma C.11 and Lemma 103 in [I. holds that
Em (des(a 27 )}
2 C. [t,(t) C2 Ingeliill + (+(0il++
C h ا0لا0
(C.18)
where a ~ ((=77))))(777)) for some constant C₁ depending only n, P, and for sufficiently
small t. It can be seen that
it(t) = (" Eg M(att)
27

---

By Jensen's inequality, one has that
Amin (R(())
En Amin (Ma (Maa)))a())
(C.19)
Since entries of (a, 1) are all ((1) by Lemma C.2 which implies the boundedness of the eigenval- ues Ae (M
- ...,.... ("+P). one has that
(det(M)(a. det (Ma 1o (a, S C2Amin (M)aat))aaatt)
(C.20)
Combining (C.18 C.19). and (C200), one conclude that
Amin (KC()) 2 hig(a, m) الاع
C1
[ (0m()>")
2
2
where we used |أا|| S N ("++) maxigr 8; and only considered S By Proposition C.I we have that
Amiu (K((t) - Ami (R(1)) O(
Then we can obtain
4.3 as we set I. 2sm P))
Proof of Theorem 4.3 Let C, be the constants Proposition 4.4 and consider T. It follows
from Theorem 3.5 that (a, = O, which leads to that up (A1,.... Sp: T) 0 and hence that
[NN(2; Pt) and g(x, 1) only depend on zy for all 1. 2 T. Define g(() E IR (R("(²)) via g(()) =
Ex,g(x, (2v)( )] Then according to (2.6) and (4.3 one has for T that
E(p)) - Σ B. B [all,, ()((w(a T) x))(w(( TT To))g
di
=- =-g(() ((()g(() S -Xmin(((TT))
(K(TT) 2n 20TT2m0m"") (*:") E(pe),
27min
which implies that
E(pt) S (pr) exp 222 (w) (t (t-T)).
by Gronwall's inequality. Then we obtain the desired exponential decay property by noticing that (pr) = 1,, (2)])
D Further Discussion and Characterization of Assumption 4.1 and
Theorem 4.3
D.1 Verification Assumption 4.1
We provide some verification characterization of Assumption 4.1 Without loss of generality, fix an orthonormal basis and and view that = IRP The results in this subsection are independent of the choice of the orthonormal basis.
It has been discussed in Section
4.1 that if C (R) with s 2p-1 and ( (0))
(x) (0)
are all nonzero, then Assumption 4.1 can be verified with s for h" (z) 21 + + +... 21 2p.
using the calculation [1. Proposition 33]. Similarly, the same result also true for h h=*))) C1 02 + + Gp2122 2p following.
if C1, Cp are nonzero. More generally, we have the
Proposition D.1. Let {ai, 02 "en.,,,...aaa amd be a set of pairwise distinct elements in NP that contains (1, O..., 0), (1,1,0, O).............. (0) ..., (0) are all nonzero, then
1). If E (RR with 2- and
171
ha Σ c: II Hz))))(Zy), 1=1
F=1
satisfies Assumption 4.1 with s unless (61, ......, Cm is some measure-zero subset of R with respect to the Lebesgue measure.
28

---

Proof. We assume that 01 (1, (1....... .0......,...... 0), 02 (1,1, .)........... am = (1, .,..)...))) As in the proof of Lemma C.9. Assumption 4.1 true with if and only if the matrix 9 := (st)) of full-row-ramh i.e., de * By (C.). each entry in q a polynomial in (c), C2, Cm), which implies that det( ) is also polynomial in (CI, C2 ................................ Cm) This polynomial is nonzero since it takes nonzero value at 11....... 1, 1,0.....0 0) with the p entries being I and all other entries being O, which is because that Assumption 4.1 is true for h (=) 21 21
+ 2122 Ap-
Finally, the conclusion of Proposition i. is true since the set of roots of a nonzero polynomial is of measure zero with respect to the Lebesgue measure.
D.2 Discretization Results Implied by Theorem 4.3
The discussion in this subsection similar those Appendix We slightly modified the flow P: generated by Algorithm I to guarantee some boundedness conditions, and then use the standard dimension-free estimate [19 to derive a sample complexity result implied by Theorem 4.3
We use the same bounded modification f as in (B.3) for a given constant CY > Simi-
larly, for any 8 > 0 and C > O. there exists dimension-free constant Co > depending on h", 5, C.. such that one can modify the activation function ā() = (1 ()T ā satisfying that
(L)) S C.., ||²|| ((=)))))) I Cb (R) Cg. and (L=)((o,L)) [] x) o(w 2x) x)
EE,,((..1)) [lō(w x) (w x))²] < 5, for all Idd with ||w|| S C...
The associated mean-field dynamics pt. that can be viewed as a slight modification of Pt generated by Algorithm
[ is given by (B.4) for 0 s T and follows
0.pc = V o (ele-T== = PT,
(D.1)
with
p'(0:p) = aBv-N((O.Ta) ( - (x)) o(w 8(wTx)).
[NN(2; p) = nā(w> (o(wTx))(dee x)p(da, dw),
for t 2 T. Here, the learning rate {(t) = diag(Ea Et is shared with Algorithm namely (4) = 0, e. (4) = for S L S T and (1) = 1, Em)( = for T.
The SGD associated to the modified mean-field dynamics given by
w (++1)
w/
(*x) - fNN(22: e(k))) 00 ((w( xxk)
(xx)))=))))))) rk.
(D.2)
(k+1)
(2)
a;
for i = 1,2, N and 1: = 0, ,,., ,TC,,T////. where N is the number of neurons and T/c c/c is assumed be an integer, and
(k+1)
w
wi
(D.3)
(+)
(k) a. + (f((z)) ( ā ( Txx))
for = 1,2,.... N and l = T/c
Suppose that assumptions made in Theorem 4.3 hold and fix T' > T> 0. Using similar analysis as in Appendix A.2 one can conclude that for any > 0, there exist dimension-free constants Cy and Oh such that
sup (E(p)) - E(P))
0<1ST
Applying Theorem 4.3 and [19 Theorem 1],
conclude that for any μ (0, and any 5 > 0. there exists dimension- free constants No. dg, C., such that for any N 2 No and d 2 do, the following holds with probability at least μ for any e S I-log N with T/c N:
inf /e(o,1""e]nN
((()) 8.
we further assume that N = OEed), this indicates that SGD with (D.2) and (D.3) can learn the cisspace-sparee polynomial f within finite time horizon and with ((d) samples/data points.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical results claimed in the abstract and the introduction estab- lished in Section 3 and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in the last paragraph of Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

The assumptions and the proof sketches are included in Section and Section 4 The complete proofs are in the appendices. Guidelines:
Justification:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper is purely theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer:
[NA]
Justification:
This paper is purely theoretical and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
ool for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuii wwwiiicgguie//eeeeeeee CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is purely theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is purely theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is purely theoretical and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppe///hourrr...cccaaa/////a/a
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm that this paper conforms with it in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This paper conducts fundamental research and is purely theoretical. Thus, has no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is purely theoretical and poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper is purely thcoretical and does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is purely theoretical and does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper is purely thooretical/mmathemattall and does not involve crowdsoure- ing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper is purely theoretical/mmathemaiiial and does not involve crowdsoure- ing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "o151O20n83", "reviewer": "Reviewer_nSKZ", "summary": "This paper studies how well two-layer neural networks can learn subspace-sparse polynomials using stochastic gradient descent when the input is Gaussian. It proposes a necessary condition for learning, showing that if the target function has certain symmetries, the neural network cannot learn it perfectly. The paper also provides a sufficient condition and training strategy that guarantee the loss decays exponentially fast to zero, with rates independent of the input dimension.", "questions": "No questions", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well written, with detailed explanations, proofs, and algorithms.\n\n2. It gives both necessary and sufficient conditions for when neural networks can learn these functions well, which helps understand the limits of what neural networks can do.\n\n3. The results don't depend on the dimension of the input, which means they work even for very high-dimensional data.", "weaknesses": "No obvious weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your encouraging comments! We appreciate your time and consideration.", "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": "", "extra_scores": {}}, {"review_id": "awH9KhzPWC", "reviewer": "Reviewer_7m62", "summary": "This paper considers learning a subspace sparse polynomial with Gaussian data, using a two-layer neural network trained in the mean-field regime. Their main results are two fold:\n1)They introduce a reflective property that generalizes the non- merged-staircase property from [1] to Gaussian input. They show that this condition is sufficient for the dynamics to be stuck in a suboptimal saddle-subspace for a constant time horizon.\n2) They show that a slightly stronger condition is sufficient for some modified dynamics to decay to $0$ exponentially fast.", "questions": "- Is there no hope to prove Assumption 4.1, even at the price of randomizing some coefficients of $h_*$ or $\\sigma’$ and only proving an almost sure result?\n\n- Is definition 3.1 that much different from 3.2? Except in the edge case of $\\sigma’$ identically $0$ (which is the only counterexample given), it seems that we can always condition on $z_s^\\perp$.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is reasonably well written, and provides ample details on their technical results.\n\n- The paper extends the results from coordinate sparse on hypercube, to subspace-sparse on Gaussian data (also known as multi-index models in the statistics literature).\n\n- The proof techniques are involved and require careful arguments, in particular for the algebraic independence.", "weaknesses": "- I would be careful when claiming novelty for the basis-free generalization of the merged-staircase property: as correctly pointed out in the related works paragraph, several papers [2,7,9,10] have proposed such properties. It should be easy to check that Eq. (3.2) is equivalent to [2,7,9] for leap=1. The difference is that Eq. (3.1) takes into account that the activation might not be expressive enough (see questions).\n\n- Theorem 3.4 seems to be very similar to [1] ([1] goes further and show concentration on a dimensionless dynamics, so the proof does not directly compare to a dynamics that is $0$ on the subspace)\n\n- There are several unnatural simplifications made in the algorithm. \nFirst the dynamics is actually $p$ particles that are trained independently, to avoid dealing with a PDE (then it is just an ODE on a single particle). This does not seem necessary (e.g., [1]). Is there a reason to not directly consider the PDE?\nSecond, the activation is changed between the two phases of the algorithm.\nThird, the result is proved under Assumption 4.1, which looks very much like assuming that the algorithm works (phase 1 of training is roughly this ODE, and therefore it looks like we are assuming that the dynamics converge to prove that the dynamics converge)... This seems to be a major flaw, but could be clarified during discussions. Could a smooth analysis, similar to [1] work here? (see questions)\n\n- The exponential convergence in Theorem 4.3 is confusing. When seeing such a result in the PDE literature, I assume another type of analysis, e.g., log-sobolev inequality. Here, if I am not mistaken, the exponential convergence is simply due to the fact that we switch in the second phase of the algorithm to a linear dynamics, where the kernel has eigenvalues bounded away from 0.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your helpful and insightful comments and questions. Please find our responses below:\n* __Connection/difference between the reflective property (equations (3.1)-(3.2)) and $\\textup{IsoLeap}(h^*)>1$ (Abbe et al. 2023):__\n    * Our conditions (3.1) and (3.2) are more general than $\\textup{IsoLeap}(h^*)>1$ in the sense that (3.1) and (3.2) can be extended straightforwardly to general function $h^*$, while $\\textup{IsoLeap}(h^*)$ can only be defined for polynomial $h^*$.\n    * If we only consider a polynomial $h^*$, then it can be prove that $\\textup{IsoLeap}(h^*)>1$ implies (3.2). However, we currently do not know whether (3.2) implies $\\textup{IsoLeap}(h^*)>1$ or not.\n    * (3.1) is different from (3.2) and $\\textup{IsoLeap}(h^*)>1$ when $\\sigma$ is less expressive. In our original submission, we give a counter-example with $\\sigma(\\zeta) = \\zeta$, but this is not the only example. There exist other counter-examples with more expressive $\\sigma$. In fact, for any $n\\geq 2$, consider $h^*(z) = \\textup{He}_1(z_1)+\\textup{He}_n(z_1) \\textup{He}_1(z_2)$ and $\\sigma(\\zeta) = \\zeta^n$. Then it can be verified that (3.1) is satisfied while $\\textup{IsoLeap}(h^*)=1$.\n* __Connection between Theorem 3.4 and Abbe et al. (2022):__ The goal of Theorem 3.4 is to generalize the result in Abbe et al. (2022) to the rotation-invariant setting. Therefore, the statement of Theorem 3.4 is similar to Abbe et al. (2022). However, the proofs are significantly different since Abbe et al. (2022) analyze the dimension-free dynamics and we do not use that. We directly show that the flow cannot learn any information about $S$ by connecting it with a flow in $\\mathbb{R}\\times S^\\perp$.\n* __Some explanations for Algorithm 1:__\n    * In Algorithm 1, we need to repeat Step 2 for $p$ times, and for each time the flow is an interacting particle system, where the whole system is described by a PDE and the dynamics of a single particle in the interacting system is described by an ODE. Therefore, Step 3 does not train $p$ particles independently, but trains $p$ interacting particle systems. Compared to training only one interacting particle system as in Abbe et al. (2022), we need to repeat this step to lift the linear independence to the algebraic independence.\n    * You are correct that we change the activation function in Step 4. We want to mention that this is somehow acceptable as in existing literature (see Abbe et al. (2022)).\n* __Exponential convergence in Theorem 4.3:__ You are correct that the exponential convergence is from linear dynamics, i.e., the second phase. This idea is standard as in many existing works including Abbe et al. (2022). The most difficult part is to prove that the eigenvalue of the kernel matrix has a positive lower bound.\n* __Verification of Assumption 4.1:__ It is very difficult to directly verify Assumption 4.1 in general. But there are several cases that are manageable and we will let you know if we figure out a more general case during the discussion period.\n    * If $h^*(z) = c_1 z_1+c_2 z_1 z_2 + \\cdots + c_p z_1 z_2\\cdots z_p$, then Assumption 4.1 can be proved with nonzero coefficients $c_1,c_2,\\dots,c_p$.\n    * If $h^*(z) =  \\sum_{s\\in\\mathcal{S}} c(s) \\prod_{i=1}^p He_{s_i}(z_i)$, where $\\mathcal{S}$ is a finite subset of $\\mathbb{Z}_{\\geq 0}^p$ with $(1,0\\dots,0),(1,1,0,\\dots,0),\\dots,(1,1,\\dots,1)\\in\\mathcal{S}$, then Assumption 4.1 can be proved in the almost sure sense when $c(s)$ are randomly generated (e.g., from iid Gaussian) for all $s\\in\\mathcal{S}$.", "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": "", "extra_scores": {}}, {"review_id": "tLGPLio1EL", "reviewer": "Reviewer_kar1", "summary": "This manuscript extends previous work on learning sparse polynomials on the hypercube to Gaussian space. To achieve this, the authors introduce a generalization of the merged staircase property studied in previous work. Specifically, they demonstrate that their \"reflective property\" is necessary to learn polynomials in O(1) time, while a slightly stronger condition, defined in Assumption 4.1, is sufficient for learning.\n\nAs is common in the literature, the authors propose a two-stage training process. First, they train the input layer while keeping the output layer fixed. After learning the representation, they fix the input layer and train the output layer to learn the link function.", "questions": "The authors did not discuss their \"Reflective property\" in the context of leap complexity suggested in [1]. It is known that the merged staircase property corresponds to leap 1 functions. In this sense, is there a way to relate the reflective properties with the leap complexity?\n\nAdditionally, in the definition of the \"Reflective property,\" they require the condition to hold for any shifted version of the activation (i.e., for any $u \\in \\mathbb{R}$  in Definition 3.3). However, in Theorem 3.5, they did not use a bias in the activation. What is the reason for this discrepancy?\n\nFurthermore, I am not familiar with the terminology of Dirac delta measure defined on a subspace, and I could not find its definition in the paper either. Could the authors include this definition in the revised version of the paper?\n\n[1] Abbe, E., Boix-Adserà, E., & Misiakiewicz, T. (2022). The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks. ArXiv, abs/2202.08658.", "limitations": "See the Weaknesses part.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the work effectively extends the previously studied merged staircase properties to a basis-independent setting. The manuscript is well-written and contributes valuable insights to the multi-index setting, which is an active area of research in the neural network theory community.", "weaknesses": "The main weakness of the proposed algorithm is its requirement to run the training algorithm several times to average the weights and change the activation function in the second stage, which differs significantly from practical training algorithms. At the same time, existing work addresses this issue with random feature approximation in the second stage, though this is also not an ideal solution. Therefore, the question of whether we can train input-output layers together remains an open problem in the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your helpful and insightful comments and questions. Please find our responses below:\n* __Connection/difference between the reflective property (equations (3.1)-(3.2)) and $\\textup{IsoLeap}(h^*)>1$ (Abbe et al. 2023):__\n    * Our conditions (3.1) and (3.2) are more general than $\\textup{IsoLeap}(h^*)>1$ in the sense that (3.1) and (3.2) can be extended straightforwardly to general function $h^*$, while $\\textup{IsoLeap}(h^*)$ can only be defined for polynomial $h^*$.\n    * If we only consider a polynomial $h^*$, then it can be prove that $\\textup{IsoLeap}(h^*)>1$ implies (3.2). However, we currently do not know whether (3.2) implies $\\textup{IsoLeap}(h^*)>1$ or not.\n    * (3.1) is different from (3.2) and $\\textup{IsoLeap}(h^*)>1$ when $\\sigma$ is less expressive. In our original submission, we give a counter-example with $\\sigma(\\zeta) = \\zeta$, but this is not the only example. There exist other counter-examples with more expressive $\\sigma$. In fact, for any $n\\geq 2$, consider $h^*(z) = \\textup{He}_1(z_1)+\\textup{He}_n(z_1) \\textup{He}_1(z_2)$ and $\\sigma(\\zeta) = \\zeta^n$. Then it can be verified that (3.1) is satisfied while $\\textup{IsoLeap}(h^*)=1$.\n* __Definition 3.2 and Theorem 3.5:__ We understand that it is a bit confusing that we use $u+v^\\top z_S^\\perp$ in Definition 3.2 and use $w^\\top x_S^\\perp$ without bias term in Theorem 3.5. The reason can be seen in line 479-480, where we write $w^\\top x_S^\\perp = w^\\top x_V^\\perp + w^\\top (x_V-x_S)$. Then $w^\\top x_V^\\perp$ is the bias term $u$ and $x_V-x_S$ is the orthogonal complement of $x_S$ in $V$, corresponding to $z_S^\\perp$ in Definition 3.2. We will make this point more clear in our revision.\n* __Delta measure on a subspace:__ For a subspace $S$, the delta measure $\\delta_S$ is a probability measure on $S$ such that for any continuous and compactly supported function $f:S\\to\\mathbb{R}$, we have $\\int_S f(x)\\delta_S(dx) = f(0)$. We will add the definition in our revision.", "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": "", "extra_scores": {}}, {"review_id": "1ePdIbgZjk", "reviewer": "Reviewer_JjNH", "summary": "This submission studies the training dynamics of a two-layer neural network in the mean-field limit, when the data is isotropic Gaussian and the target function is a low-dimensional multi-index model. The authors consider the population gradient flow on the squared error, and identify a \"reflective property\" that is necessary for GD to learn the target function in finite time. A multi-phase gradient-based training algorithm is also proposed to demonstrate that such property is (almost) sufficient for GD learnability. This provides a coordinate-free generalization of the merged staircase property (MSP) in (Abbe et al. 2023).", "questions": "See Weaknesses above.", "limitations": "See Weaknesses above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main contribution of this submission is the introduction of the reflective property of the target function which entails whether the parameter distribution evolved under the mean-field gradient flow can achieve nontrivial overlap with a given subspace in finite time. This \"basis-free\" extension of MSP to Gaussian data is an interesting result.", "weaknesses": "I have reviewed this paper in another venue. The authors addressed some of my concerns in the revision.  \nI shall reiterate the remaining weaknesses from my previous review. \n\n- This submission only analyzes the mean-field dynamics up to finite time. If $T$ scales with the dimensionality, then it is known that SGD can learn functions with higher leap / information exponent; these functions may not satisfy the reflective property, yet the mean-field dynamics can achieve low population loss. I do not hold this against the authors since this point is already acknowledged in the main text. \n\n- The learning algorithm in Section 4 is non-standard as it requires an averaging over trajectories and a change of activation function during training. Moreover, the authors do not present any learning guarantee for the discretized dynamics, and therefore a sample complexity cannot be inferred from the analysis. \n\nAfter reading the revised manuscript, my main concern is that the relation between the proposed reflective property and prior definitions of SGD hardness (in the Related Works paragraph starting line 73) is not clearly explained. Specifically, the authors only listed the alternative rotation-invariant conditions on SGD learnability, but did not discuss the advantages of the proposed definition. \n\n- Is the reflective property equivalent to isoLeap > 1, if we do not take the activation $\\sigma$ into account (that is, assuming $\\sigma$ is sufficiently expressive)? If not, how does it differ from the sufficient conditions in (Abbe et al. 2023) (Bietti et al. 2023)? More explanation is needed. \n\n- The authors brought up the even symmetry condition in (Dandi et al. 2024), which does not exclude high isoLeap functions. In fact, (Lee et al. 2024) (Arnaboldi et al. 2024) have shown that any non-even single-index functions can be learned by variants of online SGD in $T=O(1)$ time horizon (and the discretized dynamics require $n=O(d)$ samples). The authors should clarify if this is consistent with the proposed necessary condition for SGD.  \n(Lee et al. 2024) *Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit*.  \n(Arnaboldi et al. 2024) *Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your helpful and insightful comments and questions. Please find our responses below:\n* __Connection/difference between the reflective property (equations (3.1)-(3.2)) and $\\textup{IsoLeap}(h^*)>1$ (Abbe et al. 2023):__\n    * Our conditions (3.1) and (3.2) are more general than $\\textup{IsoLeap}(h^*)>1$ in the sense that (3.1) and (3.2) can be extended straightforwardly to general function $h^*$, while $\\textup{IsoLeap}(h^*)$ can only be defined for polynomial $h^*$.\n    * If we only consider a polynomial $h^*$, then it can be prove that $\\textup{IsoLeap}(h^*)>1$ implies (3.2). However, we currently do not know whether (3.2) implies $\\textup{IsoLeap}(h^*)>1$ or not.\n    * (3.1) is different from (3.2) and $\\textup{IsoLeap}(h^*)>1$ when $\\sigma$ is less expressive. In our original submission, we give a counter-example with $\\sigma(\\zeta) = \\zeta$, but this is not the only example. There exist other counter-examples with more expressive $\\sigma$. In fact, for any $n\\geq 2$, consider $h^*(z) = \\textup{He}_1(z_1)+\\textup{He}_n(z_1) \\textup{He}_1(z_2)$ and $\\sigma(\\zeta) = \\zeta^n$. Then it can be verified that (3.1) is satisfied while $\\textup{IsoLeap}(h^*)=1$.\n* __Discretized dynamics and sample complexity:__ There have been standard results (see e.g. Mei et al. (2019)) that bound the distance between the SGD and the mean-field dynamics. To apply the results of Mei et al. (2019), one needs the boundedness of $f^*$ and $\\sigma$. However, in our work, $f^*$ and the second activation function $\\hat{\\sigma}$ in Algorithm 1 are bounded, which is the reason that we did not give a sample complexity result in our original submission. Recently, we realized that a sample complexity result can be derived as follows and we will include such analysis in our revision.\n    * Step 1: We slightly modify the mean-field dynamics by replacing $f^*$ and $\\hat{\\sigma}$ by $\\text{sign}(f^*)\\min(|f^*|,C_f)$ and $\\text{sign}(\\hat{\\sigma})\\min(|\\hat{\\sigma}|,C_{\\sigma})$ that are both bounded. $C_f$ and $C_{\\sigma}$ are dimension-free constants guaranteeing that the distance between the original dynamics and the modified dynamics is smaller than $\\epsilon$. Let us remark that $C_f$ and $C_{\\sigma}$ can be chosen as dimension-free since $f^*$ is subspace-sparse and dynamics in Algorithm 1 does not learn any information about $V^\\perp$.\n    * Step 2: Apply the standard results in Mei et al. (2019) to the modified dynamics and then obtain the sample complexity for SGD.\n* __Some explanations for Algorithm 1:__ We agree with you that taking the average in Algorithm 1 is non-standard. The reason is that we want to lift the linear independence to the algebraic independence. For the change of activation function in Algorithm 1, we find it is somehow acceptable in the existing literature (see Abbe et al. (2022)).\n* __Consistency with Lee et al. (2024) and Arnaboldi et al. (2024):__\n    * Lee et al. (2024) require a sample complexity $\\mathcal{O}(d\\cdot \\text{polylog} d)$. So the training time is not constant, due to the $\\text{polylog}d$ term. Our work always considers a finite training time $T$ and we definitely agree that SGD may learn a larger family of functions if we allow the training time to scale with the dimension $d$.\n    * Arnaboldi et al. (2024) analyze a variant of SGD, not the original SGD. Our necessary condition considers the mean-field dynamics corresponding to the original SGD.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers initially raised several important concerns and the extensive responses of the authors have partially addressed them, which lead the reviewers increase their scores. Given all the material (paper, reviews, rebuttal and discussion), I am recommending an acceptance by trusting the authors that they will implement all the promised changes and clarifications one by one (there are many points to be clarified & elaborated as revealed during the discussion period). Please make sure you go over all the requested changes carefully and update the camera-ready version accordingly.
Decision: Accept (poster)