From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD
Authors: Konstantinos Christopher Tsiolis
Alireza Mousavi-Hosseini
Murat A Erdogdu
Venue: NeurIPS 2025 poster ()
Keywords: Feature learning
stochastic gradient descent
single-index model
Primary area: theory

Abstract: To understand feature learning dynamics in neural networks, recent theoretical works have focused on gradient-based learning of Gaussian single-index models, where the label is a nonlinear function of a latent one-dimensional projection of the input. While the sample complexity of online SGD is determined by the *information exponent* of the link function, recent works improved this by performing multiple gradient steps on the same sample with different learning rates — yielding a *non-correlational* update rule — and instead are limited by the (potentially much smaller) *generative exponent*. However, this picture is only valid when these learning rates are sufficiently large. In this paper, we characterize the relationship between learning rate(s) and sample complexity for a broad class of gradient-based algorithms that encapsulates both correlational and non-correlational updates. We demonstrate that, in certain cases, there is a phase transition from an "information exponent regime" with small learning rate to a "generative exponent regime" with large learning rate. Our framework covers prior analyses of one-pass SGD and SGD with batch reuse, while also introducing a new layer-wise training algorithm that leverages a two-timescales approach (via different learning rates for each layer) to go beyond correlational queries without reusing samples or modifying the loss from squared error. Our theoretical study demonstrates that the choice of learning rate is as important as the design of the algorithm in achieving statistical and computational efficiency.

From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD
Konstantinos Christopher Tsiolis University of Toronto & Vector Institute kc. tsiolis@mail...... wtw.smmmm....ooooooooooo utoronto.co
Alireza Mousavi-Hosseini University of Toronto & Vector Institute mousavi@cs toronto... edu
Murat A. Erdogdu
University of Toronto & Vector Institute
erdogdućcs. toronto. edu
Abstract
To understand feature learning dynamics neural networks, recent theoretical works have focused on gradient-based learning of Gaussian single-index models, where the label is nonlinear function of a latent one-dimensional projection of the input. While the sample complexity of online SGD is determined by the information exponent of the link function, recent works improved this by performing multiple gradient steps on the same sample with different learning rates yielding a non-correlational update rule and instead limited by the (potentially much smaller) generative exponent. However, this picture is only valid when these learning rates are sufficiently large. this paper, we characterize the relationship between learning rate(s) and sample complexity for broad class of gradient-based algorithms that encapsulates both correlational and non-correlational updates. We demonstrate that, in certain cases, there is phase transition from an "information exponent regime" with small learning rate to a "generative exponent regime" with large learning rate. Our framework covers prior analyses of one- pass SGD and SGD with batch reuse, while also introducing a new layer-wise training algorithm that leverages two-timescales approach (via different learning rates for each layer) to go beyond correlational queries without reusing samples or modifying the loss from squared error. Our theoretical study demonstrates that the choice of learning rate is as important as the design of the algorithm in achieving statistical and computational efficiency.
Introduction
A key aspect of deep learning theory is understand how neural networks can adapt to underlying data structure and achieve desirable statistical and computational complexity through their optimization dynamics. Towards this goal, several works have focused on learning target functions that depend on low-dimensional projections data, such as single- and multi-index models. The complexity of learning these models depends assumptions algorithm. For Gaussian data and online (also called one-pass) SGD on the squared loss, the number of training samples/iterations needed to learn single-index model depends function known as the information exponent [BAGJ21]. Moreover, through computational lower bounds, the information exponent governs the complexity of any Correlational Statistical Query (CSQ) algorithm for learning single- and multi-index models [DNGL23, VE24]. Such an algorithm interacts with data only through queries of the form y)(x)) that lie within fixed tolerance of their
the data distribution and the optimization
property of the target
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

expectation [Kea98, Rey20]. Though SGD can only heuristically be cast as CSQ, this formalism has served as a useful proxy inform attempts to break this "curse of information exponent".
One such attempt is to consider variants of SGD that apply consecutive gradient updates - with distinct learning rates general non-correlational queries h (z, y) and thus bears a connection to the broader class of Statistical Query (SQ) algorithms. Here, the complexity may be controlled by another property of the target function, namely the generative exponent [DPVLB24] which is at most as large as the information exponent, and can be significantly smaller. [JMS24] further demonstrated that batch reuse is not strictly necessary and other online algorithms can also break the curse of information exponent by instead choosing alternative loss functions, while leaving open the study of other components of the training algorithm.
the same batch [DTA 24, LOSW24, ADK+24b) This simulates more
A puzzling observation around reusing batches is that the sample complexity of full-hatch gradient flow on the squared loss, through the best known upper bounds, still depends on the information exponent [BBSS22, MHWSE23J. This is in contrast with the intuition that reusing samples is sufficient for breaking out of CSQ, since full-batch gradient flow reuses the entire dataset at every "iteration". This observation suggests that the role of the learning rate, while ignored in the current literature, is also crucial in determining the query class and the resulting sample complexity of SGD,
1.1 Our Contributions
In this paper aim to answer the following question:
Can we characterize the regimes of complexity emerging from the choice of learning rate?
We give a precise answer to the above question for a class of online iterative algorithms when learning single-index models. Specifically, we make the following contributions:
In Section 3, introduce general framework and provide careful learning-rate rate- dependent analysis of the sample complexity of learning single-index models, resulting in bounds that explicitly demonstrate phase transitions induced by the choice of learning rate hyperparameters.
We show that our framework is expressive enough (Section 4.1) and algorithms with non non-correlational update rules such as SGD with batch reuse (Section 4.2). For the latter, our analysis interpolates between the complexity n ((d(e.-1)v1) and the online SGD complexity decrease, where p and p. are the information and generative exponents respectively, n is the number of training samples, and d in the input dimension. Specifically, we prove phase transitions in the complexity as function of the learning rate for the first update on each batch.
capture both vanilla online SGD
O(d(r-1)vl) the learning rates
In Section 4.3, we show that when considering squared loss, batch reuse is not the only approach that goes beyond CSQ limitations. In particular, we introduce a new layer-wise training algorithm that uses a different scaling of learning rate for the first and second layers of the network, thus using a two-timescales dynamics. We demonstrate that the performance of this algorithm also depends critically on the learning rate of the second layer. When the latter is sufficiently large, the algorithm can recover the target with almost linear sample complexity when the square of the link function has information exponent 1 or 2. Additionally, this analysis can be extended to a sparsely-connected network with D layers, with the same conclusion holding (under further assumptions) when the Dth power of the link function has information exponent 1 or 2.
The rest of the paper is organized as follows. We provide background on Gaussian single-index models in Section 2. In Section 3, we introduce a generic framework to study online gradient-based algorithms and provide our main result. We instantiate this framework for SGD with betch-reuse and the layer-wise vrottimeccales algorithm in Section 4. We sketch the proof of our main result in Section 5, and we conclude in Section
Notation.
k}. For & E N, we use [k] to denote the set f1....,k) All asymptotic notation is with respect to the input dimension d. We use Ō(-) and é(-) to denote O(-) and 0(-) up to polylogarithmic

---

