Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model
Authors: Siyu Chen
Beining Wu
Miao Lu
Zhuoran Yang
Tianhao Wang
Venue: ICLR 2025 Oral (2025)
Keywords: single-index model
feature learning
gradient-based method
computational-statistical tradeoff
Primary area: learning theory
TL;DR: We propose a unified gradient-based algorithm for feature learning in Gaussian single-index model with sample complexity matching the SQ lower bound

Abstract: In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal statistical-computational tradeoff in learning Gaussian single-index models? 
Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires $\Omega(d^{s^\star/2}\lor d)$ samples, where $s^\star$ is the generative exponent representing the intrinsic difficulty of learning the underlying model.
However, it remains unknown whether neural networks can achieve this sample complexity. 
Inspired by prior techniques such as label transformation and landscape smoothing for learning single-index models, we propose a unified gradient-based algorithm for training a two-layer neural network in polynomial time.
Our method is adaptable to a variety of loss and activation functions, covering a broad class of existing approaches.
We show that our algorithm learns a feature representation that strongly aligns with the unknown signal $\theta^\star$, with sample complexity $\tilde O (d^{s^\star/2} \lor d)$, matching the SQ lower bound up to a polylogarithmic factor for all generative exponents $s^\star\geq 1$.
Furthermore, we extend our approach to the setting where $\theta^\star$ is $k$-sparse for $k = o(\sqrt{d})$ by introducing a novel weight perturbation technique that leverages the sparsity structure. 
We derive a corresponding SQ lower bound 
of order $\tilde\Omega(k^{s^\star})$, matched by our method up to a polylogarithmic factor.
Our framework, especially the weight perturbation technique, is of independent interest, and suggests potential gradient-based solutions to other problems such as sparse tensor PCA.

