Emergence and scaling laws in SGD learning of shallow neural networks
Authors: Yunwei Ren
Eshaan Nichani
Denny Wu
Jason D. Lee
Venue: NeurIPS 2025 poster ()
Keywords: scaling laws
stochastic gradient descent
shallow neural network
multi-index model
Primary area: theory

Abstract: We study the complexity of online stochastic gradient descent (SGD) for learning a two-layer neural network with $P$ neurons on isotropic Gaussian data: $f_*(\boldsymbol{x}) = \sum_{p=1}^P a_p\cdot \sigma(\langle\boldsymbol{x},\boldsymbol{v_p}^{\star}\rangle)$, $\boldsymbol{x} \sim \mathcal{N}(0,\boldsymbol{I_d})$, where the activation $\sigma:\mathbb{R}\to\mathbb{R}$ is an even function with information exponent $k>2$ (defined as the lowest degree in the Hermite expansion), $\lbrace\boldsymbol{v_p}^\star\rbrace_{p\in[P]}\subset \mathbb{R}^d$ are orthonormal signal directions, and the non-negative second-layer coefficients satisfy $\sum_{p} a_p^2=1$. We focus on the challenging extensive-width regime $P\gg 1$ and permit diverging condition number in the second-layer, covering as a special case the power-law scaling $a_p\asymp p^{-\beta}$ where $\beta\in\mathbb{R}_{\ge 0}$. We provide a precise analysis of SGD dynamics for the training of a student two-layer network to minimize the mean squared error (MSE) objective, and explicitly identify sharp transition times to recover each signal direction. In the power-law setting, we characterize scaling law exponents for the MSE loss with respect to the number of training samples and SGD steps, as well as the number of parameters in the student neural network. Our analysis entails that while the learning of individual teacher neurons exhibits abrupt transitions, the juxtaposition of $P\gg 1$ emergent learning curves at different timescales leads to a smooth scaling law in the cumulative objective.

Emergence and scaling laws in SGD learning of shallow neural networks
Yunwei Ren" Eshaan Nichani'.!
Denny Wu
Jason D. Lee'
Princeton University, New York University, Flatiron Institute
(yunwei. ren, eshnich, jasonlee) edu, dennywuōnyu. edu
Abstract
We study the complexity of online stochastic gradient descent (SGD) for learning two-layer neural network with P neurons isotropic Gaussian data: faxx) - 0p vt)), NO, Ia), where the activation or is even function with information exponent k. 2 (defined the lowest degree in Hermite expansion), {pp)p([P] C Rd are orthonormal signal directions, and non-negative second-layer coefficients satisfy Σp a² 1. We focus on the challenging "extensive- width" regime > and permit diverging condition number in the second-layer, covering special case the power-law scaling ap p- where E R20- We provide a precise analysis of SGD dynamics for the training of student two-layer network to minimize the mean squared error (MSE) objective, and identify sharp transition times to recover each signal direction. scaling law exponents for the MSE loss with respect to the number of training samples and SGD steps, as well as the number of trainable parameters. Our analysis entails that while the learning of individual teacher neurons exhibits abrupt transitions, the juxtaposition of P > emergent learning curves at different timescales leads to smooth scaling law in the cumulative objective.
the power-law setting, we characterize
Introduction
Recent works have studied the gradient-based training of shallow neural networks for learning low-dimensional target functions (i.e., functions in Rd that depend on P < d directions), such as single-index models [BAGJ21, BES+ BBSS22, DNGL23,, BMZ23, DPVLBB24] and multi-index models [DLS222 AAM22, BBPV23, CWPPS23, BAGP24, TDD* 24], to illustrate the adaptivity (and hence the improved statistical efficiency) of neural networks through feature learning. For such target functions on unstructured (isotropic) input data, it is known that optimization may exhibit an emergent risk curve: learning undergoes extensive "search phase" during which the loss plateaus (the length of which depends on properties of the nonlinearity). followed by a sharp "descent phase" single-index model where strong recovery is achieved rapidly. For instance, when the target d0(k.), where k. R., fa(x) or (a: 0), A Rd d the initial search phase of online SGD scales the information exponent of the link function or (defined as the index of its first nonzero Hermite coefficient [DH18, BAGJ21]), whereas the final descent phase occurs in 1/ é(1) time.
The sharp phase transition observed in the gradient- based learning of low-dimensional target functions may seem at odds with the phenomenon of neural scaling laws [HNA* + 17, KMH* 20, HBM*22], where increasing compute and data empirically leads to predictable power-law decay in the loss. A plausible explanation lies in considering an additive model, where the objective can be decomposed into a large number of distinct "skills", each of which occupies only small fraction of the trainable parameters [DDH*21, EHO* PSZA23]. While the acquisition individual skills may exhibit abrupt transitions empirically observed in (WTB*22, GHL cH] the juxtaposition of numerous
Equual contribution.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

emergent learning curves occurring at different timescales results in a smooth power-law rate for the cumulative objective [MLGT22, NFLL24).
Motivated by the above, consider an idealized setting where each learning task is represented by Gaussian single-index model, so the additive model reduces to a two-layer neural network
f.(x) = Ep= Op (v =t),
NOO, La).
where (vp) p=1 are orthonormal index features, a1 ... 2 up 2 0 are second-layer weights ordered in descending magnitude, and o R - R is even activation function with information exponent k. 2; this implies that (online) SGD learning of each task has an emergent learning curve with poly(d) initial plateau. This target function is a subclass of multi-index models (with ridge-separable nonlinearity), for which the complexity of gradient-bart based optimization has been recently studied [OSSW24, SBH24, RL24]. We highlight the following technical challenges to be addressed.
Extensive width (P > 1). Most existing results on SGD learning have focused on the "narrow-width" regime such as P = 1 for single-index models [BAGJ21, DNGL23,, MHPG 22, D4, LOSW24] and P (1) for multi-index models [DLS22. BBPV23, DKL BAGP24, ZG24]. However, to obtain a smooth power-law scaling from sum of "discrete" learning curves, the number of tasks should be large; this motivates us to study the extensive- width regime where we allow P - as effective dynamics [BAGJ22].
d + co, which yields an fefiniteedimenssion
> 1). Existing works in the extensive-widnt regime usually assumed identical second layer (41 = =...= ap) [RL24, SBH24] or proved optimization complexity that scales exponentially with the condition number к cirin
Large condition number amss
Amus [LMZ20, OSSW24] (to our knowledge
the only exceptions are [GRW721, BAGP24) which considered unnatural algorithmic modifications such as Stiefel constraint or tensor deflation with re-initialization). Such exponential dependency implies that in the poly-time learnable regime x = Oa(1) the signal strength for individual tasks can only differ by constant, and consequently, there is insufficient timescale separation to produce a power-law risk curve. We thus focus on the challenging large condition number regime K > 1.
Single-phase training. Prior works on multi-index learning typically employed layer-wise training procedure, where correlation loss SGD is first applied to the first-layer parameters to recover the index features, followed by convex optimization to solve for the optimal second layer [DLS22, BES AAM23, OSSW24]. Such stage-wise training creates complications in the scaling law description due the changing computational procedure. Hence we aim to characterize a natural, single-phase algorithm where both layers are updated simultaneously.
1.1 Our Contributions
We study the learning of an additive model (1) with orthogonal first-layer weights and even activation with information exponent k. > 2, using student two-layer network with m neurons trained via online SGD to minimize the mean squared error (MSE) loss. We consider the extensive-widtl regime/ > 1, and allow the scale of second-layer parameters of the target (teacher model) to depend polynomially on the width P. We establish polynomial runtime and sample complexity for single-phase SGD training and provide a sharp characterization of the recovery time for each teacher neuron.
Theorem (Informall sample complexity). Assume the teacher model has P s d orthogonal neurons for some small but fixed e > O, and the activation o is an even function with information exponent k. 2. To recover the top P_ S P teacher directions, we can train a student network (2) with m = ((P.) neurons via online SGD with sample and runtime complexity n x T x up: d (P))
As a corollary, we know that a student width m = (P) and sample size n = 0(a d (oly((P) sufficient to learn all teacher neurons, where amin := minpalP| ap. Prior to our work, [OSSW24] studied the learning of the same target function class using a layer-wise training procedure that deviates from common practice. Their analysis requires m Z pa(1/amla) student neurons, which is computationally prohibitive since P. a can both scale with the dimensionality d. Interestingly, we show that this limitation can be overcome by considering an arguably more natural single- -hase training algorithm. At technical level, our analysis leverages the following key ingredients.
Single-stage training. We consider a 2-homogeneous student model and simultaneously train both layers via online SGD under the MSE loss; this differs from prior layer-wise analyses where the first-layer weights are optimized under correlation loss. In our large condition number

---

setting, the correlation loss analysis yields super-polynomial complexity to compensate for the signal discrepancy across different tasks [OSSW24]; in contrast, our single-phase MSE dynamics circumvents this issue by automatically deflating the learned tasks from the loss.
Decoupled dynamics. When P >> 1, the effective dynamics of SGD cannot be captured by finite set of summary statistics. To understand the convergence of this high-dimensional system, we show that the evolution of different signal directions can be approximately decoupled via an "automatic" deflation mechanism and carefully controlling the influence of the irrelevant coordinates.
Applying general learnability result, precisely characterize the scaling of the population loss along the online SGD trajectory in the following power-law setting.
Proposition (IInformal) scaling law). Under the same conditions and hyperparameters as the previous theorem, and assuming ap p for B > 1/2, then (ignoring logarithmic factors) have
(a) Emergence. The p-th teacher neuron (where p S m) recovered at time nt ~ p d
(b) Scaling law. The population squared error follows a power-low decay up to approximation barrier L(1) ~ (1/2
1-28
ammmm 122.
This proposition confirms the additive model intuition from [MLGT24, NFLL24] in high-dimensional feature learning setting, where the length of the "search phase" (plateau) for each feature direction d9 is modulated by the magnitude of the second-layer coefficient ap, and the simultaneous learning of all directions yields power-law decay in the cumulative loss (see Figure 1). However, unlike these prior works, our problem setting does not imply that the learning of different tasks can be decoupled a priori, as student neurons may be attracted to multiple teacher directions and also interact with each other through the squared loss.
Cumulative loss
L(r) (mnd 1-30
Loss at p-th task
(emergence at pP 12-12-1)
Optimization time
Figure 1: Power-law scaling of MSE loss as result of superposition of emergent risk curves.
2
Problem Setting and Main Results
In this section, we present our main results on SGD learning and scaling laws.
2.1 Setting and Algorithm
Architecture: two-layer neural network. Let R - R denote the nonlinear link function. We assume the target function is given by the following additive model
f((x) = ((x)=>p=)) (p) x)) Vz E Ed.
(1)
where y N (0, is the input, (w))) p C Rd are orthonormal with P > 1, o yy) satisfies Assumption 2.1, and a 2 ... 2 ap 2 0 are normalized so that Σ, a = 1. Since the input distribution and our learning algorithm are rotationally invariant, we may assume w.l.o.g. that v" = Ep, where ép E Rd the p-th standard basis vector. While our scaling results will assume ap follows power law decay, such assumptions are required for our optimization results.
Assumption 2.1 (Link function). Let (halkeNgo denote the normalized Hermite polynomials.
(a) is even and has information exponent IE(or) = 21 for I 1, that is, the Hermite expansion of or is given as o = Lie dzghz, and we require θय 2 Co: we also assume || (|Tll1 = L, and ||or (o3 "ollll 11 S Co. where constants Ca. C. > 0.
(b) or and o' have polynomial growth. That is, there exist universal constants C. > 0 such that vo(x) [x'(x) C(1 C(1+x2)011 for all x E R.
Remark. We focus on high information exponent IE(or) 2 link functions as in [OSSW24, SBH24, GWB25]. This setting entails that the learning of each single-index task is "hard" in the sense that online SGD exhibits long loss plateau, and we utilize this assumption to prove (approximate) decoupling of individual tasks. The condition on even or simplifies the analysis by removing the 1/2 probability of neurons initialized in the wrong hemisphere (see e.g., [BAGJ21]).
3

---

Our learner network (student model) is a width-m two-layer neural network:
f(x) = (x: (2x) -== |/x/ 1I ( 2),
(2)
where { C Rd are trainable parameters and öy := ux/ wx/llexl1 Note that this student network is parameterized to be 2-homogeneous in each vg. i.e., the second-layer coefficients are coupled with the norm of the first-layer weights. Such 2-homogeneous parameterization has been used in many prior works [LMZ200 WWL+200 GRWZ21J: this setting originated from the analysis of training both layers of ReLU networks under balanced initialization (see e.g., [CB20J, and allows us to couple the growth of the second layer norm || 2| with the direction convergence of öy- We believe that a similar proof strategy can be applied to simultaneous training of networks with decoupled second-layer weights.
Algorithm: online SGD. The performance of the learner is measured using the mean squared error (MSE) loss. For each æ E Rd, the per-sample MSE loss is defined as
1 - (mx
(z) (a: (mx))1)) =
Using a Hermite expansion calculation ([GLMI8)), one can show that the population MSE loss can be expressed as a tensor decomposition loss as follows:
|a122 2
P ap || (ōk. )/)²² 2: + 2 Σ ||x|| 1|711 (Øx, o1)21) (4)
L = B [())]] ((o.Ta)
Σ 2
1=1
We use online stochastic gradient descent (SGD) to train the learner model. Let f-x,, f=(2)))
be our dataset with I, iid. N (0, Ia) being the fresh sample at step f. We initialize the student neurons Uk- ~ Und (oo)), where og = 1/poly(d) is a parameter we specify in the sequel. Let 17 > 0 be the step size. At each step, we update the neurons using vanilla gradient descent: vy (I + 1) = (1) - V,, ((x), for all k E [m]. where is the per-sample loss defined in (3).
2.2
Complexity of SGD Learning
Our main theorem provides a sharp characterization of the sample complexity of online SGD and the recovery time of individual single-index tasks. To characterize the learning order of the first P. S P tasks, introduce an ordering of student neurons UI...., Um and mapping π [P.] - [P] that specifies which student neurons converge to a particular task (teacher neuron). This mapping function explicitly defined via the greedy maximum selection procedure (5) which explain in Section 3.1 intuitively speaking, after the reordering, for E [P.]. up is the neuron that eventually converges to direction 8' (pp)" and the directions are learned sequentially based on the signal strength { p=1*
Let p.g (1) (pp. vg)) denote the overlap between the p-th student neuron (ordered) and the q-th teacher neuron at time 1. The following theorem describes the convergence of student neuron up to the
corresponding teacher v xx(p) in terms of direction: 122 pp)(p)) (1) - 1, and norm: (1) ax(p).
Theorem 2.1 (Main theorem for online SGD), Let C, C' > 0 be large universal constants, depending only on I and o,, and set the initialization scale as 0% = C Let P. E [P], amin. = minpe(P.) ap. and 5% be the target failure probability. Define A mP mm.mxxmmPP = =o((). (). Assume the dimension d, width m, learning rate 17 and target accuracies ED. ER = (1(1) satisfy
d 2 ||al|; { A amin.
--aat -
m 2 Ps, 1) T amin, ||al|;2 m 1p-pp1 min(A2d- (e)))
Ad 2 ED &
||a||| a d 1+1/4 P. ED 2 ER ED.
1/2
where S.Z hide both constants and logarithmic exists an ordering of the student neurons .)...., Um and a mapping : [P.] - [P] of student neurons to teacher neurons (see Equation (5)) such that, defining
Then, with probability least 1 8p. there
Tp = (41(1
1)02 (400111)3 p.mip) (0)) Vp [P.), and Tiax == (1 + A/4) maxpe|P.1 Tp
we have:
(a) (Unused neurons). 2| s C = for all k P..

---

