Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws
Authors: Gerard Ben Arous
Murat A Erdogdu
Nuri Mert Vural
Denny Wu
Venue: NeurIPS 2025 poster ()
Keywords: scaling laws
stochastic gradient descent
shallow neural network
multi-index model
Primary area: theory

Abstract: We study the optimization and sample complexity of gradient-based training of a two-layer neural network with quadratic activation function in the high-dimensional regime, where the data is generated as $f_*(\boldsymbol{x}) \propto \sum_{j=1}^{r}\lambda_j \sigma\left(\langle \boldsymbol{\theta_j}, \boldsymbol{x}\rangle\right), \boldsymbol{x} \sim \mathcal{N}(0,\boldsymbol{I}_d)$, $\sigma$ is the 2nd Hermite polynomial, and $\lbrace \boldsymbol{\theta}_j \rbrace _{j=1}^{r} \subset \mathbb{R}^d$ are orthonormal signal directions. We consider the extensive-width regime $r \asymp d^\beta$ for $\beta \in [0, 1)$, and assume a power-law decay on the (non-negative) second-layer coefficients $\lambda_j\asymp j^{-\alpha}$ for $\alpha \geq 0$. 
We present a sharp analysis of the SGD dynamics in the feature learning regime, for both the population limit and the finite-sample (online) discretization, and derive scaling laws for the prediction risk that highlight the power-law dependencies on the optimization time, sample size, and model width. Our analysis combines a precise characterization of the associated matrix Riccati differential equation with novel matrix monotonicity arguments to establish convergence guarantees for the infinite-dimensional effective dynamics.

Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws
Gérard Ben Arous', Murat A. Erdogdu Nuri Mert Vural Denny Wu 444
New York University. Uniieeriity of Toronto, Vector Institute, *Flatiron Institute
gbadcims nyu. edu, (erdogdu,rural]ees vucal]0cs. www.:toooooeeeeeeeo eduu, dennysučnyu.en
Abstract
We study the optimization and sample complexity of gradient-based training of a two-layer neural network with quadratic activation function in the high-dimensional regime, where the data is generated as (x) x Σラ Ajo ((0), 2)) (0,, La). is the 2nd Hermite polynomial, and {0,} c Rd are orthonormal signal directions. We consider the extensive- regime r = dd for 3 E [o, 1), and assume power-law decay on the (non-negative) second-layer coefficients A x j_ for a 2 O. We present a sharp analysis of the SGD dynamics the feature learning regime, for both the population limit and the finite-sample (on- line) discretization, and derive scaling laws for the prediction risk that highlight the power-law dependencies width. Our analysis combines precise characterization of the associated matrix Riccati differential equation with novel matrix monotonicity arguments to establish convergence guarantees for the infiniteddimensional effective dynamics.
the optimization time, sample size, and model
Introduction
We study the problem of learning a two-layer neural network (NN) with quadratic activation isotropic Gaussian data. The target function (or the "teacher" model) is defined as
y= = fx) + with f.))) = | Σj= ((0,, x)) and x ~ Ia),
(1.1)
where (2) = - 1 is the 2nd Hermite polynomial; is zero-mean, independent sub-Gaus Gaussian noise; (0,)5-1 C IRd are unknown signal directions (index features) which we assume to orthonormal; Ai A2 > .... A O are their respective contributions; and A = diag(Ai.... Ar) collects the second-layer coefficients. Our goal is to learn this target network using a "student" two-layer neural network with quadratic activation and r, neurons, trained via a gradient-based optimization algorithm. This setting encompasses several well-known problems:
Phase retrieval (r = 1). The learning of one quadratic neuron has been studied extensively [Fic82, CC15, TV23J. The quadratic has information exponent A (defined the index of the lowest non-zero Hermite coefficient [DH18, BAGJ2IJ). This entails that randomly initialized parameters are close saddle point in high dimensions; hence the SGD dynamics exhibit plateau ("search" phase) of length log dl before the loss decreases sharply ("descent" phase).
Multi PCA (r (1)) The target (1.1) is subclass of Gaussian multi-inder models, for which various algorithms have been proposed for the finite-rank case r. @a(1) [CM20, DLS22, BBPV23J. The setting also closely relates to the multi-spike PCA problem, for which online SGD [AGP24] and other streaming algorithms has been studied [OK85, JJK 16, AZL17].
Linear-width quadratic NV (r d). The regime where the teacher width grows proportionally with dimensionality d has also been studied, typically in the well-conditioned setting (e.g.. identical X s). Recent works characterized the landscape [SJL18, DL18, VBB19, GKZ19, GMMM19], opti- mization dynamics [MVEZ20, MBB23), and statistical efficiency [MTM* 24, ETZK25, BCN BCN+25].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Cumulative abjective
Population loss
Sum
Small width
large witth
Optimal stope
Task:
120
200
Time!
Time
Total compute (FLOPs)
(a) Additive model hypothesis for scaling laws.
(b) SGD risk curves for quadratic NN.
Figure 1: (a) Illustration of the additive model hypothesis, i.e., sum of emergent learning curves different. timescales yields a power law cumulative loss. (b) Population loss vs. compute for two-layer quadratic NNs trained with online SGD with batch size dl on MSE loss. We set d 3200, and for the teacher r = 2400, a = 1.
In this work we focus on the "extensive-rank" regime where = d for ,3 E (0, 1) and r, d for E [0, 1), and place a power-law assumption on the second-layer coefficients: >y = j- for a 2 O. Our setting is motivated by the following lines of research.
Neural scaling laws & emergence. Recent empirical studies large language models (LLMs) reveal that increasing the model or training data size often results in a predictable, power-law decrease in the loss known neural scaling laws [HNA + 17, KMH + 20, HBM [2B. While such scaling of generalization error has been derived for sketched linear models [MRS22, BAP24, PPXP24, LWK+24, DLM24], these analyses assume random projection with no feature learning, and hence cannot capture the NN's ability to learn useful features [GDDM14, DCLT18) that adapt to the underlying data structure. We aim to investigate a setting where the training of nonlinear NN beyond the "lazy" regime exhibits a nontrivial scaling law.
Feature learning in neural networks is often studied theoretically through the learning of multi-inde models, where the target function depends and references therein). For these low-dimensional targets, it is known that the training dynamics typically exhibit emergent (or liirc behavior long plateaus followed by sharp drops in loss [BAGJ22, AAM23J. To reconcile this emergent loss curve with smooth power-law decay, recent works hypothesized that the pretraining objective can be decomposed into a sum of losses on individual tasks [MLGT24, NFLL24), the learning of each exhibits a sharp transition, and the superposition of numerous emergent risk curves different timescales yields a power-law scaling of the cumulative loss (see Figure (a)). In this context, the two-layer network (1.1) can be viewed as a sum of single-indes phase retrieval tasks, where the length of each log plateau in the risk trajectory can be modulated by the second-layer coefficient Aj. This motivates the following question:
small number of latent directions (see [BH25)
Q1: Does gradient- based training of a two-layer quadratic network yield power-law loss scaling. when the target function is an additive model with varying second-layer coefficients (>g -=
In Figure 1(b) empirically observe the affirmative: when the target function has smoothly decaying second-layer weights, online SGD training yields pawer-law risk curve that resembles the scaling laws in 1KMH+20, HBM+22). The goal of this work is to rigorously establish such scaling laws.
Learning extensive-width neural networks. Prior works multi-index models have shown that when r -= (1), gradient- training succeeds with polynomial sample complexity depending on properties of the link function [AAM22, DLS22, BBSS22]. The "extensive-rank" regime where r x d for 3 >> 0 relatively under-explored (except for the linear width regime r x d [MBB23, MTM+241); this setting is arguably closer to the practical neural network training (compared to the nartow-width setting), and also bears connections to several observations in the LLM literature such superposition [EHO* 22] and skill localization [DDH 21, WWZ 22, PSZA23], where the model simultancously acquires a large number of "skills" during pretraining (see e.g., [OSSW24]).
The learning dynamics of (1.1) with divergingly many neurons is challenging to analyze primarily due to the fact that the effective dynamics may not be captured by finite set of summary statistics [BAGJ22] (as the finite-r case). Recent works [OSSW24, SBH24) addressed this challenge by assuming that the activation a has information exponent k 2 3, which allows the learning dynamics

---

Algorithm
Decay rate (Az)
Risk scaling law
Result
0: > 0.5
(2a
Gradient flow
Theorem
0.5
(1 E-
+ (1 (ra/r))-20)4
Online SGD (Stiefel)
>> 0.5
(n))
20-1
r/4
(2
Theorem 2
Ox < 0.5 (1 (ny)
2a
+ (1 (ra/r)1-20)
Table I: Scaling laws for learning quadratic neural network (1.1) using population gradient flow and its online SGD discretization. We omit constant factors in the risk scaling for ease of presentation.
a > 0.5, for population gradient flow, & t t-log is the rescaled time; for online SGD, ~ t- log d where is the number of gradient steps, which is equal to the sample size, and 1) ~ 1/(d polylog(d)) is the step size. a < 0.5, for population gradient flow, ~~ t. log d the rescaled time; online SGD, E E~ t log where is the number of gradient steps and ~ 1/(rr" polylog(d) is the step size.
to decouple across feature directions. However, the case k S 2, which includes the quadratic activation studied in this work, remained open: existing analyses either assumed "isotropic" feature contributions (A1 X₂) [RI.24, SBH24), or established computational complexity for SGD) that scales with d [LMZ20], which leads to pessimistic exponential dimension dependency in the power-law setting we consider. We therefore ask the following question.
Q2: Can we establish optimization and sample complexity of learning extensive-width quadratic neural network (1.1) with anisotropic. power-decaying feature contributions?
Finally, although our problem setup does not directly encompass commonly used activation functions such ReLU, for SGD on multi-index models it is known that the Hermite-2 component is the first harmonic capturing multi-dimensional structure in the target function [DLS22, DKL.+ Consequently, our quadratic setting represents the first nontrivial mode of feature learning in SGD) dynamics. Consistent with this view, Figure 3 shows that the risk trajectory of ReLU networks closely follows our theoretical characterization of quadratic networks over substantial portion of training.
1.1 Our Contributions
We analyze the risk trajectory of learning (1.1) with both gradient flow on the mean squared error (MSE) loss and its online SGD discretization on Stiefel manifold, covering the extensive-widtt width and power-law settings. We derive scaling laws for feature recovery and population risk as a function of teacher and student network widths Ts, r, the decay exponent a, the optimization time, and the sample size (for the discretized dynamics). Our contributions are summarized as follow (see Table 1).
In Section 3, we analyze the population gradient flow and tightly characterize the loss decay with respect to time and the student width rs. We show that signal directions are recovered sequentially, and the population MSE follows a smooth power law specified by the decay rate a > 0.
2. In Section 4, we consider the online stochastic gradient descent (SGD) dynamics the Stiefel manifold and derive scaling laws with respect to sample size. When specializing to the isotropic setting a our sample complexity improves upon [RL24] in the sitensive-width setting and matches the information theoretic limit (in terms of d, dependence) up to polylogarithmic factors.
The following technical challenges in the extensive- width regime are central to our analysis:
Coupled population dynamics. As r. 0o, must track infinitely many overlapping student and teacher neurons. [OSSW24, SBH24] assumed high information exponent A >> 2, to decouple the dynamics into independent single-index models, but such property does not hold in quadratic case (k- = 2). We address this by leveraging the closed-form solution of the quadratic problem [MBB23], which satisfies Matrix Riccati ODE. A key ingredient in our analysis is its monotonicity with respect to its initialization, illustrated in Figures 4(a), which enables sharp risk bounds via comparisons decoupled models.
Operator norm discretization error. Prior works [BAGI21, BBPV23, AGP24] focused on finite-r settings, where Frobenius norm control of the SGD noise was sufficient and natural: it allows bounding error direction-wist without incurring additional dimension dependence. However, in the extensive- width regime, such bounds become pessimistic and lead to suboptimal r-dependent rates. Hence we need to establish operator norm concentration around the population dynamics.
3

---

comparison framework. To control discretization error in operator norm, we extend the monotonicity- argument discrete time and introduce a novel comparison- bbased discretization technique. Our approach constructs matrix-valuee reference sequences corresponding decoupled dynamies that tightly bound the discrete evolution from above and below. This yields sharp operator norm control even when the true trajectories are non-monotone (see Figure 4), the analysis avoids relying on the trajectory itself by comparing against simpler bounding sequences.
1.2 Additional Related Works
Learning multi-index models with SGD. When 1, the target is a single-index model with quadratic link function. The SGD learning of single-index models has been extensively studied in the feature learning literature [BAGJ21, BES 22, MHPG 22. BES 23, MHWSE23, MLHD23, MZD+23, BMZ24, DNGL24, GWB25]; while this model has d parameters to be estimated, the quadratic link (with information exponent k 2) incurs an additional log d factor in the complexity of online SGD. More generally, the setting where r = (a(1) is covered by recent analyses of multi-index models [AAM22, AAM23, BBPV23, D CWPPS23, AGP24, VE24, MHWE24];; however, these learning guarantees for multi-index models typically yield superpolynomial complexity when the target function is rank-extensive. The sample complexity of gradient-based based learning is also connected to statistical query lower bounds [DPVLB24, DTA 24,, LOSW24, ADK+24]
Quadratic NNs and additive models. Prior theoretical works on learning two-layer neural network with quadratic activation function have studied the loss landscape [SJL18, DL18, VBB19, GKZ19, GMMM19] and the optimization dynamics [MVEZ20, AKLS23, MBB23, RL24]. While existing optimization and statistical guarantees may MBB23, RL24J), to our knowledge, precise scaling laws have not been established in our extensive- rank and power-law setting. (1.1) is also instance of the additive model [Sto85, HT87, Bac17] where the individual functions are given as (orthogonal) single-index models with unknown index features. For this model, [OSSW24, SBH24] established learning guarantees in the well-conditioned regime, under the assumption that the link function a has information exponent k >> 2.
the sieessie-wwith regime (see e.g.. [DL18,
2 Background and Problem Setting
2.1 Student-teacher Setting
Teacher Network. We consider the task of learning teacher network with a quadratic (second- order Hermite) activation function written
(0) 1) and x NOO, Ia), y = f.) + with f=(x) = | j=1
(2.1)
where Rd is the input; is zero-mean, nounded-varianee sub- Gabb-aa noise; is the teacher network width; and {0,}ī=z C Rd is an orthonormal set of unknown signal vectors. We collect these as columns of the matrix O E d The contributions of these vectors determined by the unknown second-layer coefficients A > A2 > ... d > O with a power-law decay XY X x=aa for 2 O, and A is diagonal matrix whose j-th diagonal entry is λy- The normalization in front of summation ensures Ely²) is constant. We focus on the regime where r x d for 3 E (0, 1).
Remark 1. The orthogonality of (0,}ī=ı can be assumed without loss of generality. Specifically, consider (2.1) with arbitrary first-layer weights e and normalization E(y) = 0, the output can be written as x Tr(x:: T @AQ constant + noise; hence we may redefine ()j, 02) via the spectral decomposition.
Student Network.
We learn the target model with a quadratic student network defined
(x W)
(w, x)² ww 12
(2.2)
where r, is the width of the student network, and (w 1 C Rdd denotes the set of trainable weights. We collect these weights the columns of the matrix W e _dxr,, and omit the dependence on

---

in (a, W) when clear from the context. Note that the norm subtraction ensures E. (ū æ W) 0. We may equivalently write the student network as f(x, W) E;= ((w,, x) 1) where w is unit-norm; since our student does have trainable second-layer, the norm component | allows the model to adapt the target second-layer Ay; this homogeneous parameterization has been studied in prior works [CB20, GRWZ2IJ.
2.2 Training Objective
Training constitutes to minimizing the squared loss; we define the instantaneous loss on (ær, y) as
L(W; (ax, v)) == ( j(a, w))"
where the prefactor is included for notational convenience in the gradient computation. We omit the dependence on (x. y) when clear from context. The population risk can be written as
R WW) == ((..)) [(W) = WWT
|Al| rvee B(())
(2.3)
Alignment. Observe that the student network is invariant to right-multiplication of its weight matrix by an orthonormal matrix, i.e., j(r W) j(r, WO) for any O e "R",x"> with O O Consequently, any notion of alignment that depends on individual directions in W may not be informative. To capture directional learning a way that respects this symmetry, we define alignment in terms of the subspace spanned by student weights. We formalize this using the polar decomposition:
W UQ! where Q @ W and U Ir..
(2.4)
Here, Q denotes the radial component of the student weights, while U is an orthonormal matrix that encodes their directional component. We quantify the alignment between the student network and the jth teacher feature by the squared norm of the projection of 0 onto the column space of W:
Alignment( W, W,0,) = U 0,
UTO, 12-
(2.5)
Alignment( W, ,0,) takes values in the interval [0, 1]; it is 0 if 0, is orthogonal to W (no alignment), while is 1 if 02 is in the column space of W (perfect alignment)'.
3 Continuous Dynamics: Population Gradient Flow
We first analyze the continuous- time population gradient flow dynamies for (2.3), given as
a Wi = VR(W),, where Wo E Rdx,, Wo,s aid N (0, 1/d),
(GF)
and the population gradient reads
VR(W)) 2/T. OAAT
|
w.w.") W. Vra
For notational convenience, we define
R(1)= W.WW TA T and A(I,0,) Alignment (rngmmen(WW... 0,).
The following theorem sharply characterizes the timescale for alignment and the limiting risk curve. Theorem 1. Let >i- = j and dd for some a 2 0 and B3 (0, 1). Consider the regime
- p H E (0, 2o) and d 2 an and d Pn.r (1), Define the effective student width and effective timescale as
if a E (0,0.5),
(3.1)
r,
if 0.5.
[og -/8 d) Arl, if E [0,0.5) if > 0.5.
Teff
and T == :ra d/..
Fss
Then, the population (GF) dynamics satisfy the following with probability 1 1
'The definition in (2.5) may fail converge when 0 and r. r, due rotational symmetry in the teacher network. In this case, a more suitable notion of alignment can defined using principal angles between the subspaces spanned by W and @ which provides a rotation-invariant characterization of directional overlap. Specifically, for = 0. we define Alignment W 0,) as the jth largest eigenvalue of θ UU O.
5

---

1. Alignment: For j S Tell and t > 0 satisfying t = r" when E [0, 0.5) and t = when > 0.5,
A(tTott 02) - 1lt 2 X + os().
(3.2)
2. Risk curve: Under the same time scaling.
Telf Σ
R((T.H)
1311 +a()).
(3.3)
|
Remark 2. We make the following remarks about our result in Theorem 1:
The spectral decay a determines both the choice of student width vs and the learning timescale in Theorem 1. Specifically, when > 1/2 (i.e., light-tailed regime), the coefficients {>i}ī=1 are square-summabbl making the teacher model effectively fiite-dimensional. Hence only finitely many directions need to be learned to achieve small loss, and timescale of order log d and wintt student suffices. In contrast, for the heavy-tailet regime a <, 1/2. we need to recover linear-in-r directions, which require proportional student width T,/r - ip and longer timescale r log d. This difference will be made explicit in Corollary
Theorem I verifies the additive model hypothesis [MLGT24] for quadratic neural networks in the feature learning regime; specifically, (3.2) identifies sharp transition time alignment between student weights and the j-th teucher direction, and (3.3) suggests that the cumulative loss can be decomposed into individual emergent risk curves where the timescale is decided by the signal strength Xg-
0.30
0:30
0- 0.40
2- 0:45
Poputotion 1.0
300
3.
60
(a) Heavy-tailed regime (a < 1/2).
(b) Light-tailed regime (a > 1/2).
Figure Illustration the limiting risk trajectories and scaling behavior given in Corollary 1.
Neural scaling laws. As a corollary of Theorem 1, we obtain the following risk characterization.
Corollary 1. By Theorem I, the asymptotic risk of (GF) is given as follows:
Heavvy-taildd regime (ox E 0.,):: Almost surely, for all t >> 0
R(tr log d) d=+0o (1 (1-Ct" 1-20
) V (1 - )2-22)++
Light-tailed regime (a >> 0.5): With probubility converges as + oo to a deterministic limit satisfying
- ((1 for all 1 > O, the risk R(1 log d)
R(t d) d=000 θ
(1-200 20-1
+ (2a 12)
Corollary I shows that, over appropriate timescales, the cumulative effect of these emergent transitions yields smoothly decaying risk curve. Intuitively speaking, the power-law exponent arises from the Riemann integral approximation of the infinite sum (3.3) see Appendix D.5 for details.
The asymptotic risk behavior in Corollary I visualized in Figure (see also Figure 1(b) for empirical simulation). The figure illustrates how the sharp, step-like emergent curve at a 0 (as observed in earlier works on multi-index learning [BAGJ21, AAM23]) gradually transitions into a smooth curve as increases. Notably, in the light-tailed regime a > 1/2, our risk curve resembles the neural scaling laws in [KMH+ 20, HBM+22] which takes the form of R. 1/(Data size)* + 1/(Model size)", where the data size can be connected to optimization time under the one-pass discretization, which we analyze in the ensuing section.

---

4 Discrete Dynamies: Online Stochastic Gradient Descent
Now we analyze the finite-sample, discrete-time counterpart of the population dynamics (GF) and establish computational and statistical guarantees. We first discretize the directional component of the dynamics via online SGD with Stiefel constraint (see Proposition 2), and then introduce a fine- tuning step with negligible statistical and computational cost fit the radial component: this mirrors the layer-wise training paradigm commonly used in theoretical analyses ses of gradient-bare based feature learning [AAM22, DLS22, BES 22, BEG 22]. The procedure is summarized in Algorithm
Algorithm 1 Online Stochastic Gradient Descent (Stiefel)
1: for ..... do
2:
W. Wi-1 V (WW -1/2 3: Wi Wi (. W.
>> Feature learning
4: end for
5:
W.faa final WiS where Ωz = arg min E/ L(WiS); (244). B(45)
>> Fine-tuning
In the feature learning step, we update the first-layer weights W, recover the subspace spanned by the teacher directions. To this end, we use online SGD on Stiefel manifold [AGP24] with polar retraction. The Riemannian gradient on the Stiefel manifold is given by:
VsL((WL))) == VL(W,-1) 2 W (W, + VL(W,-1) ((()))))T(-i)
where the instantaneous loss is defined for sample (a), v:). Since the goal is ensure subspace alignment (2.5), the overlap of individual student-teacher weights is not relevant during this phase.
After the feature learning phase, we perform a tine-tuning step to rotate W, so that each w aligns with the corresponding teacher direction 0j. This is achieved by solving an empirical risk minimization problem over NF: fresh samples. The optimal fine-tuning matrix Ω, admits a closed-form solution that is also numerically easy compute. Importantly, the computational and statistical complexity of this step scales only quadratically with the student width r,, which is negligible compared to the cost of feature learning. The complexity analysis for this phase provided in Appendix E.
Remark 3. Recall that the stage-wise training procedure is not required in our continuous analysis in Section 3. This is because
employ Stiefel gradient similar to [BBPV23, AGP24] which cannot fit the radial component - to simplify the discretization analysis. We conjecture that standard Euclidean discretization can achieve the same risk scaling; see Figure 1(b) for empirical evidence.
We define the population risk of the output of Algorithm 1, the alignment with teacher direction 0,. and the optimal risk achievable by a student neural network with width T, respectively as
R(1)= = R(Wffall),
A(1, 0,) = Alignment. (W,, 0z), Ropt
a Ej-(nAr)41 X3.
Intuitively, Ropt is the risk achieved by exactly fitting the top T. components of the teacher model. Note that the alignment A(t, 0,) depends only on the directional component of Wr; thus, this quantity remains unchanged during fine-tuning The following theorem characterizes the alignment and risk curve for the discrete-time Algorithm 1.
Theorem 2. Let the parameters {>, r,r,, reft and Ti and the scaling regime (3.1) be as in Theorem 1. Suppose the student weights are initialized uniformly on the Stiefel manifold, and that the step size n) and fine-tuning sample size Nr satisfy
a E (0,0.)
log (1+d/r.)
and NA = log" d,
17
x
a>0. 0.5
Cud
for some constant C.. 0 depending only on a. Then with probability 1 - Q(1/12)
1. Runtime and sample complexity: If
d/rs), a E (0.0.5) I log C.+ Ca+l
(1 C1
T 2
(4.1)
dlog da d,
a > 0.5.
have R(T) Ropt + oa(1).

---

2. Alignment & Risk curve: Fort > 0 satisfying t t= xx/////// /n E (0,0.5) and a x 1/n > > 0.5.
A(tTen, 01) Lint 2 2 (I)).
R((Ter)= =
23 fnt 2 x +o(())
A 3=1
Remark 4. We make the following remarks on the sample complexity.
The bound in (4.1) implies a complexity of drd polylog(1 + d/rs) the heavy-tailed case, and T = d polylog(d] (d) in the light-tailed case. Note that due to the one-pass nature of the algorithm, the runtime and sample complexity are identical (up to the negligible fineegiibleeettuiiiiii fine-tuming step).
In the light-tailed regime (o >> 1/2), the required sample size = d polylog(d) is information theoretically optimal up to logarithmic factors. Note that kernel methods and neural networks in the lazy regime [JGH18, COB19] requires Z d² samples learn quadratic target function; thus our sample complexity bound illustrates the benefit of feature learning.
In the heavy-tailed regime (a < 1/2), we obtain (nearly) information theoretically optimal sample complexity when a = 0. For the intermediate regime a E (0, 1/2), we conjecture that the optimal sample complexity is T = dr, which implies our current bound is suboptimal by r"
Isorropic Setting (a 0). In the isotropic case, where the goal is to estimate the r-dimensional subspace spanned by the teacher weights, the above theorem yields a sample and runtime complexity x T' dr polylog + d/rs). This interpolates between the retrieval r = 1 [TV23, BAGJ2IJ. and ~ de as + d, which matches the sample complexity in the linear- -iith regime [MTM 24, ETZK25J. Notably, our r-dependence improves upon the recent work of [RL24], which established sufficient sample size of n Z (poly(r) for similar quadratic setting. We expect our result to be optimal up polylogarithmic factors due the intrinsic dr-dimensional nature of the subspace recovery problem.
d dpolylog(d) rate for phase
Scaling laws in discrete time. As indicated by the alignment and risk expressions in Theorem 2, a sufficiently small learning rate 7) ensures that running online SGD for steps closely tracks the population gradient flow trajectory (GF) at time nt, exhibiting the same scaling behavior. The following corollary formalizes the discrete-time counterpart of Corollary 1.
Corollary 2. We consider spl d-+00 le > 0. By Theorem 2, we have
* Heavy-tailed case (a E [0, 0.5)): Almost surely,
R(t log d) d= (1 (te
Cta 1-20
V (1 1-----100 (1-20)+
Light-tailed case (a > 0.5): With probability - (((/rr)). R(tlog d) has an asymptotic limit
d-100 (te 20-1
R(t log d)
+ +
5 Overview of Proof Techniques
To avoid notational confusion between discrete-time and continuous-time dynamics, we adopt the following convention throughout this section. Subscripts (e.g., W,) denote discrete-time quantities, while parentheses (e.g.. W W(E) denote continuous- time trajectories. Specifically, (Wr refers to the iterates of online SGD; { (W(t) (t) denotes the continuous-tim time gradient flow governed by (GF). Since our proof strategy heavily relies on the matrix (Loewner) order for symmetric matrices, introduce the following notations. For symmetric matrices G₁, G2 E 1dd we write G. < G2
G2
G1 is positive definite. The reverse relations denoted by G1 G2 and G > G2.
5.1 Proof Sketch of Theorem
We first observe that both the population risk R(W (1) and the alignment Aligmment W (L), 0,) depend on (t) through two Gram matrices: the weight Gram matrix Gt) = (t) and the alignment Gram matrix ()) θ (I) O where (U())) denotes the directional component of W (1), as defined (2.4). The proof proceeds by analyzing the evolution of these matrices, each governed by an autonomous ODE; in particular, a matrix Riccati differential equation.

---

Proposition 1. The Gram matrices defined above satisfy the following matrix Riccati ODEs:
Weight Gram matrix: 0,Gw (t)
0.5
@AAO Gw(() Gw 21|Al|
G (t).
VA
Vra
Alignment Gram matrix: (,Gr(()= TA (AGU() Go((AA 2G (G)(())((())
Both equations in Proposition take the form of matrix Riccati ODEs [BLW91], whose structural properties play a central role in the proof. To illustrate the core idea, we focus on the alignment dynamics. For simplicity, we write G(t) == Gu (t) and consider
O,G(t) ||A (AG(t) + G(t)A 2G(()A
(5.1)
Note that Alignment (t)., 0;) corresponds to the 5th diagonal entry of G(t). To characterize its trajectory, we leverage the monotonicity of the matrix Riccati flow with respect to its initialization, ie., if G > Go. the corresponding solutions satisfy G(I, G > G(I, G for all / 2 0, where G(I, Go) denotes the solution to (5.1) with initial condition Go. Our proof strategy builds on this monotonicity and proceeds follows:
1. Diagonalization & decoupling. If Go is diagonal, the solution {G(t))r2 remains diagonal under (5.1), reducing the dynamics to independent scalar ODEs that govern each diagonal entry. Moreover, each scalar ODE admits a closed-form solution.
Asymptotic characterization. For general Go, we construct diagonal matrices G = Go = Go- By monotonicity, the corresponding trajectories upper and lower bound (G(t) These bounding systems are diagonal and decoupled, and as + oo, they converge to the same limit.
We apply this strategy in Appendix D.3 to derive the exact asymptotics stated in Theorem 1.
Remark 5. We note that while the Riccati flow is monotone with respect to its initialization, this does not imply that its solution is monotone in time. That is, the trajectory G(L) may not evolve monotonically in matrix order, even though a larger initialization yields trajectory that remains above that of a smaller one for all t 2 0. This distinction is illustrated in Figure 4.
5.2 Proof Sketch of Theorem 2
Extending Monotonicity Arguments to Diserete Dynamies
We begin by observing that online SGD on the Stiefel manifold approximates the directional compo- nent of the continuous-time gradient flow, with stochastic gradients arising from online sampling. The proposition below formalizes the idea that online SGD approximates the directional dynamics of the continuous gradient flow the population level. For the statement, recall that Ut) denotes the directional component the gradient flow solution (t) from (GF), as defined in (2.4).
Let W be the solution to the continuous-time gradient flow on the Stiefel manifold, initialized with U (0). Then for all t 0, the column spaces of W (t) and U(t) coincide.
Proposition 2.
This result justifies studying the online SGD on Stiefel manifold via the directional dynamics of (GF). To this end, we introduce the discrete analog of G(l) above G. θ W.W, O. Extending the analysis to discrete time is non-trivial due to the loss of monotonicity in the Euler discretization of the Riccati dynamics (5. In particular, the update
G - G + || P.F LAG-1--G-1 2GL-1AG-11 + (2nd-order terms and noise) (5.2)
0.5g
dynamics
no longer preserves the matrix order structure crucial to the continuous-time argument.
To overcome this, we construct auxiliary discrete system that approximates (5.2) up to second-order terms while preserving monotonicity. Specifically, we define the map
! (2G A2G, I.) (A,+nA - I,)) + + 2
G(G,, n) G.
(5.3)
which matches (5.2) up to second-order terms. Indeed, expanding the inverse term gives
G G. 2 (2G. (.G.--I))A(26 (,) I,) 7 2nd-order terms.
-G.+n(AG,+O) -2GGGG
The key advantage of the iteration (5.3) is that preserves matrix order:

---

Proposition 3. For > O, G = G = O, we have G .) = G .n).
We use this to bound the non-monotone dynamics (5.2) via monotone iterates. Roughly, we show that for small enough step size 7). the following holds:
G(G,-1. (1 + +)m) + Noise ł G. 2 ( E)) + Noise
for some E = o1),,, where we denote the effective learning rate in (5.2) with n vea We then follow the same bounding argument used in the continuous case by defining
G G(GT-1, (1 + E)n) + Noise, where G = Go 00
and show that G. = = G, for all & E N. Finally, by choosing Go to be diagonal, the bounding dynamics reduce to decoupled scalar recursions, which can be analyzed explicitly. This allows us to establish concentration of the original iterates {GrJee around the bounding sequences, leading to operator-norm convergence of the discrete- time dynamics to their continuous-ting timm counterparts.
6 Conclusion
In this work, presented comprehensive theoretical analysis of gradient-based learning in high- dimensional, extensive-width two-layer neural networks with quadratic activation. We established precise scaling laws that characterize both the population gradient flow and its empirical, discrete-time approximation. These results demonstrate how anisotropic signal strengths in the target function fundamentally shapes the convergence behavior and sample efficiency of gradient-bar based learning.
Beyond quadratic activations. An immediate direction for future research is to extend analysis to more general activation functions. Link functions with higher information exponent is studied in a companion work [RNWL25], where the precise risk scaling is established by exploiting decoupling structure that is unique to the information exponent > setting. Importantly, many commonly- useed activation functions (ReL.U, GeI.U, etc.) have information exponent k and also contain nonzero Hez component. For such nonlinearities, we conjecture that SGD dynamics exhibits a multi-phase risk curve (analogous to the incremental learning phenomenon in [AAM23, BBPV23),, where the higher Hermite modes affects the learning dynamics after the low-order terms are learned. In Figure we report the SGD risk curves for ReLU networks, in which we observe (i) an initial loss drop driven by the Hej component (which finds a degenerate rank-l subspace), followed by (ii) a power-law decay phase driven by the quadratic Hc₂ component where the empirical scaling exponent align closely with our theoretical predictions, and finally (Hii) a slope change late in training likely due to higher Hermite terms (in Figure 5 we confirm that this "late" phase is absent if we remove these higher-order components). Understanding this complex multi-phase learning dynamics remains an interesting challenge for future work.
10P
12-1
Population loss
Population loss
33
Width 32
Width 32
2
Wicth
Width 128
Width 128
Width 256
Width-
Width 512
22-4
Width 512
10>
10'
10
107
UP
30'
3P
Width x GD steps
Width x GD steps
(a) 0 = 1. Idcal exponeet: -1; empirical: - 1.01.
(b) a
Ideal exponent: - empirical: 1126.
Figure 3: Population loss vs. compute for two-layer ReLU network (power-law second-layer with exponent a) trained with population gradient descent. The student network adopts the 2-homogeneous parameterization as in (2.2). Ohserve that after the initial loss drop due to the He; component, the risk curves follow power-law scaling where the exponent (dashed) nearly matches theoretical prediction for the quadratic setting 1-2u.
10

---

Acknowledgment
The authors thank Florent Krzakala, Jason D. Lee, and Lenka Zdeborová for discussion and feedback. The research of GBA was supported part by NSF grant 2134216. MAE was partially supported by the NSERC Grant [2019-06167]] the CIFAR AI Chairs program, and the CIFAR Catalyst grant. Part of this work was completed when NMV interned at the Flatiron Institute.
References
[AAM22] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged- staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. Conference on Leurning Theory, pages 4782-4887. PMLR, 2022.
[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 Theeory pages 2552-2623. PMLR, 2023.
[ADK*24] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405. / 5459,, 2024.
[AGP24] Gérard Ben Arous, Cédric Gerbelot, and Vanessa Piccolo. High-dimensional optimiza- tion for multi-spiked tensor pca. arviv preprint arXiv:2408.0640) 2024.
[AKLS23] Luca Amnbolli, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan. Escaping mediocrity: how two-layer networks learn hard generalized linear models with sgd. arXiv preprint arXiv:2305.18500 2023.
[AZL17] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pea: a global, gap-free, and near-optimal rate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487-492. IEEE, 2017.
[Bac17] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681) 2017.
[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-4835 2021.
[BAGJ22] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling. Advances in Neural Infor- mation Processing Systems, 35:25349-25362, 2022.
[BAP24] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. arXiv preprint arXiv:2402.01099, 2024.
[BBVV33 Alberto Bietti, Joan Bruna, and Loucas Pillaud- Pillaud-Vivien. On learning Gaussian multi- index models with gradient flow. arXiv preprint arXiv:2310.1978 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-78877 9783, 2022.
[BCN+25] Jean Barbier, Francesco Camilli, Minh-Toan Nguyen, Mauro Pastore, and Rudy Skerk. Statistical mechanics of extensive-width bayesian neural networks near interpolation. arXiv preprint arXiv:2505.248.0 2025.
[BEG+22] Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750-21766 2022.

---

22] Jimmy Ba, Murat A Erdogdu, Tajii Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High-dimensional asymptoties of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932-37946, 2022.
[BES BES$$3) 23] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu. Learning in the presence of low- -ow-dimensionll structure: A spiked random matrix perspective. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[BH25] Joan Bruna and Daniel Hsu. Survey on algorithms for multi-index models. arXiv preprint (5t:::200.0042266 2025.
[BLW91] Sergio Bittanti, Alan J. Laub, and Jan C. Willems. The riccati equation. 1991.
[BMZ24) Raphaäl Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics, pages 1-84, 2024.
[BR14] Davide Barilari and Luca Rizzi. Comparison theorems for conjugate points in sub- riemannian geometry. ESAIM: Control, Optimisation and Calculus of Variations, 22:439-472, 2014.
[Bub14] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8:231-357. 2014.
[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.
[CC15] Yuxin Chen and Emmanuel Candes. Solving random quadratic systems equations is nearly easy solving linear systems. Advances in Neural Information Processing Systems, 28, 2015.
[CM20] Sitan Chen and Raghu Meka. Learning polynomials in few relevant dimensions. In Conference on Learning Theory, pages 1161-1227. PMLR, 2020.
[COB19] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
[CWPPS23) Elizabeth Wooddfn, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the nigh-dimensional notes: An ode for sgd learning dynamics on glms and multi-index models. arXiv preprint arXiv:2308. 089700 2023.
[DCLT18] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding. arXiv preprint 111iv:1810.044 04805, 2018.
[DD Damai Dai, Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. Knowl- edge neurons in pretrained transformers. arXiv preprint (ttiv:2204.08860 2021.
[DH18] Rishabh Dudeja and Daniel Hsu. Learning single-index models in gaussian space. In Conference On Learning Theory, pages 1887-1930, PMLR, 2018.
[DKL+234 Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step time. arXiv preprint arXiv:2305. 18270, 2023.
[DKL. [DK] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. Learning two-layer neural networks, one (giant) step time. arXiv preprint arXiv:2305.18270, 2023.
[DL18] Simon Du and Jason Lee. On the power of ovrapaaramtiiizzaooonn in neural networks with quadratic activation. In International conference on machine learning, pages 1329-1333 1338. PMLR, 2018.
12

---

[DLM24] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewiez. Dimension- free deterministic equivalents for random feature regression. arXiv preprint arXiv:2405. /5699, 2024.
[DLS22] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. Conference on Learning Theory, pages 5413-5452. PMLR, 2022.
[DNGL24] 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. Advances in Neural Information Processing Systems, 36, 2024.
[DPVLB24] Alex Damian, Loucas Pillaud- Pillaud-Vivien, Jason D Lee, and Joan Bruna. The com- putational complexity of learning gaussian single-index models. arXiv preprint arXiv:2403.0552, 2024.
[DTA [4] Yatin Dandi, Emanuele Troiani, Luca Arnaoold.. 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.03220. 2024.
[Dur93] Richard Durrett. Probability: Theory and examples. 1993.
[EHO+22] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac HatfieldDoodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposition. arXiv preprint arXiv:2209.1065 2022.
[ETZK25] Vittorio Erba, Emanuele Troiani, Lenka Zdeborová, and Florent Krzakala. The nuclear route: Sharp asymptotics erm in overparameterized quadratic networks. arXiv preprint 25X5 2025.
[Fie82] James R Fienup. Phase retrieval algorithms: comparison. Applied optics, 21(15):2758-2769) 1982.
[GDDM14] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierar- chies for accurate object detection and semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580-587, 2014.
[GKZ19] David Gamarnik, Eren C Kızıldag, and Ilias Zadik. Stationary points of shallow neural networks with quadratic activation function. arXiv preprint arXiv:1912.011 1912.0199... 2019.
[GMMM19] Behrooz Ghorbani, Song Mei. Theodor Misiakiewiez, and Andrea Montanari. Limita- tions of lazy training of two-layers neural network. Advances in Neural Information Processing Systems, 32, 2019.
[GRWZ21] Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou. Understanding deflation process in over-parametrized tensor decomposition. Advances in Neural Information Processing Systems, 34:1299-1111 1311, 2021.
[GWB25] Margalit Glasgow, Denny Wu, and Joan Bruna. Propagation of chaos in one-hidden- layer neural networks beyond logarithmic time. arXiv preprint 131100, 2025.
[2BM+22] Jordan Hoffmann, Sehastian 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.15553 155566 2022.
[HNA+1] 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 1712 2017.
[HT87] Trevor Hastie and Robert Tibshirani. Generalized additive models: some applications. Journal of the American Statistical Association, 82(398):371-388 1987.
13

---

[JGH18] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Con- vergence and generalization in neural networks. Advances neural information 2018.
processing systems, pages
[JK 16] Prateek Jain, Chi Jin, Sham M Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming pea: Matching matrix bernstein and near-optimal finite sample guarantees for oja's algorithm. Conference on learning theory, pages 1147-1164. PMLR, 2016.
2KM 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 (rXiv:2001.0836/ 2020.
[LMO0] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):330--1333 2000.
[LM7200 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.
[LOSSW4] 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.01581, 2024.
[LWK++2] Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling laws linear regression: Compute, parameters, and data. arXiv preprint arXiv:2406.08c6 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.
[2HPG+22] Alireza Mousavi-Hosseiie Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu. Neural networks efficiently learn low-dimensional representations with sgd, In The Eleventh International Conference on Learning Representations, 2022.
[MHWE24] Alireza Mousavi-Hosseini, Denny Wu, and Murat A Erdogdu. Learning multi-index models with neural networks via mean-field langevin dynamics. arXiv preprint arXiv:2408.0220 07255, 2024.
[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.
[MLGT24] Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances Neural Information Processing Systems, 36, 2024.
[MLHD23] Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban. A theory of non-linear feature learning with one gradient step in two-layer neural networks. arXiv preprint arX1v:2310.07891, 2023.
[MRS22] Alexander Maloney, Daniel A Roberts, and James Sully. solvable model of neural scaling laws. arXiv preprini 2rXiv:2210.16880 2022.
[MTM+24] Antoine Maillard, Emanuele Troiani, Simon Martin, Florent Krzakala, and Lenka Zdeborová. Bayes-optimal learning of an extensive-width neural network from quadrat- ically many samples. arXiv preprint arXiv:2408.0373: 2024.
[MVEZ20] Sarao Stefano Mannelli, Eric Vanden-Fijnden and Lenka Zdeborová. Optimization and generalization of shallow neural networks with quadratic activation functions. Advances in Neural Information Processing Systems, 33:13445-13455, 2020.
14

---

[3] Arvind Mahankali, Haochen Zhang, Kefan Dong, Margalit Glasgow, and Tengyu Ma. Beyond ntk with vanilla gradient descent: A mean-field analysis of neural networks with polynomial width, samples, and time. Advances in Neural Information Processing Systems, 36, 2023.
[NFLL24] Yoonsoo Nam, Nayara Fonseca, Seok Hyeong Lee, and Ard Louis. An exactly solvable model for emergence and scaling laws, arXiv preprini arXiv:2404.17500 2024.
[OK85] Erkki Oja and Juha Karhunen. On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. Journal of mathematical analysis and applications. 106(():69--8)) 84, 1985.
[OSSW24] Kazusato Oko, Yujin Song, Taiji Suzuki, and Denny Wu. Learning sum of diverse features: computational bardness and efficient gradient-based training for ridge combi- nations. In Conference on Learning Theory. PMLR, 2024.
[PPXP24] Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+ phases of compute-optimat neural scaling laws. arXiv preprint 1rXiv:2405.15074 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.
[RL24] Yunwei Ren and Jason Lee. Learning orthogonal multi-index models: A fine-grained information exponent analysis. arXiv preprint arXiv:2410.09678, 2024.
[RNWL25] Yunwei Ren, Eshaan Nichani, Denny Wu, and Jason D Lee. Emergence and scaling laws in sgd learning of shallow neural networks. arXiv preprint arXiv:2504. 19983, 2025.
[SBH24] Berfin Simsek, Amire Bendjeddou, and Daniel Hsu. Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence. arXiv preprint arXiv:241 1. 1,08798, 2024.
[SJL18] Mahdi Soltanolkotabi, Adel Javanmard, and Jason Lee. Theoretical insights into the optimization landscape of weer-parameterized shallow neural networks. IEEE Transactions on Information Theory, (5(2):742-769 2018.
[Sto85] Charles Stone. Additive regression and other nonparametric models. The annals of Statistics, 13(2):689-705, 1985.
[Tro10] Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12:389-434 434,,444,22 2010.
[TV23] Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. Journal of Machine Learning Research, 24(58):1 1-7,) 2023.
[VBB19] Luca Venturi, Afonso Bandeira, and Joan Bruna. Spurious valleys in one-hidden- layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1-3,, 2019.
[VE24] Nuri Mert Vural and Murat Erdogdu. Pruning is optimal for learning sparse features in high-dimensions. arXiv preprint wrXiv:2406.08633. 2024.
[Ver10] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv: 2010.
[WWZ+22] Xiaozhi Wang, Kaiyue Wen, Zhengyan Zhang, Lei Hou, Zhiyuan Liu, and Juanzi Li. Finding skill neurons in pre-trained transformer-based language models. arXiv preprint arXiv:2211.0733 2022.
15

---

Contents
1
Introduction
1.1
Our Contributions
1.2
Additional Related Works
2
Background and Problem Setting
2.1
Student-teacher Setting
2.2
Training Objective
3
Continuous Dynamics: Population Gradient Flow
Discrefe Dynamics: Online Stochastic Gradient Descent
5 Overview of Proof Techniques
5.1 Proof Sketch Theorem
5.2 Proof Sketch of Theorem 2
Conclusion
10
A Additional Figures
18
Preliminaries for Proofs
19
Background: Matrix Riccati Dynamical Systems
C.I Continous-time Matrix Riccati ODE
C.2 Discrete-time Matrix Riccati Difference Equations
21
Proofs for Main Results
24
D.I Proof of Propositions 2 and
D.2
Decomposition of the population risk...
................................
24
D.3 Proof of Theorem
25
High-dimensionn limit for the alignment D.3.1
25
D.3.2 High-dimensional limit for the risk curve
26
D.4 Proof of Theorem
30
Proof of Corollary and Corollary 2
Details of the Fine-tuning Step
33
E.1
Characterizing the Minimum
33
E.2
Computing the Minimum
................................
34
E.2.1
Proof of Proposition 11
34
Deferred Proofs for Online SGD
F.1
Preliminaries
35
F.2
Including second-order terms and monotone bounds
bound...........................
37
E221 Heavy tailed case
[0,0.5)
37
E.2.2
Light tailed case
0.5
38
16

---

F3
Definitions and bounding systems
40
F.3.1
Proof of Proposition 14
42
E.4
Analysis of the bounding systems
46
F4.1
Lower bounding system
46
F.4.2
Upper bounding system
51
F.5
Bounds for the second-order terms
55
F6
Noise characterization
57
F.7
Stability near minima
67
Auxiliary Statements
70
G.1
Matrix bounds
70
G.1.I Additional bounds for continuous-time analysis
ana.............................
G.1.2 Additional bounds for discrete-time analysis
................................
73
G.2 Some moment bounds and concentration inequalities
76
G.3 Miscellaneous.
78
17

---

A
Additional Figures
t=
0.25
t- 0.5
84-
61
612
23
Entries
-063
V/1
Time
(a) Trajectory matrix order.
(b) Trajectory of entries the Gram matrix.
Figure 4: Solutions of the matrix Riccati ODE in (5.1) with A 2, A 1, 2. (a) To visualize the dynamies under matrix order, we plot the level sets G(t) at times E {0, 0.25, for two initializations: G(0) (solid) and a scaled version 1.25 (0)) (dashed). The dashed ellipses remain enclosed within the solid ones at all times, illustrating monotonicity of the Riccati flow with respect to initialization. However, note that G(t) is not monotone in Loewner order over time, seen from the lack of nesting among the solid ellipses. (b) Entry-wis evolution of Gtt) under random initialization with 1024. The diagonal entry Gza(t) (t) exhibits non an--moottonic behavior, illustrating that solution trajectory Gtt) need not monotone in time.
Population loss
Population loss
10
Width 32
Width -4
Wieth 64
12-4
Width 128
Width 256
Wiath 256
Width
Width
12a
10a
10'
Width GD steps
Width GD steps
(a) Ideal: 11, empirical slope: 1.08.
(b) Ideal: - empirical slope: 1..8.
Figure 5: Population loss vs. compute for two-layer neural network with activation function Her + Hea-
trained with population gradient descent. The student network adopts the 2-homogeneous parameterization (2.2). Observe that after the imitial loss drop due the He; component, the risk curves exhibit power-law scaling where the exponent (dashed lines) nearly matches our theoretical prediction for the quadratic setting 1-2a and unlike the ReLU setting (Figure 3), the loss immediately platcaus after the power-law phase.
Experiment Setting. In Figures 3 and 5, we plot the mean squared error loss for gradient descent with a constant step size on the population loss, using activations a = ReLU and o = Hej + Heg. The teacher model has orthogonal first-layer neurons and power-law decay in the second-layer coefficients with a E (1.0, 1.5). Both teacher and student networks use the same activation function, which normalize have zero-mean unit L norm. The student network uses the 2-homogeneous parameterization:
((W)
w3 1 ((w,, x)) where a E ReLUU-1/V2 0.5
Hei+ Heg }.
3
We set dimension d 5000, number of teacher neurons (32, 64, 256, 512), and learning rate n 0.5/ Vr. To estimate the scaling exponents, we first identify the range of compute exhibiting a linear trend by visual inspection, and then fit the exponent via least squares. The dashed lines in the plots correspond to these fitted lines, and the reported empirical exponents represent the median values across different student widths.
2400, student widths
18

---

B Preliminaries for Proofs
Proof organization. Section B introduces the notations and definitions used throughout the paper. In Section C, provide brief review of matrix Riccati ODEs and difference equations, along with the necessary supporting statements. The main results are proved in Section D. In Section E we discuss the fine-tuning phase for the discretized algorithm. Additional proofs related to online SGD and auxiliary lemmas are deferred to Sections F and G, respectively.
Notation and Definitions. We use [x] = (1,2..... n to denote the first n natural numbers. The Euclidean inner product and norm are denoted by (5 and |1- respectively. For matrices, ||-ll2 and ||-Ile denote the operator norm and Frobenius norm. The positive part is denoted by (z)+ == max 0}. We write fa (a(1) if fa as + sc, and fa < 9a if fa/ 9a O. We use ((.) or ((-) to suppress constants in upper and lower bounds respectively, and we use subscript to indicate parameter dependence, e.g., (.(.).
The symmetric part of square matrix M Raxd is given by Sym(MM { + +M ). For symmetric matrices A, B Rdxd we write A B (or A = if A is positive definite (or positive semidefinite). Moreover, if A and B are mutually diagonalizable, we write AB A
B
We follow the convention that subscripts (e.g.. W,) refer to discrete siscrete-time quantities, and parentheses (e.g., (t)) refer to continuous-ting time quantities. The overlap matrices of interest are defined
(w) W (())()
G o (()U(() O
G. θ W.W, O
Weight Gram matrix
Aligument Gram matrix
alignment Gram
Let Z Rdxr, be Gaussian matrix with i..dd entries distributed (N0 1/d). We define Z Zimm E Imx,, as the submatrix formed by the first m rows:
Z Z Zrest
Z
Without loss of generality, we assume the teacher directions coincide with the standard basis vectors, i... 0, =;-- With this, the initialization satisfies:
Gw ZZT,
G Go Z ( -) - 1:r-
(B.1)
We start with characterizing "good events" for initial matrices given by the following lemma: Lemma 1.
Both cases (a [0, 0.3) U (0.5, co)). For d 2(1), the following holds:
(E.1) 1.05 I Amin Z Z) S Amax Z T Z) 1.05.
(E.2) 1.05 I 2 (0) Go ž 1.05 Zi. TT.
Heavy-tailed case (a [0, 0.5)). For d 2 (1)(1), the following holds:
(H.1) For m S Te log d) uniformly, we consider Amin (2 1 ZT.m) 2 Ea (1-
m
T.
(H.2) For all m S re log 1/2 d) A uniformly, Am (Z ZT.
Es 5d
(1 m 2
(H.3) Amaxe( ZI.r )Tr) v
2r.
+ 1 )=)²
d
Light-tailed case (a E 0,,..)).. For d 2 2(1), the following holds:
(L.1) Pyd I Ami Zi.r ZT_
(L.2) For m (1,2, 5r., [log* 2.5 d), [log d] uniformly, Amax Amax(Zi:m Z Imm)
3(r, Vm)
We define
(E.1)n (H.1) (H.2) a (0,0.5) (E.1) ( (L.2)) a E> 0.5.
Ginis
19

---

We have
exp
exp
2log J),
-
E (0.0.5)
Pl 2
((1/11))
0.5.
Proof. We will use the following:
(S.1) By [Ver10, Corollary 5.35), for m S rs and vrs- - v 2
2
P Amin
(Zi:m
1im
N 1
v
vFa
2
2e
and for m 2 rs and vm T
P Amin
Z 1imm
1
1
122--- -2--
m
vm
(S.2) By [Ver10, Corollary 5.35], for any fixed
P
m Amax
(Z Zi:m)
2 2e
(S.3) By [Ver10, Theorem 5.38]. there exists C, > 0 such that
Amin (Zirr Zire.)
2 11- - CE m.
4dr,
For the heavy tailed case, we consider d is large enough to guarantee
1 -
00| I 6
We have
2-
By using (S.1) and (S.2) with d, V log we can show that P[(E.1) 2 clogd for d 2 ((1).
By (B.1) and (E.1), (E.2) follows.
For (H.1), by using (S.1) with = -Fe-vm Vlogd
we have with probability 1
a
2r, exp ()). for m S r1(1 - -loog" -12 1/2/) d) A uniformly:
2 (1 vingal (1
Amin ZZ Z 1im)
1
Therefore, P((H.1) 2 2r, exp 2logdd)
By Cauchy's eigenvalue interlacing theorem, Am 1Z ITT Amin (Z Zmm). Therefore, by (H.1), (H.2) follows.
For (H.3), by using m = and / = 0.4 in (S.2), we have P((H3)) 2 1 -0.66..
For (L.1), by using (S.3) with 3/2 we have P[[L.)) > 1 0(1/r2).
For (L.2), by using (S.2) with 0.4 we have with probability 1 - (10r, + 6)e 0.16r, for E [5r.] U {[log.. d], flog d], r uniformly:
5(r, v m) <
Xmax Zl. ZT 1.m < 2 (1.4+
d
By union bound, we have the result.
20

---

C Background: Matrix Riccati Dynamical Systems
We begin by reviewing Riccati dynamical systems in both continuous and discrete time, establishing the necessary background for the arguments that follow. For the following, define
Ag
and A = VT
Ae.
For notational convenience, we adapt the abuse of notation:
Ac Ia - expl (A.)
(A, + s
0
lim 6 Ia exp( + +la))
expl
(A)
Id-r
C.1
Continous-time Matrix Riccati ODE
In this paper, we study continuous-time matrix Riccati differential equations of the following form:
Weight Gram matrix: For Tw T
d,Gw(t)
0.5 Tw
(2
(C.1)
Alignment Gram matrix: For Ty | (Tl
0.5 (Gu Gu(tAA (G)
(t) Tu
(C.2)
For = 0, we assume that the ODEs are expressed in the eigenbasis of Gw (0) Go (0), ensuring that the trajectories remain diagonal. The solutions of these ODEs are characterized in the following statement:
Lemma 2. (C.1) and (C.2) admit the following solutions:
(t
Ia exp( (thh/ww)
Á eexp(-1f/1w) exp( (ttp(((/Tw))
-1
Gw(
Ia (18/(((/TW)
Is- ex-exp( (x-exp(-t//Tw)
I.
Gu(()
I, expl (xxp(-iA/To)
exp(-0.5eA/To)
exp(-IA/Tu)
exp( exp(-0.5tA/To
I, - exp( -(A/To)
I, exp( -tA/Tu)
I-- exp( -(A/Tu)
Moreover. (Gw (t)) and (Gu (t))e2o are monotone with respect to Gw 2 and Go 2
respectively.
Proof. One can check by direct differentiation that the given closed-form expressions satisfy the ODEs above. The uniqueness of the solutions follow the local Lipschitzness of the drifts. Monotonic- ity is consequence of Proposition 25,
C.2 Diserete-time Matrix Riccati Difference Equations
In this section, we will study a particular discretization of Alignment Gram matrix ODE, given
G411 G, " (2G, 1,)A(2G, I,) A2G I,)) + +nA.
(C.3)
2
For convenience, we will make a change of variable and define V, G, A. We write (C.3) in terms of V, as follows:
V41 V. V +vV)
We characterize the dynamics of (Vi)ten follows:
21

---

Lemma 3. We consider
X1+1,1 X++122
X1,1
X X1.2
X
I,
0
I, n
+ h
where
and H
X1.2
X
Vo
^²
2
The following hold for all n E N:
(R.1) We have
A
A
Ar,1
= (Izr + n
(C.4)
AA
A
where Ar,11. A,, A are positive definite diagonal matrices.
(R.2) A1,1 + 1 A,22 and A A1,12
Ai, I,-.
(R.3) Form 1, we have A,, A (I, A2) 3 A and A,,22, (I+ 122 J.A
(R.4) If n 1
(I, (I, nAY + -
A Am
nA)+ - (1, - nA) - A1,11,,11
Moreover, if X1,, and X are invertible:
(R.7) For V41 X 111, and V. X2,1 have
V41 V (I, + n
Proof of Lemma 3, We have
I
ni
12r + +n =
(C.5)
1112
+ + 1/ A
Let
[A,
A,
(1er + +HH
A21,
A
Since each submatrix in (C.5) diagonal positive definite, the matrices in (C.4) are also diagonal positive definite. To prove (R. 1) and the first part of (R.2) we use proof by induction. We assume A, + A = A,, and A 12,1 = A We have
(a)
(b)
Ā12141= = =A,,2 + A Am12t1 (A,1 A21,)
A + (I, A2 A
(c)
A + A - + 1/2 A?) Æzi. A A
where (a) follows the first assumption, (b) and (c) follow the second assumption. Moreover,
An1t + A A. + 1/ A + A. + TT(,, + 122 A2) Azı.t
(I, + 2 A, + A2,,) + 1A21,
(d)
(I, + A ) + 7/A 2 A A
where (d) follows the first and second assumptions. For the second part of (R.2) we again use proof by induction. We assume A, Ar,11
A I,. We have
Å 1114 A AIgnoi Azi.e11
(Ar,11 + nA21, (nA²Ar,1 ) + (I, +,+ Ar.12) (11) A1,1 + (I, + +2 AsLi) (Au.22 + A
22

---

A1.11A.112 A1,12A21 = I,
For (R.3), by using (R.2), we have
A (Ar.1 + 12) A2 = 1 + A7,1))
+ ( (A,,
I, > 0
1/2
Ac11 1 + -
A
A.
4
2
The second part follows (R.2). For (R.4), we recall that
1 A,,2 AAA,2 (I, + 1f ) A 71A1,11
(C.6)
1,+1,2 7 + (I, 1イ² A,,2 A At,1, 12 + A,,2
(C.7)
We use proof by induction. Suppose the lower bound for
A, holds. We have A.12
141,22 (e)
A + Ar,22
A
Ar, + A1,2
(
(I, + nA + (I, -
(I, + + +I, -1)
(I + nA
1/A +
(I, + nA)² - (1, -I,-
(L, nA) - nA)
(I, nA)++ + (I, (I,-
(I, WA)+I (4, (1,-
where (e) follows (C.7) and (f) follows the induction hypothesis with that + a4 is monotonic
1+nAz
increasing for yiÀ < 1. For the upper bound, suppose the lower bound for A.u A.,2
holds. We have
A1+1.11
(g)
A + A1,22
A
Ar,2 + 11A11111
(b)
1 + (I, + A (I, )
(I, + A)) +I,
(I, -A) (I, + nA) (I, -A)
3
(I, + nA)² -I, -I,)) (I+
n/
(I, A + (I,-
I1 7 14--AA)+1
where (g) follows (C.6), and (h) follows the induction hypothesis. Lastly if X1,1 and X,+1.1 are invertible,
X X H1111
(X,, 1/ A X
x + nA²) (I, + x,,,,
X12X
[I, + x x n1A
X
X X
X ,,,, nA
Corollary 3. For Vo 2A GoA A1s we define
V V, V/ (I, + V n
A1, A2 and À are mutually diagonalizable, and X1, is invertible for t < 1s E N. we have for
t & t"
G
A
A
A,22 A
A A
1
1A
Au
A A.
A..12
A1
A
+GO
+
AA 1,12
2
4
Ag
2
Aa
where Aut. Ar,22, A.22 are defined with A.
23

---

Proof. By using (C.4), we can write that
Vi AA
A1.22
(A +V))= AA
12
AA A
+ +V)) A
(AA + +Vo) " AAT1
+ A,,2
I, A,,11,,1124
A
A,12A
(AA,
AA
Therefore,
A1 A,2 Å
A2,
Á
A
A1
A
Ar,1 A
Aa A,
A
G.
+
GG
2
4
A2
2
A2
Proposition 4. For some symmetric matrix S, we consider
V1 = Vo + + Vi (I, + Vo)
(C.8)
VV = Vo I, we have V 2 V1, where VT is the next iterate if we use Vo in (C.8).
Proof. We have
V (1, (I, + voo + nsS
17
The statement follows by Proposition 25.
D Proofs for Main Results
D.1 Proof of Propositions 2 and
For Proposition we observe that
G(t) = (t) and U(t)=U(()U()) = (() ((t) Tt)
have the exact same dynamics. Therefore the statement follows. Proposition 3 follows Proposition 25.
D.2 Decomposition of the population risk
The fine-tuning step relies on the following decomposition of the population risk: Proposition For any Q Rr.xx,, the population risk defined in (2.3) can be written as:
R(W,52)
VT. TA
V., W,T,AGG
W: will?
(IAIi GA l2:).
Te
where G; = θ W.W, O is the discrete alignment Gram matrix defined in the previous part.
We observe that both the second term and the matrix WT @AQ W independent of Ω. Hence, the fine-tuning step reduces to least squares problem in the matrix ΩNT in population, which is approximated via empirical risk minimization over a fresh batch of samples. By standard concentra- tion arguments, sample size of NFt poloyyog suffices to ensure that the empirical minimizer approximates the population solution with high probability.
Proof. We begin by noting that W, is an orthonormal matrix. Using this, we can express the population risk as:
R( (WW.) T
W.n W.T
oAo |

---

|
2| |
|
Trnn w, oeo (W) ove w.il?
AAIE
P
Vs
VTs
|
||||
IW,
W +
aN
W, oΛe Wi
|
VT=
By observing that eA0 || || A p we have the statement.
D.3 Proof of Theorem
We let
a [0,0.5)
1ec :- W/TalAAles
Keff
Tall = Kell vr A d/y.
1,
a > 0.5
and
r Ta [ogg2. d. a > 0.5
(0,0.5)
[ra(1 log 1/8 d)
a E (.,
Tu.
a > 0.5.
In the following part, we will establish the high-dimensional limit of the risk curve and the alignment.
D.3.1 High-dimensional limit for the alignment
By Lemma 2, have
I,
exp(-0.5tM)
exp(-tA) )
-1 -exp(-0.5tt)
Go I, - exp( (A) I, - exp(-tA)
(o)
I, - (exp(--AA)
I, - -expp((-th) -tA)
We define the block matrix forms
(t) Guna((] Gt(t) = (b,z(()) Gu
A = Aoef 0
A = Aeff. Ae,22 = A22 0
Az2
where GU (t), Aell E R's. Krm.. The following statement characterizes the meallscales for the alignment terms.
Proposition 6. Gma implies that A(tT 0,) 1[tKel 2 3 oa(1) * limg Aymen and
j S Tu.-
Proof. For = O, since the trajectory stays diagonal and the diagonal entries are monotonically increasing, by using the events (E.2) and (H.2) with Lemma 10 we have the result.
In the following, we will prove the result for O. By using Proposition 22 with (L.2)
2.1 Z 1.r.
ZT
Pore.
0
Go(()) =
0
2.1Z
where
5(1 +
(0.0.5)
2.1 2.11Aax (Ziro. 2 ) ZIr,,) 5
vøl
15,
>>> 0.5.
Therefore,
I Ir..
Gu,n((toc) 1 I.., exxp( eexp(=tAnu -tAolt
(O(r))
exp(-tA.g "xpp(-0.5tA.ff
d Ir.. + Ir.. exp(-tAeo1) I... exp( (tt(1-)
Ir.. Lr..-exp( exp(pttppff
Therefore, by Proposition 36, for j S Tu..
1
A(tTen 0,) 5
1ftheel } oa(1).
+ log' 1 (Nes)
25

---

Moreover, for & (ru. + 1)ah log d r,² by using the events (H.3) and (L.2), we have
(1
a E (0, 0.5)
2 exp(tA22) 3
O
2.5 d)Iry
0.5.
Therefore, for t S (Fu, + log d we have (U,u 2 (t) where
I
G(t) I,., -exp( 1epp--tApp tAll
exp(-0.5tAer)
Ce (1)
exp(-tAen) -1 exp((-0.5t
Ir..
I... -eppppp--00 -(Aett)
d log" d
Ir.. exp( -Aoft)
I, -expl -1A
which implies that for t < (ru. 11
log d T2
1
A(tT eff 0₂) 2
+ Ollog" d) -xaaa- [ttrfttf 2 +
To extend the lower bound for > (Fu, + 1)a log + let us define
to = (Tu. + 1o and A = Aeft (ru. + "I
We have for > to.
O,Gu,1(t)) = 0.5
A Gr,11 Gt, 2G Gu,n(t)
To
(ru Gr, Gu)) A22.
+
Ty
fru
GG,n(()) (un)(())..Gnnn(()) (1)
20
Therefore, for > to, by monotonicity and [BR14, Theorem 38), GU,11(tee) 2 G()) 2 G (to). where
I I,,, Ir.. - expl (1 to Am)
G(I)
(0)
exp(-(1- (o) G(()) I,,,- exp( to) Am) I,..- exp(-(t to off
-1 -eepp eexp(--05((- 10) off
I...- exp(- A
Therefore, the result extends to / >> ln as well.
D.3.2 High-dimensional limit for the risk curve
A_ For Err(t) = |A||E
| Gwr(0), by Lemma 2, we have
- AA exp(- -tAe)
Err(tec)
La exp(- (11A))
+ A, expp exp(-000.55 -0.5lA.)
||A||F Gw
A. exp(-1Ae)
'A exp(-0..5)) .(D.1)
Ia exp(p -tt.)
Vr.
La exp(-tA.)
Ia exp(-tA.
We define the block matrix forms
(t) Gw,12(t)] Gw ( (t) Gw.z2(t)
Aedl 0
Ag2 0
GT
A
A2a
A Acti, A
0
where (1), Actf E Bruxro Our proof strategy is as follows:
Proposition 7, we show that the off-diagonal and lower-right terms in (D.I) does not contribute to the high-dimensional limit. Then, in Proposition 8, we characterize the limit of the left-top terms. Finally, Proposition we prove the asymptotic behaviour of the risk curve.
26

---

Proposition 7. Gmit implies that [G an)l = ou(rs) and = ou(rs).
Proof. We let
A1,11 (1) D1 I. exp(ppAAo... (tAA,111)
A2 exp(-tAe,22
1
D2 Id-r. -ep( 22
Z =
Z2
and
Sn1 S12
= =(
[Alle 1ir,, Zirr + +1 Vix
||ALE
1irr Zz
1
1 S22
||ll Zo Ziri. Vra
JAAE ZzZ22 D22 VTa
where
VTs I,, + Zzg DZ Z2 ||A||r
S =
D + 1ira
Z 1:r,
VT' I,, + Z D2 22
-1
-1
S =
Di Ziora
ZITr
Z Z 23 (Z2Zg +2)
||||F
TT
S22
D2 + Z2
I, Z 1:r. D 11.r
Z
|A|[F
Off-diagonal terms:
By Proposition 26
Gw.12(f) A.n1 -.5tt.. 11) S Ac,22 exp(- Ir. exp( (AA,,
Ia-r. - -expl (1A
=exp(0.5tA..1)
Vra [Allp
Ir,
Z D2 Zg + Z Di Zi:re) Z exp(O.5tAA..2))
We observe that Amax (D2) 3 and
VT A
Reff
By using Proposition 27 with Ginit and
thoff log d write
1
|G (tt.eetTea))
||
O(1)
TuAr.
Amax Zi... Zior.) exp(t>s) (Retf + de eex(((A)) exp(ttx) - (D.2)
| (Reff + 8)2
For the heavy-tailed case (a E [0, 0.5)).
(D.2) < (1.
Σ 1(Tx; S log =} + (1)
Σ
Nell(Ad blog)) oa(1).
rlog² d
pI-a log
iSt
ist
For the light-tailed case (a: > 0.5),
(1) log d
O (1) log d
(D.2)
E1tth. log rers
Σ Xe log d od(1).
<5r,
Lower-right terms:
By using Matrix-Inverse lemma, we have
TTa Ir, + ZT.,, DJ' Zı... + Z, DT Z2
-1
-D + DrS ZZ
Zz
We observe that Amax (Dz) 1 & and Via
= Koff. By using i = theeff log d n., we have
VTs
-1
Gw.zz(tTef)
Zz
I, ZT. Di Zi.r. + ZJJ D Z%
2
TTs
A
|
27

---

0(1)
Z2 (Kott I, +1Z 22) Zz
(D.3)
|
For the heavy-tailed case (a [0, 0.5)),
O (1.
(ID.3)
v
p 2n log d p2220 log = od(1).
For the light-tailed case (a > 0.5),
[I..)) < O Oa.r,
oa(1).
f² f2
Proposition 8. For some let G(0) 1 Zir. and
May (ruy +1)
E [0, 0.5) \ (ja :j N}, a 0.5,
lgga11)
a E (0,0.5)
EE
a > 0.5.
Kig
We define
off exp(-1.bp
Errr, (tsc) =
I, (osp--AAftt
Aot exp(- oft)
Ae exp( + +G(0)
"on exp(-0.5tA.f)
Ir exp(-1A.ff
Ir exp(-IA, -1A
Ir exp(-1A,.t)
Iini implies that
Err,, (1
1
=1
1 2 22 od(1).
||
|
F
Proof. We let
Zirr.. Z Zure.
Z
Aeff A
Zirr Ziru
ZzZ
Z.Z,
Acft 22
where Aeft.11 E R'v, Xru,, Zz E (ru )xr, Let
Aett exp(-tAcftt + Zirre Z
T(tec) T,-- exp(-(Aptt)
and Err(tsc, F) Erry, (luo).
By using Proposition 22 and the events (H.3) and (I.2),
A exp( 1ospp-AAeft.iu 10crs Ir.. Ir.. - exp( -tA
0
d
[(tac] 2 P(tac)
2e r. log 2.5 d
Aeft 22
t
d
Ira-ru,
exp( -tpp-tteil.22
For the upper bound, by using clog d in Proposition 24, and the events (H.1), (L.1) and (H.3), (L.2), we have for t < (ru. 11)a log d
0.2/2 Ta I ru, + Adt.11 (xnieep((11 (ffff1) log d d
0
I.... exp( -tA
T(bxc) > (((ec)) =
1.1/c Ve Lr + expl-1A
1/2 d d
Ir.-re. -op--thi -t
28

---

Therefore, for 1 (ru, +1y",
by Corollary 8, we have
Rell
EEr(tTent I
|rr(tTen D)ll
1 theeff J + oa(1)
|
|
|
J=1
Fur
Σ ==1
(tiettl 2 22 + od(1).
|
2
On the other hand, by Corollary we have
||Err([T off,
T)
|Err((TTr) off, T)
A
1
A
Tuy
1
Fu
x > tNeett) +
2 + oa(1)
|
|
j=1
j= +1
(t 2 x,, od(1).
2
Proposition 9. Ginit implies that
||Err (TToft) )
Tu.
2 (tNefff 2 3/3 od(1),
|
|
j=1
for
tE (0),
E [0,
Sapp. (1)
E (0,0.5)
2
(0,00) :jENN,, a> 0.5,
l [ (1), 0.5.
Proof.
We recall that
A exp( - -1,,111)
D2 = A,,2 exppexxpAAApp -(A(-1,,,22)
Ziara
Dj = I. exp( -tA,,11)
Z =
Ia-ra exp(-tAe,22
U2
and
A expxp(11A
Enr(Iac)
Ia exppp1tA.
A. cxp( 1exppp0.5m00 -0.5tA.)
||A||E
A. cxp(-ttA. Ia exp(-tA.)
-1 Ao cxp(-0..tA.))
ZZ T +
Ia expp(-tAe
VTs
Ia exp(-tA.
Errr, (tac)
Gw.e (tize(tacc)
Gt.12(tae)
Note that by Proposition 35, in the time scale we consider we have Amax (2) I 1 The by using (E.1),
1-0a(1) 2Tst
S Amin (D2) s
ETe
-A exp( - offt)
Errr,, (tsc)
I,. exp( +tAef)
Aot exp(-pp000 -0..5t
(1))
As exp(-ttAett
"A exp(-0055t.
+ Ir. exp(-1Aoff)
Zir.. ZTT +
|
Vry +t
Ir, expl (xsp()1Aff))
I,, exp(-1A,t)
By Propositions 7 and 8, we have
(ryAr)
Err (tT (tTTa)l2
Σ j=1
X31st J22 + oz(1).
A
A
29

---

for
(0,
(ru. +1)"
a (0,0.5)
t
Must
(D.4)
(Fu, +1)
( :j:je N).
a 0.5.
Keet
To extend the limit for >
(Pu. (ra.+1) +1)
observe that
hell
||Err
(t)l non increasing since it corresponds to the objective under (GF).
The global optimum (GF) and the previous item with (D.4) guarantees that for (ror+1)
(r.Ar)
(r.Ar)
Err (tT 1P
Σ
(tief
2
27 (tMen 2 2 + oa(1).
A
|
|
1=1
Therefore, the statement extends to t (Fu, +12
Mell
D.4 Proof of Theorem 2
We redefine the time-scale and effective- width as:
[ra/n
a E (0,0.5)
sc = t/rrllAAll
Keff
1/m,
> 0.5
Toff = Kiff /T | log 4/r..
and
r3 Fu. Mog22. d/,
E (0,0.5)
[rs(1 log 1/5 -0g- d)ddrrj, a (0,0.5)
Ta,
0.5
Fe:
a> 0.5.
We consider the learning and fine-tuning sample size given
a [0, 0.5)
log "or""(I--/ra)
and Np. x
r² log" d.
0.5
log 19 d
We define the effective learning rate and the hitting time Thit follows:
n/2
Thit == {12 2 1120 1
|AiGA
10 log d
Σ
X3
1
|
A
A
j=(r,A1)+1
We note that bounding Thi suffices to derive sample complexity since by Proposition 11, we have
| 1. +
0(1)
R(Wffinal) 1
A
logd'
The main statement of this part follows:
Proposition 10. The intersection of the following events hold with probability 1 os(1/d²) 9(1/r?):
1. We have
2n Tx((1 llog -/o d) (r) log 20d (1+d/re) a E [0, 0.5)
Thit 5
2n r log dog 2/4d)
a 0.5.
For t> 0,
A(tTTff 0,) = 11stNiott J + oa(1) + lima परaाd and j S Tu,
| || GET... A 112 Σ X3 Antteen 2 2, + +u {1))
30

---

Proof. By using Lemma 1 and Corollary 5, we have with probability 1 - od((1dd)) 221/r33)
2n rs - log zd) AT)
log Aloog
E (0,0.5)
Toad 2
dooo 1.5
2n r log
0.5,
where Thad is defined in (F.14). Given the lower bound, by Proposition 14, and the third item of Proposition 15, we have the first item.
For the second item, by Proposition 14, and Proposition 15 (for the lower bound) and Proposition 16 (for the upper bound), we have for Tu. x ru, dimensional top left submatrices Gt,11 and A11,
(Gars exp (2ntAn1) (11))) A1)
12d exp ( (-) +1 (1) = G1,11 3 Cb
od((1, (D.5)
and
| G
122
Σ X2
Carr d
exp (2n(1i) ) - odd
1=1
2
| | E Σ
+ +oa(1AA(((.6))
1.2 d
exp (-2 1-2tmd)) +1
i= (ru, Ar)+1
i=1
Cp r.
for
(rs(1 - log
1/8 d) Ar)
log (dlog" dlogg
ro d).
E [0,0.5)
(D.7)
2n r log ddogg od)
a > 0.5.
where
2.5 11
1 vØ)
a E [0, 0.5)
log
1/2 d. a E (.,0.5)
Cub
C
15,
a> 0.5,
a: > 0.5.
The high-dimensional limits of the alignment and risk up to the time horizon in (D.7) follow from (D.5) (for the alignment), and from (D.6) (for the risk) by Proposition 36. Proposition 21 then allows us extend these results beyond the time limit in (D.7), yielding the full statement.
D.5 Proof of Corollary and Corollary 2
Finally, we derive the scaling of prediction risk under power-law second-layer coefficients. Since Corollary 2 is rescaled version of Corollary 1, will only consider the latter.
Proof of Corollary 1. We will prove heavy and light-tailed cases separately.
(1-B) +
Heavy-tailed case (a E [0, 0.5): We define C ==
We first fix (Cip)
VI-2n
By Proposition 9, for any d 2 app.a(1) we have with probability at least - ol1/P)
R(tr log d) =
1
1
tr Ca
> I+oa(1) +oa(1)
==
=Ra((Ct)&
where we define = ) to isolate the main term and make the dependence on the ambient dimension explicit. By using Aj- = =j-a in the indicator function, we can rewrite
Ra(1)
Σ + #}
We define a sequence of measures supported on (i/r : j E [r]} where pa(t) o j-2a for j = 1.... We observe the following:
31

---

pd converges weakly weakly to limiting probability measure μ supported on [0. 1]. with cumulative distribution function
cl-20
c<
x x21
Moreover, the risk can be expressed
(a((t) = - (1 + oa( [1((1 oa(1))t A 2 XH
By the Portmanteau theorem [Dur93]. it follows that for any fixed E (0, 4).
Ra(t) + 21-20
almost surely as d + co. The almost sure convergence follows from the Borel-Cantelli lemma [Dur93] applied to the failure probabilities.
To extend this result to 9, we observe that by (GF), Ra(()) is non-increasing and inf,20 Ra( 2
(1 - 4 (l-22)+ (1(.). Hence, for all > O, we obtain
(t((t) (1 (1-20) v 20- (l=2a)+
The desired result for fixed > 0 follows by change of variable. Finally, since the risk curves are continuous in the almost sure convergence extends to all f >> 0 pointwise.
Light-tailed case > 0.5): For this part, we consider the probability space conditioned Gsnat which holds with probability at least 1 - o(1/r?). We define
2 =
2a C== (r,2)a)).
j=1
We first fix a (0, (Cr.)²) \ (/a0 j N]. By Proposition for any o2
have,
R(t d) =
1
Σ
A 2
1+a(l)) +oa(1).
A
Xy
t1
(aa((()
By using X; =j= " in the indicator function, we rewrite
Ra(()
1 (1 2 2}}
Σ
A t=1
2a for j = 1, T We We define a sequence of measures supported on N, where pali} x j-2a
observe the following:
μl converges weakly weakly to a limiting probability measure μ supported N, such that
p{j}
Moreover, the risk can be expressed
Ra(t) E
<XI
Since / & N, we have
Ra((() m(( V Vr, ro)o))) 00)).
By observing that p([t, ox)) O(11-2a), the result follows for fixed E (0. (Cr, (Cr,))))\a : N). Since the limit piecewise continuous and non increasing, is sufficient take union over t {0.5, 1.5,... .....,.,, + 0.5} to extend the result for all t > 0.
32

---

E Details of the Fine-tuning Step
In this part, we describe how to efficiently solve the empirical risk minimization problem used in the fine-tuning step of Algorithm 1. Recall that this step aims to find rotation matrix Q e IR Xr, that aligns the learned features with the teacher directions by minimizing the empirical loss over Npc. fresh samples:
Ω2
arg min RRa
Σ ((W, (Ce+).
(E.1)
where each sample loss given by
Tr(s2 T W, (I445 w.))
LWWiS: (I++s. = 16 Ui+s
VT
Let us define A, W, (2 W. We observe that the loss becomes quadratic in the symmetric matrix positive semidefinite matrix = QN Then, the fine-tuning objective reduces to standard least squares problem over the cone of symmetric matrix positive semidefinite matrices: Np.
W.
( - T((SA)))
S, = arg min
(E.2)
SER Xrs S= S= .50
2NFr
j=1
Fi(S)
For the following, we also define the global minimum of the least square objective in (E.2) as:
S glob
arg min Ft(S).
(E.3)
SER"*Kra S=ST
E.1 Characterizing the Minimum
Since the fine-tuning objective reduces to a least squares regression problem over symmetric matrices, we can write
Fi(S) (tgg Tr((S ) (Sghb))))
where L is defined as the linear operator acting on symmetric matrices via
Np
L(S)
Σ Tr(SA))AJ,
2N
which corresponds to the empirical second moment operator associated with the covariates Ay. We note that the operator is self-adjoint and positive cemi-definite the space of symmetric matrices, and we can write the characterization (E.2) equivalently
S. arg min Tr((S (gin)) Sglab))
xey
S=S ,z50
SS0
We define the projection on the cone of symmetric positive semi-definite matrices as:
n( = arg min ||S -SS-Spp S.
SER* X
S=8
In the following, we will show that the operator L is close to the identity, and thus, S, is close to
I o (S Before proceeding, we make the following observations:
We observe that by the first-order optimality condition applied in (E.3). we have
Nr.
VTs
L(Sgtob) = 2N mm1
Ut+jA,.
(E.4)
By the generalized Pythagorean theorem [Bub14 4, Lemma 3.1], we have
|... Π (S )l < |S L(Sgtub)) || L
L(Sglab))
Ft(S.) - Ft (n L(Sg1on))
Tr((S. o L(Sgtob)) - (S) + +o (E.5)
where use Id to denote the identity map symmetric matrices.
33

---

E.2 Computing the Minimum
We define the approximate solution for (E.1) as:
a = (no 3
(E.6)
where S + S1/2 denotes the square root operator on symmetric positive semidefinite matrices. Note that the approximation in (E.6) can be computed by taking the spectral decomposition of L(ggiab)
given in (E.4), which requires ((dr)) including the computation of L(Sgloh). This is negligible compared to the feature learning phase, whose complexity scales as O(Tdr,). The following statement shows that f2 sufficienlly close to the fine- tine-tuning solution Ω
Proposition 11. Suppose Ne. 2 r log' d. Then, with probability at least 1 2d the final risk incurred by WiSt is close to that of the optimal fine-tuning solution:
A
13
0(1)
R(W,St) R(W,..
log d
A
log
E.2.1 Proof Proposition 11
We define the operator norm of La
||L||2 =
sup
|||())|l
SER"x
S-sT
We consider the intersection of the following events:
|| ldll2 I Vloge d
2NF. Σド=1 Uj
1 F
OAO TTTTATW,,
W:
logd
We note that for d 2 (11 the first item holds with probability - - by Proposition 31, where we choose C= and log d. and the second item holds follows with probability 1 d by Proposition 32 where we choose C = 16. Given the events, we have
VT W. OAO W. T,WWWW + (I GAG.A IA
R(W,
7o (Sttt))
Tx
|
F
IA
Vrs
2 W.
(1 A
((Sgla))
W. @AQ
|
I^
log d R(W....)
where we use the convexity the cone of symmetric positive semi-definite matrices in (a) and the second event above in (b). By using (E.5), we have
||S. - N L(S S |L - |d||2|| S. + CoennoLLSSgaan L(Sgtot))l
Therefore,
+ L
Id l
S <
|| L(Sgiob))les
ld
2
and thus,
< 2|| Id] N L(S glgh (c)
15r
S, - o L(Sg1ob))1
||
Idll2
Vlog d
where we followed the reasoning in (a)-(b) to bound ||n o L(Sgtnb)) in (c). Therefore,
1 S.
VTe T,O.O
A G
R(W,S.)
W.
|
A
34

---

2
2
Vra
$ -1s.. S. - No L(S glob 11
no (Sggab))
W.
@AQ W
188
To
|
+ (1 IAAG,A
A
0(1)
(1 I
log d
|
Deferred Proofs for Online SGD
F.1 Preliminaries
We consider
1 n2 Wi.j I(+1) - -11
Σ (00 -1) 1) + at+1 and (WW2
M1+1 ||A||
VTa
where ||x+ ll S.. We use #c-11 == (WW;; (++ and consider
The loss function is L(W;: (0441.94411
मे (Jc+1 ic+1)²
The Euclidean gradient is VL(W,)
4.70 (Ut+1 - De+1 x W. Therefore, we
-1
have
114 Vs.((W.)
(La W.W,) (3c+1 2(+1)x1+118 W..
Vx
We recall that G. = T.W,W,WW.
Then, (SGD) reads
W41 = W. + 1/4
[Ia - W.W,) (ve+1 - Dett 101+1 W.
VFx
Voibets
-1/2
I, + 1//16
W = W411
Vsi Li41 Vielety
(SGD)
Pi+i
We observe that
12/16
122/16
P(1
(y(+1
)o+1)² "W, x4413 (La W.W,)) 24415 W;
T3
T's
/ /6
(yt+1
Bo+1) 21 w.W,) x W, 24+12 W..
T,
Let
1/116 Piti
12/16
W. 2411 12. (1+41 0- -WW..,.)( W.W,) a
441
r,
r.
We define P = (Ir.
12/116
P t+1
-1/2
and since P++1 is 1-rank, we have
72/16 P41
p2 = Ir,
1+ 1+
We let
M, = 0 W,
Tw, and M, = θ W
35

---

We have
7/4 VTx
M41 M,
By recalling that G, = M,M,', we have
G++1 = M M 411 + M 1 (P M,M
n/4 M, M
1/4 θ VTa
r/² o _ V
G
V
VTs
16r,
1/2
M M Put1
16r,
+++1
We have
2
(Ia W.W,) oAO
(VsL441 E, (aLl))))); W. (AW
|||||
Therefore,
2
V
θ (4= NV0 w.
||
+ O
- E. B V
2
(I, (G) AG, T (VsiLe+i Es (Vsce+1))M,
G.)
|||F
Hence, we have
1/2
G = G. +
(AG. G.A - 2G,AG.)
|A|L
n/2
+
Sym (0 T E, (vsL+++1) M,
VTx
v/2
op MitiPu+IN
θ VVLLI411ssLL
16r,
16r,
1 1
On the other hand,
1/4
1/4 4 VsLLt+
Mr+1PH4MM M,
Vilbtt
P
M, +
VTs
VT,
MMP41MM + 7/2
1
Sym @e T
V
VsLL+1 P Ss
VT,
16r,
We collect the higher order terms in a single term defined as follows:
7
1/2
P 2
Roo Ge] =
θ
T
E,
V
S 1+1
0
M,E.
M.
16r,
16rs
1+
1
1
Vsibe+1 Pi+l
Sym
θ T R,
M,T
32r 3/2
1 G741
s
V Le+1 Pe+1
S
E,
1+1
θ.
256
1 ++
We collect the noise terms in single term defined follows:
n/2
V++1 = n/2
Sym
(T)
(OT(Vss Viibr41 - Er (ssbeet)) M,
Vrs
Vrs
n
P141
P441
Mi
E,
I c M
16r
1
36

---

1/2
T
(VirLe+) Virhi41
Ee [VsiLe+1 VsrL
16r,
11"
Vsllit1P
Vs P(+1 1+1
Sym
E,
M,)
32r
3/2 8
1 1+ ++4
1 1 +
7
ViLL++1PP P++1 Vs
Ex
Vs pt1 VSLL
00.
256r
1 + G[+1
1 1 c++
With these definitions in hand, we have
n/2
1/2 M++ vra
G++1 = G.
(AG, CGA-2G,AGAA + Roo [
|
F.2 Including second-order terms and monotone bounds
For C' 1, we define
nd I, and Aut = A VTa
TJ I Vra
Ag = A A
ClIAA|
(F.2)
We recall the definition of effective learning rate 17
n/2 TA]
By Proposition 17, we have
G 22 G. + G T
G 2GAA.
""
C
|| FT LI +
n/2
Mt-1:
(F.3
Vr.
G.A., - 2G,AG,) + 2 2G,AG:)+ G41 + Aus
C
7/2
Gr G.
V2+1-
(R.4)
VTa
F.2.1 Heavy tailed case [0,0.5)
Proposition 12. We consider
[0, 0.5,, =n + 00] and 1 alog d V E..
We define
V 2A GA At, and V,+ G Aur.
For d 2 ((1), we have
A
0.1r log
A > A A A
0.1m- I log d
(F:5)
and
V 2 V.
+ 1 1.1m
V;
+nA Cr " A
VT
V < V
1,+ 1 V+t)
+ +
A A
(F.6
TTs
where the bounding iterations are monotone the sense defined in Proposition
Proof. We first note that since |Alle x xrr- -a for E (0,0.5), we have
|| bd
Vrs
log d'
Therefore, (F.5) holds for d 2 2(1), which implies
0 for all N.
V VV, 122 1
(F.7)
log d
Therefore, the monotonicity follows from Proposition 4.
For the remaining part, we introduce the following notation, K;= A For the lower bound, by (F.3), we have
K 2 K. + (A3, - -(2,, A62)2) C +
-
1/2 A u V
A#.
37

---

By multiplying both sides with 2 and subtracting Ae, from both sides, we have
Vi+1 = V - (V 3 + +nA - -C
7 VTa
A Laa
-1
V 1 1.1n (V, }² I, + 1- 1.1m
n
n
V
+ +
-C ? A _ A
VTa
=V. I, 1- 1.1n V
+nA -Cn
A
VTa
where we used (F.7) for (a). For the upper bound, by (F.4), we have
C L K K. + (A (2K, An, )²) )
n/2
A u A
Vrs
By multiplying both sides with 2 and subtracting Au, from both sides, we get
V = V n(V+t)² nAS, + Cn
A
VTa -1
n Vi+ 1 1.1n (V,t)²
I 1+1.1n Vi+)
+
+ Cn + 7 A
VT
=V, I, 1+ 1.1m v.-)
+1 + =Cn
A Ux+1 122
VTs
where we used (F.7) for (b).
F.2.2 Light tailed case >> 0.5 We introduce the submatrix notation
G
G
Vt,11
Pt.12
An 0
A
G.
1t.12
G
V;
V2,12
V1,22
A22
A
A 22
where G1,11, 11,11, Ani A Rruxrs for ru <. Similarly, we define the block matrices of A
as 1u E Rruxtu and Au, 22. We can write iterations (F.3) and (F.4) for the left-top submatrix as:
G4L1 2 G1,11 + n A I + G.n
- An 2G.112 1,12
1/2
2 - PT. +
11+111
(F.8)
VT
G G1,11 + nI AA,, + Gr,11
2u. 122222
C " Al Pr.t.. +
n/2
1141111-
(F.9)
vr.
The following statement analogous to Proposition 12 in the case a > 0.5.
Proposition 13. We consider a 0.5, r. and
n < dlog² d 2r2t
and ru = flog2 2.5 d].
We define V. = 2A A - A and
V, = 2 (A - In.) G..11 (Arr (A ( - t..
38

---

For d 2 (11,, we have
A11 + 2t log dr > Auril > A11 X A X Ani
0.1
0.1
(F.10)
ru
log
and
(Ac1.l1- Vii1 = Vi Ir_ 1-1.11 V₂)) + AA1.11 - Siutty- In.) -on -
(A11
(Fut1)o Ir..
+ " (A11 - (ru+1)o In.) 1441,11 (An (rot1)a (rotajatra)) Iia) $
1
VF
Vit1 3 Vi + v.t) + + C + TI LARPHLAA
Vra
where the bounding iterations are monotone in the sense defined in Proposition 4.
Proof. We first note that since r3 1 and
|Alls = 1 for 0.5, we have
A F nd
2+a log" d
Therefore, (F.10) holds for 2 (11), which implies
0.1
V 12 VVV ll2 s
(ru + 1)a* for all te N.
(F.11)
Tu
2+a
log" d
For the remaining part, we introduce the following notation,
K,- = [An G.t In.) G1.11 (Aul - - 1.,²² and Kt = Al G.nA
For the upper bound, since A22 > 0, by (F.9) we have
Kt K + 17 2/2 11 -2K 11) + C I +
n/2 VTs
1+11 Ai
By multiplying both sides with 2 and subtracting A from both sides, we get
3 - AAA $
Vt 3 V (VV+ + n Cn2IAA A11 +
Vr'
(a) V,, 1+1.1 (V++2 I +
n
Vi
+ u1
1+
+ +n 1
A
A
Vra
V I... + 1+1.1m
V
+ + 1 11 /r + "
A
VTs
where we used (F.11) for (a).
For the lower bound, we first observe that Gr.11 - Gr,11) Gr,1))-,,123711 2 since it corresponds to the left-top submatrix of G.(I, - Gt). Therefore, by (F.8)
G G.,11 +1 (Ag. G.,IIG.,,
A1, AIi -Gr, -
C 3 A
n/2 Vr.
21
(Gr, Gt,11) - -T,112GT112)
1441.111
(ru 1)a
(b)
m G. (Ai,,11 Too Ir..) Gr,11 )
(A -
C n2
n/2
-
2nGr. (aGGul(A111 -111-777ipp
G.+ Ir.) Gr,11
+ VTs
V2+1.11
2
39

---

where (b) follows by A22 I (rot1ja --- Therefore, we have
1
K = K, + 11 (A66, (rut1)a Ir..² (2K, (Ae,,11 - (rut1jo 1r.)))
- ~ (A111 (ratt)a Ir..)
2 +
1/2
(A11
(rutija Ir.)) V1t1I1 (A11 (ru+1)a I...
VTa
By multiplying both sides with 2 and subtracting Ac..i from both sides, we get
V V. n(V ) n A1, (rutia (,) I,.))
-Cn'l
(nu+1)a IT)
1
+ (A11 TI-- I...)
1141,111 (A Trutiyo I..) 1
(0)
Vi 1 1.1n (V,
17
n I, + 1 ---.mmvv))
+ (A
trutiyo )ra)²
-On Al21 (A
(ruti) I..)
+ " (A (1--1)" Ir.)
U141,11 (A11 [mutijo IT,)²
vr=
V. Ir. + 1.1m Vi
17
+ +A - tratija I,.))
-Cn [rrr (A (rutl)a Ir.)) + 17 (A - Ir..)
(rut1ya I,.)),
Vra
where we used (F.11) for (c). The monotonicity of the update follows the same argument in the heavy-tailed case.
F.3 Definitions and bounding systems
To avoid repetition in the derivations, we introduce the following unified notation:
rk E (r G, E (G,, G..i., Ve E (t,11
where each variable will take its first value in the heavy-tailed case and its second value in the light-tailed case. To avoid repetition in the following sections, make the following simplifications by slight abuse of notation:
AG A - (ru+lyo Ius a > 0.5
E 0,0.5)
{ A, and Arz - An (ru+l)= I... a a> 0.5
E (.,)
and
Auri Annall a 0.5
00,0.5)
AA, a E (0,0.5)
Aus
and Au,
Ani a >> 0.5.
The dimension of each block is ru < r for a > 0.5 and r for a E 0.5). from which readers can distinguish the light tailed case from the heavy tailed case. Throughout the proof, will also use constants Ka o1( and Ö E O(1) that will be specified later. Moreover, we make the following definitions:
Noise sequence. For 24 = 0, we define the noise sequence 24+1 = V + n/2 V
Reference sequence. For T, KaTa Irk. we define the reference sequence
T T, + 2(1 2ka)n (Ac,T
3Kd
Aug T:?
Ka(1 - 2ka)
40

---

Bounding systems. We define the lower and upper bounding recursions as
n(1 + 2Kk)
-1
+ n(1 + 2ka)
A
v++1=1, V, Ix
V
(F.12)
1 - 1.2m
1 - 1.2n
(1 + 2ka)²
n(1 - 2kd)
-1
n 2kx)
A
V+1 V. I +
+
+ Cn
(FF.3) -(F.3)
1 1 1.27
1 1 1.27
2k,)
where the iterates (Ve)tes MEN and (Vi)ten functions of the bounding sequences (Gi)ten and hGr as following:
Ad
K, G.G.A. and V, -2K,
and Go 3 Gn To:
1 2kd
K, = A G. and V. =2K; 1 2Kd
Aug and Go 2 Go To-
Stopping times. We define a sequence of events {Ex
T. 3 3 Kar F n K3g <T, 3 A I K
{j. a (0.0.5)
;
KaTu T. 3 v 3 KaTu" Ti g T 3 A v H I K2
0.5.
We define the stopping times
T (w) = inf (t 2 0 & Ee) A d and Thounded == inf { 0 G V |G.l 2 1.5),
and
T Thad
Thaise A Thoundtd A (120: [Til2 > 1.2ka).
(F.14)
The main result of this section is the following:
Proposition 14. Let satisfy (F.15) and consider d large enough so that Kd S 1 Under the
50-
learning rate conditions considered Propositions 12 and 13, we have for Ö AVQ(1)
GANTar + TeXTae + MANTTa I GENTTN I GINTaN TenToa + MANTON
Before starting the proof, we provide an auxiliary statement. Lemma 4. We consider the learning rate conditions considered in Propositions 12 and 13 with
a E 0.,)
Kg
<
log
(F.15)
logd
a >> 0.5.
The event & implies for d 2 ((1) and t < Toounded A ft: [T, 2|2 > 1.2kg] that
1. 3 1 T 3 AgK A,A
2. A,, + u.A. 3 A T 3.
3. ( 1 24 TrA
4. (A Azn T.Auu
Proof. For notational convenience, we define i. TT v,T," for a E (0.0.5) that
We initially observe that & implics
Aü + 7ル
K
A
(AtmAat) 2
A 1 KA +
I, A. -3A 23 I
K2
1
(ALZ.A:)
Aü üAA ž K3
K
41

---

For > 0.5, these bounds become
A11 11A11 1
K2
An
4
AH
(ARMA)) 3
AA
K2
A11 +
R3
1 aI I
4
K2
4
4 AT K2
(AReAt)) A =
K2
k2 1 Ir..
An 1,A =
An
ru
A11
In the following, we will use these bounds. For the first item, we have
Kd
K&A
Kdr
I, Z ClAAlE nd
I..
a (0.0.5)
Ar - -rAr
kd
Ei A1111 + 4tra" Ir_ +ru C| A
vF,
ad
a 0.5
A11
For the second item, we have
Kd
KgA + Kgr K +r 2 C||A
-r. I.).
nd
a a (0,0.))
Au, Di + Am
Kd
Sa A11
+
Kd
1 T
In + 2 CI| // I I..),
a 0.5
3kaAn,
For the third item, we immediately observe that (A v,A,,, )² A 1 Therefore,
x2 A T. N 3122K, 1g A 1.22k - AA₂ 3
4
For the fourth item, we observe that
(A
A. = (1+
0.1rk-0)
A
log
Therefore
1+ 0.1rk log d
T, A u2 , 3 1125k,A 3 11.25x2rk Aw, = A2
x2
4 An
F.3.1 Proof of Proposition 14
Proof. For the proof, introduce the following notations
S = 2A 2
U.A and č. = 2 U.A. and B. = 2A TAA and B, = 2A T.A
Using this notation, obtain:
B A B, + 2(1 2kz)
1.5kg + 0.5
Ar, B,
B²
+ 10m2kaAA
(F.16)
1 - 1.1n
Ka(1 - 2kd)
2(1 2ka)n
1.5kg 0.5
B41 = B, + 1 + 1.1n
A,, B:
B
+ 100"K,Auu
(F.17)
Ku(1 - 2ka)
Before proceeding with the proof, we observe that the following inequalities hold:
Ar, 1l2 s 1, || Ae, 12 < |
and
||A wq A 122 & 1, || Ang 112
<
0.1 log
0.1
log
These bounds will be used in the following whenever we apply Propositions 29 and 30, without explicitly restating them each time. We will establish the upper and lower bounds simultaneously for rk E (r.
42

---

Upper bound proof: We will use proof by induction. Specifically, we will show that for t < Thad.
2kdAu;
2kgAuu (F.18)
V = V + C: - B, + 1- 2Kd
V
4+1 3 Ve+1 + G++1 Bu+1 + 1 2Kd
Since the base case holds at t. = 0 and Toad
>> O, it remains to prove (F.18). By (F.6), we have
Vi + Ee B, + 2k
(Vi+G:- BB+ 2kd4u1
V 3
Likt
2Kd
1 1.1m
1 2Kd
+nA I Aug +
7
A V2+1 A
VTs
V. (Ix Ixx +
V.
+na + C Auz + ?
Aus A 162
1 1.1n
Vrs
n Vi
(Si -:- + 2kaAuu
n
(Vi + E. - -B.+ 2ko u1
+ I +
I +
1+11
1 2Kd
1+ 1.1m
1 2kd
(9.19)
By using Proposition 29, we have for t < Thad
Lik 1+ 1.11 v.) (5: BG.BB++. + 2k.
(Ve -. Be + 2k
-2k))
)
Lik+ 1+ 1.1n
2Kd
1 2Kd
3 5. B, + 1- 1-2kd
2kaAuu
n
V.
(G.-BB.
Bi + 2kaAu1
1+1.1m
1- --2kd
1
(5 (5- B, +
2kdAuu
Vi
n
( BB
2k
2
+ (1 + 1.1m)²
n2²k
V.
1 1+ 1.1n
1 1 -2kk
1 1.1n
1 1-2ka
2n2/k3
2Ka4m
2
n²k3
2k
+ (1+ + 1.1n)2
G5 (6- B,
V. -.B++
Ve
2Kg
+ 1IIIn2)
2Kk
n
(3 B, AK
2k.
+ (1 + 1.1n)²
Vi
C B +
+ +nnri Ars
2Kd
1 -2Kd
n
2kgAu
n²
+ (1 1.1n)²
Ee B 1 -2cd
Vi (GI-Bi+
Vi
(1+1.In)*
-2kd
for some Õ2 O()) We have the following: First:
V2 + V ( (c- Bi + Ak/ 2
Vi+Vi (6. B. (a-B.. 1 2kd
2ka
V. 4K₂ V.2
(a)
1 1 1-2kg/
(b)
1 1 1.1n
V.2
1.22
where (a) follows by [|Vell2 S 5 and
| | BB+ + 2xaAu
< 2.5kg, and (b) follows by Kd S 50
1-2ka 2
Second,
2
G1 B, Aka
B,+ + 2kd
2kdAuu
+
- B.-B++.
V.
Se B, +
k2
2ka
2Kd
1
-2Ka/ 1-2Ka/
Au
(() 3
(5, Bi+ + 2kdAuj
9
36
+
G1 + B, +
(2: + BB)) + (1 22k
A2
20d/
K2
2Kd
Kg
where (c) follows by Villl S 5 and
||5. - B, + 1-2kA
2u
2.5ka. Third:
-v. E. B.+ + 1 1 2ka/
2kaAn1
2KarAu1
2ka 2
B.+ +
V.- C B, + - 1-2ka/
1 2kr
9n/ /23
+ 1+ 1.1m
(57 + B?)
43

---

4kd
3 ( + (.R)) + BB + B,K,)
(R,Au, + Au, K,) K3) + BB)
1 1-2kd
+ (A E. + (.A..)) - (A B: + BrAu,)+ + 4k kd))
(1 - 2kx) A2
(4)
Akd
(KAnu) + +Au Ki) + 4ka(1 (1 - kd)
K 1 2kd
A
(1 2kd) )
1
(2 -44a) Be +
33
B
Kd
2kd
1
= =2
A
(2
4k,) Aw. B:
3
B.
2kd
Kd
where we used Proposition 22, and the second and fourth items in Lemma 4 in (d). Therefore, we have
(F.19) 3 V.
I +
1
V.
2K
V.2 + 1 (1 - 2ka)n²
V.2 + A
1 1.1n
1.1m
10 (1 1.1 1.2n)
2Kd
A
1
+ Gc-- B.
1 + 1.1n
2Kd
2(1 2Ka)m
1.5kg + 0.5
B:
B₁
+ 1.1n
Ko(1 - 2Kk)
(e)
V. Iix + 111 - 2Ka)
V.
-1 +
n
(AA,, A
1- 41
+ CinIAA1/rsah
1 1.2m
1 + 1.2m
2kd
2k Be+1
+ či+1 + 1 1-2kd
2kgAus Be+1:
3 Vi+1 + 5.+1 + I-2Ka 2Kd
where we used Proposition 30 and (F.17) in (e).
Lower bound proof:
Similar to the upper bound proof, here we will show that for < Thad.
2K
2ka
V. + S + B,
I Ve = VAn1 + S411 B
Ac, 3 V (F.20)
1+ 2Kd
I+ 2Kd
Since the base case holds at t = 0 and Toud
> 0, it remains to prove (F.20). By (F.6), we have
2K 61
n 1.1
(V, +, 1 2 ))
2kaA61)
Vit+ = V, +. +B,
Ix
+ +
1+ 2kg
C1 1.222 + 7
A Vc+1A7
VTs
V. Ii 1 1.1n
V,
+ +nA? -Cn?IAAlBT,,
A Ve+1 A
VTs
Itk .TM
+ 1- 1.1m
111.1111 V,
(5, + B, 1 2kd
2kAAe
I 1- 1.1m
1
V. + S + B,
2ka
1 2kd
(F.21)
By using Proposition 29, we have for Thud
Ix + 1- 1.1n
17
V.
C + B,
2k²AG,
(Int 1- 1.1n
17
(V, + +C, + B,
2Kd
1 2kg
1 2kd
- 5 + B, 1 2kd
Ak.
n V,
C + B,
2keAc, )
n n2K2
V
1 - 1.1n
1 1 2ka
-1-1.11)
2KdAei
π
2k
2
C, + B,
V
(, + B,
1 - 1.1n
1 + 2K,
1- 1-1In
1 2K,
44

---

2n²/k3
2kdAc1
n2²33
2keAes
<, + B,
V
S + B,
V,
(1 (1-12 1-IIn)
1 2kd
-11-1I1m)
1 1 2kd
n
S. 1 2kd
Ak
Vi
S, 1+ 2Kd
Ak
-n²OAAc
(1 1-1.n)
11²
2krA6
3
n²
2KoAe
+ (1- 1.Inn
C, + B,-
(1-1..1) Vi
(, B,
Vi
1 2Kr
1 2Kr
for some 82 = =(1). We have the following: First:
2KaAe1
2k
(
V - -, 5 + B.
V, +v
B.
V 2 -32Kk.
1+ 1K2Kd
1+ 2kd
(g)
1 1- 1-1n V?
151-1.21
where (f) follows by VIV 12 S 5 and
15, + B,
2krdr
- 2..5k, and (g) follows by Kd
I+2ka
2
Second:
2
2kaAe,
2
2caAe,
2kgAe1
5, B.
+
5
B.
Vi
C, C.
1 + 2kd
+ 2Kd/
1 +2dd
(,
2k
3 (b)
-3
2 + B,
2kdAe
-9
G + B,² -36A
I I+ +Kd//
K2
1 2kd
kd
1
where (h) follows by IIV, 112 S 5 and
- + B,
2x
I+2Ka |/2
S 22.5kd Third:
2K S
2kgAe;
Vi- -c,
2kQAc 2
V. C, B.
+ B,-
1 2Kd
1 1Kd//
1 1 2Kd
9n/ 22
(s +B²)
1 1- 11.n
4kd (K +
2 -2 KiS, + t,,K, B.K.B,BB.K.
+ +B²)
1 2Kg
4ka + Ka)
(AnS + S.,.. + (A B,A.))
(1 2ka)²
(9)
4Kd
4kg(1 + Ka) (1 + 2kx)²
2 K + 1 2kd
K,Ar, + K,)
122kd
+ (2- - Aka) B,
3 +
B²
Kd
A,
2
(3
V?
21
(2 4K, B,A,,
B
(1+ 2ka)
Kd
where we used Proposition 22, and the first and third items in Lemma (i). Therefore, we have
(R211) 2 V.
I, + 1 - 1.1n
1 V,
2KM
V2
(1+ 2kz)n²/15
V?
2Kd Adt
1-1.1 (1 (1- 11.1n - 1.2n)
1 2Kd
A3 -
11
+ S + B,
I 1.1m
I+ 2kd
2(1 10--20 -KK)m
1.5kg + 0.5 B?
A A,
1 1.1m
ka(1 - 2ka)
(1)
(I, [+++
+ n(1 + +2Ka)
V, )) -1 17
A2,
-OnilAl(rraci) ) - -c411
2 V,
+ - 1.1n
1 1- 1.2n
1 2kg
2kd AGt
+ B B
1 2Kd
45

---

2Kd
V44 + +((+1 + B 1 + 2kd
A
where we used Proposition 30 and (F.16) in (i).
F.4 Analysis of the bounding systems
F441 Lower bounding system
In this section, we consider (F.12). For notational convenience, we multiply both sides by the factor
(1 + 2ka) and use a generic learning rate 17, i.e.,
V ++ V (T + n +n + (A Cnl CnIIAlBr.Ar.) where V. 2A G.A AG.
The main result of this section is stated in Proposition 15. To establish it, we first prove an auxiliary result, Lemma 5. For the following. we define
A A
Au. A
Iik
1.1kd's
2 CnlIAlBBr,AA diag( (iig(()))==)): D2 =
I
By Corollary 3, we have
G. =
A6
A
A
1 14
Agg
À
A1,12
Itk
Aei
+ +Go
AA-1
1,12
-1
A1a
Ar,
Ata
A
2A,
At
(F.22)
where A,, A,,12, and A,22 are defined as in (R.1) with &. For a = O, we will consider (G, heN in the basis of Go without writing explicitly, which will imply that {G, JIeN is diagonal due to the rotational symmetry for a = O.
We further decompose (G. and related matrices to isolate their top-left submatrices of dimension rk, {r., Tu. }, where r. < and Tu. < Tu which we will denote as rk, < rk. The decompositions are follows:
G
G2,12
Ån
Dr. D. =
Zirrk. Zz
G.
G
G.
0
Ag2
0
Dt.2
Zi.tk =
where G.,11 Dr,1, Ån
Rrr. xtk. We define
1.05 Zirkk TT + Dr,1
1.05d 1rrk. ZJJ
T D.
Z
lirk Z
1itk
1.05
Zz Z
1.05 2 Dr.2
l:rk. 1.03
and
(T 12
12
(T, )22
whenever T, is invertible. Lemma 5 is stated as follows:
Lemma 5. We consider the following setting:
E (0,0.5)
E (0,000)
<
Kd 3.5 d'
dr log 4d'
log
1
1
0.5
rs xx
n &
d 2+a log d'
Kd
Tu log 2.5 d"
Ginit implies the following:
For and K 5 rk. S rk, we have for nt < 3// (K + 1)at a log
[dlog'
T,
A A
A
A,12
Itk
1.2K
log d-
0.5r.
Ma+1
K
D
Tak: Di2
In--th.
d
log d
dl 1.g
46

---

(r-(1-110))))) log z' d) r] and Tu. Ts. and mi S (rk,, 1)a log (dlop".2) we have
For T4
Ar,22
Itk
Ciry d'log at
A,,12
=
+
Cuty d rtk
00,
(F.23)
where
16
a E [0, 0.5)
2.1
1+
1
2
a E (0,0.5)
C
and C2
vP
1.1r
Vlog
1.3
a > 0.5
2,
a > 0.5,
Within the same time interval, we have
r
12
A
A,
A1.2
2
Ipk
+
Cira dlog 1.3
0
Itk.
Cara I Itk-the) Toog a
0
1)
(F.24)
For >> O, we have
Di,1 + b/ Zink. Zrrrk. )
1
(TT ) 3
=1 for 0.001 > 8 2 log & d
r+ = [rs(1 6) A Ar and nt S (ra(1 (5) Ar) log [dlogh d)
a E (0, 0.5)
Tw. Tss and nt S fr log |llgg
a <> 0.5
provided that
d2 lg(1) ((l) (2.5a a E (0,0.5)
a > 0.5.
Proof. For the first part of the first item, by (R.2), we have
A
A,
A,,12
Lik
17 -1 AA
1.1kar,
(a)
A
82
-1
Á
A,,22
A,,12
Inn
1.2kgTs
D.
2 A
I
Ink.
2
d
2
d
where (a) follows
<<
Kalla Moreover, since A Å 2
Tog a Like by (R.4), we have
D1. 1
log2d (
a))
(Irk-th, - n1222)
1.3K In--sk.
(F.25)
(In--I + -mAz)) (Irx-th. - -1A22) )²
We observe that
(In-i - -nA2))
Iru-sh.
LIk-Ik, + ndzz)² (In--n. nA22)
exp
21n
Iik-th. tk,
1-nAm
(1+27rk, 9)( K+1
Ts
Itk-tk,
dlogg 1.5
[++1
0.9r'
I tk,
d log 1.5 d
where we use ne < [K 1) log (dlog" dd in (b) and 2 (2(1 in (c). By (F255, the first item follows.
47

---

For the second item, by Proposition 24 with E loga for E 0.5) and E we have
loga d for >> 0.5,
1
A
A
As,22
At.12
1.2KaTs Ixc
8 i Z
0
T
IPx +
2
d
1.05
0
-c I-
22
For E 00,,. since
log by (H.1), we have
1
1.. Z
1.2kdrs Ir. =
T3 1 I.
1.2kdrs
Ir, log" d
1
To I,..
1.05
d
dlog' d d622
d
Similarly by (H.3), we have
-
Zz
1.2kars ---r, = 1+
1
dlog d --rr.
2.1r,
1 - E 1.05
d
For a 0.5, since Kd
and ru [log2.5 d), by (I.1), we have
Yu lox d
1.2KeT's
1
1.3 Vlog
Zir. Z Zirre.
Ire. dlog 4.3 d
Irae
1.05
d
1.1r
Similarly by (L.2),
1
1.2koTs I
-2r I -u. d dlog" d
Z
I 1.05d
d
Therefore, we have (F.23). By Proposition 25, we have (F24).
For the last item, we have
T )11
1 Zirkk. (Ir, D 1.05
1.05 1.05 I, D2 Z3
Zyitke
(F.26)
For E (0,0.5), rf., =, the statement follows. If not by the first item, for K = 1(1 v8)rel
and r. = [r. (1 8)1, we have
+
1 V8
K++1
<
1
<
+
51- 21-00.9V8
+ 1-
8
r++1)
Therefore,
0.5r,
1-
(d)
0.5r,,
d
log
1/4
(c) Ts log d
Dr,2 2
I--r
dlog
dlog
1.5 d
d
where we used d 2 Π(1) V e2p52.5 8) in (d) and d 2 a1( in (e). By (F.26) and (H.3), we have
(2.5a
statement for a E (0, 0.5). For a 0.5, K = r. = Ts, we have
K +
0.5
< 1
$
r. +1
To +1
2(r, + 1)
Therefore,
0.5r,
1- 2(s+1)
Ts log d
Dr.2 2
I
dlog 1.5
for d 2 Or, (1). By (F226 and (L.2), we have the statement for a 0.5.
Proposition 15. Let
G (1+ + 2ka) (Go
KaT's In))
Under the parameter choice in Lemma 5, Ginit guarantees that:
48

---

We have Q1 1i0-loog log r d) Fm 3 G, whenever
n/ 2 (1 log =d) Ar) log dlogt ))
E [0, 0.5)
2r log dlogg
a 0.5
Let Alibe the rk, rk, dimensional top-left sub-matrix of A. Given 0.001 d log and
rk, = { [ra(1 6) A rrl. rs jo have
G1111
log d
1.2 d Ta
exp
An/A11) +1
and
10 log
2
| G
Σ X2
1
exp (-2ntt)) +
Ar)
1=1
Cs
for
1 82
a E (0,0.5)
[ss(1 [1r(1- v8) A
log
dlogg 2d a E (0,0.5)
Cb
and nl
y,
15
0.5
zrz log
dlopt..0 d Px
a 0.5.
For ò = log d, we define
23+ 3/
| - 1olE-IIAtOO II 2 0
Σ [=(rAr)++1
To = inf
log d
Then,
2n rs(1
log + Fd) (r)r)
log
20d (1 (1+d/r))
a E [0, 0.5)
Tio S
20d log
2n ' log
a > 0.5.
Proof. For >> 0.5, we assume that d is large enough to guarantee that observe that
1
1.3
> 0. We
1.1r
Vlog
A- A
AL.11 A,.12
Ixx
A
A (A-Ay)
Ae.
+
+G, TT
2
where we used (E.1), Ar, Ae, and n/ |
< Kata AE.
For the first item, by using rk, fr. [r. loo 7 A Arl, Tu. =r.). we define
Ciry Lik. d dog
and Dos A Drs
DIo =
Cary a alog a Ink-tk
A
We introduce submatrix notation for block Boock-diagonal matrices. Specifically, we write
Ar,22 + Trk T+x),, A
D DIs
A A
and
+ In
D
0
AA,22
+
I
A
where the block dimensions of each submatrix match those of Dis. We start with proving the lower bound part. By the second item in Lemma 5, we have
A
((A::
A
G, z 2
+
Itk
A,12
(A,11
In
+ +2D
A7,12 V
Ag
Ar12
A
49

---

Ag
A
Arz
Nez
A1,22
((A1,2
A&
A1.12
+
1i
A
A
Ink
+Di10)
Ar.12
V
Aez
(F.27)
where we used Ar, > Å in the second line. We have
A 12
Ar,22
Ix
A
Ims
+ 2Dz
A 1,12
1,12
A1,12
(A,,2
(4.12)(AA2))))
Ar.12 + +2,1) I
A1,12( (,12(Ar,22 1,22
Ar,12 12
(a)
2Dtb
Au,22 + Iik
AG,22
A.,2
Lik + 2D16
Ar,2
2Da
A1,22 +Ia))
A1,12
Ar,22
Ix), +2D16.1
Ar,12
(F.28)
2u. A1,12
Ac,22
+
I
22
Ar.22 Ar,12
-Aa +2 +2,
where we used A?,22 - A2,12 > Ix (by (R.2)) and Ar,22 Ar,2 +
2D A6,12 > (by (F:23)) in
(a). Since 4r.2 A.,2 In > 0 and D > 0, it is enough to look at the bottom-right submatrix in (F.28)
for the lower bound part. We have
2D
As,22
+ Itk)
2D
Ar,22 A,,12
+ Itk
A,,12
22
(F.29)
A..2
Like
+
A1.22 A.
+ Its )
-2 + 2D,02
A,,2
22
Note that by (R.4),
Ar,22
2(I + *1A22*
A
+ In
)
2 (Irk-rk, + *nA2)² - (I - -1A2)²
2(Irk-thh - -n² exp -2t
> 21 +
I (Irk-tk. ^)) exp (2tm
(b)
2 (2
0.9r,
Iik-tk.
dlog 1.5
where we use nt < (rk. + 1)a log dlogti'd in (b). Hence, for d 2 2(1)
2 +
dlogt ))
0.9r
D (c)
12D
(d) -15C
(F:29) = 0.9r dlog
I rk.
(F.30)
Ink- + D
d log 1.8 a Ink-tk.
Pq
log d
where we used D > -1.10r I in (c) and (d). The first item follows from (F.30). dlog" d
For the second and third items, let A1.22
denote the rk, rk, dimensional top-left sub- matrices with rk, {r. Ir, (1 8) rl, }-}- By using the third item in Lemma 5,
+ Iix 11
A,,22
immediately observe that for a > 0, G. ž 0 and
2Chr, (A1,22 + Itkk
(e) (1
10 )
d
Ai,12
G m
(F:31)
log d
A
A.,2
In
+
20nra I
d
50

---

for
1
8 E (0,0.5)
ro vō) ^r)
log
dlog' d
(0,0.5)
Gb
and nt
16
15
pT: > 0.5
2 log
dlog'
0.5,
where we used Ae, = A = 1
0.3
Ae, and followed the steps in (F.27)- (F.28) with (H.1) and
log"
(L.1)) to obtain (e). Then, by (R.4), we have
1
20rr
A,,2
A.,22
+
Lik
Lik.
2
A.11
Irk
+
20 Itk.
1 d
Un. (nA,) +
Iik.
A..12
Ch
(In, +nAi)*
Iik.
1.1 d
(-21LA1) + Itk.
exp
Consequently, by observing Å - Ad, Cn and using the lower bounds for Ac, in Propositions 12 and 13, we have
10
G1,11 = 1.2 exp (- A +1'
lo
Cb r,
where A11 denotes the rk, rk, dimensional top-left sub-matrix A. Therefore,
rk.
1 10
2
| | 11 (Ik.Ar))+
Σ
log
(F.32)
1.2 exp 2m( Cb T2
1=1
which proves the second item for 0. Moreover, since (F.22) is the eigenbasis of G.,. the arguments in (F.27)-(F228) and the condition in (H.2) extend (F.31) to a 0 in the eigenbasis of the Frobenious norm is basis
Go for 2 2(1). Given (F31), we can extend (F.32) independent.
For the third item, for 0.5 and 2 2n log 20g 2 Yo
), have
X J
A log3 d
(F32)
Σ
X2
(=(rAr))-1 logtd
(r,AAr)+1
which gives us the corresponding bound for Tib-
For a E (0,0.5) and t 2
1 (ra (1 log dd A A) log
20d 20g (1+d/re))
we have
2n
AaAr
(F32) <
X2
Σ
i= Arr
(= 1-log 3 d Arl+1
Ir. (1- Arj
2
X
Tog d
1.2 exp (-2 +
3 A
X
log $ d
+r(rArr)+1
which gives us its bound for Ti..
F.4.2 Upper bounding system
In this section, we consider (F.13). For notational convenience, multiply both sides by the factor
(1 - 2k.) and use a generic learning rate n, i.e.,
V4+1 = Vi(la + - + (A +
where V. = -=22A,.. G.A., - -A,.-
The main result of this section is stated in Proposition 16. To establish it, we first prove an auxiliary result:
51

---

Lemma 6.
The following statement holds:
The reference sequence satisfies T; = kar= In and {t 2 0: [T: > 1.2ka) 00.
d
For Tu,
2rs, we have
Go 2.2
I, 2 (1 22aa) (Go Kar= Ir)
[0,0.5)
(F.33)
Go
2r, Tuue
= (1 - 2ka) (Go,11 + Sata Ir.) a
> 0.5
ra Ir ru.
provided that Gimit holds.
For the following, we introduce T.
Aug 13kx+1) Tt. Note that for 2 2((1.
we have
Ar ka(l-Ka)
T++1 = + 2aaa--kk)nnaa Te T:: Lik - Fi)
Kd
As,
T.
and
3 Kalik.
(F.34)
1.1 Auz
T.
By Proposition 34, we have
1.1 A T exp (2nt),) 2 Pr.
(1-2x (1-2x))2md( Ae 0.1--0 1+2(1 -2ka)nd
1 A To.i exp
log
0.5)
1
2
(1-2ka)2nt d:- Tru 11 logty
1 To.i exp
a: > 0.5.
142(1-2ko)1d:
(F.35)
Proof of Lemma 6. For the first item, by Proposition 34, we have
T. z To - To
Kd''s
Iiks
where we multiplied each side with ka(1-Ka) Ac, for (a). Moreover, by (F:34)((F:5), we have 3ka+1
Auz
T, 3 K,J 1.11& {t 0: T 1.2kg)
The second item follows (E.2) and (H.3) (for E [0, 0.5)) and (L.2) (for >> 0.5). Proposition 16. We consider E [r,ru), where r. [log 2.5 d), and
1
a (0,0.5)
+ p (0,
< dr 1 log d'
Kd
log d'
1
0.5
rg 1x
n < dr log d'
Kd ru log 2.5 d
If Go are taken as in (F.33,, we have the following:
(GihneN is diagonal and satisfies
l In GG41 3 G. + nn( + Ka)A.,, G. + (1+ K.)G - -G.AAn Gi) 3 1.11
For E (0,0.5) and d 2 l(1), we have for t _ log ddoggt'd
2n
-T G. 3 11 111++t²²
for SisL.
- [1 Gj-1) T 1
5.5 1t #
(2nt V y I,.
Kd
-G, 1 (1.1Go exp (2mtA) A I.) oa(l)
52

---

- -A - TMAG,A) Eist (1=26((+)++) exp (2n1d:) ) -oa(1).
a 0.5 and d 2 9r, (1), we fort 2n log dlagg
- G 3 26.4n/
I,
Kd
- -T, [nE Gj-1) Tn 3 16m= (2r,) )a log rl
-G, 3 (I. exp (2n1A11) I.,) od()).
- Ann - TM Gr,11 An1) 2 Di= X3 (1 (1- 12. exp (2nt2:) + Eier -1
Proof. Given that I = G. N 1.1 we have
G++1 m G. 1] AA., G. + G.A., 2G,A,,, G.) 1.1TT/AAI1..
(6)
3 G. 1 (11 Kn) G. + (1 (1+ - 2G,
(6)
G++1 - G. + n (Au, G. + G.A., AG. Gi) - |
G. n ((1 (1- A G. + G AG G.)
where we use 2A us 3 (I,+VVV) in (b) and (d). By Proposition 34, we have द Ix 3 G.+1 3 1.1 Ixx. hence, the induction hypothesis holds. Therefore, we have the first item.
= 2A in (a) and (c), and we use n/ A A < Kark-o
By using the first item and Proposition 34, third items that
write for the given time horizons in second and
G. Go exp (2(1 + ka)ntA,,) (1 + (1 + ka)) ITx)
( (1.1Gr (2ttA) A Ix) 2
(F.36)
1.2 (Go exp (2mlA) A Ix).
where both upper bounds in (F.36) are valid and will be used in different parts of the proof. The third sub-items immediately follow from the first bound.
For E 0.5), we have
1 (1 A To. exp (2nt):)) Tr. 2 (Ka A To exp (2mt\:)) )
Tuu 3
(e)
Tr, 2
Kd (1
To d
exp (2ntA:)): )
4
where we used To
Kate d
In in (e). Therefore by (F.33) and the second bound in (F.36), we have for
j <t
1.2 I^ 1 +t2/ 2 2.2r. exp (2nt
G3a Taa
11
1
<
1+
0.25ka A & exp (2nth:)
kd
Vp
On the other hand, by using the second bound (F.36),
2
Eド= Gj.ú
11
(1
VΦ
n
E ex=eex((nnxxx))
Teu
Kd
2 exp (2m(2;)
5.5
1
+
1
2n
lon <
VP
x. 2nt,
xe
<
Kd
2n
log
53

---

5.5 [1 +
vF)
S
(2ne V v
Kd
Lastly, by using the first bound in (F.36), we get
2.5 2.5(1+ (1)
| - TM(AGAA)
x2
exp (2n(1 A1
For a > 0.5, we have for i S 2r, log-d d and 2 (1):
ni 2 (1 Tu.s exp (2nt)))) = Ti, 1 1
(ka A To.a exp (2nth:)). )
4
Therefore, we have
0.25(1 A &/ exp(2)())), i 2r, log a
Teu 2 Kd
i i> 2r, log d.
On the other hand, for nf S f log( d d) and i > 2r, log - d. we have for d 2 2(1).
r log( dlog d
Gin 1.2 (Go,s exp (2ntAr) A1) 1.2 Go,teep Therefore, for nt S 2r2 log( dlogg )
^1
s 1.5Go.
rg log d
1.2 (1A 5.bry exp (2nt):))
i S 2r, log _
G j,8s
0.25KA (1 A & exp (2nt):))
Tri
d 8.25r
i > 2r log +
kdT=
d
26.4ru
Kd
Moreover, for n/ S fr2 log( dlogt )
To
17 (A 4 (xp(2nAA))
26.4r,
1-1 11 1 GjAúi
i S 2r, logad d
Kd
(1 4 exp (2n()s))
Tra
d 8.25ruts
i 2r, log + d and i < 2r, log
nt.
Kdl's
d
log - A;
13.2r
2nt S
Kd
2nt,
otherwise
13.2r
15ru (2r.) log d.
(2nt (2rx)² log d) S
Kd
Kd
Finally for nt < fr2 log( d'ogg"dd d) and d 2 (1), by using the first bound in (F.36),
ro
|1 1/- -Tr(An G.l
x (1
12. exp (2nth:))
d
2rx
X? (1
12.1r,
exp (2ntAi) )+
+
Σ X²
6.0 d
cxp (2nthh) )-- -2n
d
#1,+1
1=2r+
( Fx
12.1r. exp (2nt2i)) + (1 log d
2r
xp 1
12
im
54

---

+11 6.05r, log v2 d
13
C3
1-
v2
Σ
-
A
i=2r++1
x 1 1n, exp (2nt2s)
(1-6.056) 6.05r, log log d
v2
Σ
x
+
i=1
(r' + 1)2+2a
2
log d
where we used the bounds for d in (f).
E5 Bounds for the second-order terms
We recall
112 T Eg V
RGo[Gr] =
16r;
n²
M,E.
PM+1
M,
11
Sym
E,
e+1
M,
16r,
1+ 9+1
32r 3/2
[+1
1
VsrLe+1 P S
+
UE,
E
A.
(F.37)
256r
1+
Proposition 17. For 1j < d 1/2 there exists universal constant C 0 such that
L ( r.
G.t... 1 G.. SC
n [ G. r2
Ts
Proof. We bound each term in (F.37). In the following, denotes generic unit norm vector with proper dimensionality. For the first term,
E2
L V
= II W.W,)) E. [(16+1 01, x 1 (Ia w.W,T) e.
We have
E, (1141 W x (u. x01) s Cr..
Therefore,
n²² θ TE,, E, V o CT
0= 16r;
For the second term,
P M,
M,E,
1 2+1
(Vr+1 - 00+1) I1((1a (11aa-Wa) W.W,)) 2441 1 24418744 W,
M,E,
M,
1 G4
We have
(M441 8041)31((13 W.W,) E2
2 11 (v. W,
WTT 2 2 Cd.
1 1 +
Therefore,
03 n/2
P
M 3 Pd
M.E. F
G
16r,
1 22
55

---

For the third term by using Proposition 22,
"1
V si Pett 4+1
Sym
+ EE
Mi
32rs
3/2
c+1
3
11
+ TT
Vs P 1+1
Ex
P41 V
+ + ndd
G.
r3d
1 1 G41
1 + c+1
2
We have
V. L1+ Pet 1+1
Ee
1 + G/
+ (Ia
W(W,")
(J++1 Dc+1) + c+11
E,
- -(la--,w;)) 2+ 2 W. a 241144444411 We
Then, by using
inequality, we can show that
[1++1 - )1t1)
E2
11(Ea W:W,)) æ++1
1 W. a
Wi
S Cdrss
1
1+c G+1
2
Therefore,
1 OTE, En
Vsibi41P441 1 +
P V 1 + c7
Es
2 Cn Gt).
red
We get
Sym
+ E,
V st Lut
P411 1 2
M,
(''d(L. G.) G.)
L r
32r 3/2
By repeating the argument with the lower bound in Proposition 22, we can also show
17
Sym
+ TE
V L.t1 H+1
M2
-c (nAd((, -G.) G.
n'd G.)
32r-/
3/2
To
For the last term, we write
V LI+1 P++1 V L
T E,
2+1
+
1 E7t1
T
-).WW)
(ve+1 - (c+1) 1 1 + ctai
x Es
W,, (1 (..,. 11 Ya-www,) o.
We have
(1t41 ve-1)
Eg
W. x 11 w.w,T) o 11 (0, s CCdr.
1 1
Therefore,
17
V PILinPPi 111
0 θ Te,
c = Ca/d(I,- Gi).
r?
1 1 E
By using G, > 0 and 7 < 1/2, 1/2 the result follows.
56

---

F.6 Noise characterization
To prove the noise concentration bound for both the heavy-tailed and light-tailed cases simultaneously, we introduce some new notation. Specifically, we define the submatrix notation:
[M.]] M
O W
2 and M.
6 W.
where O Rd and Mr,1 E xr. We note that Gt.11 Mr,1M, To unify the treatment of the heavy-tailed and light-tailed cases, we use the following notation to represent both cases:
: (0, M, = {M, M
With the new notation, we have
n/2
1/2
V++1
Sym
(oT(VsiLitt ViLLi41
E, Ve M.
V VTe
1p2 M,
Pi+1
Pi+1
Et
M,
16r,
1+
1
[1
T
(VsLLe+i Victi41 - Es Vsite+1 Vsst
16r,
1/²
OT
VslLi+IPt E.
Vsi P(+1 1) Mj]
Sym
32/ 3/2
1+ 1+
1 1 1
VsiLi-1P1 Virlitt 1)o.
T
E,
256r 8
1 1+
1 +++1
For rk E (r, and Ti, T2 E Riixik be deterministic symmetric positive definite matrices, we define
I2 S 2 -G)
Ar+1 (T, = V
Ltd
B,41 (T) =
T.M.P M, T3ll,
[M(TPG))T((TGG.))
2
I,'r,
C++1 (Ti,T2)
BI V V θT, 1 و GT G.))
dr,
De+1 (T)
12 Feti (Ti = TO P 0Tg
7/ T V
2 Gi)
_/2 2 VT(TT (T)) (T=))
L L'dr?
We start with the following statement: Proposition 18. Let e == (ye+1 - ).+1). There exists a universal constant C > O such that for
2 28(18 + o), the following statements hold:
L/e
We have P. [A++1 (Ti, T2) n fleet1/ s 2 1- 2eivst Moreover.
E, (Sym T M.T.)) )²]
CCIITT (Tx - -G)) + ((T((I*~G))
2. We have Pt [B++1 (Ti Tb) n f|e,-11 < 4} 2 1 - 2e(veto), Moreover,
E, [Sym (TiM,P M, T:) )²]
3 cd TTT
57

---

2 1 2c (v Moreover, 3. We have Pt [C++1 (2) n flet+1 & 2
Es (Sym (T VsLu+1 (
(I (xx G.)Ti + (I (G)
4. We have P, (De+1 (T), T2) (let1l [ 2e Moreover,
E, (Sym ( V 4 P++ M. )²
Cd.r TTT G,)Ti + (1 G.)T,,
5. We have Pi [F+1 (2) n f1 4)] 2 1- 2e Moreover
E (Sym (Ti e
V Vo
Cd Tr( GG) -G)Ti + Tr( - (2)) -G))T)
Proof. First, we derive concentration bound for lett1l. By Corollary 6 and Proposition 33 we have
E, [ett11/11 & (E, [1uc+1/1] + Eg 11u++1 p1 )² I (v8 op for 2 2,
-uie which implies P. [|e41]] ul eive-o) for 2 2e(v8 σ). In the following, prove each item separately.
First item.
We define
Oo V.LL = T
(I. - w.w. Ja 21 T W,W,Ton OT.
For u, L>0 0
P. [1 2 uty TT(Tp(Ix /
GT) lettll 2 r1
$ Pr |u4+ivut1l 2 TT - GG and le41l S L PP llet1l 1 L
Pr 12.15 T - + + (P 2 T.)
We have for 2 2
E, U14 11
< L' [ (Ia W.W, | E. T T W, W.T. 2++1
< L (2) (3TF(TP(LM G.))T(TT)) y
where we used Corollary 7 in (a). By Proposition 33, we have for 2 2e
IP, [||
lee [e Use 1 uL / (3))) -
By choosing 4.2 have the probability bound.
For the variance bound, we have
E, Sym V T.)) E, [Sym (2 2]
By using Proposition 22, we have
E, Sym (u.41v
58

---

= = (1. - J. 1 W.W, 2++1 2111224411111 (Ia- W,W, jeT
+To W.W, T (Ia W.W, | 11 W.W, 6T,
(6) 3 (T G.)Ti + Tr (T - T2G;T2)
where we used the Cauchy-Schward Schwartz inequality in (b). Second item. We define
T TiM M, e -WWW a T
STTTT..W W.W, 2441 B.41 W.W, o..
We have for 2 2
E, |1
x141 $ T, -WW,,,
22
W. W.W, N.W,T.+1.8 1111 120 | R2
x E, | W, 2
(c)
L 2p (3d ( TTTG))
where we use Corollary (c). By Proposition 33, we have for u 2 (2c)²
Pr || 1 2 2 ud.23d (TTT))))T((TGG.)) s e 1//2
By choosing
4- we have the probability bound. For the variance bound, we have
Eg (Sym (TiMpP:+1M/) Tx)) )²] E3, [Sym (uc+ie
By using Proposition 22, we have
E, Sym (uetie
TOO W.W.T
x E. [ct
(Ia W.W.) x 2+41 T6 W.W, 2,41 24112111 W.W.T eT,
+ T W.W.T
E, (Ia W.W,)
2e+ | TO
T W.W, 2 12 W.W. OT
(d)
3 Cdl
where we use the Cauchy-Schward inequality in (d).
Third item. We define
T LiL S OT2
x = 1 W, 1 (Ia - W.W, (w,-.,
a W,w, oe. )T..
We have for 2
F4 [1 11
u 10 _1
1 W. 2 1120) E, O (Ia T
w.w, J0411 W.W:)a4411
E, 1 (Ia ( w.W, J
2p
59

---

(6) I 1,2 3rx BToVTr(TP(TN G.)) (r( (T G.) P
where we use Corollary 7 in (e). By Proposition 33, we have for 2 (2e)²
P. 1o 11 lla ur (Ix Gr)) Gt)) S
w1/2
By choosing
12 6 we have the probability bound. For the variance bound, we have
Ex (Sym (T V V (T²) )²) E. [Sym (ue+ro+4))
By using Proposition 22, we have
Eg Sym (1++1=)11)
- (o-W..)
Effeit1 W., x (L- www (Ia W.W,) oπ
TE (Ia - W.W,
x E. E.feii [ T
Ti (I.- W.w, | 11: (I Ya-W,,;" еT:
S Cr.
(Lx
G.)T, TT -a
G.) G.))Ta)
where we used the
incquality in (f).
Fourth item. We define
T2 e G - - 1 W. x++1 ETO (Ia W.W, x0 of w.w.er.
We have for 2
E, u441
< E. [I(a-- w.W,), a. I (l. Wa. Ja:+111
x E, |I x T w.w, 2++1
<20) (V3TT(T
(v3r'(( (Ix G.)) 8 drav (12
(V31T(T5G.))
( P
By Proposition 33, we have for 2 (2e)3
P. ||| 2 11a 2 12 TT(T G.))TT(T3G.) Se 3/3
By choosing
I we have the probability bound. For the variance bound, we have 21V3'
E2 (Sym (Ti V )²]
E, [Sym (u1+1v
By using Proposition 22, we have
E, Sym (u4+1i), TTT
T (I W.W, W.T.
x E, [ (T W.W.
Jar+ W. x.n ToO W.W, æ [204
x (Ig W.W,
60

---

+ T W.W,
x Ee I -itallla---ii W.W, 2 x
a T ( W.W, 1
x W.W, 6Tz
3 Cdd
(
Fifth item. We define
T V L 1I P++1 V
W, W.W.Wo )a E+Ill(Ta W.W, a+ W. + TOO (Ia
M1
2 w.w, OoT. )o..
We have for 2
E2
< P
|| ([a--..w]] 1 x++1l 4p
x (I - W. F
< S. [II W.W,") x.
E2
ITO T (I - w,W, 2 4p
x X 1 PT) - W.W, a 1++1112
E. W. x1+1
- -G.)) $
< =L") (3TTT)
P
= """3""")""""" dr Tr (r) Gi)
By Proposition 33, we have for u 2 (2e)*
2/44
P. 2r
$2e
1.a By choosing u 2(2v3)a we have the probability bound. For the variance bound, we have
Es (Sym (TIO P
E, Sym (u141e4+z) '].
By using Proposition 22, we have
E, Sym (u+iv v )²]
3 T (La W,W,T)
x E, [e.t
la x (Ia W.W,T)er jeT,
(1, - W.w, 11
(Ia T
W.W,T)
x E, [c ( -
a, 1 (I, - ).W.)ax+11BB441e
x x(a - W.W.jee
3 /2 ( (Ix G.)
G.)T TT G3)) -G.))
61

---

By recalling the definitions (TekEN, A, A11 in Sections F.2 and F.3, we define the event:
n (A&, T, 3t A n (et+1 S L), (AiTT =1 -1 T AiAAi)) (ee+1 S L), a 0.5.
Ae+1
T. Ti
a E (0,0.5)
Ac+1
Aet1
Ti Ti
A
We define the events Bi+1, Cr+1, De+1: and Fe+1 in the same way. Based on these events, we define the clipped versions of the noise matrices:
A++1 Sym (o Vo AAets
Ex 10 ToTT ViLLetiM Actta)
M,P1+1 1.,..M,1BB.111
18
MMPP+MM, 18
B++1
1+ o+1
1 o
C++1 = θ V V L 0cc. - Ee [ Vs V 0
O V P IDEE1
T
V P c+1 M, 1D.11 )
D = Sym
Eg
1 c241
1 1 c+2
θ VsL P 2+1 V L,, @1
+
Pi+1 i+1
V D 01
Fr+1 =
E,
(F.38)
+ c,4
1 1 2.41
Xet
1/2
B, //16 C, n"
D, n
/256 F and
3/2
I, a 0.0.5)
AAa, a (0,0.5)
r
l2 =
Ir a> 0.5
3 Il a > 0.5.
For E (1, we define:
Quad Quad (0) k,t
(X) = Σ Bj-1 [,,,,
2=1
We have the following corollary. Corollary 4. Let rk E (r,Tu), rk. E (r, and
S 5==1 Σ GJ-1 and n
Arll and ru = flog2.5 d].
Assume the following conditions hold:
z Kay I
Ci. (2)), a (0,0.5)
T S.T." =
Ka
r log.lr..
0.5,
T G.T.²
Co In for j 11
k.
Let
Pi 1 and P2 1 a
E [0, 1)
Pi and P2 log
log
pi 1 and 0
a> 1.
For ml S 1rkk log ddogg' the following results hold:
62

---

(a) Quadratic variation bounds.
We have:
Cuond
X n/2 A
VT.
dan
X L/I B
Quad (X)ll2
C' log d || lIrrkPrkk
n/de
X 2/16
Kd r8
3/2
C
X 12/32 D
n/de.
X J
(b) Operator norm bounds.
For L 2 82, there exists 0 such that
nLa
V () G G)-1T,²)
X 8/2 A
2vr.
Vr.
n²L² dTM(TIT 7 G
X 2//10B B To
16r,
TTT; X,T, - Te (x)=
224* (T
X 2/16 C
To
n dv Tr [
(T Gy-1T,²
X 1'/32 D
32V7,
dnT(T )
X /256 F
256
L L
2/2 A
Vra
L'Cwnfd
2
C' rkpe
LARd,
1/1OC
Kd Ts
I, P LP
13/32
/256
"
Proof. Quadratic variation bounds. We will use the variance bounds given in Proposition 18. For A, we have
CallAllE (T([TaT, S.T. ). T Tu(T,, I. " s.r. VTs
Quad (9) 1, ( (2/2A) =
CnllAlle Fak log d
Like
Te
K2
For X 2²/16 B, we have
Quad (12'0 B)
&d
Tr ( ,. S Te
Tr
sup
3/2
3st
d || Ch Ch.rkirks log
K2 I
3/2
rss
For X = 92/16 C, we have
rkPt rk log d C1AAA
Quad!!!
(8) ((0((((2)))))
22/16 C) = "
Ink.
3/2
rs
For X /2/32 3/2
D. we have
(1) 12/32 D) Ca ( S,T," I ' Tr(r,,, "T,,, "
Quad!
Vr+
Cs || CurrkP' rke log d
Ink.
VTs
x2
rs
63

---

For X 22/256 1/ F, we have
df rk? log d
Quad (0 (1 /256
F) 3 Cij (
Ii
3/2
K2
Operator Norm Bounds.
We will the events defined in Proposition 18. For X = n/2
A,
have
vra
10 12 (2/2AA) VT,
n/2 L2
G,
CL²
/
VTa
Kd
To
For X = 2-/10 B, we have
1/2
CL C
(1) B)
16r,
Kd
T
For X 22116 C, we have
n
CL dr
(e)
/26 C)
=
16r,
Kd
For X 12/32 D, have
%
CL. VGan
1 132 D)
dv Tr(
G |T((TTT])) S
jtt
32 3
Kd
For X 22/256 1.
F. we have
3.
10)
(1 /250
F)
256
11=
1 (.
<
CL n7 rkk'
Kd
Ts
Proposition 19. Let (Y,, 1,2 be symmelric-matric martingale with difference sequence {X, = Y(+1 Y, 1 == 1,2..... whose values are symmetric matrices with dimension S d. Let (T,, = 1,2, be deterministic sequence, whose values positive semi-definite matrices with the same dimensionality. Assume that the difference sequence is uniformly bounded in the sense that for predictable triangular sequence {Tit)ise have
Amax((T) (T, XTT, TT for j = 1, ,t.
Define the predictable uniform bound and quadratic variation process of the martingale:
(I=+x,;;t)) for k < st= 1,2,
R == max Ta and Quadg, (X) 35k
3=1
Let T S d be bounded stopping time. Then, for any deterministic T², 0
3 ATS.YY E "T, and max
Lux S 0² and max RI, S T.
ET
KT
-u2
S d exp
02 Lu/3
Proof. We have
Eurget (3t z uT, and (X)l22 s o² and max R.t < E}]
rST
S
Ü (3k st uf, and (X)ad,,())1 s 0² and Ra, S LL..
1=0
64

---

Therefore, we have
da
P Eargor
IP
3k S t, YN 2 uT, and [ o² and Re s L... (F.39)
In the following, we will bound the each term in the right hands-side of (F.39). By [Tro10, Lemma 6.7], we have for l- = 1,... and A 0,
1 Re, RR. 1 c X.T.
1 1 RR, exp
c - -111
BR-1
(T
X ) (F.40)
L
For notational convenience call g(0) 0 < k
c.
1.
We define super martingale such that for
0 1 Y KTT
9(0) 2
Quad qu (x)
= Tr exp
T
T,
with initial values RD 0, Yu = Quado, 0, and thus, So Note that by (F.40) and [Tro10, Corollary 3.3], we can show that 18 I Sk-1. We define a stopping time and an event
This = fk 2 Amax (T YT 2 u) At:
Enit = Thi s () n {1 Quad,, (X) S 0² and Re, S L.J.
We have
0
g(0) 0²
(a)
0
g(0)
In Sm
11 em exp
+
P P(nna] exp
=1
0²
L
2
L
2
a²
+ inf exp 050
0 =
g(0)
IP
[Eai]
L
2
where we use Doob's optional sampling theorem in (a). Since the infimum is attained at 0 > 0 and
the convex conjugate of g(0) g" g0) = (0 10+1) log(O + 1) - 0, we have
0²
12/2 02 Lu/3
IP Enid r exp exp
72
g
exp
where we used (0)
12 in the last step. By d and (F.39), have the statement.
Ituf3
Proposition 20. Let Pn denote the conditional probability conditioned on Wo. We consider ru [log 2.5 d) and
1 2
E [0, 0.5):
+ +,
17 dro log (1+d/r.)
Kd
log 3.5 d'
Cub 12
1
v
a 0.5:
T. 2,11
17 dr login d'
Kd
Tu log 2.b d'
Cuu 20
For a E [0,0.5), we define T = Thad A का (ra(1 log Fd) ^ Ar) log (dlogt e ) We have for
2 (1)
Po
sup RT
T n,T," 1 U,T,"
A 2 Kar
and Gmis
20d exp(- d).
For 0.5, we set Thad A 2n 1 z log
(dlog'. d
We have for 2 Da.r, (1)
To
Po
sup Tr U,T," 12 A V,T,"
A T
kar and Gini
20d exp(-log² d).
65

---

Proof. For notational convenience, we introduce X' 2/2 A, 12/10B, 9//16 C, /32
" 12/258 F}
VFa
12
For both cases, we will set the clip threshold to L log" d. We introduce the notation maxxex maxjst
R2
(6) j.t (X) and Quaad (6) |12 = maxxex Quad (X)ll2 for = 2,
For E (0,0.5), we can write for all X E X.
Po
sup
T
D.T."
V.T.² A 2 kar o and Fmit
<
sup T
T
2
and Ginit
2
10
Xext
15
Po
sup
A A
Σ
A
Kar a and Finit
10
XEX
jCt
By Propositions 14 and 16 and Corollary 4, Ginit implies the events
0,,9,0 (r
O G (r
E
max
[hax||Quad] " 112 S 1ST
and
max R EST
log 12
Vdloy' 12.5 d
12 0,,8,0 (1-2a)
0 (r-2a)
E =
max Quad? (2)
and
max 11 1ST
log"
Volog125 d
Therefore, by using Proposition 19
Kar 2 and Gini
Po
sup TT
T
X I
10
jst
Kar +
$ Fo
sup STT
T2"
I,
and Ent
10
jst
2d exp
l-log" d).
Similarly,
sup Po
A A
X,) T A3 11,
Kar a
and 9
1T
10
jSt
$ Po
sup KT
A A
Xy) 1,
1/1
Kar
and Ent
10
1st
< 2d exp (- log d).
For a > 0.5, we can write for all X E X,
Po
sup
T
D,T,
T
U
A 2 kar
and Ginit
1T
katw
Po
sup
T
and Gint
2
10
XeX
jst
Po
sup
Σ X,
T
1
Karn a and Gint 10
XEX
J5t
By Propositions 14 and 16 and Corollary 4, Gmit implics the events
Oar, Oa. log 12 d
Or, 40
E
max Quad, (1) ll2 S E
and max R()) ST
Vdlog 11.5
O (re t0 (anl))
(ro
O, (ru 4a - (a11))
E
max Quad, 2 1|2 5 1ST
and max R22) SST
log" 12 dllog 2 Ta
v Volog221 11.5 d llgg -2
66

---

Therefore, by using Proposition 19
2 Katu"
Po
sup K
T
and Ginit
10
ist
< Po
sup
Ti
Σ
Tx T.
x
2
Kdtuu
and E1t.1
nST
10
jst
< 2nt exp
--log* d).
Similarly,
1 A T T
1/4
kd'u
sup Po
Xj)
2
and Ginit
1ST
10
jSt
kat
< Po
sup
Ti
X3) T.
2
and E
1ST
10
j5t
S 2d exp log? d).
Corollary 5. Consider rk, = {r. = Lra log -/2 d) ArllTu. = =ra and the parameters in
Proposition 20. We have
Po Thad 2 2n rk, log
[dlog' d and Ginit 2 20dd exp(- log? d).
Proof. By using the first items in Proposition 15 and 16 ,and Lemma 6, Gintt implies that
Thad
Taoise A rk. log d'log'.'
To
On the other hand, within the (negation) of the events given in Proposition 20, we have Therefore, the statement follows.
Tnoise > Tout A 2n rk, log [dlog' -5 4)
F.7 Stability near minima
In this section, we will establish that given (SGD) is near global minimum it will stay near global minimum. For the statement, (re)introduce the block matrix notation: rk, (r. log 1/8 d) A ArJ, Tu, = =rsh we have
[r>(1
G
G
Vi,11 Vt,12
An
0
A 0
G. =
G
G
V: =
11,12 Pt,22
A22
A =
Ae,
where G., Mt,11 An1, A Rik, xtk, and Ae, is introduced (F.2). We define the following iterations:
Given G. = Inx, logd diagonal and V. = 2A 1.
G
-A.. we define
22.11
n V,
VA = V.
Ink. + - 1.1n
+ n
A
rk log A
8.1
A2 log" d 12
0(1)
1.1n
. For 22- = 0, M4+1 = 2, + n/2
1111111
vr.
67

---

We define sequence of events (E1 =
rk
rk, log
- rk
Itk. I AtRA
rk log d Iike
& log" d
Tk. k 1
Ik. n
=
log"
We define the stopping times
Taaise (w) inf {t 2 0 WE
Toundedd == inf 120 Gt z Is. log Isk.
and Tstable Tnoise A Touunded
We have the following statement:
Proposition 21. Consider the parameters in Proposition 20. (SGD) guarantees that if Go,11 = 2
Tog for t < rk", log with probability 1 - d exp(- log" d).
Irk. lo we have Gr,11 2 Irk.
Proof. We define S. = 2A Kn We make the following observations observations:
Since G + Gr,12 I Ink for S Touunded. we have
Gr,12 3 log d Ink.
Therefore, by using (F.8), we have for S Thounded
G 2 G.,11 + n 11. + G., IG,,
4n rk, log d Ink.
-Cn + 112
V++1,11
Vr+
Then, if we define V. = 2A 22.11
22.11 Gr,11
Aq.11 we have
12,11
(1x
8n
V 2 V, n(V 1-1 )² nA .1
Cn A
[k logd
VTx A 11 12.11
1, -- 1.1m
n V
+
A 6,,11
rk log d Aeael) ) + A A 2a.
8.1
To derive upper-bound for G1, assuming G, 3 1.11k.. we have
n
V = V.
V
V
Inx + 1-1.1
V,
1.1m
(1 - 1.1n)
11
A 11.11
8.1
O(1) A?
1.1n
rk log d
log" d 12.11
V, - 1.1n
V2
1- 1.1n
Then, by Proposition 34, we have G.+1 1.1.
Since the bound holds for holds for all
t E N.
To derive a lower-bound, we first observe that by monotonicity V, > 0. Therefore, assuming
V, > Vn
n/2
V 2 V.
(2A
1
G.
A
12.11
1-1.1m
n/2
8.1
O(1)
+ 1-1.1n
22
A
rk log
A
log² d
A? A
22.11
68

---

t V 1 1.1n
n/2
2A
12.11
G.A
12.11 -
-
(1 41,11
1kg
8.1
12.11
log"
0(1)
A
12,11
+ 1 1.1n
n/2
A1,11
A
rk. log d' A
8.1
(
A 222
log² d
Then, by Proposition 34, we have V, = Vo.
We start our proof by showing that V. = V, + S, for t S Tstable- Assuming the statement holds for
t E N, we have
Vii = (V. +
+
(1, 1,
7 T- (V. + +si)
+
A2
8.1 rk. log Ara.1)
A 11.1144 62.11
V. I, 1 1.1m
V,
+n A2
8.1
A62.11
rk log d
-1
I + 1- 1.11 Vi
S, I +
17
(Ve + +(s))
+ A A
1 1.1n
We have for t < Tstable
-1
-1
I
1
V,
S
I I 1.1n
(V, + {(2)
1.1n
V.S.
S.V.
n
1.1n
1 1.1n
1 1.11
112
V,
I, + 1 1 1.1n
11
V,
-1
S
I + 1-1.1n
n
(V, + (.)
-1
(V, +
(1 - 1111n
5 1.1m log d
1
V2
π
(1 + log 2 d)c
n
O(rk,") ")
Lik.
1- 1.1m
1.11n
log d
(())
5, 1 1.1m log d
1111
Since Vo Vo S the claim follows. Then, by the third item above, we have for S Tatalle
rk.
2
G z G n, Ik. log d
It..
Ink.
2 Ink. log d Ink. Taoise S Toounded
log²
In the following, we will bound Tooise- We have
(a)
E, [
2タ + 0 Ln.
[ 3 30
By clipping strategy we used with L log² d in (F.38), and defining ri Ixx, [2 Ai and
Σ E (1.,,xx,,;)..)) )² Le {1.2),
Quad (2(x)
we can show that the following events hold: For any E N,
Enc,1
Quad (1) 2et 112 S ((12T)
and max R < O(yrk2 log" d)
max
STT
Ep.
max
[uad b,t
1l2 S Oa(n"Trk?** and max (() < (nrk.. log" a
TST
EST
where Pa defined in Corollary 4. By using Proposition 19, we can show that with probability d exp(p- log² d), Tnoise >
rk." log"
69

---

G Auxiliary Statements
G.1 Matrix bounds
Proposition 22. For A, B E Raxr, have
-A B B A A3A A+B''
Ifr = d, then (A+ A 3 2A A + 2AA
Moreover, if A.... .. As are symmetric matrices,
k
2
Σ
A
3
A
1=1
1=1
Proof. We have
(A B) (A - B) A B A.
By using A + A, we obtain the left inequality too. For the second inequality, we have
(A+ A ) A A+ AA + AA A AT
(A A (4 A A A AA AA A A
Therefore, (A (A+AT) 22 A T A + AAT). For the last statement,
Σ A Σ
A Σ Σ
A.A,
E
Σ
AAA
3 Σ A?
i=1
j=i+1
E1j=i
where we use the first statement the last inequality.
Proposition 23, Consider a symmetric square matrix with block partition
A
B
M
B
C
A is invertible, then M > Of and only if A a C T
Proof. If A is invertible, we have
A
B
I
0
A
0
I
A
B
C
A
B
I
0
C
B
A
Note that
I
0
I
0 1
A-
I
=
A-1 -BA-
B
Therefore, the statement follows.
Proposition 24. Let Tu < and Z E Rrxr, such that
Zi Zz
Z
where Zi E RTuXTo, E Tr.
For ant 0 < << 1
Zi TT
ZZZT Z, ZiZ (Z ) Z2
zz
2 E
+ (1 8)
0
Zz ZJ
E
where A A+ denotes the pseudo inverse operator.
70

---

Proof. We will denote a E I" as
where 21 E RR 22 E RR
22
We have
ZZ
ZZ
==
3j Zi
T
2x
Zi Z 32
22 T
ZzZ 222
I2
T
Zz
2g
x2
1
-
(0)
2 [0] Z 2 - -1 Z 2
Z2
12Z, Φ1)
8
12
Zn
Zig
02
1
where minimized the first term in the first line 22 in (a). Since (a) holds for all the statement follows,
Proposition 23. Let E R2 be a symmetric matrix. For S - -A, S , -5 + A) is monotone.
Proof. Let S > S > -A We have
-(S + A) 11-1 (S2 A) - -1 (S2 (()) -2) A + A)-
(G.1)
For S > S2, we can use S + +I, in (G.1) and take e & 0
G.1.1 Additional bounds for continuous-time analysis
Proposition 26. For a symmetric positive definite Dj, D2, and C >> 0, we have
D1 Dr + (CI, + +Z, Dr Zz) 2 Z (Z + CD2) -1 D2
ZCI,, +2 D Z2 27 Di - 2z_
Proof. We have
(Di + (CI,, + Z "z,))²
- Z + 2 1 Zo 22 2) D.
Therefore.
(D + + 2,,
(CI, D, 2 DT 21) - 'T'
(CI, -,(0,,,+2,,,2,,,
-1 "(II, +Z D2 Zz)
Then,
Zi (CI, + Z D Zn + 2 DJ 21) (CI, + +2,
D, D. 22 2 [Z + +CD, D2
= Zi (CI, + + D Z, + 2 1 ZJ
Proposition 27. For some diagonal positive definite A = diag( {11)) diag((a;)))
and B = diag((h, (b,
let
A (xpp(tt)
B Bexp(-tB3
D I,, eep(pttp
D2 I -epp
For some Z E I Xr, Ze E ((d-rx)XTo, and C' > 0, we define
M = cxp(0.5t.A) (CI, + 2 D Z, + 2 D 21) 2 exp(0..ttB.
71

---

We have
[M C
PuAts
Σ
(2 exp(((a; + +b))
(c+
Aminl (z) Amaa (D2)
2z)
exp(((a; + b:]) exp(ta;)
where
Amax Zr Zz)
Ö=
(c
Amin Z Zz) Amare D2)
Proof. For convenience, we will use
A
B
D I. exp( -tA)
D2 ld-r. exp(-tR3
2, exp(0.5/A) Z1,
Zz = exp(0.5tBB) Z2.
We let
M1 = 21 (I,, + D2 2, D 2,)
M2 (CI,, Z D Ze + D 21) 2
We observe that
TuAr.
|M Tr(M, M.M & Σ M (M, M2)
where we used that rank(M,,, ra A and Von Neumann's 's trace inequality in the last part. We have
M2 M2 I exp(0.5tB) (CI,, + Amaz (D,) ZrJ Zz) Zz exp(0.5tB))
Amax Zn Z2)
3 C' Amaax (2) 2z) exp(IB)
Amare (D,)
On the other hand,
((o+
Amin ZzJ Zz2
M,M 3 ži
Lr, + DJ 21)
27
Amax (D2)
2,
I, + 2, ((c+
Amiu 2z)
Di -1
2
-1
21
C
Amini Zzl
Amaz (D))
Amary Dz)
1
2, ZT
((c+
Amnin (2) [z) Amuz (D2)
D 2, -1
((c+
Amiin 23 2z) 27)22) Aanaa (Da)
D1
C+ Amin' 2 Zz)
Anmox Dz)
We have the following the same time:
ž ((C+
Arnn Zz Zo) Zn) Amne (Dz)
D + 22,2, ( +
Amina Zo Zz) Amma (2))
D = (C+
Aminl (ZÚ Zz))
Dr
Amar (D2)
2T ((++
Amina (2, 2z) Amnus (D2)
D + 2, (c
+
Amnin
Z 2z) Amaz (D:)
D1 1 Amax Zz Z eep((IA)
Therefore, for STAA Ma, we have
{(MMM $
Amaax (ZzZt)cx)((aa) A (c+
Amin Z2 Zz) Amazx (Dz)
exp(ta.)
Amin (2 22 2z) Araea (D2)
explfa, -
C+
Therefore,
|M E Σ
PuArs
Amax Amax(ZiZ)) (Z,2,) exp(t(a: + bb)) A (c+
Amin (2) 2z)) 2m)) Amaz (D2)
exp(t((a; + b:)) exp(ta;)
72

---

G.1.2 Additional bounds for discrete-time analysis
Proposition 28. For some positive definite diagonal matrices Do: D2 E Rexr and symmetric
matrices G. U E R we let
V = 22 - D2 and ç : DDDDDD and v=V+C,
where
Glll2 S LG and |12|2 S Lu and |Dolla S Lo-
Du Dill2 S L1/0 and D 1l2 S La/1-
For notational convenience, let Lp = 2La + L1j0 and L == 2(L + Lv) + L1/0-
For 0 S < Lgtn we have that (I, + v) and (I, + v are invertible and the following bounds
holds:
-GDD (I, vV) -VV (I++VV) S,D,, -CDD (I++DV) -1 C2Di
(G.2)
-C (I, (v+ CDD1,
-.DD (I++ I C,D,,
(G.3)
where
LoLnn/ L1
C - nL-bp pLo)
C2
1 - n
L Lo 1
C3 = 1- Io
C4 = 1 - 11 pLo
Proof. Note that |V v [ S Lo therefore, 0 S < 1 are invertible. For the following, we introduce the notation
LpLo (I, + v)V and (I, + v
G = G v and F = 2G + DT D2 and F = 2G + DD D1.
Note that we have Fl12 S LF and || S pp.. For the left part of (G.2), we write
Do x 2 (I, + vv <v I, + nV) -1
D
FD (I, + nFD)) DDoF (I, + nDFF)
Therefore, we have
FD, + FDD)) -1 LUD, + +D
| Flla Do |
F112| Do Dolla) (1 7 Flla||
1.
(Lr -
Therefore, we have the bound. For the right part of (G.2), we write
Do v (I, (I,+nV) -1 D FDoUDo (I, (I.+nDDb)) D2
Therefore, have
FDrDDo (I.+nDott)
21 nl 11
D.
Do - IL
Lr 1 Lo
73

---

which gives us the bound. For the left part of (G.3), we write
Do v (I, + + SD 3 = (FDo)² (1 v
Therefore, we have
(FDo)* (I, + nDD) a1|e - 1- FFllF
FI Doliel
L8
1 nLF
which gives us the bound. The the right part of (G.3) can be derived similarly.
Proposition 29, Let V, V E TR" be symmetric matrices such that V = +V+G S. We have
v ( -1 -V +V (4+
((,+nn) ((, -1
Moreover, given that
M -V-V--VS-nVV-- - 2
<VC + ,² +1 VVV
under the conditions of Proposition 28, we have for any Kd > 0,
2
D1 3 (I, vV -1 < I, + nv) M
2 = < n² + + + +n VVV + Crt² Dr
where == C1= + + + C3 + Co. i.e. the sum of the constants given in Proposition 28.
Proof. We write
(L++nN)- - -(, -v
= =(,+ (V +C) Vl,, -
= - (I++
For the second part, we write
(I, (1++ < (I, + +nn)
+ 1/ -1) 5 1, -n- (I, (..-n(( (1++ (I, -
II
1/V
S nnn I, - 1/V + +1 222 (I, ((-44477)) S
-nsv (I, - -,- + 22 (I, + ( + + (I, - si -55 (I, (I, + -
-S- AS 25n ,2v35 2 - ,,'v3 (I, -
- -s (v, + + - (1, (b++n))
We have
= - + = - + 1/ VV + -p - + 7223
MM.
Moreover,
2 (L, - (I.+nV)
=V'Vcv (I, (1++nV) - (1,+ cV +v²=
(I, =,/vcV - ) -1 - 222 v1,) '5V (1 (I++DV)
74

---

VVV V5 - (I++ - (v++ <V (I, [b+
MM²
By Proposition 22, we have
-2n - 1 V 3 MI + M 2n 2 V
Therefore by Proposition 28, we have
k2 - D1 1 (I, +1²) + (V,+ M
2 x (2 ,² + V D1.
Proposition 30. By using the notation Proposition 28, we consider
and <<E< 0.5/n
11 < LpLo
LpLu
Then,
VI, + -V V = V +
V + + 3 V (I, + 1 -1 v) + +155n/ CD,
Layy LoyyL1p 1. T-gLe La
where
Proof. For the lower bound, have
V (I, VV =ny
=V -V-(++))VV3 + V +
V-(1+e)m + (1+ + (1+t))))))
- (2: + - (Q = V (L, + 71 + -
where we used C3 with L, in Proposition 28 in the last step. For the upper bound,
V (I, VI,++VV) V
-1 V
= - - -11- (I--) +
(I, VV + (1-)))) (V)
+ (2s - = (I, en
1 V (L, +1 2
Lemma 7. For any 17 and E we have
(I++A))
A -1 (T+ -I.
I. D
nI
(G.4)
I
+
Proof. We observe that
0
I
Σ O'
A
A
(G.4)
A
0
Note that
A 2k
A
2k
0
and
A
2h++1
2k
0
A 26
A 2k+2
75

---

Therefore,
E'e a***** koven
Eizo W77 1-1 kodd
1/" A
k
Σ E rf A
Ei ())*
km0
(L+nAA) -1. -1,--A))
G.2 Some moment bounds and concentration inequalities
Lemma 8 (Hypercontractivityy. Let Pk: Rd + R be polynomial of degree-k and x ~ N(0, Ia).
For 2 we have E [Px(4))]] < (g 1 (+) 1/2
Lemma 9. Let x ~ (0, Ia) and 5 E 1dd be symmetric matrix. For u > 0,
PP || Sæ Tr(S) 2| ru + 2 S| 2e
Proof. We note that x Sx Tr(S) has the same distribution with Σ ((5 1), where Zi mid (0, 1). By using the Lausent-Massart lemma [LM00], we have the result.
Corollary Let y = T Sx Tr(S) and x ~ NN(,, Ia). For 2 2, we have E| S (p- - S)
Proof. By observing that E[[y|?| 1 we have the result.
Corollary For A E Rdxr, 2 2 and a No Ia), we have El[| A 20 S v3(p 1)Tr(A" A).
Proof. By Lemma we have ||||A T - S (p 1) A
-1 A
For S AAT, we have
E E
T
x [( Sz) Tr(E((x: Sx)ex (ss).
We have
(0)
E((x T Sx)xx xx 1 +
-1 E|]|
Tr(S) + S| S 3Tr(S)
where (a) follows that is positive semi-definite. Since Tr(S) = Tr(A A), we have the statement.
Proposition 31. Let æj masa N(O, I,), E [N]. There exists constant c >> 0 such that for
M(rtyCrlon d+ log we have
1 N
IP
sup SER
Σ
Tr(Saa I,))² -1 2 max
max(25,8 (25,82) + C022
j=1
|||==1
S dl exp(-cuu) -
Proof. We observe that
1 |,, I, < (1æ= +
By using Lemma 9, we can derive
PP a <r 2/T C log d + 2C log d > 1 - Cd
E
76

---

We have
E
2 TT((a(j)) - 1g) -1 = 2 1,)) 1531
$ 2 Tr TT I,)) 1/2
v2d C/2
59 012
By using [Ver10, Theorem 5.41], for 6
u(r+ Mir+yCClog Cor d+ have
VN
N ( I.))² -1
P
sup SER =]
max naxx26,,02) + C02 C/2
1=1
N [( 1g, E - - 1,))² 18, 2 max 821
$
sup SER"Xe
N 1=1
F=1
+ 2Nd
$ d -
Proposition 32. Let 2j Misd (0, Ia), for j E [N] and W E Rdxr be orthonormal matrix. For a fixed S E Rddd C 2 16 and N Cr log d, we have
-a)) W (x,z} W- W sw Tr(S(zjz) Ia))
224e||/||e (V
2e + C
Proof. Without loss of generality, we assume ||S||i 1. By using Lemma 9, we have 1a)) s 4/Clog 2 Cd
P [[(x(E
For the following, fix a 5d-1 First, to bound the bias due to clipping, write:
E [TSS(z,)] (a)) -)1s;)
< [T(((EE -1)) E [(v. x²) - 0/1- < 18 C/2
On the other hand, to bound the moments of the clipped random variable, we have for 2 2,
E [ (e)) x) -111)))))
< (4 Cooglog d 2E TT(S( - ((() 1)p] < (12e))(VV2e d)² -- p2
2
By using e-cover argument, we can derive
Tr(S La) W (I LajW W wTsw|| > 24eu 18 28 C/2
P
12 C
2 9" exp
+ u C'loo
By using
Cr/N, we have the result.
77

---

Proof. Without loss of generality, we assume
|||||
1.
We have
2
N
N
Σ
[ Ia) - S
- - -.)) -
sup
N
==1
SE
j=1
Hence, by considering the event in Proposition 31, we have the statement.
Proposition 33. Let X E R be a random variable such that for some K, C' 0, E/ & CKPP
for some e > 0 and p 2 k. Then, P[|X| 2 Kuj S Ce- wt/e for u 2 (ke)s.
Proof. Use Markov inequality with a 1/e
G.3 Miscellaneous
Proposition 34. We consider 7i S 10- The following statements holds:
1
For 0.2 8 let
Ut-1 ue mu u4), 1+ 2 un 0.
We have (6 V 4 sup, ut 0. Moreover 1" = inf(t ue 2 1}. we have u241 Ue for
1 < 1x and ur- 2 un 2 f 1 2 L*
For 0.5
and 1.1 Th un > un 0, les
+ n ū++1
E)Tu( T.) and U1+1 24 t (1 n,)
and
u + que - un S u+1 I u + n(1 + +e)ue(1 - u)).
We have
1 A (e S4 S u S u S 1.. 1.1 ((L+))))
Proof. If 2 t", by monotonicity of the update, we have 1 S ue+1 S Ue S up. If > 0. then for t", we have observe that uy < 11 + 0.25r) and by monotonicity of the update for t 2 t", we have S un < Ut.. Hence, is sufficient bound uy to bound sup, ug Note that, we have 2 4 and thus,
u, 2 0 and u 2 O, and thus, we have ue41 2 0, 2 0. Next,
0.25m.
Ue
1 -1-- -1- 11+ 1/ + ur S 1++ n
-1--1
4
For the second item, by monotonicity, we have 0 < 14 S u S Tr < 1.1. Moreover, by [AGP24, Lemma A.2], we have for t < tt == inf(t: 2, 2 0.5)
Uge T+m
Mg 2
1+7 Mgy
1 Ugo 1
Fort t 2 tu. by the first item, we have u, 2 0.5. Therefore, we have
2 u A
U4.
On the other hand, for all t N, we have Un (oer( By the first item, we have u, (I++( A 1.1.
Proposition 35. For t, X > O, we have
texp((A) exp(IA) - S 1 7
78

---

Proof.
The upper bound follows exp(tA) - -13 2 th. For the lower bound.
A exp((A) L7 - exp((A) -1 ((exp((A)-1) -1)
(G.5)
We have
(t
(t^)*
(tA)*
exp(tX) - -1 - <
= tX
tX( (exp(tt) - 1).
k!
(k + 1)!
k!
k=
k=
k=1
Therefore,
1 v
A
(G.5) (
exp(tA) -1 + +
texp(tA) S
t
exp(tA) -1'
Lemma 10. Letr, x d', 7 E [0, 1), and log - < Co < log 10 We define Fa, Ga, Ha as
Fa(u)= (1
Ga(u)= =
1 +
dC's - rx
1+ ro
(dCa
-1)
( 1.
1-1)
Ha(u)= =
1 C'
d
T5
We have
For any C
al Fa(u)] S 1or S1c(1).
sup, Ga(ui) Ha( 1
For any (0, 0.5), let Cs {u 0: - 1| < 8). For any compact K. C. (0, od) C..
we have Fa(u) d+330 1(u > 1} uniformly on K.
For any compact K. C [0, o0| \ Cs. we have
Galu), Ha(u) d000, 1(u 1}, G2(()) d000, 1(u> 1)
all uniformly K.
Proof. For the first item, if u < log d, for d 2 sc((1)
dCau >
1 > 0. log C+1 d
Therefore, [Fa(u) S 1. For the second item, since dCa > 1 for d 2 2(1), the item follows.
For the third item, since E [0, oo) \ C5 is closed in [0, oo), suffices to establish the result on small open intervals around each point of of E within [0. oo). Fix ug E E and choose 6 E (0, 6/2). Since B(un, <) = (Mo <, 140 + e) n [0, oo) is convex it can be either in Ps, = {u: > 1 + 6/2)
or Ps = [u: u << -=-5/2). Without loss of generality let us assume it is in Pz. Then,
sup CCB
|Fa(t)) S1-
Oa(1) + 0.
1+ Os(Ca) - (() (1)
d
A similar step be repeated if B, Pz.
For the last item, we first observe that uniform convergence of Ga(u) implies the uniform convergence of G2 (u). Therefore, Ps n E and Pe n E are also compact, we can directly use these sets. Without loss of generality let us Pe O E. Then,
will only prove the first result. Since E = [0, ca) \ Cs. is compact, and thus,
[Ga(u) ve(t))\/Halee [Ha(w)) Ca 20000 2, +0
sup
NEP
A similar step be repeated if P3 O E. Therefore, the statement follows.
79

---

Proposition 36. Let r and
LE (0,00) (0) jj:
a E (.,).5
rra
(0,0.5)
Kiff
a 0.5,
1,
0.5.
We have
For K [G,H) and o limo-soe Ayrant we have
Kdl delie
1 - 162 > thiell) ) = 0d(1).
For KE (F,
X Kol A (niimos) ) 1{ > trieat) = oa(1).
(G.6)
A
Proof. The first item immediately follows Lemma 10. In the following, will prove the second item for the heavy and light tailed cases separately.
For a E [0, 0.5):
We define a sequence of measures pa x j-20, S [r]. We observe that
We have pa - μ weakly such that y is supported on [0, 1] and p( 7]) = -1-2a for E [0, 1].
Moreover, (G.6) = Ex- [Ka(X* 1(x" > +
By using the Cs definition in Lemma 10:
E Ex (Ka(X" /t) - 1 > 11)1(X z *|}||
I E Exppa [Ka((X/t) 1(X" > f|| e [], call
Ex~ua [Ka(X /t) 1(x > [X cc3
(a)
$ oa(1) + Px=aaX" E Ca).
where we used the second item in Lemma 10 for (a). Since Px Px=p(Xo first result.
[X E Cs)
6-00, 0, we have the
For a 0.5: We define sequence of measures [u][j} x j 2a $ [r). We observe that
We have μa + μ weakly such that p{j} x for j N. Moreover, (G.6) = Ex~xx (aax)u[((K(("")) [(Ka(X /t) 1(X +))1{X rut]
Let E (Uj - (1-1)),511 for some j E N. For small enough > 0, we have
[xx=ne [Ka( - 1(x > f))1fx rw)]]l
(0)
Ex (X /t) - ( dc& o1(1).
where we used both items in Lemma 10 for (b).
Corollary 8. For 2 ca >> log d, we define
-Xexp(-11) + exxxp(-tA) (Ca ra + texp(-12). )-1 ga(A,t) = 1 - -exp(-tht (1 - ex-xp((-t))) t d 1 exp( (xp(--t))
Let Tu S and
r a E [0,0.5]
Kell
Tef == Kell log d/r.
1
a > 0.5
80

---

We have
Σ (aayitTaak Et > tmattt oa(l)
|
for any fixed
t [0,,00)
a E (0005)
10,,00 1110 j E EN, a 0.5.
Proof. We observe that
1a(A; =>
cxcxpp(-th) tA) + 1-xx--((- ra Then, by Proposition 36
1- 1-
At exp( -t))
Therefore, we have oā (Tof) = X2 Fal Xytrentt
Sa();; (Tot))
Σ
231 + 2 (iottt) }
A F
j=l
1
Fal (exxymaa)) - 122, > trect) (oae)-=odk) oa(1).
A
==1
81

---

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 are supported by main theorems, Theorem and 2, and their corollaries, Corollary and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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 the work performed by the authors?
Answer: [Yes]
Justification: Yes, discuss limitations in the Conclusion part (see Section 6)
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section 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 sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
82

---

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

---

Answer:
[NA]
Justification:
This is a theory paper; toy experiments are conducted on Gaussian data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
wwwassssslolooooooooooooooo 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:
/ //iips.coo. wttpccccpppccceeeeccecceccccccct httoi////uiddee/oeeeeuttiiiiiiii serbbbmsssiooo wswsnnollll cniioniylyc for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details of our toy experiments are provided the caption of Figure Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are provided in Figure 1b; however, they are not visible.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
84

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This 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 or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt///eeurris.cccco http://ccccpppptttt...ccctieeeee
Answer: [Yes]
Justification: Yes, this submission follows the NeurIPS Code 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 cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The goal of this paper is to advance the theoretical understanding of training dynamics of two-layer neural networks. There are no direct societal impacts our work that should be highlighted here
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
85

---

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 such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not 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 be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
86

---

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/mmoel 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well 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 crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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
87

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
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 (https /ttpass:///upp..../// /c///onfeerenccee/222/// for what should or should not be described.
88


Reviews:
[{"review_id": "wGCQBJDFzY", "reviewer": "Reviewer_s1U3", "summary": "This is an interesting paper with delicate theoretical results on feature learning and risk. The set-up assumes that the teacher model is a two-layer network with a quadratic activation function and with orthogonal features and algebraically decaying coefficients. It is about the extensive-width regime when the number of student model neurons is growing in specific ways with the dimension d of the data and the sample or observation size from the teacher model.", "questions": "Questions:\n“equivalently” in line 147 does not imply that the gradient dynamics are equivalent? The authors should clarify that this refers to an equivalent representation of the student network, not necessarily equivalent gradient dynamics.\n\n“which is negligible relative to the feature learning cost.” in line 207 only holds for d>>r_s? This should be emphasized by the authors.\n\nComments: \n\nYou mention scaling laws, but you could be more explicit about how the paper attempts to provide a theoretical underpinning for the empirically observed \"neural scaling laws\" in large language models. This is a central motivation for the work.\n\nConclusion:\nThe paper could be very interesting for a small number of highly specialized scientists working on very specific types of theory for shallow neural networks with quadratic activation functions that learn data generated from shallow neural networks with a quadratic activation function. However, this paper does not meet the required broad impact for NeurIPS and suffers from poor presentation. We highly recommend submitting this work to a more specialized venue where people working on similar topics appreciate this technically impressive but very niche result.", "limitations": "This work does not discuss limitations. It would be useful to add a discussion section to the main paper.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nNon-trivial mathematical results\n\nThe feature-learning setting is indeed more interesting than the lazy regime.\n\nBetter understanding of SGD dynamics and scaling laws is important\n\nThe \"matrix-monotone comparison framework\" might be of independent interest. However, I don’t have the expertise to evaluate this contribution and I don’t see a convincing story-line for whom this might be of interest.\n\nWeaknesses:\n\nThe theoretical results seem to be solid, but they are asymptotic as d tends to infinity. More clear motivations for the coefficient decay assumption are necessary. How about other decay rates?  It would be insightful to see some simulation studies about the convergence rates of these asymptotic results, and under the scenario that the teacher model is observed with noise.\n\nA key weakness of the paper is its reliance on a series of strong and specific assumptions that, while enabling the theoretical analysis, distance the results from practical applications. These assumptions include the following: Quadratic activation function (polynomial activation functions are not very popular activations functions in practice, partially because they violate the universal approximation theorem and because their gradients can explode). Also the theory only covers shallow neural networks with only 1 hidden layer. Additionally the gradient dynamics were simplified (as commonly done in theoretical literature). Additionally infinitely large training datasets are assumed. Additionally the limit $d\\to\\infty$ is taken. (Additionally the result does not cover transformers or convolutional NNs.) Additionally you assume that the true data generating process and the model you are training have an extremely similar structure. Additionally you assume orthogonal features, specific coefficient decay, etc.. These are multiple very specific assumptions which make the result very niche.  \nThere are no empirical experiments with real-world architectures using ReLU or, GeLU or any non-polynomial activation function. In practice these assumptions are (almost) never met, so the paper is mainly motivated by the hope that this theory can give insights beyond its very restricting assumptions.\n\nThe presentation needs to be improved so the main take-home messages are clearer and more crisp, especially for practitioners. What does a practitioner learn from this paper that they can use to guide their practice?  How does one empirically check that the assumed teacher model captures reality for any real data sets? The paper is hard to follow. There are multiple notation-heavy mathematical results, but not a very clear storyline. \n\nMoreover, the connections and differences between the submission and other prior works need to be made concise and clear. What precise and insightful advances have been made in this paper relative to existing works? E.g., Emergence and scaling laws in SGD learning of shallow neural networks by Yunwei Ren, Eshaan Nichani, Denny Wu, Jason D. Lee (https://arxiv.org/abs/2504.19983) seems highly related and was not cited. This preprint was only uploaded a few days before the submission deadline, so if you did not follow oral talks of this paper multiple months ago, not citing this paper is OK. Under this very specific assumptions, you might be the first to have proven this very specific result, but the question is if you have derived any impactful new insights.  The main novelty of your work seems to be the information exponent =2. A general result for an information exponent larger than 2, seems much more interesting to me than a result which only holds under your extremely restricting sets of assumptions.", "was_revised": true, "final_justification": "The submission adds a possibly valuable contribution to scientific progress as it pushes the frontier of a specific sub-field (quite fine-grained understanding of simplified training dynamics under quite restrictive assumptions) one step further. While this result does not give any significant insight to practitioners now, there is a chance that other theoreticians will be able to build up on this result to get more valuable insights in the future. This hope for interesting extensions gives the paper its value.\n\nWe appreciate the added experiments for ReLU activations. These experiments increase the hope for future progress in this line of work.\n\nThe downside of this submission is that most NeurIPS attendees probably won’t be able to obtain any really helpful insights from this paper. The paper by itself doesn’t tell any really exciting story, but rather feels like a challenging intermediate step in a long sequence of steps that might lead to some new insights in the future. However, a few other scientists might be interested in trying to extend this result to more meaningful results (or maybe get inspired by this point of view).\n\nThis paper should definitely be published somewhere. I argue that these results are better suited for a more specialized venue. I understand that other reviewers might think differently about the suitability of this paper for NeurIPS. However, I still believe that NeuriPS papers in deep learning theory should demonstrate more relevance for practice for the broad attendees of NeurIPS. That said, I would respect the AC’s final decision on the paper.", "rebuttal": "We thank the reviewer for the detailed feedback, and address the concerns below. \n\n---\n\n### Overlap with [Ren et al., 2025] \nThank you for pointing out this concurrent work, which was posted to arXiv two weeks before the NeurIPS deadline. While both works address feature learning in the extensive-width regime, our results are  **complementary**  and tackle an entirely different set of theoretical challenges. We summarize the key differences below:\n\n*  **Information exponent regime:**  [Ren et al., 2025] focuses on activation functions with information exponent $IE \\geq 3$, similar to the assumptions in [OSSW24] and [SBH24]. All these works rely on a decoupling argument that explicitly fails when $IE = 2$ (see the remark on page 5 of [Ren et al.]). In contrast, our work addresses the quadratic case, which models $IE = 2$. We note that extensive width setting for $IE = 2$ has been recognized as an open problem in the literature (see [OSSW24][MTM+24]).\n* **Practical relevance of $IE = 2$:** Beyond its theoretical difficulty, the $IE = 2$ regime is arguably more aligned with practical settings  than the $IE > 2$ cases.  The Hermite-2 component is the first nontrivial harmonic that captures multi-dimensional structure in the data (see e.g., [DLS22]). As such, it represents the most dominant lower dimensional signal component and thus plays a central role in the feature learning process. Moreover, commonly used activations such as ReLU and GeLU have nonzero first and second Hermite coefficients, and it is well-known that higher-order Hermite components contribute less due to their smaller gradient magnitudes.\n* **Effective reduction for ReLU-like activations:**\nFor ReLU-like activations with nonzero first and second Hermite coefficients, it is known that SGD dynamics initially drive all neurons into a degenerate rank-1 subspace, governed by the $\\mathrm{He}_1$ component (i.e., $IE = 1$). Once this mode is learned, the $\\mathrm{He}_2$ component becomes dominant, while higher-order terms remain negligible throughout the feature learning phase. This behavior leads to an *effective reduction* to the $IE = 2$ setting we analyze.  \nAs a result, we expect ReLU training dynamics to exhibit a rapid initial drop in risk (driven by $\\mathrm{He}_1$), followed by a power-law decay governed by the $\\mathrm{He}_2$ dynamics. To support this, we conducted experiments with ReLU-based teacher and student networks. The results, summarized below, are consistent with this two-phase description and show that the empirical scaling exponents for ReLU closely match our theoretical predictions.\n\n*  **Sharp guarantees and broader coverage:**  To resolve the challenging $IE = 2$ case (where decoupling fails), we develop a new monotonicity-based analysis that precisely characterizes the Riccati dynamics of learning. Compared to [Ren et al., 2025], our approach yields:\n  (i) *sharper sample complexity:*, nearly matching information-theoretic lower bounds in several regimes (in contrast, [Ren et al.] does not provide sharp rates in the width dependence), and\n  (ii) *stronger guarantees  over a wider range of teacher widths $\\alpha \\in [0, 1)$*, whereas [Ren et al.] imposes a more restrictive assumption $\\alpha < 0.1$.\n\n---\n\n### Clarifications and Additional Responses\n* **Finite $d$ and asymptotics:** Our main results—Theorems 1 and 2—hold for finite $d$ with high probability, provided $d$ exceeds a certain finite threshold. Corollaries 1 and 2 are stated in the asymptotic regime ($d \\to \\infty$) to highlight the analytically clean form of the limiting risk curve. \n* **Strict power-law decay assumption:**\nWe stated our results under a specific power-law decay for analytical clarity and as it yields the cleanest form of the limiting risk curve. However, our main results, Theorems 1 and 2, extend to a broader class of second-layer coefficients under mild technical conditions on the asymptotic distribution of the coefficients. Under general decay rate condition, the scaling exponents in iteration and width (as shown in Table 1) remain unchanged, while  the limiting values in Corollaries 1 and 2 may change. We will clarify this generality in the revised manuscript.\n* **Label noise:** Our results remain valid in the presence of label noise, since (i) it does not affect the population gradient flow, and (ii) the SGD analysis can be extended by incorporating additional martingale terms with minor modifications (see e.g., [DNGL24]). We focused on the noiseless case for mathematical convenience. However, in light of the reviews, we will include the label noise case in the final submission.\n* **General activations functions, e.g., ReLU, GeLU:** See above. \n* **Assumptions on data-generating process and teacher network model:**\nWe consider a teacher network with a low-dimensional hidden structure—a standard and widely used model for studying feature learning in neural networks (see [BAGJ21, MHPG+22, DLS22, BBSS22, AAM23, BBPV23, DKL+23,DNGL24, LOSW24], among others). While this model is admittedly simpler than real-world datasets, it offers a theoretically tractable framework that has proven essential for understanding key aspects of feature learning. Moreover, such simplified settings often serve as the foundation for more complex scenarios, including nonlinear feature structures [Nichani et. al 2023] and deeper architectures [Dandi et. al 2025].  \nIn addition, we note that in the quadratic setting the orthogonality of the target features can be assumed without loss of generality due to the spectral theorem — see our response to reviewer u5Uk. We will add a remark in the revision. \n* **Choice of student network:**\nUsing student networks with the same activation function is an idealized but widely adopted starting point for theoretical analysis. Proof techniques for mismatched teacher-student settings [BBSS22, MHWSE23] typically build on those developed for the well-specified case [BAHJ21, DNGL23]. While the mismatched setting is certainly important for bridging theory and practice, it should naturally come after establishing a clear understanding of the well-specified model.\n* **General architectures, e.g.,  Transformers, and deeper networks:** The teacher-student framework we adopt has been extended in prior work to more complex architectures such as CNNs and Transformers [Arnaboldi et. al 2025] or deep MLPs  [Dandi et. al 2025], with the core techniques often relying on the well-specified setting we study. We reiterate that our work addresses a foundational open problem in this setting. As such, it lays important groundwork for future theoretical developments in more general architectures.\n\n---\n\n### Relevance and scope of our work: \nWe respectfully disagree with the reviewer’s assessment regarding the narrow scope and limited relevance of our work. We address this concern below:\n\n* The main critique appears to stem from the *idealized assumptions* under which our results are derived. We note that most of these assumptions are **standard in the theoretical feature learning literature** and have been adopted in numerous NeurIPS papers (e.g., [BES+22, BBSS22, MZD+23, DNGL23, LOSW24, MTM+24], to list a few). Our goal is not to model all practical complexities, but to provide a *rigorous and analytically tractable framework* for understanding fundamental phenomena—specifically, smooth scaling-law behavior in the presence of emergent feature learning risk curves. To our knowledge, SGD dynamics in the extensive-width regime had not been theoretically understood prior to our work (and the concurrent work by Ren et al.), even under idealized conditions. We believe that our analysis (going beyond the \"narrow-width\" regime) represents significant theoretical progress in this direction. \n\n* These assumptions **simplify but do not trivialize** the problem. For example:\n\n  * The *teacher-student framework* is widely used to model low-dimensional structure in the data and underpins many foundational works.\n  * The use of *polynomial activations* is a common simplification (e.g., [LOSW24]), justified by the well-established fact that the lowest-degree harmonic component governs sample complexity in the feature learning regime. In particular, quadratic activations have received significant attention due to their analytic tractability and relevance in feature learning regime (see Martin et al. 2023, Maillard et al. 2024, Erba et al. 2025).\n  * The *matched activation* setting is another standard assumption that avoids technical complications from the link mismatch. Since the $IE = 2$ regime remained unresolved even in this setting, we believe it is both natural and necessary to begin with this baseline.\n\nIn light of these points, we kindly ask the reviewer to reconsider their assessment of the *relevance and contribution* of our work to the NeurIPS community.\n\n---\n\n### Additional Experimental Results Demonstrating Broader Applicability\n\nTo demonstrate the broader applicability of our theoretical results beyond the quadratic activation function, we conducted additional experiments using three alternative activation functions: ReLU, absolute value, and $x + H_{e_2}(x)$.  The results are summarized below. Due to the character limit, we kindly refer our reviewer  to see our response to reviewer u5Uk for the discussion.\n\n| Activation Function      | $\\alpha = 0.8$  | $\\alpha = 1.0$  | $\\alpha = 1.5$  |\n| ------------------------ | --------------- | --------------- | --------------- |\n| $H_{e_2}$ (Theoretical)  | -0.75           | -1              | -1.34           |\n| $H_{e_2}$ (Experimental) | \\[-0.83, -0.81] | \\[-1.06, -1.04] | \\[-1.36, -1.23] |\n| ReLU                     | \\[-0.82, -0.72] | \\[-1.02, -0.92] | \\[-1.35, -1.27] |\n| Absolute Value           | \\[-0.73, -0.71] | \\[-0.99, -0.94] | \\[-1.27, -1.23] |\n| $x + H_{e_2}(x)$         | \\[-0.87, -0.84] | \\[-1.11, -1.01] | \\[-1.33, -1.31] |\n\n \n\n\n---\n\nWe would be happy to answer any follow-up questions in the discussion period."}, {"review_id": "sTGsprpG4b", "reviewer": "Reviewer_6WHe", "summary": "The authors study GD of the population loss on two layer networks with $x^2-1$ activation and orthonormal weights in the first layer, learning a similar 2-layer architecture. They then proceed to use the closed form solution of the dynamic to decompose the risk into a sum of independent contributions, each given by a hidden unit. This result allows the authors to derive some neural scaling laws. These results hold both for gradient flow and discrete-step GD", "questions": "1. Would you be able to consider the case of arbitrary covariance using the same proof technique?\n2. Would the derivation change if you were to consider an activation $x + {\\rm He}_2(x)$?\n3. Do you expect the power-law to change if you were allowed to use the data for more than one GD iteration?\n4.Minor issue: could you explicitly define $\\land$ and $\\lor$ as min and max somewhere in the paper?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is clear and well written. The proof is elegant, although not very technically innovative. The scaling laws, which constitute in my opinion the main result of this paper, are intuitively reasonable, but I would have appreciated extensive numerical simulations to verify them empirically. While the scaling laws itself are not particularly surprising, there are not exact results on learning linear width networks, so I believe the contribution is valid. I think the paper would be stronger if it also tackled the case of generic covariance and label noise, but even as is it's in my opinion a strong paper.", "was_revised": true, "final_justification": "The authors addressed all of my concerns, and I raised my score accordingly.", "rebuttal": "We thank our reviewer for constructive evaluation of our work, and address the reviewer's concerns below:\n\n---\n\n* **Novelty of our proof technique:**\nWe emphasize that the proof techniques developed in all prior works do not extend to our setting, due to two key challenges:\n   \n   * *Extensive-width regime:* In this regime, the SGD trajectory cannot be captured by finite-dimensional  *effective dynamics* [BAGJ21]. As a result, existing techniques that control the Frobenius norm of deviations around the population flow are insufficient. Instead, we establish *operator norm* bounds on the discretization error, requiring significantly tighter control over the discrete-time dynamics than in prior work.\n\n    * *Information exponent \\(k = 2\\):* In our setting, the dynamics cannot be reduced to decoupled systems, unlike the higher-$k$ cases studied in [OSSW24, SBH24, Ren et. al 2025]. This prevents reduction to independent single-index problems, which are central to several recent analyses.\n \n   * To overcome these challenges, we introduce an new proof technique based on the *monotonicity of matrix Riccati ODEs*. This approach departs significantly from the standard Gronwall-type arguments used to control overlap statistics [BAGJ21]. We believe our technique is of independent interest and may serve as a foundation for future work in the extensive-width setting.\n\n*  **Label noise:** Our results remain valid in the presence of label noise, since (i) it does not affect the population gradient flow, and (ii) the SGD analysis can be extended by incorporating additional martingale terms with minor modifications (see e.g., [DNGL24]). We focused on the noiseless case for mathematical convenience. However, in light of the reviews, we will include the label noise case in the final submission.\n*  **Arbitrary Covariance:** Our proof technique does not directly extend to inputs with arbitrary covariance, as the Riccati ODE structure no longer holds when the input covariance differs from the identity. However, understanding SGD dynamics under nontrivial covariance is an active area of research. Our primary goal was to establish the emergence of smooth scaling-law behavior within a well-studied feature learning setting—something previously unclear due to the theoretical challenges outlined in point 1 even for identity covariance. Extending our results to more general input distributions is a valuable direction for future work.\n* **Dynamics for $x + \\mathrm{He}_2(x)$.**  We believe our analysis can be extended to the activation $x + \\mathrm{He}_2(x)$, and more generally to any activation with nonzero $\\mathrm{He}_1$ and $\\mathrm{He}_2$ components. However, the corresponding proofs would require more involved derivations, making an already long paper even longer—without introducing substantial new technical insights. The overall structure of the argument closely follows the incremental learning dynamics studied in the multi-index setting [Abbe et. al 2023, Bietti et. al 2023]:\n\n   * For the activation $x + \\mathrm{He}_2(x)$, the student network first aligns with the teacher's $\\mathrm{He}_1$ component, resulting in a rapid initial drop in the risk curve. Once this mode is learned, the $\\mathrm{He}_2$ component dominates the dynamics (while higher-order terms remain negligible for general activations).\n    \n   * Because the Hermite-2 dynamics exhibit monotonicity, the training trajectory for general link functions can be tightly bounded between those of a purely quadratic network, up to vanishing perturbations from higher-order terms. This suggests that in high dimensions, the learning dynamics for such activations will closely track the quadratic case.\n    \n   * To support our argument, we conducted experiments using teacher and student networks with $x + \\mathrm{He}_2(x)$, ReLU and  absolute value activations. The results ( summarized  below) validate our argument above, and also show that the empirical scaling exponents for these activations align closely with our theoretical predictions for the quadratic case.\n \n* **Scaling exponents for offline dynamics.** Thank you for the interesting suggestion. We study the one-pass dynamics where the optimization time can be directly connected to the statistical efficiency (i.e., the data component in the scaling law), as done in prior theoretical analysis of scaling laws [PPXP24] [LWK+24]. If data reuse is allowed, then the optimization and sample complexity needs to be discussed separately, and we expect that multi-pass SGD can improve the data scaling exponent, as previously shown in the linear setting (see e.g., [Pillaud-Vivien et al. 2018]).   \n[Pillaud-Vivien et al. 2018] *Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes*. \n\n* *Minor:* We will define the symbols $\\wedge$ and $\\vee$ explicitly.\n \n---\n\n### Additional Experimental Results Demonstrating Broader Applicability\n\nTo demonstrate the broader applicability of our theoretical results beyond the quadratic activation function, we conducted additional experiments using three alternative activation functions: ReLU, absolute value, and $x + H_{e_2}(x)$. In each case, we considered **population gradient descent dynamics** with the **centered version** of the activation (i.e., subtracting its mean), and plotted the corresponding **risk curve**—risk versus time on a log-log scale—following the format of Figure 1(b) in the main paper.\n\nWe considered the setting $d = 5000$, $r = 2400$, $r_s \\in [128, 215, 362, 608, 1024]$, and ran each experiment for $T = 3 \\times 10^5$ iterations. For each activation and width, we fitted a line to the decay phase of the risk curve to estimate the corresponding time exponent, and reported the resulting range alongside the theoretical prediction of Theorem 1. The results are summarized below:\n\n| Activation Function      | $\\alpha = 0.8$  | $\\alpha = 1.0$  | $\\alpha = 1.5$  |\n| ------------------------ | --------------- | --------------- | --------------- |\n| $H_{e_2}$ (Theoretical)  | -0.75           | -1              | -1.34           |\n| $H_{e_2}$ (Experimental) | \\[-0.83, -0.81] | \\[-1.06, -1.04] | \\[-1.36, -1.23] |\n| ReLU                     | \\[-0.82, -0.72] | \\[-1.02, -0.92] | \\[-1.35, -1.27] |\n| Absolute Value           | \\[-0.73, -0.71] | \\[-0.99, -0.94] | \\[-1.27, -1.23] |\n| $x + H_{e_2}(x)$         | \\[-0.87, -0.84] | \\[-1.11, -1.01] | \\[-1.33, -1.31] |\n\n**Observations:**\n\n* The predictions of our theory continue to hold across the activation functions considered. Since we are unable to include figures in the rebuttal, we describe the qualitative behavior of the plots:\n\n  * For activations with **information exponent (IE) = 2**—i.e., $H_{e_2}$ and absolute value—the risk curves exhibit a clean power-law decay similar to Figure 1(b) in the paper.\n\n  * For activations with **IE = 1**—i.e., ReLU and $x + H_{e_2}(x)$—we observe an initial sharp drop in the early stages of training, followed by a short plateau, and then a decay phase that closely resembles that of the IE = 2 case.\n\n  * In all cases, the quality of the linear fit during the decay phase is comparable to that in Figure 1(b). For $x + H_{e_2}(x)$ and $H_{e_2}$, the risk curve flattens toward the end, replicating the behavior observed in Figure 1(b). For ReLU and absolute value, the slope decreases and the risk continues to decrease at a slower rate.\n\n---\nWe would be happy to answer any follow-up questions in the discussion period."}, {"review_id": "ki3WlZYQOi", "reviewer": "Reviewer_u5Uk", "summary": "This paper explores the optimization and sample complexity of training two-layer quadratic neural networks in high dimensions, focusing on the extensive-width regime where the teacher network width scales as $ r \\asymp d^\\beta $ $(\\beta \\in (0,1)$) and second-layer coefficients exhibit power-law decay $\\lambda_j \\asymp j^{-\\alpha}$. It derives scaling laws for prediction risk, highlighting power-law dependencies on optimization time, sample size, and model width. Using matrix Riccati ODEs and novel matrix monotonicity techniques, it analyzes SGD dynamics, establishing convergence guarantees for feature learning in population and finite-sample settings, offering insights into neural scaling laws.", "questions": "No", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**: The paper delivers a robust theoretical framework, elegantly connecting empirical scaling laws to rigorous mathematics through innovative matrix monotonicity and operator norm control, effectively addressing the complex extensive-width regime. It surpasses previous sample complexity bounds, especially in isotropic settings, and validates the additive model hypothesis, deepening understanding of feature learning dynamics. Its clear problem setup, thorough proofs, and relevance to practical neural network training underscore its value. \n\n**weakness**:\n1. The paper relies on idealized assumptions—uncorrelated Gaussian inputs, perfectly orthogonal teacher weights, and a strict power-law decay for second-layer coefficients—that often don’t match real-world data. I understand the challenges of theoretical research; given the complexity of analyzing practical models, it’s nearly impossible to directly characterize scaling laws for large-scale models. This isn’t a flaw in theoretical work. However, I believe the authors should delve deeper into the challenges of extending their findings to more realistic scenarios and candidly address the limitations of their current theoretical progress.\n\n2. It’s also uncertain whether the matrix monotonicity approach applies to other activation functions like ReLU or optimization methods like Adam. The paper doesn’t explore the method’s scalability or broader applicability, which restricts its relevance to larger neural network problems.", "was_revised": false, "final_justification": "", "rebuttal": "We thank our reviewer for constructive evaluation of our work, and address the reviewer's concerns below: \n\n---\n\n* **Gaussian data:**  The assumption of i.i.d  Gaussian inputs is standard in the theoretical feature learning literature  (see [BAGJ21, MHPG+22, DLS22, BBSS22, AAM23, BBPV23, DKL+23,DNGL24, LOSW24], among others), as it enables analytic tractability through orthogonal polynomial expansions and concentration inequalities. While this assumption can often be relaxed via universality arguments (e.g. [Bruna et al, 2023]), a complete characterization of universality for SGD dynamics in multi-index setting remains an open and active area of research. On the other hand, our goal was to develop a rigorous arguments to reconcile scaling-law risk curves seen in practice with  high-dimensional feature learning setting, which was not very well-understood even with Gaussian inputs. Extending our results to more general input distributions is an important direction for future work.  \n[Bruna et al. 2023] *On Single Index Models beyond Gaussian Data*. \n* **Strict power law decay assumption:** We stated our results under a specific power-law decay for analytical clarity and as it yields the cleanest form of the limiting risk curve. However, our main results, Theorems 1 and 2, extend to a broader class of second-layer coefficients under mild technical conditions on the asymptotic distribution of the coefficients. Under general decay rate condition, the scaling exponents in iteration and width (as shown in Table 1) remain unchanged, while the limiting values in Corollaries 1 and 2 may change. We will clarify this generality in the revised manuscript.\n* **Extension to other activations, such as ReLU:**\nWhile our analysis focuses on the Hermite-2 (i.e., quadratic) activation for both student and teacher networks, we expect that our monotonicity-based argument extends to more general link functions. This expectation is supported by the following arguments:\n   * For ReLU-like activations with nonzero first and second Hermite coefficients, it is known that SGD dynamics initially drive all neurons toward a degenerate rank-1 subspace, governed by the $IE = 1$ component. Once this component is learned, the Hermite-2 term dominates the dynamics, while higher-order terms remain negligible throughout the feature learning phase.\n    \n   * Since the Hermite-2 dynamics exhibit monotonicity, the training trajectory for general link functions can be tightly sandwiched between the dynamics of a purely quadratic network plus/minus some vanishing terms due to higher order terms, which allows the general dynamics to closely track the quadratic case in high dimensions.\n    \n   * To validate this, we conducted experiments using teacher and student networks with ReLU and two other non-quadratic activations. The results, summarized in the table below, show that the empirical scaling exponents for these activations align closely with our theoretical predictions for the quadratic case.\n \n*   **Perfectly orthogonal teacher weights:**\nWe can make the assumption of orthogonal teacher weights without loss of generality in our setting, as we consider quadratic activations. For any teacher directions $(v_j)\\_{j = 1}^r \\subset \\mathbb{R}^d$ and positive coefficients $(c_j)\\_{j=1}^r$, the label can be written as:\n\n$$\ny = \\frac{1}{\\sqrt{\\mathrm{Var}\\left( \\sum_{j=1}^r c_j \\langle v_j, x \\rangle^2 \\right)}}\n\\left( \\sum_{j=1}^r c_j \\langle v_j, x \\rangle^2 -\n\\mathbb{E}\\left[ \\sum_{j=1}^r c_j \\langle v_j, x \\rangle^2 \\right] \\right), \\quad x \\sim \\mathcal{N}(0, I_d).\n$$\n\nIn matrix notation:\n\n$$\ny = \\frac{1}{\\sqrt{\\mathrm{Var}(x^\\top V C V^\\top x)}}\n\\left( x^\\top VC V^\\top x - \\mathbb{E}[x^\\top V CV^\\top x] \\right),\n$$\n\nwhere \\$V \\in \\mathbb{R}^{d \\times r}\\$ has columns \\$v\\_j\\$ and \\$C = \\mathrm{diag}(c\\_1, \\ldots, c\\_r)\\$.\n\nBy the spectral theorem, there exists an orthonormal matrix \\$\\Theta \\in \\mathbb{R}^{d \\times r}\\$ and a diagonal matrix \\$\\Lambda = \\mathrm{diag}(\\lambda\\_1, \\ldots, \\lambda\\_r)\\$ such that:\n\n$$\n\\Theta \\Lambda \\Theta^\\top = V C V^\\top.\n$$\n\nThis implies that the label distribution is equivalent to:\n\n$$\ny = \\frac{1}{\\sqrt{2} \\lVert \\Lambda \\rVert_F} \\sum_{j=1}^r \\lambda_j ( \\langle \\theta_j, x \\rangle^2 - 1 ),\n$$\n\nusing the identity \\$\\mathrm{Var}(x^\\top \\Theta \\Lambda \\Theta^\\top x) = 2 \\lVert \\Lambda \\rVert_F^2\\$.\n\nThus, any label generated using arbitrary directions and weights can be rewritten using orthogonal teacher directions without loss of generality -- we will include a remark in the revision. In the manuscript, we normalize the label variance to 2 and omit the \\$\\sqrt{2}\\$ factor for notational convenience.\n*  **Adam and Larger Neural network problems:** The theoretical understanding of feature learning is still in its early stages, and the analysis of adaptive optimization methods such as Adam, as well as deeper architectures with realistic training dynamics, remains an open challenge. Extending our findings to these settings is an interesting direction for future work. We remark that our goal is not to model all practical complexities, but to provide a rigorous and analytically tractable framework for understanding fundamental phenomena—specifically, smooth scaling-law behavior in the presence of emergent feature learning risk curves. To our knowledge, SGD dynamics in the extensive-width regime is poorly understood prior to our work, even under these idealized conditions. We believe that our analysis (going beyond the \"narrow-width\" regime) represents significant theoretical progress in this direction.\n\n--- \n\n### Additional Experimental Results Demonstrating Broader Applicability\n\nTo demonstrate the broader applicability of our theoretical results beyond the quadratic activation function, we conducted additional experiments using three alternative activation functions: ReLU, absolute value, and $x + H_{e_2}(x)$. In each case, we considered **population gradient descent dynamics** with the **centered version** of the activation (i.e., subtracting its mean), and plotted the corresponding **risk curve**—risk versus time on a log-log scale—following the format of Figure 1(b) in the main paper.\n\nWe considered the setting $d = 5000$, $r = 2400$, $r_s \\in [128, 215, 362, 608, 1024]$, and ran each experiment for $T = 3 \\times 10^5$ iterations. For each activation and width, we fitted a line to the decay phase of the risk curve to estimate the corresponding time exponent, and reported the resulting range alongside the theoretical prediction of Theorem 1. The results are summarized below:\n\n| Activation Function      | $\\alpha = 0.8$  | $\\alpha = 1.0$  | $\\alpha = 1.5$  |\n| ------------------------ | --------------- | --------------- | --------------- |\n| $H_{e_2}$ (Theoretical)  | -0.75           | -1              | -1.34           |\n| $H_{e_2}$ (Experimental) | \\[-0.83, -0.81] | \\[-1.06, -1.04] | \\[-1.36, -1.23] |\n| ReLU                     | \\[-0.82, -0.72] | \\[-1.02, -0.92] | \\[-1.35, -1.27] |\n| Absolute Value           | \\[-0.73, -0.71] | \\[-0.99, -0.94] | \\[-1.27, -1.23] |\n| $x + H_{e_2}(x)$         | \\[-0.87, -0.84] | \\[-1.11, -1.01] | \\[-1.33, -1.31] |\n\n**Observations:**\n\n* The predictions of our theory continue to hold across the activation functions considered. Since we are unable to include figures in the rebuttal, we describe the qualitative behavior of the plots:\n\n  * For activations with **information exponent (IE) = 2**—i.e., $H_{e_2}$ and absolute value—the risk curves exhibit a clean power-law decay similar to Figure 1(b) in the paper.\n\n  * For activations with **IE = 1**—i.e., ReLU and $x + H_{e_2}(x)$—we observe an initial sharp drop in the early stages of training, followed by a short plateau, and then a decay phase that closely resembles that of the IE = 2 case.\n\n  * In all cases, the quality of the linear fit during the decay phase is comparable to that in Figure 1(b). For $x + H_{e_2}(x)$ and $H_{e_2}$, the risk curve flattens toward the end, replicating the behavior observed in Figure 1(b). For ReLU and absolute value, the slope decreases and the risk continues to decrease at a slower rate.\n\n \n---\nWe would be happy to answer any follow-up questions in the discussion period."}]

Author rebuttal:

Meta-review: The submission focuses on the study of SGD for a two-layers neural networks with quadratic activations and orthonormal first-layer features. The authors obtain as a byproduct some neural scaling laws. The paper received two positive reviews and a mildly negative one. Reviewers acknowledge the non-trivial theoretical contribution that justify empirical scaling laws by a robust and elegant analysis. During the discussion period further numerical evidences in support of the results have been provided. The main objection to the acceptance of the paper was raised by Reviewer ```s1U3```, who, although recognizing the quality of the submission, stressed the highly specialistic nature of the contribution and the very idealized setup, that might have a marginal impact beyond the small community of experts working on such idealized set-ups. Although I recognize the validity of many objections of Reviewer ```s1U3``` on the distance between the idealized setup and practitioners, I must recognise that this type of works has in fact a tradition in the NeurIPS tradition and can be of interest to a subcommunity of theoreticians working on simple models in high dimension. In fact, the study of the dynamics in two layer neural networks in the extensive width regime is a current challenge tackled by the theory and the proposed contribution might be significant in this sense. After reading the manuscript I lean therefore towards its acceptance.
Decision: Accept (poster)