factors, respectively. Similarly, the relations E and 2 denote bounds up to polylogarithmic factors. We write x when a S b and 2 b. An event is said to occur with high probability if its probability is at least 1 - os()). The notations ( and || refer respectively to the Fuclidean inner product and norm for vectors in R2 in the absence of a subscript, while ||v]|A = v Av for E Rd and A E Rdxd For w E gd-1, P., denotes the projection onto the tangent space of gd-1 at w, i.e., P = Ia - wow" T_ For any g E (O, 1)), we write Hermite expansion as Hex where Hep denotes the k-th probabilist's Hermite polynomial [ and un (g) 11 (e) is the k-th Hermite coefficient of g.
g(z) E k=0 (g(g)) w
1.2 Related Work
Feature Learning and Single-Index Models. There is vast body of literature on algorithms for learning Gaussian single-index models, see e.g. [DHI8, CM20J. Here, we focus on more recent works that use gradient-based training. [BAGJ21] studied online SGD for learning high- dimensional single-index models with known non-linearity, where they introduced the infor- mation exponent as the quantity controlling the number of samples needed to learn the model. The representation learned by network single-index models with information exponent 1 was studied in [BES+ + 22, MHWSE231, while [BBSS22] considered gradient flow for learn- ing functions with higher information exponent. On multi-index models, [DLS22] considered one gradient step for learning polynomials, and [AAM23] studied learning general multi-index models where a aaddle-to-saddi dynamies can emerge. General multi-index models remain difficult to analyze [DKII+23, BBPV23, MHWE25]. However, several works have studied the simpler case of additive models [OSSW24, RL24, $BH24, RNWL255, BAEVW25).
0.8
103
Sample size n
0.6
10a
0.4
0.2
10a 10-3
0.0
10
10
100
Learning Rate
Figure Combinations of learning rate 1) and sample size which achieve alignment (w, 0.) 0.5 for network (2.2) with N trained by alternating SGD (Algorithm 2) in the setting a. a = =H3 and d = 50.
CSQ and SQ lower bounds for learning single-index models where developed in [DLS22] and [DPVLB24] respectively, where the former depends on the information and the latter depends on the generative exponent. Similar lower bounds were derived in [AAM23] for multi-index models, where the "leap exponent" controls the complexity, and ITDD* 1DDD+244 244 studied approximate message passing as a proxy for computational lower bounds.
Going beyond unstructured isotropic Gaussian data, [JKMS25) recently studied single-index models with general spherically symmetric input distributions, positing SQ lower bound for running time (which is attained by an SGD variant) and a low-degree polynomial (LDP) sample complexity lower bound. Many works considered the existence of additional input structure or modifications of the single-index model, such as a spiked covariance [MHWSE23, BES 23, BG24, BQ125, JMJS25, ZMN+25 25], sparsity in the input [VE24], or perturbation of the target [CMM25). The recovery of the low-dimensional multi-index subspace has been used to go beyond standard learning frameworks, e.g., to obtain better theoretical guarantees for adversarial robustness [MHJE25].
Learning Rate and Generalization. Numerous works have studied the effect of learning rate on optimization and generalization in deep learning. Notably, deep networks with large learning rate can operate near the "edge of stability" [CKL+ 221], where has been empirically observed that such large learning rates improve generalization by preferring flat minima [LWM19, LBD 20, JAA+21 BD21, and references therein], learning sparse features [AVPVF23), or obtaining larger margin [CWM 224. Closer to our setting, [ADK 24a] study the optimal choice of learning rate for online SGD. However, while their algorithm always remains correlational regime, we consider a wide range of learning rates to understand the effect of non-optimal choices in practice, and demonstrate phase transitions in the behavior of the SGD depending on stepsize, going from correlational regimes dominated by information exponent to full statistical query regimes dominated by generative exponent.

---

2
Problem Setup
We consider a supervised regression setting where the inputs are drawn from the standard Gaussian distribution and the labels are generated according to the single-index model, i.c.
y a. (..((,,;) 0.)) + Si:
3.3. (O, ac
(2.1)
where 0, -giiiin is the ground truth direction, o, R - R is a (nonlinear) link function, and Ça is L..d. symmetric sub- Weibull' [VGNA20] label noise with ((1) tail parameter.
We learn the above model with two-layer neural network? / with N hidden neurons, first-layer weights w E gd-1, biases by E IR, second layer weights a, E IR, and polynomial activations 0j R + Ih as in [LOSW24). When convenient, we use the shorthand of encoding the first layer weights rows in the matrix W E R RNd, the second layer weights by the vector E RM, and the biases by the vector b E R The network outputs a weighted average of the hidden layer activations:
[e; W, b)
= N J=1
Σ
agoz (ar,,, + bb)-
(2.2)
Our objective is to characterize the number of iterations (and thus, the number of samples) required for weak recovery of 0, as a function of the learning rate for online iterative algorithms. That is, starting from uniform initialization on the sphere gd-1 where (0, (0)) ) d/1/2 with high probability, seek T such that (0., w, ( 2 1/ polylog d. Studies of online SGD and variants [BAGJ21, DTA+ 24, LOSW24] argue that achieving weak recovery is the computational bottleneck in fitting a single-index target. Once this is achieved, strong recovery (i.e., (0., w) 2 1 - & for some & > 0) and approximation of the target via ridge regression on a proceed with ((d) sample complexity. We extend these findings to our general class of gradient-baser algorithms Appendices B.6 and B.7.
We introduce two properties of o, that are known control the complexity of gradient-based learning and the complexity of learning with statistical queries.
Definition 2.1 (Information Exponent, [BAGJ21]). For any g E [,, 1)), let ux(g) denote the kth coefficient in its Hermite expansion. The information exponent of g is defined as
IE(g) min(k (k= > 0 ug + 0}.
(2.3)
Throughout this paper, we denote the information exponent of the link function a, in (2.1) by p. and we use the notation p; == IE(ot) for i 2 2 to denote the information exponents of powers of о.. [BAGJ21] show that online SGD with the square loss has sample complexity while [DNGL23] introduces smoothed online SGD, which achieves the optimal 2 d(r/2)v1 sample complexity for the class of CSQ learners. Beyond correlational queries, the generative exponent controls the complexity of any statistical query learner.
((dde-1)vi)
Definition 2.2 (Generative Exponent, [DPVLB24)). For any E I2(N(0, the generative exponent is defined as the smallest information exponent over all L2 transformations of g, i.e.,
GE(g) = inf
((L.1g)N(0.1) (E(T9).
(2.4)
Note that GE(g) IE(g) for all g. Throughout this paper, we denote the generative exponent of 0. in (2.1) by p.. While [DPVLBB24] developed an optimal algorithm with sample complexity n 2 d(p-/2)v1, [LOSW24, ADK ADK+24b] showed that SGD has sample complexity n 2 díp.-1)V when going over each sample twice. Both leverage the following crucial property.
Lemma 2.3 ([LOSW24] Proposition 6, Lemma 8). Suppose there exists an orthonormal polynomial basis of the space L ((=.) (0, 1)). Then there exists 1 N such that IE(o!)) = p.. Moreover, if o_ is polynomial of degree at most g, then I < C2 for some constant Cg depending only on
Note that the class of sub- Weibull random variables includes Sub-Gaussian and eebexonnnentall random variables and is closed under transformations with at most polynomial growth (up to changing the tail parameter). "I Appendix C.4, we propose an algorithm for network with D > 2 layers and prove sample complexity improvements over the batch reuse SGD of [ADK 24b, LOSW24] under assumptions
and the oj

---

This result can be used to develop optimal algorithms [CWL* 251], and has two major implications. First, it immediately implies that batch reuse SGD with the correct choice of hyperparameterrs has linear sample complexity (up to log factors) for any polynomial target. Second, and importandy for our work, suggests that if the update for w contains the monomial transformation y' (a. ((x, 0,))),, the sample complexity can be reduced depend on p. instead of p. In the subsequent sections, we emphasize that this will only occur if the scaling of the y' term (as determined by the learning rates) is sufficiently large. Otherwise, we fall back into the information exponent regime.
3 Sample Complexity of a Generic Online Algorithm
To generalize several notions of gradient learning of single-index models, we consider updates to first-layer weight of the form
(++1)
w (1+1) + w(t) + rbn (0) w w)) P Puo x00, (((+1)
(3.1)
1 |
where (1)) is an i.i.d. draw from the target single-index model (2.1). > 0, 17 2 0, P. with Ia ww (i.e., the projection onto the tangent space of the unit sphere at w)) and bh is an update function based on "general gradient oracle". This formulation is similar to that of [CWI++25], who also use generalized gradients, but additionally incorporate weight perturbation and averaging to achieve optimal rates. We view latter modification as complementary to our work, but we note that can push the algorithms we study in Section 4 towards SQ-optimality when 7 and are both chosen as large as possible. The use of a spherical dynamics is common in studies of gradient-baser learning of single-index models and is motivated by the fact that the optimization is done over the unit sphere Sid-1 [BAGJ21, DNGL23, LOSW24, ADK 24b].
Note that due to the rotational symmetry of the Gaussian single-index model, the standard squared loss E(y. y²) = (y - y²)² and the correlation loss Ely, v') - yy induce identical gradients in the population limit, and are known to produce similar dynamics under small initialization of the second layer (see e.g.. [AAM23, LOSW24]). Therefore, in this paper we examine choices of the oracle th based on the correlation loss.
In the examples we consider, y and v) are learning rates that arise due to multiple gradient updates within the same iteration. Each plays a distinct role, with 7 serving as "global" learning rate, and 7) controlling the scale of any conccerrelatin terms in the oracle vh. Both of these learning rates directly influence sample complexity. but only y will induce the aforementioned phase transition of interest. Moreover, the largest possible value of y is constrained by the value of n (otherwise the algorithm can diverge).
We view such algorithms as inherently online, where the first step performs some transformation of the labels (modulated by 17), and the second step uses the update of (3.1). This view can be extended any constant number of steps on the same batch of samples. For such algorithms, the dependence of th, on 1y becomes nonlinear, and the key quantities elucidating the effect of this hyperparameter on the sample complexity are the Hermite coefficients*
M4 (1) == (((,,))~ (a- (()) i [r].
(3.2)
We highlight three examples in the next section:
1. Online SGD: v (y. 2) = (=) and μ4 = in,(o.)) (o) There is no dependence on 17 as each iteration involves single gradient step with learning rate 7. See Section 4.1 for details.
deg(() ((()) y and (4(1) X (k-1)!
2. Batch reuse SGD: , 2) = yo'(2) +
k=2
The algorithm first takes gradient step with learning rate 77, followed by another gradient step on the same batch with learning rate This algorithm was previously studied in [ADK 24b, LOSW24). See Section 4.2 for details.
Ek-n (nd))-1
(k-1)) (a')
In what follows, we drop the subscript j for convenience. 'The formulation below is valid in the noiseless case. We handle sub- Weibull label noise in Appendix B.
5

---

3. Alternating SGD: 2y(,,2) yo' + (z))o'22 and pa(n) = (uu(ox));(()) + (00L1(000),,,(3" The algorithm first takes a gradient step on the second layer with learning rate 7), followed by gradient step on the first layer with learning rate 7. This is our novel variant that we detail in Section 4.3.
We make the following assumptions on the target link function o, and the student update V/y, The first ensures that all noise terms are sub- Weibull, allowing us to make concentration arguments. Prior works make similar assumption (c.f., [ADK 24a, Assumption 1]. [LOSW24, Assumption 21).
Assumption 3.1. The link function d+ has at most polynomial growth, i.e, there exist constants K1, K2 > 0 such that 1o,00.... (z)l S K₁ (1+|22)) for all E R. The update function v. is polynomial of degree at most r = (1) in each of its arguments and with ((1) coefficients.
The second assumption provides some degree of alignment between o and ox, without which the model misspecification so severe that weak recovery may not be achieved (c.f., [BAGJ21, Remark 2.3]. [LOSW24, Assumptions 2 and 3], [ADK + 24b, Assumption 4), [CWL++25, Assumption 4b)()))). We explore how it manifests for different examples Section 4.
Assumption 3.2. For any i E argmin (dd we have p:- (1) > 0.
isigr
34:500
Below, we state our main result for a generic gradient- algorithm.
Theorem 3.3. Suppose Assumptions 3.1 and 3.2 hold. Let w &dd-1 such that (0., w(0) x d-/2, Then, there exists C Z 1/ polylog d such that for any E (0. if S C8 maxigisr pad then
T()) = min (1a())
(3.3)
1sis
P.So
iterations of (3.1) are necessary and sufficient to achieve (0,, w) 2 1/ polylog d with probability at least 1 8.
The nonsmooth min operation in (3.3) implies that the sample complexity T(1) can exhibit nonsmooth phase transitions when the index yielding the smallest term changes. We can identify these phase transitions by determining for which y we have /4, (n) = , (n) for given indices * j- This is the phenomenon we will concretely illustrate with batch reuse SGD and alternating SGD in Section 4, where the coefficients μ,, depend on the information and generative exponents o and non-decreasing in 1).
Remark 3.4 (On the Optimal Choices of y and 1)). The optimal choice of 7 depends on y through the coefficients μa(1)) It is immediate from the statement of Theorem 3.3 that the best choice is Y maxisisr (a())d-(iv))) Then, the sample complexity reads
T(m) min ((((())))((-11)1) #.50
(3.4)
When the p4 are all non-decreasing in T, is clear that the best sample complexity is achieved by laking 1j as large as possible subject to the constraint imposed by Assumption 3.1.
4 Examples
We illustrate the applicability of Theorem 3.3 with three example algorithms: online SGD, batch reuse SGD, and a layer-wise algorithm we term alternating SGD. The latter algorithms contain non- correlational terms that, when 17 is chosen sufficiently large, lead to strictly better sample complexity than vanilla online SGD. We outline the computation of μ4 each these cases explicitly capture this dependence on We assume that the largest possible is chosen for each algorithm (recall from
Theorem 3.3 that y S maxisisr -

---

4.1
Online SGD
We study vanilla (spherical) online SGD on the correlation loss E(y, 3/) yy as baseline for our framework. When 0j = 1, it gives the one-step update
(t+1) w
(++1) w t 3 o d'x( w w p P
w (++1)
(4.1)
[++))]
for j [N]. The update oracle ,, (g, 2) = yo' (z) is a single correlational term that does not depend 17. Consequently, there is only sample complexity regime and no phase transition. A short calculation in Appendix C.1 shows that μ4 = (a, (u)()) With this in hand, Theorem 3.3 gives the following result.
Corollary 4.1. Assume up(p.)up(O)) > y (4v1), and w(() gd-1 such that (0., w w()) x d/1/2 Then, with high probability, ((d 1))1 iterations of the update (4.1) are necessary and sufficient to achieve weak recovery.
This matches both the sample complexity bound and the constraint on y in [BAGI21, Theorem 1.3].
4.2 Batch Reuse SGD
Next, we consider the modification online SGD where two gradient steps are taken the same data. [DTA+2] 24] employ dynamical mean field theory (DMFT) to argue this enlarges the class of targets learnable with linear sample complexity. This is because the two-step update implicitly introduces nonlinear label transformation (and thus, con-correlational terms) into the update that speed up learning. This approach which we detail in Algorithm and call batch reuse SGD was further studied in [LOSW24] and [ADK* LADK+24b], where its sample complexity was characterized for any polynomial target, regardless of whether it can be learned in linear time. Both employ two distinct learning rates, which is necessary to simultaneously control the normalization error and ensure that the non-correlational term is sufficiently large (see in particular (LOSW24, Section 4.2)).
Algorithm 1: Batch Reuse SGD
Input: Learning rates 1), > 0, sample size T Initialize (0) Unif(Sd-1)
for t = 0 to T - do
Draw i.i.d. sample (x. y)
(o()) + (t)) + nyyo w ) w
(1+1)) t (() + Tyo' ((x, vo())) )
Pil
Normalize ((++1) w((+l) (t)
end
Output (T)
Combining the two update steps for w in Algorithm gives (before normalization)
w (t-1) (!) Yyo' ((æ, ()) + /||>
| | yo ((x, w (*))) P (1))
(4.2)
The norm ||=||
p. sub- Weibull and concentrates around its mean d 1. We replace the norm
with d in the population dynamics and absorb what remains into the sub- sub-Weibull noise term (see Section B.4 for details on handling the noise). Hence, by a Taylor expansion,
(z)) (2)))
V, 2) yo' (z)
(4.3)
(k 1)!
k=2
Note that Assumption 3.1 requires vi,, to be O(1) and therefore 77 S d' The quantity ndd controls the scaling of the higher order terms in the update. Indeed, we show in Appendix C.2 that
(nd)*~1 (k 1)! u4 (0 (0/)= (o')- (u)a))))
(t(1)
(4.4)
7

---

Corollary 4.2. Suppose Assumptions 3.1 and 3.2 hold, 2 d'',,,, , S (ad and w(()) E gd-1 such that (0., w(0)) = d-1/22 1/2, Then, with high probability,
T(n) min ((rd)) ((nd))2(t-))) - S5
(4.5)
iterations of Algorithm are necessary and sufficient to achieve weak recovery.
For any two distinct i,j with Pa Py > 0, induces the phase transition:
1(1 26--1)
(nd)-2(i-1) 2(i-1) (P: 1Jv1 I (nd) - 20 - (P)
S d
(4.6)
In particular, suppose that 1p (1) (o') (o.) > and up(a,)up(o) > 0 hold, which can be achieved with (1) probability by a randomized activation agnostic to a. as [LOSW24). Taking // $ "d"""" gives the sample complexity T ((d(--1)v)) which matches the online SGD bound [BAGJ21]. On the other hand, when r 2 I, taking 1j 2 d'1 as in [LOSW24] matches their sample complexity bound T = (d)). Intermediate values 1j interpolate between these two regimes. Appendix D details experiment with batch reuse SGD exhibiting this phase transition.
4.3 Alternating SGD
Next, we consider a novel and simple variant of SGD that introduces a non-correlational update without changing the correlational loss. Algorithm 2, which we call alternating SGD, employs two-step process to update W. First, computes a gradient update for a with learning rate r). Then, uses the updated value à in gradient update on W with learning rate 7. We apply the same projected gradient and normalization to w as before. Crucially, the same sample (æ, y) is used in these updates. This produces a similar effect batch reuse SGD without the need to apply consecutive gradient updates to W. Specifically, the update to W in alternating SGD contains the label transformation y -+ y². This leads a reduction in sample complexity if p2 == IE(o?) p and the second layer learning rate is sufficiently large.
Algorithm 2 is related to studies [BMZ24, MB23, BBPV23, WMHC24, BPV25), where training the second layer at a faster timescale simplifies the analysis. However, unlike these works, we perform sequential gradient updates on the two layers, and use the different learning rate scales to obtain better sample complexity. We believe that the study of this algorithm is useful from theoretical perspective and view it proof of concept to demonstrate what mechanisms might be at play in neural network training so that they achieve near-optimal sample complexity.
two-timescales optimization dynamics of two-layer networks
Algorithm 2: Alternating SGD
Input: Learning rates 7/, 7 > 0, sample size T Initialize w ()) Unif(Sd-11
for t = 0 to t = T 1 do
Draw i.i.d. sample (x. y)
Update (+++1) + + nyo (x, (())) Update ((++)) )) t- ((t) +
((
Normalize (t+1) + w (((+l)/ ( /|//((-111]
end
Output (T)
Given the second-layer gradient update (1+1) a + nyo w ()))) the update for
cly, 2) = yao' (z) + my (z)oo(()
(4.7)
Our calculation in Appendix C.3 yields the coefficients
H4 (n) aiu,(o.).(()) + (oo-1(oo')u
(4.8)
The first term is identical to what emerges from the vanilla online SGD update (4.1). The second term arises from the non-correlational update. Note that if 1) is chosen too small, the latter term may not dominate even when P2 < p. The following makes this intuition rigorous.
8

---

Corollary 4.3. Assume Hpp > 0. rj E 1 y= max(d (BVI), ,nd and wil) E gd-1
such that (0., w) d-1/22 Then, with high probability,
T(n) ((d'p- A ( 2d1e=
(4.9)
iterations of Algorithm are necessary and sufficient to achieve weak recovery.
The assumption Mp.Hp> > O is derived from our more general Assumption 3.2 and holds with (1) probability if a follows the randomized construction in [LOSW24, Appendix B.1]. The sample complexity result implies a phase transition between the regime where the correlational term dominates and one where the non-correlational term dominates, occurring at (when p 2 2)
dp-1 2d
17 d =(p-pa)V(i-2))
(4.10)
In other words, alternating SGD improves over online SGD if squaring the target reduces its informa- tion exponent and 1 is of strictly larger order than the threshold above. For example, if o, Heg, then p 3 and P2 2. The phase transition occurs at 1) x d=1/2 At or below this threshold, alternating SGD has quadratic complexity, while 2 1/ 1/polylog d gives linear complexity (up to polylogarithmic factors). Meanwhile, intermediate values of rj interpolate between these two regimes.
Figure illustrates simulation for the above toy example. As predicted by Corollary 4.3, we observe two distinct phases. In the first phase, the number of samples required achieve small test error is constant in 7 until a critical threshold is reached, at which point the second phase begins and the test error decreases at ((1/)²)) rate.
Extension to Deeper Networks. It is possible to further improve the sample complexity for alter- nating SGD in the case P2 > 2 by employing a deeper (but sparse) neural network. The natural generalization of the algorithm is take gradient step on each layer while keeping the remaining layers frozen, starting from the outermost layer. In Appendix C.4, we show that, under assumptions on the Hermite coefficients of compositions of activation functions this fits into framework with (4(n)= Σ Tp² (o!! and
T max ((0- ISED
(4.11)
where D is the number of layers. The number of phase transitions in is one less than the number of distinct p; = IE(o))) i E [D]. Moreover, if 17 Z 1/ polylog and D 2 I, where I is as in Lemma 2.3, the sample complexity is (d). As we will see in the next subsection, depth D plays an analogous role the degree of a in batch reuse SGD.
Proof Sketch
The complete proof of Theorem 3.3 in Appendix B is inspired by and builds on previous analyses of online algorithms [BAGJ21, LOSW24]. outline the main steps here. We focus on the sample complexity upper bound; the proof of the matching lower bound is similar.
First, we derive the expected dynamics for single update (3.1). The key quantity in this step the alignment between the one-step update function (*) (u, (xx(), w(()) P.d. Pulee (x) and the target
direction 0., which has expectation
(0, (0)] = Ex (y, (zz, w (0)) 10 x, 0.)
Σ (0 (0., w (0)2).
15.1)
where we have hidden the conditioning on previous iterations for convenience. The last equality is obtained by taking the Hermite expansion of th, in each of its arguments (hence the appearance of the μ4s defined (3.2)) and applying Stein's 's Lemma. Now, what distinguishes our framework is that we do not assume that the nonzero μ4 are ((1) In the analysis of online SGD in [BAGJ21], Mp is the
'These assumptions difficult verify in general. However, in the same appendix, show that they hold for a three-layer network with a(2) = z² and target satisfying uz(a?) O. which case weak recovery occurs in (d) iterations when 1) 1.

---

first non-zero coefficient, and thus the pth term in the above sum dominates. Similarly, nonzero pp. yields the dominant term in the analysis of batch reuse SGD. On the other hand, we allow for the situation where the first nonzero 14 is of strictly smaller order than some M4 with j >> i due to small 7)-
The resulting one-step dynamics are
(0,,w(t) 2 (0., w)) + 701 Σ ui (r w0y +zvl0 -2d, w w()),
(5.2)
where Čj > 0 a constant, 2/(t) is aub-Weibull random variable independent from prior iterations that results from the label noise and the randomness in the input æ, and the final term is a bound on the impact of the normalization step (3.1). The latter term can be controlled and absorbed into the expected update term when y S maxigigr pad (+V1).
Next, we unravel the recurrence to obtain
t-1 Mi 1e w0 (0,)
2-1 v(s)
(0., ()) 2 (0., ()) + 11 ΣΣ
(5.3)
and control the last term with martingale and sub-Weibull concentration bounds. We identify which of the terms in the expected update dominate by bounding the sequence
1/2
1/2 + Σ
Enlalt)i a d
(5.4)
leveraging Grönwall's Inequality (Lemma A.3) for the i 2 term and the Bihari-LaSalle Inequality (Lemma A.4) for the i 2 terms. Setting this equal to Z 1/ 1/polylog yields the sample complexity.
6 Conclusion
This work demonstrates that the learning rate is a fuundamental factor in determining the sample complexity of gradient-based algorithms for learning single-index models with neural networks. We show that algorithms that employ a combination of correlational and correllaaaii update terms (with separate learning rates) exhibit a phase transition between distinct sample complexity regimes as function of the scaling of the con-correlational term. In both our novel alternating SGD and the batch reuse algorithm of [DTA + 24, LOSW24, 3DK+244) this scaling manifests as learning rate y that appears the first of two-step update. r) is chosen too small, then the sample complexity no better than the n = ((d bound for online SGD. On the other hand, when r) increases beyond the phase transition threshold, it interpolates between this information exponent regime and generative exponent regime where the rate becomes = (IdV..IIvv
In addition to illustrating of the phase transition, our novel alternating SGD algorithm presents alternative to batch reuse and changing the loss for improving upon the CSQ sample complexity. Interestingly, admits a natural generalization neural networks with more than 2 layers that enlarge the class of target polynomials for which weak recovery can be achieved with linear (up to poly- logarithmic factors) sample complexity. These findings open the door to investigating theoretically tractable settings where the relationship between depth and sample complexity can be precisely quantified.
Other natural directions for future work include an extension of our framework to multi-index models [AAM23], more general input distributions [JKMS25), non-polynomial activation functions, and non-constant learning rates. Given the generality of our update oracle thy we also expect that our framework can be adapted capture landscape smoothing [DNGL23] as well as similar algorithms that aggregate gradients evaluated at perturbed weights [CWL+ - with the associated hyperparameter being cast as our r7.
Acknowledgments and Disclosure of Funding
The authors thank Denny Wu and Jivan Waber for helpful discussions. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through
10

---

CIFAR, and companies sponsoring the Vector Institute. KCT was supported by NSERC through the PGS-D program. MAE was partially supported by the NSERC Grant [2019-06167], the CIFAR AI Chairs program, the CIFAR Catalyst grant, and the Ontario Early Researcher Award.
References
[AAM23] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. SGD learning on neural net- works: Leap complexity and maddee-t--sddo dynamics. In The Thirty Sixth Annual Conference on Learming Theory, pages 2552-2623. PMLR, 2023.
[ADK 24a] Luca Arnaboldi, Yatin Dandi. Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. Online learning and information exponents: On the importance of batch size, and time/complexity tradcofts. arXiv preprint arXiv:2406.02157, 2024.
[ADK*244) Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows SGD to Iearn high-dimensional multi-index functions. arXiv preprint arXiv:2405. 15459, 2024.
[AVPVF23] Maksym Andriushchenko, Aditya Vardhan Varre, Loucas Pillaud- and Nicolas Flammar- ion. SGD with large step sizes learns sparse features. In International Conference on Machine Learning, pages 903-925. PMLR, 2023.
[BAEVW25] Gérard Ben Arous, Murat A Erdogdu, N Mert Vural, and Denny Wu. Learning quadratic neural networks in high dimensions: Sgd dynamics and scaling laws. arXiv preprint arXiv:2508.00 036888 2025.
[BAGI21] Gerard Ben Arous, Reza Gheissari. and Aukosh Jagannath. Online stochastic gradient descent non-convex losses from high-dimensional inference. J. Mach. Learn. Res., 22:106-1, 2021.
[BBPV23] Alberto Bietti, Joan Bruna, and Loucas Pillaud- Vivien. On learning gaussian multi-index models with gradient flow. arXiv preprint arXiv:2310. 19999993, 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 processin systems, 35:9768-9783, 2022.
[BD21] David Barrett and Benoit Dherin. Implicit gradient regularization. In International Conference on Learning Representations, 2021.
BES' 22] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances Neural Information Processing Systems, 35:37932- 37946, 2022.
[BES [23] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu. Learning in the presence of low-dimensional structure: A spiked random matrix perspective. Thirty-seventh Conference on Neural Information Prucessing Syxtems, 2023.
[BG24] Lorenzo Bardone and Sehastian Goldt. Sliding down the stairs: How correlated latent variables accelerate learning with neural networks. arXiv preprint arXiv:2404.08602, 2024.
[BM7224 Raphaël Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics, pages 1-84, 2024.
[BPV25] Raphaël Barboni, Gabriel Peyré, and François-Xavier Vialard. Ultra-fast feature learning for the training of two-layer neural networks in the two-timescale regime. arXiv preprint arXiv:2504.18200 2025.
[BQI25] Guillaume Braun, Minh Ha Quang, and Masaaki Imaizumi. Learning single index model from anisotropic data with vanilla stochastic gradient descent. arXiv preprint arXiv:2503.23666 2025.
[CCM11] Scok-Ho Chang, Pamela C Cosman, and Laurence B Milstein. Chernoff-type bounds for the gaussian error function. IEEE Transactions on Communications, 59(11):2293 2944, 2011.
22] Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2021.

---

[Cla87] Dean S Clark. Short proof of a discrete Gronwall inequality. Discrete applied mathematics. 16(3):279-281, 1987.
[CM20] Sitan Chen and Raghu Meka. Learning polynomials in few relevant dimensions. In Conferencce on Learning Theory, pages 1161-1227. PMLR, 2020.
[CMM25] Elisabetta Cornacchia, Dan Mikulincer, and Elchanan Mossel. Low-dimensional functions are efficiently learnable under randomly biased distributions. arXiv preprint (txXix:2500206444433 2025.
[CWL+25] Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, and Tianhao Wang. Can neural networks achieve optimal cemputational-statiittn tradeoff? an analysis on single-index model. In The Thirteenth International Conference on Learning Representations, 2025.
[CWM+24] Yuhang Cai. Jingfeng Wu, Song Mei, Michael Lindsey, and Peter Bartlett. Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization. Advances in Neural Information Processing Systems, 37:71306-71351, 2024.
[DHI8] Rishabh Dudeja and Daniel Hsu. Learning single-index models Gaussian space. Conference Learning Theory, pages 1887-1930. PMLR, 2018
[3] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at time. arXiv preprint arXiv: 1805 2023.
[DLS22] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn represen- tations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.
[DNGL23] Alex Damian, Eshaan Nichani, Rong Ge, and Jason D Lee. Smoothing the landscape boosts the signal for SGD: Optimal sample complexity for learning single index models. Advances in Neural Information Processing Systems, 36:752-784, 2023.
[DPVLB24] Alex Damian, Loucas Pillaud- -ivien, Jason Lee, and Joan Bruna. Commutaaioonal-sttiitti gaps in Gaussian single-index models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1262-1262. PMLR, 2024.
[DTA 224 Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdehorova, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: breaking the curse of information and leap exponents. In Proceedings of the 41st International Conference on Machine Learning, pages 9991-10016, 2024.
[JA++21] Stanislaw Jastrzebski, Devansh Arpit, Oliver Astrand, Giancarlo B Kerg, Huan Wang, Caiming Xiong, Richard Socher. Kyunghyun Cho, and Krzysztof J Geras. Catastrophic Fisher explosion: Early phase Fisher matrix impacts generalization. In International Conference on Muchine Learning, pages 4772-4784. PMLR, 2021.
[JKMS25] Nirmit Joshi. Hugo Koubbi, Theodor Misiakiewicz, and Nathan Srebro. Learning single-index models via harmonic decomposition. arXiv preprint arXiv:2506.0m 09887, 2025.
[JMJS25] Taj Jomes-McCormiee Aukosh Jagannath, and Subhabrata Sen. Provable benefits of unsupervised pre-training and transfer learning via ingle-index models. arXiv preprint arXiv:2502.16849 2025.
[JMS24] Nirmit Joshi, Theodor Misiakiewicz, and Nati Srebro. On the complexity of learning sparse functions with statistical and gradient queries. Advances in Neural Information Processing Systems, 37:103198- 10024111111,1---1111111111111111 2024.
[Kea98] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6);983-0066 1998.
[LBD*20] Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer. Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: The catapult mechanism. arXiv preprint arXiv:2003.02211. 2020.
[LOSW24] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low- dimensional polynomials with SGD near the cetimatiiontthhorde limit. In The Thirty-eighth Annual Confer- ence on Neural Information Processing Systems, 2024.
[LWM19] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in neural information processing systems, 32, 2019.
12

---

[MB23] Pierre Marion and Raphaël Berthier. Leveraging the two-timescale regime to demonstrate convergence of neural networks. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[MHJ225] Alireza Mousavi Mousavi-Hosseini, multi-index models high dimensions. The Thirteenth International Conference on Learning Representations, 2025.
Hosseini, Adel Javanmard, and Murat A Erdogdu. Robust feature learning for
[MHWE25] Alireza Mousavi- Hososiii, Denny Wu, Murat A Erdogdu. Learning multi index models with neural networks via mean field langevin dynamics. In The Thirteenth International Conference on Learning Representations, 2025.
[MНWSE23] Alireza Mousavi- Hosssvii,,sseiii,, Denny Wu, Taiji Suzuki, and Murat A Erdogdu. Gradient-based feature learning under structured data. Advances in Neural Information Processing Systems, 2023.
[O'D21] Ryan O' O'Donnell. Analysis of boolean functions. arXiv preprint arXiv:2105.1000 2021.
[OSSW24] Kazusato Oko, Yujin Song, Taiji Suzuki, and Denny Wu. Learning sum of diverse features: Computational hardness and efficient gradient based training for ridge combinations. In The Thirty Seventh Annual Conference Learning Theory, pages 4009 4081. PMLR, 2024.
[Rey20] Lev Reyzin, Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557, 2020.
[RL24] Yunwei Ren and Jason D Lee. Learning orthogonal multi index models: A fine-grained informa- tion 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.
[$BH24] Berfin Simşek. Amire Bendjeddou, and Daniel Hsu. Learning gaussian multi-in index models with gradient flow: Time complexity and directional convergence. arXiv preprint arXiv:2411.0874) 2024.
(TDD*24) Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, and Florent Krzakala. Fundamental computational limits of weak learnability in nigh-dimensional multi-index models. arXiv preprint arXiv:2405. 15480, 2024.
[VE24] Nuri Mert Vural and Murat A Erdogdu. Pruning is optimal for learning sparse features in high- dimensions. In The Thirty Seventh Annual Conference on Learning Theory, pages 4787-4861 PMLR, 2024.
[Ver18] Roman Vershynin. High- Diige-Dimessioul Probability: An Introduction with Application in Data Science. Cambridge Scries in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[VGNA20] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub- Bub-Weibull distributions: Generalizing sub- gaussian and eb-eepenneniall properties to heavier tailed distributions. Stat, 9())=311, 2020.
[WMHC24] Guillaume Wang, Alireza Hosssvv,,,s,inni,, and Lénaic Chizat. Mean-field langevin dynamies for signed measures via a bilevel approach. Advances in Neural Information Processing Systems, 37:35165-35224, 2024.
25) Thomas Zhang, Behrad Moniri, Ansh Nagwekar, Faraz Rahman, Anton Xue, Hamed Hassani, and Nikolai Matni. On the concurrence layer-wise preconditioning methods and provable fcature learning. arXiv preprint ar arXi::2502.0/66. 2025.
13

---

A Technical Background
We synthesize and reference the key technical background that forms the backbone of our proofs that appear in Appendix B.
A.1 Hermite Polynomials
Definition A.1 (Probabilist's Hermite Polynomials [O'D21, Definition 11.29]), The probabilist's Hermite polynomials Hej E IR, j E No. are defined
d
H=,(z) (-1)e
(A.1)
d=
For example, the first four probabilist's Hermite polynomials (eo(z) 1, Hei 2, Hez(z) z² 1, and Hey(z) = 2 3z.
It is well-known that (Hey) o form orthogonal basis for [2 1)). In particular,
(oeNoo = =-,;=
(A.2)
Since our proof's rely on the analysis of Hermite polynomials applied to inner products, the following consequence of orthonormality is particularly useful.
Lemma A.2 ([O'D2) D21, Proposition 11.31J). Suppose that 2, 2' N 1) such that Cov(z, 2/) p. Then,
B Hey( =ippp 8;=j-
(A.3)
In particular, for NO0 Ia), E RRd, 0, TRdd, we have
Ex He; ((x, m) He, 0.))] = j!(w,, 0.y 0.)ā
(A.4)
A.2 Discrete- Time Dynamical Systems
Lemma A.3 (Discrete Grönwall Inequality [Cla87]). Lei {me] be sequence such (hat mo and m, S a + e E my for all t 1, where a, C.C.>. >> O. Then, for all t 2 0,
m. S a(1 + cc² < ae
(A.5)
tt11 E my for all 2 1, then me 2 a(1 + c)² for all 1 2 0. Moreover, if instead m, 2 a e
Proof. The result casily follows by induction. The statement trivial for t = 0. Suppose now that holds for some & > 0. Then,
Σ a(1 c) = a (1+c)(+] - a(1 +c) (A.6)
14+1 S a + Σ mj Sa
The same argument can be used for the reversed inequality.
Lemma A.4 (Discrete Bihari-LaSalle Inequality [BAGJ21, Appendix Cl: [LOSW24, Lemma 18]). Let {mi 100 a sequence such that my a and m I a + + t-1 a, C > 0, and l 2 3. Then,
j=0 my for all 2 1, where
mi I
(A.7)
(1 (k 2)c 21)
21) E-2
c(k - 2
Moreover, if instead m. 2 + 2 m
s-1 -- then
m4 2
(a (x--2) - -c).
(A.8)
(1 Sa 2()
c(k: 2)
14

---

Proof. Let {ar be such that do = and = a + c (-- k-1
Upper Bound. Define {br by be = a and b, a + 2j (
Then, me S be by
definition. We prove that by S at by induction. Clearly, by ag. Now,
bo+1 = a Σ (dmm))=1 be + c(ma)*- S by + c(bb)* S at + c(ai)- = actli (A.9)
where the last inequality follows from the induction hypothesis. Hence, my s by S for all t 2 0.
Notice for all & that
0 01
00+1 1
dr
2
ac++ 1
dx
1
1
(A.10)
xk
k. 2
a2
a++1
Rearranging the above, we have
(k-2)
-lk-2) ckk 2).
a++1 2 at
(A.11)
Unrolling the recurrence, obtain
2k- 2 ag
2k clk- 2)t.
(A.12)
So long a (k- clk 2) 0, we can rearrange to obtain the desired upper bound
0t 5 (ar (k-2) c(k- -2))
(A.13)
(1 (k: 2)ca xt.
The condition (k-2) - c(k - 2)t > 0 holds so long as
< c(k 2)a = O(a (aa-(k22)). (k=
(A.14)
matching the condition in (A.7).
Lower Bound. A similar induction argument to the one in the upper bound proof shows that m, 2 ae for all 1
For each t 2 0, let by = a, 2k- Rewriting step of the recurrence as
a++1 = ac 1 a,
(A.15)
2k
allows us write recurrence for (0:
-k
by
cbt
bet1 = + be
(1
be
by
(A.16)
c
b.tc
by
b
+
Now, long as b, c. we have bc+1 < b the gives
S. Unrolling the recurrence and rewriting terms of
b, < by ct
(k- 2)
(k--2) Gt
3 a
< Gg
(A.17)
1
a
(a.
(k-2)
=x)==
(1 - 21) =
remains characterize for which by holds. Recall from (A. that b. bn c(k: 2)t for all / 2 O. Notice
bo c(ckk- 2)t t by
(A.18)
c(k: 2)
which matches the condition on t in (A.8).
15

---

B Proof of Main Result
We follow a very similar line of reasoning to the proofs other sample complexity bounds involving the information and generative exponent in the literature, e.g., [BAGJ21, LOSW24). Given sample
(a) y) from the target single-index model (2.1), recall from Section 3 that the update equation for w is
w (++1) ((() + 74,, (y, (1e, w(()))
P wits
(B.1)
[ + 74h, (y, (ar, wl())) P wit a|
where P = Ia ww. T. Throughout this section, we adopt the notation (²( = (0., ((,, and (wu; æ. y) (y, v. (x, w) P Pu We are interested in the dynamics of the alignment with the ground truth
1200) 700,, (()) ||2(()) + +'g00
((++)
(B.2)
In Section B.1, using standard Gaussian tail bounds and tools from high-dimensional probability, we characterize the concentration of the initial alignment (())) about d= Next, in Section B.2, we describe the "slowdown" in the alignment dynamics due to normalization. In Section B.3, we lower bound the expected update after one step. Section B.4, we expand the expected dynamics over t steps and employ standard martingale bound control the noise, leading to high probability upper bound sample complexity when the initial alignment of order d $ This is complemented by a matching lower bound proven in the same way in Section B.5. The upper and lower bounds immediately imply Theorem 3.3, our main result. Subsequently, we discuss how weak recovery leads to strong recovery (Section B.6) and approximation of the target to arbitrary accuracy (Section B.7). This will elucidate the fact that achieving weak recovery is the sample complexity bottleneck for any generic online algorithm satisfying our formalism in Section 3.
B.1 Initial Alignment
We follow [LOSW24] showing a high-probability lower bound for the alignment between a hidden neuron's 's weight vector and the ground truth direction 0.. We make small modification to remove the dependence on step size from the bound.
). Then, ((K(0) 2 Cod 1od-1/2) = (2(1) for any constant Co > 0. Moreover, for any 8' > 0 there exists Co 2 such that (p(x(0) 2 Cod-1/2)
Lemma B.1. Let (o) ~ Unif(gd-1).
1/2) < 8'.
Proof. We may write
(0) (0., (0)) (c1.g)
(B.3)
where E Rd is the first standard basis vector and (O, Ia).
To proceed, in [LOSW24], we require the following lemma.
Lemma B.2 ((CCMII, Theorem 2)). For any 3 and s R, we have
2e
862
1
dt.
(B.4)
2T
22T
Then,
((x(0)) 2 Cod-1/22
2 P((er,g) 2 20, ^ ||g|| S Cod-/2)
2 P(((e.g) (C,) P(|gl 2 Cod 112)
(B.5)
/ 2e(B 1) 22 é -R(d)
2/ π
where the second term follows from Gaussian concentration of the norm. Taking B = 2, we see that the above is (()).
16

---

We can derive a high probability bound using Lipschitz concentration [Ver18, Theorem 5.1.4] to obtain
P(Ix00) 2 Cod-1/22 s 2 exp((-c)))
(B.6)
for some Arguing by symmetry and taking Co sufficiently large gives the second part of the result.
B.2 Normalization Error
Lemma B.3. Suppose (0) 2 O. The update (B.2) satisfies the lower bound
((+1) x0 (7.0 90)) -
10 10 "0)
(B.7)
Proof. When x9 (0..g()) 0, we have
x(t) + 7(0.. 1120(0) + 11
x((+))
x( + (0..g1)))
(B.8)
v1 ?
(x(() + +,(0. (1)) (1) (9
2 (1) + +0,0,, - x² (lg (0., (
|1g
The second line follows from the facts (un g()) (due to P and w(l)) E Sd-11 The third line Otherwise, observe that when ? ( <1
trivial if (1 2
1 11 10
(B.9)
- 1)
< <
= (
where the last line clearly holds. Now, when k0() + ( < 0, the same lower bound can be shown
(1) + 7(... ()) "0 1 >2. ()) 11g "
(t) ((...
(1) + 7 g (())
(B.10)
s
(1 + 72 |1g (1) (112))2)2
B.3 One-Step Population Dynamics
We extend the definition of the coefficients μ4 from (3.2) to handle label noise. Define
Bhg =
E Ey wn (o.(a(a) + +C, ())))e(()))e)110)
i E [r)
(B.11)
((..
Lemma B.4. Assume that for some t. 2 we have d 160)) S polyloge' Moreover, suppose that Assumption 3.2 holds. Then, there exists C > O such that taking & I Cmaxiiisr (5v1) yields the following lower bound for the one-slep dynamics of the alignment x(() == (0))
(++1) 2 (9) + 1C Σ p=(1 - (166)))))) + (0)
(B.12)
1=1
where u9) is a mean-zero sub- Weibull random variable with (1) tail parameter and C > is constant.
17

---

Proof. Omitting the superscript i, the expected update to the alignment with the ground truth 0.
(given the previous iterate)
[0| [E. 966
-0, Pr. Ea Un (y, (ax, w))
0 Pu Bin.
F b
(a) (b)] He, 0-)) He))) w)) )ar
1=0 1=0
1 Hey 0.)) (0., P.)..)
(O,, (1 w)²)
(B.13)
where the third line uses Stein's Lemma and the fact P 0. Thus, the size of the update will be dictated by the first index i, such that [ w)'-1 is largest. Moreover, the centred random variable (0..g) (0,, g)] is wub-Wlibulll with constant order tail parameter since Gaussian random variables are sub- Weibull and the latter class is closed under polynomial transformation. (See [VGNA20] for more details uei-eeb random variables).
We must also control the normalization error from Lemma B.3:
7 k
l 2 7 (0. g) ||/||
(B.14)
Note that
|/||² P x
1h (3/, (z, 20)1
Es (,, (v. He) wi)| (11x1122 (0, w)?)
(B.15)
and therefore, since ||~||| and (x, w) are independent,
[[1 Enn
()), wi) (d (se, w) d.
(B.16)
By the same token, we use our derivation (B.13) to argue E (0., . 9) | | $ d. The error (B.15)
is wei-Wl random variable with tail parameter proportional to y ²d.
By Lemma B.3, this implies that the one step dynamics take the form
(++1) 2 k (1) + (O( ( + yp (2
(B.17)
for some positive constant C2 and sub- Weibull random variables (with constant order parameter) p(0), gtt) that are independent of previous iterations. Now, choosing y CC' C'maxisis+ (1v1) and recalling ((()) 2 1/2 leads
O272x S C2Crx
max p,d
( vo) < C,C ISiST
max (i(K (1)
(B.18)
IS1ST
which can be made a sufficiently small constant multiple of maxi My (1 with an ap- propriate choice of C. Hence, the expected one-step normalization expected one-step population dynamics (B.13), Furthermore, since the constraint on y also implies yd S 1, we may absorb the noise dddg(t) into the (p((t) noise term.
be absorbed into the
This leaves us with the alignment dynamics
( 2 (1) + +0 Σ (c(k(0)---111 (x:(0)2) + +zvl1)
(B.19)
for some constant C > 0.
18

---

B.4 Sample Complexity Upper Bound
Proposition B.5 (Generic Sample Complexity Upper Bound). Suppose (o.. w w))) 2 Cgd 1/2 for some Co > 0. Then, there exists C 2 1/ polylog d such that for any å (0,1). setting y Cd Ca (1v-( gives (0.; w(()) 1/ polylog d within
T(n)
min 6(7 (vi(t) -1 v
(B.20)
iterations of (3.1) with probability least 1 - 8.
Proof. Unrolling the recurrence from Lemma B.4,
k 2 k + +0C1
ΣΣ (1- -7 Σ 2(0)
(B.21)
==
a=0
Since 1 are independent mean-zero sub- Weibull random variables with (1) tail parameter, have, for some constant C3 > 0,
E
Σ
22
Σ 1
C.T.
(B.22)
Moreover,
8
12
max 0S1ST-1
Σ 22
2 4C30 'T)
max OS1ST
Σ ==0
20
by Markov's 's inequality
4C3T
==0
5
T-1
S
E
20
by Doob's maximal inequality.
C3T
$=0
(B (B.23)
Assume without loss of generality that 2 2d 1/21 Our bound on the dynamics after t updates becomes, with probability at least - 5,
(0)) > 1/2 + 1
27
1=1
= 1/2 1/2
+ 71
(1- (x(6))2) 2/22
min P4g
-1/2 ((=3-
1/2
1515
a=0
1450
(B.24)
for some C4 = Q1) by definition of T. Now, recalling that S C6 maxigiss add ($V1), we have
7 1/2 1/2 min P4
-(72v0)
< C1/2
min
Hi =
max Me IsisT
1/2 (+v4)
18i5r
Isisr 4,20
(B.25)
4.20
Cad2
which can be made less than d-1/2 by choosing C sufficiently small. Hence, our final (high probability) upper bound for the multi-step dynamics is
(1) 2 2022 + C1 Σ
(B.26)
Now, we unroll each of the terms in the expected dynamics and determine how quickly each one reaches 1/ polylog d. Consider terms where μ4 0. Since (())) < 1/ polylog d by assumption,
19

---

we may absorb the factor (1 - (x) into the constant C1 (abusing notation). On the other hand, the contributions of terms with p4 S 0 will be negligible by Assumption 3.2.
For the i = term, the noiseless dynamics give
d_ +7 2c
(B.27)
12, CT'11 15, -2c - d d 0(7 0007-1116 (17t).
When = 2, we have, by Grönwall's Inequality (Lemma A.3)
d/ + Σ x(0) 2 d 1-1/2 (1 (1+ "Ciui'' 2 2c
llog (1 + +7mm) 2 log 2c + logd
(B.28)
log 2c logd 00 -1;1 ) log(1 | + 7Cmum)
where the final equality follows from the fact x Lastly, for i 2 3, we have, from the
_² 2 S log(1 + x) S x for x E (0, 1).
inequality (Lemma A.4),
d 1/2
d/2 + 711m Σ (n
- - "22 1) 2 2c
8=0
(B.29)
マ 2 (2c) - (20) i-2 Cidd -/2
- t 2 2 c # d ((2c) i-2 d + ) = O(7 "1 dd
Thus, the maximum weak recovery time is indeed
T = min Õ(r 14 dd dd=2v0).
(B.30)
B.5 Sample Complexity Lower Bound
The proof of the matching sample complexity lower bound proceeds much in the same way as that of the upper bound.
Proposition B.6 (Generic Sample Complexity Lower Bound). Fix e 2 1/ polylo d. Suppose (0., (0)) S d-1/2, Then, there exists a constant Ö Σ 1/ polylog d such that for all d E (0, setting 7 & Co maxisisr ( (111) gives (0., w0() < c for all iterations t T of (3.1), where
T(n)
min 0(7 (H((T)) (((()()(()) -1 V10))
(B.31)
1s:5 7,50
with probability at least 1 5.
Proof of Proposition B.6. The projection error is trivial handle, obtain
k( + (0., (()) [[((() + 70] < (1) + (0.. (2),
(1+1)
(B.32)
since (wo() ()) 0 and ||mi|| 1. Moreover, from Section B.3, the expected one-step update to the alignment is given by
E g
klpu (0., w) 601 (0., w)
(B.33)
20

---

Therefore, with the initialization (0()) _ Cod 1/2 for a positive constant Co, the full dynamics are
(++1) S (1))
( (1:(1)2)) + tyll
S 5x
()) (1- (1((1)3) +7 Σ v(5)
Am
am0
a=0
(B.34)
I Cod 1odd-1/2 1/2 +
(l)s(1o())) - -(x11))3) x 1
5 200d + ΣΣ
(1) (1()))3)),
where the third line follows from the martingale bound in the previous subsection, and the last line follows from the constraint I C5 maXisisr pdddd( (iv)) with C taken sufficiently small. Then, finding the minimum weak recovery time proceeds exactly as the previous section, using Grönwall's inequality for = 2 and the Bihari-L inequality for i 2 3, once again giving
T = min e 14 d Vo). ss
(B.35)
4,50
Together, the sample complexity upper and lower bounds imply Theorem 3.3.
B.6 Strong Recovery
Now, starting with wo that has achieved weak recovery, we characterize the maximum number T' of subsequent updates of the form (3.1) required to achieve strong recovery with high probability.
Proposition B.7 (Strong Recovery Given Weak Recovery). Let E > Suppose that (0.. ux 2 2c for some 2 1/ polylog d. Then, there exists a constant C O such that for all 5 E (0, 1), setting Y S Côd maxigigr 4,c²-1 implies that the update rule (3.1) achieves (0., w) 2 E within
T'
min 6 15i5 M450
(B.36)
iterations with probability at least 1 1-6
Remark B.8. I 1==000 0(1), then T" $ T. That is, achieving weak recovery is the bottleneck during training.
Remark B.9. the algorithms we consider Section we have maxigig- μ4 (1). Therefore, given that weak recovery has already been achieved. then strong recovery for E = 6(1) proceeds after at most ((d) additional iterations with high probability when x d-!
Proof. Similarly to Section B.3, have lower bound on the one-step dynamics:
(1+1) 2 (0) +
Σ C1l (xx(0))))))))))))))))))))))))- + (1)
-222d.
(B.37)
Since (0, 10))) 5 - and Assumption 3.2 holds, we can re-write this as
((+1) (t) 7he Σ (1(( 70()) 22
(B.38)
for some constant C₁ > 0. Setting 7 S te leads to
2202 < C2Cosy max H.c--1 1 < C2CrôE max 14:n (1)(-)) 1si5r
(B.39)
1SiST
21

---

Thus, taking C' sufficiently small ensures that this is fraction of the dominant term in the population update. Unrolling this over steps, we obtain, with probability at least 1 - 6,
t-1
x 2 2c 7ce
p4 (x)) )
(()
==
8=0
2 2c 7018
Mr (x(( -203/20000 1/2/2
(B.40)
==0
2c + 7hh
ΣΣ i=1
p=(x(00))-11 - 1/2--1/2//-//
min 14 1/2 p:20
using the same martingale bound as in Section B.4. Now recalling S Cod maxigisr 11tt11, we have
1/28-1122 1/2 min 14 1/20000 0//200-1/22-1
112
S 5C1/2
(B.41)
1sis A220
which is of lower order than Hence, our final (high probability) upper bound for the multi-step dynamics is
k 2 c 1CE ΣΣ (i(
(B.42)
We analyze how quickly this exceeds 1 E. For the = 1 term, we obtain
(9) 2 c - (1- -1---c)
(B.43)
0(7-1e-'mi
For the i term, we have, by Grönwall's inequality
(0) 2 c 71E Σ
(+) 2 c(1 + + 2
0=
(B.44)
log(1 - 8) loge - 1 1ー-1) log(1 + +CEE12)
For the i terms, we have, by the Bihari-LaSall inequality,
(+) 2 2c+
(M(O))=1 (1 C 2)
21
(B.45)
- 2(1 (1-) e Mi (1-2) 1-1
= -01--e
Hence, the (high probability) maximum strong recovery time given weak recovery is indeed
T' min -(y-te-1,,,)) P250
(B.46)
B.7 Ridge Regression on the Second Layer
For completeness, state the following result from [LOSW24] that outlines the sample complexity of proceeding from strong recovery to approximation of the target to arbitrary accuracy. In particular, if the error tolerance is of constant order, then the sample complexity obtaining of strong recovery (starting from weak recovery) is strictly larger.
Proposition B.10 (Second Layer Training [LOSW24, Lemma 20]). Let > 0 and N = Ô(=-'). Suppose that ((N) neurons in (2.2) satisfy (0., w,) > 1 Let b, Unif([-Cs, Cb)) such that
22

---

C₁ Ó(1). Then, there exists a choice of penalty parameter X = @(1) such that the solution à = (ā1,.... âx) of ridge regression with ((N + t samples satisfies
N
1
((0.L)))))
Σ
((r, + b1) a. 0,( S6..
(B.47)
N ==1
with high probability.
The key assumption in the above is that a constant proportion (up to polylogarithmic factors) of the neurons achieve strong recovery. Recall that the initial alignment sufficiently large with constant order probability (Section B.1), and that each of weak (Section B 3)4) and strong (Section B.6) recovery occur with high probability given such an initialization.
C
SGD Variants
Recall from our proof of Theorem 3.3 in the previous section that the coefficients
A4 =
E
Bi wh (o)(((()) (a) + +,, (a)ee_(())) i i [r]
(C.1)
(a.b) (O..1))
are the key quantities governing the sample complexity of an online algorithm that fits in our framework. We detail the computation of these coefficients for each of the three SGD variants we consider in this work: online SGD (Section 4.1), alternating SGD (Section 4.3), and batch reuse SGD (Section 4.2). This along with Theorem 3.3 immediately imply the corollaries in Section on the sample complexity of these algorithms. Additionally, in Section C.4, we investigate how alternating SGD can generalized to an online algorithm for a D-layer neural network and calculate the uus
C.1 Online SGD
As discussed in Section 4.1, given fresh data point (æ, y) the spherical online SGD update has the form
(+++)
w (++) (t) + ryyo w)) P u x, w (++1)
(C.2)
|w(++
Therefore, under our general framework introduced in Section 3, the update oracle is
,, 2) = (2).
(C.3)
Hence, for E [r], N4 = EcEaal(o, + ()H = u=(o.)us-1(''--
iu,(o)u((oa).
(C.4)
C.2 Batch Reuse SGD
The update for Batch Reuse SGD (Algorithm 1) takes the form
(t)) + ryo' ((x, P pec
(1) - (t) + myo' ((x, ( Pw x, (t+1)) [[=(() + ryo' ()z w)) Pa xl x||
(C.5)
Combining the two steps (and disregarding normalization for the time being), we have
w (++1) (t) + ryo' ((æ, w (²)) + nyo' w (x)) pu)e)))) P
Pul
(C.6)
The presence of > [224 in the update prevents us from immediately casting this into formalism. We handle this follows. Using a Taylor expansion, have
(k) ((xc, will)) )/ k- ,, k l w (0)))) ((k-)) Piice
2(k-1)
(t+1) (t)) + YV
(C.7)
(k - 1)!
1=1
23

---

Note that ||llip
xa-1 and therefore Ei|l P.,(t))
(d'-1). This, along with the assumption
wite
yd I 1, allows us to replace || ||a 1) in each term the Taylor expansion with d' and add a sub- Weibull remainder term g( with O(1) tail parameter:
(++1) -w(t) YY (lh ((xr, ) (())))))(((((()_)___)))))""))))a (d'((a, (1))))) k-1 P Pw gg(h) P
(C.8)
The g(t) term can then be absorbed into the noise that appears in the multi-step analysis in Sections
B.4, B.5, and B.6. Hence, we can take
(v, Σ [0)]
(C.9)
k=1
And so, f E [r].
Σ (nd) h- EcE ((=(()) + = (H
(e((e)He;11(b)
H4
Σ ( Ui 10 (B) Σ (a=(
(C.10)
k=1
(0
C.3 Alternating SGD
The alternating SGD (Algorithm 2) update for single neuron is
(()) + (t) o' ((x, w()))
((++1) nyo (*))),
(1+1)
(C.11)
[l((() + (t)(+++))) ( w(()))
Note that we only use the second layer update in order to update the first layer parameters w. We do not replace the second layer parameter with à at the subsequent iteration, but instead keep For simplicity, assume a = 1. Then,
(y; =) = (z) + ( (=)')())((=).
(C.
Noticing that the first term in the update is the same as in the previous subsection, we have, for i [r].
( (00 (c) + He,(((]
(C.13)
C.4 "Deep" Alternating SGD
We define D-layer neural network student by the recurrence
f(x) = (x)), fo(æ) Wa, f(()) = Aso(fi- i [D-1) - 1],
(C.14)
where Wo E Rxd as before and A; N X.N. such that N; N and Np 1. We are still interested in recovery of the ground truth direction 0, by the finst-layer weights W. To make the theoretical analysis tractable, we consider the simplified sparse network where N; N₂ ND-1 N, A₁ is N₂ x N1 matrix of o and A = Ag off- off-diagonal entries frozen zero during training (i.c., they do not receive gradients). This prevents
Ap-1 = IN with
'Note that chose the same initialization for two-layer network in the previous subsection.
24

---

interactions between weights that would render the analysis intractable. Hence, the output of the network is of the form
N (
((x)
Σ aj
o... ((cr
(C.15)
Hence, to analyze weak recovery, suffices to focus on single summand (where we drop the subscript for convenience);
(D- o.... o (xr,w)))))
(C.16)
which we express as the recurrence
F(z) = FD-1(2), == Fo(z) w),, F((2) = (() 1].
(C.17)
We propose the following update rule inspired by alternating SGD algorithm: 2 (x., w)
D-1
τ0 t (0 + my
II
"0 (F((F--(((()) a (Fi-1(=(1)), ie 1
(C.18)
j=it1
a T (FF-1 Pu Puwz w(++1) w
(1++) (t))) my
II
|
i=1
Expanding the update for w (before normalization) gives
w (1+1)) =w +7
D-1
II 1=1
d000
+ vy
II 1=++1
D-1
d) o o(fl- - o' (FFi
P
(C.19)
where we have omitted the superscript (t) on the right-hand side for readability. This fits into our framework (3.1) since the (0)) remain constant. In fact, for simplicity, we may fix all = 1 for all
i (D - 1]. Our update oracle then
D Σ
(,,,)))=
n'y
Σ
II J45
SEP.((D-1)
(C.20)
D-1
II RES
II 1=++1
d((000-1)()))
-h (3)o (00(0))))))) (1))
where Pi((D 1)) denotes the set of all subsets of [D 1] of cardinality i. Now, assuming that the Hermite coefficients of the relevant compositions and products of and o' are positive, this gives
Pi Σ p u.(!)
(C.21)
Under an optimal choice of y, Theorem 3.3 implies a sample complexity of
T= max 2(i-)) -1)v1)
(C.22)
ISiD
for deep alternating SGD to attain weak recovery.
Now, the positivity of the relevant Hermite coefficients is nontrivial assumption. We consider the special case where (2)) 2?. Then, the update will take the form
D-1
D-1
] (C.23)
( = C
Σ
n'
Σ
[[ JØS
1yv1
II RES
II 1=
0
SEP.([D-1)
25

---

0.8
0.8
105
109
Sample size n
Sample size n
0.6
0.6
10*
0.4
10a
0.4
0.2
0.2
10a
0.0
10a
0.0
10-3
10-2
10-1
10"
10-3
10
10-1
10"
Learning Rate
Learning Rate
(a)
(b)
0.8
10a
Sample size
0.6
10
0.4
10a
10-3
10-2
10
100
Learning Rate n
(c) d 75
Figure 2: Alignments (wo 0.) greater than 0.5 for alternating SGD with different choices of nj and The hyperparameter 7 is chosen according to Corollary 4.3. Results are averaged over 10 runs.
for some positive constant C. Every term in the sum above contains an odd power of z (this is most easily seen by separately considering the cases and 1 & S). Hence, the Hermite coefficient Ez-N((,1) (v. =)He;-1(2)) [2]] is zero for odd and positive for i even. In particular, μe is zero for i odd and has the form (C.21) for even.
It is immediate that weak recovery is achieved with ((d) complexity if é(1) if uz())) > 0 for some j [D] and u2(o²) 2 0 for all / k. This is strict improvement over alternating SGD two-layer neural network when p and p2 are larger than 2 but Pj for some j >> and over batch reuse SGD under the same conditions and quadratic
The above has the limitation that it will not recover in (dd) time if uz(ot) - 0 for all k: E [D] but U1 (o²) > 0 for at least one such k. For p3 = 1, this can resolved by taking ((2) = 23 and = in which case ([)) (2))))) >> 0 and hence μl 0. However, to know the target a priori, and a more generally applicable choice of a is preferable (perhaps randomized approach as in [IOSS24]). We leave thorough examination of potential choices of activation function to future work.
cannot assume
D Experiment Details
In this section, we provide the details the experiment that generated Figure in the main text and discuss additional experiments on batch reuse SGD and online SGD in the same setting. Code for experiments is available online.? Throughout, we consider noiseless single-index teacher (2.1) with o. = Heg, 0, = E1. and a two-layer neural network student (2.2) with N = hidden neuron and no bias, i.e., fxx ao (xx w)). The network is initialized with 1, the first entry of w equal
26

---

0.8
0.8
105
109
Sample size n
Sample size n
0.6
0.6
10
0.4
10*
0.4
0.2
0.2
10a
0.0
10a
0.0
10-4
10-3
10-2
10
10-4
10
10-2
10-1
Learning Rate
Learning Rate
(a)
(b)
0.8
10a
Sample size
0.6
10*
0.4
10a 10
10-3
10
10
Learning Rate n
(c) d 75
Figure 3: Alignments (w,, 0.) greater than 0.5 for batch reuse SGD with different choices of r and The hyperparameter r is chosen according to Corollary 4.2. Results are averaged over 10 runs.
to 1/Vd, and the remaining entries of u are drawn from the uniform distribution over the sphere S 1/d). This ensures that for each simulation start with the same initial alignment so that there is a fair comparison across learning rates.
For all algorithms, we experiment with d E {25, 50, 75} and take logarithmically spaced mesh of 50 learning rate values. We consider the range v) E 110-3, 1] for alternating SGD, r) E [10-4, 10-1] for batch reuse SGD, and y E [10-4, 1] for online SGD. We choose y = max 3/2 ndd-1 as per Corollary 4.3 (disregarding constants). y max d 3/2 n7) for batch reuse SGD as per Corollary 4.2, and 17 = 0 for online SGD. We empirically verify the theoretically predicted phase transition in for alternating and batch reuse SGD and the predicted consistent decrease of the sample complexity with for online SGD.
Each of the algorithms is implemented exactly specified in Section including the projection and normalization steps. We train in a single-pass over the data (i.c., one epoch) with fixed batch size B 128. In other words, we perform [n/ B] online updates. Collecting the alignments (w, 0.) for each (Ir, n)) combination in our mesh gives the colorbars in Figures 1,3,4. To more clearly visualize recovery 0, and the phase transitions for alternating and batch reuse SGD, we threshold alignments at 0.5.
For alternating SGD (Figure 2), observe that the sample complexity remains flat for small r) before decaying as power law after reaching a critical value, as predicted by Corollary 4.3. Also in line with predictions is the observation that this critical value decreases with d. (Note that for this example, Corollary 4.3 predicts the phase transition occurs 17 d/2.2) The results for batch reuse SGD (Figure 3) are similar, with the only difference being that the phase transition occurs at a smaller critical value of 17 than it does for alternating SGD. This is is in line with the prediction of Corollary 4.2, which predicts the phase transition at
3/2 Lastly, for online SGD, we observe that the
3/2
27