(b) (Convergence). vp p. (1) 1 1-ED. (1)l = = ax(p) all [P.). (HA)) S $ Tmax-
(c) (Sharp Transition). v2, p.xip) (1) S d 1/1 11) s o for all p [P.], r S (1 p)
(d) (Loss Value). At time 1, the population loss of the student network can be bounded by
1 Σ PC[P.]
2xi) 1 1f (1-A/4yT,) O(E)) - (() 1
Σ PC[P.]
a 1 frz (1+A/477,) O(E)).
We observe the following conclusions about Theorem 2.1.
Points (b) and (c) suggest sharp transition in the learning of the teacher neuron a. xx(p) around time Tp- (p) ( (0), " (x(p) )x(p)))(111) )2(1-1))-1 In particular, for time / (1 o(1))pp minimal progress is made on the learning of v. "(pp as (ūp. " "(())² /2plllll///a (()pp) < Then, at some point during the short time interval (1 o()))Tp both directional and norm convergence occur rapidly as the quantities (ūp. V (pp)) and || approach and (x(p) respectively.
The theorem implies that a student width of m 2 P. (P.) is sufficient to recover P. teacher neurons; this minimal (logarithmic) overparameterization allows us to establish near-optimal width dependence for the scaling laws in the ensuing section.
Selecting 77 ((mmindd' poly(m, (m. P)), the runtime required to recover all directions (0gkk=/P)) to to l/d error, and thus obtain an MSE loss of O is 7 = ((d poly(P)a - which is polynomial in all problem parameters - this contrasts with the exponential dependence the condition number in [LMZ200 OSSW24). Moreover, our Assumption 2.1 permits high-degree link functions; hence when deg(or) > IE(or), the sample complexity in Theorem 2.1 is far superior to the (deg(er) rate for neural networks in the kernel/lazy regime [JGHI8, COB19, GMMM21J.
2.3 Neural Scaling Laws
Now we apply Theorem 2.1 to the setting where the second-layer ap follows a power-law decay. Proposition 2.2 (Scaling laws). Consider the same setting as Theorem 2.1, and suppose ap p -B where B > 1/2 and Z = Σp= p- -28 is the normalizing constant. Then, with high probability. (a) For p s P. = @(m), the p-th teacher neuron 1r, learned at time 6(p dd d'-1nn ")>
(b) There exist constants 0 < CB < Cp and 0 < cBB < C3 that can depend only on B such that
1-28
1-2B
cB|
logm
+
Konz Jーー
O(ED) 1 L(1) s CB
Togm
Konft
+ O(E)),
Vr E [Tmins ]. where Ko log"!-2 m/ Tmin ((ad""1((Ko))) Tmax
pB d= d
Remark. We make the following remarks.
As in the literature neural scaling laws [KMH* HBM*22, PPXP24],
scaling law in
Proposition 2.2 consists of the approximation bottleneck 0mml-28 governed by the width of the student network, and the optimization bottleneck O ((()d) (1-28)1)) governed by the number of online SGD steps (or equivalently number of samples).
Note that the times the first and last directions get learned are approximately d'-1/(Kom) and pe d' dK')) Hence [Tmin. m covers the time interval where most directions are learned.
We state the risk scaling for qquare-summable second-layer coefficients B > 1/2 similar to prior theoretical works scaling laws [BAP24, LWK*24]. In the "heavy-tailed" regime (B < 1/2), we can also apply Theorem 2.1 to obtain [(r) @((1 (P/m)" 1-20), v (1 (Ind"-))(1223/1) Note that in this setting. the required student width is roughly proportional the teacher width m O P) in order to achieve small approximation error.
"Unstable" discretization. Given fixed training budget f, it can be quite pessimistic to choose the learning rate 77 amin. ap, for P. 6(m), since any < (NQx(P.) 221-2 than P. directions are learned. As such, consider pre-specifying the runtime (or equivalently the sample size n). If we only are interested in learning the top p neurons,
(0)) -! far fewer
(P.) (0))
apply Theorem 2.1
5

---

Population loss
Population
Small width
Small width
Large width
10pe 0.35
Large width
Vppa 0.35
Optimal slope
Optimal slope
10'
10
Total compute
Width steps
(a) Theoretical scaling law.
(b) Empirical scaling
Figure 2: Theoretical and empirical risk curves with 8 0.8. (a) Idealized scaling curves described in
Section 3.1. (b) Empirical scaling curve of GD training the population loss with d 2048, P 1024.
with P. p, which gives a larger learning rate of rj = @ @aip)dd
poly(P) The p-th direction is now learned
7, =6== x(p) df'-1 P)) 2 poly(P)). (P)). This leads to "unstable" scaling law.
Corollary 2.3 (Unstable scaling law). Let m be the student network width and n be the total number of training examples. Then, there exists choice of learning rate n (depending n, m) such that with high probability the population loss after i n steps of online SGD is
(1-201/22))
[(n) + m 12
n
# O(E))
d2l
poly
We remark that the above sample size scaling matches the minimax optimal rate for Gaussian sequence models (see e.g., 3.. [Joh17]), and the exponent is consistent with existing scaling law analyses of SGD on linear models [BAP24, LWK*24, 24, PPXP24]. Note that despite the matching exponents (in terms of the decay rate B), the underlying mechanism and our theoretical analysis differ from these prior results due to the presence of nonlinear feature learning, which is reflected, for example, by the learning rate selection in our unstable discretization see Section 3.3 for more discussions.
2.4 Simulations: Compute-optimal Frontier
assuming decoupled learning and exact emergence time for each task (see Section 3.1), and (b) the MSE loss curves for GD training (with fixed step size) on the population loss, where we set 2048, P 1024, o h4, and vary the student width. While the idealized scaling law does not exactly hold at finite d, the slope of MSE loss vs. compute (on logarithmic scale) is independent of the problem dimension; we therefore compare the slope of the compute-optimal frontier in (b). Omitting the dimensionality d (which does not vary across models) Proposition 2.2, we know that given fixed computational budget T mt, the compute-optimal model under constant learning rate exhibits the following scaling,
In Figure 2, plot (a) the idealized scaling
L ~ 7 (1-28)((19)) m 1/1+B))
set the power-law exponent to be B = 0.8 in Figure Observe that:
The sum staircase-like emergent learning curves yields a smooth power-law scaling in the cumulative MSE loss towards the tail, followed by plateau due to the approximation error.
The compute-optimal slope (dashed black line) is roughly consistent between the theoretical and empirical risk curves. Specifically, for B 0.8 we theoretically predict a loss scaling of f 1/3 for the compute-optimal model; note that the empirical slope is slightly steeper due the finite-width truncation error of the infinite power-law sum.
Overview of Proof Ideas
We discuss the proof ideas in this section. Section 3.1, we describe the idealized dynamics, and show that they imply loss scaling law when the signal strength {a (ap) {4 follows power law. In

---

Section 3.2 we show that gradient flow approximates this idealized dynamics, and in Section 3.3 we discretize the gradient flow with online SGD. For ease of presentation, we will assume Hermite-4 link function o = h4 in this section; the same argument follows for more general activations.
3.1 The Idealized Learning Dynamics
Learning single task. First, consider the single-index setting and suppose the target function a + aha(e1 x). Let v e Rd denote the learner neuron. It is known that, under gradient flow, the correlation of with the ground-truth direction e approximately follows the quadratic ODE: d o 8av, prior to weak recovery, i... when P = o(1) [BAGJ21]. This ODE has a closed-form
solution: v1(()) (1/8) Sar) We have two immediate observations from this formula:
(i) v = (6, e1)² will grow from @(1/d) to a nontrivial value around time (8)))(0))
iii of stays small for most of the time and then suddenly increases around time (8))
The above claims imply an emergent learning curve for the directional recovery of the single-index task. Due the 2-homogeneous parameterization, we can show that the norm of v will not grow until strong recovery is achieved, and the norm growth occurs at a much shorter timescale than the dynamics of 6. Consequently, the MSE loss remains nearly constant for extensive period of time, followed by a sharp drop by a²/ 2 at the aforementioned critical time.
Decoupled learning of multiple tasks. Next consider the multi-index setting where we have orthonormal ground-truth directions (ep)pe(P) with signal strength pe()p Assume these P single-index models are fully decoupled, i.e., for each p E [P], there is exactly one learner neuron Up associated with direction Ep. and the learning of different directions do not interfere - in other words, we are learning P single-index models independently and simultaneously. Then from our previous discussion, we know that direction Ep will be learned around time (8ap p.p (0)) and the
MSE loss will have sudden drop of size /2. Therefore, the idealized loss can expressed as the sum of loss decrements different times (we omit the constant factor 1/2 for concise presentation)
Ł(1) = Σ/- dZ {1 (8ap <( (0)=
See Figure 2(a) for illustration. Based on this heuristic, we can derive the iteration/sample scaling in Proposition 2.2. Suppose that the signal strength follows a power law ap p p- for some B 1/2, and assume identical initial overlap for all neurons 52 p.p (0) 22 for all p [P], that direction ep is learned at exactly = 2//8. Then, when P is large, we have
ipp Σq=p 9- fp s 28 ds = p' 1-2 (2, 1).
Applying the ohange-of-variables L(r) = (2B 1) -1 (2
2 p 188 we arrive at the idealized loss scaling
Width scaling. To obtain the student width dependence, we show that a width-m student network learn θ(m) directions- note that this is sharp up to logarithmic factors. Hence the approximation error can be computed truncation of the top @(m) tasks: Lyze(m)) -2 x 1(m
3.2
The Gradient Flow Dynamics
In the previous section, assumed complete decoupling of the learning of each single-index task. We now discuss how this condition holds approximately under gradient flow.
Re-indexing and greedy maximum selection. To simplify notation, we first re-index the neurons based on the initial correlation with the ground-truth directions. Let V c dd be the collection of initialized neurons. Define (x(1), v1) == argmax,e[P],ves ag v,v2 7 By our previous heuristic argument, we expect ex(1) to be the first direction recovered, and overlap (weighted by ax(1)) with (x(1) at initialization - to the student neuron that converges to this direction first. After (x(1) is fitted by vn we remove this task from the cumulative objective; assuming the remaining student neurons have not moved too much during this process, we can determine the next task to be learned and the corresponding neuron via
which achieves maximal
(T 1), Up+1) argmaX,e (PPla (pI....).
ag ag 2 Vp E [min P, m) - 1].
(5)
7

---

x()) x2)
x(P.). x(P):
The greedy maximum selection matrix. The red diagonal entries represent the relevant neurons eventually achieve overlap close to 1. The remaining irrelevant entries can be partitioned into thrce groups: the upper triangular entries V pp,z(g) with E [P.] and p q [P], the lower triangular entries, (p, with p [P.] and p k [m]] and the lower right block FR.n(() (g) with <> P..q > P... will control these blocks using the row gap (purple arrow), column gap (blue arrow), and the threshold gap (green arrows), respectively.
Figure 3:
amip 12 p.zip)
(P)) P PP.
Finally, if P < m we index the remaining unused neurons as (0p+1..... Bmh, and if < we assign { + 1)....,,((P...)).,... to the unlearned teacher neurons arbitrarily so that is a permutation of [P]. Following [BAGP24], we call (5) the greedy maximum selection scheme and the matrix {ax(p) h.x(p) (0) the greedy maximum selection matrix (ef. Figure 3). Note that by construction, (x(p) 1-21-2 is larger than all entries below it or on its right-hand side. We have the following quantitative estimates on the gaps between the on on-diagonal and remaining entries of the maximum selection matrix at initialization. See Appendix B.2 for the formal statement and proof.
h.x(p)
Lemma 3.1 (Initialization (informal)). Consider the greedy maximum selection matrix (ef. Figure 3). At initialization, with high probability, the gap between the first P. diagonal entries and all entries below them in the same column or to their right in the same row is lower bounded by 1 1/poly P (instead of 1/poly d). The same also holds for the (P.))(P.))) -th entry and all entries in the lower right block.
A Approximately decoupled dynamics. We claim that when all irrelevant coordinates are small, the learning of different teacher directions can still be approximately decoupled. By Lemma B.1. the dynamics of the overlap 52 (px((p) can be decomposed into a primary signal term and the sum of contributions from the remaining coordinates:
22 p.T(p) 8((x(p) p2 pp.at)) )52 p.r(p) Equap axig) p.atg)) p.x(p)'
When the overlap p2 (p)((p) is small, the signal term is of order ax(p) p.m(p) = Q(ax(p)/d) d). Also, if we assume all irrelevant coordinates (i.c., 52 pp,x(q) for q * p) are small, say bounded by -09 then Equepp a ax(g) p.r(g) 1.1 Egqqpp ax(q) 12-22-1.8 < ax(p)/d, as long as amin p1/2 -08. As result, when 52 p.)(p) is still small, we have
pa d d p.x(p) & (1 a 0 (ax(p) p.a(pi'
Now suppose amin > 0.3
0.3 Then, the above implies that 22 pp)(p) has a sharp transition around time (1 + o(1)) (8ax(p))² 12 p. -- ((d/a and the 0(1) error term can be made much smaller than IPpoly(P) when d is large- this will be useful in bounding the growth of irrelevant coordinates.
Similar to the analysis in [GRWZ21], we know that once üp converges to ex(p). the convergence of norm (x()) occurs within Olog d' time, and its dynamics become local in the sense that the influence of other teacher neurons becomes negligible. In addition, after ex(p) is learned, the remaining learner neurons will no longer be affected by this target direction.
Bounding the irrelevant coordinates. We show that the irrelevant coordinates, i.c.. ones that are not in (Fpxx(p) pe[r.] (cf. Figure 3), stay small throughout training using the fact that the dynamics have sharp transitions. Here, only consider the lower triangular entries of the greedy maximum selection matrix, i.e., (2,=(p) with p E [P.] and p < k E [m]. which we control using the column gap. The other entries can be controlled using similar strategies see Appendix C.2 for details. Recall
that 2 kpx(() x 8ax(p) ( ",'(())' which has a sharp transition around time (8ax(p)) k.mip) 2xxp))) (0)) From the column gap in Lemma 3.1, this implies that 82 (xx(p)) stays small before up fits (x(p))x(p)>
After that, the signal from a Cx(p) will be close to O, and consequently v2 kkx(p) will cease to grow.
3.3 Online Stochastic Gradient Descent
We next outline the proof of Theorem 2.1, which requires converting the analysis of the gradient flow dynamics to one for the online SGD trajectory. At high level, our proof relies the martingale-
8

---

plus-drift argument used in prior works [BAGJ21, AAM23, DNGL23, OSSW24, RL24]. In order to rigorously handle the interdependence of the different martingale arguments, we rely on the stochastic induction arguments of [RI.24). The complete proof of Theorem 2.1 is presented in Appendix D.
Controlling the irrelevant coordinates. First, consider a lower triangular entry (k, x(())))) (i.e q E [P-].q k). We wish to argue that i22 (xxx(q) stays small during the time it takes for F2 q.x(q)) to reach 1. By Lemma B.1 and similar argument to Section 3.2, the update on v2 (La(q)
is given by
tg (1 + 1) v xi) (1) + Sna ( kharg) (1) + Ei+1 Z,+1,
where trt1 < 1 is an error term we will ignore for case of exposition, and Z,+1 is the fluctuation
Z++1 2 (t) OL- (V (n)(())))))) VoL()) ex(())))))))))>)) [f)g())]
By Lemma 1.1, the conditional variance can be bounded as B| [r. 2,x10) (t). Hence by Doob's s inequality, the total martingale term |Σ Ze| bounded by (mn/T/d) with high probability (we use the heuristic that "k.x(1) (1) is ((d=l) on average). [BAGJ21] selects $ d=
k,)(
which bounds the martingale by ((d-1). 12 ( (1) can thus coupled to the deterministic process 8z-1 & + S with io 1.5F2 k.)(4) k.xg)) (0), which implies the time which x2, (1) ceases to stay small is within constant factor of its corresponding gradient flow escape time (8naxig) k. (0))-1 However, this is insufficient for our purposes, as the gradient flow escape time of 72 g.)(4) is (8nax(q)) than the escape time of xl.xxg))() (1). By decreasing 7 by a 1/poly(P) P) factor, the total martingale term can instead be bounded by 6(F2.x(e) (0)/poly P)), thus guaranteeing the online SGD escape times (q.(()) are within 1 + 1/poly(P) ()) factors of their gradient flow escape times, and hence that 62 (,,(()) will stays small during the time it takes for 52 q.x(q) to grow to = 1. Afterwards, the signal from Ex(g) will be close to O. The upper triangular entries (k E [P.]. k q) can be handled similarly.
22 (.xig) (0))-, which by Lemma 3.1 is only a ++1 1/polly P)) factor smaller
for vi "i,00))" v2
On the unstable discretization. Next, consider the entries v2 kkr(()) where q > P.. In the argument above, since the martingale term scales as Ody/T/dd and Ex(q) is learned at time T Ta = -ddn-lar ) we selected a learning rate of 17 x d= However, it is pessimistic to scale 17 with the signal strength of neuron which is not learned, as this can be arbitrarily small. Instead, if we are only interested in recovering the top P. directions, the martingale term only needs to be small up time Tp. = a' We can therefore scale with (P())) ax(q)- This can be interpreted as an unstable discretization: the choice of 1) is too large for any of the directions I x(q) with P. to be learned, yet nevertheless, we can still control their growth and show that they remain small until the time that (P.) is learned. Altogether, it suffices to choose n x a (x(p.) /poly(/))))))
Controlling the relevant coordinates. Finally, consider the growth of the relevant coordinates 22 (.m(p) for E [P.]. Following the argument in Section 3.2, the update on 1s
(.)(p) is approximately
2 p (1 (1+1) 1) 72 p.xip) (1) 8nax(p) (1 22 p. (O) p. (1) Z4+1.
where the Z+11 satisfies BIZ?,, | Fil 2 pppppp))()) By choosing the learning rate S d= (=2ax(p)/poly(() we can bound 82 p.Rip) (1) between two deterministic processes (x/)), (x,)), which satisfy N/= (1 I ) pix(p) (0) and follow the updates 1+1 = + 8T (x#)) This guarantees that 22 p.x(p)
D2 p.r(p) (0) Lower bounding the process 22 p.x(p) (f) is slightly more challenging, x; diverges from x, in the time interval when the sharp transition occurs. To handle this, we partition [ }1 into smaller subintervals, and rerun separate martingale-plus-driff arguments on each subinterval. We conclude by showing that once 12 p,x(p)
polycP) up to time of p--poykpp
( (8nax()) 1
crosses 1/3, it rapidly converges to 1, after which ||u rapidly converges to ax(p)- Altogether, Lemma D.2 shows that G indeed converges to (x(p) in time (1 + poly(p (8na p (0)) (0))

---

4 Conclusion
In this work, we study the (online) SGD training dynamics and sample complexity of learning two-layer neural network with orthogonal ground truth weights and signal strengths pe(] C Rgo- where the width P' and the condition number Qmax/ Umax/Amin Amin can potentially be large. We establish sample and runtime complexity that is polynomial condition number; an application of our sharp analysis, when the second-layer coefficients of the teacher model follow a power law ap x p P for B > 1/2, we derive scaling laws for the population MSE as a function of the student network width and the number of SGD steps.
the problem dimensionality, teacher width, and
Our current results assume input data with identity covariance; one interesting extension is to consider anisotropic data æ N (0, Σ) analogous to [MHWSE23, BQ125], and derive a two-parameter scaling law when the eigenvalues of Σ also follow a power law. Another future direction is to consider decaying learning rate schedule that achieves the unstable scaling law (Corollary 2.3) at any time r. Finally, our analysis relies on high information exponent link functions to decouple the learning of different directions, which does not cover the case of IE(or) 2 studied in [MBB23, RI.24] for this setting, the scaling behavior for SGD training is studied in a companion work [BAEVW25] for the special case of quadratic activation function.
Acknowledgments
The authors would like to thank Alberto Bietti, Theodor Misiakiewicz, Elliot Paquette and Nuri Mert Vural for discussion and feedback. JDL acknowledges support of the NSF CCF 2002272. NSF IIS 2 2107304, and NSF CAREER Award 2144994. This work was done in part while DW and JDL were visiting the Simons Institute for the Theory of Computing.
References
[AAM22] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged- -trged-staircase property: 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.
[AAM23] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. SGD learning on neural networks: leap complexity and Annual Conference on Learning Theory, pages 2552-2623. PMLR, 2023.
dynamics. In The Thirty Sixth
[ABRC24] Charles Arnal, Clement Berenfeld, Simon Rosenberg, and Vivien Cabannes. Scaling laws with hidden structure. arXiv preprint arX1v.2411.01375, 2024.
[AZVP24] Alexander Atanasov, Jacob A Zavatone-Veth, and Cengiz Pehlevan. Scaling and renormalization in high-dimensional regression. urXiv preprint arXiv:2405.00592, 2024.
[Bac17] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
[BAEVW25] Gérard Ben Arous, Murat A. Erdogdu, N. Mert Vural, and Denny Wu. Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws. 2025.
[BAGJ21] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high- -ineennnnnioonal inference. The Journal of Machine Learning Research, 22(1):4788 4838, 2021.
[BAGJ22] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling, Advances in Neural Information Processing Systems, 35:25349-25362, 2022.
[BAGP24] Gérard Ben Arous, Cédric Gerbelot, and Vanessa Piccolo. Stochastic gradient descent in high dimensions for multi-spiked tensor PCA, October 2024. arXiv:2410.1816.
10

---

[BAP24] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws, arXiv preprint arXiv:2402.01092, 2024.
[BBPV23] Alberto Bietti, Joan Bruna, and Loucas Pillaud-Vivien. On learning Gaussian multi- index models with gradient flow, arXiv preprint arXiv:2310. 19793, 2023.
[BBSS22] 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- 977768 2022.
[DK Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, (((17)):231188111)) 2024.
[BES Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang. Denny Wu, and Greg Yang. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932-37946, 2022.
[BMZ23] Raphaël Berthier, Andrea Montanari, and Kangjie Zhou Learning time-scales in two-layers neural networks. arXiv preprint 0tt::2303000055: 2023.
[BQ125] Guillaume Braun, Minh Ha Quang, and Masaaki Imaizumi. Learning single index model from anisotropic data with vanilla stochastic gradient descent. arXiv preprint arXiv.2503.23642, 2025.
[CB20] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on learning theory, pages 1305-1338. PMLR, 2020.
[CDB23] Vivien Cabannes, Elvis Dohmatob, and Alberto Bietti. Scaling laws for associative memories. arXiv preprint arXiv:2310.0298, 2023.
[CDV07] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
[Chi22] Lenaic Chizat. Sparse optimization on measures with over-parameterrized gradient descent. Mathematical Programming, 194(1):487-533 2022.
[CLKZ21] Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131-10143, 2021.
[COB19] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
[CPT*24] Francesco Cagnetta, Leonardo Petrini, Umberto M Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Physical Review X, 14(3):031001, 2024.
[CW24] Francesco Cagnetta and Matthieu Wyart. Towards theory of how the structure of language acquired by deep neural networks. arXiv preprint arXiv:2406.0000 2024.
[CWPPS23] Elizabeth Collins-Woodfnn Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the high-dimensional notes: An ode for sgd learning dynamics on glms and multi-index models. arXiv preprint 208.v:2308.0888 2023.
[DDH+21] Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowledge neurons in pretrained transformers. arXiv preprint arXiv:2/04.0080 /04.08666. 2021.
[DH18] Rishabh Dudeja and Daniel Hsu. Learning single-index models in gaussian space, In Conference On Learning Theory, pages 1887-1930. PMLR, 2018.

---

[DKKZ20] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis. and Nikos Zarifis. Algorithms and sq lower bounds for pac learning hidden-layer relu networks. Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
[DKL*23] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. Learning two-layer neural networks, one (giant) step at a time. arXiv preprint arXiv:2305.18270, 2023.
[DLM24] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-free de- terministic equivalents for random feature regression. arXiv preprint arXiv:2405.15699 2024.
[DLS22] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference Learning Theory, pages 5413-5452. PMLR, 2022.
[DNGL23] Alex Damian, Eshaan Nichani, Rong Ge, and Jason D. Lee. Smoothing the landscape boosts the signal for SGD: Optimal sample complexity for learning single index models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[DPVLB24] Alex Damian, Loucas Pillaud- Jason D Lee, and Joan Bruna. The computational complexity of learning gaussian single-index models. arXiv preprint arXiv:2403.05529 2024.
[DTA+24] 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.05220 2024.
[EHO*22] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac hatfeld-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposition. arXiv preprint 0rXiv:2209.10632 2022.
[GGJ+20] Surbhi Goel, Aravind Gollakota. Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference Machine Learning, pages 3587-3596. PMLR, 2020.
[2HL+22] Deep Ganguli, Danny Hernandez, Liane Lovitt, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova Dassarma, Dawn Drain, Nelson Elhage, et al. Predictability and surprise in large generative models. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1747-1764 2022.
[GLMI8] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning One-hidden-layer Neural Networks with Landscape Design. In International Conference Learning Representations, 2018.
[GMMM19] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz. and Andrea Montanari. Limita- tions of lazy training of two-layers neural network. Advances in Neural Information Processing Systems, 32, 2019.
[GMMM21] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Lin- carized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-100 2021.
[GRW721] Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou. Understanding deflation process over-parametrized tensor decomposition. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, pages 1299-1311, Red Hook, NY, USA, December 2021. Curran Associates Inc.
[GWB25) Margalit Glasgow, Denny Wu, and Joan Bruna. Propagation of chaos in one-hidden- layer neural networks beyond logarithmic time. arXiv preprint arXiv:2504. 131 10, 2025.
12

---

[2BM*22] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks. Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203 2022.
[HNA*17] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv: 2017.
[HT87] Trevor Hastie and Robert Tibshirami. Generalized additive models: applications. Journal of the American Statistical Association, 82(398) 1987.
[Hut21] Marcus Hutter. Learning curve theory. arXiv preprint arXi:: arXiv:2102.04072 2021.
[IGT+24] M Emrullah Ildiz, Halil Alperen Gozeten, Ege Onur Taga, Marco Mondelli, and Samet Oymak. High-dimensional analysis of knowledge distillation: Weak-to Neak-to-strong generalization and scaling laws. arXiv preprint arXiv:2410.1 18837, 2024.
[JGH18] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Con- vergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[JMS24] Ayush Jain, Andrea Montanari, and Eren Sasoglu. Scaling laws for learning with real and surrogate data, arXiv preprint 2402::240..44376, 2024.
[Joh17] lain M. Johnstone. Gaussian estimation: Sequence and wavelet model. 2017.
[KC22] Arun Kumar Kuchibhotla and Abhishek Chakrabortty, Moving beyond sub-Gausse Gaussianity in high-dimensional statisties: applications in covariance estimation and linear regres- sion. Information and Inference: A Journal of the IMA, 2022.
December
20] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001 200.0000000.0.61,,, 2020.
[LMZ20] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over wvrr-parametrized two-layer neural networks beyond ntk. In Conference on learning theory, pages 2613-2682. PMLR, 2020.
[LOSW24] Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoreii limit. arXiv preprint arXiv:2406.0/ 0/58/ 2024.
[LWK+24] Licong Lin, Jingfeng Wu, Sham M Kakade, Peter Bartlett, and Jason D Lee. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprint arXiv:2406.08466 2024.
[MBB23] Simon Martin, Francis Bach, and Giulio Biroli. On the impact of overparameterization on the training of shallow neural network in high dimensions. arXiv preprint arXiv:2311.03794, 2023.
[MHPG*22] Alireza Mousavi-Hosseinn Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu. Neural networks efficiently learn low-dimensional representations with sgd. The Eleventh International Conference on Learning Representations. 2022.
[MHWSE23] Alireza Mousavi-Hosseini, Denny Wu, Taiji Suzuki, and Murat A. Erdogdu. Gradient- based feature learning under structured data, In Thirty-seventh Conference on Neural Information Processing Systems (NewrIPS 2023), 2023.
[MI.T224] Eric Michaud, Ziming Liu, Uray Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, 36, 2024.
13

---

[MRS22] Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:2210.16855 2022.
[MVEZ20] Sarao Stefano Mannelli, Eric Vanden-Eijnden and Lenka Zdeborová. Optimization and generalization of shallow neural networks with quadratic activation functions. Advances in Neural Information Processing Systems, 33:13445-13455 2020.
[NFLL24] Yoonsoo Nam, Nayara Fonseca, Seok Hyeong Lee, and Ard Louis. An exactly solvable model for emergence and scaling laws. arXiv preprint arXiv:2404.1756,, 2024.
[NLB24] Eshaan Nichani, Jason D Lee, and Alberto Bietti. Understanding factual recall in transformers via associative memories. arXiv preprint arXiv:24122006538 2024.
[NS20] Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. arXiv preprint arXiv:2006. 12297, 2020.
[OSSW24] Kazusato Oko, Yujin Song, Taiji Suzuki, and Denny Wu. Learning sum of diverse features: computational hardness and efficient gradient- training for ridge combinations. In Conference on Learning Theory. PMLR, 2024.
[P*97] Allan Pinkus et al. Approximating by ridge functions. Surface fitting and multiresolutiinn methods, pages 279-292, 1997.
[PPXP24] Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+ phases of compute-optimal neural scaling laws. arXiv preprint arXiv:2405. /5744, 2024.
[PSZA23] Abhishek Panigrahi, Nikunj Saunshi, Haoyu Zhao, and Sanjeev Arora. Task-specific skill localization in fine-tuned language models. arXiv preprint arXiv:2302.06600, 2023,
[PWL25] Zhixuan Pan, Shaowen Wang, and Jian Li. Understanding I1m behaviors via com- pression: Data generation, knowledge acquisition and scaling laws. arXiv preprint arX1v:2504.09597, 2025.
[RI.24] Yunwei Ren and Jason D Lee. Learning orthogonal multi-index models: fine-grained information exponent analysis. arXiv preprint arXiv:2410.09677 2024.
[RR17] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, pages 3215-3225, 2017.
[SBH24] Berfin Simsck, Amire Bendjeddou, and Daniel Hsu. Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence. arXiv preprint arXiv:241 1.08798, 2024.
[SH20] Johannes Schmidt- Hieber. Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 1874) 2020.
[Sto85] Charles Stone. Additive regression and other nonparametric models. The annals of Statistics, 13(2):689-705. 1985.
[Suz18] Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:1810.0803: 2018.
[Tao06] Terence Tao. Nonlinear dispersive equations: local and global analysis. Number no. 106 in Conference Board of the Mathematical Sciences regional conference series in mathematics. American Mathematical Society, Providence, R.I, 2006. OCLC: ocm6516550)
[TDD*24] Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, and Florent Krzakala. Fundamental computational limits of weak learnability in high-dimensional iulti-index models. arXiv preprint 24X.v:2405.54440 2024.
14

---

[VY24] Maksim Velikanov and Dmitry Yarotsky. Tight convergence rate bounds for optimiza- tion under power law spectral conditions. Journal of Machine Learning Research, 25(81):1-78, 2024.
[WTB*22] Jason Wei, Yi Tay, Rishi Bommasani, Colin Rafell, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682. 2022.
[WWL'20] Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond Lazy Training for Over-parameterizeed Tensor Decomposition. In Advances in Neural Information Processing Systems, volume 33, pages 21934-21944, Curran Associates, Inc., 2020.
[ZG24] Mo Zhou and Rong Ge. How does gradient descent learn features-a a local analysis for regularized two-layer neural networks. arXiv preprint arXiv:2406.01766 2024.
[ZGJ21] Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over- parameterized two-layer neural network. In Conference Learning Theory, pages 4577-4632. PMLR, 2021.
15

---

Contents
1
Introduction
1.1 Our Contributions
2
Problem Setting and Main Results
2.1
Setting and Algorithm
2.2
Complexity of SGD Learning
2.3 Neural Scaling Laws
2.4
Simulations: Compute-optimal Frontier
3
Overview of Proof Ideas
3.1
The Idealized Learning Dynamics
3.2
The Gradient Flow Dynamics...
3.3
Online Stochastic Gradient Descent
Conclusion
10
Additional Related Works
17
Structure of Gradient and Initialization
17
B.1 Population and Per-sample Gradients
17
B.2 The formal version of Lemma 3.1: Initialization
19
C Gradient Flow Analysis
23
C.1 Convergence Guarantees
24
C.2 Maintaining the Induction Hypotheses
35
C,3 Deferred Proofs
43
Online SGD Dynamics
48
D.I Preliminaries
48
D.2 Convergence Guarantees
50
D.3 Maintaining the Induction Hypotheses
59
D.4 Proof of Theorem 2.1
66
Deferred Proofs
70
Scaling Law Derivations
74
16

---

Limitations
One limitation of our work is that we require the input data to be drawn from the standard Gaussian. We remark that this assumption is common in prior works on learning multi-index models [BAGJ21, DIS22, AAM23, DNGLL23, OSSW24, RI RI.24]. However, it would be interesting to understand how our results generalize to other input distributions. Another limitation is that we assume or is an even function with information exponent 2 4. One final limitation is that Corollary 2.3 requires not anytime, and requires specifying the number of SGD steps It would be interesting to consider a decaying learning rate that can achieve Corollary 2.3 at any time 1.
A Additional Related Works
Theory of scaling laws. Neural scaling laws describe how the performance of deep learning models improves predictably as a power-law function of increased computational resources, data, and model size [HNA+17. 17, KMH*20, HBM+22, BDK+ When the optimization algorithm is not taken into account, such scaling relations have been established for the approximation and estimation errors of deep neural networks [P*97, Suz18, 8, SH20J, as well as for the (precise) generalization error of simple closed-form estimators such as ridge regression [CLKZ21, MRS22, DLM24, AZVP24]. Recent works have also studied the loss scaling in distillation and synthetic data [IGT*24, JMS24], associative memory [CDB23, NLB24] and hierarchical models [CW24, CPT*24, ABRC24, PWL25], among other theoretical settings.
The scaling laws of SGD in sketched linear regression have been characterized in [BAP24, PPXP24, LWK* - this problem setting corresponds to a two-layer linear network with random, untrained first-layer weights, and is parallel to earlier works [RR17, NS20] on learning random features model under source and capacity conditions (see e.g.. [CDV07, VY24J). However, this linear setup fails to capture the feature learning efficiency of neural networks. On the other hand, existing scaling analyses for the additive setting [Hur21, MIGG22, NFLL224] explicitly decompose the loss into an independent sum, simplifying the analysis due to task decoupling. We aim to understand a more natural- - yet arguably more challenging nonlinear feature learning scenario where the individual tasks are not decoupled.
Learning shallow neural networks. The learning of two-layer neural networks with near-orthogonal neurons has been extensively studied in the deep learning theory literature. Existing works have studied the optimization dynamics for variants of ReLU [LMZ20, ZGJ21, Chi22], quadratic [GMMM19, MVEZ20, MBB23], and general Hermite activation functions [OSSW24, RL24, SBH24). In the absence of the (near-) Jorthogonality assumption, this function class can be computationally hard to learn, as suggested by statistical query lower bounds [DKKZ20, GGJ+20J. Our target function is subclass of additive models [Sto85, HT87], where the individual components take the form of single-index models- - see [Bac17, OSSW24] for further discussion.
B Structure of Gradient and Initialization
B.1 Population and Per-sample Gradients
In this subsection, we compute the population gradient and derive variance and tail bounds for the per-sample gradient. Namely, we prove the following lemma.
Lemma B.1. Consider the setting described in Section 2. Assume w.l.o.g. that or Cp for p [P]. The radial and tangent components of the population gradient are given by
- -(V L. Lx = 2 211
p 2i - 2 21/ex11
|elll (ūz, 21)
23
28
i=1
p=1
(I - 020,) Vay 24 L
P
|| 1/4
200
21
22-2
22 0g
v.g
k.q
Vk.P
1=1
80
210 21
Σ
|| (ōx. .1) 0/- 2i ((I ((I-((II)) 11-00()))
Hlak
17

---

Suppose that Z || Ollalli). Let u E s be fixed direction. Put Q = 4(1+ Q). Then, there exists universal constant such that, for any s C,
Var (Vog) u) S Cilaali.
P
p
(V (Vr
(x))
u)
Cm exp Cm
(s/laal)))))
2 s
|
Proof. The proof of the variance and tail bounds is essentially the same as the proof of Lemma A.5 of [RL24].2 Now, we compute the population gradient. First, recall from (4) that the population loss given
L
aall 2
ΣΣ
ap 1 (ōk, vi))
|x |elll (0t,
61)
Σ
Li.
2 k./=1
i=1
i=1
For its gradient, first note that for each i 2 I,
(v, (v),2)'
u)²
Vo (v. u)
(v, (w,2) V. ||
V. (lwll
(0, (0, u)) =v. ||||||=2
1|w|11-2
||lli' ||
i(v, i(v. u) u (0. u) (i - 2) [|ul|(
||a||'~2
||
||a||
= =( u) || u (i- 2) (ö, u) v.
Then, for each [m]. we compute
ve
Σ ap - p=1
20, || ex 07? ||
Σ
(Tx, 71) 5i - (i- 2) (ūx, ;i) Tx.) |1ail12
li*k
Hence, for the radial component, we have
(VogLi, = -00 ||
Σ
ap k. 20, |1xl1
Σ 1=1
| (ōx, o1)
p=1
Meanwhile, for the tangent component, have
P (I 6z- Li -0 ||xl|| Σ
a apti -I
p=1
+ o |x Σ
||,/112 ( 84) (I- o
lilk
-f ||xx|l Σ
aptii-1 k.p (ep- - Ux)
=
p=1
07- llllll
Σ
|| i (82, By) (Ø) (0x, σ1) σx)
In particular, for each p [P], we have
[(I ū Lilp
= -10?
apkk.
r--
Σ
agvyy
vx.p
||
q=1
+ 10?
Σ link
11
(Ux, ((),0))/ bi)it1 (Vi.p
(ox. 61) VR.p).
Nott that though Lemma A.3 of [RL24] is stated for i.i.d. random variables, the original theorem in [KC22] requires only independence and therefore applies to setting.
18

---

Sum over i 2 1, and we obtain
P
20
m
(V L. (.)x)) = -2 -2 11
a k,p
+2 1|0x11
_
0
1olll (Øx. B1)²
p=l
[[I - ) V v2 {
P
| ||
Σ
i0,
ap
k.P
pi-2
aq
Vg
vk.p
im1
4=1
+
i
||
(ōx, B1)²11 (Vi. (VLL (ōk, 51) Fr.P)-
liak
B.2 The formal version of Lemma 3.1: Initialization
In this subsection, we prove the following formal version of Lemma 3.1.
Lemma B.2 (Initialization). Let 85 E (e
log" d 1) be the target probability. Suppose that ö, 2x (3xz)
6ox 6, 8c 2mp2
6ex d 2
40011-11²
6" log
m 2 log( P-/ōp) 100
log' 2
m
12m p
512 log (P_/5p) Then, the following holds with probability at least - ((p))
(a) (Row gap). For any p E [P.] and p q E [P], we have ax(p) p,p(p) (1 + 6, ( 221-2
p,a(g))
(b) (Column gap). For any E [P.] and < kk E [m]. we have 521-2 2 (1 + 6c) 21-2
ppx(p))
k.n(p)'
(c) (Threshold gap). For any P. < q S P. P. kks m, we have ax(P.) v....)).... 221-
P.,x(P)) 2 (1
ó, 6))a 22122 k.zlg)'
(d) (Regularity conditions). max @ s log² d/d, pe(p) v2 p.)(p) 2 (log P.)/d and mP maxj>p. 1).4 2 1/d.
Proof of Lemma B.2 (row gap). Consider an arbitrary neuron v and let N (O, Ia). Note that e _ x/|lzz ||æ||| and therefore, for any i ///V/ & zı/zj. which follows the standard Cauchy distribution. We know that P(ze 5 2] x- arctan(2) 2) + 1/2. Fix i # j, compute
P 1j,071-2 (1 1,) 2.P (1- 8,) aj
aj
S
8,)
ai
ai
aj
aretan (1 (1 (1- 8,)
aj
arctan
(1 8,)
ai
(1+ as I=. - -(11 01)
aj
arctan
11-2
1 (1+ - 6r)
where the last line comes from arctan a arctan b arctan feab Note that for any p E (0, 1), by the concavity of z + z", we have a" - b" s pbl - b). Therefore,
aj (1+ ai - (11 8,) aj -(11-))
1
(1- 8,)
aj
aj
aj I dr-
S
8
aj
21 2
2
aj
aj
21
2
aj
Recall that arctan z S 2. Thus,
P pap 21- E (1 61)
2
aj
a1
6
6,
(a;a,) 2122
<
(1- 1)xt (a²) . + (1 82) पー (a))
1 +
(1 - 02)
19

---

a v va) -
6,
(1 1)TT
87) u (1))
8r
(1 () 63)
The last term is upper bounded by TT as long as 6, s 1/2. Apply union bound over all neurons and all p2 (-.airs, and we get
2mP2 3K E [m].i jE 21-2 (1 21-2
P
π 6,
2mp2. so that the above implies a; & (1 o,) for all k E [m] and i j [P] with probability at least 1 - Óp. To complete the proof, recall that by the definition of the greedy maximum selection process, we have ax(p) 22
Choose 6, =
6xx
p.x(p) 2 ax(q) v2 p.x(q))
Proof of Lemma B.2 (column gup). Let 2 2m be independent N (0, Ia) variables. Fix k # / [m] and [P]. Note that (FR.nip), FL.x(p)) (zR.p/1lzx|l pt.p/ =/l). Hence, we can write
21-2
|| 21-27
22-2 (((i)) E (1 6, P
=
ZR.P
E (1 8c)
1x((p)
Zk.1
||
Zk,p
21-2
||
21-2
$ P
1 + 38
+
$
8e
Zx.1
|
By our previous calculation, know the first term is bounded by 68./nt. Meanwhile, by the standard concentration results for N (0, Iz), we have
| |
P
2
s 2 exp (12 s exp (-di/4). Vr 2r20 0.
In other words, with probability least 1 4 exp (-dr2/4), we have
|z (1 (1 21-2 = 4(1 - 1)r,
|| = 4(1 1)t,
and therefore (1|=*1/ /1 21-2 10(1 1)r. Choose 6c/(10(11- 1)), and we obtain
|| |
21-2
4exp d 5²
$ 1 + 6e
100
1)2
As result, have
212 k.T(p)
E (1 + 6 (.T(p)
s
66
+ exp
d
82
π
100
1)
Take union bound over I E [m] and p E [P], and we get
P 3k # [m]. p E [P], ( (1 (
21-2
21-2
m
66.
4 exp
d
4
100
1)3
For the RHS to be bounded by 8z, it suffices to require
126
m
S 6p
=
8, 5
12m-P"
d
82
68
400(1 | 1)2
2x
exp 4 100(1 - 1)
d
log
π
6²
36
To complete the proof, recall that by the definition of the greedy maximum selection, we have 22
p.x(p) 2 v2
xxx(p) when k >
20

---

Proof of Lemma B.2 (threshold gap). Consider arbitrary k # E [m] and p # [P]. We estimate the gap between a axip) k. and ax(a) 221-2
(4x( Let 2ko zy be independent N (0. Ia) variables; we
As in the proof of column gap, have (Vk,z(p), F1,z(qi) _ (2x.p/ 2Ill 21,g/ =/))
write
P x E + (1+ ( k.t(p)
1.t(p)
2/-2
P ax(p)
ax(a)
Ik.P
Z1..1
21-2
E (1 ó,)
1|
|
2/-2)
dx(p)
ZK.P
2/-2
||
2/-2
S P
E
1 + 36,
+P
# +
8
(x(a)
Zk.
|
By the proof of the row gap and the column gap, the last two terms are bounded by
65. and
67 4 exp - 100 respectively. Note that this is the same as the bounds in the column gap proof (up to changing 6, 6τ). Thus, we have
P 3k # E [m],PE [ 2,
E (1 6,) s Op,
provided that
400(1 1)2
2x
6, s
d2
log
12m2p'
57
36,
To complete the proof, note that by the definition of the greedy maximum selection process, we have 221-2 (x(P)) (P.)((P)) ax(g) 221-2 for all P. < s m and P. < P. R,z(q)
Proof of Lemma B.2 (regularity conditions). First, we consider the upper bound. Let 21. Zm be independent N (0, Ia) random vectors. We have (ox)a (zz/ IDx=- By the stan- dard Gaussian concentration results, we have F(maxke[m) || = 2 z) 2mde 1212 and P(max*< [m] ||| /B | 11 1| 2 8) s 2me s'd/3, Therefore, we have max; || ll. s log² d/d
with probability at least - 0(p))
Now, we consider the lower bound, Let K be a parameter to be determined later. Our goal is to show that with high probability, ax(p) ppx(p) is at least the K-th largest entry of the π (p))th column of the greedy maximum selection matrix. In other words, at most the first K largest entries can be covered by the earlier neurons.
For any k # I E [m]. the events that the k-th and I-th neurons are used by some earlier are independent. In addition, by symmetry, the probability that the k-th row is used by some other neuron is at most P./(m - P.), as we always have at least m - P. neurons remained. Meanwhile, since the coordinates of üg are negatively correlated, conditioned on that v2 kp)(p) among the largest entries of that column, the probability that that row gets used is still upper bounded by P./(m - -P). Thus,
P. P.
[all first K largest entries of the x( (p)-th column are used] s
By union bound, the probability that one of (n2 p. } pE[P.] not at least the K-th largest in that column is upper bounded by P. m-P.) For this to be upper bounded by 82, it suffices to have
log (P./ōp) =
K = log (P./öp). m z 4P, log P./52).
P. P.
6p
=
K
log ((m P.)/P.)
Finally, by Lemma B.3, provided that?
m
128x (P./op) and
m
2 512 log2
log m
log m
we have with probability at least òy that
2 (p)( (0) 2 d log
m
log P. d
[P.
Log(P./óp)
3 Note that the second condition is stronger, it suffices keep the second
21

---

We conclude by establishing the last regularity condition. For fixed j.q, the PDF of Z == f..q is r( _
pz(z)
( - and therefore
2
2
vdj2
2
P(?
$ 7
0.8,
Vd
(
Vd
VI
where the first inequality upper bounds the PDF by pz( and the second is Gautschi's inequality. Therefore
P(max v) - 1/d) P( j=P.
Σ
2 1/d) P.).
jE[m]
Note that jm(( 1 2 1/d) is subGaussian with variance proxy S m. Therefore for m 2 10P.
P(
Σ 1(7) j4 2 1/d) s P.) s exp(-(P. - 0.2m)² /m) = exp(-m) 100)). [E[m]
Union bounding over all E [P]. we get
P( min max j.q s 1/d) s Pexp(-m/100) s 6p pE[P)>>P,
for m 2 1001og(P/62).
Lemma B.3. Let Zı.... Zm be independent N (0, 1) variables. Suppose that
128 log log (1/6p) and log 512m
m
log m
Then, with probability at least 8z, the K-th largest among Zı.... Zm is al least vlog(m/ K).
Proof. Let & denote the CDF of N (0, 1). Then, the CDF Fx of the K-th largest element among Zi...., Zm is
K-1
m
(x)
())) (m
k
It is well-known that the mill's ratio of N (0, 1) satisfies
z
2/22 (z))
-212 12
2
+
V2T
Mcanwhile, we have (*) S m e kk As result,
K-1
2-22 m-k
(z S
me
e
2/22
2t
V2n
x²
me
1
kz²
k
72/2
exp
exp
2x
V2n
+ z?
Choose 2 = ((1 - e)2 l02(mm/m/ K) for some e (0, 1).
Then, we have -2122
(K (K/m)) /mmmmm=- and
me 1 K 1-6 k
k
K 1-c
(2
exp
k V2T Z m
1 + 22
m
k=l
Choose & 1/2 and suppose that K s m/2. Then, we have
(2) S
K-1
Σ
m 1/2 1/2)
exp
4v2x
m
1/2
K
cxp
2
k
log(mK)
4v2xx
m 1/2
m 1/2
$ exp
2K log
4
Vlog m
22

---

To merge the first term into the second term, it suffices to require
1 m 1/2
2K log 2
m
2 512nk²
8 8 Vlogm
log m
Finally, we compute
m 1/2
exp
Öp
128x (og(((1)=))
8 8V2
vlog
logm
C Gradient Flow Analysis
In this section, we analyze the gradient flow dynamics and show that gradient flow implements the greedy maximum selection scheme. We will assume the following on the initialization.
Assumption C.1 (Initialization). Suppose P. s min m). We assume that the following hold at initialization.
(a) (Row gap) For any [Pa] and < E [P], we have ax(p) p.x(p) 2 (1 2-1-2 p.xlq)"
x(g)
(b) (Column gap) For any [P.] and k E [m], have 221-2 p.x(p) (1 (1+6 k.
k.mlp)"
221-2 (c) (Threshold gap) For any P. < k E [m] and P. < q E [P]. we have ax(P.) P (...((.) 2
(z)))))())) 221-2 (.x(g) k.z(q))
(d) (Regularity conditions) maxxe[m] || 11. log² d/d and minpe(P.) 12 p.m(p) 2 1/d.
Remark. By Lemma B.2, this assumption hold with high probability with 8e. 6r, ö, = 1/poly( P).
Now, we formally state the main theorem for gradient flow. The proof is deferred to the end of this section (cf. Section C.3). In the statement, we hide the constants that depend only on or.
Theorem C.1 (Main theorem for gradient flow). Assume Assumption C.I holds at initialization. Let ED, &R be our target accuracies and ör be the target error in time. Pul or == 8, A 6r. Suppose that
||al|
min, 8c
||l|| 1
ED Zo
d1-1/4 Sor ER Sor (log² d)
amin d1/4 So ōr So 6e 6, A 6,.
amin, d'-1/4'
( 5e
amin
(log² d'at Zo 573 V
6ryt
||ll|
|alli
Choose the initialization scale be
88((68))
amin, ST d1-1/2
amin, Sr
a
min, 5c
of zo
Amin, ED
A ER A
^
m
(log d) 21-1122 112 1/2
(log² d)--1 dl-1/2
where o o (1-1)) define
07 07.02
ER anin
2
d'log dy For each p [P.).
d(log dy
d(log dy---
(Ing' dy
Tp : 41(1 - 1)02) 221- (0)
=
an(p) 221- (0)
=
(m(p)dd-
p.xlp)
p.x(p)
Then, we have the following over time interval [0, (1 + 2067 205
Note that the lower bounds are 1/poly(d) (d). and we know from Lemma B.2 that dc δy Ey are 1/poly(P). Hence, the range from which eD. ER, 8T chosen is not restrictive.
23

---

(a) (Unused neurons) ||x||l of all k P..
(b) (Learning) For any p E [P.], 12 p.H(p) 2 ED and ||plll ax(p) + ER for all
(1+ (1+20)))Tp.
(c) (Sharp transition) For any p E [Pt], 12 p.a(p) S
4
and || s of for all H
log'd
ör
1 (1 TO
In words, for each p e [P.]. B converges to ex(p) and fit ax(p) at time (1 + o(1)) and all other neurons stay small throughout training.
Our proof will be large (continuous) induction argument. Namely, assume collection of induction hypotheses, analyze the dynamics under these conditions, derive the convergence guarantees, and show that these induction hypotheses hold throughout training. One may refer to, for example, Section A. of [GRWZ21] or Chapter 1.3 of [TTo06] for details on this method.
We will maintain the following induction hypothesis.
Induction Hypothesis C.2. Let 0n > do. z Eo. y be o(1) parameters. We say this induction hypothesis holds at time point if the following hold that time point.
(a) Define L == (k e [m] || 2 on). For any p e [m], up L implies p P. and 2 p.x(p) 2 1- E.
(b) For any (k, that is not in (p,x(p))
[P.]), we have v2 (k,(()) 80 (1-x)
(c) We have ||pl|l 2a for any p E [P A m] and 22 ppx(p) 2 1/d for any p E [P.].
Remark. Condition states that the norm neuron large (when compared to on) only if it is close to one ground-truth direction. Condition (b) means that all irrelevant coordinates stay small throughout training. Condition (c) includes some basic regularity conditions.
Before proceeding to the proofs, we state the following lemma that controls the interaction between different learner neurons. The proof is deferred Section C.3.
Lemma C.2. Suppose that Induction Hypothesis C.2 is true at time Then, at time for any [m] and q [P], we have
80
P (x(r) k.a(r))
2 k.n(q)) x()))
-22
Σ
210
221-2 (xig) (x k.Tlq))
Σ
2i
(k # q. E 2 2//1l -1-12 (2,
Σ
210 k(
i=1
* 1231+6 (x faxiaio faxioi) o0 v mo? v ||al|| s
In addition, for any larget 5 > 0, we have
(11-))(1-1),
E (x(4))
122 moo v ||a]]; of s
mo S 6,
(6)
d 2
||a||
The rest of this section is organized follows. In Section C.I. assume Induction Hypothesis C.2 and show that Up (p e [P.]) converges to ex(p) and fits ax(p) at time (1 # o(1))T, Then, in Section C.2, we verify Induction Hypothesis C.2. Finally, in Section C.3, we prove Lemma C.2 and Theorem C.I.
C.1 Convergence Guarantees
In this subsection, we show under Induction Hypothesis C.2 that Up (p E [P2] converges to (x(p) and fits (x(p) at time (1 o())),, We will first consider the dynamics of up and then ||>p|| Our main result is the following, whose proof can be found the end of this subsection.

---

Corollary C.9 (Convergence), Let ED, EN be our target accuracy in the tangent and radial directions, and ô7 the target error in time. Suppose that y 1/(21). 8, 1/3.
231+ C ||all ED
ER 2 |2||||11 | 2nd d (1-m) 81
2 C2
|all|
1
(6 amin, d(--y)
02
amin.
d2/2--1
mo? 8 min.
(6%)' 3
ER
^
231+7
d!-1/2
12"
(6,) 02 21 C3
021
8
E ()d2(1->)(11))
19
ER x2p)
231+4
d1-2y(1-1)
Then, for any p E [Pa]. we have
2 p.)(p) 2 1-11-p ED.
||pl1" =x(p)) + ER.
Vr (1+206r)],
4
log²d d
22 p.)(p) $
|,>1| oo.
Vr s (1 - 1067)
d
where
Tp = 41(1 4I(I- a 2-1 (0) p.x(p)
=
= an(p) pixip) (0)
an(p)
C.1.1 Tangent Dynamics
Here, we analyze the diagonal entries (v?
p. Let [P.] be fixed. For d E (0, 1), let p.x(p) reaches 8. We split the training process into [o. [To,.
To denote the time y2
To. and Ti-el, where 6, o(1) and 6, (()) are two parameters to be chosen later. Our goal is to show that 22 pp*(p) will converge to close to I around time (1 ((6))) where Tp is the time indicated by the idealized process and ô7 is a parameter measuring the error.
Lemma C.3 (Dynamics of the diagonal entries (Stage 1)), Suppose that at time E [6,
Induction Hypothesis C.2 is true and the following hold:
öT 2102 21
1
82 mmi. mo? 81 231+2 C2 ddd'111 11/1
8, S
<<
2
C2
21'
2
8T C3
21
d2
21
anin. ||al|1
87
11+2((1-1))
23 2
Then, at time E [0, T.. for any p E [P.]. we have
22 dr p.t(p) = (1 + 38,) x 410 2f x(p) 221
p.a(p))
Proof. First, by Lemma C.2, we have
d 2 dr p.x(p)
2
2102/
(x(p) 21-2 p.a(p)
Σ ax(r) p.r(e))
p.m(p)
8
+ 27
2002
a ax(p) 22122
Σ (x(r p.r(r))
p.)(p)
p.r(p)
* 12 3/6 c
p ((iip)el12 8/- v mo? v ||alli Ei}
Ti d dr
+ d +2 dr p.pppp))
T2
2 dt
(p)(
For the signal term T,, by Induction Hypothesis C.2(b), have
Ti 4102, (x(p) (1 (1- V2 sp
2212
Σ rs
82 Pp a2 p.x(r)
25

---

=4102/ ax(p) (1 dy) -21-2
p.aip) + + (ellaal1) 12
p.m(p)
o, + 6 111aa111 221-3 4x(p) p,F(p)
x 410z) v2 p.a(p))
We want the error terms in the coefficient to be bounded by dr. For this to happen, first require 8, I 8y /2. Then, recall from Induction Hypothesis C.2(c) that v? p.x(p) 2 1/d. Also recall
En (1-1))) Hence, we have
% 1a1l
ÔT 2
Amin, ÔT
Amin ÔT 1-7y
d
= 1<1/1, d2
ax (x(p) 12.-3
||al| 2
|alli 2
When the above conditions hold, we have
Ti 6T) x ( p.a(p)'
Then, consider Tz. We have
T2ll s 2C or
2 p.n(p) (xx()) p.x(p) + ||all o)) C
$ (axip)) pat(p) ||all b))
x 1102 p.x(p))
2212
2212 p.a(p)
Again, for the coefficient to be bounded by ör, it suffices to require
Crantp) 521 p.x(p) dr
C2 pxx(p)
p.x(p)
ōT
5T 210 = ō, s
2102 xx(p) 121-2 p.a(p)
S
2
=
210?
S
2 C2
C ||all1 s/1
ôT 21 21 amin.
= o
S
210 x(p) 121-2
2
2
C² ||al|
p,
b9 2102 amin.
= y 1/1,
d
2
C
|all|
Finally, consider T3. We have
[T'l 12 1ali {ax(p) 20-1
1-1 mo? ||all s/}
2314 x 410 x(p)) p.xip)
= {ax())) 1/2 8/ v mof v ||all e
pzan(p)
By (6), for a (xig) 8l 2-1 22 v mot v ||all oy s
8r to hold, it suffices to have d
82 ami..
22
o axpx( br |all| 231+4 C2 1122
[1-y7
mo? s
23 S7, ES
57
d
c3
11
Note that the last condition has d both sides. Rearrange terms and it becomes
1-1
02 amin, |aal|
02 amin 8r 231-1 C²
1-297
(1-99
= v< 21'
d
231+AC2
||]|]
Combining the above bounds, we get
d 12
(M)( = (1 + 36y) x 21 21 x(p) 221
di
p.a(p)"
as long as the following conditions are true:
T : 6, S ST 2
Umin, 57 1-79 d
< 1/1,
|||||
26

---

51 21
ō9 210
21 amin.
12: 6, s
y < 1/1, d2
2 C₂
2 C
|all
02 amnn
0
T3 mot or
Ör 231+ C
231 C d1-1/22
d1+2y(1-1)
J2
1-by
anin.
y 21'
d2
Ö8
C3
||a||1
Clear that the second set of conditions is stronger than the first set. In addition, since 1->7 T-2yl the last condition on d is stronger than the first one, Hence, can prune the above
2
89
21
1
02 amin.
8, S 2
mot df
C2
21'
231+4 C2d 11/22222
1-ly
8 8T 23
21
d2
amin. 231+4
21
87
d1+2y(1-1)'
||a||
We will that the time needed for Stage is much larger than all other stages combined, which allows the estimations to be looser in later stages.
Lemma C.4 (Dynamics of the diagonal entries (Stage 2)). Suppose that at time t E [To. To, Induction Hypothesis C.2 is true. In addition, suppose that the conditions of Lemma C.3 holds and 5, S 1/3. Then, at time E [T,,, T. for any p E [P.], we have
dt p.((p) 2 2
x a p.a(p)'
Proof. Similar to the previous proof, by Lemma C.2, we have
p Σ
dt p.x(p) = 2p
- p2 22
p.r(p) 21021
ax(p) p.m(p)
(x(r))21 p
r=1
Σ ax(r) (.r0)) rml
+ 2v
200
(x(1))p1.10 p.a(p)
pp)(p)
i=7+1
+ 12 c2
( 6/ v mof v ||alli of)
d =: Ti p.((p)
d di p.((p)
+
22 di p.x(p)
+ T3
Since 22
p.a(p) is larger this time, under the same conditions of Lemma C.3, we have
v21 T&l ö7 a10
V p.a(p))
In addition, we have
80
T2 2 -2
Σ
210
anir) p.*(r) 2 -2C2 x2 rrrt
Σ
a p.)(p) ||a|| of
(p)(p)
2²
||all /+1
410 22
2102 2 k(p)
22122 221-2
pix(py
For the same reason, under the conditions of Lemma C.3, the coefficient is bounded by ő7. Hence
(
- 2
di pp)(p) 2 Tı
di p.x(o)) - -257 x 4 p.a(p))
27

---

Finally, we lower bound T₁. To this end, we compute
Ti = p
p.t(p) 21021 ax(p) (1 12 p.)m))) p.)((p)
Σ
ax(r) p.rtes)
rrop
2 2 p.x(p) 21022
(x(p))
(1-8,) 1
pppiip) ||aall1 o/)
|aal| 6
1-6, 8 ax(p) 12
D2 x410 p.a(p))
We will see that since the initial 52 pp)(p) in Stage 2 is much larger than 1/d, Stage 2 is much shorter than Stage I, whence we only need the error in the coefficient to be smaller than a constant, say, 1/2. To this end, suffices require 8, 1/3 and |all
3. and the second condition is again p.rip)
implied by the conditions Lemma C.3.
Lemma C.5 (Dynamics of the diagonal entries (Stage 3)). Suppose that at time [T si
Induction Hypothesis C.2 is true. In addition, suppose that the conditions of Lemma C.3 holds and
C2
5 Then, at time [To, T1 any p E [P.], we have gf V moi ||all: {/
(6,)'0
agin
Amiza
2 di p.t(p) (6)) xx()) (1 (1- (1-12.x())) p
d
Proof. By the proof of Lemma C.4, we have
=T di p.m(p)
d - d
dr p.ríp))
- +2
d
To
- di p.x(p))
d
x2
T3
-
dr p.mlp))
d
22
where
Ti 272
p.x(p) 2102, (arip) (1 (1- p..pp))))) spaipp) ||all sb)
T2 2 -22 ||all 5tt1
[Tsl - 1231- c2 (/2 V mo? v [|alll *0)
For the first term, we compute
|alll 5/
Ti 2 & (o)) (0))-11
x x410 ax() (1- 82 p2.
ax(p)e
2||al1 of Gnin (T. we can further rewrite the above as
When
(6%) x x10 (1 (1- 1-22x(11))
T 2
When p2 p.=(p) 1- 8, the RHS is lower bounded by (o))' 410 (x(p) Our goal now is to show
(8)) x 410 amipE.. For T2, we compute
ensure T2 and T3 are both bounded by
(6))
4C2
||al|| 1+1
-T2 s 2C2 ||ll| s+1 s
um(p) = 8 (8 amin.
60
8
Then, for T3, by (6),
(8")' 02
112 E 1-1 v mof ||all of
2231+6 dx(p)
'Note that the order of the RHS is higher than This allows to be smaller than ep and E.
28

---

(6))
(6,) 02
&
2231-60
21
8)
d
mo?
22 C
amin, &,
(6%) 02
d |alll C2
ax {
Then, rearrange terms so that they become conditions on
moi amin.
||a||| o
8
V
(6))
02
amin.
Combine the above results, and we obtain
(8%)
di p.m(p)
2
2
4
x
410
(1 v2 p.z(p))
provided that
2 2||a|l1 5o
|all (8)) amin,
4C3
23 (6%) 022
moi
||ll|
1112 E
8
6
amin. (8,)
amin.
amin.
Note that (the last condition of) the third condition dominate the first two conditions. Hence, we can simplify the above condition to be
2 C 2 (8)) 62
mo? Amin.
||a|| e
amin,
Now, we combine the previous lemmas and estimate the convergence rate of 0p- Lemma C.6 (Directional convergence). Inductively assume Induction Hypothesis C.2. Let & be the target accuracy and ör the target error in time. Suppose that
1
Y <
21'
8, =
3'
4C2
(6,)'
d
1+1/1-21
02 aiin. 231+7
6r d=-1/2
8 2 exp
mo?
s
(8)) &
10
81
log2 d
227 c2
||alli
0
amin. ||al|1
-
d 2
V
ST
(8
amin.
23144
(6,)) 22)
8 <
67
23
231-4 C2
d d1+2y(1-1)
Then, for any p E [P.], the time needed for 12
(.a(p) to reach - satisfies
1 105T
Ti-E 41(1- 1)02, mip) 221- Moreover, the requirements on d be removed if c
21-22 p.)(p) (0)
axíp) 2212 (0)
= (x(p)dii1)
23147 C2 ||a]|] 8
||all]
(8.) '0 amin, d11-))1
amin, (1--))
23++02 ||a]|] 1
||al|| 1
8,
02 amin, d1/2-y1
amin, d1/2-y1
Note that this condition is stronger than the existing
29

