The Computational Advantage of Depth in Learning High-Dimensional Hierarchical Targets
Authors: Yatin Dandi
Luca Pesce
Lenka Zdeborova
Florent Krzakala
Venue: NeurIPS 2025 spotlight ()
Keywords: feature learning
sample-complexity
depth
multi-layer
Primary area: deep_learning
TL;DR: multi-layer networks perform hierarchical learning through multiple levels of dimension reduction,  surpassing shallow networks.

Abstract: Understanding the advantages of deep neural networks trained by gradient descent (GD) compared to shallow models remains an open theoretical challenge. In this paper, we introduce a class of target functions (single and multi-index Gaussian hierarchical targets) that incorporate a hierarchy of latent subspace dimensionalities. This framework enables us to analytically study the learning dynamics and generalization performance of deep networks compared to shallow ones in the high-dimensional limit. Specifically, our main theorem shows that feature learning with GD successively reduces the effective dimensionality, transforming a high-dimensional problem into a sequence of lower-dimensional ones. This enables learning the target function with drastically less samples than with shallow networks. While the results are proven in a controlled training setting, we also discuss more common training procedures and argue that they learn through the same mechanisms.  These findings open the way to further quantitative studies of the crucial role of depth in learning hierarchical structures with deep networks.

The Computational Advantage of Depth in
Learning High-Dimensional Hierarchical Targets
Yatin Dandi Luca Pesce', Lenka Zdeborová', and Florent Krzakala'
Inforration,, Learning and Physics Laboratory. Ecole Polytechnique Fédérale Lausanne (EPFL), CH-10015 Lausanne, Switzerland.
"Statistical Physics of Computation Laboratory. Ecole Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland.
Abstract
Understanding the advantages of deep neural networks trained by gradient de- scent (GD) compared to shallow models remains an open theoretical challenge. In this paper, we introduce a class of target functions (single and multi-index Gaussian hierarchical largets) that incorporate a hicrarchy of latent subspace dimensionalities. This framework enables us to analytically study the learning dynamics and generalization performance of deep networks compared shal- low ones in the high-dimensional limit. Specifically, our main theorem shows that feature learning with GD successively reduces the effective dimensionality, transforming a -igh-dimensional problem into sequence of ones. This enables learning the target function with drastically less samples than with shallow networks. While the results are proven in controlled training setting, we also discuss more common training procedures and argue that they learn through the same mechanisms.
Understanding the computational benefits of deep neural networks over their shallow counterparts central question in modern machine learning theory [76 87.. While shallow models can approximate any complex functions [27]] deep networks almost universally exhibit remarkable advantages in practice [49 There has been much progress in approximation theory on the
68] and reference therein), however, the dynamics of learning with gradient descent more complex question. A fundamental open problem thus:
advantage of depth (see e.g. 62
79
61
Can one quantify the computational advantage of deep models trained with gradient-based methods with respect shallow models in some analyzable setting?
One line of work on GD-based methods in deep networks leading interesting results is in the setting of deep linear network sse e.g. 73
40) While deep linear networks offer valuable insights into nonlinear learning dynamics, their simplicity renders them insufficient to capture the complexity of hierarchical feature learning.
46
12
51
Another popular line research is to study the dynamics of gradient-based methods learning multi- index functions with shallow models [99 17 39
22 1 [1]. Multi-indes functions provide a rich class of targets, but their efficient learnability by shallow two-layer networks [|] undermines their utility as benchmarks for understanding the computational advantages of depth. This motivates the following consideration:
What is the natural model of targets to consider for understanding the emergent computational advantage of depth when training with gradient- bassd methods?
The present paper addresses both these questions. To answer the latter, we introduce a class of target functions designed to probe the hierarchical structure and computational potential of deep networks. These Multi-Index Haussian-HHerachiee Target (MIGHT) functions encapsulate a hierarchy of latent subspaces with varying dimensionalities. We then proceed to answer the former interrogative
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

by analyzing the learning dynamics of multi-layer neural networks on such targets, providing characterization the computational advantages afforded by depth. We show how depth enables a hierarchical decomposition of tasks, reducing the effective dimensionality at each layer, and leading to quantifiable improvement in sample complexity over shallow models.
Hierarchical Targets and Main Results
1.1 Single-Index Gaussian Hierarchical Targets
Our simpler setting, where the task using Gaussian i.i.d data {x,]==1 E Raxd_ to learn the following Single-Index Gaussian Hierarchical Target (SIGHT) function class that we write in three equivalent forms as:
(x)) = g"
a
Pa (W Vdti
x R
(1)
g"
a'
Pk (z*)
= W'x E Rd1
(2)
Vdei
-g'(h"), h" =" -x (z ER.
(3)
Here Ps is fixed polynomial applied component-wise, and d denotes the dimensionality of the second-layer features (non-linear features) in the intermediate layer, which we choose to be e1 E (0,1), The first-layer features (linear features) are zt W*x, where W* Rxd has orthonormal unit vectors as rows, and a* Rd4t is choosen randomly from a fixed distribution. We refer to the variable Ae" as the index in the name of the class. This construction, a generalization of the hidden manifold model [43] is motivated by the compositional structure present in real-world functions and by the analysis carried over by 88 66]. The strictly decreasing dimensionality of the features across depth allows to avoid the pitfall of the original hidden manifold model 43 that
turns out to be equivalent to Gaussian linear target 41 45 64
1.2 Multi-Indes Gaussian Hierarchical Targets
simple generalization of the above construction is include many non-linear features, leading to Multi-Index Gaussian Hierarchical Targets (MIGHT) defined as:
f"(xx g" (x))x)..... hx))))
(4)
where
1 (x)
Vde am Pk.m x)), m l,...r,
(5)
with now directions, each with their own layer weights (am and Wit), and polynomials (P& (P.,m).
Deep Multi-Index Hierarchical Targets
Finally, we define the deep version of MIGHTs
(*(x = g" (x), (x)(
(6)
with Gaussian data {x,} Rd, and where each features h (x) E R-4 are recursively defined as:
h (2)m(x)= = Vder-1-e1 aj .l (h: (D1-1,,14((-1)))-----
(x))
(7)
with l 1... L, m 1 1...dee
d and where at.m E - acts on the mea block of the previous layer feature h (x) (each of them being of size d Again Pk.me are fixed polynomials d denotes the dimensionality of the features at layer L, which we choose to be strictly decreasing across depth, ie., 1 > E1 >> 52 > ... > EL-1 > O, with hj E IR" being dineesooanniin.l... This "tree-like" construction ensures that for any layer index / E 1,..., L, the
for 1= 1.. 1--1;
hidden features hi,m(()) remain independent for different index m E ".....d" (Appendix D.1
Finally, the llayr features are defined as 2x==
(8)
where W* E ER has orthonormal unit vectors rows. By explicitly incorporating multiple levels of non-linear feature transformations, each associated with a progressively reduced latent dimensionality, it models the deep hierarchical structure is feature of complex real-world tasks, see e.g.
24 [4] We exemplify SIGHT [1) and MIGHT (4) functions Fig, 3 and their deep version 6, where the tree structure of the deep version of these targets is apparent, in Fig.
55 49
65

---

1.4 Learning Model
Generalization Error
(8)
We now consider learning SIGHT and MIGHT func- tions f* (x) through an L-layer neural network, that is a standard multi-layer perceptron:
Random guess
Lazy/Kemel
ZLLN
fx(x) = by b
a ob, Wi (x(x))) (9)
log
where denotes the ensemble of trainable param- eters (b,, We, é = 1...L) L). The hidden layer weights have dimension We RPEXP-- for & (2, (2..... . L - 1 with readout layer Wy E R and first layer W1 E RPixd and the biases by are in R We shall consider Empirical Risk Min-
Generalization Error
(b)
Fandom guess
Lazy/Kemel
2LLN
JLLN
log
log
1.5
imization (ERM) of the square loss R(xxx))
Figure An illustration of the phase tran- sitions in learning SIGHT according to the main Theorem dennoting the computational advantage of depth for two different target model: (a) generic shallow SIGHT function (eq. ①1) and (b) the example in eq. (11.
Ex= (f'x))) - fo(x)))
with gradient descent.
1.5 Main Results in Nutshell
The backbone of our results is the analysis of the asymptotic performance of learning SIGHT and MIGHT functions using multi-layer networks trained with Gradient Descent on Gaussian data, as both zi (the number of data) and d (the dimension of the data) grow to infinity. We unveil a series of sharp thresholds in the sample complexity ratio log where neural networks learn the target with increasing accuracy. To summarize: log
Our targets offer solvable playground to unveil the computational advantage of deep networks over shallow ones. The learning mechanism can be viewed as the reduction of the "effective dimension" in which networks trained on (xx successively reduces the dimensionality of the search space: d + d== + d'a,... ..... - r. Depth acts as a progressive filter that distills data into lower-dimensional representations physics), enabling the learning of subsequent layers.
hoarse-graining mechanism akin to renormalization in
We focus the rigorous analysis in the paper on the case of shallow SIGHT functions (eq. 11) learned by 3-layer networks, where each layer is trained sequentially and independently. We prove that three-layer network trained in a layer-wise fashion can learn a SIGHT function (x) efficiently. Specifically, the network first recovers W* using ((d samples, then reconstructs h² with (dde)) samples (with & denoting the degree of Pk. case kεj < 1 + &1 both happen at 1 1+ E1), and finally fits f* as a function of h* using only Ó(1) samples. This sample complexity fooars--graiiing perspective, where earlier
aligns with predictions from the layers successively reduce the effective dimensionality of the learning problem. We also present additional results for deeper targets and networks.
We further explore the problem through numerical simulations using more realistic training procedures than those covered by the theorems. Our results suggest that the dimensionality reduction mechanism remains broadly applicable. Notably, we illustrate such a phenomenon using 3-layer networks training all the layers jointly with standard backpropagation. We provide the code of our simulations at httpss:/ggituub.oo. IdcPHICSePPHoniii CoMIII///CCmmuuttooanDppppp
1.6 Related Works
Random Feature Models- - A key attribute enabling the effectiveness of neural networks is their ability adjust to low-dimensional features present in the training data. However, inter- estingly, much of the current theoretical understanding of neural networks comes from studying their lazy regime, where features are not learned during training. One of the most pre-eminent examples of such "fixed-features" regimes are Random Feature (RF) models, initially introduced as a computationally efficient approximation kernel methods by [69], they have gained attention as models of two-layer neural networks in the lazy regime. One of the main motivations is their
sharp generalization guarantees in the high-dimensiionl limit 38 42 58 however, the performance of such methods, and of any kernel method in general, is limited. A fundamental theorem in 58 states that only a polynomial approximation up to degree ERF of any target f*, with KRF (ii(KK1, K2) when learning with d data and p d features.
86 34
As mentioned,
3

---

While even shallow networks can surpass these limitations a fundamental role in our analysis.
40 17 31
this relation for KRF plays
Multi-index Models- Despite the theoretical successes in describing fixed feature methods, the holy grail of machine learning theory remains a rigorous description of network adaptation to lowddimensional features. A popular model to study such low-dimensional structure in the learning performance is the multi-index model. For this class of target (denoted as fM)). the input datum x
is projected on a r- diimensional subspace W = :J E 1 1...r) and the input-output relation depend solely on a non-linear map g" of these (linear) features:
[x(()) = "x"'ii,......... wi...., w);
(10)
While the information theoretical performance is well understood [8 14 there has been intense theoretical scrutiny to characterize the sample complexity needed to learn multi-index models with shallow models. On the one hand, kernel methods can only learn a polynomial approximation [58]; the other hand, the situation in neural networks appears more complicated at first as the hardness of a given Mi has been characterized by the "information" " and "leap" exponents 52 77 [3]. It was shown, however, that simple modification of vanilla Stochastic Gradient Descent (SGD), such as Extra-Gradin methods or Sharpness Aware Minimizers, are able to attain sample complexity corresponding to Statistical Query (sQ) lower bound [ [2]. and are essentially optimal up to polylog factors in the dimension [28 81 A motivation of the present work is to go beyond such limitations and analyze hierarchical feature learning.
19 2 30 28
Substantial effort has been devoted to investigating the approximation ad- vantages conferred by deeper neural network architectures 77 36 70] However, it remains unclear how these approximation gaps translate into sample complexity ones for neural networks when trained through gradient descent. An important step towards the role of depth in neural networks has been carried over by 84 66). who proved separation results between the test performance of & 3 layer networks. More precisely, [4]] proved that 3-layer architectures with a fixed first layer can learn a target function of the form g g'(x" Ax) in n = O(d') samples through single-gradien step on the second layer, where x E Rd and A E Rdxdd In contrast, 2-layer networks require a super-polynomial number of samples in terms of the degree g". 666] subsequently improved the sample complexity to Ó(d²) and generalized the result to functions of pu. -order polynomials. [37] further extended these results to learning muutiple-nonlineer features. We go beyond these results to prove stronger separation results by analyzing fully trained networks without a fixed first layer.
3-Layers Networks
The dimensionality reduction we describe is closely related to the concept of learning features across different scales. This idea has been explored in the context of machine learning through connections with the renormalization group 885 in physics. where each scale corresponds to a distinct set of features. Such techniques have inspired studies of deep neural networks 57 53 56 Here, we present concrete example of such a coarse- heare-grriiiig mechanism, illustrating how hierarchical structures can be analyzed explicitly.
Coarse-graining
Hierarchical data models - A key insight in explaining the superiority of deep over shallow networks is that depth enables neural networks progressively reduce the effective dimensionality of the learned data representation [80 5 3 72
8 35 23 This aligns with the latent hierarchical structure observed in real-world data, which deep models exploit through layer-wise composition. Leveraging these observations, the construction of hierarchical data models has been central in theoretical analysis [65
23 Tree-like structures analogous to our SIGHT ①I) and MIGHT 4 are considered in 68 leading to provable approximation benefits across depth. More generally,
75
24
67 linked compositional sparsity to efficient computability. Since learnability subsumes computability, such computational sparsity is expected to be necessary for efficiently learnable functions, further supporting our construction. However, since efficiently learnable functions form strict subset of computable functions, functions learnable by gradient descent must possess additional structure on top of being compositions of local/sparse functions. Our class of targets shows that one such additional structure is obtained by insuring sufficient regularity/stabilit w.r.t intermediate features at each step. In our setting, such regularity is ensured by the presence of low-degree dependence on lower level features. This mirrors the dependence structure in real data, where for instance, the target labels for images/language datapoints have direct correlations with low-level features such as edges or bi-gram, trigram counts. Results supporting the benefits of deepth for tree-like hierarchical models have been provided by 65 and [ who consider
stre-structured inputs, in contrast to our focus on structured targets (but non structured input).
4

---

Universality- - A crucial role in our analysis is played by the asymptotic Gaussianity of h (x) which leads simplified description of how dependencies on h (x) propagate to lower-level features. Such a property is a crucial component of the analysis in 66 84] Specifically, 666 84
showed that the projection of g" ((Hex(x); A}) on degree-k k Hermite polynomials lies along the non-linear feature (He, (x), A) while g has vanishing projections on lower degree terms. We generalize these results to describe the projections on all degree components.
2 Heuristic argument underlying the main results
Before presenting the main technical results, we describe here a heuristic argument describing the narrative behind the results. For concreteness, we focus here on learning shallow SIGHT function
(1) as a first step toward broader understanding. For concreteness, we will discuss the following example (later used in Fig. P):
aa'" P3 (W*) dd=i=1/2
(x) = tanh
(11)
with polynomial P3(x)
He)(2) + Heg(2) (the second and third Hermite polynomials), é1 = 1/2, and discuss the performance of different learning architectures, highlighting the dimensionality reduction due to feature learning, The learning dynamies for general SIGHT (eq. (1) and the particular example above (eq. (11) are illustrated in Fig. respectively in the top and bottom panel.
a) Kernel methods, or random feature models, can only learn polynomial approximation of degree K in the Hermite basis of f if n (dd) [88. This is a strong limitation that leads to poor performance as the learning method is not sensitive to the presence of relevant low-dimensional structure, but rather only to the degree of the target. the example (1)), the lowest (Hermite) polynomial order is quadratic in x (as can be seen by expanding the tanh): learning it thus requires n = OdP) samples of data for kernel method beat random performance. Learning the cubic approximation would requires in orange in Fig. [
(dd) samples, etc. The corresponding thresholds are sketched
b) We now turn to two layer net of the form (we do not write explicitly the additional biases for clarity) with a number of neurons at least of order ((d +6)
fo (x) = w (x)
(12)
Thanks to feature learning, such architecture should perform better; Indeed, for W1 to learn the d x d first-layer feature matrix W', we need at least = O(d x d=t) data. If >> d'+61, we thus expect that W1 correlates with W*, Intuitively. W1 is then close to noisy random rotation of W' and behaves roughly as W, & W + Ze (with Z₁ and Z2 are essentially random matrices). The two-layer neural net thus now behaves as:
fo(x) = WT (Zzz² + Zz).
(13)
Fitting now the outer weights wa leads, once again, to random feature model, but now applied to the
target eq. (2) seen as function of instead of eq 11 seen as a function of x. This leads to an effective
Random Feature model with respect to the lower dimensional vector {z" E Rdd }. Thanks to this dimensional reduction from dimension d to the effective one d=, we just need of data to now fit a K K-th degree polynomial approximation of f* This is a drastic improvement. Coming back to the example: with
(d )" samples
O(d Odd++e1=l.),, K 1.5, data samples two-layer net learns the first layer representation W*, leading to a dimensionality reduction from vd. From n Oddee==1.)) 1,) K = 1.5, we are also able to fit a (Hermite) polynomial approximation of degree 3 of the target viewed as function of z. The next order in the expansion of (11) is power 6 in and thus will be fitted at A = 3. We discuss the extension of the above arguments to two-layer networks trained with a general gradient- baased algorithm App. B.
c) We now finally consider a three-layer neural networks, with width P2 Pi = O(dhe1+0)
fo(x) = w. (W2oo(11)))
(14)
We still expect that W, learns the first-layer features W when > dl+e1, which point:
fo(x) oWoo (Ziz² + Za))
(15)
However, contrary to the previously depicted shallow case, three-layer networks can further approximate ht' by updating the second layer. With each power of d expect to be fit an
5

---

additional power approximation of h" and, in particular, with n = Oddhs1,, we expect the second layer preactivation hx(xx) (W to correlate completely with the (k- polloyynomia)) features h.. Therefore, denoting again Z4, Z5 as random matrices, 3-layer network now acts as:
fo(x) R w3. (Zah* + Zs)
(16)
Fitting now W3 leads a random feature model on the scalar h, which can be fitted perfectly with any growing number of samples n. In other words, through successive coarse-grainin from d= =d==dvvd-1, we have reduced the dimension from diverging one (d) to finite one.
Note that generalization error as plotted in Fig. can jump for two reasons as n increases: either because of reduction of the dimension deff, because of an increase of polynomial fitting power within this dimension. The phenomenology a bit simpler in the particular example [1] where the advantage of three-layer net is considerable: for = O(d..5), the network learns to represent the non non-linear features h* directly, and thus can learn the entire function.
While such parameter counting sounds reasonable, this heuristic may fail for general data distribu- tions, as high-degree polynomials may localize on low-dimensional structures and develop heavy tails. However, for Gaussian and spherical measures, isotropy and hypercontractivity ensures that such polynomials remain delocalized and well-concentrated [Lemma 5) Our analysis relies on proving that such a property holds under feature learning, and even for deep non non-linear hidden features.
This scenario, illustrated in Fig. I extends mutatis mutandis to generic deep multi-layer MIGHT functions, where sequence of transitions emerges progressively across the layers. Consider for instance the following hierarchical target function from eq. (see also Fig, 4
a² Per (h3) Vd
aa.m Pk (hi = W W*x) (1+ 1)
('(x) = =anh
h22m =
md 22)
v /dE--22
In this case we expect reduction from + + The first one arises at n = +(d when learning W* then at Oddeet=22) (to learn all the d polynomials, each of them requiring dh data) and finally at n = (d =²) ) to learn the activation in the tanh (a single k polynomial in dimension 2) Note that while these must proceed in this order, some of these jumps can happen at the same value of K. For instance, if K < kee + E2, then the last two jumps arise simultaneously.
Main Theoretical Results
We now turn to the main part of our results that describe learning of the SIGHT and MIGHT function classes with deep neural networks trained by gradient descent. We present rigorous analysis of gradient- based Empirical Risk Minimization (ERM). Since a complete rigorous analysis of gradient descent in deep networks is extremely challenging and hitherto elusive- we first present a rigorous description for the SIGHT target of eq. ①1) under a specifie deep-learning schedule. This approach enables to provide precise theorems that capture the hierarchical learning process. We analyze the following training procedure:
Initilization: The parameters of the model (x) wi] (W1)( are initialized as Wi,1 U(8)-1(1)) for i E [Pi], W₂ = Ip and W3,4 = for i E (p), where U(8d-1(1) denotes the uniform distribution on the unit sphere in Rd
Layer-wise training: (i) We first perform a pre-determined number Ti of gradient updates on the first layer Wi on independent batches of data for each step 30. (ii) Subsequently, we re-initialize the second layer W2 do a single large gradient step. (iii) Finally, we update W3 through ridge regression. Layer-wise training procedures are common simplifying assumption in the analysis of two-layer networks [29 30 A complete analysis of the joint training remains open even for two-layer networks except for training of layers at differing time scales [20] 22 An interesting direction for future work is to rigorously show separation results between deep and shallow networks by constructing targets where joint training of the layers provably surpasses layer-wise training. A first attempt in this direction was considered in 771 who illustrated the advantage of joint-training through the mechanism of "backward feature correction".
Neuron-wise spherical projections: While updating the first layer parameters Wi, utilize spherical gradient and project each neuron onto the unit sphere. Such spherical projections are commonly utilized in the literature on two-layer networks [].
-aberical-gradeent

---

Pre-conditioning of gradient for the second layer: We use a pre-conditioning of the gradient step broadly used various optimization schedules (e.g. Adam 477) using the sample-covariance of the features as preconditioning matrix, i.e.,
AW2 = --( )
Through the feature map x + ((Wix), the updates of W2 in parameter space translate to updates to (x2x) in function space. Without such pre-conditioning online SGD leads worse sample complexity of (d as in the single-step analysis of [[6]] as we explain further in Appendix C.16 Although pre-conditioning plays an important role in the proof scheme, we argue that the core of the results hold in more realistic routine in Sec. 5
With this algorithm, we can now study gradient descent and demonstrate the learning of class of SIGHT function. The theorem will assume the following conditions:
Uniform weighting: We set {ap = 1 for all E E-11-- 1. J: This operation ensures isotropic dependence along all components, simplifying the analysis. While o 1 is particular choice of target weights, the training algorithm of the model is agnostic to this choice and we, therefore, obtain
sample-complexity expected for a general non-linear feature of the form a' Pk (W*)) des.
Information exponent: We shall indeed require that the information exponent 19 of
g (+) is and that of (-) is 2:
Assumption 1. Let 2 ~ N(0, 1) denote standard normal variable. We assume that E (z)= 7f 0,
E [Px(2) (e)) o 0.
The condition on 9*( (.) is necessary, as gradient descent (without repetition) has a drastic worst
complexity for exponents larger than We expect however, that the condition on Px(+) can be relaxed to information eexpontennnexooenttt 2 2 instead of being exactly
2. The information exponent of P& being results in linear components that do not require recovery of the full subspace spanned by W Thus setting the information exponent of Px (-) to 2 simplifies our analysis by avoiding the need for a separate treatment of such linear "spikes".
We further require the activations of the neural net (-)) to be sufficiently expressive and to satisfy certain alignment conditions:
Assumption 2. a I + E is analytic, non-polynomial with o' o'(0) + O and there exist con- stants L1, La E R+
RR,m m E such that [a(x) < L1 + L Furthermore, (.) satisfies: (a) k. (ii) E (o) (PP (z)) > 0 and iii)
E He, * 0 for all 1 <
E [o)(a()))2]= =
The last two conditions ensure that all neurons in W1 recover spherical projections of W*. In the absence of the above conditions, we still expect recovery of W but with anisotropy across neurons. Such anisotropy is expected to complicate the subsequent analysis. We show in Appendix C.7 the existence of a (-) satisfying the above set of conditions.
The next assumption, however, is only technical one that arises only because used {a} 1}. It could be relaxed by taking Gaussian values, or by performing more gradient steps on W2, but this would complicate the proof. We discuss this in detail in App. C.25
Assumption 3. E5~N(0.1) [g" (=) = 0 for 1 < < k
Under the above assumptions, our main result now establishes hierarchical learning for the target of the form [1] by a three-layer network f*(x) ) by first recovering W' through the first-layer Wi, next recovering h² (x) through the second layer pre-activations h2(x) W20 (W1x) and finally fitting f*( upon training the last layer Wy. The full formal statement of the result is provided in Appendix C.1
Theorem 1 (Informal). Let (x) be as in Eg. with e E (0,1) 1) and consider a three-layer model:
fo(x) w. w]o(b2++ W2x(W1x+bb))
(17)
with W RPiidd W2 E RRIXPI W3 E R.P.
Let (0) denote the correlation loss defined as La) = (x))) Under Ass. 1 for
any 0 < 8 < 8' < 1, there exist time-steps Ti = Oppolylogd) such that with batch-size ni @d n2 ((khert)) and p2 Pi @(dhel+ō'), the following holds with high probability as + 20:
(1) Ti steps of neuron-wise spherical SGD on correlation-loss (0) applied to W1 with step-size 7 7/p2v/ v d independent batches of size n1 results in W1 learning random projections along
7