Published as a conference paper at ICLR 2025
CAN NEURAL NETWORKS ACHIEVE OPTI- MAL
TRADE- OFF? AN ANALYSIS ON SINGLE -INDEX MODEL
Siyu Chen"l, Beining Wu' Miao Lu Zhuoran Yang', Tianhao Wang Yale University, University of Chicago, Sttanford University, Toyyoa Technological Institute Chicago {siyu. (siyu.chen.. Sc3226, zhuoran. zhuoran.yang yangyaaannnneeeeee beiningw@uchicagg..edd mi mialli@stanford.eda tianhao. wangêttic.edu
ABSTRACT
In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal caaistical-oomputattionall tradeoff in learning Gaussian single-index models? Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires O(d' dd samples, where s" is the generative exponent representing the intrinsic difficulty of learning the underlying model. However, it remains unknown whether neural networks can achieve this sample complexity. Inspired by prior techniques such as label transformation and landscape smoothing for learning single-inde index models, we propose a unified gradient- based algorithm for training a two-layer neural network in polynomial time. Our method is adaptable activation functions, covering a broad class of existing approaches. We show that our algorithm learns a feature representation that strongly aligns with the unknown signal 0* with sample complexity O(d"' /2 v d), matching the SQ lower bound up to a polylogarithmic factor for all generative exponents s* > 1. Furthermore, we extend our approach to the setting where 0* is k-sparse for k o( vd) by introduc- ing a novel weight perturbation technique that leverages the sparsity structure. We derive corresponding SQ lower bound of order ((kk"),, ). matched by our method up polylogarithmie factor. Our framework, especially the weight perturba- tion technique, is of independent interest, and suggests potential gradient-basee solutions to other problems such as sparse tensor PCA.
variety of loss and
INTRODUCTION
The success of neural networks is largely attributed to their remarkable ability learn rich and useful features from data during gradient-basse -aaed training (Girshick et al., 2014). This feature-learning capability allows them to outperform traditional methods like kernel-based approaches, which rely on predefined features (Allen-Zhu & Li, 2019; Ghorbani et al., 2019; Refinetti et al., 2021). However, when trained using (stochastic) gradient descent, neural networks can sometimes fall into "kernel regime", where their behavior resembles that of a fixed kernel method, constrained by their random initialization (Jacot et al., 2018; Chizat al., 2019). 9). In this regime, the ability of the network to learn complex representations is severely limited, undermining the primary advantage of deep learning. Therefore, it is crucial to understand when and how neural networks trained with gradient- method can perform effective feature learning to unlock their full potential, particularly in scenarios where a balance between computational efficiency and statistical performance essential.
In this work, approach this question in the context of Gaussian single-index models, canonical class of problems in statistics and learning (MacCullagh & Nelder, 1989; Ichimura, 1993; Hristache al., 2001; Härdle et al., 2004). The model is defined as follows: for covariates ~ ~/ Ia), the out- put y depends on the inner product (8* 2) with an unknown signal 0 E Id through a link distribution p, i.e., y ~ p(- (8", 2)). The goal is to recover 0* using i.i.d. samples (21, y1...., (Zn, Vr gener- ated by the underlying model. While n = ((d) samples suffice to recover 0* information-theoree
"Equal Contribution

---

Published as a conference paper at ICLR 2025
27 10"
accurncy 71% weammey acturs/y
1754
Lower
5 22
159
2 SQ lower bound
1.6
sucoow region
1.3
2 eccomse regien
log n/llg d
Conjecture regioe
9.9 107
1:80
v'd
Conjecture
9.3
6.0x 10
5" 1 (information)
050
36x 10
fail
37
5.5
08
log k/logd 26
11Dtmonsston. of Imputt
(a) Scatter plot of (d, n)
(b) (n, k) paradigm
(d, n)) for Algorithm 1 under model y (z, 0-)² exp(-(z, 0*))), which has generative exponent 8 4 (Example 2.2). Here acc(d, n) the average of the largest 8 values of the alignment between the neuron weights and the unknown signal 0" The slopes of these contour lines are all close to 2. indicating a sample complexity n z d2 for s* = 4. (b) The paradigm of sample complexity achieved by our algorithm for different generative exponent s* and sparsity level k, illustrating the success of achiving ceapuutttional-sttiittiii tradeoff.
Figure/ 1: (a) The contour plots of (log d, log n. acc(d,
(Bach, 2017; Damian et al., 2024), achieving this efficiently is difficult for polynomial-time -iiee algo- rithms, where the required sample size also depends on properties of the link distribution p. creating petpuutatiioalltttttttitii
gap. For example, when y is a polynomial of (0 22. it has been shown that two-layer neural networks with square loss need ((()") samples (Arous al., 2021; Bietti et al., 2022; Damian et al., 2023), where q" is the information exponent of the polynomial link function (Arous al., 2021; Dudeja & Hsu, 2018). Such sample complexity is indeed inevitable under the correlational statistical query (CSQ) framework, leading to a cumputaaional-ssttiittin gap for q" 2 2.
However, the CSQ framework does not capture the fundamental limits of all gradient-based algorithms. Recent works have shown that by leveraging higher-order terms in the gradient, neural networks can learn polynomials with as few as (d) samples (Lee et al., 2024; Arnaboldi et al., 2024). It turns out that the intrinsic learning difficulty captured by another quantity called the generative exponent 8*, which is at most 2 for polynomial link functions, and the corresponding SQ lower bound on the sample complexity is n (2d''/2 /2)1 (Damian et al., 2024). Thus, there is no computational -atatiiiiiai gap up to poly-log factors for learning polynomial single-indes models. However, for general single-index models with a* > 3. no gradient- based algorithm for neural networks has been shown to match the SQ lower bound, leaving it an open problem (Arnaboldi et al., 2024; Lee et al., 2024).
Furthermore, learning the Gaussian single-index model can benefit from additional structures in the signal 0*, such as sparsity, which can significantly reduce the sample complexity compared to those depending on the ambient dimension d (Candès et al., 2006; Donoho et al., 2009; Raskutti et al., 2012). Recent work by Vural Erdogdu (2024) examines the effectiveness of pruning in learning sparse features, demonstrating that it matches the correlated statistical query (CSQ) lower bound de' for k < Vd. However, the method fails to achieve the CSQ lower bound in non-sparse settings. For sparse single-index models with information exponent 9" 1, gradient descent diagonal linear networks nearly achieves the information-ther -thooretic lower bound thanks to its implicit regularization effect (Fan et al., 2023). Nonetheless, how to achieve the optimal sample complexity for general s* 2 is also unknown under the sparse setting.
Contributions. Towards characterizing the fundamental feature learning capability of neural networks in the Gaussian single-index model, our main contributions are as follows:
1. We propose unified recipe of gradient-based algorithms for training two-layer neural network to leam the Gaussian single-index model. Our method integrates a general gradient oracle with a weight perturbation technique, carefully designed exploit the underlying structure of the
'This 22dd (2) sample complexity lower bound is essentially for the detection problem. Dudeja & Hsu (2021) shows that there is an estimation-detecn unclear whether such gap exists universally. Throughout the paper, always refer to the SQ lower hound as the detection lower bound, since detection in general is assumed be easier than estimation.
gap for tensor PCA under the SQ framework, though it is
2

---

Published as a conference paper at ICLR 2025
Gaussian single-index model. This allows the neural network to perform feature learning of the unknown signal 6* in a computationally efficient manner. Our framework encompasses many existing approaches special cases, such as batch reusing (Dandi et al., 2024; Lee et al., 2024), lahel transformation (Chen & Meka, 2020), and landscape smoothing (Damian et al., 2023).
2. We show that for an unknown link distribution p with any generative exponent s* 2 1, the weights of the neural network achieve strong recovery of the true signal 0 after training by our algorithm using (dd /2 d) samples and polynomial running time. Our method achieves the SQ lower bound up to a polylogarithmic factor, and the first gradient-based algorithm for training two-layer neural networks that attains the nearly optimal computational-stttistiie
tradeoff for Gaussian single-index models with any s* 2 1. Figure 1 (a) illustrates an example for s* 4. 3. Furthermore, our method is able to take advantage of additional structural information of the true signal 8* Specifically, a novel weight perturbation procedure tailored to the sparsity of 0r Equipped with this, we show that the weights of the neural network can achieve strong recovery of the sparse signal 0* after training with Ö(k*) samples in polynomial time for any generative exponent s* 2 1. This sample complexity is also nearly optimal according to the sample complexity lower bound we establish for SQ algorithms, which might be of independent interest. Also, our method suggests a new approach to achieve the computational-statinn staatsssiall tradeoff for sparse tensor PCA.
consider the case where 8 is k-sparse for lo of o(Vd), and develop
In summary, our work provides a unified framework for training neural networks that can achieve cuntationallstatiiiionn
the nearly optimal generative exponent s* 2 1. Our method not only tackles the intrinsic difficulty of learning the under- lying model posed by the link distribution p, but also leverages the additional structural information of the true singal 0" that benefits the learning process. Integrating these results, our method attains nearly optimal balance between computational efficienty and statistical performance across almost all regimes of sparsity levels and generative exponent s* 2 1, as illustrated in Figure 1 (b).
tradeoff for the Gaussian single-index model with any
2 PROBLEM SETUP
We begin by introducing the notation used in the paper, and then describe the problem setup. For a probability distribution P, we denote by L (P) the space of
functions with respect to means equality in (TP) We denote the normalized probabilist's Hermite polynomials by --=e=="² /2 These polynomials form orthonormal
P. and (P)))
())(-)).0. where each h2(x)) := (-1)" -=²//_ dx
Val
basis for (O 1)), i.e., the space of square-integrable functions under the Gaussian measure.
Gaussian single-index model. We study the following Gaussian single-index model: The environment first samples an unobservable signal 0* ~ from some known prior E (SL-1)) Then i.i.d. data (21, (21.91..... y1)..... (Zn. yn) E Id x IR are generated according to the following distribution Pę- given 0*:
Po. 2~ ~~, Ia) y p(- ()),
(2.1)
Here p( (.) : HR ++ (IR) is referred to as the link distribution. A canonical example is the additive model where o( (0" 2))
) + c for some deterministic link function Φ R -> IR and random noise c. See Damian et al. (2024) for more complicated examples.
Generative exponent. The following discussion on the generative exponent is based on the work of Damian et al. (2024). We aim to learn (2.1) where the link distribution p has generative exponent gap for learning single-index models. We let (0' , =). Notice that P... (y, TP(y, .) (,==;0, Td-1) where we use P denote the joint distribution of (I, y) as this joint distribution is independent of 0- As the marginal distribution of also independent of 0*, we define the null distribution Q(y, 2) = (zz;; 4a) & Q(y) and denote Qv æ² = (x; 0, 1) @ Q(y) where Q(y) = Jg Ply, x)dz. Under square inttr-ietterrble condition under Q, the likelihood ratio admits a Hermite expansion with coefficient functions (C.(w) i.e.,
8* 2 1 a measure of the computational-statiinn
(v.s) P(y.:) (2( (1.22
E (z() hh, (x),, where (v)) EE (x))v)
(2.2)
[(v.s)
and FE (v) <1 for all 2 1. Note that (2.2) makes sense only when we are working with the inner product of P/Q and syguareintegrable function under the null distribution Q
Definition 2.1 (Generative exponent). For the Gaussian single-inde model defined in (2.1), the generative exponent s* of the link distribution p is defined s* (p) == min(s 2 1 Eg((s(y))) > 0).
3

---

Published as a conference paper at ICLR 2025
Example 2.2 (Example 2.7, Damian et al. (2024)), Consider the special case of the Gaussian single- for a deterministic link function $ R - R. When o is index model (2.1) where y = (( 2))
polynomial function, it holds that s (ő) S 2, and the equality holds if and only if f is polynomial. In particular, 8* (h,) = 1 for odd and 8* (h,)) = 2 for even 8. While for the example of <(x) = =x² exp( (op(-=?)) which is not a polynomial, it has generative exponent 8 (Φ) 4.
Two-layer neural networks. We consider using two-layer neural network with M hidden neurons to learn the single-index model (2.1). The weight vector for each neuron m [M] is 6. E Rd and the weights of the second layer are dis.... A.M E R. We collect all the weights and denote = (O....., 0M) E RdxxM a (al...., aM) Rd,, Now for any input x E IR' the output of
the network is given by f(z; 0, a) = Em=l am ((2, 0m)), where ø R + I is the activation.
3 OVERVIEW OF TECHNIQUES
In this work, we apply gradient- based methods to learn Gaussian single-index models, with a focus on feature learning in neural networks and the corresponding computational-statisii tradeoff. To motivate the techniques involved, we begin by discussing an illustrative example that highlights such tradeoffs. For this overview, we focus on s* > and the uniform prior и = Unif(Sa-1) has been shown that gap exists between the Cooommttionthhorreee (dd" /2) under this setting when s* > 2 (Bach, 2017; Damian et al., 2024).
lower bound 52 (d()) and the SQ lower bound
For illustration, let us consider training a two-layer network with a single neuron under the population square loss. When the weight of the second layer is small, the rescaled negative gradient satisfies
9 = -2a (o) y)) - ((2 0)) v) o' (2) = (yo' ((z, 0)) + err)
where we take yo'((z, 0)) as the signal term and treat -a00 0) ((2,,))))))) 8)) as the error term since it scales with a We ignore the error term in the following discussion. Taking expectation over (z, y) Pa- and using the likelihood ratio decomposition in (2.2), we have
Ep,, [g] Re Ee [y]
B2 (o'( 0)) 2]
Ea [vCo (v) Eg ((, 2)) o' o'((,, ((2,0)) 0)) 2]. (3.1)
bias
informative queries
where we use the fact that y and are independent under the null distribution Q. Note that the bias term does not contain any information about 8*, and it can be casily removed by a debiasing procedure, so we assume for simplicity that [F[y]] 0.
Failure of vanilla online minibatch SGD. We first consider the vanilla online minibatch SGD, which updates the weight vector 9 by 6 t- 0 - r Σ 9i for minibatch of size n. The sample complexity of gradient-based methods is determined by the signal-to-noise ratio (SNR) of the one- sample gradient, which in our case defined as SNR = [gg 0*)]² [E]//E[(l [ [1))) This the square of the alignment between g and 0*, governed primarily by the informative query corresponding to the lowest degree s* in (3.1) assuming that Eq [ (3) * O. It can be shown that the inner product between the lowest-degree informative query 1) and the signal 0* satisfies (see Lemma H.
Eg [h.- ((0", =)) d ((2(0)) (z, (z,00)) s* G.. (0", 07,* 0)50'== - Odd-(s*-1)33)
(3.2)
where a.. is the s* -th coefficient in the Hermite expansion of a. While for ||g|| we have
Egg. [lla [ d d. 10'0o(((2)))) 0)) = 2(d).
where the high-order terms in the likelihood ratio decomposition are ignored and we come back to this point later. Now we can argue why vanilla online minibatch SGD has difficulty achieving the SQ lower bound for generative exponent 8* > 2: Suppose Eo[U(s- (y)) and ã.. are both nonzero constants. Then the one-sample SNR is Odd=*). For a minibatch with n samples, the SNR of the gradient averaged over the minibatch is roughly n times the one-sample SNR?, i.g., nd==" To ensure
AA rigorous derivation of the error term with multiple neurons and general loss function can be found in the proof of Example 4.6 in Appendix C.2.2.
*This argument is not fully rigorous because B2,, [|g also includes "bias" [B2 [g] besides the fluctuations, but it remains valid long as ||g|| is dominated by fluctuations from all d directions initialization.
4

---

Published as a conference paper at ICLR 2025
one update step achieves alignment, i.e., the square root of the n-sample SNR, V nd= exceeding the trivial d/1 threshold attained by random vector, it requires at least d samples. Note that the sample complexity would become even worse if s* < argmin, {s [y]y(.(v)] * 03. This contrasts with the sample complexity O(d (2) suggested by the SQ lower bound.
The above failure of vanilla online minibatch SGD exposes three key challenges:
(Non-polynomial) How to handle the infinite sum of high-order terms in the likelihood ratio? LLow SNR) How to enhance the SNR to achieve the SQ lower bound?
(Zero correlation) How to ensure that the algorithm still works if EglyC. (w) = 0?
Below we discuss our techniques for addressing these challenges.
Label transformation via general gradient oracle. The idea to fix the zero correlation problem is to apply a nonlinear transformation T RR. - R to y such that T (v) has nonzero correlation with (.- This label transformation technique has been widely used in the literature (Lu & Li, 2020; Mondelli & Montanari, 2018; Dudeja & Hsu, 2018; Chen & Meka, 2020; Damian et al., 2024). In particular, Lee et al. (2024) show that the label transformation can be automatically realized by running two gradient steps on the same batch, a technique termed as batch-reusing (Dandi et al., 2024; Arnaboldi al., 2024). In this work, we study a more general class of gradient-bused methods with gradient of form = (y: (0, 2))2 which is an abstract form of the transformed gradient T T(y)o' ((2,, 0))z. z. The
desired condition becomes E2 (v){a- (v)] j O. where &. (y) is the s-th Hermite coefficient function of (1y, x) in the Hermite basis of x. One particular way to obtain such a gradient is to use a modified loss function, similar to the approach in Joshi et al. (2024), while in our case the specific choice of e is also related to the other two challenges addressed as follows.
Exploration by weight perturbation with high-pass activation. The low-SNR challenge corre- sponds to the fact that points on the equator of S orthogonal to H* are all saddle points in terms of (0, (. and random initialization typically lies near this equator. To efficiently escape from such saddle points, we perform random weight perturbation, akin to the approach in Jin et al. (2017) for non-convex optimization. To understand the effectiveness of weight perturbation, we still stick the squared loss and the two-layer neural network for the following recond-moment calculation. Specifi- cally, suppose the activation o is high-past and has the lowest degree s* .i..,, (zz) = E. (z). and consider for simplicity the case of odd s*, In the extreme case where 0 is perturbed into i.i.d. pure noise ...... 0g d we compute the gradient for each 02 and aggregate them into g = I.- (g1 + ..... + 9L). Using the properties of the Gaussian noise operator (see Appendix B for details), the second moment of this aggregated gradient satisfies
E [[al@]] R EEr Egls") Eelo' ((=, (0))0((=2 2 d d. 8 0 Eo, 100,0')- 0')
where 0, 0' are drown independently from Unif((d-1)). Since (0,0' R d-1/2, we have E[lgg R (3d-(,")))/) yielding higher one-sample SNR as the first moment remains unchanged and pushing the sample complexity towards the SQ lower bound. Moreover, we also see from the above calculation that the weight perturbation resolves the non-polynomial issue thanks to the near- orthogonality of the perturbed weights. The above heuristics can be made rigorous for polynomially large L, thereby handling non- polynomial link and activation functions.
Our approach also draws inspiration from the landscape smoothing method in Damian et al. (2024), but in constrast their problem setup, do not require full knowledge of the link distribution in advance. Instead, it suffices to know the generative exponent s* to construct a high-pass activation function as well as the gradient oracle vb. See Example 4.6 for detailed discussion on this.
4 GRADIENT-BASEE ALGORITHM FOR UNIFORM PRIOR
We first present our method and results for the case of 0* ~ Unif(Sd-1)) or equivalently, when there is no structural information on f*. Motivated by the discussion in Section 3, we propose gradient- based meta algorithm (Algorithm 1) that can train a two-layer neural network to learn the unknown signal 8" with Ö /2 v d) sample complexity, nearly matching the corresponding SQ lower bound. This
*The label transformation only affects the second moment by a constant factor as we show in Appendix C.I.
5

---

Published as a conference paper at ICLR 2025
Algorithm Meta-Algorithm for Gradient- based Feature Learning for Uniform Signal Prior
Input: Initialization (()) (0 ..... ( Rd where 0 iidd Unif(("-1)) a a e
RM number of iterations T learning rate 77 batch size n E N. polarization level y (0, 1), number of perturbation L E N.
For & = 0, 1.......2 T 1, in the t-th iteration:
Sample a fresh mini-batch of data ((x,) (5) ")
3:
Perturb weights [() = (70th + sm, 1/ + e(t) sm, 12, e(t) ltd Unif(S*-1) for all m,l.
4:
Compute the gradients Im,l = (1b(1, (0) (wmm =/")) + errm,,,) (1 for all m,
5:
6: Aggregate the gradients: 9m = (nL) " Ei (omm, 3 11 m
) for all m.
7: Normalize the update step: 9m = gm /llgm 2| for all m.
Update the weights 0(t+11] (B(+) ng.h // //10(() + nggnn 2/2 for all m.
Output: Final model weights O(T)
meta-algorithm (Algorithm 1) covers extensive family of gradient-based methods including the batch-reusing and gradient descent with label transformation or modified loss.
4.1 GRADIENT-BASED TRAINING ALGORITHM CAAAAITTHMALLGORORA (ALGORITHM 1)
We initialize each neuron m with 0.00 Unif(gdd1)) and we set om a for some sufficiently small >> 0 throughout the training. In each iteration E [T', sample a new data batch of size n.
Weight perturbation. Before calculating the gradients, we first perturb the weights of each neuron to get L noisy replica, by injecting uniform noise from the sphere gd-1 as in Line 4. There is simple rule for choosing the polarization level y. the previous section, we discussed how Ex,, [|]g||]] in the one-sample SNR depends on the following quantity:
B,00) Smd e
m (mm. w w -1 S (72110m)
+
B.a 20 Sm
Sm. (1)) -mpr"" = (n² 12-) Sm,
In this context, ?2 represents the bias from the exploitation of the learned search direction, and d 1/2 accounts for the variance from the exploration for the unknown signal. In fact, y should be set as large as possible to maximize exploitation while still ensuring that the exploration noise dominates. This balance is necessary fully gain the SNR enhancement from weight perturbation. This gives rise to the choice 7 = (dd1/44). Moreover, suffices to set ((nvd) as stated in Theorem 4.2.
Gradient aggregation and debiasing. Then for each neuron m and its perturbed weights wm,t- we calculate the gradient ii
L. for every sample (Line 5). Here, we express the gradient as sum of an oracle term (/( (1) (=(") w ((ll))) and an error term err m,,a which we will discuss in more detail in the next paragraph. Next, we aggregate the gradients for each neuron m by averaging over the samples and L perturbations get g!oe) as shown in Line Here we additionally subtract a term en (v) Jum. debias the gradient, where iin (y) the first coefficient function in the Hermite expansion of the oracle function v' .)) with respect to æ. Finally, we update 0/ according to Line 7 and Line 8.
Implementation for a general loss function. The gradient step in Line is an implicit decomposition of the actual implementation, and we present the meta-algorithm in this way for the purpose of theoretical analysis. Specifically, for general loss function E(y. [(; 0 a)) evaluated the two- layer neural network, the actual I. d. is the negative gradient of the loss rescaled by am i.e.,
Imdd. = am Von. (1)) f(z))) (w a)) = -E' ff(2) (w0 a)) o (m1m
((( 200)) 20)

---

Published as a conference paper at ICLR 2025
where we denote by (y. f) the partial derivative of the loss function with respect to the output f. Correspondingly, the oracle term and the error term are given by
<bt (0) mm 24 2/()) = ('v .0) o o' (?))), (1) = (C( - ((v [(x
errm,
(2)); (wmmmm= (.mtmm=m.a.))) a))) o' (( 2)
Note that err m.l.i can be made small by setting a to be small. Again, we emphasize that these two terms are not calculated explicitly, but rather from an implicit decomposition of the actual gradient.
Beyond the above example, the meta-al algorithm encompasses more general gradient- based methods, and the theoretical results presented later are valid as long as the actual gradient can be decomposed in the same way such that the assumptions of our main theorem are satisfied.
4.2 FEATURE ALIGNMENT AND STATISTICAL COMPLEXITY
For any v E (2((), we write its Hermite expansion as (yy, z) = -. (.)) hy( in the (2)()) sense, where (v)) is the s-th coefficient function and Σ== Eglv. < 00.
Assumption 4.1. For the Gaussian single-index model in (2.1) with generative exponent s* 2 1, the
oracle V R R satisfies the following conditions:
(a) (Quadruple- integrabble under Q) Both (y. x and v)(.x)) belong to (A()))
(b) (High-pass under Q). For all = 1,....88 -2, the s-th coefficient fanction is zero, i.e., (v) = 0.
addition, there exists a constant C > 0 such that [Egl<+. (y) ---- -1 11)]] 2 C.
(c) (Polynomial-like tail under IP and Q). There exists a constant C > 0 such that for all r 2 1,
max EEp (y, ])]"], Eg [Iv(y,,)) =" cCr
The
condition (Assumption 4. (a)) ensures that the decomposition of the likelihood ratio in (2.2) well defined for calculations involving the second moment, i.e.,
Ee [)) Ee x)
P(y.2)
Ba x),,x))?² (==()(())h
2(1=a)
The high-pass condition (Assumption 4. 1(b)) has been motivated in Section 3 and guarantees noise reduction for the second moment. The polynomial-iin like tail condition (Assumption 4. (c)) used for concentration arguments in the proof. Note that this condition is analogue to the Gaussian [==
hypercontractivity property, where E= (z) S Dr/2 if fxx is polynomial of degree at most D. In particular, v can be constructed as (V x) = l' (v)o' where I is the loss function and is the activation in the two-layer network. It suffices polynomial activation a for the polynomial-like tail condition (see Section 4.2.1 and 4.2.2).
use a loss l with bounded derivative and a
Now we are ready state first main result on the sample complexity of Algorithm 1 for uniform prior. See Appendix D for proof sketch for even s* 2 2 and Appendix E for detailed proof.
Theorem 4.2 (Sample complexity for uniform prior). Under Assumption 4.1, set the initializa- tion of the weights as 0(") ...., ((0) Lid. Uni Suppose that the event E {[err (t) d-10s" V(,,1,i,t) E [M] x [L] x [n] x [T]} holds with probability at least (a for some constant Co > O with (M, L, n, T') specified as follows. Set the learning rate 1j > 2, the polarization level 7- = 1/1 (log d/t/ and the number of neurons M = (1)) Suppose
ma S
n = θ ((d='/2 (2og +a 12) d(log d)²). L= O(d +1/22 log d).
Define t = (11-1111 11, and let A = (log d) 11/2 if < and A = d-1/ d) if 3. Then with probability at least O(d for some constant c > O, after running Algorithm I for T Ollog d log A 1111 / log(r-1) steps, there are at least ((M) neurons having alignment
KelT" 00) 2 - O(VA).
Theorem 4.2 shows that the sample complexity of Algorithm I n7 = 0(d=" /2 d). matching the SQ sample complexity lower bound for all s* 2 established by Damian et al. (2024). Compared to the partial trace method in Damian et al. (2024), our algorithm does not require special warm-start initialization. Mcanwhile, the computational complexity of Algorithm 1 is LLT = +1d2"+1/2vd" Indeed, one is allowed to choose 7 +00, which resembles tensor power iteration. So far the gradient
7

---

Published as a conference paper at ICLR 2025
oracle s is still abstract object, and next we will instantiate the above general theorem with concrete examples of & that yield implementable algorithms. We consider the special case of polynomial link functions with s* S 2 in Section 4.2.1, and then the general case for any s* in Section 4.2.2.
Remark 4.3 (Benefit of overparametrization). Algorithm I trains two-layer neural network with constant width M, involving L times of perturbation for every neuron in each step. Indeed, this is equivalent to train a two-layer neural network with width LM = ((d'* ad==" -1)/2 v (d d) d))/2), where we divide the neurons into L groups, each having M neurons. In each iteration we perturb the weights and compute the gradients, and then aggregate the gradients within each group of M neurons. This combination of weight perturbation and gradient sharing exploits the benefit of overparametrizaaton.
4.2.1 ONLINE SGD WITH BATCH REUSING
The oracle function &ú can be specialized to two consecutive gradient descent steps on the same batch under square loss to handle polynomial link functions corresponding to 8* S 2 (Lee et al., 2024).
Example 4.4 (Batch-reusing: iè for polynomial link functions). Suppose that the link distribution is polynomial of degree q. We consider & induced by batch-reusing single neuron, i.e., bly. x))
(x) + yo' (x + yo' (z)) (see Section 4.2 of Lee et al. (2024) for deduction) and choose of (z)
Lie (.):(z)) where C. E N is constant depending only on q and each q; (ni 1)).
Corollary 4.5 (Batch-reusing for polynomial link function). Suppose that the link distribution is given by polynomial link function. Under the same setups in Theorem 4.2 with the oracle vē given by Example 4.4, the sample complexity of Algorithm 1 is (d). recovering the result of Lee et al. (2024).
The proof is deferred to Appendix C.2.1. However, batch-reusing may not be optimal for s* 2 3 due to violation of the high-pas pass condition, necessitating more general approach to construct 1b.
4.2.2 LABEL TRANSFORMATION VIA MODIFIED Loss
We discuss another approach to construct v by modifying the loss function, a universal method for arbitrary generative exponent s* 2 1. Additional details and proofs are postponed to Appendix C.2.2.
Example 4.6 (1b based on modified loss). Let (y,xx) E' (g)oo' (x) with f(y) being certain loss function and (I)) being some activation function. Such a form corresponds to the gradient of the loss Ely- [(z; 0)) (assuming that a. is fixed and has small entries), since
mm E f(z;0) 0)) = -y f(=;0) o' ('(0m, ())= 2)) === -y( o' a'((m, 2)) 12 + errm 2, am Vo
where errm :=(( - (yy - (z; 0,))) o =00m ((s 0, a)) d'((0, denotes small error for sufficiently small a. In Appendix C.2.2, we provide specific choice of the activation function (xx) (order-s" Hermite polynomial) and the loss function Ely) (a carefully designed random loss function), satisfying all the conditions in Assumption 4.1.
Corollary 4.7 (Modified loss for general s*). The oracle va given by Example 4.6 satisfies all the assumptions of Theorem 4.2, thus the results of Theorem 4.2 hold for Algorithm using this *b
To satisfy the high-pass condition with high probability, we construct random loss function based on the spectral properties of (.- in the likelihood ratio decomposition, detailed in Appendix C.2.2. Furthermore, we show an equivalence between direct label transformation and modified loss functions (see Appendix C. for details). Therefore, using random label transformation with the standard squared loss can also achieve a similar effect. (See Appendix C.4 for a discussion on the limitations.)
5 EXPLOITING THE STRUCTURE: ALGORITHM FOR SPARSE PRIOR
We have seen that when the prior on 0* is uninformative, our method nearly achieves the SQ lower bound that scales with the ambient dimension d. It is natural to ask whether our method can benefit from extra structural information on 8*, one classic example being sparsity. To this end, we consider an extension of the framework in the previous section to the setting where 8² is a k-sparse vector. We first introduce the algorithm for extreme sparsity k of Vd) and then discuss the general sparse case.
8

---

Published as a conference paper at ICLR 2025
Gaussian single-index model with sparse signal. Given sparsity level & = o( ((dd). we consider the Gaussian single-index model in (2.1) with 8* drawn from a k-sparse prior:
T :
8* 1 ~ (nir) o² ~ Un)
(5.1)
where St : := C
:= Rdd Dico 1, vj $ Φb is the associated h- d-dimensional unit sphere for any @ E St.
[d]
|0) }} is the collection of all k-spasse support sets, and Sh (o)) E
We show that Algorithm for the uniform prior can be easily adapted to leverage the sparsity of 6*, striking a nearly optimal crapuutaiionl-stattiiie balance with O(k*)) sample complexity.
5.1 ALGORITHM DESIGN: How TO LEVERAGE SPARSITY?
Note that Algorithm can also learn the k-sparse Gaussian single-index model, albeit with O d) samples, which is apparently suboptimal in light of the classic example of sparse linear regression. Here the key challenge is support identification of o², and the issue of Algorithm I lies in the weight perturbation using noise Ç ~ Unif(gd-1), thus unaware of the sparsity of 0". Below we discuss how to calibrate the weight perturbation with the sparse prior.
Perturbation by replicating the prior is not enough. An intuitive first-cut attempt is to use perturba- tion noise from the same distribution as the sparse prior Ty. in (5.1), which turns out be suboptimal as well. To illustrate this, we assume for simplicity a balanced 0* where every nonzero entry of 0* is equal to A 11/2 and consider i.i.d. fI...., EL ~ Tk. For each j E o*, consider the j-th entry of the lowest-degree informative query (analogous to (3.2)), whose first moment satisfies
Eeg- [رو] R Eg]y(+(v)] S 1, EtEL, (0" 01)0"110 R Be-ng 1100 "00"00""
12
(----11)
VE
Vi
where the last step follows from direct calculation for 0 ~ Tk. Similarly, the second moment satisfies Ep,.(13 R Σ.>.. s (6.)² Eg.0 ~x [00,0'; 01)--11
k² 4 A -1"
where and 0' are drawn independently from the prior TR. This calculation implies that the fluctuation of each entry of the aggregated gradient is of order /k2/d- k==-- -1/2 for batch size n. To successfully identify the true support Φ", the signal must be larger than the fluctuation for entries in o², resulting in sample complexity of n Ö(K** d/k²). In comparison to the SQ lower bound in Theorem 5.4, this is suboptimal by a factor d/k². However, for s = 1, we observe that Ep,- [ = (0(k-1) for j E o² and Eg,, 1a O(1), indicating that the support o* can still be identified using Ō(k) samples. The form of the perturbation does not matter here since both (0", 0) and (0, 8') are degree zero in terms of k Therefore, we conjecture that our algorithm succeeds for s* = even without weight perturbation as outlined in Conjecture 5.3.
Perturbation by groups that cover the prior. The suboptimality of the previous stragety originates from the fact that ø² is sampled from a uniform distribution over (3) different k-sparse support sets, making it unlikely for two independent sets to overlap (only with h²/4 probability). Then how to perturb the weights in way that guarantees a significant overlap with / The solution is to construct a polynomial- cover for the prior Tg. Specifically, we divide Sy into d subsets, where the j-th subset is define Sk.j := tØ E Sy j E Φ), which contains all k-sparse support sets that include the j-th coordinate. Now suppose 8r E Sg.j. then for any perturbed weight 8, with support from the same subset Sk.j. its support overlaps with o* almost surely, thereby eliminating the d/k' factor.
In particular, considering a two-layer neural network with width d, the above strategy can be carried out by perturbing each neuron mn using Om..,..... Om,I. whose support sets are sampled from the same group Sy m. As result, at least & neurons will have or more overlapping coordinates with the true signal 6*, For these neurons, the signal in the aggregated gradient would be strong enough for simple thresholding methods to correctly identify the true support 6= with Ō(k*) samples. We further refine this by first projecting the aggregated gradient for each neuron onto its top-k support, and then selecting the strongest projected gradient to update the weights.
Combining these yields Algorithm 2 for the sparse case, where we define the support projection matrix Ps = Eieo e and the top-k operator Top (v)= = argmax ( which extracts the k-sparse support & corresponding to the largest (in absolute value) k entries of v. We set the polarization level 7 = - 1/2 following the same balance between exploitation and exploration as in the uniform case, since the exploration noise is now of order -11

---

Published as a conference paper at ICLR 2025
Algorithm 2 Meta Algorithm for Gradient-basel Feature Learning for Sparse Signal Prior
1: Input: Initialization ( = (0 ..... 0 "00,.....,,)))
RdxM M, where 0 em. 1 E RM with number of neurons M = d, number iterations T E N, batch size n N, polarization level
7 E (0, 1), number of perturbation L E N.
2: for iteration t = 0, ,,
do
(2) ) 3: Sample fresh mini-batch {(=] Ui
4: Perturb as Line 4 in Algorithm with e(f) Lid. ((mm.)) and Φm, 1id Unif(SA.m).
Sm,l ~
(0) 5: Compute and aggregate the gradients to get gm same as Line 5&6 in Algorithm 1.
6: Find the top-k support of gm and project: dn Top, (g 9m = ao (gm)) for all m.
7: Locate the neuron with the largest |0 1|2: in = argmax,,.................... 11 2 1l2-
8: Update weights by gradient sharing: 0 9m
(1)
/ ||2 for all m.
9:
end for
Output: Model weights ((T)
5.2 SAMPLE COMPLEXITY ANALYSIS FOR SPARSE PRIOR
Theorem 5.1 (Sample complexity for sparse prior). Under Assumption 4.1, consider the sparse prior in (5.1) with sparsity level k satisfying w(d') < k < ol olvd) for small > O. Suppose that the event & = =[lerr & 10s", ((m,,,i,1) E [M] x [L] x [n] x [T]} holds with probability at least 1- -(d for some constant Cy > O with (M, L, n, T) specified as follows. Let k- n (2(kk loo k)²* -logd), d)), and L L +3)/2.log( log(k)* (k)a'=())))))))a Then with probability at least 1 - 0 for some > O, after running Algorithm 2 with T = 2 iterations, there are al least (2M) neurons that have alignment ( 8*) 2 1 O(A), where A k-1 v(k (6-(6'11)/2 -loo(k))33) -3/2) o(1)
Theorem 5.1 shows that the sample complexity of Algorithm 2 is n O matching the SQ lower bound established in Theorem 5.4 which will be presented below. Here for simplicity, essentially use an infinitely large learning rate when updating the weights in Line 8 of A Algorithm 2, so it takes only two iterations to achieve strong alignment. This equivalent to running the same algorithm with a finite learning rate but with a larger number of iterations, which is omitted for brevity.
Remark 5.2 (Implication for sparse tensor PCA). The connection between the Gaussian single-index model and tensor PCA has been discussed in Damian et al. (2023), by showing that estimating lr corresponds to a tensor PCA problem defined over the empirical Hermite tensors. Our weight perturbation technique can be potentially applied to iteratively solve sparse tensor PCA problems.
Conjecture 5.3. df < k < old) for a small i > and s* = 1, Algorithm 2 succeeds with sample complexity n = Ō(k). Furthermore, the same guarantee applies even without perturbing the weights.
Finally, we present the following SQ lower bound for the sparse prior, complementing Theorem 5.1. Theorem 5.4 (SQ lower bound). Consider the Gaussian single-index model in (2.1) with generative exponent s* 2 1. Suppose 0* is k-sparse for w([log d)2) & < d/2. Take 2 constant. For any (stochastic) algorithm using exp(SI (Iog )) calls to the VSTAT((ps n) oracle with sample size n, in order to achieve nontrivial alignment (0, 0-'1= > p with probubility at least 2/3, it requires 2 (log dy where p= p= if (log d)2 k / /d(logd) dys,
(5.2)
/2 n 2 [log 72: where p= 1/2) if / díllog d) < k < d/2.
(5.3)
More discussion on Theorem 5.4 is available in Remark G.8. Fork (Vd), running Algorithm 2 will succeed with Ö(k=*) samples, matching the lower bound in (5.2) for every s* 2 1. For = ((vd)) running Algorithm 1 will succeed with Ö(d" /2) samples, matching the lower bound in (5.3) for s* 2. In addition, for l Ω (d) with s* where the information-theoretie lower bound is 2 log(d/k)) (Neykov et al., 2016). This gives rise to the paradigm in Figure 1 (b).
conjecture = Ö(k) samples to be sufficient,
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-sen saddee dynamics. The Thirty Sixth Annual Conference on Learning Theory, pp. 2552-2623. PMLR, 2023. 19, 20
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019.
Anima Anandkumar, Yuan Deng. Rong Ge, and Hossein Mobahi. Homotopy analysis for tensor pea. In Conference Learning Theory, pp. 79-104. PMLR, 2017. 19
Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant:
Data repetition allows sgd learn high-dimensional multi-index functions. In Hight-dimensionll Learning Dynamics 2024: The Emergence of Structure and Reasoning, 2024. 2, 5
Gérard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in
sparse pea. In Conference on Learning Theory, pp. 479-482, PMLR, 2020. 19
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Muchine Learning Research, 22 (106):1-51, 2021. 2, 19,
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. Advances in Neural Information Processing Systems, 36, 2023. 19
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53, 2017. 2, 4, 19
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonmull complex sample covariance matrices. The Annals of Probability, 33(5):1643 1697, 2005. 19
Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander Wein, and Ilias Zadik. The franz-paris criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems, 11:33831-33844 2022. 19
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768-9755 2022. 2, 19
Giulio Biroli, Chiara Cammarota, and Federico Ricci- Tersenher How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application tensor pea. Journal of Physics A: Mathematical and Theoretical, 53(17): 174003, 2020. 19
Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-55 509, 2006.
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. Advances in Neural Information Processing Systems, 33:22134-221455, 2020. 19
Sitan Chen and Raghu Meka. Learning polynomials few relevant dimensions. Conference on Learning Theory, pp. 1161-1227. PMLR, 2020. 3,5
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Davin Choo and Tommaso drsi.. The complexity of sparse tensor pea. Advances in Neural Information Processing Systems, 34:7993-880 8005, 2021. 19

---

Published as a conference paper at ICLR 2025
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 Neural Information Processing Systems, 36, 2023. 2, 3, 10, 19, 20
Alex Damian, Loucas Pillaud- Jason Lee, and Joan Bruna. The computational complexity of learning gaussian single-index models. arXiv preprini urXiv:2403.05529, 2024. 2, 3, 4, 5, 7, 19, 31, 64, 83
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pp- 5413-5452. PMLR, 2022. 19, 20
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step time. In NeurlPS 2023 Workshop on Mathematics of Modern Machine Learning, 2023. 19
Yatin Dandi, Emanuele Troiani, Luca Amaboldi, Luca Pesce, Lenka Zdeborova, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. In Forty-first International Conference on Machine Learning, 2024. 3, 5, 19
Alexandre d' Aspremont, Laurent Ghaoui, Michael Jordan, and Gert Lanckriet. A direct formulation for sparse pea using semidefinite programming. Advances in neural information processing systems, 17, 2004. 19
David L Donoho, Arian Maleki, and Andrea Montanari. Mlssage-passinggg algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 18844))11111 2009. 2
Rishabh Dudeja and Daniel Hsu. Learning bongle-index models in gaussian space. In Conference On
Learning Theory, pp. 1887-1930. PMLR, 2018. 2, 5, 19
Rishabh Dudeja and Daniel Hsu. Statistical query lower bounds for tensor pea. Journal of Machine Learning Research, 22(83):1-51, 2021.
Jianqing Fan, Zhuoran Yang, and Mengxin Yu. Understanding implicit regularization in over- parameterized single index model. Journal of the American Statistical Association, 118(544): 2315-2328, 2023. 2, 19
Vitaly Feldman. A general characterization of the statistical query complexity. In Conference learning theory, pp. 785-830. PMLR, 2017. 19
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2): 1-37, 2017. 19, 62, 63
Gerald B Folland. How to integrate a polynomial over sphere. The American Mathematical Monthly,
108(5):446 448, 2001. 77
David Gamamik and Ilas Zadik. Sparse high-dimensional linear regression. algorithmic barriers and local search algorithm. arXiv preprint arXiv:1711.04952, 2017. 19
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. Advances in Neural Information Processing Systems, 32, 2019. 1
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accurate object detection and semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 580-587, 2014.
Wolfgang Härdle, Marlene Müller, Stefan Sperlich, Axel Werwatz, et al. Nonparametric and semi- parametric models, volume I. Springer, 2004. 1
Marian Hristache, Anatoli Juditsky, and Vladimir Spokoiny. Direct estimation of the index coefficient in single-index model. Annals of Statistics, pp. 595-5955229 623, 2001. 1
12

---

Published as a conference paper at ICLR 2025
Hidehiko Ichimura. Semiparametric least squares (sls) and weighted sls estimation of single-index models. Journal of econometrics, 58(1-2):71-12)) 1993.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, 31, 2018.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International conference on machine learning, pp. 1724-1732. PMLR, 2017.
lain M Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. Journal of the American Statistical Association, 104(486):682 693, 2009. 19
Nirmit Joshi, Theodor Misiakiewicz, and Nathan Srebro. On the complexity of learning sparse functions with statistical and gradient queries. arXiv preprint urXiv:2407.05622 2024.
Achim Klenke and Lutz Mattner. Stochastic ordering of classical discrete distributions. Advances in Applied probability, 42(2):392-44) 410, 2010. 66
Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the tnforeetion-theoretie limit. arXiv preprint arX1v.2406.01581, 2024. 2, 5, 8, 19, 26,22 27
Yue M Lu and Gen Li. Phase transitions of spectral initialization for nigh-dimensional non-convex estimation. Information and Inference: A Journal of the IMA, 933):007-54,, 2020. 5
MacCullagh and JA Nelder. Generalized linear models. Monographs on statistics and applied
probability (37), 1989. 1
Marco Mondelli and Andrea Montanari. Fundamental limits of weak recovery with applications to phase retrieval. In Conference On Learning Theory, pp. 1445-1450. PMLR, 2018. 5
Alireza Mousavi- Hossein,, Denny Wu, Taiji Suzuki, and Murat A Erdogdu. Gradient-based feature learning under structured data. Advances in Neural Information Processing Systems, 36:71449- 71485, 2023. 19
Alireza Mousavi- Denny Wu, and Murat A Erdogdu. Learning multi-index models with neural networks via mean-field langevin dynamics. arXiv preprint wxXiv22408.0725: 2024. 19
Matey Neykov, Zhaoran Wang, and Han Liu. Agnostic estimation for misspecified phase retrieval models. Advances in Neural Information Processing Systems, 29, 2016. 10, 19
Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. 18
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax-optimat rates for sparse additive models over kernel classes via convex programming. Journal of machine learning research, 13(2), 2012. 2
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed. In International Conference on Machine Learning, pp. 8936-8947. PMLR, 2021.
Ryszard Szekli. Stochastic ordering and dependence in applied probability, volume 97. Springer
Science & Business Media, 2012. 66
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32, 2019. 19
Nuri Mert Vural and Murat A Erdogdu. Pruning is optimal for learning sparse features in high- dimensions. arXiv preprint arXiv:2406.0866 086.88688, 2024. 2, 65
Tengyao Wang, Quentin Berthet, and Richard Samworth. Statistical and computational trade-offs in estimation of sparse principal components. The Annals of Statistics, 44(5):1896 1930, 2016. 19
Peng Zhao, Yun Yang, and Qiao-Chu He. High- figh-dimensional linear regression via implicit regulariza-
tion. Biometrika, 109(4): 2022. 19
13

---

Published as a conference paper at ICLR 2025
CONTENTS
1 Introduction
2
Problem Setup
3 Overview of techniques
4
Gradient-based Algorithm for Uniform Prior
4.1
Gradient-based Training Algorithm (Algorithm 1)
4.2
Feature Alignment and Statistical Complexity
7
4.2.1
Online SGD with Batch Reusing
4.2.2
Label Transformation via Modified Loss
8
5
Exploiting the Structure: Algorithm for Sparse Prior
5.1
Algorithm design: How to leverage sparsity?
5.2 Sample Complexity Analysis for Sparse Prior
10
A Numerical Experiments
15
Notation, Preliminaries and Related Works
17
B.1 Background on Hermite Polynomials
18
B.2 Additional Related Works
19
Supplementary Proofs for the Main Context
19
C.I Proofs for Section 3
19
C.1.1 Equivalence between Direct Label Transformation and Modified Loss Function
20
C.1.2 Moment Calculation around Initialization
20
C.1.3 Heuristic Derivation of Sample Complexity
22
C.1.4 Failure of High-Pass Assumption
24
C.2 Proofs for Examples of Oracle Function
24
C.2.1 Batch-reusing for polynomial link function
25
C.2.2 Modified loss for general 11...
28
C.3 Debiasing the gradient estimator for Unknown Oracle
30
C.4 Summary of Limitations
Proof Sketch of the Main Theorem for Uniform Prior
31
Proof of the Main Theorem for the Uniform Prior
32
E.1 Properties of the Gradient Step
33
E.2 Proof of the Main Theorem for Uniform Prior
35
E.3 Proof of Key Results
40
14

---

Published as a conference paper at ICLR 2025
F
Proof of the Main Theorem for the Sparse Prior
46
F.1 Proof Outline and Preliminaries
46
F2 Properties of the Gradient Step
48
E3 Proof of the Main Theorem
49
F.4 Proof of the Key Results
54
F.5 Proofs for Technical Results in the Sparse Case
G Statistical Query Lower Bound for Sparse Signal Recovery
62
G.1 Proof of Technical Lemmas for SQ Lower Bound
65
H Supporting Lemmas on Moment Calculations
67
I Technical Results
72
I.1 Technical Results for Hermite Tensor
72
1.2 Technical Results for Uniform Distribution on the Sphere
77
1.3 Technical Results on Polarized Random Vectors
79
J Auxiliary Lemmas
82
A NUMERICAL EXPERIMENTS
We conduct extensive simulation experiments to validate the sample complexity result established in Theorem 4.2. In specific, for a fixed Gaussian single-index model, we run Algorithm extensively over variety of problem instances with diverse scales and report the average accuracy in terms of the alignment. We lay out the details of the experiment setting follows.
Gaussian single-index model. We focus on the Gaussian single-index model introduced (2.1) with a deterministic link function p and Gaussian additive noise. Here set p(z) x². -exp(=xp"> + where ~ (000, o²) with Ø² = 0.5. As shown in Example 2.2, the generative exponent the function p is s (p) = 4. In addition, the signal parameter 6* is uniformly sampled from the unit sphere in Rd.
Neural network architecture. We adopt the two-layer neural network introduced in Section 2 with M set to 15 and am = 1 for all m E [M] in all experiments. Since s* (p) 4, we set the activation function (2) h4 (z), i.e., the fourth-order Hermite polynomial.
Training using Algorithm Algorithm 1, we set v0 y) y d'(x), as stated in Example 4.6. Such vb is justified by considering the following alignment loss:
L( 1 y f(2; a) =1 Σ a a((2, bm)) y,
(A.1)
where recall that each entry of a is equal to a. As a result, by (A.1) we have
Vo_ L(0) o' ((2(00m)) z = ((22, 0m)) .
As result, we can alternativeyy interpret the gradients in Algorithm as those with respect to the aligmment loss L()). Thus, the choice of does matter in this case, and set 1 for simplicity. Furthermore, other details of Algorithm are specified as follows:
The parameters (0,, mm[[M] are initialized i.i.d. random vectors R uniformly sampled from the unit sphere.
We fix M = 15, a 1. 1 = 3, T = 24, and L = 500 throughout all experiments with different values of and d.
15

---

Published as a conference paper at ICLR 2025
We enumerate and d over grid with d E [32, 499] and [5 x 10 10%) Note that log E (3, 7), our choice of T satisfies the requirement in Theorem 4.2.
Choices of (d, n). We select 40 different values of d and 30 different values of within the ranges E [32, 499] and [5 x 109,3 3 10%) respectively. These values form an evenly spaced grid in terms of log and log d. See Figure 2 for an illustration.
28
13,00
10.00
3:00
3.50
5.00
5,50
(a) Scatter plot of (d,
(b) Scatter plot of (log d. log n)
Figure 2: Scatter plots of (d, n) and (log d, log n). In (a) plot against d and in (b) plot log agains log d. As shown in (b), we choose n and d such that they form an evenly-spaced grid after logarithm.
Evaluation. We report the accuracy of Algorithm based on 25 repeated experiments for every choice of (n,d). report two types accuracy metrics:
(i) Average accuracy: We report M -- M over the 25 experiments.
m= 10m 0*) in each experiment and then average
(ii) Top-8 accuracy: Given [0m]me[a] returned by the algorithm, we sort the alignment values {K0m, 0*) [M]- [m Then report the average of the largest numbers. The rationale is that if the top-8 accuracy is close to one, at least half of the neurons correctly find 0*
Contour plots. After calculating these two versions of accuracy for every (d, n) pair, we generate the contour plots based on (log d, log n, acc(d,n)), where acc(d, n) is one of the two versions of average accuracy introduced above. We report these two contour plots in Figure 3 and Figure 4, where Figure we zoom in to a smaller range of d for better visualization. In these plots, points with the same color indicate (log d, log n) with the same level of accuracy.
Validate (dd='/2 /2) sample complexity. As shown these figures, the average accuracy and the top-8 accuracy clearly exhibit linear relationship. That is. for fixed accuracy level 8. (d, n) satisfying acc(d, n)) = 6 a line segment. That is, log n Ci log + cg. To determine e₁ and Cg. we further fit linear models for (log d, log n) with the same accuracy level 8, where ó E {0.6, 0.7, 0.8}. For both the average accuracy and the top-8 accuracy, the coefficient e₁ in the linear models close to 2. We report the linear models corresponding to different accuracy levels in Table 1. This finding indicates that n x d2, Note that s* 4. Moreover, since we compute the accuracy for all (d, n) on the grid. The fact that Rs 2 indicates that the ((d= /22) sample complexity sharp.
Table 1:
Fitted linear equations of the form log n = C1 log + C2 for n, with the desired accuracy level. Notably, the slopes of these equations are all close to 8* //2 2, which shows that n x d=" /2
Accuracy level
Average accuracy
Top-8 accuracy
0.8
log(n)
1.9058 log(d) 4.4516
log(n)
1.8201 log(d) + 4.6218
0.7
log(n)
1.9103 log(d) + 4.3273
log(n)
1.9343 log(d) + 4.0790
0.6
log(n)
1.9640 log(d) 4.0361
log(n) 1.9653 log(d) (d) + 3.8901
16

---

Published as a conference paper at ICLR 2025
accuracy 70% accuracy
50% arnteny
1,6x 19
0.80
Poitte)
eccuracy
0. 39
0.48
6.x
0.16
45
Emputt
(a) Average accuracy
(b) Top-8 accuracy
Figure 3: The contour plots of (log d, log acc n)),, where aco(d, n) is either the average accuracy and top-8 accuracy. Here we zoom in to a smaller subset of d's for better visualization. We also plot the lines containing (log d, log n)) with the accuracy level among {0.6, 0.7, 0.8). The slopes these lines are all close to 2. This indicates that n ss d2 samples are sufficient and necessary for accurate estimation.
27
0.96
27 10
55% ScCurnty
occuray
60% Rccuray
aCCurACy
10
93x
0.68
10
22
6.32
133x
81
A1x10
6.00
Imput)
Inpero
(a) Scatter plot of (d, m.)
(b) Scatter plot of (log d, log n)
Figure 4: The contour plots of (log d, log acc n)), where ac n) is either the average accuracy and top-8 accuracy. We also plot the lines containing (log d, log n) with the same accuracy level among {0.6, 0.7, 0.8]. The slopes of these lines are all close to 2. This indicates that n Rs d² samples are sufficient and necessary for accurate estimation.
B NOTATION, PRELIMINARIES AND RELATED WORKS
Notations. We use N to denote the set of positive integers and No to denote the set of nonnegative integers. For vector E Rd we denote by R,, the set of polynomials of degree at most n in z with real coefficients. For s E N, we denote by IT, the symmetric group of all permutations of [s]. We denote by Na(-) and (-)) the standard normal distribution in Rdd and IR, respectively.
For two tensors (IR 60* and (IRd) 6M where 2 t,
(STT))
S Si...-a-edi
$1....91=1
Here, S[T] produces tensor of order and dimension d. We also define the symmetrization operation for tensor T e (Rdysr as
Sym(T)
Σ
t!
zEm
The followings notations for the relationship between two quantities (or matrices):
17

---

Published as a conference paper at ICLR 2025
b: There exists constant C' = (1) such that I Cb and S Ca. Note that and b should have the same sign. a = ((b) also has the same meaning.
2 b: polylog(d) b and b S polylog(d) (d) and the same for (b).
S bt There exists a constant C = ((1) such that a S Cb, and the same for = 2bb). The use of
a 2 b is similar.
a x a - polylog(d) b, and the same for a = (b). The use of a ž and a = (bb is similar.
< b: a S (polylog(d)) -1 b. The use of is similar.
In addition, we denote by a = b a ~ bbt, a ~ b + that b - a 5
こ E, respectively.
For square matrices A and B, A N B means that B A is positive semi-definite, and A B means that there exists a constant 0(1) such that C' B positive semidefinite
B. BACKGROUND ON HERMITE POLYNOMIALS
The probabilist's ' Hermite polynomials satisfy the following recurrence relations
ha(2)'= = /s h x (2) = v +1 hat1(z) + /s h 12-1
(B.1)
where we adopt the convention that h=1 = 0. For any function (O, 1)), its Hermite expansion given by
((x) = - h..x),
where we denote by f. the s-th coefficient of the Hermite expansion of f.
Gaussian noise operator. For p [-1, 1], define the Gaussian noise operator
Upf(x) Ev'~V(a. [f VI-p² p² x²)]
Proposition 11.37 of O'Donnell (2014) shows that the Hermite expansion of U,f is given by
Upf(x) ()
Σx p² fa hx(x).
A direct implication of this identity is
(===) = (oo
>
1o P...
(B.2)
==0
As result, for any fixed w. gd-1 holds that
Ez-N(o,1,) [f((w, h, =))] = E [U,f hg (x)] = (w, 0)* fe.
(B.3)
Hermite tensor. Corresponding to the Hermite polynomials defined for scalar variables, we define the Hermite tensors over Rd.
(-1) 1111//22 V 1=16/2
h (2)
(R for 2 0.
Vs!
The scalar-valued valued Hermite polynomials and the cunsor-valued Hermite tensors related follows:
h,( =)) = (0)0), vO c sd-1
(B.4)
Now let f Rdd R be s-times differentiable function such that for & I s, every component of k belongs to (2 La)). Then it follows from integration by parts that
E E ((
Vs! EE-N(OL (V [())]
(B.5)
This is version of Stein's lemma for tensor-valued functions.
18

---

Published as a conference paper at ICLR 2025
B.2 ADDITIONAL RELATED WORKS
Related Works. Our work contributes to the recent research on the computation-ssttistiee tradeoff' in learning single-index models. The information-theoreti limit for estimating the latent signal is n = =Q(d) (Bach, 2017; Damian et al., 2024), but the sample complexity lower bound varies across computational models. potentially revealing a computationall-tatiini
gap.
The information exponent qº (Dudeja & Hsu, 2018; Arous et al., 2021) governs the sample complexity for learning Gaussian single-index models in the CSQ framework (Chen et al., 2020; Bietti et al., 2022; Damian et al., 2022; Dandi et al., 2023; Abbe et al., 2023; Ba et al., 2023). Notably, Arous et al. (2021) show that online SGD has a sample complexity of n Ö(d -)), which is worse than the CSQ lower bound
((d /2) (Abbe et al., 2023; Damian et al., 2022). This gap can be closed by a loss landscape smoothing technique (Damian et al., 2023) originally developed for tensor PCA (Anandkumar et al., 2017; Biroli al., 2020).
Our work extends beyond the CSQ framework, aligning with more general SQ algorithms (Feldman et al., 2017; Feldman, 2017), where the sample complexity lower bound is Q2 /2), with s* as the generative exponent (Damian al., 2024). In this context, online SGD with batch reusing suffices for learning polynomial link functions (Dandi et al., 2024; Lee et al., 2024), while for 8 2 3, only the partial trace estimator proposed by Damian et al. (2024)
match the SQ lower bound.
In the sparse setting, including sparse linear models (Vaskevicius et al., 2019; Zhao et al., 2022; Gamarnik & Zadik, 2017), sparse PCA (Arous al., 2020), and planted models (Bandeira et al., gaps also exist. For example, in matrix PCA, the best rank-1 estimator achieves near-optimal sample complexity of (dd) due to the BBP transition (Baik et al., 2005; Choo & d' J'Orsi, 2021). Under extreme sparsity, however, sparse estimators require Ö(k)) samples, utilizing methods such as diagonal thresholding (Johnstone & Lu, 2009) or semidefinite relaxation (d' Aspremont et al., 2004). These approaches improve upon the (d) sample complexity but reveal a notable computational-statiann (Wang et al., 2016).
2022), wowppataiioollllsttssssittttttii
gap relative to the information-theoreticc lower bound of Q log d)
Related to our work, Fan et al. (2023) provide a Ö(k) sample complexity for learning single index models with n- using diagonal linear networks, and Neykov et al. (2016) report Ö(k2)) result for phase retrieval where q* = 2. However, as previously noted, the information exponent does not fully characterize the intrinsic computationallstatitieee tradeoff. Our work completes the picture by providing a mudient-based framework that simultaneously handles all sparsity levels and any generative exponent s* 2
On the other hand, Ba et al. (2023) and Hoosseiii et al. (2023) demonstrate that additional structures in the data, such as spiked covariance in the input, can break the d² sample complexity lower bound compared to the standard Gaussian single-index model. A promising direction for future research is to explore whether similar structural properties could be utilized to surpass the d' /2 sample complexity lower bound in the SQ setting.
Other works show manifold method can break CSQ or SQ lower bounds. Mousavi- -oossvii et al. (2024) investigate learning multi-index models using two-layer neural networks trained with the Mean-Field Langevin Algorithm (MFLA). In Riemannian setting, constraining weights to compact manifold allows MFLA to achieve polynomial-tine convergence while surpassing the CSQ sample complexity lower bound.
C SUPPLEMENTARY PROOFS FOR THE MAIN CONTEXT
C. PROOFS FOR SECTION 3
In this section, first argue why (E.,)((011) (V)-((y) is the major difficulty for vanilla (stochas- tic) gradient descent to achieve the informationntheoretti lower bound (dd) (the same for SQ lower bound) when the information exponent q² is larger than 2. It has been shown by Damian et al. (2024) that the generative exponent s* for polynomial model is either 1 or 2. Consider the information exponent q" > 2. We have the following lemma saying that the correlation E.))( (cC.(0) = 0 for any < q"
19

---

Published as a conference paper at ICLR 2025
Lemma C.1. Recall that Ss is the coefficient function for degree in the decomposition of the likelihood ratio P(z. (z.(( in (2.2). For any q² 2 2, consider the Gaussian single- index model given by y 3o + pp2" Sph((z) with (0, 1). Then for any << E2lys, (v)) 0.
Proof. The proof can be done by noting that (v) //) v) h (ar) [y), and and
Eoluc:(v)] Bo y EQ
(r v)
h (x:)
b]] Ep ly h=))]]
Q1 y)
3 E (z)(+ +
3. (o.n =0,
where the second equality follows from the independence between x and y under Q
Therefore, the first nonzero term in the informative queries of (3.1) is of order at least p". This gives rise to sample complexity d="-1 for vanilla online SGD (Arous et al., 2021) and d2"/2 for SGD after smoothing the landscape (Damian al., 2023). This sample complexity d²"/2 matches the correlated statistical query (CSQ) lower bound with gradient of the form yo(2) (Abbe et al., 2023; Damian al., 2022).
1. EQUIVALENCE BETWEEN DIRECT LABEL TRANSFORMATION AND MODIFIED LOss FUNCTION
In this derivation, we focus on a single neuron f(2; - (0. with & E s and sufficiently small a E R. A more general case with multiple neurons is handled in the proof Example 4.6 in Appendix C.2.2. We consider the following cases:
(i) T loss with direct label transformation - T(y).
(ii) Label transformation with modified loss function (f()), y)-
Let () denote the partial derivative of {(f, () with respect to f. We have the following observa- tions:
Lemma C.2. Take T()) ((,0,) -). Assume ((( B- B-Lipschitz with respect f. The gradients obtained from both cases (i) and (ii) are the same to a small error term that scales with a.
Proof. For case (i), the rescaled negative gradient obtained as
- Vo(T(v)) - (T(y) - f(2;0,a)) o'(((, = T (00, =}) - - (10,2)))
For case (ii), the gradient is given by
g = --
((0,))))
= (0, o' (10, (0.2) 2)) + (e()0,) - (f(zz 4)) (((0, ())
where (6, y) (' 0, a). y) S la B a (0. =) Therefore, in the following we just focus on case (i) and omit the enror term that scales with a for simplicity.
The assumption on the Lipschitz constant B is just for the sake of simplicity, which is not required in our main results.
1.1 MOMENT CALCULATION AROUND INITIALIZATION In the following, we provide a detailed calculation of the first and second moments of the gradient g ((y)oo((0 (00,))).2
20

---

Published as a conference paper at ICLR 2025
Without Weight Perturbation. Consider gradient 9 (())o'((8) 2 for single neuron with weight E gd-1 and input & E I2, where we omit the error term for simplicity. The first moment of the gradient is given by
Epg. (T()) o d'0,, 2))
= T(y) o' o(),,))) 12 1+ E Sely)ho(10" 2
Ee (T() d'0 =)) 2
+
Σ Ee (T()s (v) Eg (00, ((0))))&,(10 (())
bias
informative queries
The right-hand side of the above equation gives rise (3.1) in the main text. From the above derivation, we can see clearly that using a direct label transformation or modified loss function can handle the zero correlation issue Eg (v) = 0 for the informative queries. Invoking Lemma H.1 with (b,, (wr, =)) o' d'((0, ((0,=)) =)) where we replace - 0 and 0 0" in the lemma statement, we obtain
Eglo'((8) 2)) h, 2)) 2] V (o') (0,6*)* 8 vs (0'(0'))-) (0,6%)--1 0
where (a'), is the s-th coefficient of the Hermite expansion of o', and we have by a simple calculation that (o'), = / ōet1. Since we are only interested in the aligmment between the informative queries and the unknown signal 8*, only need to focus the second term for s* as the remaining terms are of higher order in (0, 0*) d d'1/2 at initialization. With debiasing procedure (Line 6 in Algorithm 1), we can also cancel the bias term in the first moment of the gradient. For simplicity, we just assume Eq(T(v)) O in the following calculations while the more general version handled in the proofs of both Theorem 4.2 and Theorem 5.1. This gives rise to the first moment
Egg- Kg.0") = EQ(T(w)<s s" -.. -0,00) Oad + (2) O (111/))) (C.1)
For the second moment, we have
Ep,- ||al|:] Ep,, . =)) -| O(d),
where || contributes to the ((d) term.
With Weight Perturbation. Let wi (76 + 4)/lh/ Erllz for I E [M] with & Unif(S and y d1/4 As the norm I/0 + E1l2 [1 - 1 +*] thanks to the triangle inequality, we can just focus on numerator, i.c., Wi = 70 & For given Wi, we denote the previous calculated gradient Then, the aggregated gradient over all L. perturbed weights given by g = + Sf= St. For the following calculation, we focus on s* being an odd number and larger than 1 for simplicity. In the formal proof of Theorem 4.2, we handle the remaining cases separately. Following from the same calculation for (C.1), the first moment now becomes
as gt. i.e., 9 = (yy)o' ((m, =))
1 Σ a. ((()S.)))))) s8" swx, - =(a==)))=0(00000-0000 (C.2)
EF,, ((g,0') =
40
which gives the same order as (C. The things are quite different for the second moment. Note that in the first moment, only the -- coefficient of the Hermite expansion of a contributes to the alignment with 0*, while the lower order terms are canceled out due to the fact that the likelihood ratio P(x, v)/vvv/QQvv (xx 2) has the lowest nonzero order s*. The second moment is now given by
L
Er,, |||s|13]
Σ
Epp,
[T()) o' ((ww,, 2)) - o ((wr, 2)) ||
1
L11=1
L
d
Expt [T()] d'(u,, 2)) o (ww,, 2}}]
21

---

Published as a conference paper at ICLR 2025
The approximation in the second line is a heuristic calculation for the second moment, and the rigorous version is available in the proof of Proposition E.4 in Appendix E.3. Now, we plug in the likelihood ratio Pzx, /2/ (z. y), and under certain regularity assumption (See Item Assumption 4.1(c) for details) we obtain
L
(1+
Eg |11g|13]
=
Σ
Eq
T(y)²
o' o'uur, 2)) d'(wp,z))
Σ (1(0)))((0+2))) $2.*
L
111=1
Σ
Eq [Tv]]]
Eg ((un, 2)) ((wr,
(C.3)
2
1,1=1
+ L
Eq [.)) Eq [o' (1w1, 2)) o' o(wwr, 2)) ho((0 ,
2))]
$2
higher order term
Here, remark that when comparing the terms on the right-hand side, the higher-order terms 2 s* are of order at least d d'='/2 /2 due to the fact that both wi and wy have correlation with #* of order d= 1/2 at initialization. Therefore, when considering the first term (C.3) only, we have
(
L
Ep [191|2 ~ Ea [T()]]
EB (our, 2),, L2
d
d
Σ Ee Jo' ((u), 2)) o' d'(wyy, 2))] 1711"
The first term in the bracket is of order d/L since Eylor' 2 (1). With large L, the main contribution comes from the second term in the bracket. Suppose the lowest nonzero Hermite coefficient of a is r, then we have by noting that Eg (ww,, wy s 0( + Eg (x)))) (d-r/2) for constant r and hence d Bolo''(uun o' (((wy, CAP
d up) <
(C.4)
L
L
180
where in the first approximation, we ignore the higher order terms. One would like to pick the largest possible r, which will be s* (C.2) requires G.. * O. This leads to the second moment
Bp,, [11 Od (0" -3)/2).
The case for r < 8" will be discussed ilater. Here, we remark that the label transformation T(-) is only changing the second moment up using label transformation would be changing ETIT())² {1 to Eg ] in the above calculation. This is also the reason why can stick the standard La loss in the discussion of the weight perturbation in Section 3 for showing how the weight perturbation can help boost the signal-to-noise ratio (SNR) in the second moment.
constant factor as the only difference that occurs for not
1.3 HEURISTIC DERIVATION OF SAMPLE COMPLEXITY
In the following, we first discuss what is the thresholding SNR for developing a O(1) alignment between the neuron weight 0 and the unknown signal 0*, Then, we provide heuristic derivation of the sample complexity Od /2) for the case with weight perturbation. We still focus on the two-layer neural network with a single neuron f'2=00, a) = aa (o0(()=)) as in the previous discussion. We asssume the following to hold in the following discussion:
(i) 8* is an odd number greater than 1. (ii) The activation function a satisfies the high-pass assumption, i.e., the lowest nonzero Hermite coefficient of is r..
(iii) The alignment (8,, (*) = o(1) (to ensure the previous simplified results are valid).
(iv) The label transformation T--) is such that Eg(T(() = and (e(T(()) (v)) + O.
(v) The number of perturbation T. is sufficiently large.
We will follow the update in Algorithm and take learning rate = oc, which means directly updating the weight by the gradient at each step.
22

---

Published as a conference paper at ICLR 2025
Sample Complexity from the View of SNR Recursion. Let first consider s", i.e., Assump- tion (b) holds. At step i, let the weight be g((-1)/|| (1-1) 22 and the perturbed weight be
1 ? g ((- (t 12 c)
ll ((-g((1)) //ggg10>>)|1 112 112
with </0) gradient as
Unif(Sd-1). Following the same procedure as in (C.2), we have the first moment of the
1 Er 1000000900 00) = T. (w)
= (7 -
12,,+ -
where the last equality follows from the fact that 8 1 an even number, and hides some constant factors. A proof of this calculation can be found in Lemma H.4. Following the similar derivation in (C.3)-(C.4)) the second moment is given by
E Illg
Σ (wy, wp)
d (7? 1d-112
r=
where hides some constant factors that depends on The last equality follows from the observation
that (w), wp)"*"1 V wp "1))2"=1 = / (Et,
(?² + KEE, Ex)))===1, and
concentration of (Ei, 11 for S s* - 1. Hence, the one-sample SNR is given by
(NR Bp [() (000)00011 1² C.
( (22
0 + d s'-1
Eg,- (1g(())
72
d 1/2
where some constant factor that depends on s*. One can replace (t-1) [gg 11, 0-> by nSNR (1-1) as the square root of the sample SNR is roughly the alignment between the gradient and the unknown signal. Under this replacement, we always have (t-N((t-1) = o(1) by our assumption (iii). We also obtain the recursion
Cn d=
(2d n2 SNR (1-1) +1
1/2 (
22 +1
Viewing the term inside the bracket function of = /22, and taking (1 (N)( we have
>2
+1
f(x;a)= x ++11
For a 1, decreasing function of x, and for a > 1, is an increasing function of æ. At initialization, the alignment order d1/2, which means (0) = ndd//SNR(0) (d-1//2) << 1. The best choice x and [(x; a (0) 1, and the corresponding next-step SNR is given by
(1) On
/2"
& /2, then a (1) & 1, and the same argument applies for (2) < and so on. This means that the alignment cannot break the barrier 1/4). On the other hand, when > d= /2 we have (1) >> 1. Suppose we can choose x as large as possible such that f'z; (1)) = (1), then we have another recursion:
On (t-
(9
/2
which means that the alignment can grow exponentially with
Polarization Level as a Trade-off. From the above discussion, we can see that when < 1, we want to choose as small as possible such that [(x; a) and when > 1, we want choose as large as possible such that f'(x; a) = a. In fact, setting x 1, i... y d-1/4 1/4, good choice to balace the two cases, as it is easy to check that
f(1a) 2 if < 1,
if >
which is optimal in the sense that it only introduces
1/2 factor when compared to the best choice.
23

---

Published as a conference paper at ICLR 2025
Heuristic Derivation of (Samlee Complexity from Alignment. Previously, derive from the SNR recursion that why (2d" samples are necessary to achieve nontrivial alignment with weight perturbation and why = d-1/4 is good choice for the polarization level. Now, we provide an alternative view to understand the sample complexity d from the perspective of the alignment between the perturbed weight and the unknown signal 6*. The following discussion is more heuristic in nature when compared to the SNR recursion. We still follow the assumptions (i)-(v) as in the previous discussion. We set = d-1/4
Consider the case of an infinitely large learning rate y, where at each step, the weight approximately given by the gradient from the previous step, i.e., w = /g/llgll2 + E, where is the gradient from the previous step, and & a perturbed noise. Here, our goal is for the perturbed weight to exhibit nontrivial alignment with 0* Specifically, we require
(w, 0*) 20 y (g/1l9 10002,00)) 0*) + (5,00) ((2-1/2).
Since (E, (5. is of order 1/2, follows that we need y (g/ 0*) > 0d2-1/2). This translates into the condition VnSNR > d 1/4, From our previous moment calculations, we know that
Erg- 00, =0 Egg, 11913
d=(="-1) d-(3'-3)72 -1)
SNR
which leads to the condition n = Ö(d 12) when combined with VnSNR >> d 1/4,
The rationale behind this criterion is that if y (g. f*) does not sufficiently exceed (5, 8*), then the perturbed noise will dominate. In such a case, the successive gradient updates would not provide more information than those derived from random initialization.
1.1.4 FAILURE HIGH-PASS ASSUMPTION
Previously, we heuristically derive the sample complexity O /2) for the case with weight perturba- tion and the activation function a satisfying the high-pass assumption, i.c., r =* Here, we discuss what happens when the high-pass pass assumption is violated, i.c.. 1 < < s" We still focus on s" being an odd number greater than Here, we have r 2 1 as by definition, is the lowest nonzero Hermite coefficient of a. This is akin to the case where Assumption 4. (b) is not satisfied. We still assume that a. * this is needed for the signal term to survive in the first moment calculation. Using the second moment calculation in (C.4), we have
Er,- [g. 22) Er,, ||9e|11
d d=(6--1)
d d-(r-3)/2 (d-1-1)/22 = Old (26' (2+1//)))
SNR
Combined with the same condition VnSNR > d-1/1 we obtain = ((d(()"=)))) Hence, for general 1 S S s", the sample complexity interpolates between O(d"' /2) and O 1122) We would like to point out that the above calculation is heuristic, and a formal proof is left for future work. However, we believe that the above calculation provides sufficient insight on the sample complexity when the high-pass assumption violated.
On the other hand, if s", this is equivalent to the case where the generative exponent is (as the terms in the decomposition of the likelihood ratio with degree less than r don't 't have any effect on both the first and second moment). Hence, we obtain a sample complexity = Ö(d/22, In summary, the sample complexity
d((2'' -r)Vr//2
Notably, if the activation has the lowest nonzero degree r, the oracle vb defined ('(, T(y)o (z), has the lowest degree - 1.
C.2 PROOFS FOR EXAMPLES OF ORACLE FUNCTION
Here complete the discussions of the specific examples of &a in Example 4.4 and Example 4.6.
24

---

(b, (t) (wmm) gradient descent steps on the same data under the square loss. More specifically, let us consider Published as a conference paper at ICLR 2025
C.2.1
FOR POLYNOMIAL LINK FUNCTION
We consider a polynomial link function y p(æ) Enr by (x) for general q" and By IR where q" is the information exponent of the link function, and we also denote it by ("(p) in the sequel. For batch-reusing, we take (v) yo' (x) + you (x yo (x)), where activation function (ar) satisfies that
C₂ (x))= Ey og- d'(x)= Vi.ag ag hz-1
Co
(C.5)
j=D
Here the degree C. E N only depends on the degree q of the link function and is specified later, and each coefficient aj Uni 1]). The second equality in (C.5) follows from the property of Hermite polynomials in (B.1). The error term err,,, m,,,i now comes from the difference between m. x("))) 2/ and the exact form of the update step obtained from two consecutive
single neuron whose weight is Wm, and single data point (zi, Vi). Here we omit the time index / for convenience. Then two gradient descent step on (2z, V4) gives
- ( Ui) (ys fzz; { / (me(())) o d'(Wm,d 21)) -2
+ (y:: fzz; tw (m))))))())) ((w zi)) 24.
(C.6)
where w Wm., + Re (y:-f(e f(;; ( o' o' ((wm,ts z3) ) Zz. Here nf the learning
rate for batch reusing, different from the learning rate 77 in our algorithm. More specifically, to fit the gradient form (C.6) into our general framework with oracle function vb(,, we take the batch-reusing learning rate nf =/11= Then the error term is given by
m. = -m, Ui) - (st, (Wm,t, z:)) = errm,ti.11 + elTm,da + erTm.1..3
(C.7)
where m.,,1 C.Tm,,ii,. and crrm, are given by
elTm,Li,1 - f (z4 (um, me(a)) a ((wm,) 24)): ClTm,1i,2 - f (es
me(m)) o' (ww m, 2;)): CTTm,Lis y/o' (wwm,), 21) + yoo (Wm.. 21)) + crrmatia) 1io'' ((mm,; + yoo (wo,,,
(C.8)
Proof of Corollary 4.5. To prove Corollary 4.5, it suffices to show that (i) Assumption 4.1 holds, and (ii) the event & holds with the desired high probability. In the following, we first verify Assumption 4.1, and then check the event E
Verifying Assumption 4.1. Note that the fact of y p(x:) being a polynomial immediately implies that both the square-integrable condition (Assumption 4. (a)) and the polynomial-like tail condition (Assumption (c)( are satisfied. remains to check the high-pass condition (Assumption 4.)())).
Since now s* < 2, we only need to check the condition that [E (y) V.a -1 (w)]] > 0.
Case 1: 8* 2. In this case, we have that
21 (y) = Em-> x (vo'(z) yo (I + yo yo (x))
C,
y. E
Σ Vj a, x hz-1 + Σ j=1
Vi aj ho-.--g-l (x
(C.9)
j=1
For the first summation (C.9), only the first summand is nonzero, so we obtain
y. E.E
Σ ai x -)))(()) V202 y.
(C.10)
1=1
For the second summation in (C.9), we have the following expansion,
y. E E
Σ j aj x h (x + yo (x))
25

---

Published as a conference paper at ICLR 2025
C₁ Σ
y. BENN
aj
Σ
J- hz-x-1(x)- (goo(x))
==l
k=0
C
J. 1--1 Bea x (1) (d'(a)) yett.
(C.11)
0=0
1=++1
(x(
where so (a)...... ..., SC, ( (a) are just polynomials of = (a..... ac,) (recall the definition of o o' in (C.5)) and each 1 1.k is positive number. Combining (C.10) and (C.11), we get the following decomposition of < (3):
V2(y) = V22g +
Σ km
(a(a)- M+!
Further using y = p(x) and the definition of (2 we get
Eg((2(1) - (y) Ep(h2(x) - 2 (y)
C
222 Ea-N (ha(x) p(x)]
Σ
Sh (a)
EnaN (ha(x) p(x)++1].
According Proposition of Lee al. (2024), we can set Cg E N+ (only depending on q) such that there exists smallest I < C, such that the information exponent 9 (p²) < 2. We notice that in this case s* (p) = 2, where we abuse the notation and let 8* (p) be the generative exponent of the polynomial p. In fact, s (p(p)
1 means [ (Ty) fx]=)] = 0 for all label transformation T. Hence, the only possibility is that q (p') = since p is just special case of label transformation and we
cannot get any first-order term from p'. Therefore, we further simplify the target quantity as
Go
Eglsa- (3) 1. -1)) = V2ay EerN (12(z) p(x) + Σ Sk 2k-1((a) EEEr [h2(x) p(x)*1
:=b
Rm
bk
Cy
= - 222 +
Σ by (k-1(a), k=
(C.12)
where by * 0 according to the definition 1. Now we take a closer look at the polynomials (sa(a), ac, ac,)) - We claim that: (i) they are different polynomials and are linearly indepen- dent, and (ii) especially, they are all nonzero. To see these, recall that
C₁
Sk (a .c.,) = Σ
BLWN [I- (x- -)--)---())) (o)
j=k4
where d'(x) = L Vi Oj- h1-1 (2). We can calculate that for k: - 0, so(an,, ",,,,,,,))))))))))) V202 which is a non-zero polynomial. For l = 1, we have that
Cg
sifan.... ,a,,) =
Vi- -aja- T--1.1 EE- (x
J=2
C₁ Vi aj r--11 E fx hz-2(x) ox)))
2r
2z +
3
which is non-zero (since in the summation from j = 3 to C, there would be no term in the form of 2²) and is linearly independent of of so because each terms in the summation here has degree exactly Now consider for k 2 2,
St sa ,ac,) 22k + 1)k: Tk.k at -020000
26

---

Published as a conference paper at ICLR 2025
C. Σ 2=R+2
Viagrz-1x
BEn ( hz (0))))(()('(())))))))))
2 to Cg there would be no aaaiaaaaaaaa 0204++1 and is linearly independent of So. :.... -k-1 due to the fact that the highest degree of these polynomials is larger than k. and the order for each term in Gą is exactly k ++11 1. Thus we have proved the two claims by induction. Now recall that we are aiming at proving the RHS of (C.12) is non-zero. By our two claims just proved, the RHS of (C.12) is linear combination of C. T + 2 linearly independent and non-zero polynomials where at least one of the combination coefficient non-zero (which is by). Thus we obtain that the RHS of (C.9) a non-zero polynomial of (a1. ac..) and its zeros form a zero-measure set. This proves that with probability over the randomness of (01, ... ,a.,,acc,, ). the high-pass condition holds.
Again, this polynomial non-zero (since in the summation from j
term in the form of a 1
Case 2: S* = 1. For this case of s* = 1, the proof is almost the same as that for s* = 2, where we additionally utilize the fact that polynomial link function with generative exponent s* can not be an even polynomial (Example 2.2) and thus there always exists some T S Cg E N such that the information exponent qº (p') 1 (see Proposition 5 of Lee et al. (2024)). With this fact, repeating the above argument can give the desired high-pass property.
Verifying the event E. Now we verify that the desired event
{Icrr 2 S d=10"", 10s", i,,, [M] [L] [n] [T]}
holds with probability at least 1 - (d) for some constant Cu > 0 that we specify later. With (C.7)
and (C.8), it suffices to look at each of the error terms err(() m err (t) and eir m.,,3 respectively,
1,22
For (r) m.1.1
eer
(t) m.lii
Σ |amll
(w z1t)| for (w =i)
(C.13)
Note that (m ] mE[M]] are standard Gaussians since ( (em.)mm Sd-1 Therefore, with probability at least - d co for some constant co >> O, we have that [Wm, 24)] Õ(1. Meanwhile, since that a and o' are both polynomials with constant order and bounded coefficients, and that M = (d), then by taking am = d 11s", we conclude from (C.13) that
emr (t) m. s O
(C.14)
For the second error term err (t)
similarly we have that
m.1.2.
err (1)
Σ Jamll ((((( + zil)| - (
(C.15)
m.1.1,
[M]]
Note that the one-step updated weights satisfy that
((w(t)) )+ 21) (w0 21) yt o' (((W 21)) + m...1.
Ö(1,
(C.16)
with probability least co since y/1 = p( (0+ 2,)) and p also a polynomial of constant degree and coefficients. Therefore, with the choice of am by (C.15), we conclude that
err m.1.1.2 S Ō
(C.17)
Finally, regarding err m.i.3 note that with the same argument as (C.16), we know that with probability m_ 1 zx) + yi (((w x)) + eir m,l..1 and (10 2;) + y/ o' ((0 (m 21)) are Õ(1) Since o' is a polynomial, it is O(p)-Lipsc continuous for inputs that are Ō(1). Therefore, combined with 1C) that we have proved, we can obtain that
at least 1 - d both (w
err m.L. S |wil (( m. = 100)
(C.18)
27

---

Published as a conference paper at ICLR 2025
Finally, combining (C.14), (C.17), and (C.18), obtain that for given i,,,,,,t), with probability at least 1 - O(d ")) holds that
eerr m.,,a (dd-10s))
19)
Finally, taking cu as a constant that is larger than 2 and applying union bound argument, we can obtain that
Pr(E) 2 1 MLnT - 2- a Old 60) 2 (d
for some other constant cg > Here we have applied our choice of (M, L, n, T) in our algorithm (see Algorithm 1, Algorithm 2). Thus we verify the property of the event &, proving Corollary 4.5. O
C.2.2 MODIFIED LOSS FOR GENERAL S* 21
Here we give specific choice of the activation function a and the loss function We mainly focus on the situation where Qy has continuous cumulative distribution function Fo, with bounded density fo. For the situation where Q2 is a discrete distribution (e.g.. classification task), we discuss them in the end of this section. For the activation function d, let (x) = (1/ s*) h. (z)). Since then,
(v) = (2)((1,)) 9) (x) v = Exlo'(x) (x)] ((()) = O, 4s
(C.19)
Regarding the choice the loss function É, we remark that if one chooses fixed loss function. there always exist instances such that the second assumption in the high-pas past-pass condition fails. To address this issue, we propose to construct random loss funetion To rule out pathological examples the underlying distribution IP, we make the following assumption on the coefficient function Ço..
Assumption C.3. We assume that the expansion of E.. == So Q [0, 1] on the Fourier basis (x)(x) of [o, 1] has non-zero coefficient of order at most D = O(1).
We then choose the loss function as the following.
D (w)) = Σ 2a.4. 9. (w), as ~ Unif([O, 1)), vosis
Notice that Fa, can be estimated from data using a one dimensional density estimator. Thus here we directly assume the accessibility of the function Fe. This further gives that
D
Eolss- b0) Eolcs- e())
Σ aj EUmr((.
[ (0) pi
(C.20)
which is a non-zero polynomial of the coefficients (as)iso due to Assumption C.3.
Proof of Corollary 4.7. To prove Corollary 4.7, it suffices to show that (i) Assumption 4.1 holds, and (ii) the event & holds with the desired high probability. In the following, we first verify Assumption 4.1, and then check the event E.
Verifying Assumption 4.1. First, since o' is a polynomial and E' is bounded (the Fourier basis is bounded and D O(1)), we know that both Assumption (a) and Assumption (c) are satisfied. Then, by the discussions before the proof, we know from (C.19) that the first condition in the high-pass assumption (Assumption 4. (b)) is satisfied. Furthermore, according (C.20) and Assumption C.3, Eg(Sa+ (v) -1)) (v)) is a non-zero polynomial of the coefficients (a.h<s and thus its zeros form measure-zero set. This means that with probability 1 over the randomness of (a), a.D), the second condition in the high-pass assumption is also satisfied. This verifies Assumption 4.1.
Verifying the event E. Recall our definition in Example 4.6, the error term is defined as
(t)
(e(w)) - E' [zz (w [ (m(mmmm))) - o'((w (t) m =;))
err errm,t m.1.
First, since w Wm,1 E gd-1, (w0 1 z1) is standard Gaussian and therefore (( 21)1 = Ō(1) with probability least 1 do for some constant co 0. Since a' is polynomial of constant degree,
28

---

Published as a conference paper at ICLR 2025
Õ(1) with probability least d= Second, consider that the second derivative of the loss function (y) is given by
then obtain that lo' d' mm 2:)i1
(1)
D Σ as p (Fe, fa, ==
e" ("(
which satisfies 1e" (y)] O(1) since the derivative of the Fourier basis still bounded and that the density of Qg is assumed to be bounded. Therefore, we have
l' (v.) - (u. f(2s m (mm = (1 tw ( (mmm)))
0 aml o ( 20)
Since is a polynomial of constant degree and (w m. :: 2;) are all standard Gaussians, we have that (1)
(o((u m. 24)] |= Ó(1) with probability at least Od cu). Now given that M O(d) and taking
am = d 11x", we have that
(v:) - l' (v: f(z (wm (mmmm())))))) = Ö(d-
with probability least 1 O(d-av) Therefore, for any given (m,2, i, with probability least 1 1 O-O(d- it holds that
lerr m.,, Odd-10+*) -(1)
(t) m,1,
Finally, as the proof of Corollary 4.5, we take co as a constant that larger than s* + 1. and apply a union bound argument, by which we can obtain that
Pr(E) 2 1 MLnT 00d 2 1- - O(d- 1- O(d
for some other constant c > 0. Thus we verify the property the event E, proving Corollary 4.7.
Remark C.4 (Discrete labels). For the case of discrete label that supports finite set y (e.g.. classification tasks), the construction of vp is somehow more direct. this case, we can still consider oracle function in the form of zy. of dxx) (pyy) for some function sply). The activation function (Ix) (1/v5*) hy. (x) and the function (pyy) is random function given by
+(y) ~ Uni 1)), Vy E y.
(C.21)
On the one hand, we can directly conclude as (C.19) that G. (v) for all s < s* On the other hand, we have that
Balsa- (v) - = Rolls (v) p(v)) Σ Qy(v) C.. (1) ((1))
DEy
By the definition of generative exponent (Definition 2.1), Ea, So- (y) > and thus at least one of (Qg(y) Cs. (y) yey is non-zero. Thus under (C.21), Relss- (y) - is non-zero with proba- bility over the randomness in sp. Thus we have verified Assumption 4. (.b.. Assumption 4. 4.1(a) and Assumption 4.1(c) can be verified in the same way as for the continuous case, and thus Assumption 4.1 is checked. Finally, we remark that in the discrete case we do not attempt to reduce the oracle function from certain loss derivative and thus we simply set the error terms err zero. Thus all the conditions in Theorem 4.2 hold and Corollary 4.7 is proved.
Remark C.5. -Non-monotynicity of the loss function) Note that this loss function constructed above not monotonically decreasing as f approaches y. However, this mon-oonntyyy does not impact analysis since our primary objective learn the feature direction.
29

---

Published as a conference paper at ICLR 2025
C.3 DEBIASING THE GRADIENT ESTIMATOR FOR UNKNOWN ORACLE
In Algorithm 1, we propose a meta-algorithm that incorporates weight perturbation at each gradient step. Specifically, as outlined in Line 6, after computing the gradient estimator
Im. (1hy, (0) (w
m. 2; 2/")) errm m...) 2 (0)
we aggregate the gradients and remove bias through the following operation:
1
(11 w m.))
nL.
We would like demonstrate that the debiasing operation only needed for s* S 2, as the high-past assumption already guarantees that the bias term is zero for s* > 2. Therefore, we only need to consider the case where s* S 2. In the two examples presented in Example 4.4 and Example 4.6 (where the modified loss e is known), we demonstrated that the oracle (0(,, a:) can be derived in closed form. Consequently, calculating &i (y) debias the gradient poses no significant challenges in such scenarios.
However, in cases where the gradient oracle is not readily available in closed form, additional complexity arises. Examples include scenarios where mini-batch SGD involves multiple passes over the same batch, or when label transformations are applied using a neural network. To handle such cases, we propose to use debiasing technique based on the U statistics.
To simplify the notation, we omit the time index Additionally, we drop the dependence on the neuron index m and the perturbation index I. For given mini-batch {(z, }-) we retain {v: ) and resample { } from an isotropic Gaussian distribution. Taking the product of these two sets, we obtain dataset of size n.:
D = {(2), 34 [e(
The gradient calculated for each sample (ž vii is given by:
Li.j (t>(,, (w. 2,)) + err,,)) Zz.
Note that here the term is uniformly bounded by (dd-10e) under the assumptions of both Theorem 4.2 and Theorem 5.1.
Leveraging the independence between { and {us and noting that (yy x) a has polyno-
mial tail (as established in Assumption 4. (c)),, we apply Lemma J.3 to obtain the following result with probability at least 6:
x
log 8-1 N
Σ KE(N),==[N]
(gr.s. w) (2
Σ
(yn, x)x
S
+Ō(N
Σ eerr.gl nN
nN
By choosing N large enough (e.g., N= dd for some large constant C), the estimation error becomes negligible and can be safely absorbed into the error term for our analysis. Note that this debiasing procedure is only needed once at each iteration for single perturbed weight, and we don't need to repeat it for each neuron or perturbation as the distribution of (w, 2z) the same for all neurons and perturbations. It is also worth noting that N only affects computational complexity, not sample complexity. Furthermore, the computational complexity remains polynomial in d.
In summary, suppose the gradient oracle is not available in closed form, can instead implement the following procedure for 8* < 2 at each iteration of A Algorithm 1:
1. Sample isotropic Gaussian vectors {
2. On synthetic sample {(), y4 beeel.leee perform gradient backward to obtain each ga.f for weight W1,1. which is the first perturbation of the first neuron.
3. Compute the debiasing term v un Eiein (9ig w1.1).
After this procedure, in Line 6 of Algorithm 1. we compute gifd (nL) - Σ/ (0 v (1)) instead. The other steps of the meta algorithm remain the same.
30

---

Published as a conference paper at ICLR 2025
C.4 SUMMARY OF LIMITATIONS
Failure of standard methods. Although being a gradient-based method, our approach is extensively modified to adapt to the structure of the problem. Although we have shown in 4.2.2 that some fatal issues prevent the vanilla mini-batch SGD from efficiently learning 0*, it remains unknown whether there is any standard gradient-basee methods (for example noisy-SGD) that can succeed in this problem.
Minimizing the expected loss. Current work focuses on estimating 0* using the two-layer neural networks. However, training the second layer with learned feature goes beyond the scope of this work. We leave it as a future direction to investigate whether a learned feature enables minimizing the expected error efficiently.
Misspecification of the gradient oracle. The validity of Theorem 4.2 is based on that the order of the gradient oracle is correctly specified as the generative exponent s*, i.e., Assumption (b). In general estimating tasks where the link distribution is unknown, the generative exponent is beyond the access and requires additional identification. In Appendix C.1.4, we heuristically derive that size samples required for order-r high-pass oracle obtain non-trivial SNR. This indicates that both the optimistic or pessimistic specification of the gradient oracle deteriorates the sample efficiency of our algorithm. To address the issue of unknown generative exponent, Damian et al. (2024) propose to run their partial-trace algorithm with different order and compare the quality of the estimated feature on the hold-out validation set. We expect that a similar strategy for our algorithm can also tackle this issue. However, this brute-force approach is computationally inefficient. an interesting future direction to construct an efficient and adaptive algorithm that works for unknonw s*.
Constructing modified loss in general cases. In Appendix C.2.2, we provide an example of loss function which provably satisfies Assumption 4.1. However, the construction of this loss function involves a random linear combination of Fourier basis, which is unnatural and is rarely adopted in practice. Additionally, this construction requires access to the marginal distribution of y under that needs an ad-hoc estimation. is unclear whether using an estimated version of Py would cause the failure previous argument. Besides, the minimal order of non-zero Fourier coefficient in Assumption C.3 is involved in the construction, which is typically inaccessible in practice. It would be an interesting future direction to investigate if there is any natural choice of loss function that generally follows Assumption 4.1.
D PROOF SKETCH OF THE MAIN THEOREM FOR UNIFORM PRIOR
In the following proof sketch, we only focus on the case s* being an even integer and 8* 2 2. The other cases only differs technically and we defer readers Appendix E.2 for detailded proof. For simplicity, denote ( = (0()) )²), the alignment between the weights of neuron m and the signal 0" at time t. Recall from Line in Algorithm 1 that the update for neuron at time step t is
g(4) 79m
(t)
g(++1) m
(D.1)
|| | (1) 70m 12
(++1) This implies that the alignment of the next iteration, pmn is a convex combination of the previous
alignment (1) and the alignment of the update step (T 0+) = (g ,0')/l99'' 2|2. Therefore, to show that the alignment improves after one iteration, we need to first analyze the scale of (o 0*) and I ||; then we will be able to characterize the improvement of (11 across iterations.
Alignment of the update step ( 0*). To this end, we calculate the first moment and and second
moment of gm over the randomness of the data ((=(") uu (t) ))2) and combining these leads to the (1) concentration of (gin /0//////// l|2. More specifically, for the first moment of gm we have
(E.,. 1, ,00 z pll (lel0) by + d 1/2
31

---

Published as a conference paper at ICLR 2025
while the magnitude of Er,-- [9m in any other direction orthogonal to 0* is of strictly higher order. For the second moment of 9m setting Y = ((d-1/4,, it can be shown that for any direction E gu-1, Ep,- [ggh o} =(d--s---1)2) Now chooing n [dd='
/2), it follows from Bernstein-type concentration inequality that the fluctuation of (gm ut) is of the same order (2+111))+ for any direction E g Therefore, with high probability,
(9th 8*) 2 p (1 by + + 1/2 -2((dd
0 8' 12+1/4),
(D.2)
l1 S p127 (1pm17 1/22// O(d (0(d-e'12tt0) 12+3/))
Phase I: from d-1/2 to weak alignment. Due to random initialization, it holds with high prob- (0) (d211/2 for (MM many neurons. Therefore, it suffices to consider neuron ability that Pm
with pm = (/2 When ((d-1/3) S pmd - O(1), by choosing ? (dd we can ensure that the first term in the lower bound for (gm ,*) in (D.2) dominates the
fluctuation. Based on this, we can leverage (D.2) to further show that (gm 0*) = (gm 0*) /11 1|2 2 (1+c)pm for constant 0. Consequently, it follows from (D.1) that
p 2 (1 + c)p!? for some constant > 0.
1/2 Therefore, takes (log d) many steps for pm increase from d to O(1). During this period, the dynamics will go through two phases separated by critical alignment level p* such that
7 (lpl2 1/2 x O(d-
which gives that p² (d- After the alignment p reaches p", there is short period where (1+1)/ /p-
0* 2 (pm /p*)"">,, until the alignment reaches d' 111441/4(s" -1), The length of this period very short compared the other periods on the road to weak alignment.
Pm grows rapidly as Pm
Phase 2: from weak to strong alignment. Finally, after pi grows to a constant scale, we need to (1)
track the value of pm Again using (D.2), show that p (++1) (1 + c) pm for
(t)
some constant c > Hence, it takes another Ollo d) steps to eventually achieve strong alignment.
E PROOF OF THE MAIN THEOREM FOR THE UNIFORM PRIOR
Now we present the proof for Theorem 4.2. We introduce a shorthand p = (0,0*) for the alignment between 0 and 8 This shorthand inherits the subscript and superscript of 0 as well, i.e., (t) (0(t) 0*).
Recall from Algorithm 1 that at the 1-th step, given the normalized gradient step gm = gm I9m 1|,. the updated weight parameter given by
g(++1) 0 + 7gm
/lgg0 (t) l|2
10 + ngm /llg.0 (t)
||2
Note that the alignment (0!h-1), 0*) depends on the alignment of the previous iterate (0th 0+) and the alignment of the current update step (ghh) /1lg/ [|, 0*))0))..))) so we first need to analyze the latter.
Here, we stop introduce immediate result that is crucial in characterizing the alignment.
Almost orthogonality of smoothing noise. Recall that the perturbated weights are w
(70l1)) + +mm.i)/ll0ft + fm.. where Em. ii.d. Uni Due to the high dimensionality, &m, is almost orthogonal to any designated direction with high probability. In the context, we are primarily interested in the alignment with 0* Correspondingly, we decompose gm with respect to the following orthonormal basis
(1) m = 0*, Umm2 (1- (1-p2)-10 12)-1/2 (0()) (0(9) 0*) -0),, v 3.
m.
(E.1)
32

---

Published as a conference paper at ICLR 2025
We justify this property by defining the following nice event for 0:
max Isadd (5m,i i m.2i) e, 1I e [4]].
(c)
This event helps in characterizing the alignment between the expected gradient Be,, [gm] and the signal 0" Additionally, we define another event for غ > 0:
T m (+) (1((m...mm../) <ε, vI, E [L] s.t. 1 +1).
This event controls the correlation between the noise vectors, which helps in controlling the fluctuation of the gradient. The following lemma provides some direct benefits of these events.
Lemma E.1 (Polarized weight
the nice event). For the orthonormal directions defined in (E.1), suppose that the corresponding nice event t (c) O Ele (e)
{0r, (1))
mm......, (
holds and the polarization level 7 E (0, 1/2). Then we have for any E [L] that
Kw m. 00) ( +
Km m. Um. fm,1)1 s 2 (7V 1-(00h ,0,2 +6),
1w (wm, m,t mmni) 2 2, 25isd.
Additionally, for any 1 + V. have that
(w m, W m.,) S 4(7² 27e + =).
Proof of Lemma E.I. See Appendix E.3.
Characterizing (ghn) 0*). Note that gm n- 1n-1E,
(t) where
(8)
1
Σ (v(y) (w 24
((1))) 24 (1( wm.))
Im.
||a in Appendix E.1 with two steps, stated in two key We characterize the alignment (g0 00)/Il9n (1) propositions follows:
1. In Proposition E.3, we analyze the magnitude of Ep,, Kom 0*)] and [pg, (Po) (ol2 0*) 0*)]l-
2. In Proposition E.4, control the fluctuation of (g.h) 8*) around its expectation using the polynomial-tail like property in Assumption (c).
Both propositions are established under the nice event El (c) n 200 sitions is deferred to Appendix E.3. Finally, with these two propositions, we prove Theorem 4.2 in Appendix E.2.
(?). The proof these propo-
E. PROPERTIES OF THE GRADIENT STEP
In this part, we characterize the alignment of normalized update give /Ilg (0) with the signal 6*, given oft) Since are focusing on the one step behavior for fixed neuron E [M], omit the neuron index m and time index t in the sequel. To facilitate the presentation, we propose the following simplified setup that extract all the essential elements to describe the one-step behavior.
Definition E.2. Fix and 8t and let p (0,0*). Suppose the data points (21, v1). ..., (Zn: Vn are
i.i.d. generated from Ps. Define = (7/ + ( + for = 1.... L, where e Er.
Udd are independent of (()s, Given the orucle vp RR - IR, we define
(v,,, (wr, zz)) =i E1 (v:) wt)
L
33

---

Published as a conference paper at ICLR 2025
To describe the associated good event. fix orthonormal basis:
0 p0
V1 = =
V1 p² 03.... ..... Vd:
and define
E(e) = [(5,00)|| <e, E(2) (KE, <τ,
max 25$5d
(5i, wi)l <e, vi Mel4]
VI,1 E [T]] s.t. 1*1).
As mentioned in Appendix D, we can reduce this problem to first characterizing Eg,, [g]. and then control the fluctuation of g around its expectation. To this end, we first introduce lemma that characterizes the first moment of the gradient step. This lemma is valid for both the non-sparse and sparse setting and is helpful in understanding the structure of the expected gradient.
Lemma H.2 (Decomposition of the first moment). Suppose that we are working with the setting in Definition E.2, where the oracle function & follows Assumption 4.1. Then it holds that
Erg- [g]
Σ
BolG(()) -
ww,, 0-)0- 0²
V8 +
Re(s.()) (1)1
(1), 0*)0 wr-
L
1=1
Proof of Lemma H.2. See Appendix H.
One can easily see that the first summation term corresponds to the signal, while the second corre- sponds to the resilience of current weight. The structure of wy guarantees (wi, 8*) small, therefore only the leading term in the geometric series above is dominant. Also we note that the leading term from the signal is larger than the leading term from the resilience, which indicates that the expected gradient is highly aligned with the true signal. This is justified in the next proposition.
Before stating it, we fix M to be a sufficiently large constant that does not scale with d and = Olog d). The involvement of M, T here is merely for the union bound argument in Appendix E.2.
Proposition E.3 (Alignment of expected gradient). Suppose that we are working with the setting in Definition E.2, where the oracle function & follows Assumption 4. 1. Additionally, we set 7 o(1,,
L Q(( V -1.""=1.d'"" dd" f2 v log d)) and e = o(1) chosen such that Pr(E(e)) event &g with Pr(E,) 2 1-----o (MMT)
Od (dd=="/2) such that on the
Then there exists event & O E(c), it holds that
BB 19) ~ [7p- (rlp) + d=1/2300
if 8* is even; if s* odd,
(7/pp + d d=1/220'
and that
Ep,, [glll2 - (Ep,, 9, 0-) $ (ale) + d 1'2/2
as long as rlel = w.
Proof of Proposition E.3. See Appendix E.3.
From this proposition, it is already clear that the expected gradient is highly aligned with the signal 0* in the sense that 1y-- [g]]| < 1<F [g), 0'') whenever 7/p|= = w(d-1). Later we will see that this is indeed the case during the trajectory of Algorithm 1.
=
Proposition E.4 (Fluctuation mini-batch gradient). Under the simplified setting introduced in
Definition E.2 where db IR x IR that
IR. follows Assumption 4. I. Suppose that choose and & such
<
27052. SZ
34

---

Published as a conference paper at ICLR 2025
Also, suppose that sample size
n (1)2+)))-1++1-1)) - log(d)2((+2)
where Cp is defined in Assumption 4.1(c). Then there exists {(vi, zi) 2)) hej event &g with Pr(E2)) S d (MT) -1, And it holds on Eg n ((() n E() that
(672 + 2) + I-11 log(d)
Kg, (*) (Ero-19) (o).
and that
||g Egg, loll| 2 +(72+2)0--1 + 1.-1) dlog(d)
n
Proof of Proposition E.4. See Appendix E.3.
E.2 PROOF OF THE MAIN THEOREM FOR UNIFORM PRIOR
Now we are ready to present the proof of Theorem 4.2.
Proof of Theorem 4.2. We first establish the good events required for the proof, characterize the properties the update step on these events, and then put things together establish the alignment of the model weights with the signal.
Preparations. To start with, we clarify the event we will work with by verifying that our configu- ration is compatible with the conditions Proposition E.3 and Proposition E.4. Recall that we set Qdd(' 11/22 V (d d) and is at most polynomial in the scale of clearly satisfy that L = ((d V (dlog d)). During our algorithm, = (d-1 -log d) 1/4 = o(1) () is fixed. Choosing d/1/2 log d, we have by Lemma J.6 that for any t and m, it holds that
- Pr(E()) (c)) < Ld (exp(-d/16) + + d logd/))
which decays faster than any constant- polynomial in d. Therefore, for sufficiently large d, it O(d /2). So far, we see that all the conditions in Proposition E.3 are satisfied and we denote the associated event as e(t) m,
holds that Pr ((l (c))
Next, verify the conditions in Proposition E.4. We choose ē ( |(c++oog d log d, then holds by Lemma J.6 that
S - Pr 2L0 (2) S L2 (exp(-d/110 + (og -
Additionally, we see that both e² < ē < and 27E S ? is satisfied for sufficiently large d. It is easily verified that our choice of I. a(( +1)/2 (dlogd) clearly meets the condition that
L L (cV d= dlog
we have that the sample size threshold now
log log(d)2C: 2Cp
log C2, (0" 11)22
(7 + 2 -1-
which is satisfied by our choice n @ ((dlog dys dog d) logd) Hence, all the conditions in Proposition E.4 are satisfied and denote the associated event cm
c(t)
35

---

Published as a conference paper at ICLR 2025
Recalling that the gradient in Definition E.2 does not include the error term err m,,,a additionally
need an event that controls the norm of the inputs 212 (4) this purpose, define
which helps to control ||err m.d 24 24 For
(1)
12 S VVa..
m,
max iE
By standard Bernstein's s inequality, we have that Pr (Em.3 ( S Ld exp(-d/8) Olexp(-C'd) for some C' > 0. To put things together, we work on the following event:
M T 3
= Mnne (c) m=1
80 (c) n 80 E O m, O cl0 m,3))
glo
which is of Pr(E) O for some e > by the union bound argument. Denote
(v(y, (t) (m (10) 2! Ei (u)²) wm..),
nl.
then Im and the mini-batch data ((,)) 2/2) )ie(m) match the definition in Definition E.2, which allows us to apply Proposition E.3 and Proposition E.4. Thanks to the event c(t) m, we always have for
any gd-1 that
Ko v) -( e)) S |1 12 1 |
< 1/2 max lerr (1) 1, m..ii
S d 98'
(E.2)
In the sequel, we restrict our attention to neurons that have d' 1/212/2 /2 alignment, i.c., the index m such that (0%) 00) 2 d-1/2/2. From now on, we will drop the neuron index m and the iteration index (t) in the following analysis for simplicity. The updated weight parameter is denoted as 0', and the aligmment after the update is denoted as p' (8', 8*). Note that for large M > 1, the number of neurons with initial alignment |pl 2 d- 1/2 /2 least ((M) For our convenience, the following
we will denote by
log /2 dogd (log ()gd)= d) ((().
Under the preceding configuration, Proposition E.4 and Eq. (E.2) together imply that the fluctuations of (g, 0*) be further bounded by
(172 +2) L log(d)
K9. 8*) -Es, (g. 01 $
-gg1((0))) - (g. 8')
n
(d- log (0
1)/2 log(d)
d
(2s* 11/4 (log d) 1/4 (2s
if 2, if 1. Ep,, [g 0-)]
1/2 112
(E.3)
d 1/2 (log d) 1/2 k 1/2
On the other hand, we have by Proposition E.3 and Eq.. (F.2) that
Ep., Kgg 0*) }) 2 EE,, [(g 0* (g 0*)
> | + d 1/2 2 (2-" (26"-1//4 (log 2/4/
95
whenever Jply = 22d-3/44) Therefore, when x is sufficiently large, we have the fluctuations to be strictly bounded by half of the signal strength. Thus, we have
1
10, 2
2 KB [7], 0-))
36

---

Published as a conference paper at ICLR 2025
For the norm of g, have that
||91l2 - ||ol| - |
+ || |p [
+ -||1EE G0|l2 Rr,, (2. 10, + Br.. (., 01
d= + l1g Er.. Toll2 + +111EE Øill (Egg (0..0))) || + KEgg Gg. 0')1
2/ Erg Mg. 2' (tlpp) d= + (d- log d)te -1/22 log
(E.4)
n
where in the second inequality, we apply Eq. (E.2) and the triangular inequality that |
[Bp [g] s ||g E.,, [o]]|- And the last inequality is deduced by combining the result Propo-
sition E.3 and the fact that d 95* d s2, For the leading term, it holds by Proposition E.3
that
[1pl7 + d 1-11 Ulph(lphy + d 1/2/220--2 if s* is even.
if sf is odd,
E g., 6-)
(E.5)
Recall that the alignment admits the following iterative update rule:
10', <
110 + G 1 0+)
+ nG
KG. 8*) 17 (8,0*)
1 1+ 1
where G = g/ 1/ In the following, we will define -² = d 1/ as critical threshold before the weak alignment. Specifically, in the phase I of weak alignment, we assume that |p| I p²: When the training process goes across this critical threshold, the dominant term in Ep.- [g 0* (ryp) (s" is iseven) (yp d 1 (s" even) becomes p instead of d 1/2
Stage of weak alignment. Case I: s* * s, is odd. Combining the results in Eq. (E.3), (E.4)
and (E.5), we conclude that for s* 2 3 being odd,
Kg,0%M 1 2 (lpl (dlog d) -1/4 + d- 1/2
1/4
1/4 l|all2 S (Ipl (dlog d) 1 + d 12250"0--1 d -3/44 (log d) 1/4 .x" -1/2
is important to note that here ">" and "5" only hides constants that are independent of d and n. Combining these two inequalities, we have that
Kg. 8*)l
1/4 1)
[g l2
(Ip)d)/4 (log d)-1/4 1)0" (log d) 1/4 .. 1/2
1/4
(lpl/p* + 1)x--1
+ +
Thus, if |p| S pr and take k. to be a sufficiently large constant, after the first gradient update, the alignment will grow to at least pr by noting that Kg. 1/1gll2 Z p*x and that
p*k x²x1/22 1/2
17 7 Pp
10'1
+ 11
VK - 1 2p' 1 -
p
As summary of Case I(a), with one step of gradient update, the alignment will grow to at least p² |pl p²
Stage I of weak alignment. Case II: s* even. In the case where s" is even, we have by the previous arguments that
(g.0*>= 2 lpl (d log d) 1/1 (lpl (d d) 1/1 + d 1/2/3""'-2 -1/4
|lgl|2 $ lp| (d log d) 1/4 (lpl (d log d) 1/4 + d 1/2gs*
d 12+ - // (log - 1/4 x 11/2
37

---

Published as a conference paper at ICLR 2025
Here, use the following fact that
(1el Σ (lply + d -211/300-2. /p2r? + d=') S (pll + d=11/300- -1pph
where the last inequality holds since |pl d=1//2/2 Thus, conclude that
(g. 0-21
|e| (1ood d) -1/4 11
1
p (1pld1/4(log (20gggd)=)) 1/4 1)
1) 1/1
|e| (lpl/p' + 1)"²
(E.6)
pel (lll/p* 1)
1/2
Note that = (()). Hence before the alignment reaches p², n 1/2 will dominate the denominator in Eq. (E.6), which gives us that Kg. 1/19gll Z lpl VR. Importantly, the "2" hides constants that are independent of and k. Thus, by taking x. to be sufficiently large constant, we can conclude that
VK-
1'1l pll.
1+ 2 2/pl-
As summary of Case II(a), before the alignment reaches pt, the alignment will grow exponentially fast, and this phase takes at most (llg(d)) steps. In the following, we consider the case when lpl 2 p" for both cases and
Stage II of weak alignment. Case I&II combined. Now consider the case when |p| > p* for both cases I and II, ie., s* 2 2. For this case, we have Ipl/D* + = lpl/p". Let us define r lpl/p* and r' = 1p 1/p", and follows that
Kg. l*)
-1
|1g
R 1/2 1/210"
and consequently:
r (1--=1p p" + x -1/2)
+ 11
(VK (Vh.res 1 -1) A pr
11 1
1 1
It can be noted that the maximal ratio r S (p*)-1 and also V -1 2 2n given that k is sufficiently large and r 2 1. Thus, we conclude that in this case
For this case, the growth of the alignment will be also at least exponentially fast, until it reaches (((p*)-1) i.e. |p| C for some constant C. This phase takes at most (llo(d)) steps.
Strong alignment. Case I&II combined. We need achieve strong alignment. When the alignment is on a constant level, we can deduce from its original form that
careful analysis for this case in order to
EE O 0-) Bpp, (Ehe()) (Iph))*-114 Fr,
where Bpp, (G)) = 211) is constant that depends on p and the random perturbations {&i hE(L)) and the error term follows that [E| < Odd-*).- In the following, we will drop the dependency on and (Elee and use B for simplicity. We have by Eq. (E.3) that
Kg. 0*> 2 -( - -2s' (25"-1)/4 (log - 1/4 x 1/2) -1/2)
=B(1pl))*'1 - 0 ((dlog d) - - ///4/"""""0/00"/0.. -1 xz -1/2
=---11 (0l..(Bl)) (Blp)"~11 (dlog d) - 1/
0 -11))
38

---

Published as a conference paper at ICLR 2025
and also
lll12 s B(loh))) ((ob)) + d2-1222"311 (log d) 11/4 x 1/2)
B((lh)) + ((1b))* + d -1/44))44_ (log d) - g0 x 1/2)
S- ( (Blp)*-11 (0d -2/44 (log d) - /4 1)
Therefore, once the alignment reaches a constant level |p| 2 ( we have
Kg, 0>1
B1p O /2)
I(G, 0*)
|
B p pp + O (log d) 1/4)
2 - 0dd-1/4(log d) 1//4/4 =: = A.
Here, A dlo//(log d)2/4. Thus, as long as 17 2, after one step gradient,
(G 10,
10'1
(G+ 10. + || (G 17 17 10)
(1 (1- A - 1p))
(1- - 1 k|) + (v1
- A)2 + +1 p9)² p9)2
(1 - A22
(1-1) 1 - + - pp) + +2V20+++22 +22
(1 1
(1- + 21 O(VD).
Here, the first equality holds by the Pythagorean theorem, the first inequality holds by the triangle inequality, and in the last line, separate the major term and the error term that scales with v A. where we use the fact that 17 1/2 with v) > 2. In addition, by letting = 1/ /(1 1 have
1-
1- (0)²
(1 (1- 11 112 + 11 2( (2) +O(VA)
T(1 - p²)
1+ p²) +O(VD)
< - +
Therefore, we conclude that as long as T < i.c. > 2. p² will exponentially decrease to O((1 - r)- VA), and achieves strong alignment in O A (logl steps.
Weak & strong alignment. Case III: 1. In this case, we conclude from the previous arguments that regardless of the alignment level, it always holds that
(E 000') B = 0(1)
which gives us
(6,00)) 2 B O 1/2, (log d) 1/2 x- 11/2),
and
|llll2 s B + 1//-1//((1/)) 1/4 + (log d) - 1/2 16 -1/2),
where we use the fact that d(log 2) Therefore, we also have
(g. 80) - O(llo d) -1/2 1/2 k 1/2) 1
HG, 0*)
||g/|2
where in this case, we also have A ~ (log - of the proof follows the same arguments in the previous case for the strong alignment.
1/2 just like s* in the previous case, and the rest
n
39

---

Published as a conference paper at ICLR 2025
E.3 PROOF OF KEY RESULTS
Proof of Lemma E. We begin with proving the first part of the lemma. For conciseness, we drop the supscript (t) and simply denote 8m as the present weight. We have the projection of Wm,r onto 6 as
7/0m, 0*) + (Sm.
[wm,, 0-)
S 2(71mml +c.
11 Em,il2
For direction 2, by definition have
[wm.1 Um.2)| = 7(mm Um.2) + (6m.l Um.2)
170m Em,il12
S 2. (1 0m.: Om Pm
110m Pm Pm l
-2(vV Pen + +c).
For the remaining directions, we always have
(W0mt umma)) (fmm, Um,s) + (Em,t, Um,s)
< 2-c.
170m Em,1l12
where we use the fact that (fm, Um,s) for i 2. This completes the proof for the first part. On the joint nice event E. (?), we have that KWmdd Wm.P
S 4- (70m + Em,i 70m + Em,y S 4(7² + 7 (0mm Smil) )) + 7 Em,v))-
On the other hand, it holds the event &m (c) that
( 1( p² Um.2 + (m,,1, (V1 1² (pl) . 2c.
Therefore, have for any + l' that
(Wm,t, Wm,r)) | 5 4(72 + +
Proof of Proposition E.3. Invoking Lemma H.2 with the fact that ||0* = 1, we can decompose
(Brgs [g), 0*)
19].0") = V
BelCo(v) Voti(u)] (wi, (wn,0+)*t 0+
825"
+
Eg (1)) -.-1(1)] (wr, 0-
2
Vs*
= Eglss (v) F.- (v))
(wi, 0--00-1--11--
(E.7)
L
where all the remainder terms are collected by R. defined as
vs
Σ (Eolss()) (44z 0*) + BelG++1(0) (00G++10)))60)))) 0').
==
Below will analyze the scale of each term in Eq. (E.7), and show that the remainder R is negligible compared to the first term in Eq. (E.7) with high probability over the randomness the injected noise E1,...,LI. Et.
40

---

Published as a conference paper at ICLR 2025
Analysis for the remainder term R in Eq. (E.7). To bound [R], apply the triangle inequality with the fact that Kwi, 8*) & 1 to get
R
V
Be (sa(v)) ( + (s+1
(. ((w,, 0*)
L
#2
1=1
Since Bols++(1)) S 1 for all 2 0 by the property of the decomposition of the likelihood ratio, we have
Bolls++1()) (o(ll - E (v) (v)
I Ec (v)
Σ (1))
and similarly for Evlls+(v) (4111)) then suffices to bound Σezer (V++1)/L
Etn Kw,, 0' Recall that we restrict ourselves to the following nice event
{
E(t) ((,,00) <,,
max 25isd
(G, <,
where {0r 0*, 02 (0 - (0-p0-)/ /1 p², V3. v..... fa is an orthonormal basis. Since we assume
that 7 = o(1), ) it follows from Lemma E.1 that Kw,, 0*) < 1/2 for all I E [L] on E(e). Consequently, holds on E() that
(1)
Σ 828
(wi,0'11 0'11'
Σ Vs+l.
Kwn, 0-11"
L
2
L
1=1
$28*
L
Kwn, 0-)
(E.8)
1=1
where S hides a constant that depends on s". Now it reduces to upper bound the right hand side in Eq. (F.8). proceed, we define
wn sup, (wr,, mi)l <6
wi
o otherwise.
can be easily verified that Wi wi for any 1 E [L] on E(e). and (wihetrr sequence of independent and bounded random vectors. By Lemma E.I, we have that
k 0") < 27 V..
To find its second moment, we have by definition that
Ex, [Wi, 0-)2-"1- = Eny, [(u,, 0-120"
sup (wi, (wi, ui)l S }]
< Eu, Kwr, 0-020" 2 (lply + d 1/2y20"
where the last line holds by Lemma H.4. Therefore, we can apply the Bernstein's inequality (Lemma J.1) to the right hand side of Eq. (E.8) restricted to E(e). We deduce from it that there exists a event E1, with 1r(E1,)) 2 1 - d ((MT), and it holds on E1 (E(() that
T. Σ Kwn, 0-)1"
1
Σ
Kwn, 0-'1"
T,
+ L- L-- log d) (lply + 2/22// + (e (VV logd
L
S (1ply + 1//2/
(E.9)
Here we use the fact that M and T are most polynomial in d and the last line holds since we choose L= 52 (11//2 (e 7)) log d V log d).
41

---

Published as a conference paper at ICLR 2025
Analysis for the dominant term in Eq. (E.7). We then consider the major term T-1 Ei= (w, 0- ya--" -1 By the definition of iū approximate its expectation follows:
Es, [(r 0--="-11= BEni [uy, 0''-' -1 { sup (wx, 21)1 S [
Eu Kwy, 8*) 000=="""====--000000000 -1 Pr (sup) Kwi, 24)) > c)
= Ru [(n,, ((un,0)))) 0-)00 Pr (E())))
where we use the fact that (wn, -1 < and the event {sup, (wn, ux) > o) C E()). Again, we have by Lemma H.4 that
(lpl7 dt 1/2 if s* is odd; pxx(lel + 1/2/220--2 if s* is even.
E (wr,, 0-)a --
Similarly, have for the second moment that
Emg (10,, 0*) -1>]
-1)) = Ev,, [1,,, 0- (0)))(2-
Supp/uu. us)l S {
I Ewn [wi, 00))((0-11)
(lply + d 1/1/222(==-1)
Given the boundedness on (c) and the second moment characterization, the Bernstein's 's inequality (Lemma J.1) implies that there exists & with Pr(E1,2) 2 - d d='/((M) Furthermore, it holds on E1 (e) that
wwr, 0'00'
1
Σ
W 0-00'-1
L
L
=Ear [ur,, ((),, 01) + E,
where the error term E is absolutely bounded as
E $ (1phy + d 1/2g5- logd (EV log + Pr (E(e)) L
L
$ (1el + 1/2/" + Pr(e (e))
S (1pt + d'11/23s
Here, the second line holds because L ( d2d . log d v dlog d) and the last line holds because Pr(E(e)) S /2
So far, we have obtained that on the event E(e) n E E the following holds:
Bg [(g, 0*)) Eng (wn, 0+3a" -al"""]]--- E R,
where [E| + RR| & (lply + d=1/2 given configuration of and Pr(E(())). On the other hand, provided that |p/r > d we have that
(lph: + d 1/2//=2= = (lph + d-1/2/0" ((pp))² d - 1ph 1/2)
= (lpl + ad |phr
+ d- + (1pl)) 2d 2d-1/22
(1ph d-1/2/s' Iphy
Therefore, Ep,,, [(g, 8*)] is always the major term no matter whether s* is even or odd, and we have that
Er,. Kg. 0*)] ~ TTp- (rlp) + -/21/2 if s* is even; (rrpp + d=1/2300-1
if s* is odd.
42

---

Published as a conference paper at ICLR 2025
We now turn to the norm of Bp.- [g]. We have already shown the projection of Ep,- [g] onto 8*, Next, define Pgt = II- - 0-0 as the projection matrix onto the orthogonal complement of the space spanned by 0*. Now. it follows from Eq. (H.6) that
|| P of loll22 -
Σ $2.*
[Ba(sa()= Ve+1(v)]l-
V
(1i, 0-)00 wi
Σ (wyy 0*)1"
Here, the first inequality holds by noting that the second term in Eq. (H.6) lies exactly along the direction of 0 and thus does not contribute to the norm of Pa- Te, [g]. while for the first term in Eq. (H.6), we use the triangle inequality and the fact that P vll2 S ||el|a for any v E Rd In the second inequality, we also use the triangle inequality and the fact that ||wx I|2 for all I E [L]. Here, the "S" hides a constant that depends on the boundedness of (V)(s(y) 1e++ (v) as we have shown in the previous analysis.
Note that the term Ex2.. & El= Kw,, 0-)1" is already handled in Eq. (E.8) and (E.9) under the success of event (()) n 1, on which we have
V8+1
||| lolll2 [Br, (g), 00,0")11
Σ
Kun, 0')1 (pph + 123/2
L
$2
1=1
Setting & E1, U gives the desired event.
Proof of Proposition E.4. The polynomial-taii tail property allows to control the fluctuation of the gradient estimator g in each direction at the level that is determined by the sample size n and the corresponding variance. To this end, we begin with calculating the variance of g along each direction.
Calculating the second moment. mal directions:
Given 9 and 8*, recall that we consider the following orthonor-
8 02 U3 Udd where we set di2 (0 (0,00)0*)/100 (0, 0 00 ll and i for i 2 are orthogonal 8* and 02- Our goal is to show that g has small variance on each of these directions.
As each sample (zi, y/) is independently drawn from Pa., we just need consider the variance of
1 in the direction of e for E (0), .1,..., 1a-1)
g1 = L Σ (111, (wi, 21)) 21 (v1) wi)
Varr,- (gg, v/) = Er, [gn r/
Er. Koi, n))²
< Ep, Kg 2)
From this we see that it suffices to bound the second moment of (91, v). which is given by
Ep (99 1
<
Erp, [vb(,, (wy, 2)), (wr, 22) + L
Σ Er. [(2()) (tor w/}
2
1,
1P=1
1
E2
(uu (wi, 2)) (wr, (2)
(1
Σ
((()) (00,))
L2
225*
Be [vb(,, (un, =)), (w), =)) u)
Σ
R (1))) u) (wr,e) v)
L
I
1x11
E (w))) v/2.
1=1
43

---

Published as a conference paper at ICLR 2025
As (y 2) is muadruple-interrabe by Assumption 4.1, the above integral is well-defined. We split the summation into two parts: | I' and I * I'. For -= I', we directly have an O(L bound for each direction 8*, 02..... Ua thanks to the polynomial-lik tail property of & in Assumption 4.1.
For 1 + I', Lemma E.1 implies that we have on the nice event E()) that
Kwy, wp)) > Σ 4(7² 276 +
- 8((? + ==
Invoking Lemma H.3, for any E f0*, U2. ;2...., Ud), holds on E(2) that
Ee (y (wn, 2)) (wr, (2, 0)2.
I+ Σ (o(v))o((00
$2s'
2 -1
1
of
c
c 1(v 1 0*)
c
c
(G
+e 1(s" 2 4))
62
E2
E2
E2
(E.10)
where we also define c max (wy, 8",, Kwy, 1)). eo max 2) (uo,, w)1}. If the nice event E() also holds, on which the following holds for all / E [4]:
KE,, 0- <,
max (E,, 2)) < 25isd
then we have by Lemma E.1 that [wi,,0)] 0'1 Tlpl + [(0,, 02), S - - t Ui V2
AI E [Z].
Consequently, we can set el Tlpl + = o[1) and
Hpp +c,
if 0" if U2 otherwise.
en
TV p² +c, e,
Therefore, we have the ratio
(ole 292
if = 0*,
& ~ A(72 2)
(alp) + c)² ?lpp +e
of
867++0 7242
6VVI- 20110041
~ 72 +ē
~
if = 02. otherwise.
62
7748
7+22
Since x² < ē, we conclude that /2/e2 $ 1 and eg/e2 S Hence, the right-hand side of Eq. (F.
bounded by o² -0-1 (n² 2)-- for all E {#*, U2..... va}.
Similarly, let us consider the term 1_- Eier Eolvi (v) (un, u) (wr, v). On the good event E(c), we have
Eglee (v) (w),, (ur, v) - 11s 2
T
S 1 2)
$ ( + 2)0 -1, 11ss 2).
The first inequality holds because F (v) whenever s* 2 2 because of Assumption 4.1 and the second inequality holds due to the condition that c² <
Lastly for all the terms that take single summation over I [L], we have them bounded by 1/ L as each term in the summation can be upper bounded by 1. Combining the results for / = and + l'
we have on the event E(6) n ε(2) that
Varp,- [g1. u>] < Ep,, [99 1)) +200" -1 '' We E U2,... "."",,...,, vd)-
44

---

Published as a conference paper at ICLR 2025
Concentration. The first thing is to control the variation of g in the direction of 0*, where need to upper bound the L' (IP+) )-nomm of (91, v). To this end, we define G (IR x IR) x IR + as
G(z, y, w) = Ioy,, (w, z, )) (2, w) + | (v) (w, ut|-
Also we define the empirical measure dl((w) L-1 E, (wr)), then holds by integral Minkowski's inequality that
(ʃ dl (v, (v.+)) dp(w) G(z,y, w) )))
2/r
Ex Kgn, u)
<
< / du(w) (f (v. G(2, y, v.)" 1/r
~ Σ Epg- [lv (wn, =)) (z, x/17 1/r
+ T. Σ
Kwn, w)|-
(E.
For the second term, we have on E() that Kwy, e) s 2 2e < 1. Applying the Bauchy-Schwarc inequality, we have for the summand of the first term in Eq. (E.11) that
Ep,- [[vCy, (un, =}) (ui, 2) I Ep,, [1b (wr, ( Ep,, [[ 2)/2r/1/22
Note that Er,, (wn 2)/2111/2 I (2r (2r-1)!!'/en) I ////, suffices to deal with Eg, [[ 2) 1//11/2 To proceed, we can decompose (wi, 2) to components that are correlated and independent with y as (wi, 2) = (wi - (1i, 00)00, z) + (un, 0")(0",,,
/ (wi, 0-)2. x' + (wr, O²)x''
where I (0", 2) (O 1) is independent to x' = (1 (wi, ())2)-1/2 (wi (w,, 0-)00 0000 2) ((, Therefore, we define a Gaussian noise operator as Up = Ez'~N(00,)(2(1 pr VI p²x')], And it holds that Ep,, (W,, (w,, 2)) E (0- and x)
P(z, v)
Eq
U (or-un mid (1,
(3r; y)
P(,,, 8)
((,,)) (nn
Ee
Qix y)
Ee ( (U
[2x,, 8) Q(
1/2
(E.12)
where the second line follows from the property of the Gaussian noise operator in (B.2). By assumption of the tail bound in Assumption 4.1, we have that Bq Ba(b(,,,)) x) S (4r))) For the second term, we have by the Parseval's identity that
Eq (U
P(a.8) v)
} -1 Σ (0 wn)² Eo (so(v))) $2.
where we use the property that on the good event E(E) we have Kwr, 0*)l < 7/pp + 5 < 1/2 And in conclusion, we get for the first term in Eq. (1. that
and also (1) <
1 Σ Bp,,. [1 (wi, (wi, 2)17 $ C2t122
Combining everything, we have
Ep,- (9 1/ C Ao {0t, ......, val. Thus, by Lemma J.3, there exists a {(=, (m)amm event E2 with Pr(E2,1) 2 1 d= (MT) and holds on Es that )*) Epg. [gg 0')]
Ep,, (9))0))) (e(ddMM) MT) M
n
((72 + 77'0'-1 + L-11 log(d)
1op(d)C++3/2
Vo E (0", U1 u,....,ea.hh (E.13)
45

---

Published as a conference paper at ICLR 2025
where utilize the fact T, M, all have polynomial dependency d. Moreover, since assume that
n = 2()) +-- -lg(d))(,+11))
we have that the first term in Eq. (E.13) dominates, which further implies that
Kg. 0*) Es 11. 0')1 /
((( 2)- I.-1) log(d)
n
Meanwhile, for the f2-norm of g. we have by the Jensen's inequality that for any 1,
1/2 1/r
Er,, [19:111]/r=
Ergg
Σ
u))
DE vaa
I Vd. (d
1/r S va. (r)
Σ
Eg Kgn (g.,,))")) m3/17)
vEJ0" va.....a)
This polynomial tail bound enables us to apply Lemma J.3 for the f2-norm of which implies that there exists some event 2,2 with 2r(E2,2) 2 1 /-= d-M/(M)), and holds &22 that
(()2 2))-+))--1+ --1) dd log(d)
119 Ep [ S
n
Setting & = &2,1 n 222 gives the desired event. This concludes the proof Proposition E.4.
F PROOF OF THE MAIN THEOREM FOR THE SPARSE PRIOR
F. PROOF OUTLINE AND PRELIMINARIES
In this section, we provide detailed proof for Theorem 5.1. We begin with some good events that we will work with.
Signal concentration. within its support. Define a series of event:
We hegin with good event which the signal spreads almost evenly
Eor = [||@| s Cp ///1//33
E,,00 = 1110 < Coo h -1/2 log log(k) 1/3;
k
Eo = Σ
(10 2 V2k 4
jEId
The following lemma guarantees that the all the events above hold with high probability.
Lemma F.1 (Good signal), Suppose that is sufficiently large such that k/ log(k) 2 32c(r V 1), k/ log" 2 k 2 /2c + 2, then it holds that
Pr(Eo,r) Pr(Eo,,e) 2 OK Pr(Eo.:) 2 0( (eexp(-co.2k3)
for some constants co.1, C0,2 > 0.
Proof of Lemma E.I. See Appendix F.5.
For fixed s*, we collect all the indices such that the corresponding nice event Eor- will be involved And we will stick to
in the coming analysis. Define S(s*) = {s* 1, 1(s" odd), 2s 2s*, 4s* the following high probability event
E0, Eo.; n (Nres(.))Eo,)
With Lemma F.1, have that Pr(Eo) 2 O(k-ou) for constant Co 0.
46

---

Published as a conference paper at ICLR 2025
Preparation for characterizing one-step gradient. Following the same manner as the proof for the non-sparse case, we first characterize the alignment of the gradient step (without adversarial error term err err m.t,). We begin with the definition of a minimal setup, that collects all the essential elements to form the one-step gradient. The following definition is the sparse analogue of Definition E.2. Apart from the method of generating the noise, in the sparse case, we will analyze the gradient in a coordinate-wist manner to adapt to the sparse structure.
Definition F.2. Fix k-sparse vectors 0, 0* sdd-1 with supp(0) and O supp(0"). Let - (0,0%) Suppose that a single batch of data {(zi, (i),,i) is iid. generated from Po.. We
fix the index m as the current neuron. We first sample 2m.1, 2m...... Dm... iid. Un,)(S i.e, uniform distribution over all k-sparse supports with m-th index always included. Given these random supports, sample independent noises Sm.1 Unif(St-l (0m. 1)) for I [L]. Now, for each I [L]
and y = o(1), we define Wm,1" = (70 + (m.)/ + Emall2. Then our target is
L
Im
ΣΣ
(1b (um,,) (.)) 21 125-v1660 (2(()) wm.)).
(F.1)
nL.
The associated good event is defined as (c) = {ssu (Em,; e,)l S c);
(F.2)
1.
Em = max sup 16m, n @m.rl, ( sup Iom n 1111, 16m, n nøl} s log ). 17
(F33
Almost orthogonality. Recall that our perturbation noise Em, is sampled from Unif(S*
which is approximately isotropic. One can presume that each Em. is evenly distributed among different coordinates. Additionally, expect that (Em.t, @m.1) and (Em.v, Pm.v) should have negligible overlap. These two qualitative properties, which can help simplify the analysis, are captured by Eq. (F.2) and Eq. (F.3) in Definition F.2. The following lemma characterizes the property of the perturbated weights Wm,t on the nice event &m (t) EE.
Lemma F.3 (Polarized weight on nice event, sparse case). Consider the setting in Definition E22 with y < 1/2. Suppose that the nice event (m)() Em holds and [|0" 1lo S 1/ log k, then we have that
sup (wm, eyy 2(y10, + c); 1
sup (wm,,, 0- s 2(Tppl + +c).
Additionally, we have that
sup W.mmi,WW... S 4(72 elog 1
Proof of Lemma F.3. See Appendix F.5.
This lemma, serving as the counterpart of Lemma 1, controls the behavior of the perturbated weight Wm. in its coordinates and alignment with 6*, Additionally, they are approximately orthogonal with each other, which allows for good characterization to the second moment of the gradient.
One may notice that the definition of غ differs from the non-sparse case, where we explicitly bound the correlation between different Em,,. This is the benefit of the sparse structure, as two randomly sampled k-sparse supports are naturally of low overlap.
Before delving into the component- wine wise analysis, we begin with a proposition that will be frequently used to calculate the average contribution of each term in the gradient. This proposition serves the counterpart of Lemma H.4 in the sparse case.
Proposition F.4. Suppose that the polarization level = o(1) and the noise (Em,ts 2m,1) ~ ( & Unif(Sr.m)) Let p = (0, 0*) where O is the polarized direction in Wm.l- Assume that the event E0,e-1(s odd) holds. Then we have that
[Tp- (r/p) + k 1/2
0*
+
ifs odd;
Em [ 0*79] ~
( + 4: 1/2 1/2 0
+ 1 18,)
if even.
where 8, o(1) for any s 0(1)
47

---

Published as a conference paper at ICLR 2025
Proof of Proposition F.4. See Appendix F.5.
Recall that we define the good event over the signal as & E0, n Eo.g n (ess(r)) Eorrs where S(s*) = {s* - s - 1 s odd}, 2s*, 4s*). This definition facilitates our defered analysis where need to control multiple moments of different orders and collect all the necessary good events in Eg in the first place.
F.2 PROPERTIES OF THE GRADIENT STEP
In this section, we preview some properties regarding the gradient defined in Eq. (F.1). The following proposition deals with the first moment.
Proposition F.5 (First-order moment of the gradient). Suppose that 0r is fixed such that the nice event Eo holds. Under Definition F.2, we choose S = =(1) such that Pr (Em(t))) < O(k-s' and
L l (oog(d) (k (E"((""-1 hh +1))
Then there exists a (Em,theetu)mmaanne constant C1 > 0, such that E n Em) Ema it holds for any j E [d] that
event Em,11 with Pr(Em,1) 2 o(k=o)) for some
[Eg gz [9ml. = Balss- (v) -1 v** Es,,, [W
+ Rmn:
where the expectation
B [ 07 0-'' 11 hp- ( + k 1/210 + +
0J if s* is even;
(vlel + k- 1-1 + k
85. 1
87
if s* is odd,
and Rmgg is the remainder that can be bounded by
Rm..l S (( (nlp) k- 1/2 (1. 1-12010
(Tlep k- 1-1 + + 5 + k k .1091 + (vle) + 1/2 0 + - 6+)* (710,) + -- 1/2 (k/d)) [itm)// + k (0(
Proof of Proposition F.5. See Appendix F.4.
The statement of this proposition clarifies the leading term explicitly, which enables to track the leading term in the strong alignment more precisely. To complete this section, we provide proposition that characterizes the fluctuation the gradient, serving as the counterpart of Proposition E.4.
Proposition F.6 (Fluctuation of mini-batch gradient). Under the simplified setting Definition F.2 where va follows Assumption 4.1. Additionally, suppose that the sample size
n= + log k)) --- - log(d)2C,+2)
where C the order of the polynomial tail in Assumption 4. 4.1(c). Then there exists a (2z, yi) heiml measurable event E,, with Pr(Em.2) 2 1 (id-(et)//T), such that on Em, N & (e) O Em, it holds that
((72 + e² log h1 -1 + L-1) log(d)
(mm eg) (Ero- [Tm],
for any E {ei, ez...... eal
Proof of Proposition F.6. See Appendix F.4.
With these propositions, we have completed the preparation for the analysis of the gradient step and ready move on the proof of the main theorem.
48

---

Published as a conference paper at ICLR 2025
F.3 PROOF OF THE MAIN THEOREM
Proof of Theorem 5.1.
Preparations. We first clarify the final good event that will use throughout the proof. We first fix k-1/2 llog k then it holds by Lemma J.6 that for each and t, we have
Pr (c) S Ld ((ex(-cck) + k- log k/4).
Since L and d are at most polynomials in k, we see that for sufficiently large k, it holds that Pr (em (t) s k k==", Additionally, we see that 7 = k-1/2 fixed and our parameter config- uration
= k) logd). L= 12( (00k((*++000 +3//2 log(k)"'-1
are clearly compatible with the conditions in Proposition F.5 and Proposition F.6. At the 1-th step, the mini-batch {( M/ (1))) (())))))
0 -=0% 0 and the error-free gradient
L
9m =
(b(y) (wm. m. 2 24 (3 wm!)
(F.4)
nL
1=1
together form an instance of Definition F.2, for which we can find the event ((9) and e(t) probability at least - O(d-c-1/T), such that on c(t) Proposition F6 hold.
m,2 both with
m,1 1 m,2 O c(t) the results Proposition F,5 and
The gradient we use in the algorithm differs from Eq. (F.4) by the error term err m,t." this difference, we define
(1) To control
sup 1 111 vdj.
m,
Given our specification on supm,l.i. err m. it holds on Elt that for any u e gd-1,
|1 la + la! V Ko u) (oll) .>ل $ 11 g
S supllz supllerr malle
s d 9s*
(F.5)
Our final event fixed to be
T
= n n
(c)
n nelh n new n g
in
me(d [d]
t=1
With union bound, we have that Pr(8) 2 o(d for some constant e > 0.
To avoid confusion, denote for each m that Gm Er,- loth Later will encounter some data
w(t)
dependent index n and using <(t) avoids the ambiguity of the expectation. With our choice of n and L, Proposition F.6 guarantees that for any m, f, holds that
|m. Fm.
(1)
((t)
S k -s---11/2 log 3/2 k.
(F.6)
In the sequel, we will drop the superseript whenever there is no ambiguity. We will frequently involve ((t) (o (9)))
(t)
Weak alignment. The proof towards the weak alignment in the initial step comprises three parts. In the first place, will show that the index of the gradient choose m guarantees that 1 2 k- Thereby, the corresponding gradient exhibits good alignment towards the signal. Based on this, we show that the support choose Top, (9m) is of considerable quality by successfully identifying
49

---

Published as a conference paper at ICLR 2025
0- (j |8 well-aligned with the signal 8"
1//2k). Combining these elements, we can show that the gradient Im is
We begin with analyzing the quality of 9m where m argmax,, l9 ll2 With this objective in mind,
we first work on deriving a signal-dependent upper bound for [l I|
Note that Pm = (fm. 8*) = 10%
where mm cm is the initial weight. Applying Proposition F.5, have for any o, |e) = A that
Σ JEB
gm 12 I (A-1/2168) (0 11) 11)2 even) (I:
+ 10 m
- ) ) -1 -1-14----11 oven))
Σ 03²
5E
+ (k: 2 v (1: 1/2 ) 11/
1/2 0 + 1 -1) 1) + k==="
Σ
07²
JEØ
+ (k: 1/ | + - )20 Kー Σ JE
(03 + -(k/d)L(stm))
+ k (2+"++1)
Note that we have ||0* 10 S 1-122 llog k; it holds that
kー (k 10 (A- 1/- 1 + + 2((= S k-= loggk))²*
For any ē such that |ò| = k. we have Ejeo 03 S 1 for any such that 110|lo = k. Therefore, we can further upper bound this quantity by
Σ sup [0) k
1m. 1 2 (1: 1 1/2 1 + 1- (5+)22² -2 + 20" log(k))>*
JE
+ (k 1/2 | + k 6+) 20" --
$ (k: 1/2 0z
+ k )=))2²-- 225'
+ k
loog /2 A: +
k=2= 2s= log(k)2*
(F.7)
Now we combined Eq. (F.7), Eq. (F.6) and Eq. (F.5) to conclude that
lam 12 S le sup Imm. Im.s" 2 + sup Im..s - Jmol
1 + sup
Σ
l3m. 12
sup k JEN
10| JEL
S ke (10 + k -- 5+ 220 -2 + k =200 log(k))²0
By definition of g.. we can further conclude that
sup 10 jEN
(grn e;)1
S k 1), -10 21== + o(k -2(0-
(F.8
On the other hand, for m E 0², we have (z/pp + 1111210mm + + -1- Proposition E.5 that
- 2 kT. Then it holds by
18m.s
2 2200 - Ō(k-26")
SE
and by Eq. (F.6) and (F.5), we have that
| 2 2-66 2(-- -Ō(k -20))
(F.9
Now, combinig Eq. (F.9) with Eq (F.8) by the definition of m we have that
h- (+ -1) |0 11)* + of (k- (1=- ス -
Ō((--2"))
We conclude the first step from the last inequality that there exists a global constant et > such that for sufficiently large k:
0 > (a . (1 o(1)) k -10---1) 1).3 -1) 112
2 c,k
(F.10)
50

---

Published as a conference paper at ICLR 2025
Now move the support identification. We have shown that 10 2 k-1/2 To establish 6 C Φ
Topp (9m). is sufficient to demonstrate that
sup
S inf 19mp]
(F.11)
jEd
JE
In the following, we will bound each side separately. Consider j & Φ², we have by Proposition F.5 that
Mm,l S 1/-11/210 +
'+)) " (k-1/2 1/2 001 (k/d) 1/3) - k (1++1)
Combining this upper bound with Eq. (F.10) and Eq. (F.6) gives us that
| < |m..j gm.l
Iin. 9m. + lōm.cl
S (k
- 1/2 10 + k +6+ )²² (I: 16-1//10,1 + (k/d) 1112) + (0=+11
+ d 95 k (s'--1 log 3/2 k
I k (0 1/2) log
3/2 O (6" +2)).
(F.12)
On the other hand, for E Dth we have that
Iām.l 2 115 1/2 + k- 10-
k (5-
Similarly, it holds that
gm 2 |r - 19m. Imm.l 1 - Iim. J
Im
2 k (=-(--1/22 -1/2)
o(k (k=--=--112)
(F.13)
Comparing Eq. (F.12) and Eq. (F.13), we successfully validate Eq. (F.11) holds, and consequently 6** CO.
We complete our proof weak alignment by analyzing the inner product between Im and 0 and the norm of Um respectively. Since 10 ml Z 1-1/2, we have that
(Tl + k 1/2 10" ml + 64)"* -1 A (Hllal + k 1/2 100ml mlI++ 1 k=)=
Impml 2 k 110-11 10% -"-1
For the inner product, we apply Proposition F.5 for á and each j E 6** and get that
Jm..j 0j 03² k 11)/22 10% | sign((
(m + 19m. Jm.al 1im.s Im..l) 103
(F.14)
Since 6x' C Φ1 can lower bound the summation of the leading term
Σ 0r2 k: -s-- 11/2 |0=1
Σ 07² ----==1-1)) 11/2 |0 1-
jE
jE
k (8" 11/2
10 10" 1 -1
k 10t11
2 k 1s" 1)/2
| -s
(F.15)
where the last line holds by the definition of Eo.; C Eg. For the term associated with Rm, we have by the characterization in Proposition F.5 that
Σ je
Rmss 1871 S (I * log(k))* + -
Σ 1811
JE8
+ -= log(k))* k 11/2.
1051 1051 1031 (k/d)215tm))
jE
+ k (6=++)
Σ 1871.
jE
51

---

Published as a conference paper at ICLR 2025
Applying the Cauchy-Schwand inequality, we have that
Σ jEdı
1091- (1031 + (k/d) <
10133112.
+ /0
+1++1/89112
jE(d
SE
O1).
(F.16)
And therefore
Σ Rmmll 1071 S k k- log(k)* +k=s' + 18" +1/2)).
(F.17)
jE
For the rest of the error terms, we have by Eq. (F.6) and Eq. (F.5) that
Σ
(19m3
Im. + I9m, (mm.i))
1091 S
1091
k (s"
(Aog(A) -3/2
jE
jE
- I k (s log(k) 3/2.
(F.18)
Combining Eq. (F.14), Eq. (F.15), Eq. (F.17) and Eq. (F.18), we have that
(@m. 0*) 2 k- --- -1)/2 10 |s" olk (6" -1))
For the norm, we already have in Eq. (F.8) that
| 1 S k (- 1)/2 |0 (+' - o (6--
Combining last two inequalities, we concludes that
(Pás Iin 0*)
A | o(k: (0" -1)/2)
(0- O(),,
P Imll
1/2 given that 10% 2 &g 1//2 for some constant of >
0. This concludes the proof of weak alignment.
Strong Alignment. Starting from the second step, we have by Algorithm that the neurons share the same weight parameter. Let 0 be the weight parameter in any step after the first step and we suppose that p = (0, 8*) = @().. From Proposition F.5, we see that now the choice of the gradient should not change the quality of the gradient significantly, as r|pl > k 1-1/2 m for any m E [d]. Therefore, we start by analyzing the alignment increment using any Jm. This alteration does not affect the alignment increment, but substantially simplifies the analysis.
We additionally define support o² {j E [4] 1051 2 kー }1. In the following, fix an arbitrary m [d]. We begin with analyzing the magnitude of gm.ij for at \ {m). Since lpl = 22)), holds that
(dippl + + 11/2 10%1l + k 10.- ~ (rlel + --12 10tl + k 2)= -2, (>le)) ~ h (0- -1//2
With triangle inequality, Proposition F.5 indicates that, for j E Φt:
I0mol 2 Mm - 10mj - Imol - 10ml Im.jl
2 -- (0" -1)/2 10/] - k== 12.0,11 1071
- k- (5 +1)/2 (10,1 + (k/d)² (imm)//2 -ō:: -6
Similarly, we have for j $ 8² that
19mma < |mmll + I Gm.jl + 1imj gm.il
Sk-10" - (10,1 + (t/d)/10=///22) + Ö(k 10" -1/2)).
Comparing last two inequalities, we have that 0,1 > - implies that [9mpl 2 maxj 19m5l for sufficiently large h and therefore
min 1gm. jEa
max 19m.p
jd
52

---

Published as a conference paper at ICLR 2025
which means that Øt C Φm Topx((mm) Thereby, have
Σ
1031 2 1 -
Σ JEØT
1011
11-k
jebm
We then move on to the alignment analysis. Retreat Eq. (F:23), we define
3m MELL), ,0, Egls.- (v) x (y]] v Eü,.. (.. 0*)a* -11
sign(p) [( even) (7|p1))*~1
Tm.(Pp Le 0" 0) = Er., 199m e Then follows from Proposition F.5 that whenever |p| (21), we have that B. > 0 and
- 03
(7(pp))*=1 sign(p))( 1/ oven) Bm
(F.19)
Bm V 9m
< B
|mml S m.j
b m.
where
r m. S Cok Cok- (10g1 + (k/d) /
I mj I C. 1851 (7)pp))*
(F.20)
with some global positive constant B, C. and Co. whenever the designated parameters are compatible with the definition of our nice event. With this representation, can deduce by Eq. (F.6) and Eq. (F.5) that
Egm
Im Cg) 23)-03. 03| + Σ
((gmm eÿ) (gm. e2) 19m eạ) (mm. eg)l) 1831
jE
jEØm
Σ Tmm ez) 071 - Σ
1071 O(k 16-2) ((k-(60-1/2)
llog"" 33/2 -3/2 k.)
j.
SE6
2 Bm (rle)) =1,
Σ
10312
Σ
|mol 1031 - 10( O(k--6'' (0' llg 3/2 k))
jEăm..
SE6
2 (8m (7/pp)e''
Co. (Tlp)))))
Σ
101 -Co
log
3/2 k).
jE
(F21))
where the last inequality holds by Eq. (F.16). To complete the analysis, we need an upper bound for ll l12. Note that by the triangle inequality and Eq. (F.19), have that
||
|| 9mll + [|P om Im -P
6m Iml IIP om
Im
Po
9mll
< [1 (71p)))0- Ps 0r1 + ||P rmll + [|p r
+ 0(: -1- log 3/22 k),
where rm = (Fm,1,..... am) E Rd and ri = (Im,1,.... r mm,a) E Rdd To proceed, note that by Eq. (F.20) and Eq. (FE6,, we have that
Par ll
C. Cak- +1111) (110112 V1+
3C,k 3
1/2
P b ll S Cn. (7ll))*
Putting these upper bounds together, we have that P3gmllz 1l I (Bm
Σ 18)12) 1/2
j.
+ 3C.kk +3,,k-(''+ (#'+1)/2 + +O -01--00-11 -1---)
loog
3/2 R))
(F.22)
53

---

Published as a conference paper at ICLR 2025
Note that for any 01 A 0g >
b >> 0, it holds that
0 b (al b) (a2 b)
a3 b² 2 (a1/a2- b/a2) (1- b/az).
a2 +
Setting A = - + k 1ss 11/22 log
3/2 k V k- = - =o(), we get by combining Eq. (F.21) and
Eq. (F.22) that
(3m - Cb. -lp)) (Ijeâm 0/2)
-3C 1o O 11-2 -0 llog 3/2 1t)
Gm. 0-)
9mm
(pm -bol) (Iςeōm 073)
1/2
+ +Co. k- + O(K O(k--(0--1)) 10121)/2 llog"" 3/2 k)
2 (1-O(A)))) (1
11 ylpp
0/2)1/2-000
jEØm
21-C-
where the last line holds because (1 Ck Ck-ly 2 rC -- for any C,r r > and sufficiently
large k. Note that k- = O(4), we see that
(mm 0*) 11 ||
2 0(A)
This concludes the proof Theorem 5.1.
F.4 PROOF OF THE KEY RESULTS
Proof of Proposition F:5, First, by Lemma H.2, we have for each j E [d] that
V 1
(mm = Σ Bol((()) (1)1
1m,, (0)0 (Wmm):e)) eg)
L
$2
Σ BxlCo()) -2-1
(m,,1 1, 0- ,0)))))-
L
= EElls SSa (v) -1))l
8*
(mm, 0-100=11 10-0 ,00,,z))
1=1
+ R1 - R2,
(F.23)
where the remainders R1, R2 are defined as
1
R1 = Σ (2((++1())
- [x)]
1
Wm,1 0-)0 (0*,,,)) ez);
L
$2
Ro
Σ Eg(ca +441 (w)
+ I
(wm,), 02-0 (wm,,
L
We also denote the leading signal term
5 5= (y) C.- (v)
(wm.1. -1. (00,e)))
By definition R1 collects the higher order term that aligns with the signal and the R2 collects all the terms in the expected gradient that are parallel to Wm,1- In comparison to the non- case, here we analyzing the gradient porddintte-wiseffe Therefore, Rú and R2 need to be controlled separately.
54

---

Published as a conference paper at ICLR 2025
Analysis for the dominant term S in Eq. (F:23.. We first define
Wm. Wm.! 1 sup((m,, eg)l S sc).
By definition of i, we have that I, E [4] are independent to each other and Um,1 Wm, on event (E). We can approximate the expectation of the (Wm,,1 0*) as
E. [10m, 00)0m)0000'0-- 0-)0--11
Bew,, [(wm, 00)mm,00'''"0 0-) sup (5m (mml)
Ew 00)
0- Pr sup ((),
= Eum,, [W 0r)s" -1 = (c)
Here the last line holds because Em (e) Urfsup, (5m,,, ej²l > e). For the first term, holds by Proposition F.4, we have that on E0,s* 11---11- -1 1fs- even)
7p- (all) k 1/ + k 85 52-2 if s* even; (rlpp k- 1/2 + k 1
Eu WW 07) 01 1
s* odd.
For the second moment that is involved in the Bernstein's 's inequality, we have that on 00
E [[ 00220" = E (um,) 0- (sup/ e₁)l e}
E (wm,l. 07) 0²)20"-1
= (rlpp - k 1-122 00:l1 + + 12g 20
To proceed, we have by Bernstein's 's inequality (Lemma J.1) that there exists an event E,,11 with Pr(Em,11 2 1 O(d- And it holds on E1 n E that
+/
1
Σ Wm., 0-
+ Σ (wm.. 0'30"~1
Beem, ( 1
11 + E,
where the error term E. can be bounded by
log(d)
- e5' log(d)
E < (7lpl + k- 1--1/1107 + - 82s
+
Pr (Eth (c)).
L
Moreover, the assumption that
L log d (R2 (e"-11,x*))
Pr(Em((()) Sk-
allows us to simplify the upper bound for E, since
E S k-1 (rlpl + 11/2 0% + k 1-1 1200 )0-²1 + 4 10-
(F.24)
In conclusion, we have E n Em (e) that
S (Ew... [wmm. 8 -1 11 (8* es))
We remain this form for further simplification.
Analysis for the first remainder R₁ in Eq. (F.23., For any s', it holds by the property of likelihood ratio decomposition that
(glls(())
G.)ll) s Ev(5 (2))))
Σ
(ol
<
<20
55

---

Published as a conference paper at ICLR 2025
and the last quantity is constant that is independent to s, s'. To bound the summation for 2 8* have on by Lemma F.3 that (2m,, 8*) $ rppl+ 6 1/2 on
v
(Wm.1. 0''0
Σ Vs+1+ 1.
(wm,, 0-)1"
2
$2
#2**
b S
(mm,l
0-11""
(F.25)
Now it reduces bound the right-hand side of Eq. (F.25). Note that on &m (c), Wm.l = Wm..t We can first track the first and second moment of (Wm,1: 0*) as
B 1, 001 S Ee (K 1-)
S Ew.. | [Wmml 0- 25 11/2.
To bound the last quantity, we see that given E0, Proposition F.4 reads
E (m 2-) S (r/ppl + k 1/2 m + - + 5+)22²
By Bernstein's inequality, there exists event 1,,12 with Pr(Em,12) 2 1 - Old 0,322 such that
Em,12 O Em (c), it holds that
L 00m, $ (1+ V logd)
(rlpl + 1/100 14)=" + c" log(d)
L
L
Given that L 2 log(d) (k v (6" k²))) )), it further holds that
T. Σ 00) (clel + k 1-1 10m ==+))= + =
In conclusion, holds on E,,12 O Em (c) that
Rí (7lll + k- 1/2 + k 1=-1 + x==))) + 1(0", ez)l-
Analysis for the second remainder R2 in Eq. (F.23). Similar Eq. (F:25), we can first upper bound R2 as
R2 < L
(wm,. 00)1"
1=1
Σ
(
((mmare)))
where the last line holds by the definition of &m (c). We decouple the product with the Stuchy-Sehwan inequality follows:
Bi... Wl 0')'"" 160m, ez)il Ew... Wm 0')|=" 1Kw,,t
E (l..ll 0*) p2' |20"11/ E [K 22//211/2
The first term in the upper bound can tackled with Proposition F.4. For the second term, we have that
E Eum (W e,) S B[((Em.d 03) + (0, e1
S B((Em.i e] + 720
-20 Ei1 (j E pmm) s2nt5
2 223 + -1 (kk/d) (k/d)
56

---

Published as a conference paper at ICLR 2025
Here, the first line holds because 178 Ell2 1/2. The last line holds by applying Lemma 1.5 and that PP[ E 6m.)) I k/d for J # m. Note that each term in the summation of bounded by e log(()) up to constant on (m(E). (E). We have by Bernstein's 's inequality (Lemma J.1) that, there exists event 1m,13 with Pr(Em,1s) 2 - Old And holds on &m, O (c) that
log(d) L
(rlel + k- 1/210/m + )++) (710,) - (=12(//0)454mm11))
Ral
1 +
log(d)
Given that
L. 2 log(d) (KV (6 (c 1))
we conclude that it holds on 13,13 n (t(e) (t) that
R2 (7 711 x k 5+)
(7100) + 11/2/21//d (tt/d)mimmm/m/) + + -0(++11
Summary of first-order moment. We now merge previous results to summarize the results for the first-order moment. Note that it is sufficient set
L = 2
- log(d) (& e log k)) +1)
Define the final event as E,, E,,11 11 n E,, O Em, which is {wmshe[L) measurable. By previous analysis, it holds on this event that
S= 03 (71) even) (7/pl + A: 1--1/110t 1:1111 1--18--1-14-- oven)) -0-n))"-1111(= even) + 03 F; 16'
R1 - ((71l) + k-1/2 18.1 + k 15+) ) + k =-* -1871:
R₂ H (aløl + k -=1/210%,1 + k 1+)
(7/0,1 + 11/2. -k:/d) + + -=0++11)
Following the error term E Eq. (F.24), we define R= Rı + Rs + E. which be bounded by d
R S k v (y/e) + + 1- (mlpl + -12 1//2/81 0 + k )- - + + 1871
+ (> h k 84) (7118) 1 1/2 (4#m)) + +k (1)
(F226)
And we summarize the first moment on Em, 0 (c) as
Erg. (Tm,, eg)l 03- (Tp) (s (rlll + k- 1 10 + 1-1 6--16----1(6 ((s even) )² 8' 11
+ R.
where upper bounded in Eq. (F.26).
Proof of Proposition F.6. Similar the proof of Proposition E.4, the proof of this proposition com- prises two parts. To begin with, we calculate the variance of each coordinate of gm.
Second moment calculation. It suffices to consider the variance of the first sample. To this end, we define
1
(1b(11 (Wm.i, 21)) 21 - -Zi(v)) wm.).
Im.11
7.
1=1
57

---

Published as a conference paper at ICLR 2025
For any fei, (ei,e2..... ................................ ea,.,,,,.,ell
it holds by the definition of 9m,1 that
Ep,, 11m,, 1
1
Ep. (v, (wi, 2)) (wr, 22,
u}
+
Ep.
[wi(w) (w) 2) (oor w)]
1
1,5
1,1=1
1
Ee (v, (w), 2)) (wy (2)
(1+
Σ
(1 2))
L
#2**
Be [bb(us (mm,))))(0 (wn, 2)),,
Σ
Belvi (1) u) (wr, v)
1.2
1 + T
Balia (wn,
(F:27)
In the same manner as the non-sparse case, we can derive O(/L)) upper bound for the second and the last summation, which traverse through all I = L'. Recalling Eq. Lemma F.3, we already have that
sup (wm e₁)l 7
1
sup (wm,t, 0*) S r|p| +
sup
(w (Wm, Wm, S --2 + e log(k)) 1+1
To incorporate with the notations in Lemma H.3, we denote the upper bounds the (Wm,t e2), (Wm,i, 0*) and (Wmd, wm,p) (1 (') as
4 +
+ == + 2 log(k))
respectively. By the virtue of Lemma H.3, the desired expectation is behaving nicely if the ratio (2 v ////2 (2 is constant term. To validate this fact, we note that
c +2 log(k))
& = 722 +
62
72
62 g2 + log(A)
Since & 1 & 1og(k))// we conclude that o v / S 1 for sufficiently large k. Therefore, we have by Lemma H.3 that
Σ Te (en (Wm,1; 21)) (yn,, (Wm,v, 21)) (21, u)2 u)1, (1 Σ (()))(((0,))))) Se
1
On the other hand, we have for the third term in Eq. (F:27) that
Σ Eolvi v) (Wm,rr 1) S sup (( 1fs 1fs" 2
1
6 11s <
62 1fs <2)
where the first line holds by Lemma F.3. In summary, we have on the event Ey, (E) Em that
sup n Varr,- lg wt1 S o -1 ce
1
(lg(k)))** 2 + L'
-1 1
Concentration. We now turn validate the condition of Lemma J.3. For any {e ..,..., ea}. we set G(2,8) y, w) = [10 (w, 2)) (z, w¹ 1 100 (v) (w, v)) with the domain measure defined as
dPp, (21, 31) x dp(w), where dp(w) I- E, Summ.er the integral Minkowski's inequality implies
58

---

Published as a conference paper at ICLR 2025
that
(ddFa (utt://)) 1/r
Er 11 1)17"
$ dulw)) (dtto)(//Ao...::))))0a0a 1/r
1 Σ Eg,, [W (Wm.1, 2)) (2,, 0) 17 + 1
Σ (Wm,d: u)]. (F.28)
To proceed, we leverage Cauchy-Schwarz inequality to decouple the average of the product in the first term, which reads
L E [1b (Wm,1, 2;)) Rp. (1(s, b) 2))2111/22
Ep (1vi(1 (Wm,), 2:)) (zi, 1/ & L 1=1
1=1
Similar to the proof of Proposition E.4, have that
P(z, 2 21/2 Q(x, y)
Ep.- (y, (Wm,12,) )) I B2lUG0 w....)
Eg Eel((,, ,,
where the first inequality exactly repeats Eq. (E. and the second inequality holds by Assump- tion (c)(c). On the other hand, we have that Ep,, [2, 2)2r11/2r I //2 Since the second term in Eq. (F.28) is bounded by O(1), we conclude that
Ep,- 11 "//")//- S 1/11/2
Thus, Lemma J.3 implies that there exists {=,, yi JE(N) ((n -easurable event 6,, with probability least 1 O(d /T) on which for any v E (61, C2 ..... ea), it holds that
Ep.- Kgm, 1) (77()++17)
log(d log (Tddd"++nn) Cp+1/2 Cr
(gm, v) Eso. (9m,, /S
((>2 + e² log(k))) 8' --1) log(d)
log (og(d)C.+3/)
n
given that T, n are at most polynomial rate in d. Since we assume that n= n= ((>2 -(((((2 + e² log(k)))* -- -1 log(d)2C,t2)
the above inequality be further simplified as
((>2 + log(k)) 8* + 1-1) log(d)
Kgm, - EE,, Kimms S
Additionally, Em, is the desired event. This concludes the proof of Proposition F.6.
F.5 PROOFS FOR TECHNICAL RESULTS IN THE SPARSE CASE
Proof of Lemma F.l. With slighly abuse of notation, we assume that 0* ~ Unif(S*-1). We first consider the event E0, = {|]0*| S C. k 1/2 log(k) From the proof of Lemma J.6, we see that
P( 2) 2k P( 2 < 24 (xp(-k//p/p0pceee 2k exp(-t2kk44)
Take t C k- 1/2 log we have that the failure probability is upper bounded by 2k exp( (-111-k + 1
For the r-norm, we leverage the property that 0* //| where AO Tt). Now, | Eis, Z7, where Z E| 2 -1. Applying one-sided Bernstein's 's inequality with failure probability Ro, have that
| < le + H+v22 2ook log(k) + lo3(k)/3.
59

---

Published as a conference paper at ICLR 2025
On the other hand, note that we have for 01 >> 2 that
max k
2 v 2c, log k) - 21 v 201 log
I <eep((-clog]) k2-a1
To apply Bernstein's 's inequality, we note that
2| 1[ 20, log k}] - E1 2r/1/ B122,- . < /2c, log k}] < E1|
where |0 (2r- 1)!!. Therefore, it holds by truncated Bernstein's inequality that P( ([1Z||>> > (I: + 2egk log()))
|-]// + (V2C'log(A)) " 02 log(3)/3) s k k + 0
Combining the two bounds, we conclude that with probability 1 Ok: -coVeeev)))))) it holds that | IF - : h + Vk k + (log k) 1
E (k + oolog& k + log k) k k1-1/2
with probability at least - O ()) for some constant c <> O.
We now move on to consider the event Eo.s = Eiigk 1 1(10 2 1/v2k] 2 k/43. First, it holds by the Hoeffding's 's inequality that
kp
Σ 11 21/21 kpl S k
2
1
k))
2
where p P(Z 2 3/4) > 0.5. Denote above event as Ar. On the other hand, we have by the
Bernstein's 's inequality that
P(1
Σ 2 11/2) 2 1 - 2-xxxp((k/33)
iSk
Denote above event as A2. Then the event A A2, have that
21
Σ
Σ
2
2
7
2k
2h
isk
K
A
2
Σ
1[
)
K
kp
Σ
k/4.
2
In conclusion we have that P(H |0:] > 1/ 1/v2kJ|| some constant C3 >> 0.
k/4) > P(A, Ab) 2 expp(-cak) for
Proof of Lemma F.3. Clearly, it holds that
||>0 + Em,rl2 l2 2 ||Em,112 - |lEm,ela 2 1/2.
Bu substituting this lower bound for the denominator, we have for any j. I that
(Wm,, es>l < 2(>|0,1 + ((mm.,
< 2(710,1 +c).
The last line holds by the definition of E,, (c). On the other hand, we have for any that (10m, 8*>1 < 2(Tlp) +
Σ
Em.r
0] 1 [j E Φ² n (m,)))
jEld
< 2ylpp + 2(
Σ
22
j E 0= n )mm.))) 1/2
(E03²
032 iij E 0e (mmm))) 1/2
< 2ylp + ssu Em.lsl 110 10t n Amall
60

---

Published as a conference paper at ICLR 2025
To proceed, note that the event Em n& (c), it holds that [ø* S log is and that sup, Emdd S Since we assume that 1601 I 1/ log k, it holds that
[wm, 1: 0*) - 2(7lp) + c).
Now we turn to consider the correlation between Wm., and Wm.!'
[ Wm,r) p)) s 2 27
Σ Emiil (mmlyy 1{j @m, O @m,y
Σ 10,1 1mmasl 1ij E Om, u (U)
Σ 10 -iii E &mr ssupp())))
For the second term, we have with definition of (e) that
Σ kmadl (5m I(j Om, O 2m,r } S max
Emdds 12 P0ma O pm.rl
3,1
S So2logh
For the third term, applying the Cauchy-Schwann inequality, we have that
Σ 10 jm {j E Am, O 1mmrr _ >|00|22 e evlog k =S 7² + e² 2olog k.
Putting them together, have that
KWm, "mm.),WW.... S 4(7² + log k).
This concludes the proof of Lemma F.3.
Proof of Proposition F.4. For conciseness, momentarily drop the subscript m, in the following analysis. Conditioning on fixed Φ, we have that
Bu kw,, 0- E. [l 1 = (7(0, 0*) + [5)
E& En [170 Ell=" (7p (g. PaOT)) [o]]-
(F.29)
Given the polarization level y = o(1), we see that || + Ell 1 ((). and it suffices to evaluate E.. [(Tp+ (S, Pa [o). Without loss of generality, assume that 1 E a and we can translate characterize the
Pat" into the first coordinate by the isotropy of over (d). To this end, first term as follows:
[7p + (E. Pat"))" [0 =E =E((pp (E, PPO0 (1)))
(1p)
| 11 [ o) 1r even]
r
[x/2]
/2|s/21
(11))
1 11000113" -- (7p) ((xadd)
2r
0=0
(1p) 11+ odd)
((>p 1: 1/2 11/2 |11/21 + (xp 1-1/2| l1 (le/2))
~ (1p) (s add)
(ripl + k - 12) 2L+/2]
(F.30)
Here, (i) holds by applying Lemma 1.5 and ~ denotes the equality that is up to a s-dependent multiplicative constant.
Putting together Eq. (F:29) and (F.30), we conclude that
Eu kw, 8*)* [0] (1p) 1 (ddd (xlel + k 1121 112) 1102)) odd)
(F.11)
61

---

Published as a conference paper at ICLR 2025
In the sequel, consider averaging over Φ. From Eq. (F.11, see that it suffices to consider [p[[[ppp]] + 1-1/2|| PaO' 1 for some 2 2. We alter the notation to facilitate some deferred calculation. Consider m C [d] with constant size i = 0(1) that does not scale with A or d. Now define 6m
Sn, J. where Sg.m = {S [d] |S| = k, m C S}. It is easily seen that this definition covers previous definition of Sk.m by setting m = {m].. We characterize the magnitude of Egm. [|| [|I. P... [1]] from both sides as follows. For the lower bound, we have that
Bom [0 P 0* 12
Esm
(110
12
+
10 2
2
4m)) //2)
jmm
ESm
11
+
0 l' iíj E pml)
m
jmm
@ (1
k d
k/d)
110 I1F +
110
(1)
k
110 II:
+
d
k² r/1 110 110'1///
h2
1 I1.
k-1/2
d
Here (i) holds by the fact that E[ E 0mH H = k/d for j & m. and (ii) is a consequence of Jensen's s
inequality. For the upper bound, we have that
E P Bom [110:1 11 +
10312
1ij E vml) ) 1/2
jmm
1071. M E @md ) )79
Bdd
|10
+
Σ Jm
Kem nod [(mm
nonzero summands
Jensen
|1 + Egg. [10m n (²)) m 1/2-1
Σ
1091" E
E 0ml)) (F:32)
jmm
Next, we apply Cauchy-Schweee -Shhwaz inequality as follows:
(F.32) ||0 |F + Em
Σ
0-1"
1ij
Φm) 1(0m
no*) \ m /2-11
j
110m (gn")) ml mmm""? 1/2
S |10 + Edw.
107|2
iij E dmb
Emg Σ
1 E dm
jmm
j4m
-10t
IFF + Σ
10312r)
1/2
Emp [00m n mm 1m|--11/// 1/2
jmm
(8)
1/2
2
(r-1)/2
110m I|- + (o) r-rr)
d
2²
|10 + d
k 1112
where (i) holds by E0,er and Lemma J.7. In conclusion, we have that Es P(O01 ~ 110
--//2. 8 given that lo ol o(Vd). Combining this result with Eq. (F.31), we obtain that [w, 0- ~ (7p)² odd) (rlll k- k=1/210 + k 10/1 (ssddd))) - where 8 k2/d o(1) and 6, 51/r.
G STATISTICAL QUERY LOWER BOUND FOR SPARSE SIGNAL RECOVERY
In this section, provide a * sample complexity lower bound for the single index model with k-sparse signal when querying a VSTÄT oracle. The statistical query (SQ) framework was developed in Feldman et al. (2017) and for completeness, we present essential definition and results here.
62

---

Published as a conference paper at ICLR 2025
Definition G.1 (VSTAT Oracle). Let D" be the input distribution over domain X. For sample size
parameter n > VSTAT(D", n. oracle is the oracle that for any query function h X - [0. 1],
returns a value E 1p- T, + where p = E [h(x]] and T max(t vp(1~11111 (o(1-p)/m p)/n}.
To define a key concept statistical query dimension, we first introduce the following notation.
Definition G.2 (Relative Pairwise Correlation). Given two distributions D1, D2 A(X) and reference distribution E A(X),
Dí(a) D2(x) ((x) D(x)
Xn(Di, D2) = EnnD
-1
Definition G.3 (Statistical Dimension). For > 0, E (0, 1), domain X, a set of distributions D X, the statistical dimension SDA(D, of with average correlation and solution bound vj is defined as the largest value m' such that there exists a reference distribution E (X) and a finite set of distributions DD DD which can depend on the reference D with the following property: for any solution D* E 'D,
(i) (DD (D"H 2 1011-100 1))Dpl:
(ii) for any subset D C ED (D*) such that (D'l 2 (DD (D*H//m
Σ IPb Dr,DEED,
XD Dj) 57.
The above definition of the statistical dimension is speical case of the original Definition 3.1 in Feldman al. (2017) where we consider search problem of exact recovery of the ground truth D Definition G.4 ((7, -)coorelat Distributions). We say that set of distributions D (Di,.. D over X is (7,, (1,8))-crredd -oorrllate relative to reference distribution D E A(X) if:
{3 for =j E [m] {
XD(D,,
for j E [m).
The following lemma borrowed from Lemma 3.10 of Feldman al. (2017) provides lower bound on the statistical dimension terms of the (7, (7.3)-correlatioo property of the set of candidate distributions.
Lemma G.5. Given a set of candidate distributions that are (7/, correllttt with respect reference distribution D, then for any of 0 and |D]-
( 1)7'
SDA(D,
8 P-7
The main result in the SQ framework is the following statement that relates the number of queries required to the statistical dimension, which is borrowed from Theorem 3.2 of Feldman et al. (2017).
Lemma G.6. Let X be a domain and D be a set of candidate distributions over X. For any 7 > 0 and 1) (0, 1), Any randomized SQ algorithm that solves the problem of finding the imput distribution D* E 'D with probability at least or >> 1) requires at least (a - n)/ -n) :) SDA(DD; F, 1) calls to the VSTAT(D* (35)-1) oracle.
Our strategy for proving the lower bound is to first construct set of candidate distributions D that are (w(k-)) -correlatd with respect to reference distribution Q with 8 (P Q) and [D] exponentially large. Then by Lemma G.5 and Lemma G.6, we can derive the desired hardness result. remains to construct the set of candidate distributions that are (w 1))-1)))))-000) -coreelate with respect to Q. To this end, we introduce the following result on the packing number of k-sparse vectors.
Lemma G.7 (Packing Number for k-Sparse Vectors). Define plu, v) (u,,)) Let packing number M, k t) he the maximal cardinality of the set of k-sparse vectors in such that p(u, v) < for any o in the set. We have for any E (1/k, 1) that
min {(d k))1 3kt}
Mpld,k,t 2 exp
8
63

---

Published as a conference paper at ICLR 2025
With all these ingredients in place, are ready to prove the main theorem.
Proof of Theorem 5.4. Let us pick parameter Ka E ((log d)?, k/44) that scales with d and set
Kd t max (V d 3k
Rdd
E (1/k,
(G.1)
Note that / E (1/k; is able to hold by our choice of and condition that (log d)²) < k < d/2. In this vein, we can pick DD
the maximal set of distributions Po for some k-sparse vectors 0 E gd-1 satisfying p(O, 0*) < t. for any 0 + l' in the set. It follows from plugging (G.1) into Lemma G.7 that [D] N exp(Ka /2, which super polynomially large for our choice of Rd.
Next, we configure the remaining parameters in Lemma G.5 and Lemma G.6. We choose the reference distribution to be Q, which the covariate is independent of the output y. For B, we note that
Xo o, o Po) (TP Q O(1),
which is a constant independent of due to the rotational invariance of the likelihood ratio with respect 0. Thus, we define this quantity as B can just set 3 xxa(Po || [[Q
B. For 7, we note
that for any two Po, Po. in D for O + 8',
Po(x) (x) -1
(To, Po.) = B
((x)
(z)
(1+ I+ Σ ((w))o((0)2))) (1+ E (o)t (((())))(10 .2))
= BanQ
$2
222x*
Bolsa(v) 10,00' S Σ (v t S Eelss ts + 4at
s' the cross term (((,,((8,2)) ((0', 2)){ is non-zero. In particular, by the property of the Gaussian noise opera- tor introduced in (B.3), we have that Eg ((, 2)) 2)}] 8*)a < t For the last inequality above, we simply use the fact that ()) S 1 for any (Damian et al., 2024) and t < 1. Now, we conclude that
Here, the third equality follows from the fact that only when
t 1-)) t"" s (Ealso (v)
(x)( S Ealss- (x)
We thus set set = --= (U) + 1) -5= O ). Finally, we set 1) 1/3 and a 2/3. Then all the conditions in both Lemma G.5 and Lemma 6.6 are satisfied and we have
(A,(D,,,144 2 ( 1) DDy 7 (exp(na/8)
3 7 2 23
43
Lastly, recall that we have (0,00)) < L. for any 0' in D, which means that in order achieve alignment at least 2/ with the true signal 0*, we need to exactly identify the distribution Py-. Con- sequently, by Lemma G.6, we have that any randomized SQ algorithm that solves the problem of achieving alignment 2t with probability at least 3 requires at least 7 exp(Ka (8)/ calls to the VSTAT((Po (67) oracle.
Simplification of the lower bound. To simplify the lower bound, let us take (log d) /2 for some constant >>> 2. Thus, the alignment 2t upper bounded by
[6k ((d-1/2)
if Vd if Vi.
21 <
where (3-)) hides some poly-logari factors. The number of queries is still super polynomially large in d. Following from (G. we can safely set
(logd) d/ (log d
if (log < < /d(log d)
if / /d(log d/e < l < d/2
64

---

Published as a conference paper at ICLR 2025
Hence, the number of sample
k (log dje d" 6(log djss 72 6
if (log d)2 < < Vdllogd)
(6y) 11
/ d(log d) S d/2
Hence, we have established the desired lower bound on the sample complexity.
Remark G.8 (Difference between CSQ and SQ lower bound), The following a comparison between SQ lower bound and the CSQ lower bound in Vural & Erdogdu (2024):
Difference: CSQ is constrained to operate on a specific set of functions, whereas SQ is not. In this sense, CSQ creates a large family of functions with small average correlation, while SQ constructs a large covering net over the support of 0 as a hard instance, allowing for arbitrary query forms.
Similarity: Both methods rely on Bernstein concentration inequalities on the correla- tion level for two random sparse vectors. This leads to the critical correlation threshold max / /d, 1/k), where d is the dimensionality and k is the sparsity level.
G.1 PROOF OF TECHNICAL LEMMAS FOR SQ LOWER BOUND
Proof of Lemma G.7. We use the probability method to prove the existence of set of k-sparse vectors Sd-1 with the desired property. We i.d. sample m vectors w()), (m) from the following distribution:
w.p. 1 j
Vk JE
Φ Φ~ Unif(S:),, wy =
w.p. i jeld
0,
j
where we recall that Sg is the set of all size-k subsets in [d]. Since each (1) is i.i.d. sampled, we can equivalently view (1) ( for i + random variable sampled from the following distribution:
(w) wh)) d Rx where r1; T2, tributed as
where
rx, X Hypergeometric(d. k, k), (G.2)
k
are i..dd Rademacher random variables. Let us consider random variable W dis-
W d Ry k where = +ry Y ~ Binomial kk d
h: ).)
ddkk)
(G.3)
We will invoke the following fact on the tail probability regarding the above two random variables.
Proposition G.9. For Rx and Ry defined (G.2) and (G.3), respectively, we have that P Rxx 2
< (Py 2 t) for any t 1.
The proof of the proposition is deferred the end of the proof. Thus, it suffices to study the tail probability of W. Note that W d
Σj= Wy where wy i.i.d. sampled from
Bj n w.p.
2 w.p.
w.p.
j [k].
0,
d=k
where E[wy] and Biw3l (k(d k))-- Hence, we can apply the Bernstein inequality obtain that for any 1/k:
k(t/k)2/2
(P((w() w()) 2) < 2P(W 2 < exxp
(k(d k))-1 1/(3222
1.22
(d - k))1
3k1 1
= 2exp
S 2exp
(miin
min
}
21 (d
k)
2kt/3
4
65

---

Published as a conference paper at ICLR 2025
Suppose randomly sample i.idd w( from the same distribution. Then the probability that all such pair (w0 ا(اسسس < & for 1. >> 1/k is lower bounded by
F((WW0, t, vi + 5) 2 - m² 2P((( ,00)
2t)
(d
k]t
3kt
2 1 - 4m exp
min
4
4
Ensuring that the probability is nonzero will give us a valid construction of the set D. Therefore, there must exist a D satisfying (w)()) ((ا
< for any + j and with size
min (d k))² 3kst
D
exp
8
Hence, complete the proof.
Next, we aim to present the proof of Proposition G.9. To proceed, let us introduce the definition of stochastic dominance.
Definition G.10 (Stochastic Dominance). For any real-valued random variable X and Y, we say that X is stochastically dominated by Y, denoted by X S Y, if 2 P(Y 2 for every t.
s.t.
The following result from Theorem A, Chapter of Szekli (2012).
Proposition G.11. We have X S.t. S Y if and only if there exists a coupling (X, 8) with law(X)
law(X) and law( = laa(() such that X almost surely.
Proposition G.12 (Theorem 1.1, Klenke & Mattner (2010)). Hypergeometric (d, Binomial (/ A)).
Another way to think of the problem is that Hypergeometric(4.. k. k) corresponds to the number of times a black ball drawn when sampling for times from an urn with d white ball and & black ball without replacement, while Binomial(k;, k/ - k)) corresponds to sampling in the same urn but with replacement. We claim the following fact on the tail probability of sum of Rademacher random variables.
Proposition G.13 (Sum of Rademacher Random Variables). Let r1, P2,...... be i.i.d. Rademacher random variables. Let R₁ = 71 +... + TI for 1,2,.... Let pi()) ) be the probability mass function of B, Then the following holds for any 1 = 1,2.....
1. pt is symmetric and supported the of odd integers if l is odd, and supported on the set of even integers if even.
2. For i E supp(p)) and i 2 0, (i( is non-increasing function of
3. PP(R 2 t) P R242 for any t 1.
4. (PR 2 t) 2IP R for any >>
5. (PR 2 t) < 2P R 2 t) for any 2 1 and 222 1.
Proof of Proposition 13. The first claim immediate from the symmetry of the Rademacher random variables and the fact that the sum of an odd number of Rademacher random variables is odd, while the sum of an even number of Rademacher random variables is even. For the second claim, we note that
(i( 2- ( (1+00/2) i supp(pi),
1
which is a non conninnceg function for 2 0. For the third claim, we let = =[[t/2] if is even and ( 1)/21 + 1 if is odd. In other words, 1 min(r E supp(pi) 2 2). (..TThe Then have
66

---

Published as a conference paper at ICLR 2025
that
P(R1+2 21) P(R 2 PP( -()rP + 112 20)
-2)
+ + = 2)
F(R 2 ( + (P(1
=f ( - P( = =()) P(r141 + 11-2 = 2)
2 P(R 2 - 21.
where in the first equality we use the fact that rt+1 + 7142 supported on (-2.0,2) and in the second equality we use the symmetric property of the distribution of r1+1 + 7142. The last inequality follows from the monotonicity of the probability mass function of R& for the forth claim, we similarly have that
2 0 when t 1. For
P(R++1 2 P(R 2 (*) P(R: = (²) (1)-)P(()+)) -1) P P(R 2 1²)
- P(R 1).
The last claim follows from combination of the third and forth claims where
P(R 2 ((24221/21 2 P(R4a1//)22220
P 2 1).
Hence, the proof is complete.
Next, we proceed to the proof of Proposition G.9.
Proof of Proposition G.9. By Proposition G.12 and Proposition G.I there exists a coupling X, Y with (8) law(X) (X) and law(Y)= law(Y) such that X < y almost surely where X Hypergeomeerri((, k k) and Y Binomiall(: k/(d k)).
Consider i..dd Rademacher random variables r1, :........: Let R2 = = +.. + for = 1,2..... Since Rx = ri + + rx & & 2Binomial( 8, 1/2) L and Rg = ri + +... + +ry 1 -
2Binomial ( 1/2) L for the coupling (8,8) with X < ÿ, consider the conditional random variable
1 -1, w.p. 1/2
w.p. 1/2
Fx+i (R
-x
i= 1 -
The equality holds by the i.i.d. property of these Rademacher random variables. From the distributional perspective, the distribution of Rg. is obtained by conducting convolution with the Rademacher
distribution for --X X times on the distribution of Rx- Invoking Proposition G.13, we directly
conclude that P(Ry 2 2 9) 2 P(Rx 2 t f)2 for any > and Ý 2 X. As p 2 x
holds almost surely, by the law total probability, we arrive at the conclusion that P(Re 2 1) F(Rx 2 2 for any t 1.
H SUPPORTING LEMMAS ON MOMENT CALCULATIONS
Lemma H.1 (First moment). Under Assumption for any 2 0. it holds for any E R and Wi, 0 E S that
EzeNa [V(y, (w, 2))2 h(0 2))] = G. (v) (w, 2 + Vs (.-1(1) (w. = 18
in the L sense over the marginal distribution of under Q
Proof of Lemma H.l. For convenience, denote p == (w, 0*). We claim the following identities:
Eg (.l(.. ut 2)2 ha 2)]
EEnNia (o gr hh, 2)) 0* BynNs Vil,, T2)) h0 2)) Pp. (H.1)
= =EruNa w. 2)). T h-h,(00 hg
0" pw p²
+ EzaNa wT. 2) TT t [))
w p0
1 p²
67

---

Published as a conference paper at ICLR 2025
Here, in the first identity, we project in the direction of # and the orthogonal complement of 0*, where Pg- I 0-00 is the projection operator onto the orthogonal complement of 0*, To how ToTT) 2) hg (0* T0)TT) Po the second identity holds, we first look at the second term Benua [b w
For each direction orthogonal to both 0 and w, we have
Ra (V, w 2) ha(0"
Ez~Naaww (/W, h₂ 2) x 0. ( (
Also, by projection Pol is always orthogonal to 8". Thus, the only direction left for consideration is (w - /0")\ V p²: for which we have
Na (bly. wT 2) h0 2) (PoL2,
w p00
p0
ExnNa (o(. (0)T)
V1 - p2
V1 1 p²
= EEnNa (bl wT 2) ha 2) (w T)
p0* T
2)
W
p0
(H.2)
1 p²
Plugging Eq. (H.2) into the second term of line 2 in Eq. (H.I), we thus have the last identity in Eq. (H.1). Next, we analyze terms (I) and (II) in Eq. (H.1). For our convenience, we define U, as the Gaussian noise operator such that
U ()) Ew'n px v1- vI-
For term (I), we have by the definition of Up that
(I) E (U, x)) x ha(1))
E [Vs+I- Unbb(, x) (x) + vs.
hx)1
(2) Vs+1- (1) p² Vs V 1 p²-1.
(H.3)
where the second line follows from the recurrence relation of the Hermite polynomials in Eq. (B.1), and the last line follows from the property of the Gaussian noise operator in Eq. (B.3). Similarly for term (II), we have
(II) BErN UU, (V,,))))) hx())
(2) p" Exr2 (b(,,x) x) x (x))
12(0)) p² (
Vs (2-1
(H.4)
where in the last line we borrow the calculation in Eq. (H.3) by letting p = Plugging Eq. (H.3) and (H.4) into Eq. (H.1), we hence have
(H.1) 1000 (V++1 Foti(v) px + v . ( p²-1) 8r
p
-p0 + pp (Vs+I- -o- + Vo. S5 v5-1(1) (v)) Ø²
= v + E. (y) p'u V8 C.- (v) pp" p=-10-
which completes the proof.
An implication of the previous lemma is that
Ey(h,- ((0", , .)) o' 0(((2, 0)) (2, 0*) = - g0") ) (0000) 00-- v(s 1)(s + 2 ((0'+2) 10',0)" 04
where we take (*) the s-th normalized Hermite coefficient of a. Here, we take () o d((x) and thus (v) vs + T (++1).
68

---

Published as a conference paper at ICLR 2025
Lemma H.2 (Decomposition of first order moment). Suppose that follows Assumption 4.1 and
(Wive (wi, zi)) 2, Wh (y:)) wi).
nL
where (zt, Lid. Pa. and twi is fixed. Then it holds that
Vs
Eg,, [g] =
Σ
Byl(s(v) 3--1
(rr, 0- 10.00-000
#2
v +
Ee (v) v0+1(1)]
(un, 0*)0 wt.
Proof of Lemma H.2. Applying change of measure from Po- to and invoking Eq. (2.2), we get
EFg- [0]
Ep.. (b, (wr, z)) (y) w
(b (101, =))² (1+ Σ (olv) ,2)) - (w)) (v)
Ee
(H.S)
$2
Note that for have for the first term in the summation of Eq. (H.5) that
L
Eale(u (wi, 2]) = Ea [1))
wi.
which is cancelled out by the debiasing term in the algorithm. Applying the result of Lemma H.1 to the remaining terms in Eq. (H.5) yields
Ep,, [g] = (olss (++1(v)
wr, 0*)0 wi
L
$2
Σ Eg((x()) f-)1
(wi 0%)000)).... 0*
(H.6)
where the (olvi(0) 7, Ele term from Lemma H.l with = 0 is cancelled out by the debiasing
term in the algorithm.
Lemma H.3 (Second moment on nice event). Suppose sp x R + R satisfies the quadruple- integrable and high-pass assumptions in Assumption 4.1. Let 5* be the generative exponent defined in Definition 2.1. Suppose [v) < C. some universal C = =(1) and for all s 2 8". For any 0,80 U..UE E gd-1 where either v = 8 or (e, (0) = in the non-sparse case, and either u = e, for j E supp((*) or = eg for j & supp(0") in the sparse case, suppose that
w, w',0",
max{l<e, w)l. (v. w/) w/) I cu. max (8", w) w')l S.c. Kw,, w')lsa
for some e, Eo, e1 such that 4este < 1/2. Then, have s* that
Eq v'ys (w, 2)) (w/, , 2),
1+ Σ ((r))ho(10,
(1 1+
2
2 (
$ -1
[ E1
- c 0+)
(e.
2 24)
E
E1
El
and for s* the bound is (11) Here, S hides constants that only depend on s* Eglú(x y) and C.
69

---

Published as a conference paper at ICLR 2025
Proof. Using the results from Proposition I.I, we have that
h,(10" (,) = v(s - 2) + 1) (==)) & v02) + h (=)
(H.7)
2s h. (=))) 8 o|_ T_ (0) + vols - 1) h (2) 0 10, 1022)
Thus, we only need to focus on these degree terms in (y,, (w,, z)) (w', z)), Our goal is to compute the following quantity, which we denoted by F:
Σ (())))(((0)))))) 2)1) $=0"
F Eq (y. (w, 2) 2))((,))
1+
Ee [v, (w, =)) (w', ()) =)²]]
Ee (G. (w, My,, ()) 2) ()0r)
(H.8)
Here, for the term corresponding to s = 0 in Eq. (H.8), we plug in Eq. (H.7) and have by Lemma 1.3 that
Ie [v,,, (w,, (,, (w,, =)) =}
= Ec (u (w, (V) (w', 2)) h2 h2(2)(009++ +1]
1 (5" 2)v0 2a0e (2-c0)v0 + - s cf 22v0 og + -1- - 1s" =1) +
2
Here, to use Lemma 1.3, for h2 2 we take test tensor T2 x2 and set cu 2. The last line also holds by using the Cauchy- Schharz inequality for Eglls. xy,,x))] < (2)(s(
(x(+((,x=)+111 < Eqlv(y, x>) $11/ (1). As for the case s* = we already have constant outside, and noting that the second moment is at most O(1) due to the quadruple-integrabe sumption, it suffices to consider in the following 8" > 2. For the second part of Eq. (H.8), we can split the expectation according to Eq. (H.7). For the first term in Eq. (H.7) which corresponds
as-
to v(s 1s++2(6 (s + 1) hs+2 (244(2)(((0))) y8s @ e we take test tensor T2 = 8 x (0+)8(s-2) with co 2, s* + and have by Proposition I.4 that
Σ V +)s$))(s 1) Eo [c.(z) (vc, z)) (w), =))hs+2(2)((00)) & L
1s0 S co). (4' -1-- [90/ /2]
do + +G
11-111
100/21 200) + 60- v20
+ 1 S 2(8" - 1))
6
5 -111-((0
5 e s 2(5² - 1741-00)
20'22--2 + 1ss 2 4) 2 o/ + o 20-
For the second term h. (=))))0))))) Sy,, we take test tensor T3 = (0+) 05 with co = 0, so = s* and have by Proposition I.4 that
Ee (C.(u))(,,, (w, 2)) ()) 80]
I 60 Nv50 + G -1-00((0)1))) 60 c + 60 266' 210-11)
S 20 + +1- c 20' 20 f-'-t c 22220"= -1
For the third term 28 h (=)))) @ v] (0), v), we take test tensor T2 = = 6 (0+) with Co s0 8* and have by Proposition 1.4 that
Σ 28 Eg (v) (w, >)), (3)))
S 60 [25 vas + g- -1--0((0++))/1 600 c co 260 -10--101--00)
6 20 -1 +(- -2- .0. .
20 -5²" co
c 25'-2
70

---

Published as a conference paper at ICLR 2025
For the last term vs(s 11) h (00) 21 -00, u)?, ,0,,))
we take test tensor T. (0+)8s with
Cu 0, Su = s" - and have by Proposition 1.4 that
80
Σ
Va(s -1)- Rg (V) (1,, =))bb(y (wl, 2))))=-2(())(00)))))))))) (0-00))88-2111))))))) .. (0*,00)
$ 1ss =2) (ái -6i--1-150/31
ch + +1 -1-111/0/2
6
+ + (225")vo0
+ (
5' -1=
@ - 00 210--1)+1-00)
S = 2) +
+ +ef e 28
c e 20 -0 S 1(s* = =2)=1 + 5 e -
Summing up the above terms, we have that for
s* 22
F
20 + ( -1) ( 22 +1ss" 2 4) (='"2 eh c oΦ. 2
./.22 26'
1 c ) (9'- 60
25' + 1s 2] + q x 1(0 110=0% 0*)
S 2 + 8' - + 20 -2 + 1l (8 2 4) c -3 + 20'-1
+ 5 c0 + + t . -)- 1(v 0*).
If v 8*, then we additionally have cg = c, which simplifies the above bound to
2
F 2- Sa 22 ef
20 -1 =i-
(1t
1
E1
E1
For o 0*, we have that
Fl P1.2220100 E e9
25--2e + e
--- + c
.22
22 + +1ss* 2
33 -3
+ 20
S -1 (1+
(1+
2
2
(e + 1(s" 2 41)
+
Where for 8* = 1, we have Fla-m1 S 1. Hence, we complete the proof.
Lemma H.4. For polarization level ς = o(1), take the polarized random vector
yC1 +
where E~ (~Unif($a1))
11r1 + Ell2
where ei = T)T is the first standard basis vector in Rdd, Let 0- = (p, /1 - p²,0.....,0) gd-1 be a fixed direction. Then, we have that
(1ol7+ o 1-1/ 1211- p/2
if s is even
E E [)
(INlT+ + v - pd pd-112)) 1/2)
8-1
if is odd.
Proof of Lemma H.4. For w. we have by Lemma 1.9 that the first moment is given by E [w] C(er, -1 e1 ye1.
and the second moment is controlled by
C((e1, 7) (y fy+d 1-12222
(y d 1/2y2
0
0
E Blww]]
3
C(2e2, 7) la-1
d la-1
For (0', w) w, we look at coordinate T of w. and the first moment is given by
E (( w> w-1 E [por + /1 - p2 w.
71

---

Published as a conference paper at ICLR 2025
Note that if + 2, then the expectation is zero. For more generality, let us take 11, E N. We study the following expectation:
E [100, ,w)² wwi w
p²
E W1
tra jtr
Wi2
11 j + +22 even)
1//2|
2 V1 p2
2
2/
w
25t
W2
2
if 12 is even,
2j
1=0
[1s 1)/2
Σ
25+1
V
12
2
E
2j
+
w22 - 2
if + 12 is odd.
2j ++1
Here, the first equality holds by noting that each term in the sum is zero if the degree w2 is odd due to the symmetry in the distribution of w2. Next, we invoke Lemma 1.9 for the moment as
1(0", w)) wi ufu ==2"
if 8 + r2 is even:
[e/2]
g 162 odd) (7+ 25+2(n/2] (a-1/2) x s-2j+r2
p²
21
j=U
if + 12 is odd:
((s-1) Σ j=0
2-22 1(r even) (7+ 1-1/2) 25+21 الع21
(d-1/2) 8-2j-1tr2
2it1 V1 02
21+1
if + r2 even:
VI p²
(s old)
7 101 odd)
(1+
1
21
r2+1(( odd)
(1e(7 11d-22d-122 21g1
Vil
if s + r2 odd:
PV (s even)
(rr even)
(x
1
2 1itt
12+ even)
+ + VI- p-p VI- 21"
Va
Here, the symbol conceals some constant factors that are governed by upper and lower bounds dependent on s only. Using the above calculation, have We can specialize the above results the case T1 = T2 = 0 and obtain
(l0l(7 + + + v1 - 22d-1/2)² py (1 + v1 - p2d 1/2
if 8 even
B(00", w) ~
if s is odd,
which completes the proof.
TECHNICAL RESULTS
I.1 TECHNICAL RESULTS FOR HERMITE TENSOR
Proposition L.1. Let s E No. For any E Rd, we have
(2) Symm(V( (s + 1) hs+2(=)(es e,) 61)h((2) + h,(=)ee)) + s (z) 8 0e, + Vs(s -1) h.-2(=)) 8 e, 8 es), where we define h- (z) and h 2x) to be all zero tensors of any conformable shape.
Proof of Proposition I.I. Note that each element of h8 2)22T must lie in the polynomial space with degree at most s + 2, i.e., 2x+] We take a test function F: Rd + IR such that R E [[
Thus, we can write down the inner product of F and (6- (2)22 for i,j E [d] as
E (F(),,( 2))42z]
E.-Ms (F)))(F())a)))) Santey-hh.e1 (0)=) 191),
72

---

Published as a conference paper at ICLR 2025
where in the equation, we use (B.4) rewrite the Hermite polynomial in terms of the Hermite tensor. suffices to understand the tensor F(2) h2(2). Note that F is differentiable to any order, and the tensor obtained by differentiating F to any order is square-integrable with respect to the standard normal distribution. By the Stein's ss lemma for Hermite tensor (B.5), we have
vs! TE (2))222,h = NN (V)(())
8(s - 1) F (22)V(
= Sym
EE~Na
3 V
E N. 2PE))
2
+ sB F') @ e₁] + s(s
(1.1)
Here, the "Sym" operation symmetrizes the tensor in the parentheses. The last equality holds by the following calculations. For
we have
Ex~.a (z)))aa)) = Sym (E5~Na (())) + Bs
V (()]e)))))
-yym (E (2222) B, V @ e,]l),
where we use the Stein's lemma for both equalities. For B,.,, = we have
Sym (Be-Na VV>
Sym [[==:__a3"===0000e_=_2
e,))
= Sym (Es-.,, ( + ( @ ez)).
Now, for each derivative of F in (I.1), we have by the Stein's lemma stated in (B.5) that Ez~N Vs! NE- (F()). which gives us
E (())==)z),,())) = Benus F(2) Sym (amm@dggh (z) + V (s + 2) + +1) (x)
+ (=)le,) & e, + h.(z)led) @e + vs(s- 1) h 22) (z)
Since F E [R+2[=] is arbitrary, we conclude that =2 h2) = Sym( ( / (s () 1) h= @ eel + 8. (2) + h. (=)leg)
+ (z) + Vs(s - 1) h2-2(1) (e)
The proof is completed by further taking the tensor inner product operation with respect (0*) 8+ on both side.
Proposition 1.2. Let w, w E gg and s E No. We have
E [h,,(ww, 2))m,((w', 2)) hz(2]
S - ()) s!((i T)!)² (w,, (u,,"))- Sym(u o @ w w
ilj!
The above term is equal to
8 (15 (i ((-j+t))2) s)/2)
V ilj!! (w,,"((ttj-))
s! ((i+j- - Sym (ymm(oll-stet)) & u - o
i/ - 5 i j and & =i-j j mod 2. Otherwise the expectation gives the zero tensor.
Proof of Proposition 1.2. By the Stein's 's lemma for the Hermite tensor (B.5), we have 1
E [h,((w, 2)),,((w', 2)) h=(2) = Vs!
-E [VV"(h,((w, 2)) ((w()
1
E Sym V he 2)) & V hy ((w', 2)))]
Vsl 7=0
ilj!
V (i - T)1(j s + T)!
E
h4- ((w, 2)) @ ((u- ((w1,2) 2)) Sym Symnwwr @ w @ (+-)))
i!j!
- 27,
2T,
(w, w -y (1) Symmm @ n 887))
(i ()-
s!
73

---

Published as a conference paper at ICLR 2025
the condition can be translated into | - =s sit and = jij mod 2. Then, can take
T = (i - j ++ s)/2, T = (j ( - (i+j s) to obtain the desired result. t
Lemma 1.3. Let v : E + R such that 2i² (N). Suppose that &b is high-pass in the sense that v; = for any i < s* for some s" E Ny. For w, w E ga-1, take a series of test tensor ]== U E (R²))s)s such that supiseo (k v.)1 Kw va)l3 S for some
{T, @ 02
e E (0, 1/2) and integer on E No. Let
6o
max
(lw,, w.)l (('', v....
isiSmo
Suppose that (w,, (w,,"")l S 61. Then we have any No that
Ea (ww, ()) (w', 2)) h=())[]]]]] & 4||0112 (4es where 1| = (enn((??())
anco (0-co) 2/2 V8 - st 16-11_1/2
Proof of Lemma L.3, As (z))(a)) is also square-integrable, we are able to extract the s-th tensor coefficient of the Hermite expansion of (xx)))((r))
BanNa (ww, 2))()((w ,2)) (z)l
= ELNNN
( 2) 2))hg(((( 2)) (z)2)
1(j 1iits-2r,i277 (7) V s!((i 7]1)2
i!j!
Vidyy (w, w'y " Sym(w & w w
r=0
iliiss s 2T) 3) Di (w, w/)ir. Sym(w or @ w (lo--))
10
@r
(ii-)
1=0
where the last second identity follows from Proposition 1.2, and in the last line we restrict the condition j = i s 2r. Note that the double sums are interchangeable only if the series converges for each т. However, by our condition that (w, w²) S 1 for some > O, then for each т, we have for any test
tensor T U1 @ 0/2 ... @ Ug with || l12 = 1 that
Σ
ilii + s- - -2T)!
((i 11--1 +))2 $3 P2 (w. ()) i- Sym or & w r 7
(i + 8) e/2 ( (1 (1- (1- < oo,
where we note that 1 - e will dominate the polynomial growth of (i + s)//2 and also using the fact that W.4444-2 is uniformly bounded by Σi D3 < co. Now, interchange the double sum and apply the high-pass assumption and have that
EgaNa [ew(w,, 2))()((w 22) (=)
ili + -27)! ((i -]]] B Direna (w, w')i Sym(w 8 (w( [T].
where we define
io = max {(5 -1 1
-8 2r - s),
Note that the tensor product part is independent of i. Hence, we pull out term (I) and have
io!(io + +s- 2r)
())
(iio - =] ii Sio (w. wi)
8
+ ||11 (w, 10-
Σ
55* 1)....
[(s 1)/21) (w, w')l
74

---

Published as a conference paper at ICLR 2025
Here, the first term is given by splitting out the term with i in from the summation, and the second
term is for 2 io + 1. For the second term, we have the following argument:
max du + s - 2 = (s" - Vs 1 2T V (s" -1 - (s) 11)
1) (s-) 7)
= -1= - 6) V Vs - - VT
(s* -1+ s|) (|T s/21 ss' 1.
Hence, we then have that for any i 2 10 with j = i (io + 1) that
max(i, i + - 2r S S* +s+
Therefore, for any i 2 du + 1, we have
[ilii + -TT! vili 1) (1-T+1) (i+ 2T) - - 1)... (+
())=
8 + sj + + (j+ + [(s + 1)/21).
To characterize the second term, we use Proposition J.5 where we have conditions (w,, w')1 1/2 and s* + 2 2[(s + 1)/2] satisfied, which gives us
Σ ( + s ) + + - - 1). 1))...i++ + [(s + 1)/21) w')l'
j=0
1
2( ... '.'("" + [ss + 1)/21) 1- Kwi, w')l
S 4( ((8+88) ... (8* + (s+ + 1)/21)-
Combining these results, we have for (I) that
(I) = io0(00 + - 2T)!
((io - 7!)2 Vio +s (wc, w'yoo + 11b112 4(8 (6* + [(s + 1)/21) (wo, w w/yo--r4
C(s s, (u,, w')) (w, w 10750-7,
where we define C(s", S, (w, w²)) = (1) (w,, woyio- T as the coefficient, which is given by
C(s", T, (w, w') io0 + s - 2T)! ((io )))
+ vioo 2 |1
4(s + + ... (s* - + [(s + 1)/21) Kw, w>>,
and also enjoys the following upper bound
C(s*, 8, T, (w, w())| S 11 + 5* (5* - 1 + [(s + 1)/21)
(I.2)
Here, the upper bound can be obtained by noting that the previous upper bound for terms i 2 i0 + 1 can be also applied to 2 ig.
Case 2 1. Let us plug in test tensor T, into the expression, which gives us [BENNN (1,( ((w))((((,))) (=)[(]]]]
CC(s (w, (ww wn>) "0- Sym @r & w (86
IC(s s. (w, w')) (ww "o
1 s! mEIT,
II (10, eo
II
Kw eل(ni)
1=++1
where II, denotes the set of all permutations of s elements. We further have this term bounded by (w/,)))
Ez~Na [WW(w, 2) (ww', 2)) (x)[T.l]]
(I.3)
I max ( UST
8
s, (w, w('i)l Kw, w/) - snco (x-co))V0
7=0
2
-= max |C(s 7, (w, w²))l 1)1--110 kw, w/) -11-//11))))))) r0 proe (o-00) O5T5$
Vs!
75

---

Published as a conference paper at ICLR 2025
where the last inequality follows from the following fact
i0 - T = -
2 16 1/ vo
(s (dd)/2)vV-- (8 -1- [=/22] VO.
Plugging (1.2) into (1.3), and by noting that Kw,, uz)l V ((w',s)) S e for any is {0,, 0) and
(w, w²)l S 6, we have that
Na No [ww ()),' =))- h. (=)
2
|
snco ( 4(ss + 5" 11) -1+ [(s + 1)/21) - -1-1//223
c
!!
4e(s
+ 8* -1=
8/2
Vs + - +*
sAro (0-col]v 4 1 (8' 11-=1=1
c
$ (4es*) )3/2
4 1 ci 1-' -0000 (co_o))vo
V
Here, the second inequality follows from the Stirling's approximation, and the last incquality holds because 8 2
Case O. For the case O, we have that
EE [ub( z)) 2))1 = 00,0, (u,, w')) (w, - S 4/|bb [e
which can also be upper bounded by the quantity derived for the case 2 1. Hence, the proof is completed.
Proposition L.4. Let (2,))) satisfies the quadratic integrability condition and high-pass condition
in Assumption 4.1 with s* being the generative exponent. Suppose the remaining definitions (co {T e, 60, 61) and conditions are the same as Lemma 1.3. Suppose co E {0, 2] and so Ng-
Take function series (-))))) satisfying Bo(ss(v) 2] < C, Vs E No for some universal C = 0(1)
Suppose 4ee² < <1/2. If 1, then we have that
Σ (s + 2) -EQ (v) (we, 2)) (2) h.) (T)I S < + c
#280
If s* 2 2, then we have that
Σ (s + 2). IE (Sa(v))(u (w))))) , ()),]
8280
$ 1 (80 S co) (1 11-111100/2) 60- + +1
00 11-11-
c0
+ 60 (25"))s0
+ 1(s0 S 2(s* 1)) (ei ((
E 2 -1)1-10)
c -
Here, S hides constants that depend on 8o, Co, C, C,Ea(v(V,x))
Proof of Proposition 1.4. Let F denote the target quantity. Invoking Lemma 1.3 for each degree 8, we have that
F F<
Σ
V s(s + 1)- Egnu EZNNA (o) (w, 2)) (w (>)),(
$2.0
(s(s+ + 1)- Egna
(4es*)*/2 9/2 V s-( (0' /////_//// co (o-0-/0
$250
Σ /s( + 1) 4 Eols (w) (4es*) V*+ (0" (e/2])vO snco co $2.0
<
where the last incquality follows from the Cauchy-Schward inequality. Noting that by our assumptions, (ol = O(1) uniformly over 8, which gives
FS Σ Vs(s - () + 5*) (4es*) 8/2 e /// snco (+-ocvv)
Eo
2280
76

---

Published as a conference paper at ICLR 2025
For the case s* 1, we have the above term controlled by
F s== 2 Σ Vs(s+ 1)² (4e))/2 0 go (x-cavo
$2%0
< (cn > 80)
sup 6 +
Σ
Vs(s+ + 1)2 (4e))/2 co 6000-
Vec
2 1(c0 80) c c (80-co
Σ
Vs(s Vo(s+ + 1)2
1 (dee²) (5-ooV(==0
< 1s00 < co) c0 + E c
< 6
where S only hides constants that depend on so: Co. The last second incquality holds by noting that 4ec² 1/2..
For the case s* 2 2, we note that cu 2 2(5* - 1), and we have
F 82 S
Σ /s(s+1)((s +*)) (4es*)s/3 -11111//0 snco e
(s-col00
#2#0
< (s0 S co)
max 1
11 E
40 $55
+ 1s0 S 2(s - 1))
max +1 15=5= 1)+1
11/2
9)
co c000
Σ
V () 5*) (4es ) 12/2
20 c0ee_0s
22(2 -1)+2]vo0
$ 1 S 0o) (1'- -1 8l + 6 11-1-100/21 1 + 00 (25 1122/--00
+1300 s 2(x" - 1)) (e) ( (1-
60 E + 2 -1)+1-00)
Thus, we complete the proof.
1.2 TECHNICAL RESULTS FOR UNIFORM DISTRIBUTION ON THE SPHERE
Lemma 1.5 (Moment of polynomial on a sphere, adapted from Folland (2001)). Let g = (E1,6,....,E)) ~ Un and 81, , E No. Let 8 Ein 8i. Then we have
if some s is odd,
Eg
c
[((s; 1)/2)
T(d/2) T(1/2) I((s + d)/2)
iflll 8; are even,
To evaluate this moment, we provide the following bound. Fact L.6. Take even degrees 81, $2,82, 8d E No and Ed= 8t. Then we have
< (2)²²
()) x/2
T((s, +1/22
T(d/2)
S 8 8/2
T(1/2) I((s + +d/22
(
where we define (0)0- 1.
Proof of Fact 1.6. Note that we can rewrite the product
d II 1=1 T(1/2)
I((s; + 1)/2)
d (s: 1)!! I((ss d)/2) (s+d-2) (s d
r(d/2)
Using the fact that a/b 2 (a 1)/(b 1100-1 1) for 2 S S b we can recursively apply this inequality to the factorial until it gives us the desired lower bound of (1/dy//2 For the upper bound, we can lower bound the denominator by /2/2 and upper bound the numerator by s*/ We thus have the desired result.
77

---

Published as a conference paper at ICLR 2025
Note that the second moment B[g x d=! thus Fact 16 can be viewed some kind of reverse Holder's 's inequality where we use lower moment to control higher moment. Notably, the reverse inequality gives dimension-free bound for the moments of the polynomial on the sphere. The following proposition formalizes this intuition.
Proposition 1.7. Suppose Ç = (21.52..... .aa Unif(S(-1)) Let f R² R be a function such that (E( - 1)²] S e². Take nonnegative degree 8 = (81, 82, .2....... .8) with || and suppose each 8; is even for E [d]. We then have
(
8/2
0/2 (7)
(1 - (26)
SE f(E)
II c
S 51+
Proof of Proposition 1.7. By the Cauchy-Schwand inequality, we have for any j = 0,
81122.
d
d
2ss
8/2
(S(S) - II 5. S v (((((E) 1)2]
28
S
&
d
where we use Lemma 1.5 and the upper bound in Fact 1.6 for the second inequality. Additionally, note that each s; is even, we use the same argument have
#/2
8/2
E
7
Combining these two inequalities, we conclude the proof.
Proposition I.8. Let & = (E1,E2..... Ea) ~ Unif(Sd-1) 7 > O be a fixed parameter, and
($1, $2, ,......,,.... sd) be nonnegative integer vector with ||s||| = It then holds that
Le1/2]
G(s) = E (51 +1
#c 2=2
=
E
81
23
c
2j
f=U
0,
if some 8; is odd for 2,3.....44 otherwise,
((s,)) (7 + vta where 1/5 S ((s,n) S 5/2
2[11/21
201 odd)
(11 Vd
Proof of Proposition L88. Note that
81
G(s) E (51 7)
E
81
517
II
j
2
2
Note that if there exists any odd degree s; for > 2, then G(s) = 0. For 82, 83.... being even, we have
[21/2]
d
G(s)
E
81
$1
22
2j
t=2
[2
Σ
81
24
T(j + 1/2)
III
T((s: + 1)/2)
T(d/2)
2j
T(1/2)
I(1/2)
T((s $1 + d)/2)
1=0
==2
[2
Σ
$1
2j
(2j
1)!!
II
(8: 1)!!
2j
81
2j
2)
81 2j + d ...
==
(1)
where for the second identity, we use Lemma 1.5 to compute the moments of the polynomial on the sphere. Now, compute the lower and upper bounds of G(s).
78

---

Published as a conference paper at ICLR 2025
Lower Bound.
For the lower bound, we have
[s//2]
G(s)
Σ
81
7:t 22 d j-
5
[2//2]
Σ
(2($1/21)
-22151/21-211
1
2/
d (02ttst o Mes odd)
5
2j
vdl
j=0
(2) (2(s1/2) j
d
1(01 odd)
Here in the first inequality, we use the fact that a/b (a 1)/(b - 1) for 2 S a S b and apply it recursively to the factorial (I) until it gives (r--(( For the second inequality, we first rearrange the terms in the summation and lower bound the binomial coefficients by changing 81 to 2 /2.. For the last inequality, let us define
A₁ = (2131/21) 2 j
Vdl
We invoke Lemma J.4 and have that for each odd j. have that
A, 2(4 Af+1), j = 1, 2| [2] 1
Therefore, the summation of all the odd terms is upper bounded by times the summation of all the even terms, which gives us the last inequality. Therefore, the lower bound of G(s) is
(a-a1)
G(8) 2
7
Va
(ss odd)
Vi
Upper Bound.
For the upper bound, we have
[x//2]
v G(s)
Σ
81
70t 21
dt -----022000
+o0) 80/2
2j
j=0
2 2 /2]
[ (2[$1/2)
-22001/21-0
d (e2test g21(s odd) g02
<
j
1=0
2/.1/2]
-(--1))
1 Vd
8/2
7 Vd
(sg odd).
where the first line, we lower bound the denominator in the factorial (I) by tsat and upper bound the numerator by s²/2, For the second inequality, we use the nonnegativity each terms and append the terms with j being odd to the summation.
Combining the lower and upper bounds, we have that
0.
if some is odd for = ,d, otherwise,
G(s) ((8,7) (7+
1 Val ) 2|0s/2] I(1 odd).
for 1/5 < C(s, S 8/2 Hence, the proof is complete.
I.3 TECHNICAL RESULTS ON POLARIZED RANDOM VECTORS
Lemma 1.9 (Moments of weakly polarized random vector). Suppose & (E1,E2,...,, Unif(Sd-1) 1) and define the polarized vector w as
E 761
[ + ye1 l12
79

---

Published as a conference paper at ICLR 2025
where y o(1 > 0 is parameter that describes the polarization strength, and 61 (1,0. ..... .0) the first standard basis vector. Take nonnegative integer degree s ($1, 82...,,) with || 0(1) < (2ver) 2. Then we have
0,
if some 8; is odd i = 2, 3, dd
c(8,)) (7+ )
Ew
w
Va
if 81 is even, , Sd are even,
C(s,n).n (7+ +/2)
5:-1
5-
if is odd, $...... Sd even,
vd
where - 0(7) s C(8,7) 7) v g(0+1)/2 + 0(7).
Proof of Lemma 1.9. Let r = || + ye1ll2. We reformulate the moment as
(E1 + 7)
E
II
c
By symmetry, we have the moment equal zero if some is odd for = 2, ..., d. Hence, we only need consider 82, ;3, being even. In the following, we study the case for 81 being even and odd separately.
Case I: is even. We first look at the simpler case where is even. We note by weak polarization in the sense of |kEl|2 > leelll we can approximate 1/r" as 1 with approximation error
E
W
E
(51 + +7)
II i=2
&
S v E
[(1
E
(51 + 7
c
2#:
2=
d II
S Sesy
V
E (Ei
2201
28
(1.4)
2=2
where we use the Cauchy-Schwarz Schwarz inequality in the first line and for the second line, we use the fact
7 - 11 exp ( 87 (1-)) )
1
1 S esy
(L.5)
71
for < (2veT) Define
C(s)==B
(S1 + 7)
c
By Proposition 1.8, we have that for even 81, 82, .2,.....
C(s)=C((ssn) (1+ Vdl
Vd
with 1/5 S Ca 7) S 8/2 Plugging the form of G(s) into (I.4), we have that
E
w
-((s) c (2s))
(C'(s,)) + es7 e (7+ Vd
1
Vd
4-8;
(C'(s,)) + + 7
Vdl
Here, (8 e27 1/5 (2) and C' (s, 7) + esy(2)) < s02 + (27(2))012
80

---

Published as a conference paper at ICLR 2025
Case 2: $1 is odd. We now consider the more complicated case where $1 is odd. In the following proof, we will frequently invoke the following proposition, whose proof is deferred to Proposition 1.7 of Appendix H.
Proposition 1.7 (Restated). Suppose & ($1, E ..... Ea) Uni Let f R2 I be function such that [[( - - I E². Take nonnegative degree s = (81, $2............. ................................ Se) with || and suppose each s; even E [d]. We then have
(1 - (28)
(2)
8/2
s E
f(E)
c S (1+ (1+221/2))
(2)
8/2
i=
We first rewrite the moment as
(51 + 7)
d
E
(I.6)
1=2
(sr
12//2
Σ
(1
7 1-11-2
2j
E
2j
c3i
+
(s 11/2
91
7 2j
E
51
2j+1
d
2j
2j +
ps
1=0
j=0
(T) even terms
(IT) odd terms
Let us look at the odd terms of (1.6). Let = lk + ye1 ll2 and r- = 11- + 701 By symmetry. we have for the expectation within the odd terms that
E
2
1 E
1
1
25+1
2
+
p
(r2 - 22) EE=
d
IE
2j+1
2
r r (r+ +r_)
i=2
2. s- r_ s-1-1
d
- E
2j+2
II
r r (r+ +
2=2
Here, the last identity holds by noting that r2 r -4 Note that
2 -i
1
sup SEB4
<
-
r4 r (r+ +r)
1
Hence, we have for the odd terms (II) that
(s 11/2
2
(II) E
Σ
1 75- g22
22+2
c
r4 r
+r++
2j +1
1=
1=2
11/2
(s- +2)++2//
81
(1 + 2(x+2)/2 2(0+2) e7(++2))) 2))
8 s
2j +
d
1=0
s +
(2-8
Σ (91-1)
(Vatz +2
< 81 (1 + 2(652)222e(( 2))
en
7 7
d
==
where the first inequality holds by Proposition 1.7 and the second inequality holds by ( (2/t1) ((/7)) 81 s1/(2j + 1) < 81 and also appending the odd terms the summation. Thus, we have
-1-1
5-81+2
+
+
-II) < (1 + (2+2)) (ey(s + 2)) 7. 7+ d
81

---

Published as a conference paper at ICLR 2025
Next, we study the even terms (I) in (L6).. Using Proposition L.7 with the uniform bound in (I.5), have (I) upper bounded by
(+1
11/2 Σ
21
(
81
2j
E
51
2j
r
3=0
i=2
$ (1 <(1 25/2 es7)
(81 (81-1)/2 Σ
(81
70 22j
8
$-51+2j
Vdd
2j
j=0
S (1 21/ es7)
Σ
81 - 1)
. -
(V d
(V
5
-8
j
i=0
-1 (1 + 2 2 77
7+ V
a
8
81
(v d
8-81
Similarly, we have the lower bound for (l) as
(x1-1)/2
2
(=
Σ
81
E
2j
(81
1)/2
(Vá)
s-s1
2 (25)* 1/2 ((87)
$1
22
2j
1=
81 1
(va)
(V2)
2 (1 - (2s) 2/2 (2s) (07)
Σ
y
5
1=
/
(1 - (25) (87)
7 v
Combining these upper and lower bounds for (I) together with the upper bound for (II), we have
N ( (23) 81 (1 + 2(0+2)/2 + 2)) (s + 2)
E
w
d
g+ v2)
81-1
8-81
r..
and
81-1
( v2
S (1+22/\2687) g(o+1)/2 ... (7+
E
Vd
Hence, we complete our proof.
J AUXILIARY LEMMAS
Lemma J.1 (Bernstein's inequality), Let X1y..., Xx be independent random variables with XX; E[Xi]| S for all i [n]. Then for any >> holds that
1
(- nn. Em Var + Ct/3
nt212
X;
EX
< 2exp 21)
1=1
or equivalently, for any ā E (0,
2.
ΣR Var(X.) log 6-
C' C'log 8-1
P
Σ X.
EX,
$
+
2 1 1- 5.
3n
1=1
82

---

Published as a conference paper at ICLR 2025
For the vector case, by union bound over all the coordinates, we have the following corollary. Corollary J.2 (Vector version of Bernstein's 's inequality). Let XI...., Xn be independent random vectors in Rd with ||X; - o[ S C for all E [n]. Then for any d (0, 1), holds with probability at least å that
Σ ii=
Tr(Cov(X.)) log (og(d6-1) VdClog((d-))
X
E
X.
n
n
Lemma J.3 (Lemma 1.3. in Damian et al. (2024)).
Let Xi.... .n Ed be independent mean-zero p pip < 22 for some constants C. and
random vectors such that for all p >
| X;
E
vector norm |||||, Define o² := n D B least 25,
X
and Y == n Ei= X,. Then with probability
|YII a. 1og(1/6)
Cllo(11 /6) log(n/ log(n/8)*/2
n
where $ only hides constant that depends on
Lemma J.4 (Ratio bound of binomial expansion), For real numbers a, b > and integer s 2 define
A3 ..-)).o0..00) V, for j 0, ,.
Then for all j = 1,2.....8 holds that A, S 2( + Az+1).
Proof of Lemma J.4. By the definition of Aj.
min ( A A₁
s j a 1+1]
8
+ 1
a
j+1
min
AA-1' Az-1)
j b 8 s-j
b
j
VV(1+ (1+
1 -
( (1+ , 2.
Hence, the proof is complete by the nonnegativity of Ay.
Proposition J.5. For E [0, and s,r E No with 2 2r 1, it holds that
(i+s) 1) J=0
(i+s-r+ 1--1--ss---------t--------- 2s (s 1) ... (-s + I-E
-f+s-r+ Proof of Proposition J.5. Denote (i (eao-)))..((trtrt))). for E (0,
The desired quantity on the left-hand side of the inequality is simply F(c). can be verified using the expansion of 1/(1 x) = Σj= x for I E (0, 1) that
d"
x ) x (s-r)
F(x) dx ( x
Expanding this expression, we have
--
F(x)= =
0 dar (x*)
x (s-r)
-r 1 1
Σ s(s 1) ..... (s - - 1) x- (-1)r- (r-
(1 --+- . (8-r)
x
Σ (r. (r 1). (r + 1)) (s - 1) 1.... (s T 1)) (--1)-7
(1 r-+1
83

---

Published as a conference paper at ICLR 2025
Write the above summation Fx)) Ex= (x), where Fx(x) is the 7-th term in the summation. Then for each T = 0, , 1, when x E (0,1), we have
(x)
8-7 7
1-
x
< -1
(+)
T+1
Note that (x( is positive, and for each k = I,..., |r/2], Fr- F(x) is positive, then upper bounded by [x(x) + (..(z))..ee.
22-1 <FF-2()1)) < 0. Since Fr-22+1
1
F(x) S (s 1)............ -s--+--- 11 x
r! (1 (1-x)r+1 28 (8-1) (s 1
1 1- F
The proof is complete by setting x =.
Lemma J.6 (Gaussian-like tail bound for spherical coordinate). Suppose & ~ Unif(S Then the first coordinate of e. denoted by f1, satisfies that for any t Z 0,
Pr(E1 2 VCd- (Cd-'logd]) llogd S exp(-d/16) d C/4
where C is a constant.
Proof of Lemma J.6. Consider 2 ~ (0, Ia), and it holds that & - 21 >1/1|=||2. where 21 is the first coordinate of Note that |==1|2 xa. and by standard tail bound for the Xa distribution, we have
Pr(1I=12 22222232 I d 2 dx) I exp(-2)) for any 0.
By taking x = d/16, we get Pr[1 - d/2) S (ep(-d/16) Thus, applying a union bound,
Pr(Ei 2 t) = Pr
21 2 t $ Pr (1|=13 - d/2) - Pr(zi 22/d/2)
|
I exp(-d/16) + exp(-
The proof is complete by taking / = VCd-1 d.
Lemma J.7 (Hypergeometric behavior). Consider random variable X Hypergeometric(d,k k) with probability mass
Pr(X x)
for 1,2....k.
Suppose l: d(vd). then for any constant s > 0, it holds that E[Xx] ~ /2/d. In addition, the following tail bound holds:
Pr(X log k) S (k2 (k2/d)loz look
Proof of Lemma J.7. We first notice that for 2 2:2 / since k: = ol olva).
Pr(X x: +1 Pr(X = x) (x + l) 2k x +
(k: x²
(1
k 2 d
k2
7
+
(I.I)
This immediately implies the tail bound:
222 log
Pr(X 2 log k.)
<
Pr(X = j) i) S
flog A.
Next, for the moment E[X"], we first study the magnitude of P(X = 0), which, by Stirling's approximation, is given by
Pr(X = 0) = ((d- k)))2
(d- k) ((d-k)
d! (d - 2k)! ~ dd+1/2. (d - 2k (d (d-26)+1/2 e e k(
(1 2k/d k22 ddd
(1 2k/ 2k/d) 3k/d)d-2kt1) 2k
d-k+1/2
2h
1 (12kkdd d2/12
1
84

---

Published as a conference paper at ICLR 2025
Since l olvd), have (1 -kk//dd)* 1. Further applying the fact that (1 1/m) O(1,
(1-2k/4) /12 222.2222//
Pr(X 0) (1+ (1 2k/d) d2/k2
(1).
As consequence, using the first equality in (J.1), we can lower bound the expectation of X by
k²
k2
E[X* 2 Pr(X = Pr(X 0) d 2k: +
d
For the upper bound, we again use the first equality (J.1) get
22
Pr(X x)
k2
Pr(X = x 1) (x 1)(d - 24 1) Pr(X = x) -
2 + +1
d'
Recursive application of this inequality yields that P(X x) S P(X = 0) /d) / and thus
k2
E[X*]
x Pr(X x) - Pr(X = 0)
d
1=1
Therefore, we conclude that E[X*] /2/d. This completes the proof.
85


Reviews:
[{"review_id": "Zj1yOBMIay", "reviewer": "Reviewer_NQEc", "summary": "This paper investigates the sample complexity of learning Gaussian single-index models with a two-layer neural network. The authors introduce a gradient-based training method that learns the target with $d^{s^*/2}$ samples, where $s^*$ is the generative exponent, hence matching the SQ lower bound up to poly-log factors and improving on previous works. The authors present also an improved sample complexity bound in the case of sparse teacher prior, a setting not addressed much in previous literature.", "questions": "- Is there anything you can say for non-high-pass activations? More generally, I would like to understand whether these results generalises to some extents to natural gradient oracles.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Gaussian single index models have received a substantial interest recently, and this paper provides a detailed unifying framework, supported by theoretical proofs, which is of interest to the community.\n- The framework includes several previous works, which allow to compare this work to previous result.\n- The sparse teacher setting is novel and of interest.", "weaknesses": "- The algorithm requires a gradient oracle, which is a bit unusual and requires choosing the loss and the activation ad hoc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IlZPQJJb3O", "reviewer": "Reviewer_A2wU", "summary": "This paper studies the problem of learning single-index models with neural networks. Under a general gradient oracle, the authors present an algorithm that can achieve the optimal computational-statistical tradeoff by obtaining a sample complexity of $\\tilde{O}(d^{s^*/2} \\lor d)$, and contains the batch-reuse approach of prior work as an example for learning polynomials where $s^* \\leq 2$. Furthermore, the authors construct a random loss for each single-index model that implements this general gradient oracle for all $s^*$ when using the $s^*$ degree Hermite polynomial as the activation. Finally, the authors consider the case where the single-index model has additional sparsity, proving an SQ sample complexity lower bound of $n = \\tilde{\\Omega}(k^{s^*})$ for $k = o(\\sqrt{d})$, and presenting an algorithm that matches this lower bound.", "questions": "* There are some ambiguities in the discussion starting from Line 258:\n    * The paragraph before introduces a general class of gradients $\\psi(y,x)z$, but here we switch back to activations. What kind of loss function are we using here? The calculation seems to be for squared loss, but my impression was that we have to change the loss to go beyond correlational queries in this online setting.\n    * The identity in Line 267 might require further clarification. For example, I think $E_Q[y^2]$ should be replaced with $E_Q[\\zeta_s(y)y^2]$. Maybe we can apply Cauchy-Schwartz from here to use the assumption on $\\zeta_s$, but this would lead to the fourth moment of $y$ appearing. Perhaps the authors could add more details on the derivation to make it clearer.\n     * My impression was that the only benefit of weight perturbation is to give a smaller denominator in the SNR, however, that doesn't match the following argument. If I try to replicate the SNR calculation of the paragraph starting at Line 220 for this paragraph, the numerator in the SNR is still $d^{-(s^*-1)}$ while the new denominator coming from weight perturbation is $d^{-(s^*-3)/2}$. This leads to an SNR of order $d^{-(s^*+1)/2}$. We argued we need $\\sqrt{n\\mathrm{SNR}} \\gg d^{-1/2}$, therefore $n$ should be of the order $d^{(s^*-1)/2}$. Are there other effects happening when we perturb the weights?\n\n* Line 320 mentions that $L = \\tilde{\\Omega}(n/\\sqrt{d})$ is sufficient. Given $n = d^{s^*/2}\\lor d$, this leads to $L = d^{(s^*-1)/2}\\lor d^{1/2}$ (which seems to be used in Remark 4.3 as well), which is different from $L$ in Theorem 4.2.\n\n* The loss defined at the end of Page 22 is not exactly a loss function, for example it seems that it can decrease while $y$ is moving away from zero due to the derivative being negative. If this interpretation is correct, perhaps it could be highlighted in the main text that the goal of this loss is not to measure the difference with ground-truth labels, but to construct suitable gradient oracles.\n\n* Can Assumption C.2 be verified for distributions with high generative exponent?\n\n* Theorem 4.2 only states a lower bound on the learning rate. To me it seems like the ideal scenario would be to let the learning rate go to infinity, and directly update the model weights with the gradients as in Algorithm 2. Is there a reason we would want to have a finite learning rate in Algorithm 1?\n\n* Relevant prior works:\n    * Theorem 5.4 resembles Theorem 3.1 of [VE24], which presents the CSQ lower bound under sparsity, where generative exponent is replaced with information exponent. I think having a discussion on the similarities and differences of the two statements and techniques would be interesting.\n    * The authors cite [Bach17] as an example of neural networks achieving $O(d)$ sample complexity for learning single-index models. From [Bach17, Table 1], it seems the sample complexity of learning single-index models is $O(d^2)$. In [Bach17, Table 2], the sample complexity will be $d$ with a sign activation and $d^2$ with the ReLU activation. There is a discussion on the sample complexity obtained from [Bach17] in [MHWE24], where the authors also show that standard gradient-based algorithms can achieve the optimal $O(d)$ sample complexity, albeit with a number of queries going beyond the SQ lower bound. This might be interesting to point out while having the discussion on information-theoretically optimal sample complexity with neural networks.\n    * Another example of additional structure reducing sample complexity is structure in the input covariance, which is known to help in the CSQ setting [BESWW23, MHWSE23]. Developing algorithms that benefit this structure to achieve a smaller sample complexity in the SQ setting can be an interesting direction for future work.\n---\nReferences:\n\n[VE24] N. M. Vural and M. A. Erdogdu. \"Pruning is Optimal for Learning Sparse Features in High-Dimensions\". COLT 2024.\n\n[Bach17] F. Bach. \"Breaking the Curse of Dimensionality with Convex Neural Networks\". JMLR 2017.\n\n[MHWE24] A. Mousavi-Hosseini, D. Wu, M. A. Erdogdu. \"Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics\". arXiv 2024.\n\n[BESWW23] J. Ba, M. A. Erdogdu, T. Suzuki, Z. Wang, D. Wu. \"Learning in the presence of low-dimensional structure: a spiked random matrix perspective\". NeurIPS 2023.\n\n[MHWSE23] A. Mousavi-Hosseini, D. Wu, T. Suzuki, M. A. Erdogdu. \"Gradient-Based Feature Learning under Structured Data\". NeurIPS 2023.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has solid technical contributions and presents an alternative to the tensor power iteration algorithm of Damian et al., 2024 for learning single-index models with an algorithm that instead relies on a training procedure for neurons. In particular, having a framework that encompasses both batch-reusing and loss modification approaches of prior works is valuable. Further investigating the sparse case presents a nice example of additional hidden structure that can benefit sample complexity.", "weaknesses": "* The original motivation as stated in the abstract is to see whether neural networks trained with gradient-based methods can obtain the optimal computational-statistical tradeoff. But the algorithm presented, while interesting from a technical perspective, has little resemblance to the training of neural networks in practice. In that sense, the problem of having a more standard gradient-based algorithm that achieves this tradeoff is still open.\n\n* I believe the writing can be improved in terms of clarity and citing relevant works, with some examples provided below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WcsmSHFLLs", "reviewer": "Reviewer_mmjr", "summary": "This paper studies the learning of Gaussian single index models with an SQ complexity bound using a gradient-based technique. The main contributions are twofold: 1) They demonstrate that a carefully tuned two-layer neural network, trained with a gradient-based algorithm, can learn a non-polynomial link function within an SQ complexity framework, extending prior results that focused on polynomial link functions. Notably, their analysis is agnostic to the specific form of the link function. 2) They further extend these results to sparse single index models, achieving the optimal SQ bound in the sparse setting.", "questions": "* Is there any potential to use losses other than the squared loss to avoid label transformation, similar to [1]?\n\n* In the case of sparse priors, prior work [2] also employs a similar approach to that used in this paper, involving index-sensitive perturbation followed by gradient sparsification and support identification via a top-k operator, achieving the CSQ-optimal bound for sparse priors. Could the authors elaborate on how their technique differs from this previous approach and discuss the challenges encountered in extending these CSQ results to the SQ setting?\n\n[1] Joshi, N., Misiakiewicz, T., & Srebro, N. (2024). On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries. ArXiv, abs/2407.05622.\n\n[2] Vural, N., & Erdogdu, M.A. (2024). Pruning is Optimal for Learning Sparse Features in High-Dimensions. Annual Conference Computational Learning Theory.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is reasonably well-written and provides ample details on its technical contributions.\n* It extends the existing results on learning with SQ bounds from polynomial link functions to more general non-polynomial link functions.\n* The proof techniques are involved, involving careful arguments to address challenges such as avoiding zero correlation and enhancing the signal-to-noise ratio without prior knowledge of the link function.", "weaknesses": "* Although the paper considers neural networks, the proof techniques require numerous modifications that make the proposed algorithm somewhat unnatural. For example, the use of Hermite polynomials as the activation function is required to apply the weight perturbation technique, and the specific label transformation depends on the cumulative distribution function (CDF) of the labels.\n\n* Notably, the second assumption for label transformation and Assumption C.2 are not discussed in the main text. I recommend that the authors include a \"Limitations\" section to explicitly outline the constraints of their proof techniques for future reference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ClssHQZuyQ", "reviewer": "Reviewer_TYz2", "summary": "The author consider the problem of recovering the unknown direction in Gaussian single-index models. They present a class of online algorithms for that match the Statistical Query lower bound for this problem. As specific realizations of this algorithm, they consider the class where their iteration matches a randomized gradient-type update scheme. They also present results in the case of sparse models.", "questions": "As the authors will see, my rating is largely due to the presentation. Please consider making some of the following edits and/or answering my questions and I will gladly raise my score.\n\n**Major comments:**\n\n*Alg 1:* I am having trouble understanding the definition of the main algorithm, Alg 1. What is $err^t$? It never seems to be defined in the paper (main body or appendix).\n\n*Eq D.2* Was this sketch intended only for the case of $s_* \\geq 2$? If $s_* = 1$ then the $\\tilde{O}$ term in the norm bound in Eq D.2 seems to be the dominant term and divergent.\n\n*Gradient based:* It is not to me why the authors refer to their algorithm as gradient based. On the one hand, their algorithm as stated is more general, it is an online algorithm given some function $\\psi$ which, in certain cases, is a gradient.\n\nHowever this does not seem to correspond to an optimization algorithm for risk based inference on a loss of the form $L(y - f(z,\\theta))$.\nHow can you get a small loss since the algorithm is only updating the hidden layer? Also, why can't we just take $a = 1$ in this algorithm? \n\nIt seems that the answer is that something essential is baked-in to Assumption 4.1(b).  E.g., if $y$ can be both positive and negative but we take $a,\\sigma$ to both be positive we run in to issues; This will presumably violate (b)? Am I missing something? \n\nAlso, perhaps your point is that you *can* view it as an optimization scheme where youre finding the best fit in this model with constant second layer, and we don't really care about minimizing the loss because our goal is really to infer $\\theta_*$?  \n\n\n**Minor questions/comments + typos:**\n\n*unknown link* Contributions item 2, you state that the link function is unknown.  Is the assumption that the generative exponent mild? Can you access this given just the data/without knowing the link? What happens if it is misspecified?\n\n*Definition of model* In Eq 2.1 you define the model, but your first example, immediately after seems to not fit in to this framework due to overloaded notation. Perhaps choose different letters for the link *function*  and link *probability*?\n\n*Ln 83:* \"thus there is no...gap...\" I do not see how this is concluded. what you stated only implies that the algorithmic and information theoretic thresholds are the same order of magnitude. They can still be different, no?\n\n*Ln 176:* The notation $\\mathcal{N}(z^\\perp;0,I)$ should be defined.\n\n*L^p* The notation $\\stackrel{L^2(P)}{=}$ is a bit excessive. Perhaps just write = ?\n\n*Assumption 4.1* Please condense this. For example, instead of \"Both $\\psi(x,y)^2$ and $\\psi(x,y)^2x^2$ are square integrable...\" maybe just \"$\\psi(x,y),\\psi(x,y)\\cdot x \\in L^4(Q)$? Also, the remainder of Item (a) is more of a downstream consequence. Perhaps move this observation outside of the assumption environment. \n\n*Ln 254* \"Fourier coefficient\" Perhaps \"Hermite coefficient\"?\n*Ln 302* Netwok ---> Network ?\n\n*Ln1280* “follows from [a] Bernstien type...”", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The class of algorithms they present seem to capture other state-of-the-art online SGD schemes, such as \"batched reuse\" SGD (for generative exponent $\\leq  2$) and \"landscape smoothing\" (for generative exponent $\\geq 2$). The key difference in the latter case, is the use a tailored randomized objective that allows them to improve the rates down to the SQ lower bound, as opposed to the CSQ bound, which is a substantial improvement.", "weaknesses": "*Content*:  The algorithm for generative exponent > 2 seems quite tailored to the problem. You need to know the generative exponent of the, nominally unknown, link function. See questions below.\n\n\n*Presentation:*  My main concern with this paper is the presentation. While globally, the paper is reasonably well-written, it could do with a thorough round of editing. I had trouble interpreting essential aspects of this paper.  I have tried to made precise suggestions in \"Questions\" below.\n\n*Correctness:* The paper seems plausibly correct, though the sketch presented in Appendix D appears to have a flaw? Unfortunately given the timescale of refereeing, I could not find a fix to this on my own. I'm sure the authors will find a quick fix. See \"Questions\" below. [I will retract this comment, upon clarification from the authors during the discussion period.]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)