---

Proof (Part I): convergence rate. By Lemma C.3, for any r E [0, To we have
2 di p.a(p) = =11 36T) x 41(2) (22
x(p) x (0)1) -
12 p.nlp) (1) 1221- p.xip)
(0) (1- (1= ( x(pp)
This implies
221-2 (0) 1-11
1 48
p.)(p)
1 48
1
S To. 41(1 - 1)0 xp)) 121-1 (0)
41(1 - 1)02 x(p) 2 (0)
p.a(p)
For the lower bound, note that
2/1-2 (0)
log d' 1-1 dôg
p.a(p) 6,
6, , p.P(p) (0)
I ög
=
= 8, 2
When the above condition holds, we have
1 + 6ôT
To 41(1 ( x(p) 1 p.m(p)
2 (0)
For Stage 2, by Lemma C.4, we have
di p.a(p) 2 2110 (P20ce)))
d - 1
x2 (. (1) 2 6r (1 (I-To)) -
To.))
4721 -2
(0)
p.x(p)
T& - To, S
To.
21(1- 21
6/-1
For the coefficient to be smaller than 67, it sulfices to require
2 p.n(p)
(0)
4521-2 p.x(p))
+ (0)
4
log 2 d
S ÖT
6,
o, 2
6/-1
ôt
br
d
Finally, for Stage 3, by Lemma C.5, we have d
I 52 (ppx(p)) s s6())'
(1 (1- p.x(p))
dr
x2 p.x(p) (1) exp (-(6))' 18 102)
=
log(1/6)
81V21-2 p.xpp)
(0) log( 1/8)
Ti-o To, S (6')) 10
Ts.
(8%)
Again, for the coefficient be smaller than 8r, it suffices to require
81221-2 (0) log(1/e)
8r (6)) 81721-2 p.x(p) (0)
p.a(p) S 2t
exp
(o,))
6T (6%)
d 1-1
= 2 exp
81
log² d
Combine the above results, and we obtain
1 106T
Ti- To, = 28,
41(1 -
121-2 (0)* p.n(p)
provided that the conditions of Lemma C.3, C.4, C.5 hold and
log² d
1-1
4
+
log² d
57 (5%)
d 1-1
6, 2
and
2 exp
dör
87
d
81
log² d
30

---

Proof (Part If): resolving the conditions. We now resolve the needed conditions. For easier reference, we list the requirements of Lemma C.3. C.A, C.5, and this lemma below:
21021
1 21
8 amin
6, S 2 C
y <
moi S 81 231+ C d1-1
3 amin.
3 2
19
2
81
C
d142y(1-1)*
231+4 C2
||al|
6, $ 1/3,
C3
mo²
||lll
82
1/122
80
(8
amin
amin.
log² d
1-1
4 6T
न
log"
Ör (8))
d
6, 2
v
2 exp
dôg
81
log d
We proceed under the following principle. First, & is given parameter, so we should have minimal restrictions on it. ö7 should be interpreted the final output of the lemma. In other parts of the proof, we only need to be 1/poly small, and it is relatively easy to obtain contains form ōr 1/d". Hence, we will try change condition on other parameters conditions on 67. Finally, 6v, 6, are only used in this proof, so suffices to ensure the existence of them.
We start with the conditions on e, which are
23 C2
mo? mmin.
||alli o/ amin,
87 (8%)
1-1
8 81/2
V exp
(6)
81
log2
This can be translated into
(6,) 21 amin,
8, mo? (5,))
(6,) 02
ef s 23++7
81128/1
amin, E.
23/+ C 8,
||al]
231+7
81
log² d' d
1-1
67 z (6))
log
Then, consider ov, 8, We choose 6, = 1/3. For the existence of 6v, it suffices to require (cf. the first and second last conditions (7))
log? d dōr
1-1
4 8T
log" 2 d
87
2102
2
C2
1/1
log
d'
1-1/1
4C2 log? d 10
1-1/1
=
V
182
d
d
4C2
log² d'
1-1/1
89 2
10 21
This condition will also be stronger than the previous one, as long
4C2
log2
1-1/1
81
log?
2
1-1
2
log
1
d
(
d
4C2
(6,)'
d 141/1-21
8 Z exp
10?,
81
logg
While this is a restriction on E, it is very mild as the RHS is super-polynomin small. Now, we have replaced (7) with
4C2
(6,)'
d 141/1-2)
82 a.a.
5r (6))ee
8 2 exp
1 81
log2 d
moi s
23
d!-1/2
31