---

W upto enror oa(1). Concretely, there exists a sequence of random matrices Z E R with independent rows sampled uniformly on the unit sphere ie 2, (8(()))
Wi Z(W)) o(1)
(18)
as 00
(ii) Subsequently; upon reinitializing W2 = Oaxd and wa with entries N(0, 1), a single pre-conditioned gradient step correlation loss (0) with step size 1u2 ((v /P2) and using an independent size n2
results in learning h" upto error oa(1) with the preactivation h2 (x) = W22rr (W,()W E R
h2(x)) = cwyh" (x)gg(()) (x) + (1()),
(19)
where + 0 denotes a constant and the (a(1) error w.r.t the metric induced by (2(N(( Ia)).
(iii) Upon training W1, W2 as above, updating Wa with ridge-regression on (dd)) samples results in approximating f* upto error 0a(1) with the 3-layer predictor w3 a (W12 ()))..
The details of the initialization projections and pre- conditioning steps are provided in App. C.5 The condition P2 Pi is again solely to simplify the analysis and we expect the results to hold for ((d)) ).PI Pi (dk
10"
Random
ZUNN
Kemne
Layerwise
Since each row of W; contains d parameters, the complexity R ((d++1) matches the total num- ber of parameters in wi..... W and is therefore expected to be the information-theoreti scaling of the complexxm required for the (strong) re- covery of WT. ..... W., Similarly, the complexity n2 = (d) is the expected minimum sample- complexity required for the strong recovery of degree-k functions on a -dim. space.
10-1
d
10
Random
Komel
Layerwise
Joint
d 32
10-1
d
* d
Proof sketch We provide the full proof of the above result in App. C and highlight the most im-
1.0 1.5
k=log(n) log(d)
portant steps below:
(i) Composition of Hermite decompositions:
Figure 2: Numerical simulation: Gener-
Building upon [84] we use the asymptotic Gaussian- ity of h" (x) to relate the Hermite decomposition of (x) the one of h (x)..
alization error versus K = log 1/log d for f (x) = tanh(3a".
((W""))/Vd<-=ll)
with different training protocols: (Top) ker- nel ridge regression (orange points) only beats the random performance (purple solid line) starting from and is limited to quadratic approximation (or- ange line). 2-layer net (green points), instead, starts to learn al k = 1.5 (black dashed line) and can beat the quadratic limit (asymptotics is given by the green line). 3-layer net trained with layerwise training (blue markers) not only learn at K = 1.5 (vertical line). but also surpasses the best possible 2-layer net error, illustrating the advantage of depth; (Bottom) comparison of layerwise training (blue) with joint training (red) of all the layers of 3- layer net with standard backpropagation.
(ii) Low-dimensional dynamics for W1: Using above, following [19 10 1. we show that the evolution of W, during the training of the first layer can be described through an effective dynamics the over- laps Wi (W+)T* Unlike the mongle/muutii-ii indexi-iixxxxx anal- ysis of [19 10 1. the diverging dimensionality of W* W1 that appear in our approach, as well as the later use of the updated weights W2, requires care- ful control over the error terms. Concretely, we show that the components of W, along W as well the error terms, maintain isotropy and hypercontractiv ity through the dynamics. Moreover, such divergent dimensionality d' of W* leads to "strong recovery" of W* by W.. We refer to Appendix C.8 for details. (iii) Function-space decomposition of the 2nd_
the compositional Hermite-decompostion
d + (d 1)d/2,
layer are-activations: Gradient steps on W₂ extract statistics in features- cratures-space a (W1x). Similar to [8 66]661 37], we show that these statistics appear in the updates for the pre-activations (x) as projections of a perturbed version of f on the conjugate Kernel defined by the first-layer:
Ah2(x) ca (Wi)) ((x))T(_oWWW (
(20)
where X E RRaxd denotes the batch of data utilized in gradient step and > denoles a constant. (iv) Concentration of the sample-covariance matrix: In light of (Mii) the recovery of features
8

---

in (x) depends on the feature matrix xW, being able to approximate and span the relevant functional subspace, which requires both sufficiently many samples and sufficiently many neurons. Building on the
analysis of [58, we show that the projections onto the a (W, X) up to degree-k functions can be well approximated as long as n. P1 ((d Low- degree eigenfunctions concentrate faster since they span niver-dimensional subspaces.
From SIGHT to MIGHT - While we expect similar results to hold in generality, the theorem is only fully proven for the class of target in eq. []. While complete proof for MIGHT is difficult task, we discuss additional (r > 1 and l > 1) results in this and subsequent paragraphs.
We first remark that part (z) of Theorem [ weak-recovery of W*), under suitable symmetry
assumptions on g (-), holds for arbitrary r. and thus for MIGHT functions f (and not only SIGHT ones) (see App. F Establishing rigorously part (ii) for > 1 involves technical hurdles relating to the control in the Gaussian approximation of h² We describe them in App. F
MIGHT functions are interesting in illustrating the role of the information exponent in Ass I is easy to design counterexamples, for instance, the parity problem with y sign sign(h (h/ hg/3)) violates Ass. We illustrate some of these numerically in App. 5 (See Fig. 10). We believe, however, that with reusing batches, the information exponent could be replaced with the much permissive generative one 32 52 11. SIGHT and MIGHT functions are indeed generalizations of the multi- index functions, and the properties of the latter such as information [9] and generative exponents [28], and the notion of trivial, easy and hard directions [81] should translate to the former.
From MIGHT to Deeper MIGHT Depth introduces more difficulties for rigorous studies, but our mathematical analysis can be extended for more general constructions. By the tree-like hierarchical construction of features (Eq. ( for general depth, the components h (x) remain independent and asymptotically Gaussian. Generalizing Thm. [ for L 2 3 in its full-generality requires however not only an extension of part (it) of Thm. to > 1, but also careful control over the non-asymptotic rates for the tails of hū (x) and the associated kernels.
We instead prove weaker, but useful, result corresponding to the hierarchical weak recovery of a single non-linear feature at a general level of depth T. E N, under an idealized scenario of perfect spherical recovery of hidden features at level I. 1. We refer to App. D for the full formal statement and its proof, which exploits the independence of components of hx-1(x) and the typer-contractivinn of the Gaussian measure:
Theorem 2. For L E N, let (x) denote a target as in Eq. 6 with r = 1, and let 6',5 be arbitrary reals satisfying 0- < 8 <.8 8' < 1. Consider a model of the form fo(x) WW]
with W. E 12- having pr.-2 = @(dhet-2+0')) rows independently sampled as w; ~
((8 Under Ass. 1 3 after a single step of pre-conditioned SGD Wi.-1 with batch-
size (ddee-att)) step-size O ((PL-1), the pre-activations h (x) W W (x)) satisfy, for a constant > O:
h = cw (x) + oa(1),
(21)
General Conjecture for Efficient Hierarchical Learning
Building on the above results, we now propose a general structure for hierarchical learning and conjecture its relevance in broader settings, as we briefly alluded to in Section 1.6 under "Hierarchical data models". As highlighted in Assumption] [ our analysis requires the target nonlinearities g (-) and (-) to have low-degree components (in our case Information Exponents 1, 2 respectively).
More generally, for any such compositional target to be learnable through gradient descent, conjecture that for every depth level L = =,,.... L., the intermediate representation h; (x) retains transformations of y. Concretely, defining the following require that at every layer &: E [x]x (x)) @(1) for some small k: E N. More formally, one may introduce the Compositional Information Exponent:
low-degree correlations with the target y (x)
Definition 1 (Compositional Information Exponent). Given SIGHT or a MIGHT function (x),, we define the compositional information exponent at level as:
CIE(E) = inf [b((())) 8k f*
O())}
(22)
Therefore we conjecture that compositional target learnable through gradient descent have, at every layer f, low CIE(E). Intuitively, even when the mapping from (h)( to the final label y = (x) is highly non-linean, the low-degree correlations with the intermediate representations h (xx ensure that it can be recovered through gradient descent. This aligns with the general wisdom

---

on the structure of real data. The non-trivial correlation of image labels with low-degree features: edges, shapes, and colors, or the case text, the correlation between labels and certain word- frequencies or bi-gram counts (see for instance the discussion in 24 ). Equivalently, such low-degree dependence can be interpreted as robustness of y with respect to perturbations in (h₃ (x)), in which case the condition becomes to mantain a robust compositionality. This hypothesis generalises the classical notion of information exponent-originale formulated for the input layer-to all intermediate representations of hierarchical model. Consequently, within the SIGHT and MIGHT classes, functions that are efficiently learnable by gradient descent are characterised by the presence of such low-degree alignments at each level. When this condition fails, for example, in parity functions whose first non -on-ainisiing Hermite coefficient lies at large degrees, gradient descent fails to efficiently recover any intermediate features.
Beyond the information exponent, we believe this layer-wise information exponent condition can be replaced by more generic one, at the price of a more complex analysis. For a start, with repeated passes and data reuse, it is natural to expect that the information exponent can be replaced by the generative exponent, as discussed for two-layer networks in 28 32 can be generalized to:
In such settings, the condition
E (b))
8k] |l @(1),
for some transformation J IR- and small & N.
Moreover, it may be possible to replace it by the more permissive "staircase" picture once one goes beyond layer-wise wise training analyses. Making this precise is exciting, but challenging, direction for future work.
5 Numerical Illustrations
While our theorems provide a rigorous control of learning with a particular, well-conditioned, training procedure, training routines with mini-batch updates, finite (and rather low) dimensional examples, using multi-pass (instead of single one) for the second layer, etc. For concreteness, we consider ff
numerically test the validity of our theory towards describing realistic
tanh
3a Pa(W"x) x)
similar example as discussed in Section and with, again, polynomial
Vdr1-179
Pk=a with second and third Hermite polynomials. We show simulations in Fig, and discuss here the most salient observations:
(i) First we compare the performance of kernel methods with those a two-layer network. On the one hand, the former method should be able to fit the quadratic part of the target function as soon as n = (dd)) 600 This is well observed, with a double descent peak when the number of data hits the number of features in quadratic kernel, i.e. Пpeak d(d 12/2 + d d++1 1. On the other hand, 5) therefore improving the test
two-layer networks are capable of recovering W* when performance to quadratic and cubic when K 2 1.5.
(ii) We then train a three-layer network, with a layerwise approach resembling the procedure in Thm [ where we train every layer in order, (first W1, then W2, etc.). We do not, however, follow the restrictions of the theorem and just perform standard gradient descent (no reinitializing, no projection, using minibatch, etc.). Not only does the method starts to learn when n >> dl.5 but it outperforms the 2-layer baseline in agreement with Thm.
(iii) Lastly, we consider the standard training procedure -refered to as joint training- with backpropagation through the network with mini-batch gradient descent. The routine performs similarly to the layerwise approach, illustrating the generality of the dimensionality reduction beyond the assumptions of ThT. 1
We refer to App. F for details on the numerical implementations, along with the analysis of the quality of the learned representations as a function of the sample complexity (see Fig. 9).
Conclusion- We introduced theoretical framework for understanding the computational ad- vantages of deep neural networks over shallow models when learning high-dimensional hierarchical functions, where depth facilitates progressive reduction of effective dimensionality. We hope our paper will spark interest these directions.
Acknowledgement- We thank Alex Damian, Jason Lee, Bruno Loureiro, Yue M. Lu, Theodor Misiakiewicz, Eshaan Nichani, Tomaso Poggio, Zhichao Wang, Denny Wu, and Mathieu Wyart for insightful discussions. We acknowledge funding from the Swiss National Science Foundation grants SNSF SMArtNet (grant number 212049), OperaGOST (grant number 200021 200390) and DSGIANGO (grant number 225837).
10

---

References
[1] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural net- works: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552-2623. PMLR, 2023.
[2] Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The mergee-staircase prop- erty: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782-4887. PMLR, 2022.
[3] Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. Journal of Machine Learning Research, 19(50):1-34, 2018.
[4] Ben Adlam, Jaehoon Lee, Shreyas Padhy, Zachary Nado, and Jasper Snoek. Kernel regression with infinite-width neural networks on millions of examples. arXiv preprint arXiv:2303.05420 2023.
[5] Alexander A. Alemi, lan Fischer, Joshua V. Dillon, and Kevin Murphy. Deep variational infor- mation bottleneck. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
[6] Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Advances Neural Information Processing Systems, 32, 2019.
[7] Zeyuan Allen-Zhn and Yuanzhi Li. Backward feature correction: How deep learning performs deep (hierarchical) learning. In The Thirty Sixth Annual Conference on Learning Theory, pages 4598-4598. PMLR, 2023.
[8] Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[9] George B Arfken, Hans J Weber, and Frank E Harris. Mathematical methods for physicists: a comprehensive guide. Academic press, 2011.
[10] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. Online learning and information exponents: The importance of batch size & time/complexity tradeoffs. In International Conference on Machine Learning, pages 1730- 1762. PMLR, 2024.
[11] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows sgd to learn nigh-dimensional multi-index functions. arXiv preprint MiXiv:2405.15455 2024.
[12] Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In 7th International Conference on Learning Representations (ICLR), 2019.
[13] Gérard Ben Arous, Cédric Gerbelot, and Vanessa Piccolo. Stochastic gradient descent in high dimensions for multi-spiked tensor pea. arXiv preprint arXiv:2410. 18162, 2024.
[14] Benjamin Aubin, Antoine Maillard, Florent Krzakala, Nicolas Macris, Lenka Zdeborová, et al. The committee machine: Computational to statistical gaps in learning a two-layers neural network. Advances Neural Information Processing Systems, 31, 2018.
[15] Guillaume Aubrun and Stanislaw Szarek. Alice and Bob meet Banach, volume 223. American Mathematical Soc., 2017.
[16]
Sheldon Axler. Measure, integration & real analysis. Springer Nature, 2020.
[17] Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang, Generalization of two-layer neural networks: An asymptotic viewpoint. International conference on learning representations, 2020.
11

---

[18] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová, Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12):5451-55 -5460, 2019.
[19] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1-51, 2021.
[20] Raphaël Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics, pages 1-84, 2024.
[21] Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien. On learning gaussian multi-index models with gradient flow. arXiv preprint arXiv:2310. 19793, 2023.
[22] Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768- 9783, 2022.
[23] Francesco Cagnetta, Leonardo Petrini, Umberto M. Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Phys. Rev. X, 1 14:031001, 2024.
[24] Francesco Cagnetta and Matthieu Wyart. Towards a theory of how the structure of language acquired by deep neural networks. In Advances in Neural Information Processing Systems, 2024.
[25] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368 2007.
[26] Sourav Chatterjee. A generalization of the lindeberg principle. The Annals of Probability, 34(6), November 2006.
[27] George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[28] Alex Damian, Loucas Pillaud-Vivien, Jason D. Lee, and Joan Bruna. Computational-statsition gaps in gaussian single-index models. In Proceedings the 37th Annual Conference on Learning Theory (COLT)) 2024.
[29] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn repre- sentations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.
[30] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two- layer neural networks learn, one (giant) step at a time. Journal of Machine Learning Research, 25(349):1-65, 2024.
[31] Yatin Dandi, Luca Pesce, Hugo Cui, Florent Krzakala, Yue M Lu, and Bruno Loureiro. random matrix theory perspective on the spectrum of learned features and asymptotic generalization capabilities. arXiv preprint arXiv:2410. 18938, 2024.
[32] Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint arXiv-2402.03322, 2024.
[33] Amit Daniely. Depth separation for neural networks. In Conference on Learning Theory, pages 690-696. PMLR, 2017.
[34] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-free deterministic equivalents and scaling laws for random feature regression. In Advances in Neural Information Processing Systems, 2024.
[35] Diego Doimo, Aldo Glielmo, Alessio Ansuini, and Alessandro Laio. Hierarchical nucleation in deep neural networks. Advances in Neural Information Processing Systems, 33:7526-7558 2020.
12

---

[36] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
[37] Hengyu Fu, Zihao Wang, Eshaan Nichani, and Jason D. Lee. Learning hierarchical polynomials of multiple nonlinear features with three-layer networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2025.
[38] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pages 3452-3462. PMLR, 2020.
[39] Behrooz Ghorbani, Song Mei, Theodor Misiakiewiez, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33:14820-14830, 2020.
[40] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2), 2021.
[41] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pages 426-471. PMLR, 2022.
[42] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. The gaussian equivalence of generative models for learning with shallow neural networks. In Proceedings of the 2nd Mathematical and Scientificc Machine Learning Conference, pages 426-471, 2022.
[43] Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10(4)0041444, 2020.
[44] Harold Grad. Note on N-dimensional hermite polynomials. Communications on Pure and Applied Mathematics, 2(4))325-333 1949.
[45] Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. IEEE Transactions on Information Theory, (933:193221199 2022.
[46] Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
[47] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6990, 2014.
[48] Achim Klenke. Probubility theory: a comprehensive course. Springer Science & Business Media, 2013.
[49] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning, nature, 52147553)4436-444 2015.
[50] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer-Verlag. 1991. Google-Booke Books-ID: juCIQAACCAJ)
[51] Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
[52] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low- dimensional polynomials with sgd near the information-theoretiic limit. In Advances in Neural Information Processing Systems, 2024.
[53] Shuo-Hui Li and Lei Wang. Neural network renormalization group. Physical review letters. 126626) 2018
[54] Yue M Lu and Horng-Tzer Yau. An equivalence principle for the spectrum of random inner- product kernel matrices with polynomial scalings. arXiv preprint arXiv:2205.0668 2022.
13

---

[55] Stephane Mallat. A wavelet tour of signal processing, 1999.
[56] Tanguy Marchand, Misaki Ozawa, Giulio Biroli, and Stéphane Mallat. Multiscale data-driven energy estimation and generation. Physical Review X, 13(4), 2023.
[57] Pankaj Mehta and David J Schwab. An exact mapping between the variational renormalization group and deep learning, arXiv preprint arXiv:1440.3833 2014.
[58] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022.
[59] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84 81, 2022. Special Issue on Harmonic Analysis and Machine Learning.
[60] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766 2022.
[61] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
[62] Hrushikesh N Mhaskar and Tomaso Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 1400s,, 14(06):829-848, 2016.
[63] Theodor Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204. 10425, 2022.
[64] Andrea Montanari and Basil N Saeed. Universality of empirical risk minimization. In Conference on Learning Theory, pages 4310-4312. PMLR, 2022.
[65] Elchanan Mossel. Deep learning and hierarchal generative models.
arXiv preprint
arXiv:1612.09057, 2016.
[66] Eshaan Nichani, Alex Damian, and Jason D Lee. Provable guarantees for nonlinear feature learning three-layer neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[67] Tomaso Poggio. How deep sparse networks avoid the curse of dimensionality: Efficiently computable functions are compositionally sparse. Technical Report CBMM Memo No. 138, Center for Brains, Minds and Machines (CBMM), 2023.
[68] Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but not shallow-networks avoid the curse of dimensionality: review. International Journal of Automation and Computing, ((5):593-519, 2017.
[69] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
[70] Itay Safran and Jason Lee. Optimization-based separations for neural networks. In Conference on Learning Theory, pages 3-64. PMLR, 2022.
[71] Itay Safran and Ohad Shamir. Depth-widee tradeoffs in approximating natural functions with neural networks. In International conference on machine learning, pages 2979-2993 PMLR, 2017.
[72] Andrew M. Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan D. Tracey, and David D. Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124020, 2019.
14

---

[73] Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning deep linear neural networks. In Proceedings of the International Conference on Learning Representations (ICIR). 2014.
[74] Antonio Sclocchi, Alessandro Favero, Noam Itzhak Levi, and Matthieu Wyart. Probing the latent hierarchical structure of data via diffusion models. In The Thirteenth International Conference on Learning Representations, 2025.
[75] Antonio Sclocchi, Alessandro Favero, and Matthieu Wyart. A phase transition in diffusion models reveals the hierarchical nature of data. Proceedings of the National Academy of Sciences, x2207111248 2025.
[76] Terrence Sejnowski. The unreasonable effectiveness of deep learning in artificial intelligence. Proceedings of the National Academy of Sciences, 117(48), 2020.
[77] Berfin Simsek, Amire Bendjeddou, and Daniel Hsu. Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence. arXiv preprint arXiv:2411.0877 2024.
[78] Yitong Sun, Anna Gilbert, and Ambuj Tewari. On the approximation properties of random relu features. arXiv preprint arXiv.1810.04377 2018.
[79] Matus Telgarsky. benefits of depth in neural nelworks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517-1539, Columbia University, New York, New York, USA, 23- 26 Jun 2016. PMLR.
[80] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw). Ieee, 2015.
[81] Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, and Florent Krzakala. Fundamental limits of weak learnability in high-dimensiona multi-index models. arXiv preprint arXiv:2405. 154880 2024.
[82] Ramon Van Handel. Probability in high dimension. Lecture Notes (Princeton University). 2(3):2-3, 2014.
[83] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
[84] Zihao Wang. Eshaan Nichani, and Jason D Lee. Learning hierarchical polynomials with three-layer neural networks. arXiv preprint arXiv:2311.13774 2023.
[85] Kenneth G Wilson. Renormalization group and critical phenomellhhemmma...mmm ii phase- space cell analysis of critical behavior. Physical Review B, 4(9)43184, 1971.
[86] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and higher-order scalings for dot-product kernel regression. Advances in Neural Information Processing Systems, 15:4558-45700 2022.
[87] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Under- standing deep learning (still) requires rethinking generalization. Communications of the ACM, 64(5) 2021.
15

---

NeurIPS Paper Checklist
(i) Claims
Question: Do the main claims made the abstract and introduction accurately reflect the paper's s contributions and scope?
Answer: [Yes]
Justification: All claims in the abstract and introduction are supported by mathematical proofs or numerical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 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.
fine include aspirational goals as motivation long as it is clear that these goals are not attained by the paper.
(ii) Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the setting are pointed out in Section 3
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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated 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 few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a 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 be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency
16

---

play an important role in developing norms that preserve the integrity of the com- munity, Reviewers will be specifically instructed not penalize honesty concerning limitations.
iii
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The statement and the assumptions are stated in the main paper, while the proofs are presented in detail Appendices C and
Guidelines:
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 clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
(iv)
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the algorithms used for the simulation are described in the paper (and relevant cited literature). All plots are accompanied with description and parameters used.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer 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 the contribution, reproducibility be accomplished in various ways. For example, the contribution a novel architecture, describing the architecture fully might suffice, if the contribution it may be necessary to either make it 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation,
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
17

---

(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (egg, a large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (e.g. with an open- ppen-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-soures models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
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?
Question:
Answer: [Yes]
Justification:
The code provided in the GitHub repository associated with the manuscript.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: /tpp:s//nis.. cc/ public/ public/guides//ooes/// hte///ddeeuubmmm ss sssisssssoooiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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://nigg cctpublic///cccccccccccccccccllt httee/ggieee//eeeeeeeeeeee http:/gidddee/eeeuiiiiieeee Ccodesubmissioonoo.. more details.
for
The authors should provide instructions data access and preparation, including how to 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 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 as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
(vi)
Experimental setting/detail
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: [Yes]
Justification: Justification: We detail the choice of the parameters in Main theorems, caption Figures and Section 5 We also provide Appendix with further details regarding the numerics.
18

---

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 a level of detail that necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
(vii) Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appro- priate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experiments are carried over by considering multiple random seeds and they include error bars as described in Appendix F.4
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, con- fidence intervals, or statistical significance tests, at least for the experiments that support the 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 to a library function, bootstrap. etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
(viii) Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We provide the relevant informations regarding the compute resources in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
19

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't 't make it into the paper).
(ix)
Code of ethics
Question: Does the research conducted in the paper conform, in every re- spect, with the NeurIPS Code of Ethies httts:: cttpsssiccpppciccpccc
EthicsGuidel iine?
Answer: [Yes]
Justification:
The manuscript is conform to the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors a deviation from the Code of Ethics.
No, they should explain the special circumstances that require
The authors should make
preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
(x) Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Due to the theoretical nature of this work, we believe that discussion of positive and negative societal impacts not required.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that 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 being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
(xi) Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g. pretrained language models, image generators, scraped datasets)?
20

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no 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 to 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.
(xii) Licenses for existing assets
Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected!'
Question:
Answer: [Yes]
Justification: We work with synthetic data and we are the creator the code and the model.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (egg. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged reach out to the asset's creators.
(xii))
New assets
Question: Are new assets introduced in the paper well documented and is the documenta- lion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dalaset/cood/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
21

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
(xiv)
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 to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
(xv) 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) obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research 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.
(xvi) Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formalting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
22

---

The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components.
Please refer to our LLM policy /tlp:s://euripss cc/Conferecces/ 2025/LLM for what should or should not be described.
23

---

A Illustration of SIGHT and MIGHT targets
exemplify visually SIGHT (1) and MIGHT functions Fig. and their deep version 6 in Fig. These illustrations clarify how hierarchical compositions operate across layers and how depth progressively compresses the input through structured non-linear transformations. Specifically, they highlight the architectural transition from shallow models to deeper ones, where each layer reduces the effective dimensionality via localized polynomial projections. The tree-like structure of the deep targets, emphasizes the compositional nature of the learning task and motivates the layer-wise training regime analyzed in the main results.
SIGHT
MIGHT
6'00")
W' E Rdd
W R
E
R
xe
Figure 3: SIGHT and MIGHT targets: Illustration of Single and Multi Index Gaussian Hierarchical Targets, i.., SIGHT in eq. (2) and MIGHT in eq. (4. Left: A SIGHT function. Here we first go from x E RRd to z E Rd After applying the polynomial transformation pointwise (not shown), this is projected to create scalar ht R. One can then output the label y = =g" (h"). Right: A MIGHT function. Again, pointwise, we finally projecte on two values hi, and hi.2. from which we create y as two-index function y = g" (hi,1,)1.))
go from R to E Rdd After applying the polynomial transformation
B Depth Separation
Here, we further discuss the separation in sample complexity for deep versus shallow models complementing the exposition in the main text. Different works in approximation theory have established clear depth-separation results in expressive power. For example, [79 constructed a family of highly oscillatory functions (essentially obtained by iterative compositions of ReLU units) which a network depth and constant width can express in contrast to two-layer networks. Similarly, 771 demonstrated depth separation using simple geometric indicator functions that can be efficiently realized by network with an exira hidden layer, but cannot be approximated to high accuracy by any two-layer network of polynomial size. It is important note that "lcarning" in the context of these results refers to the ability of the architecture to approximate a fixed target function under given input distribution. In contrast, the present work focuses on representation learning via gradient descent to recover hierarchical feature compositions in Gaussian data. The depth separation we highlight is not purely about static approximation power, but about data-efficient learning through hierarchical dimension reduction. A deep network can progressively extract and refine features across multiple layers, effectively performing stage-wise dimensionality reduction. such that each layer learns meaningful intermediate representation of the data. Along these lines, 23 addressed under different data models similar questions and found that deep networks trained with gradient descent learn hierarchical features and progressively reduce dimensionality across layers. As highlighted in the main, the advances closest our framework are due 84 66 [y
who established depth separation results between 2-layer and 3-layer networks under simpler
24

---

L=3 SIGHT
L= MIGHT
W' R
8
b.
R
ER
xc R
2*
Figure 4: Deep SIGHT and MIGHT: Illustration of deep target functions. Left: A SIGHT function with depth = 3. Here we first go from IRd h Rdd After applying the polynomial transformation pointwise (not shown), now divide h1 into d blocks of sizes d=1-=2 Each of these blocks is projected to create one of the components of h, E R After another polynomial transformation (not shown) we finally project to single value hz. We can then output the label y 9² (hz). Right: A MIGHT function with depth
4. Again, we go from x R' to h E _dd After applyging the polynomial transformation pointwise (not shown), we now divide h into d blocks of sizes d =2 Each of these blocks is projected to create one of the components of h2 E Rdd We repeat this operation: we further divide h2 into a blocks of sizes d=a-es and each of these blocs is projected to create one of the components h3 E IRd" After another polynomial transformation (not shown) finally project two values hi, and h4.2 and create two-index function y (hi,1, h4
training setups, where the first layer remains fixed. contrast, our analysis strengthens these separations by considering fully-trained architectures without fixed layers.
B.1 Towards General Two-Layer Networks Lower Bound
In Section 2 we argued why two-layer network, upon recovering W* (up to noisy random rotations), insufficient for learning SIGHT targets (see eq. (13). Ideally, one would hope show that such barrier introduced holds for two-layer networks trained through general gradient-based algorithm. While obtaining unconditional gradient descent remains a challenging open problem, we briefly comment on why we conjecture our class of SIGHT targets be hard learn with polynomial sample complexity. Amongst lower- bounds closest to our class of targets, 33 established that targets of the form g" (x Ax), with
sower-bounds on two-layer networks trained under
A = ( 1) T for some orthogonal matrix E RRdxd cannot be learned under polynomial time and cample-complexity by two-layer network.
We next discuss how such targets fall under the setup of MIGHT 4 Consider the setting of MIGHT with r = 2, l = 2, Pa(2) = x² and:
hg)
h h2g
(23)
25

---

Since h13 va Ei=(( (( x))² 1, we obtain that:
di h - h2
(wi w. x))² ((W2,;x))*
vd
(wi, - W2, w2.))
x
= U (t Dux
where U e Raxd is an orthogonal matrix whose columns are suitable orthonormal combinations of the vectors (wi,sh U (w2,);: We provide below a short derivation for the mapping.
Let m = d and define the block-rotation R := 1/2 (1 2)), which satisfies R (6 - - (96)-
Let Uo E Rdx2 collect the 2m orthonormal vectors {wi,s} U {w2,). and complete it with an orthogonal complement U1 to form Ú = [Uo U1] E Raxd Let U Ü diag( R, Ia-2m), which is orthogonal. Then:
m
Va hg(x)) = (T(
wi, wi. wi.,
x- - x TU())UXXx
This is exactly of the form (x Ax) with A = ū(9))OT.
C Proofs of the main Results
C.1 Full Statement of Theorem
Theorem 3. Let (x) be as in Eq.
with E (0, 1) and consider three-layer model:
fo(x) w2 ab + W2a + bz)),
(24)
with W1 RPIXd, W2 E XPIPI W3 E RP3
Let (0) denote the correlation loss defined as (0) = - (x)) Under Ass. 3 for any 0 8' < 1, with batch-size n1 =(dr++++d) n2 = (d) and p2 = p1 = (ak +58 the following holds with high probability as d + 8o:
Recovery by layer 1: For each E [P1]. let w denote the neuron W1 Suppose that w: is updated as in Algorithm C.5 through spherical SGD on correlation loss (0), using step size 1j 7. dd Let the value at the lah iterate be denoted by w Le::
mn 1 Σ whe w.t + (Ia (w (w: (T
(25)
11+1
1,t
[w2.1
Let Pw- E Riddd denote the projection operator onto the subspace spanned by W and define:
u Pw !!!
(26)
PPw
Let Tú denote the stopping times defined by:
T = {inft: t : ((u w nx..
k].
(27)
then, for any < 1, constant C₂ and ñ > such that whhpp as -> oo:
max Th C.e logd
(28)
26

---

vi E [pil:
wi 1h x u + vI ktu, u, +ol
(29)
where n² and u, ~ U())-1(1))
Recovery by layer 2: Suppose that W2 is re-initialized to W axd while Wa is re-initialized with entries drawn from N(O, 1). Let Z = =(X((i) E 22x and consider single pre-conditioned update of the form:
W2 t (1 z Vw,Ce-
(30)
There exists A2 RR+ with d2 = (
) and step size 1p2 = (vpp)) such that the pre-uctivation
h2(x) (21 E IR satisfies:
1
h2(x) owgh" 00
(31)
v /dmin(6,8'
Remark: Here, we introduced the regularization parameter X2 > O since we assume that P1 ng (overparameterized setting) and thus Z Z singular. Alternatively, one could consider the underparameterizee setting p1 < n2 without the need for additional regularization.
Recovery by layer-3: Let Raaxd denote a matrix with rows containing ng independent samples from the input distribution N(O. IJ). Let H E R=axps denote the corresponding pre-activation matrix with rows (W2aWWxx)) - f (x,), for i E [na]]- For ny = (dd)) YE > 0 such that the ridge- regression predictor W, given by:
WA (
1 H H
+ f(X),
(32)
satisfies:
E ((,,
|| -
os(1).
(33)
C.2 Proof Sketch
We prove each the three parts of Theorem in succession. We outline the proof for each of these parts below:
Part (t):
(i) The asymptotic composition of Hermite polynomials allows us decompose the Hermite decomposition of [*(() along Hermite polynomials applied to W*x.
The leading order term in the Hermite-decomposition f*(x) lies along Hea (W"()) contributes a linear drift to the dynamics of each neuron in W,, with the direction of the drift for neuron given by u W WW(++) w! i.e, the initial direction of w projection onto W
xx), which
(iii) We show that the neuron w! remains approximately isotropic wrr the rows W*
(iv) Under the above isotropy and due to d= > 1, we show that the above linear term dominates throughput the weak-recyvery and subsequent states the dynamics.
(v) As a consequence, each neuron in W, evolves primarily along uj with the noise controlled through the choice of batch-size. A stopping- time based analsyis then yields w!2) ut
(vi) For subsquent use in part (ii) however, we require finer control over the distribution of w and its residual terms.
(vii) Inductively, we show that the distribution of w! conditioned on suitable stopping- time is approximately uniform on the unit sphere along W and maintains hypercontractivity.
Part (tt):
(i) Through results established in Part (i), we show that the distribution of the updated weights Wi approximately maintains hypercontractivity for the eigenfunctions of the random- features Kernel associated to the features a (XWT). ). This ensures the concentration of the associated sample covariances.
27

---

(ii) Upon establishing concentration and spherical approximation along the subspace corre- sponding to W*, through an analysis similar [58], we show that the feature matrix 7 = a (XWT) contains (dd)) spikes with diverging eigenvalues and an isotropic bulk with eigenvalues 0(1).
(ii) Under P2 > (ddhe)) ), show that these spikes suffice for the pre-conditioned update
L ((oo -Wz,,
nt
to approximate (x) upto degree k-components. As a result, we obtain the recovery of ht (x) through (x)
Part (dit): Finally, fitting the target (xx upon training W3 follows through universality of the
random features Kernel associated with a(-) and perturbation of the Kernel regression operators.
C.3
Preliminaries
C.3.1
Stochastic Domination
Throughout the analysis, much of our probabilistic error bounds will take the following form, which are standard for functions of random variables with finite Orlicz-norm such as JubDGaussian/su- Exponential random variables:
(log d) dm
Pr
X 2 C
S e eoloogd))"
(34)
for some constants m > 1, > 0, e O. slightly weaker form of the bound takes the form:
Pr X
C dm S d
(35)
for any 5 >> 0 and k E N. To concisely represent such bounds, we use the following notation: Definition 2. [Stochastic dominance [54]] We say that a sequence of real or complex random variables Xa in normed space is stochastically dominated by another sequence Ya in the same space if for all 8 > 0 and k, the following holds for large enough
Pr|lIX > II S dd
(36)
We denote the above relation through the following notation:
X = OYY...
(37)
Through union bound, obtain that O~ is closed under addition, multiplication, i. X, (Yi)) and X₂ = (Y2) imply that:
X1 + X, O+2Y+++ Y2),
(38)
and:
X1X2 = OKVV).
(39)
Furthermore, due to the flexibility of setting arbitrarily large k in Eq. 336 observe that stochastic dominance is closed under unions of polynomially many events in d.
We will often exploit this while taking unions over (dd neurons and n = ((d) samples. Furthermore, x absorbs polylogarithmic factors Le::
X O+) X (=pooyloog(d))
(40)
subsumes exponential tail bounds of the form:
Pr[X, > (Yd) -t"
(41)
for some a > as well as polynomial tails of arbitrarily large degree:
Cx
Pr > tYal <
(42)
th
for some sequence of constants C2 dependent on k.
The above bounds directly translate to the following control over moments:
28

---

Proposition 1. Let Xa, Ya denote two sequences of random variables with:
X x=
(43)
then for any E N and 6 > 0:
E ||I S (1X
(44)
Proposition 2. The above proposition follows directly through the following decomposition:
[| = E [|Y]| | [[x]==1))
1/p
+ +E [|-]|* 1 ||x]|>d*|11
(45)
where denotes the indicator function.. Using the property E|Z] = - Pr[Z > s|ds, the second term is bounded by t for any k and large enough d.
Asymptotic notation: In light of the above proposition, throughout the subsequent sections, use the notation to denote deterministic asymptotic bounds upto factors d for arbitrarily small 5 > 0 i.::
f(d) = (g(d)),
(46)
if for any 8> > 0, f(d) S d' g(d) for large enough d
Through standard application of the Lindeberg exchange technique following useful estimate:
26 82
we further have the
Lemma aoym-ssypiiotic CLT -bound). Let 1...., X, R ben Lid random variables satisfying X, = (1).). Then, for any any function q R - I with E e (R), Ilq" < oo and any 8 >> 0:
E
xi) - NO,1) [a(=)) S SavaB c0 [X]] 1|+
C3 d1/2-6
E
|
(47)
where C1 C2 denote constants dependent only on
Through standard truncation arguments over the tail of 1 va (E X;), the above bound extends to
all polynomials R -> IR of finite degree.
C.3.2 Orthogonal Polynomials and Spherical Harmonics
Hermite Polynomials: A key role in our analysis is played by the decomposition of square integrable function with respect to the Gaussian measure in terms of the Hermite polynomials [4]. Definition (Hermite decomposition). Let f RT + R be a function that is square integrable wrt the Gaussian measure. There exists family of tensors (Cy(f))seN such that Cj(f) is of order j and for all x E R.
f(x) ((C,(0),6(())
(48)
JEN
where Hx(x) is the j-th order Hermite tensor [44]
Gegenbauer and Associated Laguerre polynomials Let U((dd+(VV)) denote random variable distributed uniformly on the sphere Rd of radiues Vd. Let pdd denote the associated push-forward measure of the projection vdw,we e1). The Gegenbauer polynomials (²(() 33 for l E N form an orthonormal basis w.r. (1a))) with Q+(-) being a polynomial of degree Therefore, for any f E (Ja) and E Idd with |||||| = 1, the following decomposition exists:
f(vd(v,w) = Σ Q w))
(49)
Next, suppose that x N(O, La). Let denote the associated pushforward measure of ||x]] Then, the associated Laguerre polynomials (.) form an orthonormal basis w.r.t Ta [9].
Spherical Harmonies Recall that any inner-product Kernel can be diagonalized w.rl L2(U(8d-1(V))) along the basis of spherical Harmonics BeBa..enB.. where Bid, k) denotes the number of spherical harmonics of degree k; satisfying B(d, k) = O(d*):
k(x,x')
d (x)
(50)
k=0
29

---

where A denotes the eigenvalue of K w.r. the k-degree spherical harmonics Yí, (x).
40
The Spherical Harmonics are related to the Gegenbauer polynomials through the following identity: Proposition 3. For any W1, U (Vd)):
B(dk)
Q (w1, w2) B(d,k)
E
(51)
next recall that the Gaussian measure N(0, Ia) admits the following tensor product decomposi- tion:
N(O, (((*
(52)
where UV8)-I(Vd)) denotes the uniform measure on sphere of radius vd
The above tensor product decomposition naturally relates the Hermite orthonormal basis w.r.t the Gaussian measure against the product of radial functions and Gegenbauer polynomials. In particular, we have the following relation:
Proposition 4. For any k E N, the kus degree Hermite polynomial lies in the subspace spanned by functions of the form:
|
2 Vdti
f(
)ee, Vdx// [|x]]),
(53)
with 0 < S k.
Proof. Recall that Y ( (V dx/ [|x are homogenous polynomials of degree j. Upon restriction to the sphere of radius | Her (x) polynomial of degree at-most k. Therefore, by Fubini's theorem, we obtain:
| 2
E
Yess(Va dx/ (aakk/||1]]/t (x)))))((xx = 0,
(54)
dd
for j > k.
Proposition 5. For any h >> 2 and polynomial q(z):
E
Var
n
WETT ==
(w:
x)
9(
n
He Hea(( x))) = 0( V
(55)
d
de
Proof. The above is a direct consequence of Lemma D applied the random variables (())(( He;
E R2, whose higher-moments are bounded by Gaussian hyper-
contractivity (Lemma
We utilize Gegenbauer polynomials and spherical Harmonics primarily due to the absence of results on eigenvectors of inner-product Kernel matrices under polynomial scalings. This also the primary bottleneck towards the extension of our theory multiple layers. Essentially, our analysis relies on showing the concentration the sample-covarianc matrix to the population covariance matrix along the degree-k components.
C.3.3 Spectral Norm of tensor
Definition For symmetric positive-definite tensor di order we define the spectral norm TfT as follows:
|| = sup
(x 0k TT
(56)
=ERd
| m=|=1
30

---

C.3.4 Hermite-tensors and Gaussian-inner Products We denote by He, for & E I the normalized Hermite poliiittepplyooiialsss forming orthonormal basis w.r.t L2 (7). For any f E (y), we have:
f(z)
(cHex
(57)
The Hermite tensors result in the following generalization of the above decomposition: Proposition 6. Let denote the m m-dimensional Gaussian measure. For any f.g : R + R (TR." mm), let (f) denote the ken -order Hermite-tensor, defined as:
Cx(f) = Ezwrn [f Hew = EZwYm
V [V)(())
(58)
where (z) denotes the kinh -order Hermite tensor on mm Them:
(0,9)~ = [(C,())
(59)
KEN
C.3.5 Compact Self-Adjoint Operators
We collect here the following well-known properties of bounded linear operators on Hilbert space
(p) [16
Proposition 7. Let A (2, > (p, denote bounded-linear operator on hilbert space
(p). Then:
(i) A is compact, self-adjoint then A can be diagonalized along countable-bast of eigenvectors.
(it) Suppose that p a-finite, then any integral operator (xx,))
+ R with
(1 v) (1))(1))))) < 30 is compact
(iii) For symmetric integral operator [T ( 60:
f [(x, yddu(w x w) = =E Aks
(60)
where } denote the eigenvalues associated with [(,)).
C.3.6 Concentration in Orlicz-spaces
Definition 5. For any a IR, define (x) = - 1. The Orlicz norm for real random variable | defined as
innf inf { t>00 E
X
|X =
(61)
Random variables exhibiting suitable bounds orlicz norms of finite-order exhibit the following
concentration inequality:
Theorem 4 (Theorem 6.2.3 in mean and second moment EX??
50
Let XI,..., Xn, be independent random variables with zero
o²¹ Then,
X
$ Ka l/a
Σ of + max |
(62)
C.4 Useful Preliminary Results
central result underlying our analysis for part (it) of Theorem 1 based on [60| is the following
matrix bound for matrices with independent heavy-tailed rows: Lemma (Theorem 5.48
(3). Let E Raxp random matrix with independent rows a,
with covariance [a,a,] En and E maxisn |all]] m. Then:
A T A Σ,
< maax||Ea1] 1/2 8, 82),
(63)
where 5 Cy log(miu(n.p))
31

---

Lemma 3 (Weyl's inequality). For any A, B E Rm for all i E N with i I min(m, n.):
(o.(A) - 0; oB - A B|
(64)
Lemma 4 (Resolvent Identity). Let, A, E R be two invertible matrices, then:
A- B A L A)B
(65)
Our next central tool that will be utilized frequently throughout our analysis is the hypercontractivity
w.r.t the Gaussian measure: Lemma 5 (Gaussian Hypercontracttivtyy Proposition 5.48. in 15 For any polynomial q R
R
of degree and any p E N, 2 2:
I1a(2)) p.y S (p 1)a [1a(2) 2,
(66)
where 7 denotes the standard Gaussian measure on R2 and [|q())]) denotes the p-norm:
(=) Ezw [1]
(67)
Proposition 8. Let ~ N(0, I2) denote d-dimensional Gaussian vectors. Suppose that X1, denote ii.d random variables obtained by applying a fixed polynomial of degree p E N to distinct subsets of coordinates of Then:
Xx
X₂) 02(y E [X + A/E [X]]).
(68)
Proof. Since q(=) = 1 (E x,) is a polynomial in with finite degree p. Lemma implies that its higher-order moments are bounded as |lq(=)]|, I C, |1((2)] The result then follows by noting that:
vI
E [a(())]
E [X] + 2(k [X]
(69)
Lemma 6 (Discrete Gronwall). Let ar, br, ci. ch be non-negative sequences satisfying:
a++1 2 a + cia + cbbb,
(70)
then, for anyl L N:
a++1 2 II ( ao ao
(71)
j=1==1
We analogously have the corresponding upper bound i.
a++1 S at + cfa + cgbb
(72)
implies that:
a++1 S
II (1 ci 0a0 + E1
02by
(73)
==
C.5 Full Algorithm
We describe the full algorithmic routine used in Theorem in Algorithm
C.6 Leveraging Asymptotic Gaussianity
crucial property of the non-linear feature h h*) that we leverage is its asymptotic Gaussianity, not only w.r.t their marginals but w.r. propagation to the lower-level features. Specifically, building on 884, we show that the high Hermite-degree functions h (x) do not propagate projections along low Hermite-degree functions of > To show this, we provide an inductive proof inspired by the combinatorial approach developed
84 wherein the (entropically) dominant contributions in (he, ( arise from terms having the lowest degrees in ((w( xx)).
32

---

Algorithm 1 Layer-Wise Training for Three-Layer Network
Input: Training data D, mini-batch sizes n4, 12,, learning rates M), 12, ridge regularization A,
iteration steps Ti.
Initialize:
w ltd U(8 for [pi]
W(2) +- Ip2xd
(60), ((2)) pm xp2
Layer updates (correlation loss with spherical projections):
f(x) = fx( W ((
L: R x x R [xx, v) = -yf(x) (Set loss & to correlation loss)
for f= T1 do
Sample mini-batch X,y D of size 71 For each neuron j in layer 1:
w/Dh - w(()
m V (w (00
(
end for
Fix layer 1, update layer
Re-initialize (2) -> 0pp
Sample mini-batch X.y C of n2
W2 (((
Vw
Fix layers 1,2, solve for W3() via ridge regression: Sample mini-batch X, D of size n3
Form design matrix H:
For each yx in D:
h + (W x B())
l12 - o (W + (2))
H(z,)) + [h2]T, Y
Solve:
( + H H + + TTY
Proposition For any E > 0, and k E N, let (x) for IRd denote a non-linear feature of the
form:
(x)
Pa((w;,))),
(74)
where P& denote polynomials of degree le satisfying 12 [Pa(z)] and B2 [Pa(2)2]
Denote by S the set of indices in [d=*] and by I'm the set of all m-permutations in consisting of distinct values.
Then, the following holds for any E N:
Hem (x,(
1
Σ (ST
PI x)) + (x)) O-()),
(75)
V Vidmmr
where I' (x(x) satisfies:
(i)
I'm (x) = 0+(
(76)
Vdl
33

---

(ii) For any l E N and R
(
0(
(max REd
(w,
v)1)--1),
(77)
d
for some 8 > 0,
where recall that Ô subsumes factors of the form d for arbitrarily small 6 > 0.
The above set of properties characterize, in particular the projections onto Heermite-polynomial x of non-linear functions applied hi (x)
Proof. The proof proceeds by induction. Similar to 84], the central idea is to utilize the fact that the Hermite-degres is additive for products of terms dependent on orthogonal subspaces. The putropically-dominge
terms in (h, (x)) arise from products of (w,, x), (wJ. x) for #
contributing leading Hermite-degree of dk.
We show inductively that Equation 75 holds for any m N.
The base case m = 1 holds trivially. Suppose that the statement holds for some m E N. Recall that the (normalized) Hermite polynomials satisfy the following recursion:
Hem- 1 (a)
"V
m + Hom (x) - -V m + Hcm 1
(78)
Applying the above relation with = (x) yields:
Hem+1 (x),))))
Pa(2)) Hem (x) my
Hem Hem-i(h,(xi) (79)
The induction hypothesis on Hem(h,(x)), then implies:
Hem (h,(()x))
Σ Pa((w; x))
Σ
P[ x)) +x)())) mm m
H (x)(x)
=V m dd
mmd
m +
(E)
(80)
The first term splits into two components depending on whether i 8 i 8
d=1
Hem (h. (x)) = Σ (P&(( x)))3)
1
Σ II PM(( x)))+ x)))+
V (m l)d(++ DJE,
SE ((S))) 9,
m 1 PA x))) my
+( (m(m + 1)d(m+1)e
Σ
m ++ Hcm Hem-1(h, +0.(
)
d=
sE (S)
(81)
where we used that Σi= Vasi Pu((w x))(w. 0 (dT)) through the closure under-
muliplication of (-)-) and Lemma The second term is exactly the desired expression for
Hem (h" (x)) in Equation 75
Next, we rewrite the first term as:
Σ I(
(m 1
sET (8/8)
Ti
(IPx(W;;x)))22
Σ (
(m 1)d(++1)e
SET m (8/3) s.
T2
34

---

By the induction hypothesis, Ti cancels with -my m=i Hem (h, upto an error 0-( (zr) remains to show that T2 is stochastically dominated as O-( VZz ). To achieve this, we note by Gaussian hypercontractivity (Lemma) 5
it suffices to bound the second-moment of T2. We have:
E
[2
Σ
II Pa(((w (x))))
sE mETm-1(8/)
(PPP x)) Pa((w x))) s
E
Σ
PI x))
d(1+1)Je
SET 2(S/(1.))
where in the last line we used the fact that the cross-terms vanish for terms with He& (ww", appearing once. The desired bound is obtained by noting that by the inductive hypothesis:
x))
Σ
II [Hex x)) 0x ( 1)a)).
(82)
NET (5/0) 81
Therefore the first term contributes d terms of order (d((mmm-))) while the second term consists of d2s) terms of order 2 (d(dm))))) Therefore, both the terms are entropically sub-dominant compared to the factor Xm+tjee yielding:
To O
(83)
de
It remains to show statement (ii) (Equation 77)
We first consider the residual term:
d
Pa ( (x)
(84)
Recall that for any u E Rdd and any r(x):
E [[V"r(x) = E ((xx) v)].
(85)
Therefore, by induction and the closure of stochastic domination under multplication, the above term satisfies (fi).
For the remaining term T2, (ii) holds by noting that by Proposition 6 for each E Vdei, |EE (x) (x) willllp is polynomial in ((w), vi of degree at-least kt 1.
Since (xx, w are orthonormal functions:
vdi
ō 1 |E (C(((m()))) w/11 (3)
d=
(86)
C.7 Existence of activation satisfying Assumptions
Consider any R IR and constant 0. Observe that the activation à R. TR. defined
x(x) (z)) cr,
(87)
satisfies:
(())(=)) = (((()) cr) c(a(x) cr).
(88)
Set (z) as a bounded-analytin function with E (ex))He)2)) + 0. for instance (22) tanh( (2
a) bz, for some a. b # such that such that E (z (ex & for all & N. Furthermore, may further set b E R such that 15~N(0.1) (a(()) 0, for instance by setting b ss 0 and
a 0, a
Then, by Equation
88 the condition R.-NOOD [=))) = 0 corresponds to the following
equation on c g(c) = E.)NOD = =
(0(((z) - c2) c(a(2)) +22)) E (o(((=) cz)] cE, [(a()))=)] 2 0.
By the choice of a, g(0) while the boundedness of further implies that g(c) oc as c co.
Hence 3e E such that g(c) 0. On the other hand, note that 5
35

---

C.8 Feature Learning by the First Layer
In this section, we analyze the dynamics of W1 (part (1) of Theorem 1) In fact, for subsequent usage in the dynamics of W2, W3, require stronger characterization of (i) of Theorem | precise result, we first set up the required notation. Let Dr = {X Ye denote the batch of samples at time-step for t N. Observe that under the correlation loss, and with W2 L, each neuron w; for E [p) evolves independently. In-fact, the dynamics is equivalent to that of a two-layer network with modified activation x (()())))
To state the
Therefore, the gradient descent dynamics on W1 defines a stochastic mapping:
w w(!)
(89)
applied to random variable w ~ U(84-1(1)
Let hFthen denote the filtration generated by D1, ......
.... Let U E R denote the subspace Po-
spanned by the teacher weights W*, Define u* == TPP woll to be the unit-vector along Pw wo- Our analysis proceeds by establishing the following:
(i) The dynamics of (()) is dominated by drift along the initial direction u².
(ii) The overlap of ((t) along W grows linearly upto reaching a threshold 0nd
subsequently w()) reaches overlap x in a constant number of iterations.
(iii) The distribution w(t) maintains isotropy and regularity of tails.
To see intuitively why the dynamics of w(!) dominated by the drift along u*, consider the following heuristic sketch:
d!(() -V Wio
dl
I1* (x)xxo(w((()))) (x))) higher-order terms,
cl
where we substituted the decomposition in Proposition Next, we note that the degree j contribution in E hh (x)oo'
(x))o((((*)) (w(t))x )x] is of the form:
He, He,(( x))o (w (w
de > (ww), (00))
(90)
For j 2, the above term results in drift along ut, while for j the contributions suppressed as long as (w;, w(1)) -(((T))) Analogously, the contributions from higher-order
terms suppressed as long (())) doesn't 't align with individual directiosn wt
We now move on to the full proof. Let x > fixed We introduce the following hitting time:
Tx {inf (uu,, w (()) s].
(91)
Let I" denote the product aagnaa- w.rt (F.). Since is measurable w.r.t ( U (Ww)))). the random variable T then admits a regular conditional distribution w.r.t F*, pa ((F") 48
Suppose that each neuron for E [p:] in Algorithm is stopped at defined above.
Let e ed-da1 denote a fixed basis for the complement of W*, The main result of this section establishes points (i) (jit) described above and constitutes the formal statement for part (i) of Theorem
Theorem 5. For any 0 < k < 1, let [1,, X2,,,.,..) denote the regular conditional measure over w conditioned on the sequence of datasets X,, X2. associated with the natural filtration F.. Then, for any E N, there exists sequence of hioh-probabilitty events & E Urz 1r2 {Ft) such that:
(i) Pr[E] 2 1- Gt for some C' and large enough d.
36

---

(ii For any X1, X2,.. E, the random variable w ~ Mny X2,, satisfies the following with probability Ce- log d' as d 0c:
W k uuu uu +v.
(92)
where n²* 2 16 and:
(a) I U V...
(b) In || = (z)))
(c)
sup ((% w;)1 = w;)l= =0x( ied"1
(93)
vd
and
1
sup jE|d-da1
, = 0-(
(94)
(d) For any (deterministic) w U*:
1
(Iw","""" = Oz(
(95)
VitEi
and for any Ti E U?:
1 [(w1, =oZ Vil
O~(
(96)
(e)
- www- 0-( d8
(97)
where w U()) denotes the initialization of the neuron.
Properties (c) stipulates that WT remains approximately isotropic with well-behaved tails along fixed basis of U** and its complement. This is important for ensuring concentration of bellebe
functions of w in part (it). Maintaining this properly throughout the dynamics further leads to control over the higher-order terms.
Corollary 1. Let w7, be as defined Theorem Then, 36 > and choice of step-size 17 nj d= for some i) > such that:
E wT (w))
(W (W*) /1 x² vd d (1 (W (W*)T(W")) (W*)) (1-(W1))
1
= 0 de
de
(98)
C.9 Form of the Update
Under the initialization W2 = Ip. b1, b2 = 0, W' 1, for any E [pi]. the update to any neuron in W1 can be expressed as:
W w' + (Ia - (w::)())) 1 Σ ('x))o' ,(w'
(99)
w 1+1
w
[12
In what follows, we denote the gradient update as:
g'
f (xx)) x()) (w(),
(100)
and its corresponding spherical version as:
g' = g''(L (I
(101)
37

---

where we recall that ||w[ by the spherical constraint.
Applying the Hermite decomposition to f" (x) and utilizing the composition of Hermite- established in Proposition 9 in the following expansion for the gradient:
Lemma 7. Let C% for I denote the ken- -order Hermite tensor of (z) and let {cu]Rmm be the Hermite coefficients of o Then:
= (La - (we)(w)))
Σ Ck+1 Ch+1 X1...t (w")
(102)
Proof. The above is direct consequence of Stein's Lemma applied to Elg']:
E [xx ((w,)))))))))))))))) x) ff (x)] = "V (x) ("w Vxf (x)
w/F [ I)) + I2 (/) (x)]
The first term vanishes under the orthogonal projection (La (wol)) while the second term results in Equation 102
Combining the above with the recursive Hermite decomposition of (x) through Proposition yields the following form for the expected updates:
Proposition 10. Let (uR]E h {et ( denote the Hermite coefficients of g", o, P respec-
tively. Then:
&
(V2 o2c ( (W-)-- - #1
g+ = (Id (w))
(ww) ())( v))
Vds
VdL
/=3
Σ
C w)) v)
Σ Cm (r. (x)ō x)) wil).
PmCm
Vinmms
m=b+1
JET(S
4m1
(103)
where I' (x) denotes the remainder for the degree-m Hermite term in Equation 75
Proof. Proposition 9 applied to (xx yields:
(x) Σ Pm Vmdmo
Σ
P x)) + Σ Mm m (x).
(104)
mE) #;
Next, by expanding Pa Pa x)) Σ/ Hee x)). the first term the RHS can be further decomposed as:
Σ P (, x))
Σ
II He,, (W w)).
Am
Um
Vd
m.
1+
SET (S) 8t
TD R+1
(ET(S.))
JE(A]* 4m1
(105)
Equation 103 then follows by noting that any term of the form Il Cj. Hej, ((w w)) appears in
C with EnE ja-
The magnitude of the gradient updates is bounded through the following Lemma:
Proposition 11. Let gi,; = a (x)o' (a (o'((,, x)))x({ 1 www! )) denote the spherical gradient
for neuron at time-step Then g1 satisfies:
(1)
gg 2
| [gi]]
0+ doL+
(106)
(ii) For any Rd with || 1:
1 = 0-(
(g), v) [g] v)]
= 0
(107)
vn
Val++ō V
38

---

(iii
1
Pu.gi
- -E Pu
g" 0+(
(108)
V
Proof. We begin by writing:
g
2
g g
E
g
(109)
By the assumption on o, the composed activation ă and its derivatives are polynomially bounded. Therefore, applying standard concentration results for for independent random variables with bounded orlicz norm (Theorem we obtain:
gi E [gi] 0~(V _) O-( V
(110)
n
which yields Equation 106
Applying the same result (Theorem to projections of gi along and Po+ then yields Equations 107 108
C.10 Initial Overlaps
Before proceeding with the analysis, collect the following result the concentration of the initial overlaps along W for the first-layer neurons at initialization: Lemma 8. For N(0, IT,
dd--i (1
0+(
(111)
Proof. Since w ~ (1)), the squared overlap norm ds1 [ w/. is an average over des sub-exponential random variables. Therefore, standard application of Bernstein's 's inequality [83] yields probability of cc log The proposition then follows through union bound over the P1 neurons.
C.11 Difference Inequality
Let Pt- = (W*) (W*) denote the projector onto the subspace spanned by W* For i E [pı]. define u, to be the unit-vector along the projection of w/ along W*:
Pū w
(112)
W* w
00)
Further define m = (u", w(.) and m = =I((p7- u²(u))) (w(())))())))) denoting the projections of ((t) along ut and its complement in the span of W and:
m
V max REVET
kw w/)l
(113)
Additionally, we track the residual component in w(') lying in UT but orthogonal to Wo:
r = =1 w- (w (0) (()
(114)
Our analysis relies on showing that the dynamics of (()) is dominated by linear drift along u This requires a control over the following additional terms:
(i) Residual linear drift along U This term is controlled through bound on mf.
(ii) Contributions from higher-order terms: These controlled through bound on m
(iii) Noise in the gradient updates: This is supressed through the choice of batch-size +5d++))+
39

---

Recall that n1 = +(d Let be any arbitrary value satisfying 0 < 8 < 5 For any > 0, we define the following stopping times:
TN
inf(t: |m² 2 1-k) k)
(115)
T inf(t: |mn) s d= min(m1, mxx:
(116)
Vdi
The stopping time - simply accounts for the overlap reaching the desired value k. The stopping time 73 ensures that for S T/- the three residual contributions in g' listed above, namely the drift along U1, higher-order terms and the gradient noise remain supressed.
Note that by definition, m._
1 by Lemma While both m m2 grow while m vari
exponentially, we will show that for any 0 << δ < 8, there exists small enough such that with step size 7 = rjd"1 T > r with high-probability. Concretely, under small enough step-size, both mf. m grow under approximately identical linear dynamics, ensuring that the initial lead in the magnitude of m. is maintained till weco-rec over the contributions from the remaining directions.
Proposition 12. c p10502 and v) = Fi Define = - A T For any δ < ő1 < 6, and E N, and any constants cth ct, xx Cm: cx such that cm < < cnt ci < c ct. Cx c < cx there exists constants C1, C22 C3, C4 and îj such that for large enough
i1)
1
P(m*+1 2 m² + mom ne m Ci
WI <
2
(117)
d
1
P(m+t1 S m² + nic mm, At V<TT) 21
1-
(118)
dk
(i)
C3
2 1
P(mmt) (+ $ mi + +njtmi nee m'Im'm =702(m²)) + Vdl-=1+01
Vt xT)
dk
(119)
(iit)
C P(mms I m' + fic - nitm + Vdi+ol
Vt <
<TT)
2
(120)
d
Before establishing the above proposition, first show how implies Theorem
5
C.12 Proof of Theorem 5
Suppose that < r" Applying a union-bound over time-steps to (i) in Proposition 12 then implies that with probability at-least t(1 1 1²). for all $ r", we have with high-probabiliyg m ++1 2 m² ne m - -jtt m? - - Cm
(121)
Since 7* < T we further have that me k. for all 1 -- and thus r Equation 121 then implies:
ij Kmms
m 1+1 2 (1 + nc, - (ñct + )))
(122)
which inductively implies the following intermediate bound:
(1 nm (īct. (i)mm)m))
(123)
Since m < Km,, the above simplifies to:
m
++1 2 m² + (nct (1 k)) -ni 'immm
(124)
40

---

Therefore, v4 < T", we have:
m' 2 (1 ijct (1 - n) - -op G/C'n"2'm
(125)
By Lemma 8
have:
1
|m| = d22/2(1-51) + (-)
(126)
Since for small enough 7/, ctt x) i xx 0, Equation 125 implies:
T < Cx.s log d.
(127)
for constant Cx,s 0.
Next, consider the orthogonal component m² 0. Note that m 0 by definition. Part (it) of Proposition 12 along with the discrete Gronwall inequality (Lemma implies:
1-1
C3
m²
nct - "eImmm + Vdl-51+0
j=1==1
[-1
C3
EI
jet ñe (m/2 (26
(m')² +
Vil Vdl-51+01
where used that m s since Tg.
Our goal next is to compare the above bound against the lower-bound given by Equation 123 Since
[log(1 + a) log(1 + b) I la - for a, b O, we have:
(1 + imcm ( + ((())))
S exp( - ctI+ 1c c- -1+ oj((
(128)
(1 + カ . m²)
Therefore, we obtain the corresponding bound:
mi < t texp(ilcn - ctl + - - +(()) ( 828
C2
C2mo +
(129)
For any 0 < 8 < 5, may set lct cT,, lcm ctl and small enough that for any t < Cn.e log
(tñlc,, et + lctt c- 1 + rr²Cxx) + log C2 < <81 -
(130)
Implying:
m d
m
(131)
Similarly by setting lott - cxbbl |c, - cx1 small enough enough we have by part (iii) in Proposition
12
m db
m
(132)
Therefore, while the dynamics m'' m'1, m in m' over m m' through initalization ensures that the hitting time for m' arrives first, ensuring that:
evolves at arbitrarily close rates. The initial advantage
(133)
5
By the definition of 7*, this establishes all claims in Theorem 1 apart from (e). To obtain e, note that by the form of the updates, rf updated solely through the gradient noise gi E [gi and normalization. Therefore, Lemma II implies that:
ri = 0z dvo).
(134)
41

---

C.12.1
The conditioning input set
To complete the proof of Theorem 5 it remains to specify the high-probability set 8, g- For any
5 > 0 and E R, consider the event:
d
_x,8 : Desti
(ggg.) v) - E [g',, v)|l
(135)
di+e+8
Equations 107
110 and a union bound imply that for any & N:
1
Pr[E,,8 dk
(136)
where the probability is w.r. the joint measure Wp, X1, X By the law of total expectation:
1 E Pr(e x 2 jh
Iprree x.
(.xleel 2 dk
(137)
implying, for any le > l N:
E 1| (1
2 dk
1
(138)
d
taking the interesection over is N the required conditioning set & in Theorem
C.13 Proof of Proposition
Consider the "effective" activation:
((x) = o'
(139)
Let 82 E. [ (e))))) Define the constant p2c By assumption 3
0.
part (i): Applying Proposition
we obtain the following decomposition for the update gr:
gi = -I- ww((((w((1)
111 P10222Pu-w!
Vdta
d
- (t))))
uidfe
1
Σ [(w) w) w +
Cm
1
II
(( W
Vdti
mEd
3m3
m.m 1
JE
aml
+ (I - (w(())
(mmm (x))((((w) x) xx)
+ (I - ((()(
E gt
As
(140)
Since m, (w((), u²), |w(|| the first term simplifies to:
Va (ic502(1") Po. (t))
( w(( Po. w(t) cm - cm?
(141)
Va
Next, for AJ, separately consider the component along w for each i vdEı
(Ai, w/) = Σ
Micte 1
((W), w)) pm Cm
Σ
m-
C ((w,, w)
Vidmms
1=3
(E((S JIM [=1
(142)
42

---

m vd
Each term of the form (w w) is uniformly bounded as O(d(m=1)e:) we obtain:
Since m), sm = 2/
(( wi)l
(
(143)
for some constants oj with sup,ley sc. Therefore geometric-series bound (applicable since m 1) yields:
KA wiYl
v m
(144)
for some contant C > Summing the above bound over i E vdFi, results in the bound:
| S
m
(145)
vd
Next, for 42, first apply the Hermite decomposition of o' to obtain:
E fm (z))())(((wwx))))
2 (rm (r))
(146)
By Assumption 2 c
O while (ii) in Proposition implies that the terms corresponding to j > 2 (m*²) )a
bounded as 1P-
We therefore obtain:
Om Vd
A
(147)
for some constant Č > 0. Lastly, Lemma implies that:
1(A3, u²) = 0-( dks+0
(148)
Since t < T3 the above bounds on A,, 22, As can be absorbed within arbitrarily small constants compared to m:
KA, uz) + 144, u²) u²) ((As, u & Cm
(149)
for arbitrarily small constant C > 0.
This results the bound:
m' + VaEi m n²(m²))
m ++1
(150)
V + 172 1
where ē E. c & for arbitrarily small 8. Next, we use the inequality v + 2 (1 i)) for / 2 0 to obtain:
(11 12 1
172
2 110²113)
(151)
1
21 1
1,'² mb))
where in the last line applied the control over the squared gradient norm in Lemma 11 and Co < è can again be set arbitrarily close to Combining with Equation 150 yields part (i).
Next, for part (ji), introduce the operator:
Pot = (I- (u' (u=""")u'))))
(152)
corresponding to the projection onto the orthogonal complement of u² in U* Let u', = (I ( (t)
43

---

gellr (I (I-W()(w(0))
(W") + -I- (( Art
Viti
(153)
+ +II-w (I-w!((w(0)) T) A2 + +I (I- (w P)uu-ss
Pu
Since [P w'll = m4 and Pu. will = m' the first term simplifies to:
- (w(()) 11 Pr (W")"""""""""" (W")w")
s
Po (W*) (W")w")
Vi
Vizi
M10202
(wo()((()) P (W") (W"))("")
vdsi
=mm'1 - cm'm'..
By Equation 145 have:
(I - 1. (w-) &1Ai|| S
m
(154)
vd
for some constant C'> 0.
Similarly, by Equation 147 we obtain a bound:
Ö m
[I (I-
A2
(155)
vd=
The above combine to result in the term (02xm²²) in Equation 126 Proposition 11 Pyp is bounded as:
Finally, by Equation 108 in
[[ (w 4s 0~(
(156)
v /di-
yielding the last term in Equation 126
Analogously, part (iii) follows by considering the terms (w;, E V for j = 1,2,3 for (Mi)
respectively, with the bound on || remaining the same.
C.14 Feature Learning by the Second Layer
To motivate setup for the training of W2, start with heurestic discussion of the dynamics of gradient updates the absence of pre-conditioning and projections. Throughout the subsequent discussions, denote n2 and P1 by n, p respectively. The presentation of formal results towards the proof of part (fi) of Theorem starts from Section C.18
C.15 Updates in Feature Space and Projection Onto the Kernel
Under correlation loss &. (x))xx(xx, the gradient update for neuron W;2, i E [p] in the second layer has the following form:
w
1+1 1.2
w VW w +
RP
(157)
Under the approximation f(x) 0, the updated pre-activation out of at fixed input are thus given by:
(w) o (Wi(x)) = o(H(())) + n
fr (xx)a.0 (1
+
(158)
44

---

Letting ( (x) =
we obtain:
2, (x) (x) + y2 (
(I"(X)o' (X), (X)):
(159)
with X E IR the data matrix and Z denotes the feature-mapping (
We see that in the limit n, P1 - oc, the above update results in a projection of f on the following
Kernel (integral operator):
Ki (1 = Ew [o((w, x))o((w, (w,x
(160)
where li denotes the distribution of the rows of W obtained upon feature learning in part (i).
C.16 The Role of Preconditioning
In light of Equation
159, we obtain dynamics of the form:
(x) = (x) + Exx [i (x)) (x() (x')) + noise, 22
(161)
where Ki (i (x)oo (h2 (x)) denotes the projection of f (xx)o' ( (x)) onto the Kernel K Through central limit theorem-based based heurestic, we expect the noise to be of order 0 ( + vB 66
However, the decay in K₁ 's spectrum, entails that the degree-k: components in Kxf'(x)) (x)) are of order 0 ((*)) Comparing 0 vi } and O ((t)), expects a somple-complexity of d for recovering it (x) through a single (non-precondittonee) gradient step. For quadratic features, this is precisely the sample-complexity obtained in [66].
A possible way to get around the additional sample complexity would be to re-use single batch of size (ddx) for up to (dde)) steps, ensuring that the projection on the Kernel is well-approximated at each step while the number of steps are enough for the dynamics described by Equation (59 to approximate ridge-regression, which effectively has the same effect as are-conditioning through the removal of the learned components. However, analyses of gradient descent with the re-use of batches for a large number of iterations is expected to be challenging due to the accumulation of additional correlations and memory terms
32
Therefore, to allow simplified "online" analysis opt to include additional pre-conditionin in the updates, which effectively removes the extra / factor from Equation 159
Remark: Under the additional assumption that 1 [o(2)=] = 0, 666| improved the sample- complexity for recovery of quadratic features from ((d") to (dP). Such an assumption on (-)) however, appears insufficient towards reducing the general (dd2k sample complexity to (dd*) for general degree components.
C.17 Main Result for part (ii)
This section deals with the recovery of the non-linear features h" (xx).
Theorem Let W. denote the updated layer 2 weights after a single pre-conditioned gradient step with batch-size n22 with initialization W 0p2xpr as in Algorithm
W! = -n w (ooWixT)TTWWW.2 + +
Vw2C.
(162)
where W1 E Xd The updated pre-activations h = (W1x) then satisfy:
xd denotes the updated weight matrix with independent rows obtained as per Theorem
h2 (x) = 1 o'0) (x) + r(x),
(163)
where W3 the readout sealar weight and the remainder r r(x) satisfies:
r(x) = 0=( 6 -6)
(164)
45

---

C.18 Structure of the Pre-conditioned Update
Let denote the feature matrix = o(WW) applied to an independent data-matrix E Ru using the updated weights Wi obtained in part (i). Throughout the section, we assume that the threshold parameter x > 0 in Theorem 5 is fixed to some dimension-independeen value and occasionally consider the limit + 0 (but after d + 0). Denote by (xx) the same mapping applied to fixed point x E RR.
The proposition below expresses a pre-conditioned gradient update on W2 as "Kernel-ridge regression like" update to hx)x). Proposition 13. Suppose that W2 re-initialized The updated pre-activations l2(x)) satisfy for i E [P]]
(x) "wy,) n
(x) { -2
(165)
C.19 Decomposition into Radial and Spherical Kernels
Let ig. 0% for l E N denote the associated Laguerre and Gegenbauer polynomials in dimension d. Recall that U* denotes the span of W
From Theorem for any i [PI], the updated neuron w! can be decomposed as:
W u, + Vi:
(166)
where |w] = L, u, E U and v, E UT
For any x E Rdd, denote by x", x², its components along U and U1 respectively.
Next, we decompose the inner-product (w,, x) as:
||x*|| + xx (v, X1
x"
(w, x) |xx (u,
(167)
||_||] ||
By the Gaussianity of x, the random variables ||x*|| (u: | ||* (v, 1 are mutually independent. The variables ||x*|* and |x_]| are distributed as x2 variables with d and d d' degrees of freedom respectively and hence admit the associated Laguerre polynomials as an orthonormal basis (Section C.3.2). Therefore, (w, admits an orthonormal basis given by the tensor product of associated Laguerre and Gegenbauer polynomials.
By expanding along this bases of associated Laguerre and Gegenbauer polynomials, the activation ((w,x) b) can then be decomposed as:
((w.,x) + 6)
Σ
x² 2n (b, ||u:||, [[ ([xx (1x="))) (1x11R)) (dF)
10 (d d (v,
x
))
|x
x
(168)
where L Pd denote the associated Laguerre and Gegenbauer polynomials in dimension d respec- tively. The above convergence holds in Le w.r.t x ~ N(0, Ia).
Proposition 14. For all k E N:
lim lim of (b.. (b) R x d
(169)
Proof. Let d_ == d - d=, then:
o((w,x)++b) -o (1/1t |xx| del dei
x* Wdiuu, ||||
||x||2 - di v(d1)(v,
X1
+ +V++ dp
+ +b)
||x_||
(170)
Let rr = |x|2_1 and n = | Subsequently, the result follows through the Taylor ex- vi
Vd
pansion vi + = 1 + + o(22) w.r.t ri, while noting that vd (u, - - N(O, R) and
Vidijlv, x + N(O. R) by Theorem for some R > k.
46

---

The Taylor expansion implies that the coefficient of r" converges to mb( ( On the other hand, the coefficient must also equal Σ5zs a S5.. where Gja denotes the coefficient of = in the kin associated Laguerre polynomials.
In light of the above decomposition, introduce the following sequence of radial Kernels, with kj = h2 = j2 =
(x1, X1, x2)
E a (,,,,,,0.,, |uil IewlDDa a.o.o (b, || [vslD Of" (Ixxil) <1x 11²)
J
(171)
Proposition 15. Under Assumption
hi.2. Kö admits uniformly continuous cottinoossssussessefnuntun eigenfunctions 11, 22,d
with associated eigenvalues A1 ( 2 O ( such that r (xxxx -ेे (1|x*11 1) satisfies:
(x) P a o (x) 0(
(172)
v des
where I denotes projection in (xxx)))).
Proof. By proposition 14 ag converge a.s deterministic limits of as d + co. We obtain the following limiting expression for K xx)x
x2) E, [a + E, [a 4 (1x (1|x) + Es [0o01] (000)) (173)
+ Eb [a001] (1xx)
+...
Note that:
[600ll22 /1 = E. [ao]] d Es [bā(t]]
(174)
By assumption on o, (b) analytic in b and hence non-zero almost sure w.r.t b N(0, 1). Therefore, by the variational characterization of eigenvalues for compact self-adjoint operators
16 we obtain:
(Ko(x,),))) > Es [ao())ao(b)] 0-(
(175)
implying:
X1(Ko(X1,x)) =a(1),
(176)
Similarly, we obtain:
E [1xx (2)))(((x)))/// (1)x((1 = Es [a O
(177)
d=l
implying:
>2(Ko(x,x)) = Dal del
(178)
Analogously, since a is analytic, with probability 1, agiu # 0, we obtain that the ju eigenvalue for Ko(x, x') satisfies:
Xx(Ko(x,))) Oal 1
(179)
dšer
Equation 172 then follows by noting that:
E [r (x) x')r
aa(
(180)
de
The continuity of the eigenfunctions then follows since we have: (x) = Ex [X x x') (x)a(x)))
(181)
Since K(x,x')
x') ) is uniformly continuous in x.
47

---

C.20 Decomposition of the Feature Matrix
For ji, ki E N, let 0g k1.2 by denote the cigenfunctions of the radial Kernel Kg for k E N, defined as (Generalizing Equation 171:
K1,22 X2)
Ja Ji.ki " (1x
(|xx 13 (11x21 (1 (||x² x 11
Ji 12.3
(182)
Analogously, let n Ai.ik denote the eigenfunctions of the associated companion Kernel defined on the weights:
N A2 (w1,
w2)
Σ
jj &y (W1)a Ao (W2)
(183)
==0."=0
Define:
0
f1.k1
(184)
And for the conjugate:
Jn. (b, |ull, [ell) |lll [[vl)
(185)
With a slight abuse of notation, we denote 0d 3,0.0,0 and ad *,000,0 by 0g and ki respectively, These correspond to eigenvalues for the zeroth-order radial Kernel along U+.
We partition the indices j1. 1 2 into three disjoint sets:
81 [Ji, ki, h2 kn j2 122 = 0, - 2 U {í,, j2, ki k2 51 = j2 = k2 = =0, I kj
82 (J1.22, ki, b2 j2. 2 2/2/ + k1 h2/E1 k} 8,
8, = U1, h1, k2 E E U.2).
The above partitioning is motivated as follows:
(i) 8 corresponds the set of cigenfunctions whose projections can be approximated via Z with 122 P2 ((dke)) and are relevant towards learning (x)
(ii) S2 corresponds to the set of eigenfunctions whose projections can be approximated by Z but do not contribute to the learning of f*)x).
(iii) S3 corresponds to the high-degree set of cigenfunctions for which the number of samples, neurons f12; P2 are insufficient towards being approximated through Z.
Let R5.R Ry denote matrices with rows 0d jn ja, (r*,rl) and xgt ki (b, || ||vl] respec- tively. Similarly, let L K2 (X), Ja and J2, (x)
(W) denote matrices with rows da As An (x)
Expressing Equation 168 in matrix form and applying Proposition 3 to expand each term Qf(:), obtain the following decomposition:
z
Σ
(D) lul) Σ ((X*)D()Y,(U))
An (X)
J1.ja ky $ 52 (W)
(186)
Σ
V Vn (X) 83
& $ M
where Dj denote diagonal matrices with entries (62)2 (af)² respectively. We denote the above three-components corresponding to 8, S2, 83 as Z1, Zz Z3 respectively.
48

---

C.21 Approximation of Eigenfunctions
we obtain M = (dd=). We next show that the above partitioning of eigenfunctions translates to "spike"+bulk structure for Z, with the spikes arising from components corresponding to $1, S2 allowing the reconstruction of the corresponding eigenfunctions through the sample-covariance. The higher-degree components 53, on the other hand, coalesce into a bulk.
Let M = | Since B(d, k) - O(d*) (section C.3.2
For each x E IRd, let v8, Us, (x) E IR denote the combined vector of components along eigen- functions indexed by 81, 82, ie:
(8, (x) = ((11 ((1)).22 ja (1
(187)
Analogously, define:
(w)) = do baet
(188)
These properties are summarized in the following proposition, which constitutes the central result of this section: Proposition 16. There exists sequence ca with ca (1) such that
ii
(x, -M
= 0x
(189)
d3
(ii)
L8 (w:))s, -IM p
0
(190)
d3
(iii)
-z23 = -calld + +02(
(191)
aminl 6
(iv)
11330 (W)ll = 0-( 0 P2
(192)
Before proceeding with the proof. we highlight the key-takeaways from the above result. Points (i), (ii) imply that the matrices Z1, Zz contribute M spikes Z with left, right singular vectors aligned with L,,,,,, (x) and us, (w) respectively. Points (ii), (iv) imply that the high-degree components Z3 contribute an approximately isotropic bulk, that doesn't 't interfere with the spikes along us (w). Note that (ir) is necessary since the large rank of Za could cause the correspond- ing components to collectively interfere with the low-degree components.
The crucial consequence is that the spikes in Z1, Zo allow effective reconstruction of the components along S₁ U 82. In contrast, the failure of Z3 to estimate the covariance structure along S3 prevents the recovery of such high-degree components.
and the hyper-contractivity of the spherical measure. Equation 190 however, requires additional control over the error in w.
Proof. Equation 189 is direct consequence of Lemma and
We start with showing that the covariance is well-approximated in expectation Let E R", ||vl = denote an arbitrary fixed unit vector. Then:
v T E [os.us, (w)os,us,(w)) (w) 1M v
E Σ
(w) - 11
(193)
#Ealusa
since vs are uniformly lipschitz on Sa, applying a taylor expansion on w around u yields:
E
Σ
E
Σ
0
1
(194)
Lo881U82
L888,
49

---

where we used that (w) E ESES, J8g (w) is an even polynomial in w. Therefore,
[Vh, (w)] = while || h/hoow) (w) || I C for some constant > 0. Corollary then ensures
that the second order-term is bounded as 0 +z) ). Taking supremum over e for ||||| 1, we obtain:
E Us, (oo)ss(ww)))) (w)ds; (w) IM ]| 0
(195)
We move on to establishing the concentration of 4gg, (w). By Equation 28 63 spherical harmonics Ym,k of degree k E N admit basis with the following representing along the cartersian coordinates:
for some
d-2
Ya(w) = ha W2)
II J=1
................................ + w w (w] +.......
2s/2 Q()))
Wd Wd-j+1
(vu W + ... + w
(196)
where N contains at-most e-non-zero entries. Therefore, Y. is polynomial in at-most É coordinates in along with the l projection norms rj E wz. Applying part ii, c of
Theorem then implies that:
sup iede
Σ
(w w;)) = 0-( t
(197)
5=1
Subsequently:
| (u,) y (uz) 0-(
(198)
d
and:
Ya (u.) - Ya (uti = 0 2t))
(199)
Taking a union bound over the @(dhei) values of a yields:
E max V22 (w) (().
(200)
For the radial components recall that [|u]] |||||| = x1) while the radial eigenfunctions are continuous. We conclude that:
E max Ilss,us, |2| = Ö(M)
(201)
Setting < 8, 8' and recalling that, no (d to) ), O(dhtit0') while |8, U8 = (dtte)
we may apply Lemma to obtain:
| (w) (w)os,us, (W)T - -E [ (oruuss())ssss (w)ds,us, TIl 0~
(202)
where we absorbed the d factor into the p
1 factor in the bound in Lemma (Equation 63
The proof of (iii) similarly follows from Propositions 4, in 60 We outline the central steps.
First, via the expansion of (-) given by Equation 168 for any V (x)
4bs (w) can be expressed
as o((w,x) + b) - ss...s(()) (x. (w). Through Equation 196 L (xx (ss (w) therefore
depends on w only through finite number of coordinates U*. Analogous to Equation 202 applying Lemma 2 and using p >> > n, we obtain that:
1 2zz - Ga(X, x) = 0~ 78-88)
(203)
/
where Gx(, denotes the gram-matrix matrix associated to the Kernel:
xx(x,x)= Σ Xe (x),,,)),,
(204)
SEgg
50

---

applied to the data-matrix X E Rexd
The gram- matrix G3(X* X*) now corresponds exactly to the spherical distribution on U*, with decay identical to the case of spherical data in [58]. Therefore, proposition 8 in [58] applies, which entails that the off-oiigonal contributions from G3(X", X*) are neglible operator norm. This results in the bound:
|Ga(X", call| = 0~( 1
(205)
for constant implying (iit) and (iv).
C.22 Properties of the Feature Matrix
Having established Proposition 16 and the concentration of the top eigenvectors, the setting of is now reduced the spike "bulk" structure in the proof of Theorem 1 in [60 with (dd*=i) spikes arising from the eigenfunctions S1, 82 corresponding to near-identity sample-covariancee and remaining bulk with uniformly-be -ooounddl- operator norm. A consequence of such structure is that the top singular vectors of Z align closely with these "spikes". This ensures that projections onto Z "reproduce' functions in 8 18
Therefore, the proofs of Propositions 6, 7 in 600, based on perturbation inequalities for singular values, singular vectors, result in the following estimates for Z: Proposition 17. vi Z admits a singular value decomposition
z = U. + U2SV - U3S.V3 vp
(206)
such that:
(i) mim (S1 U22) Oa(1)
(ii) SS: - call| = 0d.p for some constant C3 > 0.
(iii) v s,uu - = nz) and 1 suus, V = oalvp)
The proof of the above Proposition follows directly through Proposition 6 in 600. The above result exactly charaterizes the projections of functions onto pre-conditioned features:
Proposition 18. For any g Rd R such that the projections onto radial components of degree
are (1), for any 22 = O :.:
x(x) - zT 7 7 121) '7T 9 = -ssgg()) + +0
(207)
d
The proof of part (ii) of Theorem 1 is then completed by showing that under Assumption 1 the projection onto 8, exactly along h (x):
Proposition 19. Under Assumption
P Ps,9(x) u1h (x) + oa(1).
(208)
Proof. By Assumption 3 and the composition of Hermite decompositions (Lemma 9. the non- vanishing terms along the radial component ||~:||2 consists of total input-degree-2 and 2 while the remaining terms on the complement hū have degree at least 3(k: + 1) S, therefore consists exactly of the subspace with effective degree k.
C.23 Proof of Proposition 18
Let g(x) (xx) (LZ
"2 T Z
TT 9(X). Proposition is equivalent to llğ(x) 9(xx)112
(1). Expanding, we obtain:
[xx()) Pag(())1 11x 2(j(x), [1x())
(209)
It therefore suffices to show that:
((.x), ||?s,9(x)11?
(210)
51

---

and:
[ 11 ||Ps,
(211)
Let 98, denote the vector with components:
98. [g(x) (x))
81],
(212)
Let Ag2,6 denote the diagonal matrix with the corresponding eigenvalues. Then the above terms can be expressed
-Z (xgxx) - 98, D&, $
(213)
7
and:
[[xx)) g(X) - -ZZ + +222) 9(X),
(214)
where E denotes the feature covariance:
Σ= E p [xx)))(xx))
Σ
$ &n (1 As (W)
(215)
P k1.
To compute the above terms, Proposition similar to Proposition in [60] Proposition 20. Under the setup of Theorem 1
17 to estimate certain intermediate quantities
with the decomposition of eigenfunctions specified by
Equation 186
(1)
05 z(- 22-zz zT Z + X21)) Ds. -mm 00(( 1
(216)
d3
Ds, 05 7 7 n
7 + -21)-177
1
188 0
(217)
P2
d2
M z - z A21)
08 Ds,
= 021
(218)
d2
(ii)
| = 0~(
(219)
d2
Under the above proposition, the terms given by Equations 213 214
simplify as follows:
gs, Ds, 1
zT 2 A² -TT g(x)) 98, Ds, $5 Z A2
2T,201,((x)
n
n
1 7 2) 2)- (2 + 98, Ds. $5 7- -2 9x))
98, Dz, $
9(X)
By Equation 216 the first term converges to [|Ps,g(x)||* while the other two terms are bounded as (_(#) by Equations 218 respectively.
Similarly,
1 ((X)T2(-2) T) 2z - 9(X) =(x)) -- - 9(X)
x((X) 2 - -zz-zzz 2z -'1 9(X)
By Equation 218 the second term bounded as (1). This completes the proof of part (M of
Theorem 5
52

---

C.24 Proof of part (ii)): Fitting the Target
Upon the completion of part (it), the second-layer pre-activations h2(x)) = W20r (Wi)) are approx- imately equivalent to those of random Saauuremmappin applied to the scalar input h (x), with the random weights of the feature mapping given by Φ cu'. with c no (0) as in Proposition R.
13 Hence, introduce the Kernel (). R2
(=1,, 22) = Ew [o + (co + b)].
(220)
For Z E R", we further denote by K(Z, 2) the corresponding gram-matrix K(Z, E R with entries
KlZ, Z), K(z,,
(221)
Let HK denote the RKHS corresponding to the Kernel K. Let H" E R=XPi further denote the matrix with rows h" (x,).
Since the moments of h* (x) are uniformly bounded d, we obtain:
Proposition 21. [[2 For any 8 > O, and large enough d, 3 constants c, C such that with X
O(vn):
(((, H ( K(H ( H²) + An) 1 g - g0(h")
[[ls (l1-g"(h")) l1llbb JE3G
inf
n
C (og())
(222)
where H RN contains independent samples h" (x), and Nx (A) denotes the "effective-dimensionn"
Nx(() Tr[(K + 1)-K,],
(223)
which admits the following trivial bound:
Tr Nk(A)
(224)
X
We next translate the above bound into generalization error through a control of the approximation error term
Note that the uniform bounds on the moments of h² (x) and Markov's inequality, for any E >
3R > 0 such that for large enough d:
Prih"(x) & BR S
(225)
Next, define the following class of functions:
Je = {s E HK supp(ʃ) BR.
(226)
Then:
[1I- 9* (h²)11 feR(x
inf
1111lloo +x1
inf fet.
[If g (ht) A1ffllox
(227)
Restricted to the compact set BR,, universality of random feature Kernels with non-polynomial, oolynomially-boundae activations 78 implies that for any 0, 3.e E Hx such that:
[[|s g" (1*) 12 X 111 feg,
inf
S A1
(228)
Therefore, by setting small enough such that:
de llfel S
(229)
we otbain:
inf [|I (1h)) + 1l1fll + fes,
S 25 + (1") 11:
(230)
53

---

By Cauchy-Shwartz and the uniform bound on E (h*)), the last term in the RHS is bounded by C' for some cosntant C'
Subsequently, we may set n in Proposition 21 large enough such that:
Tr K log(
An S,
(231)
Implying that for small enough A(E) and large enough nt5,, 6), with probability 1 ||k(h", (")("("",,,,,"" H") + ATI) g (H") (h* (1*))12 - Ce,
(232)
for some constant C' C>0
Now, returning to the true features (x), it remains to combine the above estimate with the concentration of the gram-matrix the associated Kernel. This is established similar to the proof of Proposition 16 through Lemma
Note that the above argument does not yield the dependence of X, n. E. Such explicit depen- dence requires finer control on the approximation, source terms. For such an analysis, we refer to the explicit rademacher complexity based bounds for ReLU activation in 29
We remark that more quantitave estimates can be obtained through radelacher-compleetty based analysis for specification activations such as Relu [2
C.25 Relaxing Assumption 3
In this section, we adress the requirement of Assumption Banemntttoonnnnndd steps towards relaxing Assumption 3 simplifies our analysis by ensuring that f*() is exactly h*(x) arising from the first-order Hermite coefficient of g" (x). In general, however, the degree-k approximation contain additional components involving higher-degree dependence ht (x). For instance, if g" g"(xx has a non-zero second-order Hermite coeffient, then Lemma 9 implies that Hez (x"()) can be decomposed into components of Hermite degree 4, 2k. Therefore, if k > 4, gradient updates to W2 result in h2(x) c(h" + + higher order components). While ideally one would hope that the learning of such additional components would only help towards fitting (x)x by wy, this would require the second-laye pre-activations to disentangle' h* and the remaining components i.e. to specialize across non-linear features. Analysis of such specialization remains challenging due to the reasons described in Appendix 2 Therefore, relaxing Assumption 3 requires going beyond the single-spike (r 1) non-linear feature learning.
(x(x may
Additionally, as we saw through the decomposition of the activation into radial and spherical argu- ments (Equation 168), the radial components exhibit slower-decay w.r.t the degree. Therefore, de samples, neurons suffice towards learning degree-k components
Vेन ||x* I| which correspond to degree 2k components on x. We believe this to be an artifact of our choice to special dependence along the radial component. Going beyond the isotropic a = 1 setting is however, challenging due to our reliance on diagonalization of the associated Kernel along a fixed basis.
1, which leads
D Deeper networks: Proof of Theorem 2
D.1 Independence of features
The independence of h (x) follows by noting that by induction, for all [L], distinct components of (x) depend projections of x along distinct subspaces.
Lemma (Block-wel wise independence of hidden features). For every layer index & (L), the random
variables [n (x)) m= are mutually independent and each has zero mean and unit variance.
dec
Proof. We prove this result by induction.
Base case (e 1). The first-layer features are hx) W*x with orthonormal rows. Hence the components (wi,m. x) are i.d. N(0, 1) and independent.
Induction step. Assume the claim holds for layer 1. Fix m [d and recall
h2. (x)
- a Pk.m.e hi- (x))
54

---

where Bm is the m-th disjoint block of indices of size d 1 By the induction hypothesis the entries of 1, (x) are independent of those in any other block Bmn (m' * m). Because m.,, and the inner product with aj.m are deterministic maps, fi.m (x) depends (x)mm(()))))))) (x) for m' + m. The variance- normalization follow from the definition of Pk.m. and the scaling 1/ 1/
only on block B m and is independent of mm
This concludes the proof.
D.2 Proof of Theorem 2
By the independence and asymplotic Gaussianity of the features hī (x) we expect the above result to extend to a general number of layers. However, proving such result in its full- -ull-alerrll requires accounting for the non-asymptotic rates for the tails of h2 (x) and the associated kernels.
Instead, we prove a weaker result corresponding to the hierarchical weak-reeovery of a single non-linear feature a general level of depth, given by Theorem 2
The central tool underlying our proof is a propagation of byper-contractivity through the layers: Proposition 22 (Propagation of Hyper-contracttiitty) Let f R + R be polynomial of finite- degree k. Then, for any E N:
(i) hx(x) xx))..
(ii) E [xb]( Ō( (iFE))
(ii) E (x) - Ipr = Ō (2)
Proof. The proof proceeds by induction. For l = 1, the statements hold by Gaussian- hypercontractivity (Lemma 5 since He, for distinct wi are uncorrelated, zero-mean random variables and thus (x) has all moments of bounded order.
Suppose the statements hold for some E N. Applying Lemma we obtain:
E [eH (ht) O
(233)
Vise
for any O. Subsequently, applying
8 leads to the following propagation of tails:
hi+1, (x)
ViEe-1-5r ai PePm
(hi_ (1-m1114(--1))0-- 1yote- "e m 4r) (xx)
Vor-
0z((),,
Vi
where we used the bound hx(x) (1) by the induction hypothesis. By Lemma 8 and Equation 233 for any 0, we obtain that:
[[ht+ (x)] = Ö(Vdre-eer ) Ō
(234)
Vdl VEe+1
The above proposition establishes that the hidden features h (x) maintain errors in means 0 Va
and preserve tails of the form O (1). Theorem 2 then follows by noting that the above error bounds suffice for Proposition 16 to hold for the Teature-matris o (Whhj., (x)). Concretely, (x) = (1)
ensures that Lemma 2 applies while the errors in means, covariances suffice for the expected covariance of spherical harmonics to converge to I.
Analogous Section
C.20
introduce the following partitioning of the indices:
S (ii, ki ki = 0, < 2k} U Ui. k1, k2 : j1 = =0, S k}
8, kiiki E (8) U8,).
55

---

Above, we only have two partitions opposed to the three partitions in Section C.20 since the features 1 are no longer partitioned into disjoint spaces, unlike the partitioning of into
x" Section C.14
We again write:
(Whi-1(x)) = Vs (x)-1()))) + V&, (M)
(235)
Unlike Proposition 16 that involved approximations W, the above decomposition involves ap- proximating h (x) through equivalent Gaussian-inputs x. The proof follows that of Proposition
16 with Proposition 22 implying that:
ss (hi-1 (xx)
- ll = 0
(236)
For the corresponding non-linear features along W, since the rows of W are independently sampled along (S)( we directly have:
Ss (Hi-1 (w:- (h ( Il O~
(237)
d
The remainder of the proof follows that of Propositions 17 and 18
E Extension to MIGHTs
While our analysis restricted towards the extension of our results to r 1:
we discuss here the primary challenges and directions
(i) Spherical recovery: Under the assumption, at some constant c, our analysis for the recovery of WT, ... W by W remains identical.
and (1(g") = 1. for
Specifically, each neuron w/ recovers u² Pwt prt.... w: w!
|wy ......:: wt!
(ii) Specialization: Even under the above symmetric setup, single pre-conditioned gradient step only leads to recovery by h2(x) of the symmelric direction / + (x). Hence, extension of our analysis to r > requires specialization through multiple pre-conditioned gradient steps. One promising approach achieve such specialization is through the use in the target g (-).
of the staircase mechanism
F Details on the Numerical Investigation
In this section, we provide additional insights into the numerical illustrations presented in the main text. We refer to https//gghhaa..oom///e/ccccccoop for the code.
F11 Shallow methods
We illustrate Fig, [ the performance of two shallow methods: kernels (orange) and two-layer networks (green). At stake with three-layer architectures (red and blue), shallow methods are not able to perform non non-linear feature learning, hence resulting in suboptimal performance. Below, we provide additional clarifications on these methods.
- We consider a quadratic kernel kxx,, x2) = (x] x2)² + (x] x2) + c o PTua (x1 (x1) Pquad (x2) that an optimal choice among kernel mappings in the data regime explored (n = (d)+))) (), as follows by the asymptotics results in [60] The feature map Pqqudd is not learned, therefore we refer to kernel methods as "fixed feature" methods. The lack of feature learning, and therefore adaptation to the relevant low-dimensional subspaces present in the SIGHT target f*, results in a large error value achieved by the best possible kernel methods (signaled with an orange solid line in Fig. 2 that serve lower bound for the simulations (shown as orange points). This bound coincides with the best quadratic approximation of the larget as shown by [60] The figure shows also neatly the presence of the double descent peak when the number of data equals the dimension of the feature space, sometimes called the interpolation peak: Openk d(d 1)/2 12/2+dl this is illustrated by a vertical orange dashed line in the left section of Fig. 2
Kernel methods
56

---

10
10
n-
di
n
d- 60
Bed
Best
10
10
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
0.50
0.75
1.00
1.25 1.50
1.75
2.00
2.25
log(n) / log(d)
log(n) / log(d)
(a) Reinitializing
(b) Without reinitializing
Figure 5: Reinitialization of subsequent layers: The plots compare the generalization error achieved by two variants of the layerwise procedure in Theorem The left panel illustrates routine with reinitialization of the subsequent layers against procedure where this assumption is relaxed in the right panel. There no substantial difference between the two algorithms when looking at
the generalization performance. The target is (*) tanh (at P3 (Wtx)/Vde.=))) and the
hyperparameters are listed in Sec. F.4
10-1
10-1
Beed 2 Layse Random
d 60
d 90
Random
10-2
0.50
0.75
1.50 log(n) log(d)
1.25
1.75
2.00
2.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
logtnad / log(d)
(a) Fresh batch layerwise
(b) Reuse batch layerwise
Figure Reuse of the same data batch over layers: The plots compare the generalization error achieved by two variants of the layerwise procedure in Theorem [ The left panel illustrates routine without using the same batch of data for different layers training, while on the right this assumption is relaxed by always holding constant the total number of samples seen for every layer. There is no substantial difference between the two algorithms when looking at the generalization
performance. The target is fx) tanh (a* P3 (W) /ddi=111/2/ and the hyperparameters listed in Sec.
F.4
Two-layer networks Two-layer networks are able, on the other hand, to capture linear features in the SIGHT target f (denoted W in eq. (I). This is exemplified in Fig, [ by the green points, with a net decrease in the test error with respect to kernel methods (orange ones). The generalization error shows transition around the expected the linear features W* are recovered (shown in the illustration by vertical black line). However, we observe that two-layer networks in this setting cannot surpass the green solid line, corresponding to the best quartic approximation the target. This explained by the fact that, although partial dimensionality reduction has been achieved d + d = vd, two-layer networks are still performing
1.5, where Theorem Ipredicts that
random features in a vd- ddddimensional space. Therefore, with n = p = O(d)) O(vd') samples and neurons, can fit the best quartic approximation of the target 60
F.2 Three layer networks
The results portrayed in Fig. show stark contrast between two and three-layer networks, with the latter surpassing the best possible performance for shallow network (green solid line) thanks to the presence non-linear feature learning.
We consider two training routines: a) the layerwise procedure, resembling Theorem and algo- rithmically described in Alg. T b) training using backpropagation and vanilla regularized gradient descent for all the layers jointly.
57

---

Layenbee vuatiing
Layowbe traiiing We detee ton sysr helge comuu
jurt traiiing
Join
4x k0m
20
33
10r
15
50
31 33
10
100
(a) Layerwisc training
(b) Joint Training
The plots illustrate the behavior of the training and validation losses as a function the iteration time. It shows respectively on the left the layerwise training procedure inspired by Theorem [ (Alg. D. while on the right standard joint training using back-
Figure& 8: Training/Validation Validation loss:
propagation. The target is [*) tanh 3a' P3 (W*x)//ve (W"*x)/Ve:==17 and the hyperparameters
are listed Sec. F.4
Throughout this section we will consider slight generalization of the routine in Alg. 1 we will update the second layer weights reusing single batch of size O(d*r) for up to (dths) steps instead of using a single gradient step with preconditioning. We refer to Sec. C.16 for discussion on the difficulties of analyzing rigorously such routine.
Remark on Algorithm
1
Moreover, we do not follow all the theoretical prescrip- tions needed to prove rigorously the results and included in Alg. The goal of Figures 5 and 6 is to exemplify the capability of lifting some of the theoretically needed assumptions. Respectively,
Fig. 5 we analyze the pres- ence of reinitialization of subsequent layers, and in Fig, 6 we consider the presence of shared batches across layers. In both cases, we do not observe stark difference be- tween the two settings. Finally, while the proof scheme is limited targets with of = 1 (see eq. (1), consider in the numerical simulations a' drawn from a Rademacher distribution rather than being constant.
0.7
||Mw|l-
0.5
0.5
0.4
||MI]FF
0.2
We plot the training and validation loss curves that guided our analysis Fig. g
F.3
Visualizing Feature Learning
We now show that this enhanced generalization perfor- mance is due to feature learning. Indeed, the key result in Thm I refers to the ability of three-layer networks to perform hierarchically dimensionality reduction through feature learning. To probe the quality of the learned rep- resentations, we shall introduce the "overlaps" (or order parameters).
K= login) / logld)
Figure 7: Visualizing Feature Learn- ing: The Frobenius norm of the over- laps Ma. Mw (Def. @. respectively on the top and bottom panel, as a function of the sample complexity x log for log
three-layer networks trained with the protocol described in Theorem (blue circles) and standard backpropagation (red squares). Following Theorem 1 the behavior sharply changes around & 1.5 (vertical dashed line) where fea- ture learning in both layers arises (same setting in Fig. 2
Definition 6. The order parameters for 3- 3-ryer networks are the matrices Mw E R xrd and M, x2x (with 2 N(O, Ta))
W.W W [Wlll
M₁ E[h(z)h((z))
Mw
(238)
/E[h(2)
The behavior of these quantities as a function the sam- ple complexity x is portrayed in Fig. 7 Since we do not follow the strong prescription of Thm. 1 and are working with a low dimensional example, we do not expect sharp 0/1 transition in the idealized scenario, but instead, the components along
58

---

335
0.
125
225
0.7
0.7
0.4
0.2
115
29 30" 0:2
10
33 10" 31 30'
1.2
(b)
Figure 9: Visualizing Feature Learning: The plot shows the evolution of the Frobenius norm of the overlaps (Definition as a function the training time t for two different values of к = log respectively = 1.2 on the left and A = on the right. Different training methods are logd
illustrated with different colors: in blue the layerwise training (Alg. in red standard joint training using backpropagation. The target is f*(x) = tanh aa* Pa (W and the hyperparameters listed in Sec. F.4
W' to occupy (1)) fraction (but not full) of the norm of W,. This is well obeyed (Fig. 7 and the clearly observed both layerwise and joint training.
predicted crossover at x
We exemplify in Fig. the "dual" plot of Fig. 7 by showing the evolution in time of the sufficient statistics Mw, M, for two different values of log d' The plot shows that when K < 1.5 (the critical threshold) feature learning is impossible, as it is reflected by the overlaps attaining the random guess value. On the other hand for 1.5 the overlaps grow far from the random initialization performance.
logn
Additionally, we illustrate the evolution in time of the overlaps under the learning of MIGHT functions (eq. (4) in Fig. 10 The figure exemplifies the necessity of Assumption [ that refers to the generalization of the information exponents of the multi-index target literature to the present hierarchical setting.
F.4 Hyperparameters
every figure showing sufficient statistics or generalization errors, we average over 20 different seeds and plot the median. The regularization strengths for the different layers optimized with standard hyperparameter sweeping for every value of x plotted, while the other hyperparameters considered fixed. More precisely, we fix:
(i) First hidden layer size: P1 (ntá)))))) with Pynax the maximal n probed the respective plot and = 0.1
(ii) Second hidden layer size: P2 600.
(iii) Hidden layer size for two-layer network: p = int (p1
(iv) Learning rates: while the orders of magnitude for the different learning rates as a function of are provided in Alg. for layerwise training use fixed prefactor Ir, 1, 1r Concerning joint training we use instead for all the three layers all the prefactors equal to 0.2.
(v) Minibatch size: n, = int( Tm with n = d
(vi) Iteration time: we follow the prescriptions of Theorem ] itterating for Ti O(polylog(d) steps and T, Odd--5) steps. In the numerical implementation we consider for layerwise training T; int(15 logd), T2 = i5t On the other hand, for standard training using backpropagation, we iterate jointly all the layers for T2 steps.
59

---

Jon 101
And bor
132
133
330
(a) 9" (hi, hg, (g) = (ign(h))gn))
(b) 9 (hj, kg)
h4 + hih5
Figure 10: Easy and Hard Features:
The plot shows the evolution the Frobenius norm of the overlaps (Definition 6) function of the training time / for two different values MIGHT
functions f (x) = ((hr)=)) (See eq. (.. with the non-linear features built as in Fig. ie..
hx(x) a* Pa(W*x) x) and P3 He Heg. The hyperparameters are listed in Sec. F.4 Different
training methods are illustrated with different colors: in blue the layerwise training (Alg. in red
standard backpropagation. The overlap component along different directions (h signaled with different markers.
r)
60


Reviews:
[{"review_id": "puSr3L0yZP", "reviewer": "Reviewer_G7h1", "summary": "This manuscript studies the problem of learning deep teacher networks in which each layer reduces the effective dimensionality through localized polynomial projections. Building on prior work on learning three-layer neural networks \\[36, 65, 82], the authors extend the setting to incorporate low-dimensional structure in the input layer and to learn the first-layer weights, in contrast to \\[36, 65, 82], which keep the input weights fixed.\n\nBy employing layer-wise training, the paper demonstrates that the network can successfully recover the low-dimensional representations at each layer and learn the full teacher model. The analysis relies on a universality argument for each layer, making the learning process analogous to multi-index learning with a two-stage procedure (feature learning combined with random feature approximation), a topic extensively studied in recent literature. Specifically, the results show a clear separation between shallow two-layer networks and deeper architectures when the teacher network admits a hierarchical representation. The authors also present simulations that support the theoretical insights developed in the paper.", "questions": "**Questions for Additional Discussion:**\n\n* The results extend prior work on learning compositional functions [36,65,82] to deeper models and incorporate lower-dimensionality in the input layer. Although the argument for universality is explained in Section 2, the theoretical challenges involved in establishing these results are not detailed in the text. Discussing the main ideas and difficulties that led to this extension would help readers better follow the contributions.\n\n* As far as I can tell, the paper assumes that the depth of the teacher and student networks is the same. What happens if there is a mismatch? In particular, is there any benefit to using a three-layer network to learn a two-layer teacher model, similar to what has been suggested in [65]?\n\n* There is one part I could not follow regarding $a_i^\\*$. It is first introduced as being sampled from a distribution but later fixed to a vector of all ones. I don’t think it is possible to rotate $a^\\*$, given that you assume the nonlinearity in the second layer is the same polynomial $P_k$ applied elementwise—a rotation would seem to break this assumption. Is there a mistake here, or am I misunderstanding something?\n\n**Typos:**\n\n* In line 291, $\\mathbb{E}[P_k(z) \\, H_{e_2(z)}]$ appears redundant.\n* In Theorem 1, the dimensions $p_2$ and $p_3$ should be equal, so the notation should be unified.\n* In lines 150–153, references \\[82] and \\[65] should be reversed.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\nThe paper successfully combines existing two-stage algorithms for multi-index learning with results on learning compositional functions using consecutive random feature approximations. Overall, the results demonstrate that deep teacher networks can be learned under assumptions that are reasonable within the theoretical community. The paper is well written, the arguments are clearly illustrated with figures, and the results are discussed in relation to supporting simulations.\n\n**Weaknesses:**\nI do not think the work has any major weaknesses. However, the presentation could be improved in certain parts, and additional discussion of the theoretical challenges involved in applying the universality argument to gradient-based learning would help readers better understand the technical aspects of the work. I have outlined my suggestions as questions in the following section.", "was_revised": true, "final_justification": "Good paper, see the *Strengths* part for the justification.", "rebuttal": "We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.\n\n>The theoretical challenges involved in establishing these results are not detailed in the text. Discussing the main ideas and difficulties that led to this extension would help readers better follow the contributions.\n\nWe will expand upon the challenges in our analysis under the proof sketch in Section 3. The revised paragraphs will provide additional details along the lines of point (ii) in the proof sketch. More precisely, the analysis of the dynamics of the first-layer weights $W_1$ in our setting requires incorporating the diverging dimensionality of the subspace $d_{\\epsilon_1}$, while for updates to the second layer $W_2$, the central novelty is combining the adaptivity of $W_1$ with the random features scaling polynomially in the dimension.\n\n> What happens if there is a mismatch between teacher and student depth? Is there any benefit to using a three‑layer network to learn a two‑layer teacher model?\n\nThe benefit in [65] towards using a three-layer network to learn a two-layer target arises primarily from the ability of the second layer to learn non-linear features, a capacity which the first layer explicitly lacks. For general depth, however, all intermediate layers can learn non-linear features. We conjecture that for our class of targets, an $L$-layer model suffices to reach the optimal sample-complexity for an $L$-layer deep MIGHT.\n\n> I could not follow the part regarding $a^\\star_i$. It is introduced as sampled from a distribution but later fixed to all ones. Is there a mistake here?\n\n\nOur class of targets is defined with a general distribution over $a^\\star$. However, for technical reasons, such as the requirement for spherical symmetry, our proofs are limited to the case $a^\\star_i = 1$. In the revised version, we will clarify this point along with reporting that the simulations have been carried out for $a^\\star_i \\neq 1$, but rather drawn i.i.d. from a Rademacher distribution.\n\nThank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification."}, {"review_id": "iSn0CbklGV", "reviewer": "Reviewer_x83L", "summary": "The paper introduces two classes of hierarchical single-index and multi-index targets (called “SIGHT” and “MIGHT”) and employs them to establish separations between the capabilities of random feature models, shallow neural nets, and deep neural nets. They show that training deep models layer-by-layer enables progressive dimensionality reduction and better sample complexity rates than training on the same task with a shallower model. They prove sample complexity bounds on the ability of 3-layer neural networks to learn SIGHT instances. They empirically demonstrate these separations for deeper models and more complex tasks.", "questions": "Is there any overlap between these results and those of [1]? This also involved layer-wise training of hierarchical tasks.\n\nCould the authors offer more intuition about why pre-conditioning is useful for training the second layers, and whether they suspect it to be necessary?\n\n[1] https://arxiv.org/abs/2108.10573", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\nAs far as I am aware, the results are novel and mathematically sound. \n\nWhile the work is primarily theoretical, the ability of deep networks to iteratively reduce the intrinsic dimensionality of a task is practically relevant and believable. The involved mathematical assumptions are common amongst peer papers, and the decision to focus empirical study beyond those assumptions (e.g. for simultaneous, rather than layer-wise training) is commendable.\n\nThe paper is well-written, and Figure 1 is particularly helpful for visualizing the results of the paper.\n\n# Weakenesses\nWhen introducing assumptions in Section 3, it would be helpful to highlight examples that satisfy those assumptions (e.g. targets satisfying Assumption 3.)\n\nMinor points:\n- L277: I would recommend introducing the information exponent rather than referring readers to other papers, especially given its relevance to Assumption 3.\n- L314: Instead of “exists a sequence of random matrices,” should this refer to a distribution of random matrices? \n- L319: “preacitvation\"", "was_revised": true, "final_justification": "My score remains as is after discussion.", "rebuttal": "We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.\n\n> Is there any overlap between these results and those of [1]? This also involved layer-wise training of hierarchical tasks.\n\n There has been an extensive line of research in the theoretical machine learning community focusing on the learnability of multi-index models by shallow two-layer networks with layer-wise gradient descent (see L27 of the submitted version). The reference [1] that the reviewer points out defines rigorously the concept of “staircase”, or sequential learning of relevant directions (in our notation, rows of $W^\\star_1$). While staircase functions exhibit sequential learning, they do not require adaptation across depth. In this manuscript, we offer perspectives on the learnability of deep hierarchical targets (as opposed to multi-index models) with deeper networks (in contrast with two-layer ones).\n\n\n> Could the authors offer more intuition about why pre-conditioning is useful for training the second layers, and whether they suspect it to be necessary?\n\nThe choice of pre-conditioning is needed for the rigorous scheme due to the ill-conditioning of the landscape and to the polynomial decay in the Random Feature kernel’s spectrum. Without such pre-conditioning, Gradient Descent will require polynomial in $d$ steps on the same batch of data to learn our class of target functions, which remains outside the scope of present proof techniques in the literature. However, our numerical experiments support that the theoretical claims hold for non-conditioned Gradient Descent with multiple iterations on the same batch (see L269–270). Therefore, we do not believe this element to be necessary and we will state it more clearly in the revised version.\n\n> The role of the assumptions: a) I would recommend introducing the information exponent rather than referring readers to other papers, especially given its relevance to Assumption 3. b) When introducing assumptions in Section 3, it would be helpful to highlight examples that satisfy those assumptions (e.g. targets satisfying Assumption 3).\n\nWe thank the referee for the pertinent suggestions regarding Assumption 3. The existence of an activation satisfying the assumptions is present in Appendix C.7 but is not referenced correctly in the main text. We will introduce the information exponent explicitly and highlight concrete examples that satisfy each assumption.\n\n> L314: Instead of ‘exists a sequence of random matrices,’ should this refer to a distribution of random matrices?\n\n The exact distribution of the random matrices is specified under the formal statement of the theorem in Appendix C.1.\n\nThank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification."}, {"review_id": "qOriCQw5iC", "reviewer": "Reviewer_xWdV", "summary": "The study introduces single and multi-index Gaussian hierarchical targets as learning models designed to illustrate the benefits of deep versus shallow architectures. These models are based on the assumption that features higher in the hierarchy have lower dimensionality than features at lower levels. The authors provide a theoretical analysis of the performance of different architectures on these tasks. Focusing on the three-layer case and under a specific training regime, they derive the sample complexity thresholds that separate the performance of three-layer neural networks from two-layer networks and kernel methods.", "questions": "### Questions:\n- Can the authors comment on the technical benefits of using online batch learning for the first layer and a giant step for the second? I would have expected online batch learning in both layers to perform better, but I assume it would also be significantly harder to analyze?\n- Why do the networks in Figure 2 perform worse than random chance during the initial stages of learning?\n- As a curiosity: I would expect that once the condition $1 > \\epsilon_1 > \\dots > \\epsilon_L$ is violated, depth would no longer be beneficial. Can the authors comment on this scenario?\n\n### Minor Remarks:\n- Line 217: One word seems to be missing, likely \"additional\" after \"to fit an\".\n- Line 219: \"completely\" is spelled incorrectly.\n- Lines 260–261 seem contradictory: a problem is stated to be open, yet the next line references [7] as providing a solution. Does [7] consider a different setting than the open problem just mentioned?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- The role of depth in learning with neural networks is considered a crucial open question in the theory of machine learning. Hence, it is significant to provide a theoretical model that showcases aspects of learning for which depth is beneficial.\n- The hierarchical structure of the data model is principled, based on reasonable assumptions about real-world distributions. The narrowing of the dimensions $1 > \\epsilon_1 > \\dots > \\epsilon_L$, a key assumption of the work, appears justified from my point of view.\n- The intuitive illustration provided with example (11) simplifies and highlights the core dynamics, avoiding the heavy notation present in other sections.\n- The sketch of the proof is very informative and emphasizes the key points of the analysis. In particular, point (ii) seems highly non-trivial.\n\n### Weaknesses:\n- All the analysis relies on the assumption of Gaussian inputs. While this is a clear gap with respect to real-world applications, I believe it should not carry much weight as a weakness, since most works in the field share this limitation.\n- The theoretical analysis assumes a simplified layer-wise training protocol which, as the authors themselves state, could be suboptimal. However, simulations support that for this class of targets, standard SGD also achieves the same thresholds.\n- The simulation section is not entirely satisfactory. Figure 2 shows very limited separation between two- and three-layer neural networks. I suggest extending the plot to larger values of $\\kappa$, to verify whether the predicted plateaus are attained. It would also be advisable to run simulations for different values of $d$, to check whether the expected scalings hold. Additionally, the descent phase for both two- and three-layer networks seems to require many samples to approach their plateaus — why is that? Could this be due to suboptimal learning rates during the descent phase?", "was_revised": true, "final_justification": "The rebuttal addressed all my question satisfactorily, I confirm my rating on the motivations of the initial review.", "rebuttal": "We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.\n\n> Can the authors comment on the technical benefits of using online batch learning for the first layer and a giant step for the second?\n\n We will expand the paragraph dealing with the use of online batch learning for the first layer and a giant step for the second (L266–270) in the revised version. The use of online learning for the second layer is both harder to analyze as well as suboptimal in terms of sample complexity due to the ill-conditioning of the landscape. Due to the polynomial decay in spectrum of the conjugate Kernel, without pre-conditioning, both online or batch gradient descent would require polynomial in $d$ steps, which would in turn need a “drift plus martingale” type of analysis for the second layer features, leading to various technical challenges. However, our experiments support that our theoretical results hold for non-conditioned Gradient Descent with multiple iterations on the same batch (see L269–270 and L418–419); we will comment on this further in the revised version.\n\n> Why do the networks in Figure 2 perform worse than random chance during the initial stages of learning?\n\n In the regimes of low sample-complexity, the gradient steps effectively add noise to the parameters. Since our simulations do not involve projections, this noise results in a scaling of the norms of the parameters. We believe this initial worsening of performance to simply be an artifact of this scaling.\n\n\n> As a curiosity: I would expect that once the condition $1 > \\epsilon_1 > \\dots > \\epsilon_L$ is violated, depth would no longer be beneficial. Can the authors comment on this scenario?\n\nWe thank the reviewer for this insightful question. We believe that an advantage of depth would persist even in the absence of a strict decrease in the chain of dimension exponents, since a high-degree polynomial expressible as a composition of lower-degree polynomials can be learned with fewer samples upon the recovery of the intermediate low-degree polynomials. For instance, consider the following heuristic example: a degree-4 target would require $O(d^4)$ samples to be directly learned in the original input-space. However, if the degree-$4$ target is expressible as a degree-2 function of $O(d)$ quadratic features, then  upon learning these $O(d)$ hidden quadratic features, the sample complexity of the target would be reduced to $O(d^2)$. Thus, the \"dimension-reduction\" can proceed at the level of the space of high-degree polynomial features even without an explicit reduction in the dimension of the features. Turning this heuristic into a rigorous analysis would, however, require a control over the \"approximate independence\" of such non-linear features, which we believe to be technically challenging. The strict decrease in dimensionality and the \"tree-like\" construction of targets in our setup avoids such issues by ensuring the exact independence of non-linear features. We will include the above clarifications in the revised version.\n \n> Lines 260–261 seem contradictory: a problem is stated to be open, yet the next line references [7] as providing a solution. Does [7] consider a different setting than the open problem just mentioned?\n\nThe reviewer is correct and the present phrasing is confusing; it will be corrected in the revised version. What we meant is that [7] considers the problem of joint training and introduces the concept of backward feature correction, i.e., how errors in lower-level features can be corrected through training of higher-level features. Although [7] is an inspiring reference, the key element in our analysis is to rigorously control the overlap between the target and network preactivations and to precisely describe the separation of deep networks versus shallow ones thanks to non-linear feature learning and progressive dimensionality reduction. This task is currently hard to tackle in a joint training setting and it constitutes an interesting direction of research.\n\n\n> [Idealized setting] a) All the analysis relies on the assumption of Gaussian inputs. While this is a clear gap with respect to real-world applications, I believe it should not carry much weight as a weakness ... b) The theoretical analysis assumes a simplified layer-wise training protocol which ... could be suboptimal. However, simulations support that for this class of targets, standard SGD also achieves the same thresholds.\n\n\n We strongly appreciate the constructive comments on the Gaussian-input assumption and the simplified training protocol. We agree there is a gap between theory and real-world applications, and our work provides initial steps towards understanding the mechanisms that one could expect to hold in other realistic settings.\n\n\n> The simulation section is not entirely satisfactory. Figure 2 shows very limited separation between two- and three-layer neural networks. I suggest extending the plot to larger values of $\\kappa$, to verify whether the predicted plateaus are attained. It would also be advisable to run simulations for different values of $d$, to check whether the expected scalings hold. Additionally, the descent phase for both two- and three-layer networks seems to require many samples to approach their plateaus—could this be due to suboptimal learning rates during the descent phase?\n\n To enhance the presentation of the numerical illustrations, we will include in the main text references to Appendix F.3, where we consider the evolution of the order parameters appearing in the main theorems (Definition 236)—i.e., the overlap between target and network preactivations—that exemplify a sharper transition around the predicted threshold. Moreover, we will include additional input dimensions and values of $\\kappa$ as suggested. Details on learning-rate scaling and hyperparameter sweeps will be added to the numerical appendix.\n\nThank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification."}, {"review_id": "WfrQsAEbD3", "reviewer": "Reviewer_r5Rj", "summary": "This work studies the problem of learning hierarchical Gaussian single/multi-index models with 3-layer neural networks. Specifically, for a 3-layer single-index model, the authors prove that a layerwise variation of gradient descent can achieve dimension reduction and obtain a smaller sample complexity compared to fixed kernel regression. The authors also provide intuitions on how 3-layer networks would achieve a separation with 2-layer ones through feature learning in the middle layer which enables additional dimension reduction.", "questions": "1. To my understanding, Theorem 2 is not really considering training in arbitrary middle layers. It only studies what happens when training the $L-1$ layer where $L$ is the network depth. Would it be possible that under a specific initialization of later layers, the same result can hold for middle layers without much additional effort?\n\n2. A missing related work is [1] where the authors study learning multi-index models with neural nets under structured input. Specifically, a direction for future work can be to extend the definition of effective dimension in [1] to hierarchical models to capture the effect of anisotropy on sample complexity.\n\n3. Some typos:\n    * Figure 5 caption: $d^{\\varepsilon_2 - \\varepsilon_1}$ -> $d^{\\varepsilon_1 - \\varepsilon_2}$ and $d^{\\varepsilon_3 - \\varepsilon_2}$ -> $d^{\\varepsilon_2 - \\varepsilon_3}$.\n\n    * The notation sometimes uses $\\varepsilon_1$ and sometimes uses $\\epsilon_1$.\n\n    * The statement starting from point (ii) of Theorem 3 has missing words.\n\n    * Theorem 3 uses both $w_3$ and $W_3$.\n\nReferences:\n\n[1] A. Mousavi-Hosseini, D. Wu, M. A. Erdogdu. \"Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics\" ICLR 2025.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I think the results are interesting as they provide examples of analyzing hierarchical models when the size of the middle layers diverge with dimension, which to my understanding is the key technical contribution of this work compared to prior works on learning features with 3-layer networks. The authors also provide some nice intuition on how to generalize their results to deeper networks and characterize what type of hierarchical models with depth larger than 3 can eventually be covered using these techniques, which can be interesting for future work.\n\nMy main concern is the lack of a concrete negative result for 2-layer networks. The authors provide a heuristic argument in the main text for why they would achieve a higher sample complexity for learning higher degree components in the target, but given the importance of such a negative result to theoretically capture the computational limitations of 2-layer nets, I think it deserves a theorem of its own. Specifically, I think the argument presented in Appendix B.1 is nice, I'm not sure why it isn't highlighted as a formal theorem in the main text.\n\nI think the numerical simulations, in their current presentation, may not be entirely conclusive about the separation between 2-layer and 3-layer nets. The range of $\\kappa$ in Figure 2 mostly includes the [0,1.5] interval where no algorithm achieves small test loss. It would be nice if the figure focused on larger $\\kappa$ where a more clear separation should be observed between all algorithms, at least up to $\\kappa=3$ similar to Figure 1. However, I agree that performing experiments for larger $\\kappa$ can be challenging due to the amount of needed compute.", "was_revised": true, "final_justification": "I didn't have any major concerns, and my minor comments were addressed by the authors. Other reviews are positive as well, so I'm happy to recommend acceptance.", "rebuttal": "We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.\n\n> To my understanding, Theorem 2 is not really considering training in arbitrary middle layers. It only studies what happens when training the $L-1$ layer where $L$ is the network depth. Would it be possible that under a specific initialization of later layers, the same result can hold for middle layers without much additional effort?\n\n\n Theorem 2 applies to a simplified setting where the $(L-2)$th layer has already perfectly recovered the corresponding features. Hence, only the $L-1$ layer is required to additionally learn the last level of hidden features. Ideally, we hope to apply the argument inductively to prove feature learning for all layers. The primary bottleneck toward such a generalization is that our analysis does not apply to the recovery of a diverging number of non-linear features.\n\n\n> A missing related work is [1] where the authors study learning multi-index models with neural nets under structured input. Specifically, a direction for future work can be to extend the definition of effective dimension in [1] to hierarchical models to capture the effect of anisotropy on sample complexity.\n\n\nWe thank the reviewer for the suggestion regarding [1]; extending the definition of effective dimension in [1] to hierarchical models is an exciting direction for future research and will be discussed in the revised version.\n\n\n> My main concern is the lack of a concrete negative result for 2-layer networks. The authors provide a heuristic argument in the main text for why they would achieve a higher sample complexity for learning higher degree components in the target, but given the importance of such a negative result to theoretically capture the computational limitations of 2-layer nets, I think it deserves a theorem of its own. Specifically, I think the argument presented in Appendix B.1 is nice, I’m not sure why it isn’t highlighted as a formal theorem in the main text.\n\n We agree on the importance of obtaining and stating precise negative results. The discussion in Appendix B.1 is limited to a particular choice of the MIGHT target, different from the SIGHT targets considered in Theorem 1. In the revised version, we will integrate this discussion into the main text as a formal corollary of existing results. Obtaining such negative results for the general choices of SIGHT and MIGHT targets is however, beyond the scope of our work.\n\n\n> I think the numerical simulations, in their current presentation, may not be entirely conclusive about the separation between 2-layer and 3-layer nets. The range of $\\kappa$ in Figure 2 mostly includes the [0,1.5] interval where no algorithm achieves small test loss. It would be nice if the figure focused on larger $\\kappa$ where a more clear separation should be observed between all algorithms, at least up to $\\kappa=3$ similar to Figure 1. However, I agree that performing experiments for larger $\\kappa$ can be challenging due to the amount of needed compute.\n\nTo address concerns about the simulation section, we will include references to Appendix F.3, where the evolution of the order parameters (Definition 236) exemplifies sharper transitions, and add experiments for additional input dimensions and values of $\\kappa$. We appreciate the reviewer’s understanding regarding computational constraints and will clarify learning-rate choices in the numerical appendix.\n\n\nThank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification."}, {"review_id": "b0ZScz4PVW", "reviewer": "Reviewer_mnX3", "summary": "This paper quantifies the advantage of depth in models learned with gradient descent by demonstrating that deeper models learn hierarchical data models with better sample complexity compared to shallow ones. The authors propose a class of deep multi-index targets (SIGHT/MIGHT) that mimic the hierarchical structure of real data. Based on this, the authors prove (for the shallow single-index model) that three-layer networks can learn (via layerwise training) such targets with lower sample complexity compared to two-layer networks or kernel methods. Numerical simulations validate findings beyond the setting of the theory.", "questions": "+ My understanding is that three layers aligns closely with the target model (where the middle layer matches up with the polynomial features h). As such, is there any benefit to introducing additional layers?\n+ For simple real datasets, can we observe a separation in sample complexity between two- and three-layer networks?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is technically sound and rigorous, providing theoretical results to back their claims. Assumptions are clear, although somewhat overly specific at times. However, numerical simulations are quite limited, and although they explore relaxing certain assumptions, are still largely rooted in the synthetic setting. The paper is mostly well written - in particular, the sketch of analysis with exploration in a simplified setting is very effective for elucidating the claims. Figure 1 is very helpful for visualizing the phase transitions. Some additional formatting could be beneficial for ease of reading. The problem studied is challenging and an active area of research, and this paper yields new developments, particularly in relaxing the assumption of fixed first layer. However, the target introduced for imposing hierarchical structure does not appear to be significantly novel, weakening this aspect of the paper.", "was_revised": true, "final_justification": "I believe this paper is a good contribution to tackling the feature learning problem in the multi-layer setting, and the authors have somewhat addressed my concern regarding novelty of the problem setup. I still feel that the experiments are a weak point, particularly for validating findings beyond the synthetic setting - nonetheless, I lean towards acceptance.", "rebuttal": "We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.\n\n> My understanding is that three layers aligns closely with the target model (where the middle layer matches up with the polynomial features h). As such, is there any benefit to introducing additional layers?\n\n The reviewer is correct in their interpretation. For our class of targets, there is no benefit, as far as feature learning and the scaling of sample complexity is concerned, in introducing an additional layer in the scenario described where the target model is also three-layer like.\n\n\n\n> For simple real datasets, can we observe a separation in sample complexity between two- and three-layer networks?\n\n\nWe did not explore sample-complexity separation on real datasets in the present manuscript. Although the focus here is theoretical, exploring the consequences of our results on real data, via identification of effective dimension and intermediate hidden representations, is a promising avenue for future work, and we will mention this in L73–74.\n\n\n> Assumptions are clear, although somewhat overly specific at times.\n\n\nWe acknowledge concerns about the specificity of our assumptions. In the revised version, we will integrate Appendix C.7 into the main text, where we will explicitly construct an activation that satisfies all assumptions to provide clarity.\n\n> However, numerical simulations are quite limited, and although they explore relaxing certain assumptions, are still largely rooted in the synthetic setting.\n\n Extending the verification of our theory to realistic data distributions is challenging, as we currently lack methods to identify the \"effective dimensions\" of hidden representations in such settings. Nevertheless, our analysis provides concrete directions for such explorations, for example, by interpreting the eigenfunctions of the conjugate kernel across depth and considering appropriate notions of \"effective rank\" for the same. We will highlight these experiments as future work in the revised version.\n\n\n> The target introduced for imposing hierarchical structure does not appear to be significantly novel, weakening this aspect of the paper.\n\nWhile several hierarchical data models have inspired our targets (see L163–172), we respectfully disagree that our MIGHT targets lack novelty. They offer an exactly solvable playground enabling rigorous description of feature learning capabilities in deep networks trained with Gradient Descent through progressive dimensional reduction.\n\nThank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification."}]

Author rebuttal:

Meta-review: This submission studies gradient-based learning of a hierarchical target function class motivated by deep neural networks. The main contribution lies in providing optimization and statistical guarantees demonstrating that a deep network can progressively reduce dimensionality through layer-wise training, thereby achieving a sample complexity advantage over shallow models. The reviewers found the results nontrivial and of clear interest to the community. The meta-reviewer therefore recommends acceptance.
Decision: Accept (spotlight)