---

0.8
0.8
10
105
Sample size n
Sample size
0.6
0.6
10*
0.4
10a
0.4
0.2
10a
0.0
10a
0.0
10-4
10
10-2
10
10"
10-4
10-3
10
10-1
10"
Learning Rate
Learning Rate
(a)
(b)
0.8
10a
Sample size
0.6
10
0.4
10a
10
10-3
10-2
10-1
100
Learning Rate y
(c) d 75
Figure 4: Alignments (wr 0.) greater than 0.5 for online SGD with different choices of y and Note that y = 0 in this case. Results are averaged over 10 runs.
sample complexity decays as power law in y, as expected from Theorem 3.3. We also that when " is chosen too large, the training becomes unstable and we longer consistently recover.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main contributions of the paper that we outline in the paper's abstract and introduction are reflected in the remainder of the paper's content, as we provide detailed overview of the sample complexity of online gradient-basee algorithms for learning single-index models, with particular focus on the phase transition induced by the learning rate.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section we list learning problems and algorithm settings that our frame- work does not cover and that are left for future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
29

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our setting and main overarching assumptions are clearly outlined in Sections 2 and 3. We state additional assumptions the individual theorem statements and provide complete proofs in the supplementary material.
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 proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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:
The experiments are meant illustrate the theory rather than serve as results in their own right. With that said, we detail our experiments in Section 4.3 and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
30