---

4C
loog d'
1-1/1
5T 2
16
d
(6,)) 0-2
(6,) (2)007 22
% s
amin.
||l|| E,
E 8//26/11
6
231+ 2
2 C
12 81
0 21
1-2yl
amin. ÖT
y 21
23
d
2
C2
||all1
Consider the last two lines. For the second last line, we compute
/ amin.
2 C2 ||all (6.))
%/ - 231+7 C2
|alli & = d2
amin,
(6,) 231
(66) 02
2
1 2
8² (--))-)-
&
ES
23
For the last line, we convert the conditions into conditions on 6r:
22
2
2
81
21
+
ôg 2 021
Ed ++y(111)
231+
d1-2y(1-1)
82
amin. dr
23143
|all| d-1/2ty1
d 2
87 2
231+
||a||1
0
amin.
Thus, the conditions are
4C2
(8))
d
1+1/1-2)
(8))en ôr dl-1/2 23/+7 C3
8 amn.
& 2 exp
mo? -
1 81
log2
2
C3
||al|
(6,)
22
E3
22
(8))
amin,
231+ C²
1
4C2
llog d
1-1/1
231 C2
23144 C2 |all d 1/2
y <
5r 2
VEd1+2y(l-1)
21'
16 21
d
+22
02 Omin.
Note that 1
1/2 < 1 - 1/1
when 1 2. Hence, the condition on dy is equivalent to
231+4
(2d1+) 23/+ ||a||| 1
ôr 2
21
amin.
To complete the proof, it suffices revert the above conditions conditions on and S7.
C.1.2 Radial Dynamies
Now, we estimate the time needed for a neuron to fit the ground truth after it converges in direction.
Lemma C.7 (Dynamics the norm (converged)). Suppose that Induction Hypothesis C.2 is true at time t. Then, at time 1, for any p e [Pa] with 82 p.x(pp) - E, we have
dr ||, 4 1110,11 (ax(p) ||, (2C 2|lall 22 e/ 2mo?))
Proof. By Lemma B.I, we have
20 21 p.x(q) 2|10p11
dr ||,l1 = 2 e|/
21
Σ
a
a
Σ
21
|| (z,.,))
9=l
P
= =2110p112
Σ
Σ
(x(4) 21
p.)(g) - ||
- ||
Σ
02
Σ Hdp
1lll (Dp.((pp)))))) 0,)
21
1=1
9=1
32

---

d Ti dr
|=,11
d 2 dr 1
+ T2
First, for Iı, first recall from Assumption 2.1 that Σi=1 22j = 1, and Σi=1 210 2i=1 2 s C. Also note that for any small E (0, 1) and integer N, we have
N-2
(1 8)- =1 No 6²
(-0)
k + 2
N-2
N 2)
= 1 - No N2 82
(-0) =1 No N282
k
k=0
Hence, we can write
60
Ti = 2|11||| Σ
02 -ax(o)-100111 1|01111))
-
+2 +2|lup1l
Σ
2 xzp)x(p) (122 (>pxx(e) - -1) 11) +1)+211p))
Σ o Σ
axig) (.
p.rlg)
F=1
1=1
9:4Fp
= =2||=p/1 (axip) - || 4C |epll axim) = 2 2||u
||all| c/
Meanwhile, for T2, by the proof of Lemma C.2, we have
[T2 2|1
|| (0p. 01)² 2 2/10pp1 (ETMP)
Σ
||wl (ūp. 11)
21
2
1=1
1=1
(ELu())
00
< <41|upl
Σ
Σ
an(1) (Vo0+ + v2ē) + +2 m
21
1=1
IETi(p)
<411bp1 ||alli 22d s/6 + 2 ||plll mo?-
As a result, we have
d
||ul1l 4 A||0/11 dr
+ 1|1lpp1| (Cr (Caaxip] & ||all of + ||all, 221 mo?)
=4||bp|| ((x(p)-11v (2 2|[all, 221 s/ + 2mo?))
Lemma C.8 (Fitting the signal). Inductively assume Induction Hypothesis C.2. Consider p [P.] and & 2 4 (Caa ||all; 22' / + =mo)). Then, after v2 p.x(p) reaches E, it takes at most
bog (1 amount of time for || to reach ax(p) In addition, once it enters this range, 4xip) will stay there.
Proof. Let To be the time 2 p.a(p) reaches 1 - E. By the proof of Lemma C.6, 12 p.z(p) will stay above 1- E after time To. By Lemma C.7 and our hypothesis on 8, we have
|| = ||///|| (ax(m) 11pp11 = & =
In particular, this implies that once ||,/1l reaches ax(p) it will stay in this range. Let 1/,1/2 and TR,1-s be the time ||,l| reaches xx(p)/2 and 1 respectively. For any s TR.1/2, have
| 2 4ax(p)
(4xx(p) (t To)
| = ||o,(0]| 2 of exp 3
di
33

---

3log (ax(n//o))
TR.1/2 To
ax(p)
After 12.1/2 and before TR, we have
||plll ax(p) (ax(o) - |10/p| di
d
ax(p)
(xx(p) - -110p11²)
2 2
(x(p)(1) -1100l
z 2 exp
ax(p)
3log (axip)/e)
TR.1-C-TR..U - -TR,1/2
xx(p)
As result, we have
3 log (az /
(log (mxm)//²) log (dx(p)/e))
TR,1-E - To s ax(p)
ax(p)
We now ready prove the main result of this subsection, which we restate below. Corollary C.9 (Convergence). Let &D. ER be our target accuracy in the tangent and radial directions, and 57 the target error in time. Suppose that y < 1/(21), 6, 1/3,
231+7 22 ||lll &D
2 C2
|alll 1
(6 amin. d(--)) ER 2 12||a|1; dd 57
amin.
d1/2-yl
mot
21 minn.
(8))' ôT
ER
23
dl-1/2
(8))
02 23144
E (( C3
ER 12C2ux(m)
8
d1-2y(1-1)
Then, for any p [P.]. have
2 p.z(p) 2 1 1
||p|12 ax(p) ER.
Vr 2 (1+ 200r)
F
log2 d
22 p.z(p) S
||인2|( oo.
Vr S (1- 10
d
where
Tp == 4/(1 1)0 xx)) 2212
=
= = (nip)di-1
(0) p.x(p)
an(p) 22 (0) p.x(p)
Proof. First, by Lemma C.3 (and the proof of Lemma C.6), we have
log² d
1 108r
2 p.t(p) (1) s 8, =
VI S
5T
d
41(1 ax(p) p.x(p)
+2 (0)
Meanwhile, by Lemma C.6, we have 82 p.*(p) S 6, D2
2 1 1-ED
ED after time
p.t(p)
1 1087
Tr 41(1 - 1)00
x(p) xxpp)
221- (0)
p.x(p)
(x(p)) (x(p))>21 p.x(p)
(0)
as long as y < 1/((2), 8, = 1/3, and
231 C2 ||a]|
231 C2 ||al]
SD 2 (8,) anin, d
87 2
amin, d1/2-y1'
21
34

---

02 amin
1g
moi
(6,)' V3 d1-112
231+ C2
(8,)
8 (2 19
& <
231+ C
231+4
d1+2y(1-1)
By Lemma C.8, fitting axip) to HER takes TR amount of time, where
3 log a (xpp) ( TR =
ax(p)
c2 |all
Since 5y 2
85 Amin d112-11+ have
Srd'-1 241 1) (log 2)
TR s 1T
log
x(p)) og
d(1-))1-1/2
= ER 2
exp
(log
d)2log))2122)
Again, this condition is mild as the RHS decays exponentially fast. To meet the conditions of Lemma C.8, it suffices require
mo?-
ER 12 1 dd
a2C)am(p)
12
Note that last condition on ER is stronger than the previous condition on ER.
C.2 Maintaining the Induction Hypotheses
In this subsection, we show Induction Hypothesis C.2 is true throughout training. Recall the meaning and requirements of Ep. ER. ör from Corollary C.9.
C.2.1 Upper Bounds on the Irrelevant Coordinates
Lemma C.10 (Upper triangular entries (case I)), Consider [P.] and (x(g) 2 min,, (2(log d) 22).. Assume the conditions of Corollary C.9 and
[P] with
E
2
5,
mo? S
32
amin.
5,
231+
24
11+2y(1-1)'
231-1 2(log d)21 221-2211117 24
1/-- 6r
8r
a amin,
5,
2
Ö7 S
(log² d) 1//
4
(log² d) ve-yt
231+ ||al| 221-2 24
240
Then, 52
pp)(g)) S En throughout training.
Remark. Recall from Lemma C.6 that we only need d7 2 6(1/d112-r) and by Lemma B.2, 6, = 1/poly(P()) Hence, the last condition can hold as long d is large.
Proof. First, by Corollary C.9, know D2 p.x(p)
2 1 E after time
1 1 206
Tp = 4/(1 - 1)0 (()) 221- (0)
p.x(p)
This automatically implies 52 pp.((p) $ E z En after time Tp Hence, it suffices to consider the time
before Tp- By Lemma C.2 and the choice Eo 2 E, we have
d di p.x(g) 2 Σ
210 xxig) 22
p.xlg) 12 34+ c2 p.xcoo ( v mo? v ||al]; o/)
35

---

d Ti
( d
dr p.)(o))
52
+ I2
12 do p.z(g))
Since our goal is to upper bound 1? need to track those r. Then, for T2, we have
p.T(q))" we may assume w.l.o.g. that 82 p..((p) 2 1/d, as we only
T2 s 1231+6 1/12 (axig) 22 60-1 vmo v ||a|| Eg) 221 pp,(()))
Meanwhile, for T₁, we have
Ti = 410 axle) p.r(q) +
Σ i=++1
2
21 ((4) p.x(g)
221
8
n
121 p,=lq) 22x xg) 22
p.
60
210
i=/+1
S <410 xlq) 22. p. rr xrg)) 2l
2C
Combining the above two bounds, we obtain
d
- 22 di p.)(()) 410 121 p.xlq) + +2 araa 8.
12 c2 1/2 1/2 (x(1)) (6 (5) v (11112 v moद v ||all| o0) oy placa)
$ (1 (1+ ōupp) 410 4xiz) 121 p.z(a)'
where
C2
(arig) (6 v mo? v ||all og)
Stup
ax0g)
4102)ax(q)
C9
2 234 11112
{a 6/2gg)8//20 1-1 v moi v ||a|l of}
1 21021
azin))))
6Tmp.1 + 1mp.22
As result, for any / Tp. we have
p.x(g) (0)) -
2 p.x(q) (1) s 22 p.) (0) (1 (1-(1- (1(+ 8tpp) 4102) 22-22
In particular, this implies
ax(4) 221-2
(0)
-
2 P. (1) S x2
(0)
1- (1 Stup) (1+ 2067)
p.
an(p) ax(p))21-2 121-2
p.T(p) (0)
(1+ 8 Tmp)
(1 + 2007)
1-1
$ 22 pxx(g) (0)
1 1
+
6r 20
2 (() (0)
20ōT
where the second line comes from Assumption Ca) Now, we find conditions under which the last term is upper bounded by &D = (1-y), We will first find conditions under which 20m + 2057 S 8, /4 and then upper bound 52 (.)((g) (0) A4.
We compute
8,
162 8
26
5
d2
12
C²
12
8,
8,
2067
87
12
240'
36

---

and by (6),
12. axiq) 8,
20 5
=
mof v ||al|; of s
12
23 C d1-1/2 24
02
8,
02 an(q) or
ES
mot
23 24
dl+2y(1-1)*
231+4 d'- 24'
21
ax(4) dr
d
C31+1 ||a|| 24
The above conditions ensure 8,/42 2dp 208y. By Assumption C.1 v2 Hence, in order for 22 p,a(4)
p.x(p) (0) log² d/d.
(0)(66/4)-1//t be smaller than &o, it suffices to have
log d 6, 1
d²
6,
$ (1-1
log2 d
We now clean up the conditions required by this lemma, which are the conditions of Corollary C.9 and
8,
82 axig) 6y 231+4 Cr
8
mo? S
231+
& 24
d1t2y(1-1)
d'-1/2 24'
-
6r
ax(q) 6y
172-y
16 6y C2
8, 240
d
8g S
(log² dy
231+4
C2
||a||
12
For the condition on d. since 1/2- < 1/2 y. the first part of it is stronger. Finally, we use the hypothesis ax(q)= 2 amin, /2tnn//22llggg d) 21 to replace (the first part of) the second condition with
32
5, 1/2 (log² d) 1255
mmnn
d 2
23 2 ||ll| 221-2 24
Lemma C.11 (Upper triangular entries (case II)). Consider p [P.] and p 4 [P] with ax(q) S amin, (2nin,/2llg"" (2 d). Suppose that the of Lemma C. are are true. Then, $2 p.x(g) S 80
throughout training.
Proof. By the proof of Lemma C.10, we have
d - 22
41022 x
221 pl 2C 2C arig) 621 ( 60
dr p.x(g)
1/2 (12 o0 v mo? v ||all $ 221 p.r(g)) 2146 c2 11/2
Suppose that ax(g) S amin. /M for some M 1 to be determined later. Then, we have
- 2 p.x(g)
5 410 amin. 2
M p.n(q) +22 Omin, 2.21 (px(g)
ED
+ M+6 c2 11112 {amin. g1/2 1-1 mo? ||all ob) 52r (lraig)
M
amin, 21
$ (1 + ŌTmp) 4102,
M p()(g))
where
C2 80
33+66
1-12 M
[miin 1//iin=////00 21/2 mo? 6
8mmp
2102
40
amin.
.M
8pm.111 + SSmp.2.
37

---

As result, for any 1 < Tp. we have
amin. 121 (0)
+
2 p.x(g) (1) s 22 p.xig) (0)
dmin,
1 - (1+ )mpppp)) (1 2067)
M
Max(p) 121-2 (0)
p.t(p)
Recall from Assumption C.I that 12 M 2 log21-2 -2 d, we have
p, (0) 2 1/d and p2 p, (0) - log" d/d. Hence, with
Amin, 121-2
"p.Tiq)
(0)
Amin, log log2l-2 d
1
1
$
Max(p) p.x(p)
2212 (0)
axip)
M
2
Hence,
22 px)(q) (1) S 22 p..(()) (0) (1 + Ótup) (1 105T) -
2
As result, to ensure 12 p. S Eo throughout training, it suffices have òTup 0.1 and dy 0.01. The second condition clear holds under the hypotheses of Lemma C.10. For the same reason, we have 1mp. I 0.05 and the first term in dtap.2 will also be sufficiently small. Finally, compute
1121
M
mot
M [|all]
S
1
4021
amin.
amin.
20
23/+6
1
40 amin,
1
d
40 amin.
= =mo
S
2
20 C3 2 log d d122
41 log T-7 d
40
C3 ||all
which are also covered by the conditions of Lemma C.10. In fact, M is chosen to balance the requirements of these two lemmas.
Lemma C.12 (Lower triangular entries). Consider [P.] and p < k E [m]. Assume the conditions of Corollary C.9 and
5c 8r S
a 8e
402
21
a min. 5²
ER S
& I
240"
68 8(lgg d) 1-1"
48
231+6
(log² d)21-2 11+2y(1-1)*
1
62
a²
de min.
1
d
1
402 aminn de
mot -
2
48 23/+4 (log² d d1-1/2"
(log² d) N
6 231+66 ||aa||
Then, we have 22 k.a(p) $ Eo throughout training.
Proof. First, by Lemma C.2, we have
P ax(r) k(((r)
12 dr k.t(p) = =2v2 kp) Σ 2102 ax(p) -212
Σ
22
k.t(p)
8a
1p (1pee))lleppp] (2,
Σ
2 2
(p)(
* 122116622 (2 {ax 1-1 v mo? v ||all o/)
$ 2 kk))))
Σ
2002 (x(p)) 1 (p (p 1.) ||,p1 12] 2 (p)
+ +12 Colix. (axp)))) 200 vom v ||all| eg)
d
Ti
dt kkxxip)
To
dr k,)(
38

---

Similar to the proof of Lemma C.10, we assume w.l.o.g. that 12 kxx(p) 1/d and write
I2 $ 1231+ 22 kxx(p) d {ax(p) 2/ v mo v ||all %0
1/2
For the first term, we have
I z 410 xx(p) - 1 {p L)) ||pl|
22
{ +2 Σ
210 x(p)
xp) k.x(p)
i=/+1
4102/ ax(p) 11p E L) |1 |p|l
22
(xx(p) + xxp) (() 80
Cz 210
x410 x(p))
ax(p)
Therefore,
1 1pp L) ||pll
22 dr k.t(p) $
+ +TTpp
x x110 xx(p) k.(()))
ax(p)
where
C9
C2
moi
||all
d--1/2 E112
òtmp
21021
40
amin.
amin.
=: 1 1 8tup.2.
By Corollary C.9, we know p L and ||up|| = ax(p)) + ER for ER satisfying the condition in Corollary C.9 after time
1 1 206
Tp == 4 221-
p.x(p) (0)
We now analyze the stages [0, Tp] and [Tp. separately. Let 5/ 8o be parameter to be chosen later. We want to show that v2 kxx(p) upper bounded by e the first stage and by Eo in the second stage.
First, for Tp. we have di 12 k() S (1 δtmP) a(pp) ((p()) and therefore
-
22
(1) s 22
kxx(p) (0)
(1 -I 1)(( 8TeP 416 (()) kkx(() (0))
21-2
ax(p) 221-2
(0)
-
$ 22
())( (0)
1 1- ÖTop) 200T)
k,T(p)
ax(p) p,*(p)
121-2
(0)
[6c -20Tmp.1 - 28 2007
$ 22 (p) (0)
where the last line comes from Assumption C.1(b). By the proof of Lemma C.10, we have
6e
20Tmp,1 + 20mmp. + 20ō7 S
4
provided that
ôe 240'
22 amin 8e
12-yy
8T
S
d
23/+4
2
||a|||
24
82
6c
a amn. de
21
moद -
21
231 C3
24
d1+2y(1-1)
231 C2
112 24"
Then, we compute
log2
de
log² de -
(1)
k. (1) 1
=
& =
d
4
4
39

---

Now, consider the second stage. For 2 Tp. we have
d
di k,((p) ax(p)
+ ÖTup
k.x(p)
41 (11-1))aaipp(e) (T-T))) -
(p)( (1) s s |
ER ax(p)
+ 8mpp
Also, recall that the training process ends before time
1 + 2007
Tp. 41(1 ((.)) 22-2 (0)
P..=(P.)
For any E [T'p T, we have
ax(p) (6/1-11
-
ER
[2z(p) S 6
+ òtup
(1+200
ax(p))
ax(P,)
221-2
(..)((.))
(0)
2(de)) 1-1
ER
$ 5
1
+ 6TMD
Omin.
amin.
8(log² d)
ER
$ 6
+ dump
Amin.
amin, 6c
where the last line comes form choosing (C.2.1). For the last term be bounded by Eo, it suffices to require
ER
8(log² d) dd'-1
ER
1 amin 6e
+ Ōuup
+ Smp.1 + +1pp22 $
dmin.
amin, 6c
amin.
2 8(log d)
which is implied by
a min.
8c
2102
amin, Se
1-
ER
S 8(log d)
d 2
6 C2
8(log² d)r-1
and by (6),
1 40221 min. 6c
1
4
amin, &c
2
mo?
E
6 23116 8(log" dd'-1 d1-1/2"
6 2321+6 C2
8(log² d)--1
d1+2y(1-1))
d
1
a 21
2
de
(log² d) 17--1
6
231+6
||all|
Combining the above conditions with (C.2.1), we conclude that 52 kxx(() S 80 throughout training, as long as the conditions of Corollary C.9 and the following conditions are true:
2 6c min.
6c 8T S
ER S
240'
6 68(log dd--1'
22 amin,
40
a² dc
mof S
min.
23 11-1/2 24
23/+6 C2 8(log² dj 1121/2"
2
40
21
amin, de 8(log² d) d1+2y(1-1)*
E
23 24
d1+2y(1-1)
23
22 amin de
121
amin, de
-
22
23/+4C2 ||||||
24
6 C3
8(log2 d)'-1
40

---

4
Lni dc
(log d) 112-07
2
8 ||alli
To complete the proof, suffices to keep only the stronger one in each of the conditions on mof E, and d.
Lemma C.13 (Lower right block). Consider k E [m].9 [P] with k.4 P.. Assume the conditions of Corollary C.9 and the conditions of Lemma C. 10, with o replaced by 8,. Then, have v2
k,z(g) I Eo throughout training.
Proof. By Lemma C.2, we have
d 22 dr (.)(q)
$ 2 Σ
200 a xx()) 22
k.rig))
i=l
+ 12 c²2 vx. 22
moi v ||a]l cj
=: Ti
22
k.mlaa)
T2 di k.)(0))
d
x2
di
For the first term, we have
410 21 x(g) 22
Σ 210
2 x(g) v k.r(4)
k.)(g)
1++1
s 410 a v 21
+ 2C ax(g) k.x(4)
k.x(a)
x xl k.((()
210
Similar to the previous proofs, we may assume w.l.ogg. that v? h.m(4) 2 1/d. Then, for the second term, we have
T2 1231+662
1212
21 mo? ||all o/) 52 ())((g)
2
mot ||all e x k.)(g)) axly) ax(g)
1112 1+1/22
402
As result, we have
C.e0 1+
22
mo? axig)
eo / an(q)
||all
22 dr ( S
141/2 g1
+
v
2102
402
x 410 2102) k.
22
Note that this is the same as the bound in the proof Lemma C. and Lemma C.11. Thus, to achieve 22
(g) Eo, it suffices to require the same conditions as in those two lemmas, with ö, replaced by 8, (cf. Assumption C.1).
C.2.2 Upper Bound on the Norm Growth
Here, we verify Induction Hypothesis C.2(a).
Lemma C.14 (Upper bound on unused neurons). Consider [m] with > P.. Suppose that
y 1' d2 amin.
1(1
1(I-1)63) ---x
||l|]
2
Then, we have 1|= eof throughout training.
41

---

Proof. First, by Lemma B.1, Induction Hypothesis C.2(b) and Assumption 2.1, we have
d dr || s 4 11
Pp P = 4 11xx111
apei s 4 e' ||
21
1=1
Thus, by Gronwall's lemma, have 1 of exp (4 |||||| Egr)
eogo long s
(4 [|laal] s/) By Lemma C.6 and Lemma C.8, the training process ends at time
2
d=1
Tr. & 41(1 1)0 ((.) 22-2
$
(P.)((.) (0)
21(1 1) min..
Hence, it suffices to require
d'-1
1(1 1)
d
amin,
2 |||al11 60 21(1 1)03 amin
|alli
2
1
amin.
I(I - 1)
y y<
d2
||a||
Then, we consider = x P.. Unlike those unused neurons, since up will eventually converge to ex(p), its norm cannot stay small. Our strategy here will be coupling its norm growth with the tangent movement.
Lemma C.15 (Upper bound on | with p & P.). Consider p [Pa]- Suppose that the hypotheses of Lemma C.14 and Lemma C.6 hold. Then, ||pl| of only if p.x(p) 2 1 where of = 20
Proof. Again, by Lemma B.1, Induction Hypothesis C.2(b) and Assumption 2.1, we have
dr | s 4 1 Σ ax(g) 22 p.)(a)) s /||0p/| Σ
-
02 (xxmm) D par(p) + ||all s6)
i=1
paatp) s 4||lppl ax Paapp) 4 || |lall o6
Hence, by Gronwall's lemma, have
(0lf s of exp (4]la|l, s/6) exp (4 I' 22r
p.m(p) (s) (s)
Let co > 0 be a small constant to be determined later and let To be the time 22 p.tip) reaches 1 co/L.
By the proof of Lemma C.3, we know
22 dr (i)(p) 2 (1 - - ((1) p.=(p) 2 co20 +21 p.z(p))
Integrate both sides, and we obtain
1 12 - co/1 42 p.x(p) (0) 2 co20))ar(p) 1 To p2r p2ixip) (s) ds.
As result, for s To. have
[0][ of exp (4 |||lll e exp
4ax(p)
co20? ax())
s o. exp ||||a||| T exp
2
co 2/
42

---

Clear that To - Tp, and under the conditions of Lemma C.14, we have 4 ||al| TTTp, s 1. Therefore,
|,0p of exp
I+
2
Vi s To.
COO
Now, consider the To S 1 $ Ti, where Ti is the time 82 proof of Lemma C.6), we know
reaches - E. By Lemma C.5 (and the
p.x((p)
d 22 di p.T(p) (1 co) 10) (1- 52 p.p(pp)
log (co/e)
Ti To
(1 co)l
Thus, I [To. Til, we have
||, ||)6( exp (4 ||lll c6(Ti To)) exp (4a x(p) (Ti - -76))
log (co/8)
[T)]]] (1 (1)(())) exp 4 (1- co)c
o(1))
(T)6| c0 a-saltog
Choose co 1/2 and recall ||> s og exp (1
2_
Then, we conclude that
[,] 20 81(103) = of.
for z Ti. Recall from Lemma C.6 that once y2 pp.(p)) reaches E, it will stay above 1- Thus, this implies that ||>l|| 2 of only if D2 p,m(p) 2 B.
C.3 Deferred Proofs
C.3.1 Proof of Lemma C.2
Proof of Lemma C.2. Recall from Lemma B.1 that
[[I - 01
P Σ
Σ 200 2i
ap
21-2 k.p
Tk.p
|
i=
r=l
20
210
Σ
|| (Üx, B1) 21-1 101-1((1- ((I- Ux
you. 0z) ep)
2 Re-index the summation as ΣP- ax(r) (,x(r)'
replace p with (q), and obtain
()))())
Σ
2102
221- aníq)
x
Σ aair) 22r xix(e) (2
i=1
Σ
2i0
Σ
||rl| (Ūx, 21) ((I- 8x 01, exir))
21
1=1
lilkk
Therefore, we have
P k,)(1))
dr (, 272
d12
k() Σ
2102
axig) 22--
Σ
xx(r) (x(r (2.
k.T(9)
(k /} 2Fx.)(
Σ
2102 |
(ūx, )q) 21-1 (II-xxī)66 0g. 0g. ex(g))
- -
210 2
Σ
|lyll22 (8x. 2i-1 ((I 0x0, (
le(k.q)
43

---

d Ti v2 dr /
d +T2
( dr hx)(g)) v
22 + I3
{
di (
We keep I it is, and simplify T2 and I3 as follows. Consider T2. When q $ L, we have | of. and therefore,
(When q & L) [T2l S 2 x(,)l
Σ 200 s (()
where the last inequality comes from Assumption 2.1. Now, suppose that q L. In this case, we have By = Sq (x(g) where Sq := sgn V xxx())- This suggests writing
(ūx. 21-1 ((I (6-0x ex(a)) (ūx. 0g) 20)2111 ((ăg. ex(a) - (ōx. Bg) (ox. ex(a))
(ōx, Ga) 21-1 )q))(a) (ōx, 0g) Fk.z(g)-
By Induction Hypothesis C.2(a), we have 72 Hence, 8 fq,z(4) Sq + E. In addition, we have
2 1 1- First, this implies 1V 1g 2 VI 11-E2 1-E.
q.
|s u/ll = v/2 - (sgerig)) 0g) V2- -22222g + E) V2E.
As result, we have
(ūz, Bg) = (ōx. sy(x(a)) (ōx, SgC((n) BB) = Sq ((,(()) # (|sgen(()) dall = =sg V2E.
Combine these estimations with the previous identity, and we obtain
(o), (2) 1 ((I 06 Gg. ex(g1) (6x, Bz)) 311 (g)x()) - -(ōx, )²) Fk,
21-1
(5q +) - (saPk,z(a) v2E) 21
= PSgPk)) + V28)
vk.
Note that, for any a. E R and integer N, we have
N-1
(a+ O)+ aa
N n 8r =a 6
Σ
N
a-N-n1 8"
n
n=0
12 1
N-1
= a + 6
Σ
n+1 a (N-1))-8"
N
n
n=0
= a
SN (lal (81) N-1
181)~~11
= a N2N N2N~11 N5 161
Thus, we can further rewrite the above as
(ū), by) 2i ((I 51
) 8g ex(y))
1 k.n(g) + 12 (8 (2) (x((a) v 112) (sq + E)
21 21-1
=
(122 ((t(()))
+ 112 TR
21-1 v 8d) v2.((1)
= ) (xmlg)
+ 2 E 2:231 (81/2 (2
v gt
32 v()((g)
For the last three terms, clear that the second one is the largest as it has the smallest exponents on both E and Fk,z(g)- Also recall from Induction Hypothesis C.2(b) that (Vx, eo. Thus, we have
(ūx, Bg) 2 ((I ( exig)) (1 1--22, )).,(w)) 22..119) 3/2 (8)/2e) v 81-112).
As a result, we have
(When q E L)
44

---

Σ
210 u0/l ((1- 22 k
82 + 3122 (5) v 81-11))
T2 1--1 # q) a(q)
1=1
= =- (k # g 2 Σ 21 |0ul1 (1 (1- (2
12 k()(())
w 28 2vk.n(q)312" (81 6 1011 vo!-1/2
Σ
21 |al
-1 (k # 9) 1|/l (1 (1- 12 k.)(4))
Σ
210 22
kix
k.x(4)
1=1
=1212 (za (51/66
d- v 112
Combining the cases q E L and q L, we obtain
2
T2 =2=11 [k # 9,4 L) 2 l|/l (1 12 x2))
Σ
210 22
2 k.z(g)
+ 1212 C (x(g))
v E112 (/)
+ 2 xi
Now, we estimate
80
T3 == -VV2,x19)
200
Σ
|لae| (ūx, 81) 2 ((I -1 j1. ex(a)
)o,,
1=1
(e(k.))
= -27x,x19)
200
Σ
melll (ūx, 21 ((I [ )1
ह.. ex(a)
21
lELU(k.a)
-2vk,
2i
2
2
Σ
||w/11 (Ux, 011 ((I- -(x0% 00, en(g))
1=1
(EAA(kg)
=: T3.1 + T3.2.
Similar to the previous analysis, for T3.1. we have
IT..I s (l
Σ 210 21
Σ of (222ollammi)l 1)o
lELUth.g)
Consider T3.2. Note that by our previous analysis, for any L {k, q}, we have
(7x, 0,) 21 ((I (20 (,)))))))))))
2-11
V(xx(1) (STE..O + v28) 2i v1.
$ (( + V28
<VVo+ v2E)
21-1
(veo+ + V28
Veo +
Note that voo v VE 21 1
VoO v vo² = v ह.. Hence, we can bound the last term as
(ox, ;7) 21 ((I - कх 01 o1 ex())) 2 (s) v
Therefore,
8
(T32l $ 2Vz,m(9)
Σ
2002 (EL:(K.9)
Σ
|| 2/22 (eb =2)) ||all |Fx.x (sb v vo)..
As a result, for T3, we have
[Tyl 20 20 1)07 + 2 c2 ||all (F (s6 vo').
45

---

Combine our bounds for T2 and T3, and we get
2 dr (la(4)
d -
22
Σ
6
210
22- anla)
Σ
P
a (x(r) (x(r) 22
k.)(4))
k.)(g)
kat(r)
1 + 9. (1-1h
Σ 21 12 kxx(1)
1=1
121231 C
v v (5)
2/ 2(n of
* C (m 1) = C² ||al| |=x, (sb v 8
For the last four error terms, clear that we can merge the second and the third terms, which leads to 20 (x. mmo.. Meanwhile, the largest coefficient is 12/2 C2. Thus,
d 2 dr kmm()) = =272 (())
200 2i
axiq)
(
k,tia))
Σ r=1
xx(r) V karir)
- 1k # q.q 6 2/2|uul
-1- x(
Σ
2 2
22r k,x(q)
* 12 Tx (x(σ) (6 v v1121 moi v ||all (ob (/)
e/1 and sy v E = = Finally, recall that E s ep. Hence, 5f v g = 2/
Now, consider the second part of the lemma. In order for an(q) 2/ mo? v ||all sy s 6, clear that we need mo? z 6. Meanwhile, for the last condition, we have
||l|| 5o = d-01-11 s
8
=
d2
8 アि
aalli
||all1
For the first condition, we have
2 ((0-))(--))
a xxig) 21 1-1 56 =
ES
(x(g))
C.3.2 Proof of Theorem C.1
Proof of Theorem C.I. By Corollary C.9, Lemma C.10, C.I1, C.12, C.13, C.14, and C.15. Induc- tion Hypothesis C.2 holds throughout training and the conclusions Theorem C. are true, provided that all the conditions of these lemmas met.
For easier reference, we collect the conditions of all above lemmas below:
Y 1/(2),
8, 1/3, 6,,1 = 6, A 6,,
23147 C2 ||ll|] dD 2
23 ||all; 1
ER 2 1||||||; 22d - 8r 2
(8 amin, d(1->)?'
0
amin. d'/2-y1
22 amn.. mo?
(6))'8 Va
8r
ER
^
23/+7 C2
11-1
12
5 (1,))
2
(1-)))))11
19
231+4
02
2
d1+2y(1-1) A
12C²a
ER
24 129
mo?
02
amin.
6r.t
221+42
d1+2y(1-1))
231+4 2(log d) 21 201-221-10 11-1/2 24
d
(5r1
021
amin.
8r.1
1/--1
88 S 8
(log2
d/
4
1-1 (log²
231+4
||a|| 221-2
24
240"
d) 1ン
46

---

6c
a² min.
40 21 48
a² 6² (log² 2)21- d1+2y(1-1)*
min.
240'
ER
$
6 88 d)--1"
&
231+66
mo² S 48 23 (log' d)--1 d'-1/2² (log² d) 1/-y1
21
d min. dc
1
d
1 40 min. de
1/-00
1-1
6
C3/+6 ||all|
In the following, for notational simplicity, we will use So and o to hide constant that can only depend on o.. First, consider the conditions on y, which
1 and (log² d/
6
y < 21
2
4
For concreteness, we will require s 1/(41) and choose such that
-
d"
log² d
4
For such a to exist, it suffices to have
(44))
6r
d
2 6,
log" d
log d
First, for the conditions on the target accuracy ED. ER and error in time Ör, need
||all1
a d 8e
||ll|
ED Zo amin, d'-1/4² d1-1/4 Sor ER Sor (log d)'-1²
amin, d1/4 So Ör So de A 8r A dr
Then, for E, we choose
62 d(log d) (11-1)
82 (log? d) d(log d) 4(1-1)
a min. 5²
o of (1-1))
ER amin.
A
d(log 4)-(11)
The condition on mo? is
d 5c (log² d) d1-1/2
mo Sor amin, ED A amin, Ö8 dl-1/2
amin. 6r,t
ER A
(log 2
Since of 20 2 81(152) this is equivalent g8i(1a3g) of Sor
amin, δT d/-1/2
amin, Sy
8. (log² 2 d)' 1 dl 1/2
a²
min,
amin, ED
ER A
m
(log 21
Finally, the conditions on are
d
d (log² (1-
1mmin 6r. ||a|||
tta
a2
min, 8e
-14
2 6,
log
81 d
||ll|
which can be merged into
mmin &e
amin
(log² djat Zo 8, v
6r.
||ll|
||al||
47

---

D Online SGD Dynamies
Our goal in this section is to prove Theorem 2.1, which we restate below for convenience:
Theorem 2.1 (Main theorem for online SGD). Let C, C" > 0 be large universal constants, depending only on and or, and set the initialization scale as (7) d' C Let P. E [P], amin, = miinp((P)] ap- and bg be the target failure probability, Define width m, learning rate n and target accuracies &D. ER = 0n ( satisfy
mP maP mP m. = ().. Assume the dimension
6,
d & I|alll A 8 min.
m % P.. 1) T mmin, ||a|| m p-1 min(A2d .e
ED & ||lll amin. 1+144 P. D + p. 1/2
ER 전 ED.
Then, with probability least 1 6p there exists an ordering of the student neurons U1..... Um and a mapping [P.] - [P] of student neurons to teacher neurons (see Equation (5)) such that, defining
where S. hide both constants and logarithmic
Tp --1(I a (0) Vp [P.), and T (1+ maxpe[P.] Tp
we have:
for (a) (Unused neurons). [|0x(r]]| d' = for all P..
(1) 2 E-E,. (1) = a ax(p) for all E [P.]. (HA)T, S 1 S Tmax- (b) (Convergence). sp (prii)
(c) (Sharp Transition). 22 (px(p) (1) d 1/2 (1)1 s of for all p E [P.]. 1 s (1 (1-A)12 T-
(d) (Loss Value). At time 1, the population loss of the student network can be bounded by
1- Σ a (x(p) fr 2 (1- (1-A/4)T,) -(EE)) s [(t) 1 PC[P.]
Σ a 2 frz (1+A/47,)+ PC[P.1
Similarly the gradient flow setting, our proof will proceed by maintaining Induction Hypothesis C.2 with high probability throughout training. We will additionally maintain the following induction hypothesis the growth of ||,,1|
Induction Hypothesis D.1. The neuron up learns time (1 o(I))Tp; that
(a) 2 p.x(p) (1) 1- spp for all / [(1 TT Tmax).
(b) |||p|| app ER for all r e [(1 + 4 T..
To maintain these induction hypotheses, we rely the following stochastic induction argument from [RL24]. Suppose that the goal to show a stochastic process X, stays close to its deterministic counterpart x, with high probability. First, assume X, x, and use this induction hypothesis to obtain estimations on the related quantities, such as the variance of the noises. Then, using these estimations, we show that when X, is still close to X,, the probability that X, will drift away from is small. This argument can be viewed as the stochastic counterpart the continuity argument, and be made rigorous by considering the stopping time that X, is no longer close to x, and analyzing the stopped process (X,xz);- One may refer to Section F.2 of [RL24] for more details on this technique. Finally, we remark that this argument be easily generalized to cases with multiple induction hypotheses by considering the stopping time that any of them is violated.
D.1 Preliminaries
The following lemma decomposes the online SGD dynamics into the update on the radial component [1)]())²² and the tangent component v22,p + 1).
Lemma D.I. Fix k [m], p E [P] and > O. Let ōz E (0, 1) be target failure probability at this
step. Let C > 0 be large universal constant. Suppose that s 2 ( [|a]]] @ (mdd)=m))))))))
and let Ht 1) = Vell VoeL denote the difference between the mini-bated gradient and the
48

---

population at this step. Then, we have (denoting Uy := Ux(1)):
[1 + = + 41
8
2i k.p
Σ
02
| (ox. 01)
11xx
-
1m1
E=1
-2n (uk. H&) + ER, 1).
R.p (1+ (t+
k..p +2m =R2.p
k.p Σ
210
ap Kppk.p Σ
Ag k.q
1=1
k.
200
Σ
|10111 (ox, B1) 01) (1)-
lilkk
+ +Et. 1), ((I oy U2 HK, ep)
k.
where (x. 1) and Ex.p(t+ 1) satisfy
(Ex, 1)1 s Cif [|all log
md
||xl| (x.p((+))s&& (1 (IV v c ||al] loge óp
md
óP.E
with probability at least 1 6p.E-
Proof.
Let k E [m] be fixed and r > O. We write
/ Vo, + (Ver vo. Hx.
where v denotes the mini-batch gradient. First, consider the dynamics of || 11 By Lemma B.I, we have that
(1 + 1)11 = =1lux - ",, ||
=||vx|12 - 217 (uk, Voz L) - 2n (Uk, H&) + +1² 1//155m 1/5e, 1||
8
80
1 1| (ōx. 01) m
[|ux|1= + 4n
2 a
|
K.P
p=l
2n (Uk, H&) 1²
4 1|
By the tail bound in Lemma B.1, , for any given direction u E gd-1, with probability at least 8e. ||wæ|l for some universal constant C 0. Take to be
we have KVez4, u)) C ||all; log ok and ei..... ed, and replace 6p with 6p/ (2d). Then, we obtain
(m/6g) (mg2/2(mm/0)
Kox. V., |>| s C [|al|, log (md 1111 || II s Cldll 1mg@ 1|
for some universal constant C > 0 with probability least Sp. Plugging in the bound for || 1|] yields the desired update for [] 1)I
We next analyze the dynamics of v2 where [P]. To this end, first we estimate 1/1l 11 With probability 1 ōp we have that,
(r + 1)11 = || -22(( vx) + 172 1 !l 2|
1| (1# 2n/C ||al|, log ( C2 (md)6p))
When 2 (Cllall) d (md3((0)))))) have
C2 (0g (md/0p) s 2n ||a]|, 012 (md///mmd//// (md/6p) 4
49

---

Hence, we can use the identity
1 1 202
V|ol s 1/2
to obtain
2n (ok, Vel!)
of 1/ ml 11
md 0p
1 +
8/ ||all
loge
(1 + 1)11?
||
1|0211
|1x111
2n (ox, VoL!)
mmd]
1
+ 2/ ||lll log
||
1|wx11
82
Therefore the update for uk.p (1 1) is
v2 k.p 2 (Vo, ep) + + (Vogl.ep)
12 (1+ 1)
| 1)112
(Vog ep)
md
k. - 2n
C²1²² ||al| log
1x
ōp
x 1 + 217 (Ux. vml!)
md
+ 17 ||all log
||
6p
(8 (8vcheep)
+ 2n (ox. Vex!)
mdd 82
vi.p 2n
22 k.p
+ 0 p² (
v2 d)
|alli log
||
112211
((I- 04 07 17)
+ o 0 (1V 12 (2 |alll log
md 832
kk.p -27
|
Finally, write Veg / VL + Hy, use our previous formula from Lemma B.1 for the tangent term of V.,, and we obtain
k.p (1+ 1) = 122p + 2 k.p
200 21
2i-2 2 kpp
Σ
aq
kig
1=1
4=1
2n
Σ
200
Σ
|| (ūx, 01) 01) ((I ox or ep)
)
i=1
litk
((I
H&, ep)
o 007 V 22 pl |all log
md
2
||
6p
For notational convenience, we will define the quantity A == min(8e. 8,).
D.2 Convergence Guarantees
In this subsection, we show under Induction Hypothesis C.2 that for all [P.], v2 in time (1 # o(1)
p.r(p) reaches 1
D.2.1 Tangent Dynamics
We begin by tracking the growth of the signal term 72 p.m(p)'
for p [P.]. Our goal is to prove the
following lemma.
Lemma D.2 (Directional Convergence). Let p [P.]. Inductively assume Induction Hypothesis
C.2, and that the conditions on Lemma C.3 hold. Let the target accuracy ED satisfy Ep z 23 C:
a 21/2 e/
V mo v. [|alli 50 the dimension d satisfy
Omnnns
C2PC4
2 22 d2
log
04
50

---

the learning rate satisfy
O2 ||alli20 62
min(d st..3188) (8))
7 C Clog(5121/A) log
md ór.5
for sufficiently large constant C. Then, with probability 1 mmax - Oz log log d. we have
A/255
22 (()(p)(1) S Vd
Vt S
41(1 ((xp))
pxxlpppppppp)))))) (0)
22122
p.x(p)
1/8
F2 p.x(p) (x)(p) (0) 1-Epp ED. 41(1 - x) p.al p.a(p)
1 Tmax-
(0)
The proof of Lemma D.2 is split into stages based on the size of 12 when 22 is small. The update is given by the following: p..(p)
p.a(p)' We first consider the case
Lemma D.3. Assume that Induction Hypothesis C.2 holds, and moreover that F2 p.x(p) S 66 for some
C. 102
5g Let ōr
Then, under the same conditions Lemma C.3, we have
52 p,>(p) (1 1) = =2 ppx(p)) (1) + 410 p.z(p) (t) Z(1 + 1) + E(1+ 1),
where BIZ(1+ Fi] $ 272 ||al| 22 p,m(p)' and with probability 1 Öz.g.
md
Ig(1 + 1)1 & フ² v v2 p.z(p) d) ||all log
+ +nrr x(p) (p)) p.x(p)
òp.g
Proof. This follows directly from Lemma C.3 and Lemma D.I.
This motivates the following stochastic induction helper lemma, with proof deferred to Appendix D.5 Lemma D.4. Let (X.), satisfy
X X, ax/ + Er+1 Ze+1. Xo xo.
where (E:); is an adapted process and (Z,), a martingale difference sequence. Define the processes (xt)r, (x,)) by
x/-1 + (x77) (xx))
xt. = = (1+8)x0
x,41 [ (x, 1-1
x7,
xō (1 - E)XO-
Suppose that when X, x77] we have LEtIl X/E1 + X, + E3 with probability 1 ōp.g, and
E[Z Fil S 2, Then, if
E6026p
8 S
EXO
B2
E₁ S
8X0
and o3 S
6 6-T-1 S
6 EIT &
6T
4 4--11 &1
T-1
have X, xx] all with probability 1 -T 8z.
We can use this lemma to bound the time it takes for 82 p.x(p) to reach some w(1/d) quantity. Lemma D.5 (Weak Recovery). Assume that the learning rate satisfies
1 ax(m)02 ||al]] A2óp
log(5121/A) logo
md 62.5
Moreover, assume that the conditions of Lemma C.3 hold for 6, 11112 S7 large constant C, and also that
Et for sufficiently
3²
CC
22 d2
log
04
51

---

Define T* by
1 1/256
T :1 (1-2//66),,, 41(1 1) 621 (0) p.x(p)
Then with probability - -2, - 6p.
sup v2 1sT pp)(p) (1) S Vd
and (2/A) v2 (0) s 12 p.x(p) (T*).
Proof. We will apply Lemma D.4 to the process with X, = 22 By Lemma D.23, the process (x²), satisfies
p.x(p) (1), a = 410 410 z(pp)) == A
2567
(1+ p.x(p) (0)
p.aip) 5 (1-41( 41(1 - 1)0 (1+)) - (0)
.) F
Therefore for
1-
1 1 7* <
41(1 - 1003, 121 (0)
p.x(p)
we have
(1 - 1)ar (16)) 1-1
(86)
== 41(1 - 1)02) (1 (1 1122--
p.zip) (0) -
s (1+ I8)
s exp(-E)
8/2.
Altogether, can upper bound f7
x S (1+8) (. (0)
S 48 1p2 p.a(p) (0) S Vd
(8/2)
as long as d log" d
2 22- As such, if X, S x at time r, then the update in Lemma D.3 holds
for 1/vd. This update is indeed of the form (8); we must now verify that the conditions on oz E,, E2, E3 indeed hold. Recall that
1- (I- 1)a (x))=-1 T 8/2 22222= 5121
A
We therefore have that
T
x
dt
+
0
1 arl (1 1) (xx) 1)
log T
1=2
1 1- (1 - al1 a1) -
+
/ 1>2 2
(1
a log( (512/AA
1=2
(1- 2) laa (x
I>2
and
T-1
T
(17))
Σ
(x+) 1 o
dt
1-1 Fr
1- a- - 1) (xx)
52

---

x/a=1
(1- (2τ) 1-1 /- (55)-111 7)
S x -1 (E/2)- 1.
The condition on o2 is
2
2 6p
16622 ópar. log((121/A) v(1-2)
1
4 E
Since o2 $ 172 [|al]; this is satisfied if we take
ax(p) d
||al|; A²
11 s
l0g(5121/A)
Next, observe that 3 $ ör nax(p) 16
We observe that
EXO
81
A na nax Ei.
E X1
and thus the condition E is satisfied since 87 CT for sufficiently large constant C. Next, see that E = nf ||al]? logê
0 ) and thus we require
md
At x a = B s
EXO
E2 S
ΣΣ E &2
log(5121/A)
md
Ad Ad- na nax(p)
- ||ll? log
log(5121/A)
ax(p) 22
||al1|2
log(5121/A) log2
0z.e
which is indeed satisfied from our choice of n, Finally, we see that 3; 12 thus we require
||all
md and log
Ōz.6
E3 S
EX0
= 1? |all; log
md
$ A(I - 1)02max<())l
6T
ōr.g
= ax(p)
1)0 d' ||a||]2 A
1og
md Dr.c
which is again satisfied by choice of 1,. Therefore the conditions of Lemma D.4 are satisfied, and so with probability 1-7',,, ôp we have X, E xx,,x, for all r s T*.
We conclude by lower bounding x7 By Lemma D.24,
X
x, 2
1- 1 ()p(--)))p((a1)) (x0) 1-1 1-11)/)
Plugging in a = =4002 na x(pp) S E, we see that
1-1
No
a(I - 1) exp(-at)
exp(-a/)
2 exp(-a/)(1 =)¹ 2 - -21,
Xo
53

---

and therefore
x (1- (1-6)x0 (21e) 1-1
exp(-A/(128)) (A/128) /4
2 xo
2 (64/A))-ix)
as desired.
Next, we bound the time that ;2 ppx(p) with proof deferred to Appendix D.5. Lemma D.6. Let (Xz), satisfy
(1) grows to 1/3. We first introduce the following helper lemma,
X Xt ax; + Erel Ze+1, Xo xo-
where (Et), is an adapted process and (Z,), is martingale difference sequence. Define the process by
R+1 = (1 ) 20 =
Suppose that when & s X, S ō, we have |E+1l E with probability 1 ô7,e and B[ Fil s o2
Then if
X6O=
E
47 and 02
16T
we with probability 1 T6 6p either have X, & for all T. or sup X, 6.
The following lemma bounds the time it takes for pp,x(p)(t) to grow slightly.
Lemma D.7 (Intermediate growth), Let ô > 1. Assume that for some Told, 82 p. (T 2 6/d.
Assume that the learning rate n satisfies
ax 1)03, ||al| 82
log
md 85.e
Moreover, assume that Induction Hypothesis C.2 and the same conditions as Lemma C.3 hold. Then, with probability 1 - O-, 6p, there exists some 1
d'1
21(1 ((1-1)), 6T- =: T such that
p.xlp) (Toia + r) min 1'' 1
22
d
ppx(p) (To/d + 1), so that Xo 5/d xo. For notational convenience, let us define 8 = min(6'/d, }). Let T be the last time at which & s ō. For T, if X, S ō, then by
Proof. Define X, v2
Lemma C.2 and Lemma D.I, we have
22
p.x(p) (t 1) 2 22 p.x(p) (1) + x 22
p.x(p) (1) Z(t +(( (1+ 1),
where B[Z(1+ J.] $ ónp ||als and Ig(++ 1)1 $ n" do ||a loge
md Ōz.c
We would like apply
Lemma D.6 with a = 2na x x(p) 10 By Lemma D.24.
8 82 Kr 2
(1-a - exp( (
and thus
T exp(el)
d'
a(1 11)8/11
21(1 1)0 na 61-1
54

---

166z
We next verify the conditions of the lemma. We first require o2 - 167 or equivalently
6'6p d²T
n² [|alli 8
6 s d (1+1) 8 ||a|| 2 6p 1(1 1) 21
= 8 1-1/6 d (+1) g/+ ||a|i 0p 1(1 - 6 2 x(pp))
1 $ a ax(p) 111 1) 6
We additionally require = 47
Plugging in E, x0, T, it suffices take
md
n d |alli 8 log
< 6 d 1(1 1(1-1)00
= ax(p) (1 1)0 d ||ll]
logo
md 62,5
where we have used the fact that 8 s 6' /d. have X, 2, for all s T. But this implies that we actually must have X, for some / 1 T, as desired.
Therefore by Lemma D.6, with high probability we
Putting everything together, we can now bound the total time takes for 22 p.x(p) (1) reach 1/3. Lemma D.8. Assume that the conditions of Lemma D.5 hold. Then, with high probability, there exists some s T (I1-1)02,1xxp 22r-2 (0) such that 12 ppa(p) (1) 2 $.
1+4/16
Proof. On the event that Lemma D.5 holds, at time T+, we have the bound
v2 p.x(p) (T*) (64/2) p. (0) óo/d,
for d6 = (64 dv2
(0). By Lemma D.7, with probability 1 1 1-Tzôv.e or, v2 p.a(p) (t) grows dt-1
p.x(p)
to a value of 6 /d in time S
111-1)0=,00x011 . Repeatedly applying this lemma for at most
log log d iterations we get that v2 (,x(p) (1) grows to be at least in time
d'11
d'
(1-1)=
k=0
21(1 - 1)0 nax (1-1)
21(1 1)0²
21 na (p))
d=11
1(1 - 1) 1(1-1)02 2) nax))
A/64
I(I I(I- ((-1))0 x((p))
1 (0)
p.r(p)
A/16
41(1 1) 1ax
221-2
(0)
p.x(p)
with total failure probability at most T g + 6g log log d.
Finally, we can lower bound the time it takes for D2 following is deferred to Appendix D.5.
p.x(p) to grow from to -ED- The proof of the
Lemma D.9. Let (Xx), 0 satisfy
X1+1 I (1 - a)), + E++1 + 24+1, Xo = X
where (Er), is an adapted process and (Z,), , is martingale difference sequence, and with probability I ōg.g we have lE++1l I E and Z F.] s oz when X, S 1.5xg. Then, if
2adr
E
16
we have with probability T5 6p.
X, (1 a) xo + 8/2 1.5x0
for all T.
55

---

Lemma D.10 (Strong Recovery), Let assume that Lemma D.8 holds, ie for some time 11/3. v2
(p.((p) (T133) 2 3. Let the target accuracy eD satisfy the same condition in Lemma C.5. Choose 17 so that
ax(p)
||ali on
min(d min eD))
n
log
md 03.E
Then with probability 1 1-T82.6 -p, have
F2 (x (1) 1 EDE.
V 1 2 ((pp)
log(2/Ep) SIST.
Proof. By Lemma D.I and Lemma C.5, when p2 p.n(p) we have
22 p.x(p) ( 1) 2 p p.x(p) (1) + 10 10 mxpp p.m(p) (1)) + Ertl + Ze41
where
md
151l n ||lll log
B[Z
Frl ||all;-
62.5
We would like to apply Lemma D.9, with 3- 10 ((pp)) and X, 1 - p.t(p) & We first require E s 4. which satisfied by taking
md
n [|all d log
$ 3
a ax(p)
1 3
||al|
21
loge
md
&
Next, we require o2 EE'0dp/16, which obtained by taking
n/² ||all $ e²3 100 Oz = S (x 3- 2
E20p.
Altogether, with high probability,
22 p.mlp) (Ti/2 +1) s (1 a)' 2 - 2 s
for 2 a log(2/8) naxin log(2/E).
Proof of Theorem D.2. This follows directly from combining Lemma D.5, Lemma D.8, and Lemma D.10, and noting that
3
1/16
162 maxp)
4I(1 1)0 na p.x(p) (0)
2112
D.2.2 Radial Dynamies
In this subsection, we analyze the dynamics of ||op12 when 82 update on the norm is given by the following.
p.x(p) 2 1 E. In this regime, the
Lemma D.11. Assume that x2 pp)(p)) (1) 2 - Then
||o (r + DI[2 = (1) + 4n (r)ll (ax
Zi+1 + Ei+1
where with probability - 5τ,5
B Fil s n² ||all ||p(())|''
1E+11 s (n2d [|all log log (mdl/r.e) + 2 ||all| 221 + mo?)) (1)p
56

---

Proof. This follows directly from Lemma C.7 and Lemma D.I.
We would like to prove that Inductive Hypothessi D.1(b) holds, assuming that D.1(a) holds. This is given by the following result.
Lemma D.12. Assume that Inductive Hypothesis C.2 and Inductive Hypothesis D.1(a) hold. Let 1+4/8
Ti- 41(1-1)0 i, naxipi 22-2
be some time at which 52 p.a(p) 2 1 - E. Let the learning rate nf and p.aip) (0)
target accuracy ER satisfy
|all
amin, d' d ER :RROP
log(2ax/ min
ER 2 log(2az/oz)
(Crux()) (C
+ ||all 2 e/ mo?)
log@(md/dp.) (md/ôp.e)
Then, with probability
- -Tmaxxp,t Öp,
[1]p - -ax SER:
A/8
Ti-s+ - 100 221-2
S Ti-8 + Tmax-
p.x(p) (0) (0)
To prove this lemma, we first lower bound the time it takes for [1]] to reach da xpp) for some small quantity őap. We start by proving the following helper lemma, which resembles Lemma F.6 from [RL24] and whose proof is deferred to Appendix D.5.
Lemma D.13. Let (X,), satisfy
Xes1 = (1 + a)X, + E Zee1. Xo x 0.
where (Et), an adapted process and (44) is martingale difference sequence. Define x; = (I+a)'xg Xo- Suppose that if X, 0.55),, then |Er+1 S x,3 with probability Öō,E and B[Z [Fl S x7 Then, if
69 of
E
47
16T
then have with probability 1 Töp 82 that
0.5)x, for all s S.
The following lemma then lower bounds the escape time.
Lemma D.14. Let 8= /or for sufficiently large constant C. Define log( log(260n(p/ S 41)0((r)
5-1 Let the learning rate satisfy $ "sipid "alll"""[all"" 8,8 With probability ōr Tôp, we
ACqurtr)
log (md) de,s)
have sup,er (T)p +D] Sax(p).
Proof.
When (t)l s (p)) bound
110p(1+ 1)[2 = =11b 4nax(p) [1]](0)] Z4+1 E1t1,
where
Kenl $ npaz(m) ||, BiZZ,1 Fil $ ||a|| (o)l".
provided that
8 2 ami
(nd ||lll log log@@ (md/ōr. CZamp)) & ||all; 221 e/ + moi)
"min, "min,d 1 ||al1 8-1 (-1( ||a|| 22d s/ + mo?) $
m (md/mm/6pp))
Define the process X, = 11 (T + r)]f where xn = || (T) and a 4na (p))- Assume that sup, X, < <dxx(p). We can thus apply Lemma D.13, since the conditions on o3, 3\t are indeed met:
6p
0 s
=
< ax(m) ||a|| 6pp
16T
C
4T
But recall that for the process = (1 a') for T = a log(26a we have xy 25 and thus X7 > S(p(p)> a contradiction. Therefore there exists $ such that X, 2 da (p)) as desired.
57

---

We next introduce the following helper lemma, with proof deferred to Appendix D.5. Lemma D.15. Let (X1), satisfy
X,+1 (1-a(x))) + E1tl + 74+1-
where (Et), is an adapted process and (Z,), is martingale difference sequence, and with probability 1 ô2.E we have at (X,) E [a_,a+], 15r+1| s E and B[Z;,1 197l $ oz when X E [-e/2, E e/2).
Then, if for some (0.x0)
E'a_ 0 S
ES
we have with probability 1 -- 6y that
(1 (1-a,)' xn 8 / s X, $ (1 a a-)xxx +8/2
for all ST. T.
The following lemma bounds the time it takes for the norm to grow from dax(k) approximately a (A)),, and furthermore establishes that it stays close to a (x(k) Lemma D.16. Inductively assume that Induction Hypothesis C.2 and Induction Hypothesis D. ((a) are true. Pick 5 > O, and let T be some time at which (T=)( e [ōax, ax/2]. Let &R > 0 be the target accuracy.
7 s & |aali 6z6 A ERd |alli 8
ER 2RZ (Caxip)E++1e [llll 2nd 20 + mo?)
logo (md/6r,8)
then we have with probability 1 mmxmaxx 6p that
||| [(x(p) - ERRax(p + ER] V 2 21og(ax(p)/ER) Sna
21 max.
Proof. Assume that the inductive hypothesis holds at time r. By Lemma D.11, we have that (t (r+ + 1)I (1)l + 4n (t) (azip) (1)p(())])) Z,+1 + E1+1
for B|Z 111 s 7 ||l|| [|> x 17 ||all a² xip) and
15+1 $ (nfd ||||| log @ (md/ + (C ||al| 22' e/ + mor)) ax(p)-
Therefore
= - (ax(p) -1b())/((pp()))))))) -10p()))))) Z++1 + E1+1.
ax(p) -
We thus would like apply Lemma D.15 the process = - |/0 (1 + I'Il with & ER.
We see that x E [ax(p)/2, (1 () so for X, E [-Ex/2, (1 (/2) we can bound
(am(p)
s [1]] s (a)
2 Therefore the conditions of Lemma D.15 are indeed satisfied. thus suffices to take nn2 || log (md/6p.e) + + ( ||alli 22d E/ + mor)) an(p) $ noaxip)eR
80
= s ERd || loge (md)
eR 8-1 C Caarmpt ||all1 22d of + +mo?)
as well
&Qa
2 s
= ||all? xx())) $ E
16
= 2x ||all opp
ax(p)
Altogether, by Lemma D.15 with high probability we have
(1 - ar.))a x ER/2 < X, s (1 a
Naively, we have the bound X, 2 -2 which implies ||0) ax(p) + t Moreover, for
2l) 2 a- (og(2xo/ER)) we have X, S ER-
1 2 O(jx(pp
58

---

Putting everything together, we can prove Lemma D.12.
Proof of Lemma D. We apply Lemma D.14 and Lemma D.16 with (log(22x/66)) The
conditions on & are indeed satisfied, and moreover [|))())] reaches the interval [ax(p) ER, (x(p) ER] within time of
log( ( (lg((x(p)\ER) log(ax(p)/00g) 2C 1og(2ar(p)/ log(ax/ER) x(px((p
((p)(p)
(p))
A/8
2212 41(1 1) ((p
(0) p.x(p)
D.3 Maintaining the Induction Hypotheses
D.3.1 Upper Bounds on the Irrelevant Coordinates
We first track the growth of failed coordinate Vk,a(q) for (4)) & (p. The update on (k) (1) is given by the following.
Lemma D.17. Assume that Induction Hypothesis C.2 holds at time Then
(g) (1 1) s v2 xxxtg) (1) + m10 21 (a - 1(q E [m].q E L) ||/l1 + +((1+ + 1) +E(++ 1),
where B[Z(I+]] 1) Fi $ フ²
||all x2 [,)( (1), and
IE(1+ + 1)1 $ (1 2 (xx(q) (1) ||all logo (md/52,e) + C Ca 22 k. eD + 1/ ())
where
8eroo 1231+6 (anig) 2/ mo? ||all; o))
Proof. From the proof of Lemma C.10, we have that
-
(xx(1) & 4 (.zig) + 2C a k,x(g) 8o + Berors
di
and the desired result follows directly from combining the above with Lemma D.I.
We will next require the following stochastic induction helper lemma, with proof deferred to Appendix D.5. Lemma D.18. Suppose that (X,), satisfies
X S X, ax! E1+1 + Zi+1, Xo S xo.
(9)
where (Er), is adapted process and (Z,), is martingale difference sequence. Let & be solution to the recurrence
841 = 8, + ax/,
io = (1 E)xo
Suppose that when X, &, have 16+11 s x 1/2 x,E, X/33 E with probability 1 ÖP.. and BI 1) F.] X,02 Then if
X X3E² 6g
E <
EXI
E S
EXO
E1 S
EXO
E4 S g7
EXn
and o7 5
(00
&
1/2
8 8 3
8
-T--1 2!
4 TT- &
have X, & for all s T with probability 1 - Tōp, 6p.
59

---

We can now control the growth of v2,x(q) by applying Lemma D.18 with X, = (.x(g))
(t). For
(k))(q)) pcl define the time r(q)) by
Th
k < q.q.e
T(k))
=
Ta q< [PM]
Tr.
k. p
By Assumption C.I(d), we have that
(1 A/
T(kxigg))
4I(1 - 2
Lemma D.19 (Total growth of failed coordinates). Let (k, x(q)) & ((p, pE(P.) Assume that the learning rate 17 satisfies
amin, 18 a |all] A20
[log(4/A) log (md) òp.e)
for some sufficiently large constant C. Furthermore, suppose that
ga of vmmo of 0min, amin, 02/d-111/24
d loga d ER S 1151
amin.
2 (4/A) A)
123146
Then, with probability T-,, òr.g 20p, we have that v2 k.xlg) S Eo (and hence Induction Hypothesis C.2(b) true) for all s Tr.
Proof. First, will show that v2 ( (k,r(g)) (1) does not grow too much more in the interval [((x,(())) Tp.].
(1) s 6o/2 up to time T())) Next, will show that
Part (t 2 x. Our goal will be to apply Lemma D.18 up to time T (()))()))) to the process X, = 52 (g) (1), with a = 410 ((())> & 37
A and x = max w7 22
k
We first aim to bound the quantity a(l 1). We begin by considering the upper triangular entries, ie those where k < and [P*], in which case T(k,((9)) TR. We have that
1-1
1+A/4
a(I - 1)x 41(1 manig) (1++)*=1
22
max
2d
41(I 1)0 na 22 22 (0)
1-1 2d
221-2
an(g) max
k
s (1++))
a (1))
221-2
(kT(k)
(0)
By the bound on the row gap in Assumption Ca) have that 4xig) Runte)
Moreover, by the
Tiy (0) T4x
definition of the greedy maximum selection process along with Assumption C. (x)) ax(g) maxj>k
( k.a(k)
2/12 (0) 2
221-2 (0) 2 ax(g)/d -1, and thus ).x(g)
Gaigi -/((2))--
s पा ामズ Altogether,
axui) x.x())
(0)
a(l- () (1+ exp(A/2)
s 51 1/4.
1+A
1+A
A and A - 1/2. since & 47
Next, consider the lower triangular entries, with < k, E [P*]. We have that ((k.)(g)) = Tg. and thus
1-1
max 1 62
k, (0)
a(1 - (T
221-2 (0)
q.mlg)
60

---

L.nie (0)
By the bound on the column gap in Assumption C.1(b), have
Moreover, by
727-1
(.
(0)
TTx-
Assumption C.I(d), we have
1/12d)
$
1
Therefore atl - 11 s
(46)41(144444) S
(.0 (0)
1+Λ
1+A
1 A/4 as well.
Finally, we consider the lower right block, with k. P., in which case T(k,p) Tp. We see that
a(I - (T= ax(ạ) max( 27 (g)( (0))
F2
ax(P.) P.. (P.)( (0)
121-2 (0)
By the bound on the threshold gap in C.I(c), have definition of the greedy maximum selection process along with Assumption C.I(d), we have that
Moreover, by the
P (0)
1
(x(P,) 52 (P.)((,)) (0) 2 (x())) pa 22 j.z(a) (0) 2 a "x(g)/d, and thus "sta) -1/(2d)-1 S Z S T+A Altogether, alI 1),8/ 'T (I+z) (1=2))11((AAA4))
OntP.) P......) (0)
A/4.
1+d
In all cases, we have a - 1)x1//11 T S 1 - A/4. Thus by Lemma D.23, we can bound iy by
fT s
20
S So(A//4 + s d 1 =: 60/2.
(1-0(1- - 1) 1) +
provided that
log byd 2 (4/
Therefore by Lemma D.17, the update for v2 xx (1) is
22 K. (1+ 1) s 12 k, (1) 410 a(
F2 k,z(q) + Z(r+ 1) + g(t+ 1),
which is indeed of the form (9) for of x
Iaal and Ei $ n 3z
5
r [|a]] (md/ e) 33 $ Ca E $ o² ||lli logg (m)
Next, we verify that the conditions on E, 02. in (10) hold. We first bound the quantity ΣT- 8,
T-1
T
Σ 7=0
XO
S
dt (1 1-a(( - 1) (5o) 1-1 (80) 1)
0
log
1
1=2
1-a807
1 1 (1-a(( 1)
1> 2
(1-2) ((n) 1
a 1 log (4/A)
1=2
2)- a -122-1 1>2
Therefore
Σ 2 $ a -1 122-1 ( Iog(4/)))
(II)
Next, we can bound the quantity
Σ/= 21/2
T-1
T
2!/2
Σ
21/2
di
(1-a(1 1) (zo))-1 20-11
1=
22
1 11 - aaI - 1).86 -T) #
a(21 - 3)86-1
$ 1T
61

---

Finally, we can bound the quantity 2/=0 8/
T-1
8
Σ 8
dt
(1- a(l 1))
1w
= a
(1-a(1- - ()) T-
$ Naaa (AA/4)-11.
Let us consider the oz condition. Plugging in (11), it suffices to take
2 - x oza =/6²6p 410 log(4/A)
log(4/A)
Plugging in oz $ x [|a]]; and noting xo 2 2d this is satisfied if we take
amin, 02 d A2 |aali 6z
17
1log(4/A)
Next, for the E constraint, we require
ENO
6X0
E S
nerroe $
8 8/ 1122
TX
c/2
= noereer & amin, 32 Ax-
Senor anin, & 1
For E2, plugging in (11) require
exp-aa a
EX _ 10, 1a
3 = 8 llg((4/A)
2 llg(44/A)
EX/ 10 nax(()
r ||all log (md (p.e))
2 (lg(4/AA)
amin, 2 ||a/1 A log(4/A) log (mdl62.g)
11
For E3, we require
EXO
Ca (A/
3
ET-1 ./
= C Ca $ A 1- 1 02 (((a)
80 C A
which is indeed true since 60 1/2 C-2 oz
Finally, for E4, we require
E
6N0
- n² ||lll log (nd//pp.e) < Ad mimn. (1 1) d- (1-1)
8T
amin, (1 1)0 ||a||=2A
log (md/ōr.e)
Therefore the conditions of Lemma D.18 are satisfied, and so with probability 1 Tō 82 have X, $ & S 60/2 for all f T.
Part (T(k, $15 Tp.) We now show that v2 (.rig) doesn't increase too much in the time interval (T(k,a(g)), Tp.]. The case where k. q P. is trivially true.
62

---

Consider the case when < k.q E [P.], so that T= TT. By Induction Hypothesis D.I(b), when
I 2 Tg. we have that (1)p = a (x()) = ER. When 12 "k (1) I 60. we have that
1 xx)) (1 1) s 22 (g) (1) 410 21 k.mig) + + + +((++ 1),
21
where B[Z([+ 1) Fi] $ xf ||a|i 2 x. (1), and
[g(1 + 1)1 $ n ||a|l End log (md/6p.e) e + (g /+1
1760 1/2 6 Seroor-
We would like apply Lemma D.18 to the process X, F2 ( Tq) up time Tr, with
-10 0.5. We see that Xo $ 2 Xo. and so setting &n 1.5xo, we have that
d=
1 S Tp. 1 21(1 1) 27
and thus as long as ER $
6-1.5----0--1 we have
Gnins
a(I 1)50 5..
1.5 E0
1-1 d'-''Ra'aa
mxamin
= 1.5 ((
gRa 1/4 s (3/4)'-1
80
1.5x0
8 S
S 2xo = ED
| a (1-
(1-a(I-1)8)))
1)
FT
next verify that the conditions of Lemma D.18 hold. We first require
E
16T
n i and log lowggmmm////a (md/ōp,e) + Cynna + n1t 2 Serror $ I(I 2/ d' (1-1) 80
17 amin, d d - 1) ||ali of
< I(I 1)6 d (1-1)
log2 (md) ōv.g)
amin, [(I 1)022 1/2
and 8errur
d'-1
Clearly the condition on y is satisfied. Next, plugging 60 d1-r),,, we require
> [(11 1)0 mmin.
Finally, the condition on Serror is indeed satisfied, since we already have Additionally, since we can bound Σ/ &, - TEo, we require
Senrr amin, 1(1 1)02, -/11/2 amin, |(I 1)0 d- 1/2
o2 s
= n² ||all? Egdp!(1 1)0 d (I-1)
Teo
1 S amin, End (1- (1-1) 1)0 ||a|]]2 2 Sp.
which is again satisfied by our choice of Altogether, we have X, s & s 8o for all / s Tp. Finally, consider the case when k. [P.]. so that =T. By Induction Hypothesis D.1 when 2 Tg. we have that (R))()) (1) 2 1 1-E. E, and thus 82 k. (1) s E z Ep, as desired.
D.3.2 Upper Bounds on the Norm Growth
We start with an upper bound on the norm of the unused neurons, i.e., Ok with P.. Lemma D.20 (Bound on the unused neurons). Inductively assume that Induction Hypothesis C.2(b) true. Suppose that choose
17 amin, d [aa))1)||all22000 1|al1-20r
log (Tmd/52)
Then, for any E [m] with & P., with probability at least 6p we have || s 0(0)) < oo throughout training.
63

---

Proof. By the proof of Lemma C.14 along with Lemma D.I, we have
[ 1)Il v + 4ney ||]|]] ||v 21 (vx, Hx(l+ 1)) fx.
The total running time of SGD is T
4111 41(1- 11
144/4
12-2 ((o()))) (0)
$
41(1- Omin,
d'-1
Therefore
5/ [|al||1 d
d- ||ll| 1,
4mgg |all] T
1(I 1)0 20 amin.
1(I 1) 2 amin.
|all
Thus (1 + 4n (|all1) / x In addition, by Lemma B.1, we have
since 2
1(1-1)0 Uein.
Var (2n llvel (ox, Hx (1+ + 1))) & n ||all Io
Hence, using the language of Lemma F.6 of [RI.24), have
2 no [all)).
02 = 0
nn
||lll og)
Tmd óp
d
n'd
|alli log
o
T=
41(1 1) 21 mmin.
To satisfy the condition of that lemma, it suffices to choose
2 x ad2o
17 6 ||all-10
ES T T
n amin, d 1(I 1(0-)) ||ll|
logê (Tmd/öp)
Then, we consider p S P.. Unlike those unused neurons, since vp will eventually converge to Cx(p), its norm cannot stay small. Our strategy here will be coupling its norm growth with the tangent movement, We will use the following extension to Lemma F.1 [RL24]. The proof of this lemma can be found in Section D.5.
Lemma D.21. Suppose that (X₂); satisfies
X = X, + (X,) + Er.l Z,+1, Xo xo=xa xo > O,
where a, R. R20 is F-measurable non-decreasing function, (E,), an adapted process, and (Z,), is martingale difference sequence. Let & > 0 be given and define the process
X = (x,)) Xo +xx00
Fix T' 0, 6G E (0. 1). Suppose that there exists E, oz 0 and o2,5 100,1 such that when X, &,, we have |Er.1 with probability at least ō2,6, and B[Z+,1 Fil s oz. Then, if
E s (27) and 02 s 62 (27)
have X, 8, for all T.
The following lemma verifies Induction Hypothesis C.2(a) for σi (loop-Cii) for some constant
Lemma D.22 (Bound on ||,,|]>. Suppose that d (T(- Amin ) and n $
||a||
Gnin. I(1-1) 10-1)33,-
Then there exists constant Cosp such that | S O (0 -Co) as p.m(p) has not reached 1 1-
log (mddmmd/))) (x.4)
long 52
Proof. By the proof of Lemma C.15, when Induction Hypothesis C.2(b) holds we have
1p (1 + 1)I2 s ||>pll 4n((xx()) v2l p.x(p) + ||al] a ||,, Zpp.(( + 1) + Ep. 1),
64

---

where, by Lemma B.1 and Lemma D.I, the conditional variance of Zp.x is bounded by
o (
Ilalli ||pp!")))))))))))""))) and we have
mdd Öp
(1+ + 1)1 & ofd [|al] log
||ppIl with probability at least óp.
First, consider the situation where 82 O Under this induction hypothesis, using the language of Lemma D.21 with & 0.5,, we have Hence, to meet the condition of Lemma D.21, it suffices to choose
(px(p) $ 0.9. We prove by stochastic induction that ||0/1| s
= |alli [all)
== pf [|all log
md Öf o
T= 0
d'1
I(I 1)0 23 amin. 1)
0 x
=
17 S amin, d d- 1(1--) 1)0 ||al| 1 8p,
T
S To
n amin, d 1-1111) ((1- 1)0 ||al|
=
T
2 log
md
When these hold, then we have with probability at least 1- ((p) that 110p (t)l (15) for any S T, where N2 is defined via
N² + 1) = (2) + 4n (axm)) 22 p.x(p) (1) |lall; sb) N2(1). N²((0) = 1.5 (l)
Now, we analyze the process N2, First, note that
[-]
N² & (0)
(1 + 4n (x<p)) D. (s)( + ||all e6))
s 1.50 exp (nT ||al| s/) exp 4njnce) Σ 22 (s))
s=0
First, we see that
d' ||al|| ef
d |alli << 1,
TnT ||al| 5/ 1(1- - 1)0 (11-1)0aammin anin.
- 1(1-1)03 amin,
since d >
[all)
T(T ((1-1)05)mmm.
Next, By the proof of Lemma D.7, when 52 (p)(p) 0.9, we have
2 p.m(p) (t + 1) 2 s² p.xlp) (1) + 2na 2n
22 p.mlp) (r) Z++1 + Er+1,
where with probability 1 - - Z++1 satisfies B|Z22 Fil $ n72 ||a||:- Therefore
have |e.+l 2d ||al| log (md/ö ().d/ and the martingale term
$2
p.x(p) ( (1+ 2 22
p.n(p) (0) 2na (p) 2
Σ
221 p.x(p) (s) + Σ
Extl + Σ Z,+1
==0
s=0
>=0
We first have
Σ Exel $ Tni
[|al| log (
Since n/ 0( T(I- 1(1-1) we thus have [N Ex+1l whenever n $
d11
Gmin. 11-
log (ind/
Next, by Doob's submartingale inequality, we have
d' ||ll
P sup
Σ Zg 2
$ T
||all $ n I(I 1)0 Amn.
65

---

and thus if & Cmnn:(ll-Jo,,llllj 1lallا we have that sup,sı 22% Zs| s with probability óp. Altogether, on these events we have that
di-i
nax(p)
xaxip)10 10
22 (s)
s.5
s=0
As result,
(²) 1.50g exp 4n/ ||a|| o/) exp
0
1
In other words, have ||pl1l o when v2 p.t(p) $ 0.9.
Now, consider the situation where v2 p.)(() [0.9, 6-.. By the proof of Lemma D.10, it takes at most To gaxip)
(2/88/8) iterations for p2 p,*(p) to grow from 0.9 to - E. In this stage, we have
pp 1)Il
||pl| 4. x()ma((p)) ||0/|| p. + (1 1).
Let the corresponding deterministic process be M 22 1) 4. M2dmp) M² with (T)) O(og)) where To the time 22 p,x(p)) reaches 0.9. Using the language of Lemma F.6 of [RL224), we have
a = 4.1 = = of).
== (
I'llaal log
md óp
0
Therefore, to meet the condition of Lemma F.6 of [RL24], it suffices to require
ax(p) 10 ||a||
E =
d3 log
md log(2/E)
02 ópart 2
= Ox ?
Meanwhile, we have
(T S (T) exp ((T - -T)) 4.1max(pp)) s so 30 Cap)
for Cexp
4.1.3/ 10
D.4 Proof of Theorem 2.1
Proof. First, by Lemma B.2, with probability 1 1- Assumption C. holds at initialization, with dr-
== min(ōr, 8c, 5,) = (( mP (m..
Define Tmax max p (r. (.. $ T(T T(- 1)0 namin. We will show that, with probability 16./2 that Induction Hypotheses C.2 and D.1 hold for all r Tmax with choice of parameters
d-1
We do so by union bounding over the consequence of the following lemmas:
(Directional convergence) Lemma D.2 for all p E [P.], with op = I6P, log logd 87,
6
This implies the first half of part (b).
167m,.
(Convergence norm) Lemma D.12 for all E [P.), with óy TOP.
of ōg.E 167 P.
This
implies the second half of part (b).
(Bound on the failed coordinates) Lemma D.19 for all (k.z(g)) & ((p. pE(P)) & This verifies that Induction Hypothesis C.2(b) holds
with 6p TomP Ōo.E To7 To
throughout training.
&
(Bound on unused neurons) Lemma D.20 for [m] [P.]] with 6x part (a).
This implies
16m
66

---

(Upper bound on norm growth) Lemma D.22 for all p e [P.]. with 6p 167. part (c).
oz This implies
Next, we verify that our choice of ED, cr. indeed satisfy the conditions of the lemmas. First, Lemma D.2 requires the conditions on C.3 to hold. Recall that we have chosen ōn CT sufficiently large constant C, and we will select 1. We thus require 37.
A² for
8r10 = d 2
C 1 A
d d
1/2 s
2 P
C₂
log
2 amin.
x mo?
12231 d2d1-112
123
11+2y(1-1)
02 U2i.min A
-
d
1221 C2 ||a||]
8 23 C2
) E d2 (1-))
2
moi
||all|
ED
2
amin.
v
amin,
50]
mo?
214 Calllll -110))1111111)) 8yp
0 Smins ED
231.731 Cr
ax(p) ||al|]20, 6p
min (2
S
Clog(5121/A) logo (md
Next, Lemma D.12 requires
|all| 2
amin, amin. 8 ER
" $ log(2ax/o)) min
(mg@(md/82.e)
ER (g((2 (00(2a//0)) /0/) (C2 G 5+ ||all 2 e/ moi)
Next, Lemma D.19 requires the conditions on Lemma C.9 and Lemma C.10 to hold, which are
231-73'C² C2
|all|
C12231+1 C |all
ED 2
ER 2 12 [|a]] 22 21--111111
A
02
amin, d(1-y)
0 amin, d1/2-yT'
22 ain.
A2
mo?
3-1ED
2
11221-122 1/2
12"
())(1)))-)))))))
ER 12C2az(p)
d1+2y(1-1) A
2314731
22
C12234442
and
A
62 amin,
A
S mo?
23 24
d1+2y(1-))
23, 2(log d) 2 24'
d (log² d)
d
02
Amin.
1/2-7
A
S
1-1 (log² d) 1/2xz
231+4 2
||l|
221-2 24
C12
240
Moreover D.19 additionally requires
Gnin, F2
E
gl/28/-1v Divvvmo mof v ||all: of amin. 2 d2 -+1122
C2
anin. & 103/2A
mo?
12
12
Omin, 02,
1
d
N
125t-6
67

---

Amin.
ER 5 1.51 dv
d
2 2 (4/A)
1o d
Finally, Lemma D.22 requires
||al|
d >
0 amin.
Amin, 1(I - 1) 1) ||a|l
5
log(mdd/óp
0 00 Cap.
Assume that log" d
2 2d (4/2) A Then by choosing y to the solution to
d
= 7T-15
loga17
we know that y s 47 The constraints d then become:
Zo A log" dA-2 v (Ilall, A 2-3amin, ) (d) (Iaall, A A- aminn.
d Zo ||all; A a
log"d st
The conditions on the target accuracies ER. ED become
Zo ||ll| amin. d'
||a||
8R Zo d'-1/4
amin.
amin. A 2( d
ER So dr(1-1)
Next, the constraints become (substituting d² log² d(4/A)/T))
So where we note we must also have E 2 En. We can therefore choose Ep, and observe that the conditions become
A
o (1-)
2
8R
d log 411-1)
10g4(111)
log( 1/o2))
6
||a|||
dlog 41-11) 41--1 Zo ED Zo
amin, d1-1/4
a Amin,
Zo ER Zo ED log((//o0)) v
||a||
log 21-
d111/4
The condition on mo? becomes
mot So d1-1/2 amin, Ep log(1/o2) d 1/2 d'
anin, 2
ER
amin. A
We additionally require of Sor 0f Therefore it suffices pick oo d c o C where C > C' > O are sufficiently large constants depending only on I.O.
Next, we choose the learning rate n7. suffices to set as
amin. ||a|| m p p-1 5%
min ain(Add-'_6
17 S
log(512//A) log md
02.4
68

---

Finally, we prove part (d), and bound the population loss L at time r. Recall that L = Eiz1 Lz.Li. Li where
m ap 1 11
m Σ
Li == 2
||all
v2
|xxl ||r! (Øx, B1)2
p=1 k=1
Recall that : (p E [P] : : 2 o1}. By parts (b) and (c), we must have L = [k.] for some
integer ko, and 52 pp)(p)
2 - for Up L. We can decompose the loss as follows:
Li L 2==51aal |aal2
Σ
Σ
ap 1 kk.
Σ kel.
2
RET. pE[P]
m >
Σ
|
||0 (ōk, 8,)
Σ
Σ
ap |1
k..p
Σ
| || |1sl1||||1 (Øk. 8,)
R.jEL.kej
PElP1
j=l
The terms with L are straightforward bound, as
Σ
Σ ap 11 112 v2,p I mor ||a]|
k pE[P1
Σ
| ||, (ūx, 7,) s 2 m
Σ
||,l1
mof ||all
2
kEL.
Next, for j L, (ōx, و1) S E. and thus
Σ
1 (ōx, 0,) s 8
Σ
|1xx1 s ||all g
R.jET.RRj
kE[m]
Finally, we track the dominant loss term. We have
||al|2 - Σ
Σ
ap ap
1xxlll
p2lp + 2 Σ
xpp+
||
2
KEL pP[P]
REL
Σ
a T(k)
Σ
a x(R) - || 112 Σ
ap v2r k,p ||0k|1
2 LEL
KEL
pep
We bound
||
Σ
ap
Spv. k.p S ||
Σ
apč' & || |alll
pFx(k)
p*x(k)
Moreover, 1 1- 221 k.p s 2iE. Altogether,
Li
2
Σ
(ax(k) - [1ox1l2) = 088),
(k)
2
kel
ket
and since Σ, 02 we have
Σ
Σ
(ax(k) - (1xx)) = 088)
f
2
xk)
2
kel.
ket.
as well. Next, if (1 A/ 4)T,,
then p & L, and thus
L2
1 d² (k)
0(0) 2
Σ 2Zpp) 1 1 (1 A/4)),
2
2 PEP.
keL.
On the other hand, if 2 (1+ 4/4)7
then p E L and (ax(p) - ||0 - ER. and thus
Σ 2 (r 2 (1+4/))),) OP.. + 8), PEP.
f
2
where the desired claim follows by additionally choosing 2x s P. P. ED.
69

---

D.5
Deferred Proofs
Proof of Lemma D.4. Assume WLOG that the bounds on X, always hold. Inductively unroll the recursion
Σ
Ps.tE + Σ
X, = XoPo.,
Ps.zZs
s=1
s=l
where ps.,
1. As such,
Po = Xo +
Σ
p-le 0,558
p-12y.
+
0,1
==1
5=1
The error term gets bounded as
Σ
E
E
Σ (
T-1 + E2
Σ
x
TE3
1=0
with high probability for all controlled by Doob's inequality,
We can bound each term by x05/6. The martingale can be
P sup rst
P Z
M
2
B[Z S M 20
Σ x7 6z.
when we take M x08/2. Altogether, we have that Po 2 Xo Xoe, and thus
X, 2 Po. E)xO = i
-a+ax,
D 2
(1,)
=x
s=1
s=l
Similarly, we have P Xr 2 No + XOE, and thus
X, Po. (1 + 6)xo I (1+ (1+ax
I (+a =
s
as desired.
Proof of Lemma D.6. Assume that the bounds on X, always hold. If susppss X, > 5 then we are done; otherwise, unroll the recursion as
XoPo.
EPs.to Ps.
PsaEss
where ps., (1+x 2 1. As such,
Po. = Xo + Σ
Pol5 +
Σ Po..Z.
s=1
s=1
The error term is bounded
Σ
P-lge
S
E
E7 4
xul
for high probability for all s T. Next, we bound the martingale term by Doob's inequality:
P
sup Pst
Σ
0.5
2 M
& M
BIZ s 2- dp,
x=1
s=1
when we take M xo/4. Altogether,
X, 2 Po,xx0/2 2 8,
as desired.
70

---

Proof of Lemma D.9. Expanding the recursion,
X, s1 (1-a) + Σ
a) 51 51-5" Σ
a Z-
s=0
5=0
We can bound the error term by and by Doob's inequality bound the martingale by
Σ
a Er-
3 (1
Σ
a)¹ 3a- 4
[-1 sup Σ (1-0)% M s M- Σ
- a)
-23 B[,7-1] M 2 5
since we take M 8/4. Therefore
Xo x (1 (1= 2 8/22.
Proof of Lemma D.13. Expanding the recursion,
= Xo+ +
Σ
(1 + St-s+ +
(1+ Z-
sa0
sa0
(1+a) = Xo + Σ (1+ E (1+
We can bound the error term by
= S X0 E(+a) E SE E (1
By Doob's inequality, we can bound the martingale term by
Σ
(1+a) Z 2 M s M 2 Σ (1+a) 25 2 - 3- s ōp.
P sup
1ST 5=0
0=0
since we chose M = xo/4. Altogether,
(1 (1+a) a)) a) X, x 0.5x0 = =1
as desired.
Proof of Lemma D.15. Define ps. = 11==1 + (xx))) Expanding the recursion,
x, = Po,
Pi-saEi-s +
Σ
P Pi-s.iZu-x.
s=0
x=0
We can bound the error term by
Σ
P Pr-s.ti
S
(1-a'' s 8/4.
s=0
5=0
By Doob's inequality, we can bound the martingale term by
P sup 1ST 0
Σ P Pr-s, Z, s
M
M
(1-a-) M 2 2 8z.
since we chose M 8/4. Therefore
X, Po, 8/2 (1- -1-a-_1xx+
X, Po. 8/2 (1 -x-) 8/2
as desired.
71

---

Proof of Lemma D.18. Assume WLOG that the bounds on X, always hold. (X,), is stochastically dominated by the process where X,+1 X, + ax; + E1+1 Ze+1. so we can WLOG track this latter process. Expanding out the recursion, we get that
Σ (5. Zz),
X, XoP
where psr [T +xx Since X, Po.s and thus
Po = Xo +
Σ
Po.55r +
Z..
==1
The error term gets bounded as
T-1
T-1
T-1
Σ
Pa.15
E
S 3
E
3
+
TE4
with high probability for all controlled by Doob's inequality:
We can bound each term by x0e/8. The martingale term can be
T-1 B[Z M 2
P
sup rst
Σ Po.
2 M
S M
R
oz.
s=1
s=1
1=0
when we take M X.e/2. Altogether, we get
X, s Po. + = Po s 81
as desired.
Proof of Lemma D.21. We may assume w.l.o.g. that the bounds on & and the conditional variance of Z++1 always hold. Define
aI
1>
(X)
1.
==s.
Note that since a, > O, we have ps., 2 1.
Then, we can unroll the recurrence relationship as
Σ
XxPo(X)
PX) +
s=l
Divide both sides with Po.., and we obtain
(x) Xo
Σ
Poll (X)ss1++
Σ
Po.l(X) (X)
sml
5m
For the second term, have
Σ (X)
Σ
16 S TE,
for all = 7' with probability at least - -ööp.g- For the RHS to be bounded by 6xp/2, suffices to choose E (27). Meanwhile, by Doob's 's submartingale inequality, for any M 0, we have
o²T P S M
Po. Z 2 M S M Σ
sup rst
s=1
4o2T z²xo For it to bounded by 8p, we need 02 2xx601/(47) The above two results imply that with the conditions on g and stated in the lemma, we have, with probability at least 1 - -72,2. that
Choose M = Ex0/2. Then, the RHS becomes
X, = Po. # ε)xo s (X) s (8) s &,
where the second inequality comes from the monotonicity of (x).
72

---

Lemma D.23. Let (x,), [O, 1] follow the update
8 = 84 a.
Then
80
& S
(1-a(1- 1)x
Proof. Define the continuous time process x(t) be the ODE x(1)= = axx(1) with initial condition to x00). We prove by induction that & S x()). Observe that both processes monotonically increasing. Therefore
f & +af xx(1) + ax(1)) xx(1) f.TH os 1).
The desired result is obtained by solving the ODE for x(1) with initial condition x(0) Xo.
Lemma D.24. Let (xx) [0. 1] follow the update
Xx+1 X2 + ax,-
Then
X0
2
1- al1 - 1) exp((-a)))x 1-1
Proof. We have that
X, X1-1
(x--1)"
(x,)
I1 - X1-1
(x1-1)
(x,)2
(x,)
(
X1
s (x--1)'
dx
x,-1 x
(xx)
(1- 1)(x-1)) 7
1-11
x/-1
[-1
= (1- - 1) ax 11-11y
x
$ (1 1)-1
exp(al) ((x()))))p(al))
x
Therefore
S x/-]
a 1) exp(-al),
x
so summing and solving for x, yields
x
2
(1 11- - -1l-)) ())1-1)exp(ppee (1xp-)))xx(p-xxx--1/
73

---

E
Scaling Law Derivations
We have shown that direction @x(p) will be learned at time (1 + o(1))T where Tp is defined by
x(p))) p. (0)) (0))
Tp =
2p=11 pd the normalizing constant. In Section 3.1, we informally derive the scaling law (1) -26--1)) In this section, we prove that this is true up to multiplicative constant (cf. Corollary 2.2).
Suppose that the signal follows the power law ap p 1/ where / > 1/2 and Z -
To this end, it suffices to (I) argue that teacher neurons with large signal strength ap are likely to lie in the set of learned neurons (x(p) E [P+]), and (2) bound the fluctuations of 12 p. (0). A lower bound on the fluctuations is given in Lemma B. B.2(d). The following lemma shows that neurons with large signal strength do indeed get learned.
Lemma E.1. Assume that ap & p for B > 1/2. Let 1 /pply(m) be the failure probability. Then there exists a universal constant so that, with probability 1 0p, all teacher neurons q satisfying oy 2 Cup, lie in the set of learned neurons, i.e q (x(p) p [P.]).
Proof. Let .1...., be independent N00, Ia) variables. We remark that [7:)e[[) is equal in distribution to (z//||;|l)iee
First, with probability 1 2m exp(-Cd), have that || = (1 + 0.5)d for all E [m]. Moreover, P(maxxc(ml. pmeee |...pl 2 2) & 2mP.e and therefore [. Sk.p I 2 log((mm.//6)) with probability 1 óp. Let us condition on these two events.
Let y 2 be some threshold. We begin by computing [m), ap Zp ap.)). By standard Gaussian tail bounds and a union bound, we have that
P
max ke|m),p>>.
P. ap apZh.p 2 ap..
s
Σ p.P.
2m exp
ap.Y 2up
Substituting an p ppppp 1/1 for B >
2. we get that
P>P.
Σ exp
ap.Y
2ap
psP.
Σ exp
2
P.
(
exp
1_ (1)
20002220 P.
dp
4 PVP.
8P.
exp( -y/2) 22
exp( exp(-y/2) - 12P exp(-xxpp) y2
Therefore
ap-kk.p 2 ar.y $ $24 (mm_p(x-//)) s 5 P max
ke <m(m).p>P
for y 2 log(24mP./oo)
Next, we aim to upper bound the quantity (x( ((.))))" The first case when {x(p) p [P-]]
[P.]. [P.]. Since [axxe[m). 2 2 log( 2mP. //))), it is clear that ax(P.) 72 (P.)(P.) S 4ap, log(2mP./os)dd. Otherwise, there exists some q [P.] such that x()) > P.. We then have [ q,5(q) I 2a y// 4ap, (og(24mP./6p)//
that (x(P.)
Let eq be some teacher neuron which was not selected by the greedy maximum selection process, i.c P.. Therefore
for P....)) & (T(P) : [P.]]. Then we must have ag 12.14 S axiP.) P...(P.)
P(q & (T(p) E [P.])) PP
U Up>p.ag Pp S ax(P.) Pr..(()))
6ar. log 24m (..p../.)))))
sP
Up>p. ag
For y one can bound P(Z, 2 y
one
1/
Le 3212 -2-2212 Therefore vān
v2n
1t2
9ar, ag
m-P.
P(g $ (x(p): : e (..))) -
exp
log(24mP./8g)
74

---

Sap.
m/2
24mP,
oq
12T
Öp
9a
m
24mP.
2 exp
2V2T
ag satisfies
9 1log(24m2 1...mm/0000 .6)p)
Qq 2 ar.
log 2v2x
log log P/ōp)
then plugging we obtain P(q & (π(p) 6p (/poly(m) we can upper bound logí z 2450 lol log
E (P.I)) S óp/P. Finally, since P. S m, for (
C for some universal constant C. Union
bounding over all yields the desired result.
Now, we are ready to prove our main theorem on the scaling law.
Proof of Proposition 2.2. By Theorem 2.1, we know that with probability at least 1 o()), we have
Σ ( (1 2 (1 - A/4)T,) - O(Ep) s L() s
Σ Gapp) 1 (1 z (1+ 4/4)T) O(Ep).
PE[A.]
pE[P.]
It suffices to estimate the LHS and RHS. For the RHS, by Lemma E.1 we have that {q ag 2 Car.) p.r(p) (log P.)/d, and thus
(x(p): [P.]), and by Lemma B.2 we have minper. 12
Σ
xx(p)) 12 41(1 1)0 na x(p) p.R(p)
o+
Σ
xip)
Čdd-1
121-2 (0)
nax(pp log P.
pE[P.]
pE[P.]
P. P.C-
Čdd-1
12
p
Ma 21 P.
p=1
Therefore, letting K = = 1000--11-22- P., we have
21-2
RHS(1) - 1 (1)
P
dl-1
281
12
Kp VV2 + +(Ep)
27
p=l
+ ((1)
P
2B
Ktt/d-1) 1/8
A APPC-11B + +(E))
p
22
p=1
o+
Kt
1+
+P. 38
q -2 dq + O(ED)
22
d-
2z
1 ((1)
Kt
+ + C2
1+o(1)
Kt
-(28-1)/8
V P. (28-1) 20-1
+ O(Ep)
22
d-
22
2B -
d!-1
When B 1/2, we have < 2B 1 2B. Hence, when s 2 d'-1/K, K.P. merged into the first term. Therefore,
CIBB the first term can be
(28-1)/8
RHS(1) Cp
Kr dd-1
V V.P. VPP-22B- (2B-1)
+0(E))
We next consider the LHS. In Lemma E. we proved that (x.)) (P.)((.)
V..PP.))P..PPPP S 4ap, 1og(24mP./6p)/
v2
with probability 1 1- ôp. Repeating the argument for all E [P.] and union bounding, with probability de we have that axip) p.x(p) 4ap log(24mP2)H)) /8)) d for [P.]. We can therefore upper bound the LHS as
Σ pE[[.]
2x1 1
12
2-11 41 100-1 ( m(p) p.x(p)
1-o(1)
(0)
S
Σ
d
12
nap log
ēd!
21-2 m
PE[P.]
75

---

Ed
Σ pe[P.]
az
1
dddp log21~
Letting = 2-1 1og21-2 m, we can similarly write
15 d'-1 kp-8
LHS(1)
2
V v P. -0(ED)
22 p=l
P
2
{p (k//d-1)) 1/8 1
P. O(Ed)
27.
P
28 dq ()(D)
27
(ka/d/-1///BPP
-(2B-1)18
1
kt
P. (28-1)
- p1-28 O(E)).
22
2B 1
di-1
When / s (2-8:(2--1) 1) pB 111 /k, the last term can be merged into the second last term. This gives the
lower bound
LHS(1) 2 cp
kt (4
(28-1)/8
V 12B---))
-EED).
Altogether, the desired claim in part (b) follows from choosing P. O log m
Finally, observe that Lemma E.1 implies that all directions ep with p PCC-IBB + log learned, and Theorem 2.1 implies that this learning happens at time O d- 11-) The conclusion part (a) directly follows.
76

---

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

---

Justification:
Assumptions for the theoretical setup are detailed in Section 2. The proof of Theorem 2.1 presented in Appendix and the proof of Proposition 2.2 presented in Appendix E.
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 be clearly stated referenced in the statement of any theorems.
The proofs can either appear 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 complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Details to reproduce the simulations in Figure 2 are given in Section 2.4.
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, 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 to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
78

---

reproducible, they Question: Does the paper provide open access to the data and code. with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA].
Justification:
This is theory paper, toy experiments conducted on Gaussian data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips..
ssi ossoolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips patts::/niiss.ccpubiii /euddeee/ seteeuubmissionnn wesssssooosoooocc
for more details. The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details are provided in Section 2.4.
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 is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are provided in Figure 2.
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, confidence 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, or 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.)
79

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-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 is 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).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: 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: [NA].
Justification: This is theory paper; toy experiments are conducted on Gaussian data. Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes, this submission follows the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consideration due laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The goal of this paper to advance the theoretical understanding SGD training of two-layer neural networks. There are no direct societal impacts of our work that we feel must be specifically highlighted here.
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.
80

---

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

---

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

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
/
83


Reviews:
[{"review_id": "mCmp5BcjMk", "reviewer": "Reviewer_cXnh", "summary": "The paper studies the online SGD dynamic for two-layer neural networks, in the limit where the width $P\\gg 1$, data is generated for a Gaussian distribution, and labeled through another, fixed, teacher network, with orthogonal weights.\nIf the target function is hard enough (information exponent $>2$), the authors are able to prove the convergence and sharp transition of student neurons to teacher ones.\nMoreover, by assuming a scaling on the second layer of the teacher, the paper predicts a scaling law of the population loss minimum, compared with the \"total compute\" measured as the product of time steps with the width of the student.", "questions": "- Can the mean field limit be connected to this result in some weight? I know the classical _mean field regime_ \\[1,2\\] is usually done for finite $d$, but there are some works that consider the limit $P\\to+\\infty$ before going $d\\to+\\infty$, such as \\[3\\]. I guess here you are considering the limit in the opposite order, but maybe there is still a connection.\n- You say that \"online SGD exhibits a long plateau\" (line 131) for $IE>2$. Isn't the plateau present also for $IE=2$? Does the separations of timescales appear also in this case? I expect not, so there is no scaling law for $IE=2$, right?\n###### Rereference\n> \\[1\\] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences\n\n>\\[2\\] Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-\nparameterized models using optimal transport.\n\n> \\[3\\] Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro. From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "- The main theorem provides a neat result about the separation of the times where the neurons are learnt, that is unprecedented in the literature, to my best knowledge. Being able to characterize this for $P\\to\\infty$ is very surprising and remarkable.\n- The formal math prediction of the scaling law is matched by numerical experiments, in Figure 2. It would be nice to append the same plot for different values of $\\beta$ though.\n- The setting is a bit artificial for two reasons: the assumption $IE>2$ is strong enough to exclude any reasonable or commonly used activation function, and the scaling laws emerge only when the teacher is crafted ad hoc to have power-law decaying weights in the second layer.", "was_revised": true, "final_justification": "My evaluation of the paper is definitely positive. The authors present a clear and formal theory for modeling scaling laws using a two-layer neural network. The authors replied promptly to my questions. I think the paper deserves to be accepted, but I'm not sure if it deserves to be in the Spotlight, given that the theory does not cover cases with $IE\\le 2$.", "rebuttal": "Thank you for your detailed review, and for the positive evaluation of our paper. We respond to your questions below.\n\n**Can the mean field limit be connected to this result?**\n\n- Thank you for the interesting suggestion. In short, this depends on whether we require *polynomial-width* learnability. \n  - If we have infinitely/exponentially many neurons and use the homogeneous parameterization (which gives a Fisher-Rao type dynamics), then MF gradient flow can learn single-index models without the extensive search phase. Intuitively, this is because with that many neurons, all directions can be covered at initialization, whence it suffices to amplify the norm of the neurons that happen to be aligned with a ground truth direction. See Section 5.3 in [GWB25] for discussions.\n  - If one wishes to do a finite/polynomial width mean-field analysis, then one needs to properly truncate the mean-field initialization to remove those neurons that are close to the ground truth directions (the total mass of them is exponentially small). Then, one could try to control the difference between the infinite-width mean-field network and its finite-width counterpart. This is the approach adopted in [LMZ20]. We believe in principle, this strategy can lead to results similar to ours in some potentially more general settings. However, controlling the difference between an infinite-width network and a polynomial-width network for $\\Omega(d)$ time is extremely technically challenging and does not seem to lead to the tight bounds. \n\n**Isn't the plateau present also for IE=2? Does the separations of timescales appear also in this case? Are there scaling laws for IE=2?**\n\n- There is indeed a plateau even when IE=2. In this case, however, there are no sharp transitions, which are usually defined as super-exponential blowups. To see this, consider the equation $\\dot{v}\\_{p, t} = a\\_p x\\_{p, t}$, which roughly captures the signal growth of the IE=2 case. Note that the solution to it is $v\\_{p, t} = v\\_{p, 0} e^{a\\_p t}$. We can make two observations from it. First, if $v\\_{p, 0} = (1 + c) v\\_{p', 0}$, then their ratio will remain $1 + c$ throughout training. Second, if $a\\_p = (1 + c) a\\_q$, then $v\\_{p, t} / v\\_{p, 0} = ( v\\_{q, t} / v\\_{q, 0} )^{1+c}$. In other words, even though the gap from the initialization and different growth rates can be amplified, the amplification will not be strong enough to create a big separation when $c$ is small. This is in contrast to the high-IE setting, where small gaps can lead to very strong separations. See the discussions in Section 3.1 for details. \n\n- When IE=2, it might still be possible to derive some scaling laws, although the situation is more complicated and our argument does not work directly in this case. For example, if the 2nd order (IE=2) terms are isotropic, then we expect the model will first identify the relevant P-dimensional subspace and the distribution of the learner neurons will be close the standard Gaussian in the relevant subspace (see [RL24] for details). After learning the subspace, we can essentially pretend that the relevant subspace is the ambient space. For some technical reasons, our proof does not directly work when $P_* = P = d$. However, we believe that when $P_* \\ll P = d$, the same argument, after some minor modifications, yields the same dynamics and scaling laws.\n\n[GWB25] Margalit Glasgow, Denny Wu, and Joan Bruna. Propagation of chaos in one-hidden-layer neural networks beyond logarithmic time. arXiv preprint arXiv:2504.13110, 2025.\n\n[LMZ20] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on learning theory, pages 2613–2682. PMLR, 2020.\n\n[RL24] Yunwei Ren, Jason D. Lee. Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis. 2024.\n\n--- \n\nWe would be happy to answer any follow-up questions in the discussion period."}, {"review_id": "NnOL9D6c9g", "reviewer": "Reviewer_vSW9", "summary": "This paper studies SGD in a very simple context and provides strong results characterizing scaling laws of SGD as a function of all the main things of interest (# training samples, amount of training, # of parameters).  A core analysis result is that scaling laws emerge from superposition of neurons with different timescales of learning dynamics.", "questions": "-- The main thing I'd want to see is some kind of empirical investigation in a much more real-world situation, e.g. like Resnet-18 learning imagenet categorization, or a GPT-2 learning process.   Is there some way to compare the theory to the empirical results in those kinds of cases?  I'm not stuck on that particular evaluation, but I'm open to anything that would take these results out of such a simple highly restricted domain of assumptions.  \n\n-- Is there some way to indicate how the scaling laws would change in other cases, like deep convnets or transformers?", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n-- the motivation for knowing the forms of these scaling curves is very clear\n-- the analysis presented is very complete and clear\n-- the P>>1 regime is often not studied so this fills in an important gap in the literature\n-- emergence result is very interesting. \n\nWeaknesses:\n-- the setting is so simple it seems to me quite unlikely the methods will generalize to real-world situations.  so it's hard to know how applicable results will be to real situations.  \n-- there is no real attempt to measure empirically if similar outcomes arise in more complex real-world situations, to which the theory can at least be compared", "was_revised": true, "final_justification": "I think basically this is a good paper but I am not that competent to judge it.    My main complaint is that it seems pretty far from being applicable to anything I can imagine people working on practically.", "rebuttal": "Thank you for your detailed review. We respond to your questions and concerns below.\n\n> “the setting is so simple it seems to me quite unlikely the methods will generalize to real-world situations. so it's hard to know how applicable results will be to real situations.”\n\nThe goal of our work is to reconcile the phenomena of emergent learning curves and smooth power law decay in the loss, both of which have been robustly observed in practice. We show that both phenomena arise in the SGD learning of a shallow neural network, thus demonstrating how scaling laws can arise in the feature learning regime. We note that:\n- Our studied model is already more “realistic” of a model for scaling laws than prior theoretical works, where most of the optimization analyses are restricted to linear regression with no learned features (see Appendix A for discussion). Importantly, it is well known that high-dimensional SGD in the feature learning regime typically exhibits emergent / staircase-like risk curves; this motivates us to consider the extensive-width and large condition number regime (in light of the additive model hypothesis) which requires significant technical novelty. \n- Our work provides theoretical justification to the additive model hypothesis of neural scaling laws in the context of SGD learning of neural networks, where unlike prior works [MLGT24, NFLL24], we do not assume explicitly decoupled tasks. \n\n> “The main thing I'd want to see is some kind of empirical investigation in a much more real-world situation, e.g. like Resnet-18 learning imagenet categorization, or a GPT-2 learning process. Is there some way to compare the theory to the empirical results in those kinds of cases?”\n\n- Firstly, we would like to emphasize that our goal is to show how emergence and scaling laws -- two phenomena which are commonly observed in practice -- arise via gradient-based feature learning; see the above point for additional discussion.\n- In addition, it is difficult to reasonably decompose real-world tasks into individual tasks, so that our analysis can be directly applied. However, we note that the prior work [MLGT24] provides empirical evidence that for language models, the overall loss can be decomposed into a superposition of emergent learning curves. Our work complements these empirical results by providing theoretical justification in the setting of SGD learning of a two-layer network.\n\n> “Is there some way to indicate how the scaling laws would change in other cases, like deep convnets or transformers?”\n\n- It is indeed an interesting question to understand theoretically how scaling laws vary for different architectures. We note, however, that there are extremely few guarantees for gradient descent on transformers, all of which are restricted to one or two self-attention layers. Even for two-layer neural networks, our work is the first polynomial width guarantee in the diverging condition number and extensive width regime. We believe that establishing such a scaling law for gradient-based feature learning in two-layer networks is a necessary first step before deriving architecture-specific scaling laws for transformers, and is a significant contribution in its own right.\n\n- We would also like to remark that the “linear representation hypothesis” posits that in pretrained language models, individual skills and concepts correspond to single directions in parameter space [DDH+21, EHO+22, PSZA23]. The additive model target which we study is an abstraction for LLM pretraining, which requires the learning of many distinct skills, and we thus believe that this is an interesting model for both the emergence of single skills and overall scaling laws in LLMs more generally.\n\n[DDH+21] Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowledge neurons in pretrained transformers. arXiv preprint arXiv:2104.08696, 2021.\n\n[EHO+22] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposition. arXiv preprint arXiv:2209.10652, 2022.\n\n[MLGT24] Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, 36, 2024.\n\n[NFLL24] Yoonsoo Nam, Nayara Fonseca, Seok Hyeong Lee, and Ard Louis. An exactly solvable model for emergence and scaling laws. arXiv preprint arXiv:2404.17563, 2024.\n\n[PSZA23] Abhishek Panigrahi, Nikunj Saunshi, Haoyu Zhao, and Sanjeev Arora. Task-specific skill localization in fine-tuned language models. arXiv preprint arXiv:2302.06600, 2023. \n\n--- \n\nWe would be happy to answer any follow-up questions in the discussion period."}, {"review_id": "TxNyQdC6PY", "reviewer": "Reviewer_yyk4", "summary": "This paper provides a precise analysis of online stochastic gradient descent (SGD) for training two-layer neural networks on isotropic Gaussian data, in the challenging “extensive-width” regime $P\\gg1$. The target function is  \n\n$f^*(x) = \\sum_{p=1}^P a_p \\sigma ( \\langle v_p^\\*, x \\rangle ), x \\sim \\mathcal{N} (0,I_d)$,  \n\nwhere the activation $\\sigma$ is even with information exponent $k^\\*>2$, the signal directions $v_p^\\*$ are orthonormal, and the second-layer weights $a_p$ may follow a power law $a_p\\asymp p^{-\\beta}$. The authors identify **sharp transition times** at which each teacher neuron is recovered, and—by overlaying these abrupt emergences—derive **smooth neural scaling laws** for the cumulative mean-squared error (MSE) as a function of sample size, training steps, and width.\n\nKey results include:\n\n- **Complexity bounds** (Theorem 2.1) quantifying when SGD exits a long “search phase” and enters a rapid “descent phase” for each feature.  \n- **Scaling-law exponents** $\\alpha = \\frac{1-2\\beta}{1+\\beta}$ characterizing how the MSE decays as a power law in compute, data, or width under power-law weight tails.  \n- **Simulations** (Section 2.4) confirming the theoretical slopes for Hermite-activated networks and illustrating the compute-optimal frontier.", "questions": "## Questions for the Authors\n1. How might the scaling-law exponents change if $x$ comes from a non-Gaussian or anisotropic distribution? What barriers exist to extending the analysis beyond $\\mathcal{N}(0,I)$?  \n2. Can the techniques handle ReLU or GeLU activations, which are neither even nor finite-Hermite? Which parts of the proof would break?  \n3. The theory requires $\\eta$ to scale inversely with $d^2 a_p$ to control fluctuations. In practice, did you find reasonable rates that match theory, or is there a gap?  \n4. Could a simple decay schedule (e.g.\\ $\\eta_t\\propto t^{-\\gamma}$) recover the anytime scaling law without knowing the total number of steps in advance? What are the main technical hurdles?  \n5. Do you foresee obstacles to applying your emergent-plus-scaling-law framework to multi-layer or residual architectures? What conceptual changes would be required?  \n6. Figure 2 shows matching slopes between idealized and empirical loss curves for $\\sigma = h_4$. Have the authors tried other Hermite orders or common activations (e.g. ReLU)? How consistent is the predicted exponent $(1 - 2\\beta)/(1 + \\beta)$ in those cases?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- **Rigorous theory connecting emergent dynamics to scaling laws.** Bridges sharp feature-recovery transitions with smooth empirical power laws.  \n- **Extensive-width regime treatment.** Handles $P\\gg1$ and allows diverging condition numbers, covering realistic over-parameterization scenarios.  \n- **Sharp, non-asymptotic bounds.** Provides concrete rates for plateaus and descents in terms of problem parameters $(d,\\beta,k^*,\\eta)$.  \n- **Empirical validation.** Figure 2 demonstrates close alignment between idealized theory and SGD simulations, including error bars and absolute loss curves.  \n\n## Weaknesses\n- **Gaussian and orthonormal assumptions.** All results hinge on $x\\sim\\mathcal{N}(0,I_d)$ and exactly orthonormal $v_p^*$, limiting applicability to more structured or correlated data.  \n- **Even activation with high Hermite order.** Requires $\\sigma$ be even with information exponent $k^*\\ge 3$, excluding common odd or non-polynomial activations (e.g.\\ ReLU, GeLU).  \n- **Learning-rate constraints.** Ensuring martingale fluctuations remain small demands $\\eta\\ll d^{-2}a_p$; such small rates may be impractical for moderate $d$.  \n- **Idealized two-layer setting.** Extensions to deeper architectures, non-additive targets, or realistic neural networks remain unaddressed.  \n- **Limited exploration of learning-rate schedules.** Corollary 2.3 requires knowing the total number of SGD steps in advance; adaptive or decaying schedules are not analyzed.", "was_revised": true, "final_justification": "This is an excellent paper, and the authors solved all my concerns.", "rebuttal": "Thank you for your detailed review, and for the positive evaluation of our paper. We respond to your questions below.\n\n**How might the scaling-law exponents change if x comes from a non-Gaussian or anisotropic distribution?**\n\n- One challenge is that when the input distribution is not Gaussian/spherically symmetric, very little is known even for the simplest single-index case. The only work we are aware of that deals with reasonably general input distributions is [BPVZ23]. They use a universality argument to show that similar convergence/sample complexity guarantees hold when the input distribution is close to the standard Gaussian. While it might be possible to extend our results to this setting, it is likely quite difficult to derive similar results for general non-Gaussian input distributions. In fact, when the target direction and the input distribution are sufficiently misaligned, even recovering a single-index model is not guaranteed. \n\n- Our results can potentially be generalized to non-isotropic Gaussians. If one assumes the spectrum of the covariance matrix also follows a power law (with a potentially different exponent), one might be able to get a two-parameter scaling law. However, we will need to use elliptical normalization, as in [MHWSE23], to ensure the preactivation is still isotropic.\n\n**Can the techniques handle ReLU or GeLU activations, which are neither even nor finite-Hermite?**\n\n- *Functions with IE=1:* First, we wish to mention that if we assume the target function is symmetric in the sense that both $v_k^\\*$ and $-v_k^\\*$ are present, then the target will automatically be even and contain no first-order terms. If the target is not symmetrized and has a linear term, then all neurons will first be attracted to the direction that is the weighted average of all teacher neurons. This cannot be cleanly fixed by using, say, a large initialization, as the effect of the first-order terms is shifting instead of rescaling. One trick to solve this issue is to learn the first-order terms first and then explicitly remove it from the target function. The time/samples needed for this step is much smaller than the later stages, so this will not change the scaling law. So far, we do not know any other fix that is more natural.\n\n- *Functions with IE=2:* Theoretically, the situation is more complicated when the information exponent is 2 (the lowest possible for even link functions). Our argument does not work directly in this case, but we expect the overall behavior to be similar. \n  - If the 2nd order (IE=2) terms are isotropic, then the model will first identify the relevant P-dimensional subspace and the distribution of the learner neurons will be close the standard Gaussian in the relevant subspace (see [RL24] for details). After learning the subspace, we can essentially pretend that the relevant subspace is the ambient space. For technical reasons, our proof does not directly work when $P_* = P = d$. However, we believe that when $P_* \\ll P = d$, the same argument, after some minor modifications, yields the same dynamics and scaling laws.\n  - The case where the 2nd order terms are anisotropic is tricker. First, we can no longer use small initialization in this case, as the neurons will all collapse to the largest direction (think of the behavior of the matrix power method). Now, suppose that we initialize the neurons so that the 0th order terms match. Then, one should expect that, again, the subspace will get learned first, and the distribution of the learner neurons will become the Gaussian distribution (in that subspace) with covariance matrix determined by the 2nd order terms of the target function. (This behavior is shown in [LMZ20], though their bounds are very loose.) Similar to the previous case, we assume that $P_* \\ll P = d$ and scale down the norm of the neurons, so that our argument can be applied here. Then, in this case, the initial correlation with direction $p$ will have order $(a_p v_p^2)^{I-1}$, instead of $v_p^{2I-2}$, and this direction will be learned around time $( a_p^I v_p^{2I-2} )$, instead of $( a_p v_p^{2I-2} )$. Effectively, this changes the power law of $(a_p)_p$ from $p^{-\\beta}$ to $p^{- I \\beta}$.\n\n- *Non-even functions:* For non-even functions, the issue is that there will be a ½ chance that the “good” neuron lies in the wrong hemisphere, and there will be no way to detect this early on when the IE is even. Unfortunately, our analysis is quite sensitive to these type of bad neurons. \n\n- *Non-polynomial function:* The only place we need the link function to be a polynomial is to get a tail bound on the per-sample gradient. We have realized that this condition can be relaxed to requiring the derivative of the link function to be polynomially bounded. We will switch to this condition in the revision.\n\n**Learning rate constraint.**\n\n- The learning rate scaling we consider of $\\eta \\lesssim d^{-I}$ is a common learning rate for feature learning via online SGD, and leads to the “optimal” rate for learning single-index models via online SGD [BAGJ21].\n\n**Could a simple decay schedule recover the anytime scaling law?**\n\n- It is possible, but not entirely clear, that a decaying learning rate schedule, where $\\eta$ is proportional to $a_p$ during the time period where $v_p$ is learned, could recover the anytime scaling law. One advantage of choosing a small constant learning rate is that this allows partial progress to be made from the beginning, even for the smaller directions. The technical challenge of using a decaying learning rate is ensuring that the total contribution of the martingale term is negligible relative to the initialization, which requires a subtle argument since a priori a large learning rate early in training could blow up the martingale term for the later neurons. One could expect to recover the anytime scaling law if these noises can somehow be controlled. Otherwise, one should expect to get a distorted scaling law, as the learning of a small direction starts only after the learning rate becomes sufficiently small. We leave understanding this to future work.\n\n**Do you foresee obstacles to applying your emergent-plus-scaling-law framework to multi-layer or residual architectures?**\n\n- There are currently extremely few guarantees for feature learning via SGD in architectures beyond two-layer networks, such as multi-layer networks with residual connections. Since results for SGD in far simpler settings do not exist for such architectures, it seems quite challenging to rigorously derive a scaling law in the extensive width regime. \n\n- However, we remark that the “linear representation hypothesis” posits that in pretrained neural networks, individual skills and concepts correspond to single directions in parameter space [DDH+21, EHO+22, PSZA23]. The additive model target which we study is an abstraction for LLM pretraining, which requires the learning of many distinct skills. We thus believe that, at least conceptually, our emergent-plus-scaling-law framework applies to other neural network architectures more generally.\n\n**Figure 2 shows matching slopes between idealized and empirical loss curves for He4. Have the authors tried other Hermite orders or common activations (e.g. ReLU)?**\n\n- We have replicated Figure 2 for the ReLU activation, and observe that after the lower Hermite modes are learned, the same scaling exponent is observed. We will add these plots to the next revision.\n\n[BAGJ21] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. The Journal of Machine Learning Research, 22(1):4788–4838, 2021.\n\n[BPVZ23] Joan Bruna, Loucas Pillaud-Vivien, Aaron Zweig. On Single Index Models beyond Gaussian Data. 2023\n\n[DDH+21] Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowledge neurons in pretrained transformers. arXiv preprint arXiv:2104.08696, 2021.\n\n[EHO+22] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposition. arXiv preprint arXiv:2209.10652, 2022.\n\n[MHWSE23] Alireza Mousavi-Hosseini, Denny Wu, Taiji Suzuki, and Murat A. Erdogdu. Gradient-based feature learning under structured data. In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023), 2023.\n\n[PSZA23] Abhishek Panigrahi, Nikunj Saunshi, Haoyu Zhao, and Sanjeev Arora. Task-specific skill localization in fine-tuned language models. arXiv preprint arXiv:2302.06600, 2023. \n\n--- \n\nWe would be happy to answer any follow-up questions in the discussion period."}, {"review_id": "841iurYFDQ", "reviewer": "Reviewer_uVcd", "summary": "The authors study the scaling laws exponents for the MSE for learning 2 later neural networks with even activations of information exponent larger than 2 and power law weights in the second layer. The analysis starts by looking at the population loss and showing that the different hidden units decouple. The MSE is then the sum of the error on each of the hidden units. Having a large separation of scale on the weights in the second layer will imply an effective power-law scaling in the MSE.", "questions": "1. Would there still be additivity in the tasks if you were to consider the gradient flow on the empirical loss?\n2. Could you sketch what you expect to happen for lower information exponents?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The paper is clear and well written. The separation between the learning of the different hidden units is well supported by the proof, and the final result is very intuitive.\nI believe the biggest weaknesses of this work lie in the poor applicability of the results and in the limitation of the model under study. Common activations used in practice do not have high information exponent, and it's not clear to me that the same additivity property that the authors exploit will translate to arbitrary functions. I am unsure about the significance of this work. On one hand, there are not many works on power-law scalings for linear-width 2-layer networks, yet the activations choice is so restrictive that the problem is essentially reduced to a stack of generalised linear model, studied in a limit where they interact very weakly.", "was_revised": true, "final_justification": "The authors clarified my questions, especially regarding the choice of activation function. I happily raised my rating to 4.", "rebuttal": "Thank you for your detailed review. We respond to your questions and concerns below.\n\n>“...the activations choice is so restrictive that the problem is essentially reduced to a stack of generalised linear model, studied in a limit where they interact very weakly.”\n\n- We would first like to emphasize that our analysis is not conducted in any limit of weak interaction between neurons. Indeed, there is no reason why the neurons should not interact a priori, and a technical contribution of our work is that we prove SGD implicitly decouples the learning of the different neurons. Moreover, if $v$ is the student neuron closest (in the weighted sense) to teacher neuron $e_p$ at initialization, it is not necessarily true that $v$ will converge to $e_p$. This is in contrast to prior works which explicitly assume that there is no interaction between the different tasks, and this is why we can remove the exponential dependence on the condition number. \n\n- Next, in the deep learning theory literature, the high information exponent regime has received significant prior interest [BAGJ21, DNGL23, OSSW24, SBH24], both since varying the information exponent controls the optimization hardness of the non-convex learning problem, and due to the connections between the IE>2 regime and higher-order tensor decompositions [LMZ20, GRWZ21]. Our work is the first to remove the exponential dependence on the condition number via a natural gradient-based algorithm, which we believe is a significant contribution in its own right.\n\n- Finally, while activation functions in practice do not necessarily have high information exponents, our work models how emergence and scaling laws can arise due to gradient-based feature learning. The “linear representation hypothesis” posits that in pretrained language models, individual skills and concepts correspond to single directions in parameter space [DDH+21, EHO+22, PSZA23]. The additive model target which we study is an abstraction for LLM pretraining -- each individual “skill” is captured by a single neuron, while the high information exponent indicates that the learning of each skill has a long search phase. We thus believe that our work is an interesting model for understanding both emergence of single skills and overall scaling laws in LLMs more generally.\n\n\n> “Would there still be additivity in the tasks if you were to consider the gradient flow on the empirical loss?”\n\n- We provide a complete analysis for gradient flow on the population loss in Appendix C. Via a uniform concentration bound on the gradient, our results will extend to gradient flow on the empirical loss as long as the sample size is $d^{\\Theta(I)}$.\n\n- We also remark that studying online SGD allows us to equate the sample complexity and the number of optimization steps, as is done in many prior works [AAM23, BAGJ21, DNGL23]. This also more closely matches the LLM pretraining paradigm, where each sample is repeated only a few times.\n\n> “Could you sketch what you expect to happen for lower information exponents?”\n- We first note that we have replicated the experiment in Figure 2 for the ReLU activation, and observe that after the lower Hermite modes are learned, the same scaling exponent is observed. We will add these plots to the next revision.\n- Theoretically, the situation is more complicated when the information exponent is 2 (the lowest possible for even link functions). Our argument does not work directly in this case, but we expect the overall behavior to be similar. \n  - If the 2nd order (IE=2) terms are isotropic, then the model will first identify the relevant P-dimensional subspace and the distribution of the learner neurons will be close the standard Gaussian in the relevant subspace (see [RL24] for details). After learning the subspace, we can essentially pretend that the relevant subspace is the ambient space. For technical reasons, our proof does not directly work when $P_* = P = d$. However, we believe that when $P_* \\ll P = d$, the same argument, after some minor modifications, yields the same dynamics and scaling laws.\n  - The case where the 2nd order terms are anisotropic is tricker. First, we can no longer use small initialization in this case, as the neurons will all collapse to the largest direction (think of the behavior of the matrix power method). Now, suppose that we initialize the neurons so that the 0th order terms match. Then, one should expect that, again, the subspace will get learned first, and the distribution of the learner neurons will become the Gaussian distribution (in that subspace) with covariance matrix determined by the 2nd order terms of the target function. (This behavior is shown in [LMZ20], though their bounds are very loose.) Similar to the previous case, we assume that $P_* \\ll P = d$ and scale down the norm of the neurons, so that our argument can be applied here. Then, in this case, the initial correlation with direction $p$ will have order $(a_p v_p^2)^{I-1}$, instead of $v_p^{2I-2}$, and this direction will be learned around time $( a_p^I v_p^{2I-2} )$, instead of $( a_p v_p^{2I-2} )$. Effectively, this changes the power law of $(a_p)_p$ from $p^{-\\beta}$ to $p^{- I \\beta}$.\n\n\n[AAM23] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552–2623. PMLR, 2023.\n\n[BAGJ21] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. The Journal of Machine Learning Research, 22(1):4788–4838, 2021.\n\n[DDH+21] Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowledge neurons in pretrained transformers. arXiv preprint arXiv:2104.08696, 2021.\n\n[DNGL23] Alex Damian, Eshaan Nichani, Rong Ge, and Jason D. Lee. Smoothing the landscape boosts the signal for SGD: Optimal sample complexity for learning single index models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.\n\n[EHO+22] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposition. arXiv preprint arXiv:2209.10652, 2022.\n\n[GRWZ21] Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou. Understanding deflation process in over-parametrized tensor decomposition. In Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.\n\n[LMZ20] Yuanzhi Li, Tengyu Ma, Hongyang R. Zhang. Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK. 2020\n\n[OSSW24] Kazusato Oko, Yujin Song, Taiji Suzuki, and Denny Wu. Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations. In Conference on Learning Theory. PMLR, 2024.\n\n[PSZA23] Abhishek Panigrahi, Nikunj Saunshi, Haoyu Zhao, and Sanjeev Arora. Task-specific skill localization in fine-tuned language models. arXiv preprint arXiv:2302.06600, 2023.\n\n[RL24] Yunwei Ren, Jason D. Lee. Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis. 2024.\n\n[SBH24] Berfin Simsek, Amire Bendjeddou, and Daniel Hsu. Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence. arXiv preprint arXiv:2411.08798, 2024. \n\n--- \n\nWe would be happy to answer any follow-up questions in the discussion period."}]

Author rebuttal:

Meta-review: This paper studies a two-layer NN with an even activation with information exponent $k_*>2$, and its
emergent learning dynamics with sharp transition and scaling law (from the juxtaposition of emergent curves) with respect to the number of training samples/SGD steps/parameters.

The reviewers appreciate the **strengths** of the paper: 
(cXnh) neat result, very surprising and remarkable, formal math prediction is matched by numerical experiments, 
(vSW9) clear motivation, complete and clear analysis, fills in an important gap in the literature,
(yyk4) rigorous theory connecting emergent dynamics to scaling laws, realistic over-parameterization scenarios, sharp, non-asymptotic bounds, empirical validation,
(uVcd) clear and well written, well supported by the proof, intuitive result.

The reviewers also find the **weaknesses** of the paper: 
(cXnh) a bit artificial setting,
(vSW9) no attempt to empirically validate the results in real-world situation,
(yyk4) limited assumptions, excluding common odd or non-polynomial activations, idealized two-layer settings.
(uVcd) poor applicability of the results and the limitation of the model (e.g,. activations). 

**After the discussion**, the reviewers agreed to accept the paper as it gives a theoretical contribution despite its limited setting.
Decision: Accept (poster)