---

some way (e.g., to registered users), but it should be possible for other researchers have some path 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 faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: The experiments meant illustrate the theory rather than serve results in their own right.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
wwssssiiiicico////o for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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:
ciitps..cc/pubic/guuu guw/es/ /CodeSubmiee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. 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 as 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All necessary details covered in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level 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, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The experiments are meant to illustrate the theory rather than serve as results in their own right.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments are meant illustrate the theory rather than serve results in their own right.
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 of compute required for each of the individual experimental rums as well as 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 fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
http///nerrrpp.eeeee wwtrriis.ccppuuulie cctppblic//eieeccccccccccccc Cetriic///iiiieeeeeeeeeeeeeeeeee htte//ttthiiieeeeeeeeeeeeeee csGuideliees"
Answer: [Yes]
Justification: We have reviewed the Code of Ethics and confirm that none of its clauses violated by this paper.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances 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: This paper is theoretical in nature, and we do not foresce any direct socictal impact of this work.
Guidelines:
32

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is theoretical in nature and poses such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/c datasttss 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.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We have no new assets to release for this work, as it is theoretical in nature.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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 crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are not the object of study in this paper.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //terr//s...../ / for what should or should be described.
35


Reviews:
[{"review_id": "7YdE67fWvh", "reviewer": "Reviewer_NSB9", "summary": "This paper analyzes how the learning rate affects the sample complexity for neural networks learning gaussian single-index models. It establishes a general framework to show that for many gradient-based algorithms, the learning rate induces a phase transition in performance. Specifically, a small learning rate confines the algorithm to a complexity determined by the \"information exponent,\" while a sufficiently large learning rate allows it to achieve a better complexity determined by the \"generative exponent\" for polynomial link function. \n\nThe authors further apply the framework to online SGD, SGD with square label transformation, and batch-reusing, and demonstrate how the phase transition occurs in each case.", "questions": "1. On Determining the Learning Rate: Beyond the specific analysis in this paper, is there a more general principle or rule of thumb for setting the optimal learning rate, or is it fundamentally tied to the specific properties of the model?\n\n2. On Extending to Broader Function Classes: The framework in (3.1) appears general enough to accommodate non-polynomial link functions. Could the current results be extended to such cases? What are the primary technical barriers to this extension? Would criteria similar to $\\mu_i(\\eta)$ still be applicable for analyzing the sample complexity in a non-polynomial setting?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\nThis paper presents a well-structured and technically rigorous analysis that builds upon the extensive recent literature on learning single-index models. Its key contribution is investigating how the learning rate dictates the sample complexity, a crucial aspect that previous works often simplified by assuming either a sufficiently large or small learning rate.\n\n1. The key contribution of this work is its investigation into the influence of the learning rate on sample complexity. The authors demonstrate how adjusting the learning rate, including inner learning rates for batch-reusing steps, allows the sample complexity to interpolate between two critical bounds:\n\n     - The information exponent-related bound of $d^{p-1}$\n \n     - The SQ bound of $\\tilde O(d)$ for polynomial functions. \n\n2. If my understanding is correct, this research can be viewed as an extension of the work by Lee et al. (2024), providing a more nuanced understanding of how learning rate selection directly impacts the sample efficiency of learning in single-index models.\n\n**Weaknesses**:\n\nA potential limitation of the proposed framework is the cumbersome process required to determine the optimal learning rate. This selection is not only sensitive, with Remark 3.4 indicating that changes in $\\mu_i(\\eta)$ can alter the optimal rate by a polynomial factor in the dimension, but it also presupposes detailed knowledge of the interplay between the link and activation functions. This dependence on specific model information may impede the practical implementation of these algorithms.\n\nAnother possible issue is that the proposed algorithms in Section 4.2 are still a little bit artificial, but the batch-reusing part seems already more natural then the version in Lee et al. (2024). Meanwhile, I'm also aware this is a common issue in the existing literature. \n\n[1] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional 442 polynomials with SGD near the information-theoretic limit. In The Thirty-eighth Annual Confer443 ence on Neural Information Processing Systems, 2024.", "was_revised": true, "final_justification": "A theoretically solid paper that might be of interest to the community, and the authors' rebuttal resolved my concerns", "rebuttal": "We thank the reviewer for their feedback. Please find our response below. \n\n**The Optimal Learning Rate:** Indeed, the optimal $\\eta$ depends on the form of the $\\mu_i(\\eta)$ in general. However, for the cases alternating SGD and batch reuse SGD, these coefficients are non-decreasing in $\\eta$ (as long as Assumption 3.2 holds so that the relative Hermite coefficients are positive). In fact, for *any* algorithm where $\\eta$ has the interpretation of a learning rate and thus appears in $\\psi_{\\eta}$ only as a scaling factor, this property will hold. It is therefore immediate that the practitioner should take $\\eta$ as large as possible while still ensuring convergence. From our condition $\\psi_{\\eta} = O(1)$ — which ensures control over the errors arising from normalization, SGD noise, and label noise — this means taking $\\eta \\asymp d^{-1}$ for batch reuse SGD (as in [1]) and $\\eta \\asymp 1$ for alternating SGD.\n\n**The Link Functions under Consideration:** We can in fact handle any link function that has at most polynomial growth (as in [2]). We will modify Assumption 3.1 in the final version to indicate this. This is a much larger function class that includes ReLU and its variants, splines, as well as any bounded link function such as the logistic and probit. Assuming at most polynomial growth for $\\sigma_*$ ensures that $\\langle \\boldsymbol{\\theta}_*, \\boldsymbol{g} \\rangle$ is sub-Weibull. Indeed, the class of sub-Weibull random variables includes sub-Gaussian and sub-exponential random variables and is closed under transformations with at most polynomial growth (up to changing the tail parameter). This condition on the noise ensures that we can make a concentration of measure argument to control the errors arising from label noise and the stochastic gradient.\n\n**The Artificial Nature of Alternating SGD:** We thank the reviewer for raising this concern, which allows us to clarify the point of studying Algorithm 1. Although this algorithm is somewhat contrived when compared with practice, we believe that its study is useful from a theoretical perspective. We see it as proof of concept to demonstrate what mechanisms might be at play in neural network training so that they achieve near-optimal sample complexity. Specifically, it reveals another mechanism for obtaining benefits of data repetition — one that comes from updates on the second layer rather than first. In practice when both layers are trained simultaneously for a number of steps on the same batch, this effect will be combined with the effect of updates on the first layer alone, which is captured by Algorithm 2.\n\nWe also highlight the connection between Algorithm 1 and the literature on studying the two-timescales optimization dynamics of neural nets. By studying this algorithm, we are able to link the discrepancy in the learning rates to sample complexity, which is a novel perspective in this literature. Once again, the ideal algorithm would take multiple steps on the same batch and observe the combined effect of Algorithms 1 and 2, but studying this idealized setting is out of reach for our current techniques.\n\nWe will better highlight these points in the final version to motivate the study of Algorithm 1.\n\nWe are happy to answer any further questions.\n\n[1] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit. NeurIPS 2024.\n\n[2] 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 2024."}, {"review_id": "vPF5QlBZ6s", "reviewer": "Reviewer_PnJT", "summary": "The paper characterizes the relationship between the learning rate and sample complexity for a class of gradient-based algorithms including both correlational and non-correlational updates. A phase transition is observed when the learning rate increases from small to large. Examples include online SGD, alternating SGD, batch reuse SGD are discussed. Some very simple numerical experiments are included.", "questions": "(1) It would be great if you can discuss when Theorem 3.3. will lead to phase transitions. I understand that you have discussed several examples in Section 4, but it would also be interesting to discuss for the general setup as in Theorem 3.3, when you will have phase transitions, when you will not, depending on the properties of $\\mu_{i}(\\eta)$.\n\n(2) Some references need to be cleaned up. For example, in [AVPVF23], sgd should be SGD, in [Cla87], gronwall should be Gronwall, in [CCM11], gaussian should be Gaussian.", "limitations": "It seems the author(s) did not discuss the limitations in the paper.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n(1) The main results are easy to follow, and the meaning of phase transition is clear in this context. \n\n(2) Various examples are included in the class of gradient-based algorithms, and they are properly discussed. \n\n(3) Figure 1 seems to be in line with what the theory suggests.\n\nWeaknesses:\n\n(1) The class of models considered in this paper still seem to be a bit special. It would be interesting to see if phase transitions can occur in more general settings.\n\n(2) Figure 1 is based on a toy example. More numerical experiments will be helpful, especially in terms of whether the phase transitions claimed in the paper can be observed in various numerical settings in practice, which will also make the theory more convincing. For example Figure 1 illustrates the toy example for Corollary 4.2., but there is no numerical illustration for Corollary 4.3. for batch reuse SGD, which according to Figure 3, should lead to multiple phase transitions. It would be great to see numerically that it is indeed the case. For Corollary 4.1. for online SGD, the theory does not suggest there will be phase transitions, and it will also be useful to numerically check that indeed no phase transitions will be observed numerically.", "was_revised": true, "final_justification": "I have now raised the score. The author(s) have addressed the issues I raised.", "rebuttal": "We thank the reviewer for their feedback. Please find our response below.\n\n**The Class of Models under Consideration:** We would like to point out that despite their simplicity compared to practice, the class of Gaussian single-index models provides a tractable formalism for the theoretical study of feature learning [1,2,3]. The assumptions inherent to this setting are crucial to establish rigorous sample complexity bounds for SGD. In the paper, we assume that the link function $\\sigma_*$ is polynomial, which is rather restrictive. We can in fact **extend this to any link function with at most polynomial growth** and will modify Assumption 3.1 in the final version to reflect this. This broadens our theory to capture much more general link functions in statistics and machine learning, such as ReLU (and its variants), the logistic, and the probit.\n\n**Additional Experiments:** As per the reviewer's suggestion, we have run additional experiments for online and batch reuse SGD. To start, we focused on our existing example of $\\sigma_* = \\operatorname{He}\\_3$ since $\\operatorname{IE}(\\sigma_*) = 3$ and $\\operatorname{IE}(\\sigma_*^2) = 2$. For online SGD, there is *no phase transition* with respect to the learning rate $\\gamma$ and the test error decreases at approximately a $\\Theta(\\gamma^{-1})$ rate, *as expected from theory*. On the other hand, we performed a larger-scale version of the experiment in Figure 4 for batch reuse SGD and confirmed that this algorithm *does* exhibit a phase transition due to the parameter $\\eta$. Since we are not allowed to share supplementary figures during the rebuttal, we can only include these experiments in the final version.\n\nWe would also like to highlight the fact that *experiments in practical settings have already observed that learning rate can affect generalization (and thus sample complexity)*, see e.g. [6]. Our study can be one way to approach a theoretical justification of this observation.\n\n**A General Discussion of the Phase Transition in Section 3:** We thank the reviewer for this suggestion, which will indeed help the readers better parse the main result. We provide a brief discussion below, and will it to the final version of the paper in Section 3. \n\nFor simplicity, assume that all $\\mu_i$ are positive. Consider the key equation $T(\\eta) = \\min_{1 \\leq i \\leq r} \\tilde{\\Theta}(\\gamma^{-1} \\mu_i(\\eta)^{-1} d^{\\frac{i-2}{2} \\vee 0})$. The sample complexity is determined by the smallest term, whose index we can identify by $\\alpha(\\eta) = \\operatorname{argmin}_{1 \\leq i \\leq r} \\tilde{\\Theta}(\\gamma^{-1} \\mu_i(\\eta)^{-1} d^{\\frac{i-2}{2} \\vee 0})$. We say that the sample complexity exhibits *phase transitions* when $\\alpha$ changes with $\\eta$. We can identify potential phase transitions by comparing $\\mu_i^{-1} d^{\\frac{i-2}{2}} \\leq \\mu_j^{-1} d^{\\frac{j-2}{2}}$. In particular, at fixed $d$, if $\\mu_i$ is growing faster with $\\eta$ than $\\mu_j$, then the $i$th term will be more important in determining sample complexity for larger $\\eta$. This is the phenomenon we illustrate with alternating SGD and batch reuse SGD in Section 4.\n\nPlease let us know if we can clarify this further.\n\n**Referencing Issues:** We thank the reviewer for pointing these issues out. We have addressed these for the final version.\n\n**Limitations of the Paper**: We agree with the reviewer that our discussion of limitations should be more explicit, and we will rectify this in the final version. Currently we are limited to the setting of Gaussian single-index models under the specific assumptions in Section 3 in order for the analysis to be theoretically tractable. In the conclusion, we list possible extensions that would broaden the scope of our theory (e.g., multi-index models [4], more general input distributions [5]).\n\nWe hope our responses have addressed the reviewer's concerns, and are happy to answer any further questions.\n\n[1] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. JMLR 2021.\n\n[2] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. NeurIPS 2022.\n\n[3] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit. NeurIPS 2024.\n\n[4] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. SGD learning on neural networks: Leap complexity and saddle-to-saddle dynamics. COLT 2023.\n\n[5] Nirmit Joshi, Hugo Koubbi, Theodor Misiakiewicz, and Nathan Srebro. Learning single-index models via harmonic decomposition. arXiv 2025.\n\n[6] Yuanzhi Li, Colin Wei, Tengyu Ma. Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks. NeurIPS 2019."}, {"review_id": "5QX7ExR09J", "reviewer": "Reviewer_wVyS", "summary": "This papers investigate the sample complexity of training two-layer neural networks to weakly learn intrinsic features with data generated from Gaussian single-index models. \n\nSpecifically, the authors focus on a set of online gradient-based algorithms that can be expressed with a general gradient oracle $\\psi_\\eta(y,\\langle x, w\\rangle)$ , where $\\eta$ is a hyperparameter that determines the non-linearity of the gradient query. \n\nThen, they stated the tight sample complexity for this general algorithm with a measure of non-correlational in $\\eta$. Using this main result, they provided the tight sample complexity for vanilla online SGD, alternating SGD and batch-reused SGD. For alternating SGD and batch-reused SGD, they revealed a novel phase-transition in the intrinsic learning rate $\\eta.$", "questions": "1. In the perspective of exploration, the pseudo-step is used to find a better gradient near the current point and smoothing can be viewed as a similar technique (however smoothing is used in some other scenarios with higher generative exponent). In that case, the polarization parameter $\\lambda$ (see e.g. [1,2]) may plays a role. Would it be possible to analyze the analogous phenomenon for $\\lambda$? \n2. Would it be possible to extend this analysis to the general link functions, instead of the polynomial links?  \n3. The main result essentially depends on $\\gamma$ (the learning rate for the spherical gradient) and there is certain notion of the optimal choice of $\\gamma.$ But in the result of [2], they only require the learning rate to be sufficiently large. Is the choice of $\\gamma$ for the technical reason or it matters in whether the sample complexity is optimal? \n4. This type of model typically relates to the SQ-problem, where I tend to think that closing the computational statistical gap is more important (see the second con). Does this learning-rate phase transition relate to some more practical phenomenon or has practical implications? (I think it’s very different to EoS which is more realistic). Or potentially your characteriaztion can provides some other insights (see the first question).", "limitations": "See cons.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Pros:\n\n1. The writing is generally clear and easy to follow. Proof sketch in the maintext is essential to capture the key components. \n2. The framework of the general gradient oracle is theoretically convenient and the characterization of the non-correlational property with $\\mu(\\eta)$ is quite critical in capturing the hardness of the problem (in terms of $\\eta$).\n3. The sample complexity phase transition in learning rate is a novel perspective for the batch-reused SGD in single index models. Previous work all focus on the cases where the psudo-step is taken with sufficiently large but reasonable step size, but the sample complexity for the batch-reused SGD with smaller learning rate remains unclear. \n\nCons\n\n1. The definition of $\\mu(\\eta)$ is a bit obsecure at first glance. It would be better if the author can preview some examples of $\\psi_\\eta$  in Section 3 and see how $\\eta$  appears. Also it would be better if authors can briefly explain how this quantity reigns the sample complexity in the main text & discuss if similar notion appears in other literatures. \n2. The result is novel by completing the whole picture of batch-reusing, but quite incremental in terms of matching the lower bound, as the prior works have fully settled the optimal algorithms and sample complexity of various online SGD in single-index models.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Please find our response below.\n\n**Clarifying the $\\mu(\\eta)$ Notation:** The formalism of the generic update rule $\\psi(y,\\langle \\boldsymbol{x}, \\boldsymbol{w} \\rangle)$ was introduced in [1]; our only modification is to track the explicit dependence on a hyperparameter $\\eta$, which appears in SGD variants that employ label transformation, for example. In fact, the expression denoted $\\mathbb{E}[\\zeta_{s*}(y) \\psi_{s*-1}(y)]$ in Assumption 4.1(b) of [1] is exactly $\\mu_{p_*}$ in our notation. While the authors of [1] assume that the latter quantity is of constant order (which in our examples amounts to taking $\\eta$ as large as possible), we consider the sample complexity for a full range of $\\eta$ values. We will add a discussion on this effect in Section 3 where we introduce the formalism and the $\\mu(\\eta)$ notation. We will also preview how this formalism captures batch reuse SGD (as per the reviewer's suggestion) for easier readability.\n\n**Incremental Progress Towards Matching SQ Lower Bounds:** We would like to highlight that our goal is not to find the optimal sample complexity under some oracle assumption, but rather to provide a detailed characterization of the failure modes of existing SGD variants that break out of CSQ. Namely, we show that incorrect choice of hyperparameters governing the size of non-correlational updates can lead to sample complexity as poor as online SGD. Moreover, any algorithm that fits our framework (including our novel alternating SGD) and satisfies $\\mu_{p_*} = \\tilde{\\Theta}(1)$ can be made SQ-optimal with the smoothing-inspired approach in [1].\n\n**1) Smoothing Hyperparameters:** We believe that it is possible to adapt our framework to capture landscape smoothing and treat the associated hyperparameter (called $\\gamma$ in [1] and $\\lambda$ in [2]) as our $\\eta$. This boils down to casting the algorithm's update as $\\psi(y,\\langle \\boldsymbol{x},\\boldsymbol{w} \\rangle)$ and computing the coefficients $\\mu_i$. This is more intricate than the three examples we consider in our work due to the random perturbations of the weight vector $\\boldsymbol{w}$. In particular, for the algorithm in [2], the gradient update takes the form $\\frac{1}{\\sqrt{1+\\lambda^2}} y \\mathbb{E} [\\sigma’(\\frac{\\langle \\boldsymbol{w}, \\boldsymbol{x} \\rangle + \\lambda \\langle \\boldsymbol{\\xi}, \\boldsymbol{x} \\rangle}{1 + \\lambda^2})]\\boldsymbol{x}$, where $\\boldsymbol{\\xi}$ is drawn from the uniform distribution on $\\mathbb{S}^{d-1}$ conditioned on being orthogonal to $\\boldsymbol{w}$. Note that the distribution of $\\langle \\boldsymbol{\\xi}, \\boldsymbol{x} \\rangle$ depends on $||\\boldsymbol{x}||$ in addition to $\\langle \\boldsymbol{x},\\boldsymbol{w} \\rangle$. We believe that the proof techniques from the appendices of [2] to handle this can be of use here.\n\nOn this point, it is also worth mentioning that that Theorem 1 of [2] establishes that that landscape smoothing SGD has sample complexity $\\tilde{O}(d^{p-1} \\lambda^{-2(p-2)})$ for $\\lambda \\in [1,d^{1/4}]$. Hence, there is a smooth (i.e., no phase transitions) interpolation between the online SGD complexity $\\tilde{O}(d^{p-1})$ and the CSQ lower bound as a function of $\\lambda$.\n\nThe situation is more complicated for the SQ-optimal algorithm of [1], where the analysis assumes that the polarization parameter $\\gamma$ is fixed at its optimal value. This choice directly influences the number of samples required per step to ensure concentration of the empirical gradient (Proposition E.4 in [1]). Moreover, the expected alignment between the gradient and $\\theta_*$ depends on $\\gamma^{p_*-1}$ (Proposition E.3 in [1]). We leave it to future work to understand the behaviour for suboptimal $\\gamma$ and attempt to cast the algorithm into our framework.\n\n*Please note: We think the references [1,2] are missing in the review.*\n\n**2) More General Link Functions:** We can in fact handle any link function that has at most polynomial growth (as in [3]). We will modify Assumption 3.1 in the final version to indicate this. This is a much larger function class that includes ReLU and its variants, splines, as well as any bounded link function such as the logistic and probit. Assuming at most polynomial growth for $\\sigma_*$ ensures that $\\langle \\boldsymbol{\\theta}_*, \\boldsymbol{g} \\rangle$ is sub-Weibull. Indeed, the class of sub-Weibull random variables includes sub-Gaussian and sub-exponential random variables and is closed under transformations with at most polynomial growth (up to changing the tail parameter). This condition on the noise ensures that we can make a concentration of measure argument to control the errors arising from label noise and the stochastic gradient.\n\n**3) The Choice of $\\gamma$:** The hyperparameter $\\gamma$ must on the order of its largest possible value as per Theorem 3.3 so that optimal sample complexity can be achieved. This constraint is necessary to control the errors in the update to $\\langle \\boldsymbol{\\theta}_*,\\boldsymbol{w} \\rangle$ that arise due to normalization, stochastic gradient noise, and label noise (see proof sketch in Section 5). It is analogous to the constraint placed on the hyperparameters in batch reuse SGD (see Theorem 2 in [3], Theorem 1 in [4]).\n\n**4) The Implications of the Phase Transition:** We had two main motivations to study the effect of learning rate on generalization:\n\na) Our first motivation was to understand when gradient-based algorithms on squared loss can break out of CSQ. While prior works [3,4] focus on the role of batch reuse, we believe learning rate is another important aspect that determines the oracle class of gradient-based algorithms, as demonstrated by our examples.\n\nb) In practice, it has been observed that larger learning rate leads to better generalization [5]. There is no consensus on why this is the case, and works on edge of stability (EoS) are more concerned with the optimization dynamics than generalization behaviour. In that regard, we believe studies that link sample complexity and learning rate can be valuable. Specifically, our work shows that significant improvements in the generalization behaviour can occur *even when one is not operating in the EoS regime*. Further studies to better characterize practical settings where this is the case are interesting, but outside the scope of our current paper.\n\nWe are happy to answer any further questions.\n\n[1] Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, and Tianhao Wang. Can neural networks achieve optimal computational-statistical tradeoff? an analysis on single-index model. ICLR 2025.\n\n[2] 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. NeurIPS 2023.\n\n[3] 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 2024.\n\n[4] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit. NeurIPS 2024.\n\n[5] Yuanzhi Li, Colin Wei, Tengyu Ma. Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks. NeurIPS 2019."}, {"review_id": "9qHEC9Kb74", "reviewer": "Reviewer_atEW", "summary": "The study builds upon a series of works concerning sample complexity estimates for the high-dimensional limit of single index models. The authors consider the case of a two-layer neural network trained by algorithms belonging to a class of optimization methods based on generalized versions of the gradient of the MSE loss $\\psi_\\eta$, where $\\eta$ is an additional learning rate parameter. The main theorem establishes a formula for the sample complexity, which depends on the learning rates $\\gamma$ and $\\eta$, as well as on the Hermite coefficients of the student's and teacher's link functions.\n\nThe authors argue that the novelty lies in the generality of the algorithmic class to which the theorem applies. They then show that both _vanilla SGD_  and  _batch reuse SGD_ belong to this class, and they establish the relationship between the new estimates and the information and generative exponents. They demonstrate how, by tuning $\\eta$, it is possible to transition from a regime where learning is governed by the information exponent to one where learning is faster and governed by the generative exponent.\n\nIn addition, they introduce a new variant of SGD, termed _Alternating SGD_, and show how it can improve standard SGD when $\\eta$ is sufficiently large. This variant can be further enhanced when applied to deeper networks.", "questions": "- About figure 1, I would strongly suggest to plot results for different values of $d$, to show how the phenomenology portrayed passes to the high-dimensional limit. Should we see a sharp vertical transition between blue and white region for $d\\to \\infty$? It may also help to continue the plot for even larger values of $\\eta$.\n- does your analysis offer practical insigths for tuning learning rate in networks, comments on this and simulations on more realistic and complex task may be interesting to practitioners.\n\n### Questions and comments:\n- In Theorem 3.3 you need to require an upper bound on $\\gamma$. What happens for larger values? From the proof sketch, it seems that it is not possible to ignore the normalization term of the iterate expansion. Is that the tight value for such constant, beyond which the dynamics become too noisy? \n- About Figure 1, I would strongly suggest plotting results for different values of $d$, to show how the portrayed phenomenology extends to the high-dimensional limit. Should we see a sharp vertical transition between the blue and white regions for $d \\to \\infty$? It may also help to extend the plot to even larger values of $\\eta$.\n- Does your analysis offer practical insights for tuning learning rates in networks? Comments on this aspect, together with simulations on more realistic and complex tasks, may be useful to practitioners.\n- Can you clarify exactly what are your contributions in the batch reuse SGD setting? \n- Can you comment on whether a non-polynomial $\\sigma$ introduces just technical difficulties, or could give rise to different phenomenologies? \n- The deep network case discussed in Appendix C.3 seems to be one of the strongest contributions of the paper, showing how depth can enhance learning. In particular, the final discussion in Appendix C.3 seems relevant, concerning which properties of the Hermite coefficients of $\\sigma$ and $\\sigma_*$ would make the deep framework better or worse than multi-pass SGD. You make comments only about the three-layer case; can they be generalized to larger $D$?\n- Can your analysis be coupled with the smoothing techniques from [DNGL23] to reach the optimal sample complexity thresholds?\n\n### Suggestion\nFrom the communication point of view, in my opinion there is a bit too much emphasis on the fact that this work establishes the importance of the learning rate. This point is stressed both in the abstract, introduction, and conclusions. For instance, the conclusions section starts with:\n\n> This work demonstrates that the learning rate is a fundamental factor in determining the sample complexity of gradient-based algorithms for learning single-index models with neural networks.\n\nHowever, I think most readers already know that the learning rate is an impactful factor in determining the sample complexity in any learning problem. It is a core aspect of gradient methods, and most of the referenced works on single index models have detailed discussions about learning rates. I believe that the excessive emphasis on this aspect could risk drawing attention away from other important contributions of the paper. Moreover, it is even technically a bit misleading, since the usual SGD learning rate $\\gamma$ is treated similarly to previous work, and it is the additional parameter $\\eta$ that is the true focus of this work.\n\nIn my opinion, the merits of this work lie in the definition of a general framework that allows studying and finding optimal learning rates for a broad class of gradient-based optimization methods, providing a unified framework in which information and generative exponents appear as limit cases. I would suggest emphasizing more the generality and versatility of these results, and how the additional learning rate $\\eta$ introduced in this novel class of learning algorithms can impact the sample complexity.", "limitations": "The authors address the main limitations of the paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strenghts:\n- well written and clear.\n- theorem 3.3 is a general results provides a unified framework in which generative and information exponents appear as limit cases.\n- the class of algorithm to which theorem 3.3 applies seems to be very broad, and Alternating SGD seems to be a nice example that could be of interest for practitioners\n- the sketch of the proof insection 5 manages to convey clearly the key idea of the argument, showing how all the terms in the Hermite expansion of the Loss can become relevant depending on the scaling of $\\eta$. \n- the technical appendices contain thorough proofs of the main results of the paper, and even rigorous analyses that go beyond the main focus of the paper, such as appendix C.3 that examines the case of a deeper network. Or appendix B.6 and B.7 that provide already known, but necessary context on how to rigorously bridge the gap between weak and strong recovery.\n\n### Weaknesses:\n- cumbersome notation for hermite coefficients, especially formula 3.2, which is one of the central definitions in the paper. Writing the definition in terms of the integral over 2 independent gaussian variables, instead of this complicated notation with two nested $\\to$, would have been shorter. I understand that in the paper you need to Hermite expand different functions, and need a compact notation for that. Nevertheless I suggest to provide the explicit intregrals at least once for the important formulas.\n- since the area of single index model has now many research works that investigate similar questions of sample complexity, it is hard to assess which contributions are original, and which overlap with previous work. I do not see much novelty on the side of the analysis of _batch reuse SGD_, however the overall analysis and _alternating SGD_ are completely new, to the best of my knowledge (even though possible overlaps with the very recent [CLW+25] could be investigated more).\n- just polynomial link functions is a rather restrictive assumption, I believe simulations that test the phenomenology on non-polynomial link functions should be performed.\n- there are no comments and simulations that test the proposed _alternating SGD_ in more realistic settings.", "was_revised": true, "final_justification": "The authors addressed all my questions, especially the key (and for me puzzling) limitation to polynomial activation functions, explaining that they will extend to a much larger class of activation functions. This is why I increase my rating to 5.", "rebuttal": "We thank the reviewer for their feedback. Please find our response below.\n\n**Notation for $\\mu(\\eta)$:** We agree with the reviewer's suggestion to improve readability. In the final version, we will define $\\mu_i(\\eta) := \\mathbb{E}[\\psi_{\\eta}(\\sigma_*(a),b) He_i(a) He_{i-1}(b)]$, where $a,b$ are independent standard normal random variables.\n\n**Clarification on Contributions:** Our core technical contribution is a careful analysis of different SGD variants to learn single-index models, while keeping track of dependencies on the learning rate, achieved through a unified set of tools by looking at a general update rule. Through this analysis, we are able to characterize how the *query class and complexity of SGD-type algorithms change depending on the learning rate*, which is our main conceptual contribution. These contributions are different from those of [3] on the technical side by a precise analysis that keeps track of the learning rate and on the conceptual side as we cover regimes in between CSQ and SQ.\n\nAs the reviewer mentioned, in the specific case of batch reuse SGD, our analysis reduces to that of [1], with the exception of explicit tracking of learning rate. However, to our knowledge, the fact that *alternating SGD* can also modify the query class of SGD is entirely novel. \n\n**Non-Polynomial Link Functions:** We can in fact admit any link function that has at most polynomial growth (as in [2]) without affecting our main result. We will modify Assumption 3.1 in the final version to indicate this. This is a much larger function class that includes ReLU and its variants, splines, as well as any bounded link function such as the logistic and probit. Assuming at most polynomial growth for $\\sigma_*$ ensures that $\\langle \\boldsymbol{\\theta}_*, \\boldsymbol{g} \\rangle$ is sub-Weibull, allowing us to make concentration arguments.\n\n**Realistic Simulations of Alternating SGD:** We would like to highlight that we only study alternating SGD as a simplified proof of concept, as it provides a novel mechanism for modifying the statistical query type of SGD, one that comes from updates on the second layer rather than the first. In practice when both layers are trained simultaneously for a number of steps on the same batch, this effect will be combined with the effect of updates on the first layer alone, which is captured by Algorithm 2. Therefore alternating SGD here should be seen as a theoretical construction (similar to the batch reuse algorithm of prior works) to allow us to understand more practical settings, rather than a new optimization algorithm. We will better emphasize this fact in the paper.\n\n**Varying $d$ in Experiments:** We repeated the experiments in Figures 1 and 4 with $d = 25$ and $d = 75$. Taking $d$ larger is not feasible on our GPU due to the large number of samples (and thus running time) required. The theory predicts that the sample complexity will be \"flat'' until a phase transition at $\\eta \\asymp d^{-1/2}$, after which it smoothly decreases until $\\eta \\asymp 1$. There will not be a sharp vertical transition as described by the reviewer. Our experimental results match this prediction. In particular, the threshold for the phase transition decreases as $d$ increases.\n\nIn our experiments, taking larger values of $\\eta$ than those appearing in Figure 1 leads to instability and poor generalization for both alternating and batch reuse SGD. We have a similar observation for all three algorithms when $\\gamma$ is taken too large.\n\nWe will add these additional experimental results to the final version.\n\n**Insights on Learning Rate Tuning:** We would like to stress that our main goal is not to find an optimal learning rate for practitioners, but to understand how learning rate can affect the oracle access/query model and the subsequent sample complexity of SGD. Nevertheless, we agree with the reviewer on the importance of being able to provide practical recommendations.\n\nThe suggestion from our results is that learning rates $\\gamma$, $\\eta$ should be taken as large as possible (while still ensuring convergence) so as to avoid incurring unnecessary additional training cost. In particular, in the cases of alternating SGD and batch reuse SGD, the coefficients $\\mu_i(\\eta)$ are non-decreasing in $\\eta$ (as long as Assumption 3.2 holds so that the relative Hermite coefficients are positive). In fact, for *any* algorithm where $\\eta$ has the interpretation of a learning rate and thus appears in $\\psi_{\\eta}$ only as a scaling factor, this property will hold. It is therefore immediate that the practitioner should take $\\eta$ as large as possible. From our condition $\\psi_{\\eta} = O(1)$ — which ensures control over the errors arising from normalization, SGD noise, and label noise — this means taking taking $\\eta \\asymp d^{-1}$ for batch reuse SGD (as in [1]) and $\\eta \\asymp 1$ for alternating SGD.\n\n**The Upper Bound on $\\gamma$:** The reviewer's intuition is exactly correct. Taking $\\gamma$ sufficiently small is necessary to ensure that the “informative” terms in the gradient update dominate the errors arising from both the normalization and the noise. The bound we provide on $\\gamma$ is tight in the sense that it is the largest possible value for which these errors remain controlled. Moreover, as alluded to in an earlier answer, we observe in experiments that taking $\\gamma$ larger than the theoretical threshold leads to instability.\n\n**Deep Networks:** We can generalize our example with $\\sigma(z) = z^2$ to any depth. This is because, up to constants, $\\psi_{\\eta}(y,z)$ will always take the form $\\sum_{i=0}^{D-1} \\eta y^{i+1} z^{k_i}$, where all $k_i$ are odd. The odd Hermite coefficients of odd monomials are always positive, while their even Hermite coefficients are zero. Hence, we can recover in $\\tilde{\\Theta}(d)$ time if $\\eta \\asymp 1$ and at least one of $u_2(\\sigma_*^k) > 0$ for $k \\in [D]$. We will add a detailed discussion to illustrate this point in Appendix C.3.\n\n**SQ-Optimality through Smoothing:** Yes, it is possible to achieve the SQ lower bound through a technique inspired by the smoothing approach in [2]. The recent paper [3] shows that this can be done by aggregating the update $\\psi(y,\\langle \\boldsymbol{x},\\tilde{\\boldsymbol{w}}\\rangle)$ for a large number of random perturbations $\\tilde{\\boldsymbol{w}}$ of the current iterate $\\boldsymbol{w}$ (see Algorithm 1 and Theorem 4.2 in [3] for details). This achieves the SQ lower bound whenever $\\mu_{p_*}(\\eta)$ is positive and of constant order (see Assumption 4.1(b) in [3], where $\\mathbb{E}[\\zeta_{s*}(y) \\psi_{s*-1}(y)]$ is exactly $\\mu_{p*}$ in our notation). This will be the case for batch reuse SGD whenever $\\eta$ is sufficiently large (on the order $d^{-1}$), whereas for alternating SGD it will hold whenever $\\mathrm{IE}(\\sigma_*^2) = p_*$ and $\\eta \\asymp 1$.\n\n**Emphasis on Learning Rate:** We highly appreciate the reviewer's suggestion to better frame our contributions. In the final version, we will establish a clearer distinction between the hyperparameters $\\gamma$ and $\\eta$, emphasizing that only the latter yields phase transitions in sample complexity whereas the former affects the sample complexity in a smooth way (due to the $\\gamma^{-1}$ factor appearing the rate in Theorem 3.3). We will also highlight that our framework allows for the study of other hyperparameter and design choices, such as the role of depth in the alternating SGD algorithm. \n\nWe are happy to answer any further questions.\n\n[1] Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit. NeurIPS 2024.\n\n[2] 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. NeurIPS 2023.\n\n[3] Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, and Tianhao Wang. Can neural networks achieve optimal computational-statistical tradeoff? an analysis on single-index model. ICLR 2025."}]

Author rebuttal:

Meta-review: This paper studies how the learning rate influences the sample complexity of two-layer neural networks under the single-index model. The authors show that moving from small to large learning rates changes the query class and the sample complexity of SGD variants, determined by the information and generative exponents, respecticely. 

The main contribution lies in a careful analysis of several SGD variants for learning single-index models, while explicitly tracking learning-rate dependencies. This is achieved through a unified framework based on a general update rule. The framework is further applied to online SGD, SGD with square label transformation, and batch-reusing, demonstrating phase transitions in each case.

The authors successfully addressed the reviewers’ concerns during the rebuttal, and all reviewers now recommend acceptance. However, several clarifications should be included in the final version: (i) a more explicit explanation of $\mu_i(\eta)$, (ii) a clear distinction between $\gamma$ and $\eta$, and (iii) further discussion on the choice of optimal learning rates, as also noted by Reviewer NSB9. In particular, comparisons to practical WSD learning rates and the possibility of a variational optimization over the function class of $\eta$ would strengthen the paper.
Decision: Accept (poster)