Learning single index models via harmonic decomposition
Authors: Nirmit Joshi
Hugo Koubbi
Theodor Misiakiewicz
Nathan Srebro
Venue: NeurIPS 2025 poster ()
Keywords: single-index models
statistical and computational complexity
Primary area: theory
TL;DR: We revisit the single-index models and argue that spherical harmonics, not Hermite polynomials, are a natural basis. We characterize the complexity for any spherically symmetric input measure, & provide several new insights for the Gaussian case.

Abstract: We study the problem of learning single-index models, where the label $y \in \mathbb{R}$ depends on the input $\boldsymbol{x} \in \mathbb{R}^d$ only through an unknown one-dimensional projection $\langle \boldsymbol{w_*}, \boldsymbol{x} \rangle$. Prior work has shown that under Gaussian inputs, the statistical and computational complexity of recovering $\boldsymbol{w}_*$ is governed by the Hermite expansion of the link function. In this paper, we propose a new perspective: we argue that *spherical harmonics*---rather than *Hermite polynomials*---provide the natural basis for this problem, as they capture its intrinsic \textit{rotational symmetry}. Building on this insight, we characterize the complexity of learning single-index models under arbitrary spherically symmetric input distributions. We introduce two families of estimators---based on tensor-unfolding and online SGD---that respectively achieve either  optimal sample complexity or optimal runtime, and argue that estimators achieving both may not exist in general. When specialized to Gaussian inputs, our theory not only recovers and clarifies existing results but also reveals new phenomena that had previously been overlooked.

Learning single-index models via harmonic decomposition
Nirmit Joshi
Hugo Koubbi'
Toyota Technological Institute at Chicago nirmit@ttic.c edu
CEREMADE, UMR 7534,
Université Paris Dauphine PSL, Paris France koubbi @erededdeeemeeee... fr
Theodor Misiakiewicz
Nathan Srebro
Department of Statistics and Data Science Yale University theodor.mii www.siiiiiwwiczyaall edu
Toyota Technological Institute at Chicago nati@ttic.edu
Abstract
We study the problem of learning single-index models, where the label y E depends the input H only through unknown one-dimensional projection (w., x). Prior work has shown that under Gaussian inputs, the statistical and computational complexity of recovering w, is governed by the Hermite expansion the link function. In this paper, we propose a new perspective: we argue that spherical harmonics rather than Hermite polynomials oolyoomials--prvideee the natural basis for this problem, as they capture its intrinsic rotational symmetry. Building on this insight, characterize the complexity of learning single-index models under arbitrary spherically symmetric input distributions. We introduce two families estimators-baut based on tensor- unfolding and online SGD-tha respectively achieve either optimal sample complexity or optimal runtime, and argue that estimators achieving both may exist in general. When specialized to Gaussian inputs, our theory not only recovers and clarifies existing results but also reveals new phenomena that had previously been overlooked.
Introduction
Single-index models (SIMs)-als known as generalized linear models- are among the most widely studied models in statisties [20, 64, 49, 40]. They generalize linear regression by introducing nonlinearity through one-dimensional projection of the input. Due to their simplicity and flexibility, SIMs have become foundational in both (semi)parametric statistics [44, 58, 26] and machine learning [52, 51, 21]. In recent years, SIMs have also emerged prototypical models for exploring several key phenomena modern high-dimensional learning, including: (1) Statistical-to cotpiicaatt--cmmpuaattinne gaps, with close ties to problems such as phase retrieval [12, 66, 61, 62] and tensor PCA [67, 28]; (2) Non- convex optimization, including mulli-phass dynamics [76, 10, 79, 15] and landscape concentration [65]; and (3) Representation learning in neural networks trained via gradient descent, where SIMs offer a simplified yet informative setting for studying feature learning [68, 18, 79, 30, 31, 6].
Spurred by this growing interest, recent line of work has investigated the fundamental limits of learning SIMs high dimensions under Gaussian assumption [12, 66, 61, 10, 28, 29, 21]. In this setting, referred to as the Gaussian single-index model, one observes i.i.d. samples (Vi, ax) ~ P.... where
(u,z) ~ P...
N(O, L.) and x
(1)
Part this work was done while HK was a Visiting Assistant Researcher in the Department of Statistics and Data Science, Yale University.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

for an unknown unit vector w, E gd-1 and a fixed link distribution p E P()' x R), modeling the pair (Y, G) with G N(O, 1). Thus, the label y depends only on the one-dimensional projection (w,, of the input. The goal is to recover the latent direction w, from these observations.
In remarkable work, Damian et al. [29] provided sharp characterization of the statistical and compu- tational complexity of learning in this model. Their analysis relies on expanding the link distribution o in the orthonormal basis of Hermite polynomials [Hex]x20 that is, (G)
Ōkj for
G N(,, 1). They defined the generative exponent (GE) of p as
(p) arg min 1 ([xxl12200) 0 where (x) == Ep (G)(()
(2)
and showed that the optimal sample size m and runtime T for recovering w. from data (1) scales as (writing k,- (p) and assuming k. for simplicity)
= (d(
T= T=
(3)
The sample complexity is optimal among statistical query (SQ) and low-degree polynomial (LDP) algorithms (up to some additional sample-runtine trade-offs, see Remark 3.2), while the runtime is necessary simply to process m samples in d dimensions.
Several works have developed algorithms that progressively closed the gap to these optimal rates. In a seminal contribution, Ben Arous et al. [10] analyzed online stochastic gradient descent (SGD) on the single neuron model Hek, ((w, x)), and showed it recovers w. with suboptimal m (a(d--11)
and T @2(d To close this gap. Damian et al. [28] proposed a smoothing- baaoohiing--seddd modification of SGD inspired by the tensor PCA literature [19], which locally averages the loss landscape and achieves near-optimal m = (dttt/2) and T = (x(dk//2+)) Finally, the polylogarithiic factor in sample complexity was removed by Damian et al. [29] via a partial trace estimator again inspired by tensor PCA [47]-which which achieves
(dd and T (a(d' log(d)), thereby matching
the optimal rates in (3).
While these results yield sharp characterization of learning Gaussian SIMs in high dimensions, several conceptual gaps remain:
Why is the vanilla SGD algorithm suboptimal, with runtime d instead of the optimal dt./2+1? Why do methods such as landscape smoothing and partial trace estimators- both borrowed from the tensor PCA iiteature-achien optimal complexity*? ? And what role does the Gaussian assumption play in these results?
In this paper, we propose simple-and perhaps aurprising-ansveee answers to these questions. Our key observation is that the complexity of learning SIMs is governed not by Gaussianity itself, but by the problem's 's rotational symmetry. Specifically, the family {Pw : w E Sd-13 consists of all pushforwards under orthogonal transformations of the input, suggesting that optimal algorithms should respect this symmetry- that is, be equivariant under the action of the orthogonal group O.,-
This symmetry-basee perspective naturally leads to spherical harmonics-whih arise irreducible representations of Oa-as the appropriate basis for this problem, instead of Hermite polynomials. Adopting this basis not only clarifies the above questions, but also extends the theory beyond the Gaussian setting to arbitrary spherically symmetric distributions.
1.1 Summary of main results
In this paper, we characterize the sample and computational complexity of learning single-index models under general spherically symmetric input distributions. Let μ E P(IR)) be distribution invariant under orthogonal transformations, i.e.. R4 = for all R E OJ. Such distributions admit a polar decomposition æ rz, where the radius r = ||>|| μu, is independent of the direction 2 /|zl||2 Ta = dd-1. We define natural generalization of Gaussian SIMs (1), which we call spherical single-index models, specified by joint distribution Va2 E P(R3):
(Y, R, Z) ~ Vd: R~H, 1 Z ~ Ta,1
and Y R, Z) ~ val: R, Z),
2 An earlier notion- the information exponent- was was proposed in [40, 10]. See Appendix A.5 for discussion. Throughout, @a(-) hides polylogarithmic factors in d. 'Let us emphasize here that these algorithms fail to achieve optimal complexity for (slightly) more general
SIMs (see Section A.3). Thus an analogy to tensor PCA is not enough explain their success in this setting.

---

Subspace Va,
Sample optimal
Runtime optimal
Spectral algorithm d=
//22
m dV
T df
8=
d
df
log d
t=
[ i2
Harmonic tensor unfolding
Online SGD
de/2
d
d
8 3
log d
[E 1
Table 1: Summary of algorithms for learning spherical SIMs on each irreducible subspace Va,e, with their sample complexity m and runtime T. Here, the notation x hides constants that depend on and assumptions vd- The estimator in the left (resp. right) column matches the optimal sample complexity (resp. optimal runtime) predicted by the LDP (resp. SQ) lower bound (8). See Section for details and formal statements.
where Td, is the distribution of the first coordinate of z ~ Td- Samples are drawn according to:
(v) P...= x (r,
μr, @ Ta and vl z) va(-Ir, (w., 2));
(5)
for an unknown unit vector E S Thus, the label y may now depend on both (r; (w., z)), rather than only on the scalar projection (w,,, 2²) Unlike the Gaussian case, the conditional distribution va(-) R, Z) is allowed to depend on the ambient dimension d: our learning guarantees will hold for fixed Pa. with explicit (up to universal constants), non-asymptotic bounds.
We now summarize our main results on estimating w. from i.i.d. samples drawn from the spherical single-index model (5):
Harmonic decomposition and lower bounds. To characterize the complexity of learning in this setting, we exploit the decomposition of (S( into harmonic subspaces:
L
+ Va t=
nd. = = dimmdiiaaaaa O2(d')
(6)
where Va.e denotes the space of degree-l spherical harmonics. For each 2 1, we define the f-th Gegenbauer coefficient of va to be
Ea R) = E,, (Q:()))))))))())))))))) R],
where Qe E Va,E is the (normalized) degree-f Gegenbauer polynomial in (²-(-1, Td.1), with E7g, [Qe(Z)Qx(Z) dRt- We establish the following lower bounds the sample complexity m and runtime T for recovering w, using the low-degree polynomial (LDP) and statistical query (SQ) frameworks:
1/2
d/2
d3/2
}
inf d 222
A inf
T
d
(8)
ELe 12:
| 12
These bounds effectively decouple across irreducible subspaces: each term f. E in the infimum corresponds to lower bound for learning spherical SIMs using estimators restricted to the harmonic subspace Va,e, with matching upper bounds summarized in Table I. Note that ||Ea,ellæ> I 1 and can decay with thus, these lower bounds capture the competition between the dimensionality (d(d)) of Va and the 'signal strength' ||Ea,e 1 it carries about IP P.g.w..
Optimal algorithms and trade-offs. For each harmonic subspace Va,t, we construct: (1) sample- optimal estimator based either on spectral methods for & (1,2) (that also runtime (near-)oup )optmmaa
'Throughout the paper, we refer to polynomial time algorithms (see Remark 3.2), and refer to the infformttion-theorett optimal sample complexity otherwise.
as the optimal conjectural sample complexity for

---

Gaussian SIMs
Sample optimal
Runtime optimal
Spectral algorithm (l. = 1 if k. odd, I. 2 if k. even)
With ||=||2
x dt T / /2+1 log d
Harmonic tensor unfolding (l, = k.)
Online SGD (l. = k.) dh
Without |
/²2
T x d= logd
m
T x d'
Table 2: Summary of algorithms for learning Gaussian SIMs with generative exponent k, > 1, with without using the radial component | 2. Here, the notation x hides constants that depend only on the link distribution p. See Section 4 for details and formal statements.
or on tensor-unfolding of reproducing harmonic operators for estimator based on online SGD for & 2 3. Their complexities are summarized in Table 1.
and (2) runtime-optimal
IT.. This leads to simple strategy for learning spherical SIMs (5): identify lm. (samplc-optimal) (runtime-opp (runtime-optimal) optimal) as the degree minimizing the corresponding term in the lower bound (8), and apply
the matching algorithm from Table 1. Note that always have mm,. 2 IT..- If m,+ IT, E (1, the spectral algorithm achieves both optimal sample and runtime complexity. If lm. = IT, > 2. it remains open whether a single estimator can achieve both More generally, one can construct distributions for which lm,+ >> IT.., suggesting that algorithm simultaneously achieve optimal sample and runtime complexity in these cases. This stands in sharp contrast to Gaussian SIMs, where both complexities are always jointly achievable. Thus,
Additional sample-rumee rumtimee trade-offs appear when learning SIMs beyond the Gaussian setting.
The case of Gaussian inputs. We now specialize our results to the Gaussian single-inde model (I), where μ N(O, Ia) and vY, R, Z) p(Y, R Z) with generative exponent k. > 1. This yields particularly transparent picture:
(1) The optimal degrees lm.. IT.. are always either 1 (if k, is odd) or (if k, is even). with the spectral algorithm from Table achieving both optimal sample and runtime complexity (3). Thus, for any Gaussian SIMs, optimal algorithms lie in the harmonic subspaces Va,1 and Va.2, corresponding to degree-1 or 2 spherical harmonics in z = 2//|==/12-
(2) The SGD algorithm of [10] is dominated by the uig-frrquency harmonics Va.k,, while smoothing [28] reweights the loss landscape toward wwwfrreuency harmonics Va,1 Va The partial trace estimator [29] explicitly projects onto them. Both methods achieve optimal complexity by effectively exploiting these low-frequency components.
(3) We provide an alternative perspective for understanding the suboptimality of SGD: its optimization dynamics remains essentially unchanged when æ is replaced by its direction implying it does not exploit the radial component r = ||ø|||- We show that algorithms that ignore must incur a runtime complexity (dk In this sense, SGD is runtime-optimal among methods that rely solely on the directional component. To achieve the optimal runtime (d(dt-/2+1) one must exploit the radial componentevee though it carries no information about w, and asymptotically concentrates around r/vd + 1.
These results are summarized Table 2.
2 Setting and definitions
Throughout the paper, we assume our link functions Va are drawn from the following class: Definition (Spherical link functions). Let Ea denote the set of joint distributions Va on y x R>0 X
[-1, 1]. where y is arbitrary measurable space, such that the following hold:
'In fact, we show that for é even, harmonic tensor unfolding achieves both optimal sample and runtime complexity, with potential additional log(d) factor in sample complexity.

---

(i) The marginals of (Y, Z) ~ satisfy Z ~ Td,1 (the distribution of the first coordinate of 2 ~ Unif(Sd-1)) and R ~ Van E ((22o) not concentrated at O.
(ii) Let vao - U @ TuP1 be the product of marginals (Y, Rt and Z ~ Td,1- Then Va < Vá,0 (V
and the Radon-Nikodyn derivative satisfy dvá dva,
The corresponding spherical single-index model over (y.z) Y x Rd are then given by:
(y, x) ~ F F.....
x = (r, 2) ~ == Va. @ Td and yl(r, æ) ~ va(- (w,,
where æ rz is the polar decomposition with r ||ح| VdR and z x ||0||| Ta-
From V2.0 = n we define the null model Pu..0 = v. TTa. where (y, r) is independent of the direction 2. Note that assumption deg E (v8,0) is equivalent to dPey.we dvu,0
dPrg. E (P This ensures that the model has 'enough noise' in the label and excludes non-robust algorithms that can beat the lower bounds (3) in the noise-free setting (e.g.. see [74]).
Remark 2.1. Throughout this paper, we assume Va to be known. This assumption is mild in high dimensions, where the primary challenge lies in recovering w.. When Va is unknown, one can modify our algorithms and use random nonlinearities. See discussion in Appendix A.2.
= 1,2(50-1, Ta) denote the space of squared integrable functions the unit sphere, with inner-product (f.g) Eywr, [=)=) and norm ||
Harmonic decomposition. Let (2(( :=
1/2 This space admits the orthogonal decomposition (6), with Va, the subspace of degree-f spherical harmonics, that is. degree-f polynomials that are orthogonal (with respect to (:. 22)) to all polynomials with degree less than L. We refer to Appendix B for background on spherical harmonics.
We use this harmonic decomposition to expand the likelihood ratio of the model in L (P(PP,,,):
dP dPrs.w. vs.ww (y. 1+ + Σ (aeeuur)Qe(((u... 8=11
EY,e R) = E., (Qe R),
(10)
dP PP.2,0
where Qe 1- R is the normalized degree-f Gegenbauer polynomial. We denote |Ka,lle
the I,2 norm with respect to Va. The x². mutual information of ((Y, R). Z) under va is given by
[x2 [va] == xx= vall = 1 Ea,e., See Appendix A.2 for further details.
Lower bounds. We establish lower bounds within two standard frameworks: statistical query (SQ) and lew-degree polynomials (LDP) algorithms. Our lower bounds will hold for the weaker task of distinguishing the planted model P Pra.w. from the null P 0= i.e., the "detection" problem. These lower bounds directly imply lower bounds on our estimation problem.
For SQ algorithms A E SQ(g, T), with g query calls of tolerance т, we derive lower bounds on the query complexity q/7². Heuristically, this corresponds to a runtime lower bound of T 2 q/72, under the standard assumption that each query requires at least ((117²) samples to implement. While this connection informal, it is validated by our matching upper bounds: the actual runtime of our proposed estimators meets these SQ-based lower bounds, except for a minor discrepancy when f = 1, where a tighter bound md (the cost of processing m samples in d dimensions) applies.
For LDP lower bounds sample complexity, we work in asymptotic setting d - co. In this case, the bounds hold uniformly over sequences {va)dzn, with V/ E La satisfying the following mild condition (the model is 'solvable in polynomial time"):
Assumption 1. There exists p E such that the sequence {va]a21 satisfies M, (va) O2(dP/2)
We refer to Appendix C for background on SQ and LDP algorithms.
3 Learning spherical single-index models
Let (va]d21 be a sequence of spherical SIMs with va E La (Definition 1). Under mild conditions, the information eitormttion-thhorttic sample complexity for recovering w. is Oa(d) (see Appendix H), However,
5

---

polynomial-time algorithms may require significantly more samples- that is. the model exhibits a so-called computational-to- caatiiionnn----tttttttitttt to-statistical gap. We introduce the complexity parameters:
M. (va) := inf 121
Qa(ua) == inf
7d,
(11)
|
where we recall that n,d, = dim (Va.)) aa(d') and Ed,e is the f-th Gegenbauer coefficient of the likelihood ratio (10). These quantities govern the sample and query complexity lower bounds within the LDP and SQ frameworks respectively, as formalized in the following theorem:
Theorem (General lower bounds). Let {Pula21 be a sequence of spherical SIMs with va E La-
(i) (SQ runtime lower bound.) Any algorithm A E SQ T) that distinguishes between P Fgga and F v satisfies q/T² 2 (va).
(ii) (LDP sample lower bound.) Assume {va)a21 satisfy Assumption I. Then, under the low- degree conjecture, no polynomial-Time algorithu can distinguish Feggo. from P Pvg.0 unless (va))(( log(d) CP) for some universal constant C >> O.
The proof and detailed statements are provided in Appendix C.
Remark 3.1. The lower bounds in Theorem 1 are for the detection problem. A detection-recovery gap can appear in this model when the infinum is achieved at = 1 and vd/ 112= < d. In this case, the information-theoretis lower bound m = (d)(d) is tighter (Appendix H). Thus, the informal complexity lower bounds (8) stated in the introduction are obtained as follows: the sample complexity lower bound is the maximum of the iioomnation-theoreee
bound (dd) and (va),. while the runtime lower bound is the maximum of Q- (va) and d times the sample complexity lower bound-that is, the cost of processing this many samples.
Remark 3.2. Similarly to tensor PCA [16, 84], one can trade-off a factor D-0(1) less sample complexity for dS(D) more runtime. See Appendix C for the LDP lower bound with this explicit trade-off, and [29] for a discussion on how to construct higher-order tensors to match it. In this paper, we ignore these additional sample-runtime trade-off's and focus on matching the exponent in d in the sample complexity. We leave finer-grained analyses to future work.
Intuitively, these lower bounds decompose the problem into separate subproblems associated with each harmonic subspace Va.e- Each I 1 in (11) corresponds to the complexity of algorithms restricted to degree-E spherical harmonics in (see Appendix C for further discussion). Below, we introduce matching upper bounds for each subspace Va.e, summarized earlier in Table 1. These algorithms are stated with general transformations Te: : x I2 + R. For simplicity, we present our learning guarantees below under the following assumption:
Assumption 2. For va Ld and & 2 1, there exist Te: y x R20 - I and Ke >> such that ||Telle= = 1, TTellso Ke and Ev,, [Te(Y, R))x 2 KF " EE,,elle..
For Gaussian inputs (next section), Assumption 2 is satisfied with Ke only depending on p. In the appendices, we state our learning guarantees under weaker assumptions (with possible additional log factors), e.g., using Te = Ea,e//lEa, [a> under moment condition on &,,e-
Remark 3.3 (Weak to strong recovery). We further state our results below for the weak recovery task (úx, w. 2 1 1/4. Having achieved weak recovery, one can achieve strong recovery (w, w..) | 2 1-8, with arbitrary& > O. using an additional Oa(d/s) samples (information-thet thhooretic optimal) and aa(d? (s) muntime-simlane to prior works [10, 88, 28]-under mild assumptions. See discussion in Appendix A.2.
Spectral algorithm: For é E 2}, we present spectral estimators-similarr to [61, 66, 62, 29]- that achieve both optimal sample and runtime complexity. Given m samples (yi, a.)), these estimators are defined as:
w
T(gh
|
m
(E(m)
(SP-Alg)
==0 2
i = arg max wt Mw, w
M
Te( 2,27 Iz].
[E(m)

---

For & = 1. the estimator Do either achieves weak recovery directly or requires boosting as in [88, 28, 29]; we leave the description of the full algorithm to Appendix D. For 2, the leading eigenvector can be efficiently computed in runtime @a (d)) via power iteration.
Theorem (Spectral algorithm). Let Va E Ld and set Te as in Assumption 2. There exists C₁ 2 that only depends f such that for any 5 > 0, the ouiput in of the spectral estimator (SP-Alg) achieves ((i,, w.)) 1 2 1/4 with probability 1 when
d
t=1: ::
/log(1/6).
and T2 Cym d,
(12)
d
2 Ceri
(1
11 log log² (d/o)), and T C.m dloo(d).
||5d,2 l/,=
Furthermore, for - one can achieve better sample complexity under additional condition: the boosted estimator achieves (vo, w.)l
I 2 1/4 with probability 1 - when
Vd Vlog(1/5),
t=1: m Ces
and
T2 T2 Cam d.
(13)
||Ea,1 12:
The proof and detailed statement of this theorem can be found in Appendix D. For & and l|Ea.2 lI (log((())) -),, the additional factor (d) can be removed by following similar argument as in [66].
Online SGD algorithm: For l 3, we propose an online SGD algorithm inspired by [10] that achieves optimal runtime. We run projected online SGD on the population loss
Ep.g... (Te((,)r) r) - Qe((w, z)))² WES4-1
min
((,,)))))
(SGD-Alg)
with carefully chosen step size [10, 88). The number of samples in this algorithm corresponds to the number of SGD iterations, and the total runtime Oa(md)) cost of computing d-dimensional gradient at each iteration. Details can be found in Appendix E.
Theorem 3 (Online SGD algorithm). Lel va E Ea and set Te as Assumption There exists C 2 O that only depends l such that for any 8 >> O. the output w of the online SGD estimator (SGD-Alg) achieves (áo, w.) 2 1/4 with probability 1 when
d
2 3: m 2 CeN?
log(1/6),
and
T Cem-da
(14)
||Ea,el 22
The proof of this theorem follows by adapting the arguments in [10, 88] and can be found in Appendix E.
Harmonic tensor unfolding. For L 2 3, present tensor-unfolding algorithm inspired by the seminal work [67] on Tensor PCA, that achieves optimal sample complexity. We introduce a degree-E harmonic tensor He(z) E (TR((T))) (the space of symmetric f-tensors in d-dimensions). It is defined via the degree-E Gegenbauer polynomial as
Qe((w, 2)) (
86 He(()),
for all w E Sd-1
(15)
We provide explicit expression of H4 in Appendix F. This tensor can be seen as the projection of ot into the space of symmetric, trace-less tensors. In particular, has the reproducing property
6ek He(w).
Ez (Qx(ww z))H)(()]]
(16)
Vna,t
Given samples (y,, x.) P Prn... compute the empirical tensor
Tels., (z.) km(m
(17)
By the reproducing property (16), the expectation under Puy,,. of this tensor is proportional to He (w.),, which has principal component @e To extract this component, will consider two
7

---

different estimators. We follow [67] and construct the unfolded matrix of f E (R2))((+))) denoted , E IR xdd with entries
J (T) (1 = T in where we identify (f1....,ir) if) with Ej=(ii (ig 1)di-1
For é 2 3 even, our first estimator computes 81 2,/22 (T) Rdlt/2 the top left singular
vector of Mat 22/2)2 E gdd x via power iteration, and return
i = V 8i Mat, (ats)a.//(TT))
(TU-Alg-b)
where the mapping Vec; : Rd + gd-1 1 applied to u Rd returns the top left singular vector the matrix U E [Rxxa" with entries U (1.(2......))) (6)
When l odd, however, the above estimator (TU-Alg-b) (now with = 18/2] and J = [t/2]) requires m x /IL, samples, which is suboptimal by factor d=/2, This is due to the covariance structure of the Harmonic tensor (z)x): similar problem, with same suboptimality, arises for tensor PCA with symmetric noise [67] (if the noise is not symmetric and all entries are assumed independent, this algorithm achieves the optimal threshold in tensor PCA [48]).
[(e - 1)/2] and Here, we modify (TU-Alg-b) by removing the diagonal elements. We set J = [(e + 1)/2], and introduce the matrix
m
M Mat, , (T) (T)
Tely r4) ) (H(((()))
m
(18)
(H((z))) dd
For l 2 3, our second estimator computes 81 (M) IRd' the top left singular vector of M, via power iteration, and return
à = Vec, (s) (M)),
Vec;
(TU-Alg)
where the mapping Vec, is as defined above.
For both estimators (TU-Alg-b) and (TU-Alg). we show that given enough samples, the leading eigen- vector $1 is well approximated by w and the vectorization operation returns good approximation of w.. The runtime of this algorithm is dominated by the computation of the top eigenvector s (MM via power iteration, which requires @m(m(d' + dd) log(d)) operations.
Theorem 4 (Harmonic tensor unfolding). Let va E La and set Te as in Assumption There exist ce, C. 2 0 that only depend on l such that the following holds.
(i) For > 3 even, the output io of the balanced harmonic tensor unfolding algorithm (TU-Alg-b) achieves ((úc, w.Yl Yl 2 1/4 with probability when
de/2
l even: m 2 Ceni |Ea,
(1 (1+ IlEa,ellra log(d/6)). and T Cem L log(d). (d).
(ii) For 22 3, the output i of the harmonic tensor unfolding algorithm (TU-Alg) achieves (w, w-)l 1 2 1/4 with probability 1 - e - when
d2/2
even:
2
and
T 2 C.m / log(d),
[|a,e
12
d²12
odd
m > C
and
T Cam 2/211/2 log(d).
12
The proof of this theorem be found in Appendix F.
Remark 3.4. A computationally more efficient partial trace estimator was proposed to recover the principal component in symmetric tensor PCA [47, 29]. Here, however, Hz(=) (contraction of two indices) projects onto Hz-2(z) and lower order harmonics, which defeats the purpose of our estimator (and lead to suboptimal performance if l is chosen to be the optimal degree).

---

Optimal algorithms.
We define the sample-optimal and runtime-optmal degrees as
Bad
Tdd.E
m,+ arg min
and IT,+ = arg min
(19)
Ea.ell2
E21 ||E
E21
Then choosing the corresponding algorithm associated to degree mm.. (resp. Ir,)) achieves the optimal sample (resp. runtime) complexity among SQ and LDP algorithms. For m., = IT.. 2 3 odd, we leave open the possibility that an algorithm achieves both sample and runtime complexity. More generally, in Appendix A.2, we show how construct distributions with arbitrary large gaps lm, IT. As discussed in the introduction, this suggest that no single estimator can achieve both optimal complexities in this case, and sample-runtime trade-offs appear.
Specifically, our example proceeds as follows. Let 2 be an arbitrary integer. The label is a mixture of two single-indes index models: Y|R, Z V/,a with probability d 2k and Y Y Z V2,d with probability 1 d 2k, The two models V1,d and V2,d chosen such that optimal sample complexity achieved at l..m = 10k (thanks to 122d) and optimal runtime is achieved at I,, T = 4k (thanks to v1.d). Thus, in this example:
Sample-optimal algorithm: the harmonic tensor unfolding algorithm at I..m = 10k achieves
m = oa (dkk), and T= θ. (d2tk).
Runtime-optimal algorithm: the harmonic tensor unfolding algorithm at I.,T 4k achieves
Oa (dok), and T 0₂ (d
4 Learning Gaussian single-index models
We now specialize our results to the case of Gaussian single-index model (1). Recall that Va, == Xa and (Y R, Z) p( 7). We assume below that p fixed link distribution of generative exponent k. > (defined in Eq. (2)). In particular, the notations x and S only hide constants that depend on p. From Section 3, we need decompose p into the spherical harmonics basis. Using the decomposition of Hermite polynomials into Gegenbauer polynomials proved in Appendix B:
k
Hej ((W,,))
(e.e(l
18r.elliA(aa = Oald (a-d-(1-01)3) (20)
ビ=
t=k mod
we show the following bounds on the é-th Gegenbauer coefficient Ea, associated to Lemma 1. For all & S. k., we have
I1Ea.e 12:= = d- (k, 81/2 for E = k. mod? 2 and ||Ea,elli= S dd-(k--et))) -4+1/2 for E $ k. mod 2.
Plugging these estimates in Theorem we deduce the following complexity lower bounds and associated optimal degrees for learning p. For sample complexity, we obtain
d²/2
de/2
2 (va) = inf Ez1
inf mod 2
inf
dk./2 dh./2
dk 0/2
E1
tk mod
and any f & k, with == k, mod 2 is sample optimal (for asymptotic rates). For runtime, we get
de
de
Q. (va) x inf
inf
inf f21
(k.+2 = 2[(k.+1)/2)
ll2. E2
F21
d- 00/2
t=k. mod
t=k. mod
and only = (k, odd) or l = 2 (k, even) are runtime optimal. Thus, although p has vanishing projection on degree & < k, harmonic spaces, this is offset by smaller nd, dim (Va,e, and we should always choose lT,. lm,, E {1,2] (depending on k, parity). particular, we can use our general spectral algorithm (SP-Alg) to leamn with optimal sample and runtime complexity:
Corollary 1. The estimator (SP-Alg) achieves optimal (2( log(d)).
Oa(d and T

---

Estimating using only directional information. Consider the same Gaussian SIM with link function p. but suppose we only observe the pair (y, z), i... the label and the direction of the input. This defines new spherical SIM with fixed radius va, ōn=1 and conditional distribution
Val R, 2) Eg()(Y( where R~ Xd-
For example, this setting corresponds to the common practice in statistics and machine learning of normalizing input vectors to unit norm. We show below that, Gaussian single-index models, such normalization necessarily leads to quadratic increase in runtime complexity. Under this model, the Gegenbauer coefficients of va scale as:
Lemma 2. For all & S k., we have
I| = -k. for E k, mod 2 and
||Ea, 12 S dk- for l & k, mod 2.
Similarly as above, is easy to verify that the sample-optimal degree is now always lm,+ k. while the runtime-optimal degrees are l = k. mod 2, l S k.. The new complexity lower bounds are given by
dh.
Thus, while the sample complexity stays the same, the optimal runtime goes from (5-/2+1 to d' Again, use our general estimators from Section 3 to match these lower bounds:
Corollary 2. For any 3 S L S k.. l = k, mod 2, estimator (SGD-Alg) achieves m Oa(d". and T -. For = k., estimator (TU-Alg) achieves
(a(dh./2) /2) and T = Oa log(
log(d))
The proofs of all the results in this section can be found in Appendix G. We also discuss the general phenomenology underlying algorithms for Gaussian LiMs-namelyy vanilla SGD [10], landscape smoothing [28]. and partial trace [29] in Appendices A.3 and A.4.
Conclusion
In this paper, we introduced generalization of Gaussian single-index models, which termed spherical single-index models, that allows for arbitrary spherically symmetric input distributions and general dependence of the label on the norm of the input. We provided sharp characterization of both the statistical and computational complexity of learning in these models. A key insight is that the SQ and LDP lower bounds decouple across the irreducible subspaces Va,e of degree- spherical harmonics. For each such subspaces, we established two matching estimators: an online SGD algorithm that achieves the optimal runtime among SQ algorithms, and harmonic tensor unfolding estimators that achieves the optimal sample complexity among LDP algorithms. The optimal algorithm is then obtained by selecting the degree lm, IT, that minimizes sample or runtime complexity respectively. In general, these may differ-i.e.. lm.. * implyinng that no single estimator can achieve both optimal sample and runtime complexity. We applied this framework to the Gaussian case, recovering and unifying prior results while clarifying the role of the harmonic decomposition in their performance. Below, we discuss two directions for future work.
Multi-index models. A natural extension is to multi-inder models, where the label depends on low-dimensional projection y ~ p(- !! with W. E IRdx* an unknown rank-s subspace. Recent work [2. 17] has shown that learning in such models proceeds via sequential recovery of directions in the signal subspace. Unlike the single-inde index case wheeeewweeeee degree- 1 and 2 spherical harmonics suffice-mull multi-index models require higher-order harmonics. For instance, the multivariate Hermite monomial 2 21 I' = 22 .-. 2, is degree- spherical harmonic with no projection onto lower-degree spaces. In such cases, landscape smoothing and partial trace estimators fail, and the harmonic tensor unfolding estimator on Va., becomes necessary. We expect our harmonic framework to extend naturally the spherical multi-index setting, and leave this direction to future work.
General symmetry groups. Finally, our lower bounds in Theorem 1-and and the decoupling into irreducible subspaces-hhines on Schur's orthogonality relations for the action representation of O₂ on (Sd-)..) More broadly, the Peter-Weyl theorem ensures that such decompositions exist for any compact group. This suggests that our bounds, and the decoupling into irreducible representations, hold beyond SIMs and Og. We hope to explore this broader setting in future work.
10

---

References
[1] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions two-layer neural networks. In Conference on Learning Theory, pages 4782-4887 PMLR, 2022.
[2] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural net- works: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552-2623. PMLR, 2023.
[3] Emmanuel Abbe, Enric Boix-Adsera Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems, 01226999-27000 2021.
[4] Anima Anandkumar, Yuan Deng, Rong Ge, and Hossein Mobahi. Homotopy analysis for tensor pea. In Conference on Learning Theory, pages 79-104. PMLR, 2017.
[5] Alexandr Andoni, Daniel Hsu, Kevin Shi, and Xiaorui Sun. Correspondence retrieval. In Conference Learning Theory, pages 105-126. PMLR, 2017.
[6] Luca Arnaoold, Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. Online learning and information exponents: On the importance batch size, and time/complexity tradeoffs. arXiv preprini urXiv:2406.02/55 2024.
[7] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405. 15459, 2024.
[8] Luca Arnaooldi, Ludovic Stephan, Florent Krzakala, and Bruno Lourciro. From high- dimensional & mean-field dynamics to dimensionless odes: A unifying approach to sgd in two-layers networks. In The Thirty Sixth Annual Conference Learning Theory, pages 1199-1227. PMLR, 2023.
[9] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor pea. The Annals of Probability, 48(4):2052-200 2087, 2020.
[10] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1-51, 2021.
[11] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932-37946, 2022.
[12] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12):5451-544 2019.
[13] William Beckner. Sobolev inequalities, the poisson semigroup, and analysis on the sphere sn. Proceedings of the National Academy of Sciences, 89(11):488 (0(11):8116- 484466488999 1992.
[14] Gérard Ben Arous, Daniel Zhengyu Huang, and Jiaoyang Huang. Long random matrices and tensor unfolding. The Annals of Applied Probability, 33(6H))5553-578) 2023.
[15] Raphaël Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. Foundations of Computational Mathematics, pages 1-84, 2024.
[16] Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Sum-of -fin-rrrs certificates for maxima of random tensors on the sphere. arXiv preprint arXiv:1605, h0t.:1605.00033,, 2016.
[17] Alberto Bietti, Joan Bruna, and Loucas Pillaud- Vivien. On learning gaussian multi-indes models with gradient flow. Communications in Pure and Applied Mathematics, 2025.

---

[18] Alberto Bietti, Joan Bruna, Clayton Sanford. and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768- 9783, 2022.
[19] Giulio Biroli, Chiara Cammarota, and Federico Ricci-Tersenghi. How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor pca. Journal of Physics A: Mathematical and Theoretical, 53(17):174003,, 2020.
[20] George EP Box and David R Cox. An analysis of transformations. Journal of the Royal Statistical Society Series B: Statistical Methodology, 26(2):211-243, 1964.
[21] Joan Bruna and Daniel Hsu. Survey algorithms for multi-index models. arXiv preprint arXiv:2504.05426 pages 1-14, 2025.
[22] Nader H Bshouty and Vitaly Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2(Feb):359-395. 2002.
[23] Sitan Chen and Raghu Meka. Learning polynomials in few relevant dimensions. In Conference on Learning Theory, pages 1 1161-1227. PMLR, 2020.
[24] Theodore Chihara. An introduction orthogonal polynomials. Courier Corporation, 201 1.
[25] Feng Dai. Approximation theory and harmonic analysis on spheres and balls. Springer, 2013.
[26] Arnak S Dalalyan, Anatoly Juditsky, and Vladimir Spokoiny, A new algorithm for estimating the effective dimension dimension-reduction reduction subspace. The Journal of Machine Learning Research, 9:1647-1678, 2008
[27] Alex Damian, Jason D Lee, and Joan Bruna. The generative leap: Sharp sample complexity for efficiently learning gaussian multi-index models. arXiv preprint arXiv:2506..05500 2025.
(28) Alex Damian, Eshaan Nichani, Rong Ge, and Jason D) Lee. Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. Advances in Neural Information Processing Systems, 36:1-39, 2024.
[29] Alex Damian, Loucas Fillaud-Vivien, Jason Lee, and Joan Bruna. caaputtaioonalstatiitiin gaps in gaussian single-index models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1262-1262. PMLR, 2024.
[30] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn represen- tations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.
[31] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two- layer neural networks learn, one (giant) step time. arXiv preprint arXiv:2305.182777 18270, pages 1 1-65, 2023.
[32] Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint 00Xiv22402.03220, pages 1-30, 2024.
[33] Victor H. de Peña and Stephen Montgomery-SSme Smith. Decoupling inequalities for the tail probabilities of multivariate u-statistics, 1999.
[34] Leonardo Defilippis, Yatin Dandi, Pierre Mergny, Florent Krzakala. and Bruno Loureiro. Optimal spectral transitions in nigh-dimensional multi-index models. arXiv preprint 2.Xiv:2502.02545. 2025.
[35] Ilias Diakonikolas, Daniel M Kane, Pasin Manurangsi, and Lisheng Ren. Hardness of learning a single neuron with adversarial label noise. In Proceedings of the 35th Conference on Learning Theory (COLT2022), volume 151 of Proceedings of Machine Learning Research, 2022.
12

---

[36] Ilias Diakonikolas, Daniel M Kane, and Lisheng Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In Proceed- ings of the 40th International Conference on Machine Learning (ICM12023), volume 202 of Proceedings of Machine Learning Research, 2023.
[37] Ilas Diakonikolas, Daniel M Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020.
[38] Iaas Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning a single neuron with adversarial label noise via gradient descent. In Proceedings of the 35th Conference on Learning Theory (COLT 2022), volume 178 of Proceedings of Machine Learning Research, 2022.
[39] NIST Digital Library of Mathematical Functions. https::/ .nist. gov// Release 1.2.3 of 2024-12-15. F. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
[40] Rishabh Dudeja and Daniel Hsu. Learning single-index models in gaussian space. In Conference On Learning Theory, pages 1887-1930. PMLR, 2018.
[41] Rishabh Dudeja and Daniel Hsu. Statistical computaialllommuuatioonnall trade-offs in tensor pea and related problems via communication complexity. The Annals of Statistics, 52(1):131-156, 2024.
[42] Surbhi Goel, Anand Gollakota, and Adam R Klivans. Statistical -ueey lower bounds via functional gradients. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020.
[43] Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. Advances in neural information processing systems, 32, 2019.
[44] Wolfgang Härdle and Thomas M Stoker. Investigating smooth multiple regression by the method of average derivatives. Journal of the American statistical Association, 84(408):986-995, 1989.
[45] Samuel Hopkins. Statistical inference and the sum of squares method. PhD thesis, Corelll University, 2018
[46] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of -f-uurrrsseees for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720-731. IEEE, 2017.
[47] Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 178-191, 2016.
[48] Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 956-1006, Paris, France, 03-06 Jul 2015. PMLR.
[49] Hidehiko Ichimura. Semiparametric least squares (sls) and weighted sIs estimation of single- index models. Journal of econometricy, 58(1-2):71-120, 1993.
[50] Nirmit Joshi, Theodor Misiakiewiez, and Nati Srebro. On the complexity of learning sparse functions with statistical and gradient queries. Advances in Neural Information Processing Systems, 37:1031 103244, 2024.
[51] Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of general- ized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24:1-17, 2011.
13

---

[52] Adam Tauman Kalai and Ravi Sastry, The isotron algorithm: nigh-dimenssioal isotonic regression. In COLT, volume 1, page 9, 2009.
[53] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 1566);983-1066 1998.
[54] Filip Kovačević, Yihan Zhang, and Marco Mondelli. Spectral estimators for multi-index models: Precise asymptotics and optimal weak recovery. arXiv preprint arXiv:2502.01588, 2025.
[55] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1-50. Springer, 2019.
[56] Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low- dimensional polynomials with sgd near the information- theorreticcc limit. Advances in Neural Information Processing Systems, 37:587 16-5856, 2024.
[57] Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborová. Statisti- cal and computational phase transitions in spiked tensor estimation. In 2017 ieee international symposium on information theory (isit), pages 511-515. IEEE, 2017.
[58] Ker-Chau Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, 366414):3163322 1991.
[59] Shuyao Li, Sushrut Karmalkar, Ilias Diakonikolas, and Jelena Diakonikolas. Learning single neuron robustly distributional shifts and adversarial label noise. Advances in Neural Information Processing Systems, 21177733366742,222444
[60] Juan Carlos López Carreño, Rosalba Mendoza Suárez, and Jairo Alonso Mendoza S. Connection between the hermite and gegenbauer polynomials using the lewanowicz method. International Journal of Mathematics & Computer Science, 18(4):1-10, 2023.
[61] Yue M Lu and Gen Li. Phase transitions of spectral initialization for high- nigh-dimensiooal non- convex estimation. Information and Inference: Journal of the IMA, 9(3): 2020.
[62] Antoine Maillard, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase retrieval in high dimensions: Statistical and computational phase transitions. Advances in Neural Information Processing Systems, 33: 13:11071-11882 2020.
[63] Pierre Marion and Raphaël Berthier. Leveraging the two-timescale regime to demonstrate convergence of neural networks. Advances Neural Information Processing Systems, 36:64996- 65029, 2023.
[64] Peter McCullagh. Generalized linear models. European Journal of Operational Research, 16(3):285-292, 1984.
[65] Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 4666A)::747-2774, 2018.
[66] Marco Mondelli and Andrea Montanari. Fundamental limits of weak recovery with applications to phase retrieval. In Conference On Learning Theory, pages 1445-145H PMLR, 2018.
[67] Andrea Montanari and Emile Richard. statistical model for tensor pea. Advances in neural information processing systems, 27:1-30, 2014.
[68] Alireza
Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu. Neural networks efficiently learn low-dimensional representations with sgd. arXiv preprint arXiv:2209. /4863, 2022.
[69] Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub- optimality of pea i: Spiked random matrix models. The Annals of Statistics, 16(5):441-2451, 2018.
14

---

[70] Loucas Pillaud-Vivien and Adrien Schertzer, Joint learning in the gaussian single index model, 2025.
[71] Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557, pages 1-21, 2020.
[72] Stefano Sarao Mannelli, Eric Handen-Eijnden and Lenka Zdeborová. Optimization and gener- alization of shallow neural networks with quadratic activation functions. Advances in Neural Information Processing Systems,
2020.
[73] Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 1033);1833-1888 2022.
[74] Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. Advances in neural information processing systems, 34:29602-2999 29615, 2021.
[75] Gabor Szeg. Orthogonal polynomials, volume 23, American Mathematical Soc., 1939.
[76] Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with arbitrary initial- ization solves non-smooth, non-convex phase retrieval. Journal of Machine Learning Research, 24(58):1-47, 2023.
[77] Emanuele Troiani, Yatin Dandi, Leonardo Detilippis, Lenka Zdeborová, Bruno Loureiro, and Florent Krzakala. Fundamental limits of weak learnability in high-dimensional multi-index models, arXiv preprint 1.Xx::2405.154800 2024.
[78] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ Machine Learning, 811-2)11-330 2015.
[79] Rodrigo Veiga, Ludovic Stephan, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase diagram of stochastic gradient descent in high-dimensional two-layer neural networks. Advances in Neural Information Processing Systems, 01222244-23255 2022.
[80] Roman Vershynin. #ligh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[81] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[82) Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. Sample and com- putationally efficient robust learning of gaussian single-index models. Advances in Neural Information Processing Systems, 37:58376-58422, 2024.
[83] Alexander S Wein. Computational complexity of statisties: New insights from low-degree polynomials. arXiv:2506. 2025.
[84] Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pea. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1446-1468. IEEF, 2019.
[85] Wikipedia contributors. Gegenbauer polynomials - Wikkpediia, the free encyclopedia, 2024. [Online; accessed 28- December-2024,
[86] Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning single-index models via alignment sharpness. arXiv preprint arXiv: 2024.
[87] Qinqing Zheng and Ryota Tomioka. Interpolating convex and non-convex tensor decompositions via the subspace norm. Advances in Neural Information Processing Systems, 28, 2015.
[88] Aaron Zweig, Loucas Pillaud-Vivien, and Joan Bruna. On single-index models beyond gaussian data. Advances in Neural Information Processing Systems, 36:10210-10022, 2023.
15

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper the relevant information is Not Available.
Please provide short (1-2 sentence) justificaion right after your answer (even for NA).
The checklist answers an integral part of your paper submission. They are visible the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] " provided a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way,
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, our paper makes an accurate claims the abstract and introduction. We describe our results accurately.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide sufficient discussion on the limitations of our results and under which situations they apply.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We specify all the assumptions that required for our results hold. The proofs are all provided in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
17

---

Justification:
There are no experimental results, as this is theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
There are no experimental results, as this is a theory paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https: /Coo/eubdiiiiccccc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
18

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
There are no experimental results, this is theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experimental results, as this is a theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: There experimental results, this is theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
19

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://wuursssccpppiiiiiccc csQuidelines:
Answer: [Yes]
Justification: We have conducted research and presented our work in accordance with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There direct societal impact of work that aware of.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
20

---

Justification:
There are no such risks that we are aware of.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, we cite all the relevant works to be acknowledged to establish our results.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
21

---

Answer: [NA]
Justification: As this is theory paper with no such crowdsourcing involved on human related subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: As this is theory paper with such crowdsourcing involved on human related subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
This paper does not involve the use of LLMs for our scientific methodologies.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non nta-standard components.
Please refer to LLM policy (https: pottps://ntt /ttaas/////eueree for what should or should not be described.
/LLM)
22

---

Supplementary Material for the paper "Learning single-index models via harmonic decomposition"
Contents
1 Introduction
1.1 1Smmmry of main results
2 Setting and definitions
3 Learning spherical single-index models
4
Learning Gaussian single-index models
Conclusion
10
References
11
Additional discussions and details from the main text
24
A.1
Related work
24
A.2 Discussion on learning spherical SIMs
25
A.3 Revisiting vanilla SGD, landscape smoothing, and partial trace for Gaussian SIMs
27
A.4 Discussion on Gaussian SIM phenomenology
29
A.5 Correlation queries and the information exponent
30
Harmonic analysis on the sphere
B.1 Spherical harmonics, Gegenbauer and Hermite polynomials....
31
B.2 Harmonic decomposition of Hermite into Gegenbauer polynomials
32
B.3 Proof of Proposition?
35
C Statistical Query (SQ) and Low-Degree Polynomial (LDP) lower bounds
37
C.I Statistical Query lower bounds
37
C.I.1 Proof Lemma
38
C.2 Low-Degree Polynomial lower bounds
39
C.2.1 Proof of Theorem
41
Spectral estimators
42
D.I Analysis of {
42
D.2 Analysis for (
45
D.3 Boosting the overlap to achieve weak recovery.
48
E Online SGD estimator
50
Harmonic tensor unfolding
56
F.I Algorithms and guarantees
56
23

---

F22
Notations
57
E3
Harmonic tensors and their properties
58
E44
Proof of Theorem
60
F.5
Proof of Theorem 9
62
F6 Runtime of the tensor unfolding algorithm
65
F7
Additional discussions
65
G Proofs for Gaussian SIMs
67
H Information--heoretic sample complexity
72
H.I Information theoretic lower-bound
72
H.2 Information theoretic upper-bound
73
I Additional technical results
75
A
Additional discussions and details from the main text
A.1 Related work
The problem of learning single and multi-inder models has long history in statistics and machine learning. We refer the reader to the recent survey [21] and references therein for more thorough account of this rich history. Early work showed that SIMs with monotonic link function only require n = (d))) samples to learn even in the distribution-free setting, using perceptron-lite algorithms [52, 51]. For non-monotonic link functions with generative exponent less of equal to 2, such as phase retrieval y = (w,, x² + E, [12, 62] established the cetemaationtthhooeee limits, including the asymptotic MMSE, in the proportional regime
n/d. In particular, using the conjectured optimality of approximate message passing (AMP) algorithm, they showed that ceissiial--cmpuuatiionn gaps appear in this model, that is, there exists algorithmic threshold that, conjecturally, no polynomial -time algorithm succeeds when air < CALG [62, 66, 61] proposed spectral algorithms that match the algorithmic threshold, with [62] explaining how these spectral methods can be viewed as linearizations of AMP algorithms. In parallel lines of work, [23] and references therein proposed a number of algorithms to learn single and multi-index models, [38, 59, 86, 82] studied the problem of robustly learning a single index model, [37, 42] demonstrated near-optimal SQ lower bounds for learning ReLUs and halfspaces under Gaussian marginals, [36. 35] established cryptographic or worst-case hardness of learning single ReLU neuron, and [5. 74] showed in the noise-free setting that some lattice-bases based algorithms can vastly outperform SQ lower bounds. We further emphasize that in the multi-index case, the picture is much richer than in the single-index case: optimal learning happens through an adaptive multi-phase process [3, 1, 2, 17]. Recent work have explored optimal learning of Gaussian multi-index models the proportional scaling [23, 77, 34, 54] and in the polynomial scaling [27]. We leave the application of our harmonic framework to the multi-index case to future work.
OALGG > Opr-the the information-theoretie threshold
number of works have studied learning SIMs with gradient algorithms, and in particular, gradient- trained neural networks. [72, 76] studied GD and online SGD for phase retrieval. The notion of an information exponent, which characterizes the sample complexity of learning Gaussian single-index models via online SGD on the square loss, was introduced by [10], sparking a series of follow-up studies [43, 79, 8, 88, 6, 70]. A separate line of research investigates how neural networks can learn in just one gradient step [11, 31]. two-timescale approach has also been proposed in [15], and subsequently applied in [17, 63] to analyze convergence of gradient flow dynamics in learning multi-index models. This information exponent characterizes the complexity learning SIMs with CSQ algorithms. [32, 56, 7, 50] showed that one can outperform this information exponent by doing multi-pass gradient descent or by changing the loss function. However, we expect these algorithms to still fall under the SQ framework and be lower bounded by the generative exponent.
24

---

As pointed out previously [28, 29], learning single-index models is deeply connected to tensor PCA [67]. Tensor PCA exhibits statistical-come computational gap for & - [67, 69, 40, 41, 48, 46, 55], and its algorithmic picture is remarkably similar to single-index models, with a correspondence between their ifformation-theoree
algorithmic, and local-search thresholds. Montanari and Richard [67] proposes power iteration and tensor unfolding to solve tensor PCA. They conjectured that the algorithmic threshold should be given by 3 2 d(k=2)/4, and proves algorithmic achievability with 3 ž d((k/27-1)/2 using tensor unfolding. They show that local algorithms like tensor power iteration may require even higher SNR of / Z d(k=2)/2, subsequently investigated in [57, 9]. The optimal algorithmic threshold is achieved by number of algorithms: Sum-Of-Square, [47, 45], partial trace
algorithm [47], homotopy method [4] for k = 3, landscape smoothing introduced by [19], and tensor unfolding [87. 14].
Finally, in a concurrent and independent work, [27] introduced an (unbalanced) tensor unfolding estimator very similar to (18)- with Hermite tensor instead of harmonic tensor- in the context of learning Gaussian multi-index models. This method achieves sharp sample complexity of n ž d2nk" /2, where k* is the leap generative exponent of the link function.
A.2 Discussion on learning spherical SIMs
Likelihood ratio. In our Definition 1, we consider spherical SIMs such that Va < vao0 and the associated Madon-Nikodym derivative satisfies ratio in (v2,)) into the Gegenhauer hasis:
||
dea,o L2((a))) < co. We can expand the likelihood
dug
dya
r,
14 rQe()))
(21)
dvaoo
2=1
where
dud (Y, R. ())x = EEy [Q:(Z)|Y,
(Y,e(R := EZ
dvao
The mutual -mmutull information divergence of ((Y, Z) is given by
( dvd
27
Txa [va] = -Eua.
Σ Ea.ellz.
Link function Va unknown. When va unknown, similar to [29], one can still hope to learn the planted direction w., as long as it is possible to approximate the non-linearity Te(,, using random linear combinations of the first few orthogonal functions
basis of L L23(vayy Similar [29, Assumption 4.1] ] this requires assuming that the expansion of Te has non-vanishing mass on these first few basis functions of 2 (v).Y,R) Intuitively, this amounts to a 'smoothness' condition on the link function va. We leave this as a direction for future work.
Weak to strong recovery. In our framework, it is only meaningful to restrict ourselves to the sequence [va]a>1 such that I [/s] is non-vanishing and there exists a component / > (independent of d) such that [<a,ellza > c >> O. For example, in Gaussian SIMs with the generative exponent k., such an f = k. always (both with or without using the norm). Under this mild assumption, we can carry out the online SGD algorithm similar to the final phase algorithms of [10, 28, 88] but now on the frequency Qt- As we have non non-vanishoe vanishing signal [|Ea.ell = Pa(1), we can achieve strong recovery (xx, w.)l 2 1 - & using (dde)) samples, and so O /e) runtime hiding constants in E.
Spherical SIMS with sample-runtine trade-off. Below we show how to construct examples of spherical single-index models with lm,+ > IT,.. We construct va such that it is a mixture of two spherical SIMs. Consider vf and v(2) associated to Gaussian SIMs with generative exponents kj and lig, where we marginalized over the norm (that is, R = 1). In particular, as shown in [29, Theorem 5. we can choose the Gaussian SIMS to be y(d = o, R (7N(),,N(O, 1). with [|o, < oo
and sufficiently large such that C-1 0
( (v) (w)/v( (2) (v) S C. (2)
Assume that (Y, 2) ~ Va (recall R = here, and we remove it for elarity) is drawn with probability
a from v/j and with probability 1 - a from / where 0 is a constant chosen later. In
25

---

this model, we have
= = =,
where
( - (0
and
( d-a + (da - 1)vd (
co Rー (V) d-a +
From our choice of vd there exists a constant C, such that for d 2 C. we have C-1 < c cle (y) S C for all y E R. We deduce that there exist a constant Ö sufficiently large but independent of d such that
I|5,,e112 < Ô max(dd""1151)) "111, 11 (2) (22=) ||Ea,eli2= Č-1 max (1-201162011
(22)
112, -
where the - are with respect to the associated nulls vd,0, v/ and (
Consider k, a multiple of 10 for simplicity, and set h2 k., ki 2k./5, and a k./5. Using Lemma 2, we can bound the contributions from (1) and v
Consider the contributions of ( to the sample and runtime complexity:
Sample complexity:
S hi,, 8= =k]12]:
mat
2R11-1/2 = /5k./5-1122
(1)
1
8 8 k1, l & k1 k1[2]:
22
121--11211 15th//5-//2+1
(23)
|K 112
<> h1
daa
2 che2 = 15+8/2
Thus the optimal sample complexity is achieved at degree l = 11 = 2k./5 with 3k. lower bound.
Runtime complexity:
i < ki,
{= k2 [2]
2a
Vdd,e
22
d2k./5
| 1
L E ki,
f ki [2]
22
Vdd,e
x 12 -5tk//51
| (1) 112,2
(24)
l ki
22
Z alite = g2hh/54t
1 Thus the optimal runtime complexity is achieved degrees E = =2, l = k1(2]
|
with / lower bound.
Consider the contributions of v/ to the sample and runtime complexity:
Sample complexity:
< k2,
f= K2
-212212 = dkk--t/2
(2)
1122
L. < k2,
& K2 [2]
x dh 11/2+1 = Hl. -1/2+1
(25)
8> K2
2 d//2
26

---

Thus the optimal sample complexity is achieved at degree / = k2 = k. with d lower bound.
Runtime complexity:
i S K2, {= k22
Ted.
= d d%
1.c.,11122
i S k2
f & 1:2(2)
ndd.e x d 11 = =
|
(26)
Tdd,E 2 de
8> k2
Thus the optimal runtime complexity is achieved at degrees S h:2 = k. l kz with dh lower bound.
From the bounds (22), the sample runtime complexity for each é the minimum of the two contributions associated to ( and v We deduce that in this model:
Optimal sample complexity is achieved at degree mm, k., with matching algorithm that succeeds with Oa(d"-/2) samples and T O(dh.) runtime (thanks contribution v
Optimal runtime achieved at degrees IT,- = & with S 2k./5 and = 2k2/5/2]. For example, choosing IT,+ 2k,
have matching algorithm that succeeds with T Oa(dtk./5) runtime and = O2 (dkkkk/ samples (thanks to contribution v
We conjecture that for this distribution Ma, no algorithm exists that achieves both optimal sample complexity m /2) and optimal runtime complexity T _d(ktt./5), Further note, that by choosing intermediary degrees f, one can trade-off sample and runtime complexity.
A.3 Revisiting vanilla SGD, landscape smoothing, and partial trace for Gaussian SIMs
In light of results in Section 4, revisit the three algorithms for learning Gaussian SIMs mentioned in the introduction [10, 28, 29], and reinterpret their behavior through the lens of harmonic decomposition. Below, state informal observations which aim to build intuition rather than make formal statements. We provide supporting computations in Appendix A.4.
Consider Gaussian dingle-indx model (1) with link function p P P(R2) and generative exponent k, : k. (p) as defined in Eq. (2). Throughout, let T + R be a transformation of the label satisfying:
TT 1,
|o0 S C,
Tk. = ETITT (G) - 11sk. 11.
Such transformations always exist (see [29, Lemma F.2)). Informally, one can construct T. by truncating (6./, Ilza (with truncation at large enough value as approximately preserve the correlation with He,,).
Online SGD with Hermite neuron. In seminal paper, Ben Arous al. [10] studied online SGD on a non-convex loss over w E gd-1 with planted signal w, and a k, -order saddle at the equator (w, w.) 0. Adapting their results to the task of learning Gaussian SIMs, their algorithm performs online SGD on the population loss
(T.(()) Her. ((w, x²)) )
min L(w) = B(yaa))P.... WEST
(HeSGD)
and succeeds with suboptimal m (a(d"--1) samples and =.a(dk.).
Observation 1 (Informal, harmonic structure of the loss). When ((,, w.Yl 2 d-1/2, the loss landscape L(w) dominated by degree-k, spherical harmonics. The resulting SGD dynamics behaves similarly to online SGD using Qu. ((w, 2)) in place of Hes, (wwx))).
27

---

This suggests that algorithm (HeSGD) effectively restricts itself to the degree-k, subspace Va.k.- As a consequence, we expect its performance be constrained by the query complexity lower bound (2(d%)) ), and its behavior to be similar to the degree-k, online SGD estimator (SGD-Alg) in Section 3. We further provide an alternative perspective that highlights the role of the norm || of the input data in learning Gaussian SIMs:
Observation 2 (Informal, norm-invariance of dynamics), The SGD dynamics of [10] remains essentially the same the input x: is replaced by f- az ||2:1|2 where F Xa sampled independently.
This indicates that the algorithm does not exploit the radial component | and effectively operates on the normalized direction z < l|2. From our theory (Section 4), any such estimator incurs query complexity of (d( In this sense, algorithm (HeSGD) is runtime-optimal among methods that ignore radial information.
Landscape smoothing. To address the suboptimality of (HeSGD), Damian et al. [28] introduced landscape smoothing operator that averages the loss on a sphere around each parameter ur E Sd-1;
[ (
+ Au
min E Bu--Uni((St-))) WES
|| + hu
(SmLD)
This modification achieves near-optimal complexities: m= Ga and T TT=+ap -d((t./2+1)
Observation (Informal, low-pass filtering effect). Landscape smoothing suppresses high-frequeccy components of the loss, effectively amplifying lower-degree harmonics. The initial phase of SGD dynamics behaves essentially like optimization over Qi(ww, 2)) and Q2((w,z) z)).
Thus, smoothing can be interpreted as projecting the dynamics onto low-degree harmonic seannenttt-pecffcallly. the statistics of the spectral algorithm (SP-Alg) associated to spheri- cal harmonics of degree E {1, 2). In this sense, the first phase of the dynamics on (SmLD) essentially corresponds to running SGD on the optimal spectral estimator (SP-Alg).
Partial trace estimator. In subsequent work, Damian et al. [29] proposed an estimator based on the partial trace of Hermite tensor, inspired by techniques from tensor PCA. Their construction begins with the empirical Hermite tensor:
T
Σ Hex, (x;)) E (RR))K
(27)
AE(m]
where Hee, (a)) denotes the rank-k, multivariate Hermite tensor, and T, the transformation defined earlier. The expectation E[T] is proportional to w To extract this principal component, they compute partial trace of the empirical tensor by contracting I with identity tensors. This results in an empirical vector or matrix, depending on whether k, is odd or even. The resulting estimator is
k. odd:
i
①
| 12
(E(m)
(PrTR)
m
k, even:
arg max wT M w. wEg4-1
M = m Σ (.(.)) (1
Id]
where Pk. is univariate polynomial derived from the contraction of the Hermite tensor. In the odd case, second refinement phase (see Section D) is used to boost wo from 1/4 to constant correlation with w.. This estimator achieves the optimal sample complexity (a(kk//2) and (near) optimal runtime (a(k /2+1 log(d)), matching the lower bounds for learning Gaussian SIMs (3).
Importantly, estimator (PrTR) corresponds precisely the general spectral estimator (SP-Alg). associated to the optimal degree E (1,2) harmonic subspaces, using
Te(y. r) (v) with 1 if k, is odd, and
k, is even.
Observation 4 (Informal, lower- frequency projection). Partial trace effectively projects the high- degree Hermite tensor onto lower-degree spherical harmonic subspaces (L or for partial trace over all but 1 or 2 coordinates).
28

---

Although our estimator recovers (PrTR) in the Gaussian case, we emphasize that its derivation is very different (including constructing the non-linearity Tely, r), see Appendix G). We construct it directly from rotational invariance and harmonic decomposition, without relying prior knowledge of tensor PCA, contractions of Hermite tensors, or coussian-speciffe identities. We believe this alternative, transparent derivation of (PrTR) highlights the advantages of the harmonic perspective when learning single-index models.
Remark A.1. We further remark that if we normalize the input æ and apply landscape smoothing or partial trace algorithms to the data (yi, vd æ / [e)m)) the sample complexity increases to at least dh. and these estimators become suboptimal.
Remark A.2. Both landscape smoothing [19] and partial trace estimators [47] originate in the tensor PCA literature, where a similar gap between 'local' and optimal algorithms urises-with d'-/2 versus d' gap in signal strength. It is intriguing to connect the phenomena observed in Gaussian single-index models (Observations 3 and 4) to analogous behaviors tensor PCA. We leave this direction for future work.
A.4 Discussion on Gaussian SIM phenomenology
We provide below quick computations to justify the observations in Appendix A.3.
Observation harmonic decomposition of the loss. First, note that
[(w) = 2 - 23,, E.z [Hck, ((w., Ho,, ((wr .z) = 2 2T (w., w)
and it is enough to consider the correlation loss. Let's decompose the landscape into contributions from the different harmonic subspaces: using the Hermite to Gegenbauer polynomial decomposition in Eq. (20), we get
Ex [ek, ((w,, Hev. ((w, x))]
B|gx. . (())) ())ek x))
8sk
tkk.
(28)
|| elli.
Qe (e((ur,))))
E<k 1=
where el1 /na.t Oa(ddk./2) (see Appendix B). For kw., un) 2 Ck2 d-1/, the leading contribution in the loss (and its gradient) is l = k, (recall that the leading term in Qe(ww, w.)) is O (d(d//2)
(odd///(())))) (w. w.)²). Informally, this implies that we could have replaced Hes, ((w., by Qu. ((w,; 2)) the above loss.
Observation 2: dynamics with independent norm. Let's consider the loss (28) when we have independent norms between the input and the signal:
E(Bx,,err)12 /na,e
E[Hek, (r (w.,, Hek, (F- (w, 2})1
Qe((w, w)))),
(29)
PSk tEk.
Oa(d aa +2/2) (see Appendix B). In particular, the leading term k. remain the same between Eq. (29) and Eq. (28). Following the proof in [10] (see Section E), the dynamics with same hyperparameters behaves similarly between the two losses (29) and (28).
where
Observation 3: low-pass filtering of landscape smoothing. the correlation term. Let's decompose
Again, is enough to directly consider
+ Xu
]
me(A) 11 12
E Eu-To Ex
Hex, ((w., x) Hee.
x
((((,,.))).
I + Aulla
Vnd.e
BSk tsk.
[2]
where each frequency (28) in the original loss L(w) is now reweighted by w + Xu
1
1Z (I+
me(A)=
Fan Qr
E
E
Qc
TTdll w Au
TddE
x
29

---

When À = 0, we indeed have m² = as long as (w, w.)l < x
= 1. For >> 1, we have m²(A) x 1/X,, and ,, the loss (and its gradient) are dominated by frequencies E E {1,
A.5
Correlation queries and the information exponent
In the main text, focused on the generative expoment introduced by [29]: this notion tightly capture the optimal complexity of learning Gaussian single-index models among Statistical Query and Low- Degree Polynomial algorithms. An earlier notion the information exponent- was proposed in
[40, 10]. Specifically, for scalar labels Y S R. the information exponent (IE) of is defined by
(p) = arg min 2 1 He + 0}.
(30)
This exponent captures the complexity of learning with so-called correlation statistical query (CSQ) algorithms, which only access labels through correlation statistics y0)x). other words, using the terminology introduced in Appendix C.I, it captures the complexity of Q-restricted SQ algorithms,
with
@ Qcsq {o(y, a) vz(x) á measurable function).
We denote CSQ(q, r) == Qcsq- SQ 7) this restricted class of SQ algorithms.
For CSQ algorithm, Damian et al. [28] showed lower bounds within the Q-SQ framework of m (c(
T= =0((dh(0//2)))
(31)
Note however, that only the generative exponent reflects the fundamental hardness of the learning task: indeed, we always have k. (p) < k((p), with (p) always one or two for all polynomial function of (while kp(p) k if y He (G)). In the case (p) (p),, the complexity predicted by the information exponent can be improved upon by using non-correlation queries, such as using non-correlation loss [29] or by reusing samples [32]. Nonetheless, IE remains relevant in several natural settings, such as online stochastic gradient descent on the squared or cross-entropy loss.
Below, discuss how to recover this information exponent from our harmonic framework when considering Sc algorithms. Introduce the CSQ query complexity
CSQ
(va)
min E21
2
where we defined
1
CSQ Sa.e CCSO (Y, = (R),
(e)e ==
Bug (YQr
La
Adapting the proofs in Appendix C.I, we obtain the following query complexity lower bound: Proposition (CSQ lower bound). Fix va La. If an algorithm A E CSQ(q, r) succeeds at distinguishing Pra,w from P P. then we must have
9/>2 2 Q (va)
(32)
Using the non-linyyrity Te(Y, R)) = e in our algorithms (SP-Alg), (SGD-Alg) and (TU-Alg) described in Section 3, we can prove the same Theorems 2, 3, and 4 with sample complexities replaced by / ( CCQ 11 and runtime complexities replaced by / cSQ 12 (one simply plug these nonlinearities in the theorems in Appendices D, E and F).
Specializing to the Gaussian case, one recover the exact same result as in Section 4, but now with k. (generative exponent) replaced by kj (information exponent) of the Gaussian SIM p. In particular, for all é < k,. we have
155.5.50 Ii. x d dk for E = ki mod 2 and ||
CSQ 112. S ck-kk(++)/2 for l * k) mod 2.
Similarly to the generative exponent case (and general SQ), the optimal degrees for learning Gaussian SIMs with CSQ algorithms are always achieves at m,, = lT, [1, with the spectral estimator (SP-Alg) achieving
m (2(c(())2))
T= 0=0(h((0)/2111
Similar results as in Section 4 hold for learning with CSQ algorithms without using the norm ||>|||2 We note, however, that here, non-CSQ algorithms can achieve much better performance (attaining the complexity predicted by the generative exponent).
30

---

B Harmonic analysis on the sphere
In this section, we overview some basic properties of spherical harmonies, Gegenbauer polynomials, and Hermite polynomials. We refer the reader to [75, 24, 25] for additional background. In addition to these classical results, we provide an explicit harmonic decomposition Hermite polynomials into Gegenbauer polynomials, which we use in our analysis of Gaussian single-index models.
B.1 Spherical harmonics, Gegenbauer and Hermite polynomials
Spherical Harmonics. Consider the d-dimensional sphere 8 {z ||=||e 1} with uniform probability measure та Unif(S and its associated function space L (8d (2 ra) equipped with the inner product:
(1 [
Jeega- J ((=)g(=) ra(dz), for any f.g E 128
We will denote (,)) = (:, (6))) (a and 1| (f, (f when clear from context.
For é E N, consider Va.e be the space of degree homogeneous harmonic polynomials (i.e. homo- geneous polynomial R + R with Ag(-) = 0). Let Va,e be the space of functions by restricting the domain to gd-1 of functions in Va,e. that is degree-l spherical harmonics on gd-1, We have the following orthogonal decomposition
L3
① Vas. t=
(33)
The dimension of each subspace is given by:
dim (a.e) = -ad = d 28 + 3
d 2-2
l
For each & E N, we further fix (Y :i nd,et an orthonormal basis on Va,e (Y )
)a dexd.g.
Remark B.1. If one considers the unitary representation p: O₂ - U(L of the orthogonal group O₂ R Rdxd, R R -R=I) Ia) given by
p(R) f(z) f(R
The decomposition (33) corresponds to the irreducible decomposition of this representation, that is, the decomposition of L (1d into a direct sum of irreducible representations O₂ (see [25] for detailed treatment on the subject).
Gegenbauer Polynomials. Let T denote the marginal distribution the first coordinate (z, ei) with z Ta. We consider the family of Gegenbauer polynomials on [,3 1], Ta,1), denoted by (d) : E NJ, where o(()) is the degree-l polynomial satisfying
(()())
[ of (2) (2) (a) J
Q.40 ((z, ( (1), ((,,))
8ex
relationship between the spherical harmonics and Gegenbauer polynomials is as follows:
( (zz, x/))
Σ
(( (z'), for all 2, z' E sd
(34)
sE(ma.e)
Another important relationship is for any v E 8d-1,
dex ((w)((w, Q 1 (1)
(0) ((,,),)) w)), Q (1: u\)
(35)
T4.1
31

---

where (1) Aua, derived in Eq. (45) in the next section. We note that the normalization of
Gegenbauer polynomials considered here is such that ||0/ (1 = 1 holds. Another popular choice is such that the value at evaluates to 1 which we shall explicitly refer by the family of polynomials {P( JEEN. The normalizing factor is such that p! = of (-) Vna.e
The derivative of the ech Gegenbauer polynomial for E 2 1 can be expressed as E(( + 2) Ma,
1 (z) = Q (d 1) dz
B(d 2, Qz= C(d,)) (1)))
(36)
where for a fixed constant l and growing d, we have C(d, f) = 0a(Vd). Let E (2 -T) such that f is invariant by the action of ow.- ( E Oa: W w w) which is the set of orthogonal matrices which keeps the direction fixed, i.e. f only depends on the projection (w,z). Then admits the following decomposition
30
[(z) -0 (
((w0, 2))
(37)
Hermite polynomials. Consider the probabilist's Hermite polynomials (Heg. h E NJ. in the normalization that form an orthonormal basis of (22(RR,) 7), where 7(xx) a 2/ Gaussian measure. Heg is polynomial of degree k and
is the standard 22
EG-N(O,1) [Ge
As consequence, for any E I,2, 7), we have the following decomposition
80
g(x) Σ p He(x), (x(g) EG Mo.G
B.2 Harmonic decomposition of Hermite into Gegenbauer polynomials
The Gaussian distribution æ ~ N(O, I2) admits the polar decomposition
x |
æ where |لح|| =: r ~ Xa and
| =: Unif(S are independent.
||=||2|
Therefore, 21 U1, where x1 N(0, 1) and 21 Td, In what follows, denote 21 and 2 = 21 for convenience. The Gegenbauer polynomials are an orthonormal basis for тa. and Hermite polynomials are (unnormalized) orthogonal basis for N(O, 1). Our goal is to explicitly express
(d) (z)), formalized in the following Hcp (x) = Hrx(r-2 2) in terms Gegenbauer polynomials {Q) proposition.
Proposition 2 (Decomposing Hermite into Gegenbauer). For any k E N. we have
Her (r- 2) = Σ ( (2),
(38)
2=0
where = = k) or (f ( h mod 2), and otherwise
3x.((r: = VkIVK(d,e) E)
( -)-1)--07422)
(39)
(N!)
(d+2))
where N = -k- and K(d, x d' as d + and & is constant, i.e. K(d, (((dd)
Essentially, are decomposing the Hermite basis into the Gegenbauer polynomials, which is the correct basis for the "directional" component and explicitly computing the coefficients that depend on the radial component r. Such relationship is derived by technical algebraic manipulations, and in similar spirit to [60], relating Hermite and Gegenbauer polynomials. However, the precise expression sensitive to the normalization used for Gegenbauer polynomials. Thus, we provide an explicit calculation of this decomposition in Section B.3.
For our upper and lower bound analyses, in order to measure correlation of Heg(r 2) with Q. (z). using both type of queries (with or without norm), the asymptotic bounds on the following moments of these coefficients will play important role.
32

---

Lemma 3. For any fixed E S K E N with same parity, i.e. == mod 2, we have
B
(m- and
E B (r. d (k-1)
In order to show this lemma, we will use the following well-known facts. Fact 1 (Moments of Xa distribution). For any p N, the even and odd moments of Xa distribution are given by.
p-1 II j=0
E By~xal 2r
(d 2j),
(40)
d+1 v
E Ex-xel (12pt
Bir
(d - 2j +
2
(d + 2j 1).
T(d/2)
j=0
i=0
Therefore, for any fixed m E N. the asymptotic behavior of the m²t moment d - Do is given by
[m/2] -1
E [TT x (va 1m = mod 2)
II J=0
(d (d+ 2ÿ)
Fact 2. For any univariate polynomial g: IR + R. the n finte difference of g at any value is given by
11 A" = Σ 3
(-1)
For any polynomial g, the th forward finite difference A"g(u) = 0 if deg(g) < n and g is non-zero constant if (g)g(g) = n. Moreover, for any polynomial given by shifted binomial coefficient of degree n, with shift un
-..... In (u) + uo) 40 ... ....(u 20 n uu+ ug
n!
n
the constant value of hh forward finite difference is unity, i.e. A")(u) = 1.
Proof of Lemma 3. We will use the above facts directly along with K (d, E) de and N,k, are constants (not dependent on d) from Proposition 2 throughout the proof. We start by the first part of the claim
(A:)
N
2N n 2p 20 +2
E (1)
(N1)2 K(d,))
Σ
(d 2ÿ) 11, +- (d + 21)
1==0
N
1)2N
++m++n- (d+ 2j)
d
(using Fact
1,500
-itt-1 (d 2ÿ)
1
1 1i+tt-1 (d 22)
df
N
N
N+4-1
2N 2N
II j=m+t
(d 2j)
II (d 21) j=nt!
11 N + 2j)
m
n=0
8
N+6-1
N
Σ
Σ
1112 1
II
(d+ 2ÿ)
II j=n+E
(d + 2j)
m
n=
j=m+t
N+C-1
etmtn-1
(d + 25) )
N
1) N-
II J=n+E
(d+
Σ
1) N-m
II j=++t
m
m=
(k=
Σ ==
N (-1) N-
N+8-1
II
2j)
N
(- 1) N-m
(d m +
2 n! ))
m
n
m=U
33

---

We are now going to show that term inside the parenthesis is some constant independent of d. A priori it may seem that depends on d, however, we have a sum with alternative positive and negative signs and we will show that all the terms that depend on d mutually cancel out.
To show this first observe that g(m) (#+**==1) is polynomial of degree n given by binomial coefficient, And, therefore, the N forward finite difference A gmm) for any n < N, or simply 1 for 7 = N using Fact 2. Formally,
n
N
N
1-1) ++++a n2 - 1 1) 2" 2" n! 6N
17=0
where the scaling factor of n! of the polynomial g(m) can be taken out the forward finite difference operator A N is linear. We conclude that
Bl3x,e(F)
N+ II (d+
N
N
(- 1) ( +m+++ 1 2n
Σ
1)
Σ m==
m
n1
j=n+é
N+8-1
N
d
(- j=
II
(d (d)
ONn 2"
=2" N! d
(k-
We now show the second part that
E [[ x d (k--))
Let us consider any k such that they have the same parity k ==6 E mod 2. We have
B[Bu,e(r]] (kl) K(d, E) (N!) 2N
( (
1=0 (d + 2j)
N
Le/2]+ (d+ 2f)
12
(Vd. 1l6 modd
Σ
N- j-
(using Fact 1)
I1 1 (d+ +
X /1//2]
Σ
(-1)
1
|= (d + 2ÿ)
E+i-1
1=0
IT
N+i-1 (d+22)
1-1)
IT (d + 2ÿ)
-+i-1 [/= (d 2j)
t=0
df//2]
(M) (-1) II
N+i-1
Σ + oa()))
(d 2ÿ).
d
k/2
1=0
f=1
In the last line, we used the fact that & = mod and N = (1-2) and thus for every 0 sis N,
N+1-1
4481
N+i-1
2j
2j
II
20)
II
(d 25) +e/22
II
1 +
II
1+
d
j=1/2+
1=
+=le/2|+1
=(1 oa(1)) +e- 8/2.
and
(k I
k+
N W 1-1-110 V+2-1//2)
+ 1 18/21
11/21 = [k/2]
34

---

Continuing to simplify the original expression
d/e/2
(M (M) (-10
N+i-1
B[(x,((r)] x /1//22
oa(1))
II (d+
(-1) N- ( + N
2 N!
N
2 Nọ d 1
Here the last line followed from the fact that the polynomial g(i) = ( is of degree N given by a shifted binomial coefficient, and thus, the M forward finite difference of g is constant, which in this case is just 1 by Fact 2. We finally conclude the proof by noting that [r))) = d dx-00 n
B.3 Proof of Proposition
We now return to the deferred proof of Proposition 2. First, the explicit expression of He, so that |He ll 122 =
L2/2J
(-1)m m
2m2m
[k/2]
(-1) m
2m = 2m
He 2) = (x) = Vk!
K!
(41)
m 2mm!
2
m!(k 2mm 2
m==
Our goal is express 2m22m in terms of Q () get the final decomposition. To this end, the explicit expressions computed with (a different normalization) of Gegenbauer polynomials. In particular, using [39, Eq. 18.18.17]
[n/2]
re!
+ 21
1
(()) (z)
(42)
a
I1a + 1)n-1
where (b), is the rising factorial and cf (2) is an unnormalized Gegenbauer polynomial Q (z) with a (d 2)/2 satisfying
T2 +2)
td dek El(e + a) [Ta]]
(43)
We can express ( ((a)//K(de))) () where K(d, E) can be computed using
K(d,e) [ (3) Ta, (dz) K(d.nB(at1..) 1.1) cf (x)² (1 22)0 22)0--ra, (de)
where B(:,)) is the standard Beta function. We can use Eq. (43) compute
-21-2aT(E + 2a)
kdd, B 3a+ ([)))
(44)
is straight-forward to simplify
k(d,e) 2 ((a 2 200-2-T0 T
T(a + o))
T(a ()((((+))[
aT(e + 2a:
(::((a)(aa + 2) = -22
a (a + f)r(2a)
(d () -2+
(d-2)
(d+t- - 3
{ 9) +a(dd))
e (d + (d) - 2)
(d + 28 2)
Also substituting c(a0 (1) from [85], we obtain
Q 1 (1) (la)(1)
(a + (2a)
I(2a + T(2o))e
d 28 2
(d+ f (-3)
(K(d,)
a2
+ +1)
d d-2
8
(45)
35

---

We are now ready to combine the equations derived and compute the desired decomposition Eq. (38). For any M N, we let
M {m N M and M mod 2). Recall from (41)
12/21
1 y
(-1)(kmm\/2n "
Hox(r u) Vi!
VI! Σ
m!(k
2m)!
2
m!((k m2/ 2(k-m
mE k
(Change of variables)
Vh!
Σ
(-1)(k-m)/2) m!!
1m/2]
a + m 21
c(a)
m- (u)
ml((k m2) 2 2m2(k-m)/22
11(a + 1)m
mE
(Using (42))
V Σ
(-1)(6-m)/2
a+t (mm-))/2)(c) + (m
1
K(d, E) 2 ( (u)
((k m) m2) 22
meT
E m
(Changing ( m m
21 and clo)) = VK(d, 8) ()
K(d,) K(d,t) Σ (w) a
(-1)(k-m)/22mm
1
((k- m) 2 m2 2)/2)!(ar + ()
k
imEk mod
(u)),, where if &
k then (L,e(r)= O.
Otherwise, letting N (k- E)/2
- k 8) +
(-1) (k)
Bx,(r) -
- (m--mm//))22mmmmmm(mmmm) E)/2)l(a + 1) (m++)222
a
N
(N -1,
= V a
(changing m + 21)
(i)!(a 1)ets)
VMK(d, 8) a+
(-1)N-1,642)
(N!)
2 1)ets
Recall that (d 2)/2 here, and thus
É+i-1
8ti-1
(d-2 +1+1)
8+i-1
2 (a+ 1)e++ zf+i
II (a+1+))=2
II
II (d 2j)
2
Thus, for == mod?
kl d
N
N
(11)N-ipt+22
(k.((r)
Σ
(N
d-2
1
1 (d 2ÿ)
1=0
The lemma follows by redefining K(d, E) with ((d,))(d + 2 2)2/(d - 2)² Oe(d').
36

---

C Statistical Query (SQ) and Low-Degree Polynomial (LDP) lower bounds
In this appendix, we briefty review the statistical query (5Q) and low-degree polynomial (LDP) frameworks and present the proof of Theorem 1. In particular, we provide an interpretation of our lower bounds in terms of subproblems with queries restricted the harmonic subspace Vd,e.
C.1 Statistical Query lower bounds
The Statistical Query (SQ) framework, introduced by Kearns [53], models algorithms that interact with data only through expectations of query functions, rather than direct access to samples. The complexity of these algorithms is measured up to some worst-case tolerance on these expectations. While based on worst-case enror rather than sampling error encountered in practice, the SQ framework has proven remarkably effective in analyzing the computational complexity of statistical problems, often yielding accurate predictions for algorithmic feasibility. We refer to [22, 71] for additional background.
Below, it will be useful to present a variant of SQ algorithms, called query-restricted statistical query algorithmss, introduced in [50]. In this model, queries are restricted to set Q C R of measurable functions y x Rd -> IR. We denote Q-5Q(g, 7) this class of algorithms, with number of queries and tolerance denoted (Q,g, T), where Q contains all measurable functions. In Appendix A.5 we discuss the case of correlation statistical queries (CSQ).
O. We will mainly consider the standard case of unrestricted queries,
Our lower bounds hold for the detection problem (hypothesis testing) of distinguishing between
{IP Pr... w Sd-13
v.s.
{Prr.0}-
(46)
Below, we describe Q-SQ algorithms in this context.
Q-restricted SQ algorithm. For number of queries q and tolerance T >> 0, Q-restricted SQ algorithm A E Q-SQ(g, 7) for detecting SIMs takes an input distribution IP from (46) and operates in rounds where each round t .I.....9h it issues query di Q, and receives response tt such that
9),
0 - (v æ)]] S /ara, (d.),
(47)
where we set Io to be the null distribution (that is, PPu,.0 here). The query Φ: can depend on the past responses UI...., 1t-1- After issuing g queries, the learner outputs A(P) E {0, We say that A succeeds in distinguishing Fr..w and F Fr.... if A(I = 1 for all w E S and A(Pr..o) = 0. Remark C.1. The variance scaling on the right-ham side in (47) is non-standard in the SQ literature. It is introduced here as convenient way to normalize queries, which is necessary for to be meaningful. We note that other normalizations are possible and refer [50, Remark 3.1] for discussion.
General lower-bound. The following proposition is simple, standard lower bound on the query complexity based on the second moment method (c.g., see [50]): Proposition (General Q-restricted SQ lower bound). Fix va La. If algorithm Q-SQ(q,7) succeeds at distinguishing IP P. from TP Pr..o then we must have
Varw (E
9/7² 2
sup SE
(48)
Varr Varr.y {Ø}
Proof. Consider A E Q-SQ(q, 7) and denote $1..... Φg E the sequence of queries issued by A when it receives responses e,- = Er,, [6t]. t lq]. Here the responses are fixed and deterministic, and the queries [ do not depend on the source distribution Pry,,,, and in particular By union bound and Markov's inequality,
Var wotTh (Er dc)
P Purory (BL [g), [Bp, ((r) vel > TV Varr 0
<
sup tE[g
Varr, o (
Var woror (EP,
q
sup dcQ
Varp [0)
37

---

This implies that the Us Ep [ responses are compatible for all queries with positive probability over ~ whenever inequality (48) is not satisfied, and A fails the detection task in that case. This concludes the proof.
The query complexity bound in Theorem 1.()) follows from Proposition 3 with unrestricted queries Qsq and the following identity:
Lemma 4. For va E Ld and QsQ the class of unrestricted queries (all measurable functions), we have the identity
VarwoTr
of
[ [Q,(va)]-
sup 6E QsQ
sup E21
(49)
Varp parp.goo (Ø)
dd
We defer the proof of this lemma below to Section C.I.1. The identity (49) shows that the lower bound effectively decouples across the different harmonic subspaces. Below, we provide an interpretation of this result: if we restrict the queries Q to be in Va.e, then the SQ lower bound becomes nd,e/ 2= Specifically, for each & 2 1, define @sq,t to be the set of all queries oly, x) than can be written as
xy = Σ
ge (os((2),
(50)
sE(na,l
where (Etatel is basis of Va,e. Then by Proposition 3 and the proof of Lemma 4, we have:
Corollary Fix E Eg and 2 Ifan algorithm E 2sq.r-S(gg. 7) succeeds distinguishing Prgm from P v1.00 then must have
Varwora (BFor
9/7² 2
sup dE
Td,E
(51)
Var {0}
[E 7.2
For each f 2 1, show algorithms with queries restricted to Va,e in (50) that matches this lower bound. Thus, effectively, the problem decouples into subproblems, one for each Vá on each harmonic subspace, we have matching upper and lower bound on the query complexity, and the optimal algorithm obtained by choosing the optimal degree & that attains the maximum in (49).
C.1.1 Proof of Lemma 4
For clarity, we drop the subscript va below and denote Fw := P P.n.. and Pg := Puo.o- Note that a property of the null distribution is that
Ew [E2,, [+]] Ep. [d],
that Po is the marginal distribution of (y. x) under the uniform prior w Ta- Thus,
Var [E.,. o Ew | (w) [²] where As(w) Er.. [Ø] - Er. [o].
Let's introduce the Radon-Nikodym derivative and write
(www) -Ee,
(
ddFw dIP
(yo, 2, 2,r) -1) o(yo 2,r)
)vv..217)
Recall that the likelihood ratio decomposes into Gegenbauer polynomials as (equality in (P²))
dl dP, (yo. 2,r) - 1- Σ Eaelyo, ((w,((()))))
Eaelvo. = Er, ( = = R = r].
Similarly, we can expand o E (Pp))) as
o(y0, r,r) = Σ
t= se [nae)
38

---

where (Yeshe2a.e((mu.)) is an orthonormal basis of spherical harmonics in (3( Using the 11/2
identity Qe((w, 2)) = nd Eselnal (eo we obtain the decomposition
(w)(w) Eyo ( r r)]
(ww))= = Σ
ma,e
(=1 aE
and thus,
Er. & ()0.
Eu B (
Ad,
1= sE(na.e
Denote PEń = Eee en aes Yts the projection on the degree- harmonics. We can decompose the supremum over & E 2sQ as
Evw A w
sup 6E
Varro (Ø)
Peolli
Ex e ars (yo. r)]
= sup de
E 121 | L
||
Tdd
121
|
(Eaee, w//T
sup dE
|
sup (Va,,)))
1|xb1122
121
12
E21
nag
11Ea,1122 La
Ee>1
|E 11
sup d
sup 121
Ee21/
1.2
which concludes the proof of this lemma.
C.2 Low-Degree Polynomial lower bounds
We now consider sample complexity lower bounds within the Low-Degree Polynomial (LDP) frame- work, another powerful tool for studying computational hardness in statistical inference problems. We refer to [45, 55, 73, 83] for background.
Below we follow the presentation of [29]. The planted distribution with samples is generated by first drawing w ~ тa (uniformly at random on the sphere), then sampling m points (yi, xx.) resia or...... The null distribution corresponds to (yi, 2x,) medd Pv..0. The likelihood ratio in this model is given by
dl F.ww
R(Ii Øs)se(m))
Ew
II sE(m]
(yis
x;))
dP dPvu.o
We consider the orthogonal projection P&D (in L (()))) onto degree at most D) polynomial in ø,. that we allow arbitrary degree on the scalars (y,, r.). We denote
Rgp (yi 2;; a))se(m)) = PenR((y, (s)se(m))
(52)
Informally, the low-degree conjecture [45] states that for D wa (log d):
Weak detection hardness: If R 1 + (1), then no polynomial time algorithm can achieve weak detection between Emw (PPSS and ppm that is, have a non-vanishing advantage compared to random guessing.
Strong detection hardness: If | 1222 Oa(1), then no polynomial time algorithm can achieve strong detection between E.g Manww and My that is, have vanishing type and II errors.
Below, we state our results for weak and strong detection for a sequence of spherical SIMs {Ma 1 with va E La. Recall that defined:
Tdde
(v
inf 221
E 11
39

---

Without loss of generality, we will assume that (, Oa (u(poly(d) that is, the model can be solved in polynomial time-as stated in the following assumption:
Assumption 3. There exists E N such that the sequence {va)az1 satisfies (, = O2(dP/2).
We can now state our bound on the low-degree projection of the likelihood ratio in this problem.
Theorem Let dva)a21 be sequence of spherical SIMs va E La satisfying Assumption 3 for some integer p N. Consider the detection task with m samples defined above. There exists a constant e > O that only depends on the constants in Assumption 3 such that if D S cd+/(++4)) then
DP/2-1 m (va)
|R -1 Σ
(e(p 1)1
(53)
In particular,
M.(ra)) (i) (Weak detection.) Ifmm Od Dw//=x then [R = 1 + od())
(ii) (Strong detection.) lfm= Od
M. (vd) Do/2-1
then || Od(1).
The proof of this theorem be found in Section C.2.1 below.
Combining this theorem with the low-degree conjecture stated above, we conclude that no-polynomial time algorithm can detect (and thus, estimate) the spherical single-index model Peg.o unless
Z (va)...
We further remark that we recover the tight threshold M, (va)/D//2 from [29]. Indeed, consider the case of Gaussian SIM with information exponent k.. We can set p = k., and our bound recover (conjectured) optimal ieauutaaiooal-ttttsiiioo trade-off dks, D from [29], which matches the optimal known trade-off in tensor PCA [84].
Decoupling across harmonic subspaces. Again, we provide an interpretation of this lower bound as the optimal lower bound among subproblems indexed by É 2 1. For each / 1. we consider the task of detecting single-index models only using degree-E spherical harmonics. Consider polynomials that are product of degree-l spherical harmonics 2;, and denote P&D the projection onto this subspace, that is
RED.C. ((9). Z:)ee()) = R(y,,
Σ
Ew II
SCIm]
Then we have the following upper bound on the norm of this projected likelihood ratio.
Corollary 4. Let {va3421 be a sequence of spherical SIMs va La satisfying Assumption 3 for some integer E N. Consider the detection task with samples defined above and fix an integer l. 2 Then for all 2 1, we have
D/e.J Σ m
eDc./2-1
1E... 11
R - 15
(54)
Vnd.E
By analogy with the low-degres conjecture, we expect that no polynomial-tin algorithm only using degree-E spherical harmonics will succeed at the detection task, unless
m
(55)
[Ea.e. 12
It would be interesting to make this subspace-restricce low-degree polynomial statement more formal, and we leave to future work. Our harmonic tensor unfolding estimator matches this heuristic sample lower bound (55) for each &, > 3.
40

---

C.2.1 Proof of Theorem 5
Recalling the expansion of the likelihood function into Gegenbauer polynomials, we can write
dP v..
RgD((y6 Tr: (()em)) DE
II [E(m)
Te. Tzi zi)
dlP dlPra.o
Enw
II [E(m]
Ca,e, (Vs. Fr) zi1)
The norm of this projection with respect to i is then given by
Eae 112
Qe, (lw, wo'))
|Rgulli =
Σ
Eur,u
II
(56)
Vdd
E tom SD
iEim
where we used
6ek Vma,t
Ez (2 2)) w'))
Qe((w, w')).
Let's separate the zero degrees from the non-zero degrees (56):
R - 1
Σ m
Σ LSD
B w!
II (E(A
Ed,e, Il:
Qe (ww, (ww,w')) w(y)
Vmd,t
To upper bound the expectation, we will not be careful and simply use Hölder's inequality and the hypercontractivity (Lemma 20) of Gegenbauer polynomials,
B aur
Qe, (uw0, w/)) KE(2]
II
II KE(2]
1qelle~ II g//2 KE(a]
We obtain the upper bound
Σ m
(m)
s 8/2 IEd.e, 11?
m
|R RR
15
Σ
II *E(0)
Σ
p(s, D)o D)
8
L.D
where
D
2/2 1E.
(), D) Σ 1=1
Vid,é
Let's upper bound D). By definition [[Ea,e 12a//a.e S 1/M, for é 2 1 (where we denote M. M. (v2) for simplicity). Furthermore, by Assumption 3, we have M, s Cd Using llEa,ella I 1, we deduce second upper bound
KEee Maa
dP/2
M
Ad.f M.ynd.
Separating & and E> p, get
p L/2
D
2/222/22
8P/2
D
Dle-p)/2
p(s, D)
+
S
P+C
Σ
M.
M. M.yaa
M.
t=1
t=p+1
E=p+1
Using that for l $5 SD D <
Vi,
we have nd.1 2 c(d) > c(d/E)e for some constant e > 0, the sum
simplifies to
D
e (l-p)/2gp1
D2
DP/2+2
< C"
C D2/2
de/2
d
d
t=p+1
t=p+1
41

---

Assuming that D S d2/(p+4) ((/pp4))CC /č, we deduce that
p(s, D) sP/2
(p 1).
M.
Thus, obtain
-
m
s
spp/2
(p + 1)*
mDP/2-1
le(p 111
M
M.
s=
which concludes the proof Theorem 5.
Restricted projection. Consider the likelihood ratio projected onto product of degree-l, spherical harmonics. The proof is particularly simple in this case:
[D/e_1 Σ
[[Ea, 1122
DRR 11
- m
En, (Qe, ((w, ='))
Addee
==1
[D/e_]
em
(11Eat, 11222
)
Sot.12
vdd..
eDc./2-111
115,ee 1122
which proves Corollary
D Spectral estimators
In this section, we provide details for the spectral algorithm (SP-Alg) and prove Theorem 2. Requirement 1. We are going implement algorithms Te satisfying the following criteria.
1. | and (yyr (Tely, (T(()))))(= = Ba. (w.lo.g.).
2. There exits NE > 1, & E N, such that, for any p 2 3, we have [Tellpp Ke kepp/2
Note that transformation Tr satisfying Assumption 2 is special case of this requirement with k = 0 and Ba 2 [[Sa,ellaa/Ke, and thus the theorem will follow by invoking the guarantee for this more general T. satisfying Requirement 1. We first specify the spectral algorithm.
Algorithm 1: A spectral algorithm on the frequency & = 1 and 8 2.
Input An example set (a),,)) i E [m]] ~id Pw.., the frequency 8 E [1, and a transformation Te-
Output:
An estimator u E Rdd
Decompose æ; 2i),
2 f then
Let pm = Lie(m) Te(yirre) vdz,
end
if
then
Let M m
1 Em Te(m, (d)zz La)
Let i V1 (M,) be the eigenvector associated with the highest magnitude eigenvalue.
end
10 Return i.
D.1 Analysis of L 2
Let M := EmM and (A;, d (e])e be eigenpairs w" such that |X]] 2 ... 2 |Agl. We first show that the top eigenvector oi w, with \ = (1 + oa(1))aa, and the other eigenvalues are of vanishing order relative to A;
42

---

Lemma 5. We have that M has top eigenvalue Xi (1 + oa(1)) fa. with v1(M = w. and for any S s d, we have [ 2
Proof. We have that _) w. (T x] = Ei Bu. z)). We now analyze M through its quadratic form: for any S consider
1 m
w M w
E Bwrran (yy) (Z1Z) - Is)w]
(l w. r)d(w, 2) -1]]
(1 (1+ (T(, ((w, ((w,,) 2))1
2² ((w, w.))
(1 (1)
7d22
where we used the fact that 0 = + oz()) - 1). As 2² has its maximum value at 1. Clearly, the w M w is maximized for w w. and thus it is an eigenvector with the eigenvalue
x (1 0, o,(1))aa22 (4) (1)/ map (1 (1))
It suffices to show that the other eigenvalues of much lower magnitude. For any 1 w.,, have Q,40 ((w, w.)) = ² (0) (1 + (a(1))(-1)) and thus, for 2 S d, we have
Ba.2
A = (1 + oa(1))
Ad2
d
which concludes the proof of this lemma.
Our goal is to ensure that the top eigenvectors á V2 (M m) and w. (MM) are close to each other, when m is chose sufficiently large. By Davis-Kall Kahan's 's theorem, it suffices to show the concentration between the empirically estimated matrix Mn, and its expectation, in the following sense.
Lemma 6. There exists a constant C > 0 (onty depending on k)) such that, for any 8 > O, with
m > C .. d
1 Ba,2 log
log
k/2+2
d
B
8,32
have that with probability 1-8
Xi
M m M llop S
8
where recall that X3 is the top eigenvalue of M (see Lemma 5).
Proof. Our goal is to Lemma 25, with Y, 1 (T(y, (dz, - La) M*)
Rxdd which
are zero mean, and thus, Y M m M Let us bound the each quantity of interest
0² [[E 2 1| 1 [IB[[M, - M < |||M]]]le
2
2
<
sup
w T [EEM@
m
w
2
E (yg, T [T(y,r)² ((d -2d) T + Ia)]
sup
m
wE3
2
(gr,.)) [T(,,)) - (w, x)² + 1)]
sup
m7
wE38-1
43

---

z)² + is polynomial of degree with S d. We now note that g(z) 2d) 2/2 Therefore using spherical hypercontractivity (Lemma 20), we have (l9())llP((T) S d. Applying Lemma 24 then gives us
[
rT -(d -2d) (we 2)² + 1)] x d 177 max 1, (1, log
177122
x dllog(Ke)
where we used the fact that ||71 and ||T||4 X log((se). We finally obtain that
dlog Ke
m
We next analyze the other variance term using similar idea:
of = sup E [uu (Mm M²)
E [M
(M1 - M)
sup
wEBd-1
4
sup [u [l(uTM 1
M
sup w
B[T (d/ () (u, v))
m
We would like to use Lemma 24 to bound the expectation, for which we will first obtain tight bound on all the moments of g(z) = (d(u, (1, (u,, v)) Let compute
119ll 2 Eid (u, 2) (v. + 1 (d'E((u, =)* (v. 2) 1)
(d EE 2) 2) 1) (d+ B[ai] + 1) =
In the above, we used the Kauchy-Schward inequality, rotational invariance of Ta. and E[a²] S 1/d respectively. Using hypercontractivity (Lemma 20), we have (|))) S (p 1)2. We now use Lemma 24 conclude that
0x
sup
E (dd(u,,))) 2) (u, 0))2
T max 1, log( (1711.) 11T112
log(nee)
$
where again we used that ||T| S Ke. Our next goal is to compute R = E [max where Y. (T);,rr)dzz M'). And thus, ||Yill 1
Y, 11 1/2
m (d] r:))
M (22) z
m (d r.)) + Sa,2), using Lemma 5. For any p 2 3, bounding the pth moment
d 2/2
B||l
1p < m
[d] + Ba.2) S
m
Using Lemma 26, we have
1/2
S d Ki log k/2 m
E
max [m]
Y 211
The threshold for choosing R is:
1/2 V2R ( (dlog Ki
1/2
d
2/2
d 122 m
d 1/2
m
m
m
where in the last step, we used the fact that we are in the regime m 2 d. only keeping the dominant term. Therefore, for any 5 > 0 we can choose some R that satisfies
Ki log h/2 (m/8)
S
and
P(max 1mmm]
Y1l 2 R) S 8/2,
m
44

---

where in the last inequality, we used Lemma 26. Finally, we apply Lemma 25, With probability 1 6/2 de have
dlog(Ne) 112/2 log Ke
( di dlog
1/3
drg log
log²/2(m/0)
| m M Hop x
(2/3
m
m
m
m
Choosing t = (og(2d/0) (). obtain with probability 1,
1/3
log Ks
log((s) log(d())
d'ri log ts log (m/ (m/6) (og (d/5)
[ 1lpp S V
m²
k/2 (m/ drg log
log(d/8)
m
Therefore, there exists constant C' such that, for
Kee 1 + 1.4.2oo"//0
(
d 8 6B8.0
)
8/242 4/2
ma
$3.2
any m 2 mo, with probability 1 1-6 6,
3d,2
Xi
M m M flop
<
16
which concludes the proof.
Proof of Theorem 2: Spectral algorithm, case l = 2: For any transformation Te satisfying
requirement Requirement we have that choosing sufficiently large that is
m S Cie
+ Ba,2 log
83.2
8 B22
by Davis and Kahn's theorem, we have
MM m M 1lop >1 Xj
min Ia (M)) v
35 {1)
According to Lemma 5, this corresponds to
X
min || w.ll2 < (1 o(1) $ -
Rearranging terms, we obtain (úx, w.)1 | 2 1 /4. Finally, the above sample complexity bound of m simplifies to the one provided in Theorem 2 under the stronger Assumption
D.2 Analysis for f ==
We now analyze the case = 1 case, where the analysis is even simpler and follows by concentration of vector its expected value. For simplicity, will denote T Tı. Let us first evaluate the expectation of the vector statistic v... computed by the algorithm.
Lemma 7, We have that B(ūmm] = Ba,1 w.
Proof. For any E [d].
Elum] = B(g,r,)).P... (T (1) (z:)) = (yynn)), ((t ((z,e))))
Σ Ba.e 10 ((u., ((w,, ( Ba, ((w,, Vray
3a,1 (w.)s.
We conclude that E[um] Ba,
45

---

We now show that for sufficiently large sample size, our final estimator i has the desired overlap with the ground-truth w, via concentration arguments.
Lemma 8. There exists a universal constant C such that for any 5 > 0 and any
2 CReVd (1+ (1+ log (1 82,1
dise
and
m 2
1 d
1
log
log
(k+1/12
die 8,d,1
Vd
88a,1
32
respectively, with probability - 6, we have
(um; u.)
d-1/1
(um; w.)
1
and
1m ll2 4
1mm l|
4
(T( w.) (v", )). Calculating the Proof. Denote o² E|uml] and define X; 1 m variance
w.) x log Kz
B[X
B (T,, u,,
where in the last inequality we used Lemma 24 and the fact that || = and g(z) = d(w. 2)² is polynomial of degree two with || S 1. Moreover, for any p 2 2
1 (.)())))))11))00 z 2)) + Sd1 S (17 + Ba,1) [Xillp -
x Kr p plt+1)/22
m
m
m
where the last inequality, we used (v", w²) Ba, S 1 (ef. Lemma 7) and || S Ke (2p) k/2
and [|Q1llpp S /2p by hypercontractivity (Lemma 20). Applying Lemma 27, with probability 1
Ke log(1/5) log (k+1)/2 (mm1)) (m/5) 1mm - w.)l S log(Ks) log(1/8)
m
m
Therefore, there is a constant C' >> 0 such that with any m 2 Ckev // with probability 1 - for small enough c
Ba,1
Kun. v², w.)l
(57)
Now let o Um (m w.) w. be the component of Um orthogonal w.. Our goal is to find high probability bound on |/,/ l12. Due to spherical symmetry, w.l.o.g., fix w. e₁ and S ~ Pm and the norm the desired vector is given by
Σ (m)) where u 1 Σ T
1 ll2
Observe that whh is a linear combination of m i.i.d. vectors, however, the coefficients of linear combinations T r:) are not independent from the vectors (2,)-1 themselves, since is coupled with 21,1- We will decouple the laws and make coefficients independent the vectors. To this end, consider (y, z) Pe; and 2 Ta-1 independent of (y, r, z). Then the following two random variables have identical laws:
T (((())) = T(y,r) r)
Vdz
/1
Using such argument for each of m samples, and vy viewed random vector of variables T(sn.r.)
(v (Vdž:)eemm) is sub-gaussian with variance parameter o < पe Em [1=2(])- Thus, with probabil-
ity -d have || l1 S a. vd. Therefore, suffices bound o.. By Lemma 27, for any 5 > 0 such that (18) < ed for some > O, we have with probability 1 - 6/2,
Kg log loglog ke
x log (1/( (og))////m(m//)))) (m/gm//))
< 1
Vlo((1/5)
1.5
m²
46

---

Here, the condition log(1/6) < ed arises from the fact the function g(z) = 1/(1 =2} only for some p < ed for some universal constant c 0.
has ||ll|p S 1
log Kig
VKee log Ke ml.5
Vlo((1/8) + 22 log(1 /6) log(m/6))
m²
Finally, for any 8 < e dt,
choosing sample size
CriVd
(1 1 vd
log ( 1)/2 (k-2221)/2 ( deit
))
m 2
(58)
88a.1
with probability 1 - -6/2- c-2d
82.1
and thus, || S o. v.vas Ba.ivd
d/
0.5
C
VCvd
vC
For C >>> sufficiently large, we obtain with probability 1 5/2 c-2
|| S d',1d'/4
Combining this with (57), with probability 1 - 5/22 e 2d dd
Ium - v2112 fin-vvll
2Bd, 2/d,1d//44
Therefore, we finally analyze our overlap combining with (57). For > sufficiently large, for any 5 > 0, for any m
Cravd
1 log (k+
d )) with probability 1 6,
82,1
va
P2.10
(Umi w-)
(v", w.) (Um v", ,",
Ba.1 Bd,1/4
d-1/4
1/mll2
| 122 + Ilum 11112 Ba,1 + 23d,1d2/4
Similarly, if (58), instead chose sample of size m 2
Cxid (1 + J log (k
d
Pa
Da.
for sufficiently large C >>> 1, then obtain tighter control weak recovery. With probability 1 5-2/ e 2d -d |um vz || and directly achieve
Saivd Sa.1 vC
| S a.vd
and |/mm v"1la S 28a,1
VCd
Combining this with (57), with probability 1 1
m, w.)
(00 w-) (Um v², w.)
3d,1 B8,1/4
| [mml 1|
10 2 +
Vm w" ||
Ba, + 2,3
Note that the regime of interest where we hope to succeed in polynomial sample and runtime is when Ea,llr>> >> poly(d)-1 i.e. which corresponds to Sa, >> poly(d)= for T from Requirement 1. In this regime, Lemma establishes that with sample complexity
CReVd 8
Ckyd 34
V /oo(L1/)
and
log(1/8)
one can achieve the overlaps
( w.)l 2 d 1/1/4 and (w w. N 1/4.
This nearly finishes the proof of Theorem for the case { (under stronger Assumption 2). De- pending on the problem, the sample complexity bound either matches the one provided in Theorem 2, or it is suboptimal by factor of ((vd). In the latter case, we can first get to (dd(d1/44) overlap, followed by another boosting phase, as long as the following assumption holds.
< C Va V vd).
Assumption 4. There exists > 3 and > 0 such that
Tea
(TE..II
Note that this assumption holds for Gaussian SIMs according to the discussion in Section 4, i.e. all = k, mod are all optimal for samples. The next section dedicated showing the guarantee for boosting procedure.
47

---

D.3 Boosting the overlap to achieve weak recovery
We now show how to boost the overlap from (2d(d1/44) to (1) We follow the boosting procedure introduced in [29]. The proof follows similarly, and we provide details for completeness.
Algorithm 2: A single step of the boosting algorithm on L 3.
Input :An example S { M.) i [ma]] ~idd ww.., the frequency / 3, transformation Tr, and vector wo such that (Wo, w.) 2 d d-1/4/4.
Output: The vector ii.
Let Y flog d] be the total number of steps be taken.
2 Divide the training set S {S(() Jieryy into disjoint collections of steps, where |(() /
for 1, ...., T do
wi 1,
5 end
Rerurn WT
Algorithm 3: boost-step
Input :An example set S of size m and vector such that (u, w.) = a E (d- (d-1/4/4,1/4)
Output: : The new vector Vwer with (Wrmn W.) aisa
Compute 0 21 Te(yis r2) z:) Z.,
2 Return D = |+||
We have the following guarantee for one step of boosting algorithm.
Lemma 9. There exists constant C Clk, () and c(k: () such that the following holds. For the input u such that (v, w.) = a E [d-0.2 /4, 1/4] of the boost-step procedure (Algorithm 3), we have that for any
d
m 2 CKę
32 20
at
with probability -dd we have Ouea (Vuzary w.) 2 20.
Using this lemma we can obtain the following theorem on the performance the boosting algorithm. Theorem 6. There exists constant C' C(k, 2) > 1 and c(k, () >> 0 such that the following holds. On the initialization (wo, w.)l d d-1/4/4, the boosting algorithm (Algorithm 2) the training set S whose size
Vdee
< Cki
$3
with probability dd we have ( w.) 1/4.
Proof. According Lemma 9, choosing |s(1)
ktd 30
(hiding constants in k. E), with
Pa.aa
probability 1 - ed we have (ww, w.)l | 2 20g- The sample size threshold for subsequent iteration is strictly less than 1/2 of the previous one since E [d-1/4, 1/4] and 2 3. Therefore, the overlap increases geometrically, and we have (wT, w.) 2 1/4 in Y = log(d=/4) = log d iterations. The probability of success is still 1 - e-e-d" by union bound over log d for smaller > 0. For the total sample size it suffices choose,
T
r
Vd
|
<
|s(0
(S())
Σ
S
2
E Ke 32
2
We now return to the deferred proof that shows the overlap increases geometrically the boost-step procedure.
48

---

we have with Proof of Lemma 9. Recall from Appendix B that we use Pt(.) Qe(-)/ / Maz to denote Gegenbauer polynomial that is normalized to have Pe(1) = 1. We first note that
e" = E = Ep... [Ty (,, B... (((,,))
= V. V
z))]
D. ((.,,)))) u)) P/ (( w.))w.
Consider any fixed w E gd and consider the following analysis. m (Te(ys ri) 2,) (2,, w) (v-, w)) Using Lemma 24, we can say that
Define X;
=
2 2 E[X;] - m² Ep (Tely, r) Q2((0, 2)) w)
m² (nee,
where we used the fact that g(z) - (,( (2, w)² is a polynomial of degree 24 with ||o||2 X 1. Thus, by Lemma 20, we have |[l|p S pf which allows us to use Lemma 24. Similarly, computing
|xillb < m
ElTTe(r))) Vi(lv, 2 (z) w) Ppup m
1
Tellepllllle
x
Kg kep(
m
g=)(2)
where we used the facts that Telllp S kept and gzz) is a polynomial of degree & with 19 S 1, and thus, by hypercontractivity, we have |1 2p S p Using Lemma 27, with probability - 5
1(0 w)), log' looloo///// m
log(1/6) log log ( m
Therefore, invoking this guarantee for w E (w., v}, we obtain that with probability - --e- edd
(0 w] (0- - -0---",)) v',2)1 log' ke log(1/8) + Ke log(1/5) log (k+6)/2 (m//))
Our next goal is to bound || l|2, where 8- the component of orthogonal to span w., v}. Due to rotational symmetry, w.l.o.g,, let us say w. = e₁ and e = ael + v1 a²ez. Then = 0 (6) - (6)2e2. So our goal is to bound
1 m
ll2
where
m Σ
Tel (() + v1 a² 22
Consider the following analysis similar to the proof Lemma 8. For a single sample (y, r, 2) ~ Per one can define Sd-3 independent of (y, r, 2). The following two random variables have identical distribution.
+ /1 - a²22) = Te(yr)) l'(azi + vI x²22)
2
Now let define / Vdz= consider 2;t the component of z, that is orthogonal to Using the identical argument from Lemma that 0 is sub-Gaussian in random variables (ž:)se(m), with probability 1 e 2d we have | a. Vd, where the parameter
m
(a VI a 21,2)²
r:)
m 2
d(1 2 -2,2)
Using exactly the same bounding strategy used in Lemma 8, for any 8 > dd probability 1 - d
log Kit
VKz log Ki
Vlog(1/8) x log(1/0) log (m/6) (m//)((mm))))))))))))))
+
m
1.5
m?
49

---

Overall, we can conclude that there exists some constant C(k, e) > such that choosing any
m 2 CKę
B2,0221-11
with probability - e-d=
| Isovaas Pa
af-2Bale
and - v~-v" w.) S af-
VCd
16
Combining have
a-2 Bale
00 S (1 o(1)
Finally, analyzing the quantity of desired interest under this high probability event that happens with probability -d=
(Ø, w.
(0" w.) + (0- v², w.)
(a) -9,,1a"'/11n 1/100
1e = (w w.)
-0012
10 12 + 1 0=12
(a.eP((a) + -B,eeaa //30
/ f-1
98a
2 (1+)(1))
100
2 2a
of at-1 +
50a 1
30
E
Online SGD estimator
In this section, we present the analysis of the online SGD on the harmonic loss which stated in Theorem 3. As in Section 3, we will implement the algorithm Te for E > 2. We work under the following assumption
Assumption 5. For each 2 1, we assume that there exists Te such that Tellz= 1, TeT S ke. consider Te = Ea,e//lEa,ellla and we have the following inequality
[e,,elle S &Cllaa,ellis,
(59)
and we denote (y, 2))] Ba,e 0.
We perform online stochastic gradient descent on the squared loss
L(w; 2,, ye, rt) (Te(s,, r.) Qe((u, (()))
(60)
We consider spherical gradients and project at each step to keep w, E gd-1
Algorithm Online SGD algorithm on the frequency
Input :An example set S {(x,, 81) e [m]]] ~id Pu.. the frequency e > 2, and transformation Tz, step size and number of step-size. An
Output An estimator ú IRd
Decompose 2; = 2;).
Sample Wi E 1d-1
for i 1,..., NN do
Compute Li = L L( 11
wi- v 1
Let w;
100 -- T.
end
7 Return w..
We state the formal statement for weak recovery of online SGD. We focus weak recovery, and refer the section for explanations on how boost the weak to strong recovery. We also only focus on l 2 3, however notice that the proof can be adapted to the cases & E (1,2).
50

---

Theorem 7 (Online SGD for learning va ) Let (wi)120 the iterates of the SGD dynamics with the loss given by (60), with b > (where only depends on E) then conditionally on ma 2 b then have
va we
Code-1
1/2
Bag
with probability at least forrr some constant <>> 0.
The proof of this theorem will follow by adapting the arguments from [10, 88).
The good initialization probability is at least constant (see [88, Appendix A]). Thus, the above online SGD algorithm succeeds in total with probability at least constant bounded away from zero. We can then boost the confidence to 1 by just choosing the best estimator over multiple starts, and Ollog(1/5 (1)6) trails suffice.
Let introduce some notations for the following, denote m. = (we, w.., we define To inf 2 O: m, I c), and To inf (t 2 0: 2 c}.
Proof of theorem 7. Let f 3. Consider transformation Te given by assumption 5. We first state lemma 10 on the population loss defined as
[(w) E\L(w; 2.
(61)
Lemma 10 (Population loss). Let 2 consider the normalized tranformation Te given by Assumption 5, we then have the following inequality
8* d
(VS" [(w),, w.) S -2(1 (0m))m²) E(E + d -2) --1 (w, w. -0
VYn 2 2
(62)
(2- (--))(+d-3) where s" (E-d/2 (1-d//23)((-d/22-) (/E(
Discretization bounds. In this part, we give bounds on the discretization error from the online SGD and the population loss gradient flow. Consider the SGD iterations
W2 V L(wa; 2t, Tt, M1b
Wr+1
wi 17 V L(w;; 21, Tes Mc)l
initialized wo uniformly on the sphere 5 Proposition 4 (Discretization bound). Consider
K2dTT²
(-2 2( + K2nP + 2bd /2n(Ba. + n/33/2)
6²
Ka
+ exx
K27 b
+
b
where we define
1/2
K1 KL
4e
log( ( 2/12
7
4e
46/2
||T2
46/2
K2 4KE
|| log
48
||
4e
f/2
Kg 2K
log( (e]l))2))))
With probability at least Ko. we have
mT 2 170
+ nBr.d
Fe+ 2)
T
Σ
mm)mm
2
d-
t=0
Conditioned on the event {T < 4 N T vaal we have the following inequality
+ 1Bedd e. (e -2)
T-1
Σ
mr 2
Vd
(d - 1)2c+1
m
1=U
51

---

Sample complexity for weak recovery We are interested in the weak recovery setting i. we want to bound 71/2- We work under the event {T I 1/2 ^ 22-- 22-/ 25r/vall , we then can apply the same analysis as
in [88]. We choose c4 a we then have
/2-11-1
TT/2 -
Be, (d-1)2eFf
(((+d-2)
with probability at least
K2tKg/bbl
exp
62 20 20b,,+ (od--))))) Rearranging this, it gives
us
2d
-d
(e d 2)
1/2 S
8 (ύ-1))Fा
b((+d-2)
F
c2
(d 1)2c+1
Proof of Lemma 10
Proof. We have the expansion
+00 B(Te(y, = Σ 0a ((w., z))- k=0
(63)
Consider the population mean-squared loss (we also directly the correlation loss)
[(w) = (g. (Trlu.)) - -T ((0,, = - 2B2,, Telu: r) ((w, ((w,
Using the above decomposition (63), and orthogonality of spherical harmonies
((w) -, ((w.,))) ((w, 2})].
(64)
Using the identity (35) and plugging it into (64), we then have
[(w) = 2 2 Ba,E 2:00) ((w., w)).
Vnr,a
Let denote (w., w). rewrite the loss in term of the overlap parameter. The spherical gradient of the population loss given by
( L(ww) wx) = -(1 m² m²))((m) 22(1 m²²
Ba.e MddE (0 w))
We can use the representation of the derivative of Gegenbauer i.e (2) E(E+d-2) 2)a (d+2) (z) ([88) Fact C.3). So, the loss can be written as (d- 1ynaaaee-
( ((w), w²) -1--mmmm
11-mia m m3))(()) = 201---11111111
m²) (001mm²)
Ba 2) (d+2) ((w., 1) TTa+2e--1
(ww,,) w))
We the facts C.4 and C.5 from [88] (note that the Gegenbauer polynomials in [88] is normalized such that p(d) (1) = 1, meanwhile we consider Q (1) = BBdd f)) to state that
8 : (VS* L(w)), w.) < 221 m ),3
E(E + d- 22) (w. w.) w.ye-1
Vm > 2 V
(65)
(6-))6+--9)) cos( π 7/2).
where 8" =
(T-4/2 10-42-3310+d/222 3)(4+4/2-21
52

---

Proof of Proposition 4
Proof. In the following, we denote Tt lw2 V L(w,; Zc, we)l and the martingale part M. L(w;; 8c) [ wt zc. ). We have the recursion
m++1
my V Tt
((w)). - 7 V w M. "..w"))
(66)
The strategy of the proof is to use the results from [88]. The proofs of these lemmas are classical bounds of martingale relying on some assumptions on the moments of the gradients. Notice here that C' is no longer a constant and extra care of the analysis is necessary for the proof of Lemma [88, Lemma B.4]. To the lemmas [88, Lemmas B.2.B.3.B.4], we need prove the bounds on the growth of gradients norms of [88, Lemma B.8]. We check this
E (s. [I| V
L(w;; 2e, 10l (yy,))
||| Pw, (z.)(Q( ( ((w,))))(w)))))) Te)
[10 (:)))((()) !
< (y)a))
|0/4-3) ((w, 2)){ Te(
S C R
4e
8/2
S dl
EE r) log(1/H (T)
[ee] i
8/2
< Kdl
log( (
S dKc,
where we have used Lemma 24, the identity and the hypercontractivity and Jensen inequality in the last line. E Bgg,r,))
V L(wi; Ze, Tes w.)1
Eg
[|]P (2.)( (e)(( ((w, z.) Te(u,
(10)))(( 21. TT(.))) []
s E (g.
? ((w, 2)){ (e r)12
< "(dY
44
48/2
|
46/2
S <4C(d)
[|e]l log
48
|
(4e)
46/2
||Tell
46/2
S KE
||Te|1 log
48
||Tel
S Kg
We have M M(w;; Zz, re, vt) L(w,; 22, Tz, U1) E[L(w;; Zt, Tr, w:)] hence
( M(w Ze. vr), w.) (VS"-' (L(w;) Ze: Ft: v.), w.) ERVE (L(w;; Z,, Tr, Ve.)), vc), w)))))))
(wo, V (T.(w);; Fr, re, 91)) Blm((w, V 26,
(T.w,
y+))]
We then have
E K 8d-1 (M(w: Ze, Vi), w.),
21, 2Var ( (T St, vt), w,)) Var (ww, Vo-- (1, vm))m
$ 2Z(( w.) ((Q (( 2,) (T),) 2E w.) (Q) (0) ( 2,)) 2T())
1/2
4e
< 2K
log
Tel TT]l2) := ;= K3.,
where we have used the inequality (a + 6)2 < 2(a² + 1P), and hypercontractivity of Gegenbauer polynomials (lemma 20).
53

---

Conditioned on the event {T S T22 //2 and using the inequality (65), we have
m++11 m4 + 21((1 - m2) L (l+ --dd22 2) mi f-1
- 1/ Me, w0))
d
Using the following bound on rt, which for all N, we have
1/ri 2 v w. L(we: Mes re, 2.)11
and plugging this into previous inequality, we have
m++1 2 20- 8. (f+ d 2) mi
m7 V M,, - pmml || Vw, I(ws yt. rt, 21)112-12
d-1
(67)
where fr = V I L( yr. rr, zT)11 1(V L(w:; UT, 2r); w=)))) w²)
We [88, Lemma B.3] state that with probability least 1 Katy"
x we have for all À >
sup 7
M w0)
S.A
(68)
KT
k=
We employ [88, Lemma B.6] state that for all À > with probability least 1 Tay have
we
sup T
3
E S.A.
(69)
k=0
We sum the equation (67) to obtain
mr 2 mo + 2m
Br.al (L + d 2)
P-1
Σ
(1 m2) m)
8-1
17
T-1
(P8
M,
d-1
==0
1=
n
me|
V Ww,
L(w To, Te, #1)1
Σ
t=0
(=0
We then use (69) and plug it into (67), and use X = b/vd, to state that with probability at least
12
JRiKaTn'' we have
1
62
mer 2
7mo
2m
se (e+ d 2)
T-1
Σ
m m
17
Σ me V (ww Ve, rt, 2t)
10
d d-1
(70)
We now bound the term coming from the projection step in incquality (70). We adapt the proof to take account the dependency on |eell..
Lemma 11.
For all > 0, ifror all L S S (26/vd, and v S ellgellle with probability
o2 exp x
at least
( -11 (d4/2) we have
2 +K
T
T-1
E Σ (1- m2) t=
2) m, 8-1 d-1
mel www L(we: yes TI, 21) +
22.
1=0
Proof. The proof is slight adaptation of [88, Lemma B.4,B.5). An adaptation of the proof of Lemma B.4 gives the following. For all À > if for all t T, ma E [2b/ /d, 1/2], and n 0, we have
T-1
X²
P(n
Σ 1=
exp
2(32 + K2d3 + 22m + ndd322)
Besides, the adaptation of Lemma B.5 gives us
m. | - L 01 21)
K2Td//27
P sup TST
A
Combining the two inequalities, end up the desired claim.
54

---

We then use À = b/ /d, and we obtain that with probability at least K2,K, where
Ki.Kas
of + exp
8
VRIKoTiPa-
+
2( + K2ddr)))
2bd //d
+ ndd322)
62
have
m& 2
170
+ 3r, d-1
8. de
2)
T
Σ
m m -
2
Conditioned on the event {T & 1/2 A T
/25/va we have the following inequality
+ BBedd +e 2)
T-1
Σ
m
mr 2
Vd
(d - 1)2c+1
55

---

Harmonic tensor unfolding
In this appendix, we analyze the harmonic tensor unfolding estimators (TU-Alg-b) and (TU-Alg), with integer f 3, and prove the guarantees in Theorem 4. For simplicity, assume throughout that the transformation Ta x Rgo + is bounded, with
TT 1,
|0 S Ki.
ET,(Te(Y, ())) Sd,e-
(71)
Without loss of generality, take Ba,t 0. We describe in Remark F.1 how relax this condition.
Algorithms and guarantees
Consider first the naive tensor unfolding algorithm. Compute the empirical tensor
Tely,, (,)H((())) E (RR)),
ke(m]
where H2((z) is the degree-l harmonic tensor (see Section F.3). Consider the 'unfolded" matrix
Matr.,(T) (T) E 1dd xd with / = === =/2 if even, and / = Le/2], J = Le/2] + 1 o.w.
and compute
(Matr (T)) gallaa
the top left singular vector Mat,, (T). We then estimate i via
w Vec (si (Matr.,(tt))
(TU-Alg-b)
where the mapping Vec : Rd gd-1 applied to u E Rd returns the top left eigenvector of the folded matrix Mat E Rdxd" that is,
Vec(u) = arg max w
J..
wc R
We first show the following guarantee.
Theorem (Balanced Harmonic tensor unfolding, even). Let va La be spherical SIM and be an even integer. Consider Te transformation satisfying (71). Their exists universal constant C₁ > O such that the following holds. For O, given m samples (Yis Dz)) wiid P Pugas. with
de/2 [1 + Bag log(d/5)),
2 Caise
(72)
d.e
the estimator to in (TU-Alg-b) satisfies (ro, w.)l 1/4 with probability at least 5. Furthermore, in can be computed with power iteration in Oa(md log(d) runtime.
We prove the sample guarantee of Theorem in Section F.4 and the runtime guarantee in Section F.6. Thus, when f is even and choosing Te such that Ba.t = O([[Ea.elIx)) the algorithm (TU-Alg-b) achieves almost optimal sample and runtime on Va,e:
1/2
d
log(d),
T
log 2 (d).
|[Eaee1E2
||E
When |k (ol/log(d)) then this algorithm achieves optimal sample complexity m x d/2 3/22/1lEa,ell?... When e is odd, however, the algorithm (TU-Alg-b) requires and is suboptimal by factor dt/2, This is due to the covariance structure the Harmonic tensor He(z):: similar problem, with same suboptimality, arises for tensor PCA with symmetric noise [67] (if the noise not symmetric and all entries are independent, then optimal complexity achieved by the naive tensor unfolding algorithm [48]).
df</2) /IEa.ell
56

---

Here, we modify (TU-Alg-b) by removing the diagonal elements. Consider integers a, 6 2 such that a < b and b = f. Introduce the matrices
Mi
Σ LE/m]
12) Mat, E Rd xd"
m
M2 m
Te(U:. 2 Mat Rd"
mE(m
and
M M, M2
Σ
MMt E Rd
m iF
Note that
E|M] (1 - m r Mat [Iw
Thus, we define our tensor unfolding estimator to be
i
Vec 81 (M)
(TU-Alg)
where (M) is the top left eigenvector of M.
Theorem 9 (Harmonic tensor unfolding). Let Va E La be a spherical SIM and let a, b 2 1 be two b and + b = f. Consider Te a transformation satisfying (71). There exist
integers such that universal constants ct, C2 > 0 that only depend on such that the following holds. Given m samples (yi, Vi) wid Fugww with
de/2
m 2 CeRR
(73)
32.5
the estimator in (TU-Alg) satisfies (vá,, u..)l 2 1/4 with probability at least 1 - Further- more, to can be computed with power iteration in Oa(mdd log(d)) runtime.
We prove the sample guarantee of Theorem 9 in Section F.5 and the runtime guarantee in Section F.6. Thus choosing Te such that Sa,e ((IEa,eelax)) the algorithm (TU-Alg) achieves optimal sample complexity
d//2
for all 1 < a < b. Choosing a < b with a + with smallest runtime, we obtain the following learning guarantees:
d//2
de+1
even:
and Tx
log(d) by taking a = =122 and b = f/2 1,
|E d²/2
|1 l!;
1/1/
E odd:
and T
|K 1 log(d) by taking
[f/2] and b [t/2].
F.2
Notations
Below, we introduce some notations from tensor calculus that will be useful throughout our proofs. Let A, B (Rdjet be two Ê-tensors. We define the inner-product
(A, = Σ A
B Biy
(74)
In particular, the Frobenius norm of the tensor is ||A|| = (A, 1)2/2 For A E (Rd)@r and
B E (IR)) with k < L, we define the contraction A E (Rd))((-K) to be the (L -tesooo with entries given by
A B P =
Σ
A Ca...BrrBye Bir---ieaoke
(75)
57

---

In particular, if l = f, we have A[B] B[A] = (), We further introduce partial contraction
A 8r B of E (RR)) and B E (RR))k, with r S min(L, (), given by
(A 8r B Bi
A
(76)
Eld]
Given a permutation т E G, and A E (R)))r we define ((A) to be the tensor obtained by permuting the coordinates of A with permutation n, that is
(A) Di... Alc
(77)
We define the symmetrization operator Sym (IR))0 + (IEd) such that for each tensor A (Rd)), it outputs its symmetrized version
Sym = A
Σ (A).
(78)
TE6
We denote (0f) the image of this operator, that is, the space of symmetric é-tensors.
We denote the unfolded matrix of the tensor T (Rd)&t as Mat (T) E Rdd Rd with entries given by
where we identify (d.....;Tg) 1n)) with 1+ ++Ei,i (ix 1---11d 1)dh and (ji..... . je-g) with 1 1+ Ef 1)d+-1_ For clarity, we will drop the dependency on g in the proofs, since the unfolding parameter will be made clear. Similarly, with slight overloading, we denote Mat,,e-q RRdd _ Rdd x folding operation that takes a vector u E Rdd and associate the matrix
(Mat (1) (ts Ma
where we identify the index (i1...., ie) with 1 Et= (1x 1)dh-1.
Throughout the proofs, we denote C' an absolute constant and Cg a constant that only depends on & In particular, the value of these constants are allowed to change from line line.
Harmonic tensors and their properties
We start by defining harmonic tensors and present some basic properties about them.
Definition 2 (Harmonic Tensors), For every e >> O, we define He gd-1 Sym((R)))) the unique symmetric tensor such that for all 2, w E gd-1 we have
Q,0 ((z = (He(z), )1)
(79)
where a is the degree-l (normalized) Gegenbauer polynomial as defined in Appendix B.
In words, harmonic tensors can be seen as the projection of z tt into the space of traceless symmetric tensors. Note that the uniqueness of (79) follows simply by stating that (He(z) (z),,, w is degree-E polynomial in w that is identically zero, and therefore He(z) = H2(z), where we use that He(z) assumed to be symmetric.
Further note that these tensors are equivariant with respect to rotations: let E Oa. then Hz(Oz) = O o (H))(, where the contraction is along one coordinate for each O, that is
H₂ Hz(Oz)) Din.niig
Σ
II Or.i. [E|(
He(z) Hr(z)aa..eee
in SeEd
(This follows simply by noting that Qx Oz)) = (w, z)).)
Recall the zonal property of Gegenbauer polynomials:
58

---

Lemma 12 (Zonal property of Gegenbauer polynomials [25]). Let f E L2((S-1).. Consider the projection Vv., of f onto the subspace Va,: of degree-l spherical harmonics. This projection can be writlen as
f(x)) = Vaat Ex [f)) ((2,))(((x
(80)
The following lemma follows directly from this property:
Lemma 13 (Reproducing property of harmonic tensors). Let E, k N. We have the identity
8tk He(w).
EXNTa
z) 2)){H((z)]
(81)
Vna.t
This property will be key to our analysis of our tensor unfolding algorithm. Indeed, recalling the definition Sa. E.,, [Y, (Z), have
Bale He(w.). Vna.
((Tely.r)Hee2a
(82)
We further list some useful properties of harmonic tensors below. In particular, the last property states that the principal component He(w,,) is (d(d4/2) w that is the principal component of the expectation of our empirical tensor @2(1) u0
Proposition 5 (Properties of harmonic tensors). Let l E N and Hz(z) the harmonic tensor from Definition 2.
(i) We have the following explicit formula:
18/2]
H₂(z) = Σ
cej Sym(=01e-2) @ 1
(83)
1=0
where
el
(d/2-1)e- 1)e-s (d - 2)e
Ci, = (-1)-2e-2)
Vnalt
gI(e 2j)!
with (a)p = a(a + 1) (a+ 1-1 the (rising) Pochhammer symbol. In particular, we have Ct, = (22))
(ii) Conversely, we have the identity
[e/2]
Σ
bej Sym(He-2y(z) 1
(84)
j=0
where
8!
(d/2 + (- 2 1) 2)e-2j
be,j = 2 jI(E - 2j)!
1 1)(22)(d/2) ma,e-2j
In particular, we have be.j = Oi(d-(12)
(iii) The harmonic tensors satisfy the following recurrence relation:
He+1(z) = a (1) Sym((He(2) 2) a Sym(He-2(2)) Ia),
(85)
where we denoted He(z) = H2((2/ /na,t and
28 + d
(2) a&t
0 d-2+(
d l 2
(iv) The leading principal component of He(z) satisfies
[[HLe(z) - 0z || = 02(22/2-1/2),
(86)
where recall that ||0,,000111 || C. Oa(d!/2).
59

---

Proof. The identities in parts (i), (ii) and (iii) simply follows from standard identities on Gegenbauer polynomials. To prove part (iv), using identity (83), we have
f/2
[[Ho(z) c0,0=0f11 v
cr [|SSmm=
[2/2
L4/2] Hell
ce,
|1|=112
Σ
lecyldi/3= (2122/21122)
where we used that |cr,y| Oa(d
Additionally, it is interesting to introduce the following tensor:
(2)
Ra.E Benra He(z) & He) E (1R))
(87)
In particular, by the reproducing property, we have for all qe, a E gd-1
2))] (B(He(z)) & He(z)), w 0e @ u s
1 (2))))
w 00 u 80) Vnn,e
Qe((u,
Vnat
and we can write
(Hl(z)), w w = (-/ (2)
So..
Note that 2/"h is only partially symmetric. Using Proposition 5.(i), we decompose this tensor explicitly into
[//2]
Σ
Cej
Sym (Ia (18((22)) (La @ 1a)
(88)
j=0
where we introduced an alternate symmetrizer S such that
Syma (18 (11-21) (La & Ia) La)
Σ
Sym(er, .... ere 8 211 @ Sym(er, .... @ Cre 2 210),
with (ex)seja) the canonical basis Rd
F.4 Proof of Theorem
Proof of Theorem 8. Denote é 2p and introduce the matrices
Z, = Te(ss, r;) H(z;) E TR dd where H(2,) = Mat,. (He(z)) E xd
and the centered matrices
Z, Z E,
where E - = E(Te(U,))
By the reproducing property (82) and Proposition 5.(iv). we have
E Balt
Ct
[w
8p @ + Ba
(89)
Mugf
where A S Ced-1/2 1/2 and c Mud Oa(1).
We consider the symmetric matrix
M
Σ Z
iE(m]
60

---

and bound we have
JM E'lop using Lemma 25. First, note that by applying Lemma 14 with A = u X
0+ (M -))²
sup
(l, (M - E)o}
u
(90)
sup [( (2,)0)) C₁ m
m u.vEStP-1
Further, note that
rM E)² = [[R[(M - EM E)oo dd (M E)² S Cani d
(91)
m
Using that || H (2,) I C2d deterministically and combining the above displays into Lemma 25, obtain with probability at least 1 5 that
di
d _ m
log log)
1/2 v
IM Ellopp S Cassy
1 +
where we assumed without loss of generality that From Eq. (89) and by Davis-Kahan theorem, the leading eigenvector of M satisfy
avoid carrying additional terms.
Ks, xPP 2 1 77
with probability at least 8 when
Ke de/2
m 2 Cr 172 89,
[1 + Ba, log(d/0)
The estimator i Vee(s) is obtained by taking the top eigenvector of
Mat p- (Sst,,p-())Maa.pp-111
= w.w, T Mat w @D Mat + Mat,,p-1(04 8P Mat "op
so that
Mat (s) w.w.looo llop 2||s "/' 2//1-
Thus, taking 7) constant small enough, we obtain (wo, w.)l I 1/4 by Davis-Kahan theorem.
Lemma 14. There exists constant Ce O such that for all A E (Rd) ye have
Ex ()+ < C/
Proof. Using the identity for the quadratic tensor (88), we decompose
Ex [HH)(z),
(x(He(())
H+(2)), A A
1
(X(2)
A ② A)
LE/2]
1
Σ 7'
CoS (E1)2
f=0
T
[//2]
lceal d |A
1=0
AI
where we used that I < d' ||A! and lee S C2d/2-55
61

---

Remark F.1. To relax the boundedness assumption in the above proof, the only changes are in the
bound on a. (. E) and
Z lopppp- First, note that for all > 1, we have by Hölder's inequality
1
a.(M E)
E[Te(u, (z)o))
sup wEBdP-2
m
1 E[ r) -2
sup El H(2)))
m
wE3dP-1
1 |Telll 2/n)
< m
sup wE84P-1
(u, (z)o)
$ Cc + 2/m)*
where we used hypercontractivity of degree- spherical harmonics. Thus long as | 1,2+ (1) for some 17 (1))), the bound does not change. Furthermore, for all integer q
Zi|log lopp 2 R) S TP( (maxx (Te( ee Rm/dd) < (c= rEim]
dp
P Mmmxx KE [m
Rm
If assume that ||Te|| qdeh for all y, set g log(m) and obtain essentially the same guarantees as above. For the second algorithm (TU-Alg), we can be less careful and simply set q C2 and only assume [e Ce.
F55 Proof of Theorem 9
Proof of Theorem 9. Step Decomposing || E[M]]lop- Recall that we fix = a + b with positive integers S b. Introduce the matrices
Z:
Tely, rz) Hz,)) xd"
where H(z,) Mat,,& (He(zz)) Rdd
and the centered matrices
Z, Z, E, where E = E|Z,] = B(Te((,,)
Recall that by the reproducing property (82) and Proposition 5.(iv), have
E = Ba,e
Ct Vnalt
ww
-0 @
+ Ba,eAg.
(92)
where Elop < 1/2 and c2,0/ /ud,t O1()). For convenience, we consider a slight change of normalization and define
M =
1
Σ Z.Z
m(m
such that
E M = EET
w
2a
Ba
+
82 Ao
A S 1/2
(93)
By a standard decoupling argument (see [80, 33] Chapter 6.1), there exists an absolute constant
C > 0 such that
PP ( -ME-EETT
EET
opp 2t =t)
M
EET
op 2t)
where we defined
1
M m(m 1) itj
with Z, Te( and (0,, Fy. 25)je(m) are iid independent of (yi, Ti, 2i) Thus, it is enough to study the concentration of M:
M
Σ Z.B.,
where B, m
Σ Z
1m(m]
jfi
62

---

Thus we decompose M EE = A + A where
1 Σ B
ic(m]
(94)
A
Σ
E(B;
-
Σ :c/ml
E(Z: E)
m
m
ie(m]
We bound the operator norm these two matrices below.
Step 2: Bound on [: [oollopp For all i E [m]] we have
5 m
E
Z.. where $
Zj E.
m
m1
iE(m]
Note that Zillop S |ell
/2 so that H (2;))
loop I ||S lop + C. + Cere d
(95)
m
We use Lemma 25 to bound
|11op Applying Lemma 14 with A = v,
(S) S
E (u, Z 2
sup LEEa
uega
E (((((z) 2 v)
sup wE vegatt
C
To bound ($), we simply use
E
E
1lap
sup -
Elu
S d
sup vegat-
Su) dso,,
(96)
ueBan-1 -leget
so that
OS)² < max(d" d' ($)² < CANi
Combining the above displays into Lemma 25, get with probability at least 1 de
d²/2
t1/2
d //3--//6///3
f/6,2/3
d//2
S I
Ceki
1/2
m2/22
m2/3
We deduce that with probability at least 1 - 8/3.
db
d log (d/8)
1/2
sup
|Blloop S Cerey
1 +
v
(97)
xE|m]
where we assumed without loss of generality that e-d avoid carrying extra terms.
Step 3: Bound on A Allop- Let's bound A conditioned on (ji, Fi, &:)se(m] Using Lemma 14 with
A B. X u.
m a,(A))²
Σ sup B((u, Z.B.o)3)
vE[mi
-
(98)
C
C ro sup |B
B((H((z)), u2) 2) m ic(ml
sup
m
-1
7E(m
Furthermore, similarly to Eq. (96),
Cek? da s5(m]
t A do (A.)
sup
B
(99)
63

---

Next, for all 2 1, we have
E B
@ppl
1/p
S dan
sup
(u, B. v) 20/1///
I <d
sup 0
El B u) S Cidlap'n
k2
sup B ic(ml
up
where used the triangular inequality in the first line and hypencontractivity of degree- spherical harmonics on the second line. In particular,
1/2p
E sup Iz.B [lppl m
1/2 v
1 m
Σ E mm(m)
S
de Cake m iE(m]
122
sup
Billopp
sE(m]
Taking p log(m), we can set
de
R
Ceri log m
e/2 (m)) sup ic|ml
BBllop.
Similarly,
2p
IP
1
|Z.B. llop
R
Ceke /2 sup sE(m]
da Rm
|B:llop] 6.
sE(m] m
Taking p C'log(m/0), we can choose
CeKs dm m
log
6/2 (m/8)
sup iE(m]
Billoop
(100)
Combining Eqs. (98), (99) and (100) into Lemma 25, we obtain with probability at least - 6/3
1/2
da
d' log fegg+tt///// (d/5)
A S Cere
sup
B
llop
1
v1
(101)
iE[m]
m
m
where we assumed without loss of generality that >> e to avoid carrying extra terms.
Step 4: Bound on ||apllop- Following the exact same argument for A and recalling that
E op S Copa,e we directly get with probability least 1 -5/3.
1/2
da
dd log + (d/6)
A lop S CeBa,eKe
1
V1
(102)
m
m
Step 4: Concluding, Combining the bounds (93), (97), (101) and (102), we obtain with probability least 1 6,
M B3. c.o (w0 [ nd,t
Sa
|Aillop + ||
lpp
Ge + Ceni / dd22 d' log e+ (d/8)
1 +
v1
m
m
where we used that a a b = Thus by Davis- Kahan theorem, the leading eigenvector M satisfy
(s wo > 1)
with probability at least - 8 when
m C 2 1/2
log 2/2+2 (d/6)) d//4-//2
Bas
1 1
By
The theorem follows by the same argument in Section F.4.
64

---

F.6 Runtime of the tensor unfolding algorithm
The overall runtime of the algorithm depends on the runtime for matrix-vector vector multiplication of the matrices (z) Mat,, (Hz(z). We show that the total runtime if (mmax(d" dd"),, that is, one does not need to compute the d x d = d' entries of H (z) to do matrix-vector multiplication with the (unfolded) harmonic tensor. The total runtime algorithms (TU-Alg-b) b) and (TU-Alg) in Theorems 8 and follows by recalling that the leading eigenvector can be obtained with @a iterations of the power method.
Lemma 15. For integers a, 2 1 with & = a + b, there exist C₁ that only depends on E such that malrix-vector maltiplication with matrix (z) Matt.. (He(()) requires most Ce(d d³) elementary operations.
Proof. Using the identity (83) in Proposition 5, can decompose
[2/2]
H(2)
Σ
Cej
M (Sym(z (e- 21) @ 1)
Thus, we can decompose (2) into C₁ matrices the following form (without loss of generality):
OPI
82
Eesl
8pa x
X
Eeki
fiomnfa E(d). drunddng Eld] Ra Ri....kuEdd
(E(11]
IE [u]
(92)
IE
M
Σ
Σ
SPI X
82
Ceuu
Σ
OF2 60
82
Eesi
Pi....oo E(4
LE [M]
Ji...do Eld)
rE(s2]
IE [u]
where P1 + P2 2j, 81 + 82 + = J. P1 + 281 + u = a and P2 + 282 + u b. The total number of operations to multiply this matrix by vector is then given by
Od (d (d d = Oa (dutprton + dutpatoz) = O2(dd + td))
which concludes the proof of this lemma.
F.7 Additional discussions
In this section, we provide an additional discussion on the use of the Harmonic tensor. First, note that all the properties discussed in Section F.3 can be derived using the following Wick's formula for spherical measure and tedious calculations:
Lemma 16 (Wick's formula). Let be uniform vector on gd-1 We have
2p
E2
kk
d(d 2)... (d + 2p 2)
Σ
II
Skcksr
(103)
1=1
pairings (a.d)ET
where the sum runs over all (2p 1)!! perfect pairings π of (1, 2k)..
We note that for our tensor unfolding algorithm, it is enough consider simplified tensor Kc₃ that only keeps the off-diagonal entries of the harmonic tensor.
Definition 3 (Elementary symmetric tensors). For every E, we define K2 : gd-1 + Sym (Rd (Rd))() the tensor obtained from Ht by putting in the entries with repeated indices: for all z E 8d-1 the tensor Kz(z) has entries
Hel ( Ce,02i, 24 2..... ... Zig
f2 ... # ies
Kg(z)i
(104)
10
otherwise.
65

---

For convenience, we will denote Id.y the set of all subset of indices in [d] with no repetitions. From the reproducing property of (2) we have similarly
Ba.e KC(ww). Vns.t
B (T(.
(105)
Apply a random rotation to all the input vectors z,. Equivalently, this amounts to having w. Td- This guarantees that ws is not aligned with any coordinate vector with high probability.
Lemma 17. Assume
Td. Define A(w) Ke(w)//ceo w Then there exist universal constants c, > O such that for all 2 0,
P(I)((w)]I 1p 2 (CC++)/00 - 2exp(-cdi1
(106)
Proof. Simply use that the non-zero entries A A(w) have at least one repeated index:
| S 6
Σ
w 26-2 Wie S elwwl
Then the tail bound (106) follows from standard concentration argument.
From this lemma, we deduce that
Mat, (BTT(())))))))))))())) = PuLe /nd.t
cr.0
(1 pD-T- (1
A):
(107)
where with probability at least e- the random rotation, we have || ol 1/2-1/2, Thus, is enough to consider the tensor XCe which has slightly simpler properties. For example,
Mat ([[[C((*) x KC(()))) = CE,0 Po.
Po. TEB:
Vna,e E!
where P, the permutation matrix with non-zero entry at row and column a(i)-
Lemma 18. For integer &. > 2 and p LL/2], there exist Ct that only depends on & such that matrix- vector multiplication with matrix
requires at most C/2 elementary operations.
Proof. Let us use Newton Girard identities decompose Kz(z). Note that Ke(z) corresponds to the ê-th elementary symmetric polynomial (in tensor form):
K2(z) = Elce.o
Σ
Zi, Sym(e, X @ (e,)).
Denote + partition of l with 1 fh so that Ejetq azj and |>| = ai +... ag. Then there exist coefficients ex such that (see Lemma 19 below)
Ca
Ke(z)) Elce,o M
Cymm
II jE(()
Σ k
e
(108)
Let's decompose (XCe()) as sum matrices associated to each À (the partition) and a 6 (the permutation in the symmetrization operator). The number of such matrices only depends Let us bound the runtime for doing a matrix-vector multiplication for each of these matrices. For each j E [4] and E [ay]. the tensor e &j has its indices εj, + fJz = j split into е,,t left indices and fú. right indices. Denote & the set of j [f], t [aj] with aj > O, and the subsets E = E that contains respectively the indices with {ej,r > 0, fr. > 0). (ej > 0, 0,, = 0} and {eg, = f. > 0). Then we can write the matrix (up to permutation of the indices)
Σ
II
Desi Exu
ekui
(Ng.)ii.eee (i,))E
(GiD)E
(irr)e
MII (1.0)En
Σ
II
Σ
II
Bega ekes
Σ
II
e
(KAAleDEEE (1,0)EE
(ky.hG.WEE
(1.))S
G.D)ES
(1,)EE
66

---

For each {kg, ( the left and right vectors take Oz(dlfz)) and Ou(dlEx)) operations to compute. Therefore the total runtime is
Oa (dlearl (dlEal + ddén)) - =O (dlEulttEn) + d (efE))) O2 (df + d) Oa (a( (dle/21)
where we used that [E + E I p the number of indices in the left side of the matrix, and [Eal + [E S f the number of indices on the right side of the matrix.
Lemma (Newton-Girane identities). Denote for each integers E, 2 1,
Q+(z)=
E
Σ
Fig
Ziee
Ps(z)
Σ #
KE[d]
the elementary symmetric and power-sum symmetric polyorriiolyynmii respectively, We have
Qc(z)= =
(109)
where À = 1a:200 for and
CA
aylaz! ae! e: 2m.
Using Eq. (109), we have the following polynomial identity: for all u E Rd.
(KC(()) u @ Qz u) flee.o
P(=))-M (2 u)
AF-
Matching the coefficients in these polynomials in u yields the identity (108).
G Proofs for Gaussian SIMs
In this, we shall prove the results from Section We first start by showing the rates on L norm of coefficients ε for a Gaussian SIM of generative exponent k, (cf. Lemma 1).
We start by recalling that, from [29], the generative exponent k, (p) only defined for p whose Va is such that V/ < Va,0, where Fd, == Va,Y @ @ Td,1 is completely decoupled null. In particular, d (12 is bounded by constant independent of d. Let (ua)a>1 be the sequence of spherical SIMs associated to the Gaussian SIM p. i.e. V/R = Xa and va(YY Z, R) p(Y Z RR) p(Y X). Let Pa. Py MR & vz. Let consider the likelihood ratio decomposition in L (Va.)) identical to the one in [29, Lemma D.1]
Proof Lemma 1:
dua diz,o
1.3 (Pa.0)
(rx =), (v) = (Y.R.Z))= Heg (R 2) Y = y).
Ily which are completely determined the model independent of d, and by definition of generative exponent (2) we have X?_ > We now use the decomposition Hermite into Gegenbauer polynomials from Proposition 2 to rewrite the above as
Denote A
dva duaoo (y, r2, -
(P(Paa)
Σ (N( k2k.
Σ
Σ 2 (2) E=O
(2)
Σ Bu.e(r)(a
t=:
k2k.
(110)
We now expand the same directly in the Gegenbauer basis
dva diu.o
(y. 22) (32.0)
Eau(y,r) Σ Ed (2),
(111)
where
dv1.Y.R (y,r) and Ea.lu,r) = B.y.R.Z) (Z) Y =y, R= Eao(y,r)= dua,y @ VA.R
67

---

Equating both (110) and (111), we have the following equalities in (Va,o)
Ed,o(,,))= dua,y & Va.
dvA.Y,
(y,r) = 1+ Σ
(=())Be,(r)) = 1+b(y,r) for v(,,r)= Σ Ca())Ba,(rr)
k2k.
A2k.
and for 221
Ed,ely.r) ('(Pao)
Eao(v.
E (a(v)Bue(r) Ec(o))a..1())
k2k.
kEIe
where Ie : (k k. = mod 2}. In the last equality, we used the fact that (r,)(r) = 0 for # l mod Our goal is to bound
dua.o (v. (v)e(v)))))) = Erco ( Ed, dva.o
EvalEa,e r) Ep,
Denoting K(y, r) = Sanlv, (., r)2 we are interested in calculating Ep,,o [N(y,))] r)]:
B [K(,,r)] = EEy. [K(v,r) + (vv.r' r) - (),r)))
= =EP.
(112)
We now have the following claim. Claim 1. We have that constant sufficiently large (only in terms of k.).
EE (ay,, r))((, < Eea (K(,,))))
The proof is deferred; for now we use the claim and proceed with the following simplification. It straightforward to see that, combining Eq. (112) with Claim 1, for sufficiently large (that only depends on k.), we have
3 2 Eoso [K(y, ((lyr))an(l.r)) S (K 2 Eee (K(y,))
(113)
Thus, it suffices to obtain rates K(y.r) (oo,),, r) Ea.(v. ( Ea,e r)2 by defini- tion. We finally have the following claim which we will show separately to finish the proof of the lemma.
Claim 2. For all l S.S. kn, we have
Ega (Ea,ly r) x (k- (k.-Kkk-0 12/2 for l k. mod 2 and Ep,, (y, (k. (k.-KK-4 -211//2 for l # k. mod 2.
Observe that Claim 2 along with Eq. (113) establishes the desired rates on Egg, (Cy, r)] Fa r) = [|Sa,ell concluding the proof of the lemma.
L
We now return to the deferred proofs. In order to show Claim 1, the following bounds on the moments of (3y, r) will be useful. The idea is to then directly apply Lemma 24 to conclude that Egg, r), r)]l is vanishing compared to Ep (Ky, [K((,,) r)], which is sufficient to establish Claim
Claim 3. Let ((y Eazk. Su(v)Bk,orr) then there exists universal constant C such that
for d 2 Cp², we have
[ S C ( P
Proof. For the ease of notation we shall denote 11-11p == I1-1le and I =
0 mod 2}. Recall from Proposition 2 that (x) ) is a polynomial of degree with only even degree terms when & is even and zero otherwise. Using this have:
|| = Ergol E 1D
1Sx11e11Bk.011
[|HexllpplBB.oll (Jensen's 's inequality)
RET
KET.
< E(
(p
1) 1/ 1
(Hypercontraatiivity Lemmas 21 and 22)
KEI
1)be
(using Lemma 3)
db/4
KET
68

---

hiding& a universal constant. We now note that the summation forms geometric sequence with ratio (p - 1) /vd Therefore, when d 2 Cp² for sufficiently large constant C, we have that
minkez
1 C d2/4
C
d2/4
Using the above claim, we are now ready to prove Claim 1.
Proof of Claim I. Again let I-lpp denote ||. [1-1)=(0000) We first evaluate
dva
1/2 (v, ())
|||||| = Eoa [K(y, r = Boa.
duao
dya
1/2
I Eea.0
(urr)Qe(u,r)) rv)
(Jensen's 's inequality)
dvao
dvd
dVa,0 S d'
2 d:
(2((a,))
where we used the fact that ||Qe|loo S /md.i = Vdd and that doa has (Pa,0)) norm bounded by
dea,0
universal constant by definition of Gaussian SIMs p. Therefore, we have 2. log ||K]|a [
S log(d).
Thus for d greater than sufficiently large universal constant, we will indeed have 2 Cp for all p S 2. [og[[[<[la>/|]]]]])> Using Claim 3, for greater than sufficiently large universal constant k,
p dkc./4
| SC
Invoking Lemma 24 along with Claim 3, we obtain that
[|]]]
Be,, [KCy, (), X
(2e)ar log" (d)
dk..7
Note that whenever k, 2 1, for d greater than some sufficiently large constant (completely determined in terms of k,), we have
Eaco [C(y, (y r)] $ ||A]|// = BRa,I/C(u ///
as desired. The last equality follows from the fact that K(y,r) 2 a.s. under Pa.0-
Finally, we prove Claim
Proof of Claim 2. Let us expand r)) under Va,
Ea Σ Br,e +2
Σ
(u)Ce,
kET,
(b2>k))EZ
Epy [a)o)))(;;))]]==
Σ (T RET
Σ
BiGr, CH) (v)) (r)),, (114)
(k2>R1)EZ,
We now use the bound from Lemma and find the rates for each term in the above. Case (a) l < k, with f= k, mod 2 The first term
Σ ElBa,e(r) X2 d (k. 0)/2 KEII
Σ
X2 d (k-1//2 = X2, d (k. (k/2
CKEI
where the last step we noticed that the latter term forms a geometric series with decaying ratio whose leading term is of smaller order than the former term. We now show that the sum arising from
69

---

the cross terms from (114) is of smaller order in the absolute value.
Σ (o) v
Σ
[E (v) (t)] [B|C, e (r) Ck2 (r))
(kg2k))EZ
Σ
Ak 1 . Blecy,e(r)) R (Cka, (r)
(kg>k))EZz
Σ
d (M1t22 1) 2 E d (-(-)++)1)
(k2
S d (1)
Substituting this bound in (114), we conclude that for any < k. with E k. mod 2, we have
Epg.o [a,e(y,)) x d (k. d 10/2
Case (b) < k, with of k. mod? 2: We now do similar simplifications.
Σ (r) min X a2(k-1)/2 2 d ok(kk+1-))/2
kokk
KEI,
kETe
Bounding the contribution of the cross terms
Σ
L0[s,, (B) (V)
(r)]
Σ
Blck, (r) 10 cc (r)
(laDk))EZ,
(kazk))E
Σ d (1
()) S Σ d (1)
(ba>k))EIe
kIEI,
S d (1)
Putting the bounds in (1 (114), for any l < k, such that l $ k. mod 2, we have
Epg, (ae r) S d -1
We next prove Lemma which we use to characterize the complexity when one is only allowed to use the directional component
Proof of Lemma 2:
The proof is very similar and, in fact, simpler than that of Lemma 1. Our
goal is to provide rates for the L norm ε,,e. However, as r = 1 always as we only observe (v, z). both completely decoupled null and "partially" decoupled null (where (Y, R) is decoupled from Z) are identical. Therefore, the change-of -e-es-ree argument required to used in the proof of Lemma no longer needed. The proof then follows from the calculations similar to the one done in the proof of Claim 2.
For clarity, will continue to denote the original problem (y, æz) with vas and the new spherical single index model where one only observes (y, z) by Ud.
Again, we have {va)a with vR Xa and p(Y X) p(Y Z R) va(Y Z, R). Let Pa,o = By @ vn & vz be the completely decoupled null. We will also let feald be the sequence of problem associated with {uu}a where only observe (v. 2). We have
dua (v, -
1.2 (8a.0)
Σ
(r where (x(v) = E( He 2) Y = v]
dvao
N2ck.
k Σ (1) Σ (l.e
1? (Ds
(z)) (2) = Σ =o (z) Σ (L))))
k2k.
O
R2k,
where in the second line, we used the harmonic decomposition of Hermite from Proposition 2. We marginalize the radius to explicitly write the likelihood ratio of only (u, part under da and va is identical to that of uy and Va.0 @ Td.1-
dea dua,o
(y,
1.2 (.2.))))
Qe (d)
(2) Σ
E(Br.(())(A(())))
k2k.
70

---

We can also expand the log likelihood ratio of (y, 2) directly in the Gegenbauer basis
dua (y, 2) (V6.)
Σ Ea.c (z), where Ea.e(y) = E)r 10) (0 (2) | = y/.
dea,o
Equating both, we have for any 221
Ea.e(y)
('(a)))
Σ
(=())[[3k,e(()) where {k 2 k. k= mod 2}. kEIe
Σ
k2k,
Squaring both sides
Ed,e(v)² = Σ (T
+2 (kazki)EEe
Ski (U)Ck, (lr
KZIN
[1a..el (A = Σ
((Bk,e(r)12 +2
Σ
ElSk, (v) (r)
(115)
KETr
(Na>RI)ET,
We now use the rates IE.~xa (r)? from Lemma 3 to carry out the simplification similar the one done in the proof of Claim 2.
Case (a) E < k. with f= k. mod 2:
Σ EB KEZ.
+
Σ <KE,
X d (k- Na. d (k.
where the step followed by observing that is sum of geometric series whose rate is dominated by the first term. We now show the bound on the magnitude of the cross terms
Σ
(B) (v)) (r)) (r)]ls
Σ
Ei (R) (v)ll (rc
(12>k))EE,
Σ
Abal V B(cx, (())
(b2>
s Σ
d (11
x Σ dk
S (kk-k(()1)
Combining these rates with (115), we obtain for any < k, with f = k, mod 2,
Kka, (lb (v) x x (k.
Case (b) < k, such that l # k. mod 2: We do similar calculation in the other case.
B[3x, x min X ((--) S (k..
ksk. REI
Bounding the cross terms
Σ
EisA, (v)
Σ (k22>k)EEI
Dey Acal
E[Cc, e(cks.e(r))
(EI
Σ
Σ d (k1--1)) S (k.
kn EIE
Substituting these bounds in (115), for any e < k, such that & $ k, mod 2, we have
Eesalkaely,r)) r) S (++1)
71

---

H Information-theoreiic sample complexity
H.1
Information theoretic lower-bound
Below we derive an information-theorees lower bound for recovering w. in single-index models under an illustrative assumption. This information-thewe -hherrrtttthhoticccccoo result completes the low-degree polyno- mial and SQ lower bounds for the detection problem. Recall that when [|Ea, llzz Oa(1), the LDP lower bounds scales vd: indeed, detection be achieved with this many samples by taking the test statistics obtained by projecting the likelihood ratio onto samplewise-(C 1) polynomials with t wi (1)()). However, the information-theorre is a detection-recovery gap in this model). This is well understood in the Gaussian case (e.g., see [66, 67, 29]) and we provide short proof for spherical SIMs below for completeness.
lower bound for recovery scales (2(d) (that is, there
We will consider the following illustrative regularity assumptions on the link function.
Assumption 6. We assume that for all 8, E R20, we have
(L(ua(-Ir; t) [va(-Ir, s)) S (tt
where L > O is constant, and K E ()rr).
Remark H.1. the case of Gaussian noise i. y = f((w, x)) + oZ where Z NN(0, we have KL (P [PPw') 2 ([(f([((rr x)) - (www, x))) which satisfies the assumption 6.
We now state our minimax lower bound under this assumption.
Theorem 10. Let Va E La that satisfies Assumption and let Fr be the associated family of SIM distributions indexed by w gd-1, Then, for any estimator ii based on observations from Eva,w. we have:
Ep. 11|00 w/|3] (d 1)
( log(C)
inf sup wES1-1
SmLC2
where C. a constant.
Proof of theorem 10. We define the planted distribution denoted by Inn Pr...: given E Sd-1 sample points (yt, a. ridd IP Pea.w- We construct the set of hypotheses H { w.- as 26-packing of gd-1 (6 is chosen small enough such that the 26-packing is a singleton), and such that Vi & j. ||w, will S C5. Using Fano's lower bound [81, Chapter 15] to the problem of estimating w from the observations (y,, )=){²1 yields
2 / 0z (1 ((Z + 1og(22
inf sup Ep Ep V wES
[|| w
w w/|
(116)
log(
where is unformly distributed over {1..... M). and Z is a random variable distributed according to IP, (Pu..oys where independent of By the convexity the Kullback-Leibler divergence and additivity of the KI. divergence, we have
((Z
Ipn vaww,
KL ((Fra,m, ([Peaa,
(117)
M 5-=
M
i,j=1
Using Assumption 6, we bound the KL divergence between two distributions Pre. w. and Prs.
dP dFrn.w (v. (w:r;
KL kn,wy, Pusnw))
Ex, Bx.rarruuuee
log
dP alPeaany
log dPenaws (y, |2,
S Ez E Eny Perm
dIP (IPPnnno
< L|lw; 2 (K(r)] S IC82
where L is a constant from assumption 6, and we used that for all j + i, l|w, - -w,ll S C5 for some
constant C > O. We then have
1(Z;J) nLC8..
(118)
72

---

We bound the cardinality of M, using a classical volume argument: let define S5(x) = { gd-1: (x, y) 2 52) = (y E S I yll - 26). we then have
Pa(S*-1) 2 Ma (S Vol (ees(()) 2 CC
Vol(S;)
where C' is an universal constant, and we denote that No (84-1) is the covering number and Pa (S the packing number, and we used use (a S Pa (S [80, Prop 4.2. I]. and that the homogenity of the volume on the sphere gú-1, With the choice of H described above, and plugging this into equation (116) and equation (117), we obtain
8² (1
nLC8 + 1og
inf sup Ep, B. w|l2| WE884-1
11-
(119)
2
(d- log(C') + log(c)
We choose 8
< I, and plugging this into the previous inequality equation (119), we obtain the following lower bound for d sufficiently large
(d=1)
d
inf sup Er + weBd
11 w
(120)
8nIC
H.2 Information theoretic upper-bound
We complement our information-theoree lower bound with sample complexity upper bound. We exhibit an estimator (which is not computable polynomial time) that achieves strong recovery with (dd) samples for general spherically symmetric measure under a mild assumption on the sequence {ua}a>1 that there exists 2 such that I|Ca,ell= = Pa (1) (cf. Appendix A). The proof is directly adapted from [29, Theorem 6. We focus proving weak recovery of the ground truth since can boost it to obtain strong recovery: there exists a (non-polynomial time) algorithm such that for 0, outputs i with (w, w. 2 1 - with probability o(1) and sample complexity
m Od/Es)
Proposition 6. Under the assumption that there exists f 2 1 such that [lEa,ellz Oa(1), there exists an estimator (non polynomially computable) that returns io E gd-1 that satisfies ( w.)l 2 1/2, with probability at least 1 2e- with information theoretic sample complexity m O (d) hiding constants and e|Ea,ell
Proof. For any 8 > let No be 5-net of 8d-11 and choose N's such that [Wsl I (3)² Consider the following gly, r,) Ea,rly,) r=)) For simplicity, let us denote Ba,e = |E Fix a truncation R 0, and denote (2r) defined as
I (w)
((n, zz), Us. (atr))))(((((x))....))))))
We consider the min-max estimator
Qe w)) /nat
i E arg min max wes
Ln(w)
WEAs
Using Lemma 24, we have
Elg((w, z), v, Elga,e((w. ((,,)) z)) (F,)((,222))) S 82 log(3/ (4/22
Using Bernstein's lemma, have for any w gd-1, with probability least 2e
$ log
3
t
Rt
Ln - (E(n((w)) <
n
n
By union bound and setting = d (log ( 1). we then have with probability at least 1 -e
73

---

k/2
d, log
3
dlog (3)
Rd (log (t)) n
sup (w)) ( x
+
(121)
wEN;
7
bound the effect of truncation
(w) [[g((w,, (w) 2), v,
(w 2), r) 2((w.))
S v Elg((w, M), (1 z), > R)
(Bar >> R).
We then have the following control on the moments of u)
Bl z), y, r> < [[]Q (a, r /1) (2p)
by using Jensen inequality and spherical hyypercontractivityy By taking R (2e) and d 12 /20
2p
(- l Ra/e
()) R) S
S exxp
(-20 2c
Rp
Combining the two inequalities gives
(-L 12/1
[E (w)) Elg((w, 2), (,,,,r)l Ba, exp
(~te
Combining the above inequalities, we then have
B3, (e, w.))
8 Qe(we( w))
max WENS
Vd.EE
Vide
8g (e
Qe wx))
max wEN,
[n(w)
max wENs
[n(w))
(eW w.))
2 max wcN.N
(ww)
Vnd,e
2 max wEN,
L, (w)
E [g(( (w, 2), M,
In (w) - E (w)) + 3 exp (-
l
11
max wEN,
de
B2 log
3 3r
Rt
+ 3d exp
R1/l))
4e
We have the following
Le/2]
Qe((w, w.)) - Qe((w, (w))
1
Σ
Ce. ((w, w.)e-20 - -(w, i0) e-2)
Tid
9=0
Cr
(w. w.)²
(w0, 20) +0d
We then deduce that
(e w-))
(e w))
32,
(w,, w.)e (w,
(w. w0 O(d
max w
Via
Dal weN,
Using
[41, Lemma 25), we then have
32,00,0
Qel(w, w.))
Qe((w, w0))
min ||sú w. S 82,0
+ O(d
max WENs
ndde sE(11)
ndge
74

---

Using this inequality above, and plugging the inequality, we have
8g log Pa.
Rd log (2)
(-Ln' 12/0
min ||si0 w.112 VV (E(11)
+ 8
3 exp
Choosing R = (4e (4g30g(3/))) it yields
P2,00.0
Sg log( 3- 2 (*)
$3.0"
Rd log (g)
+3 exp (- R2/6
l
min ||sio w. 6+1 Vnalt sE{#1}
n
n
4e
Taking 8 ((2,,) concludes the proof.
I Additional technical results
The uniform distribution тu Unif(Sd-1) and the isotropic Gaussian distribution N(0, Ia) satisfy the following hypercontractivity properties:
Lemma 20 (Spherical Hypercontractivity [13]). For any i E N and f E (Ta( which is a degree &
polynomial, for any p 2 we have
I[llLP(T)) S (p-1p) ( [15))
Lemma 21 (Gaussian Hypercontractivity) For any E N and f (2((OO, which is degree L polynomial, for any p 2 we have
lf Eoo. < 1)2/2 1
As corollary of this, we also have the following property for the Xa distribution.
Lemma 22. For any & N and f E (²(xx) which is polynomial of degree E with only even degree terms (i.e. f(r) = 2t12 a -
), any p 221 2 we have
[lllle((x) S (p - 1)
is a polynomial of æ of degree f, where N(O, Ig). To obtain high probability tail bounds from bounds on the moments, we will often use the above hypercontractivity properties with the following standard tail-bounds:
This lemma follows from Lemma 21 by noting that f(r) = f (11==)))
+.. =
Lemma 23 (Lemma 24 in [28]). Let 2 O and X be a mean zero random variable satisfying
E /| < R/2 for p 2 2og((1/))
for some k. Then with probability -, 6, we have |X| B k/2
Similar to [28], we will use the following lemma to bound E EX instead of standard Cauchy- Schwarz, when we have tight bound |X|] and all moments ||Y||, but very loose bound ||X||2.
Lemma 24 (Lemma 23 in [28]). Let X, Y be random variables with ||Y||p S B Then
B|Xy] < ||||| (20) max (1, [1 log
|X
k/2
Lemma 25 (Lemma I.5 in [29]). Let Y En. Ze where Z, E Bex9 are mean zero independent matrices. Define
oYY max
|E 1111/2 | 11/
0, = a. (Y)=
sup
[[((v, Y w) 2/1/22
PE Lue3u-1
R max
Z 1 11/2
n
75

---

Then
R2 11/20112 + v2R,
and 1 2 0, denoting [c
|2 2 R), we have with probability at least 8 - de
Y TE-RRYy Jloop I 2x + a.t g + Rt.
Lemma 26. Let (Zi) be a sequence of independent random variables with polynomial tails, i.e. there exists B, such that [[|Z,/1]//p & Bp Define R maxxelm] Ze Then for any p S log ni/k we have El[ B 2 (n)) and any ô 2 0, with probability at least 8,
R S log" (ogg/((n/5)
Lemma 27 (Lemma 1.3 from [29]). Let ...... Xn be independent mean zero random variables such that for all p 2 2, we have ||Xillp I Bp for some and let o² Di [[X,]. Let
- X4. Then with pribability at least 1 6,
Sx oolog(1/8) + Blog(1/6)oo(nn/))))
Lemma 28 ((78)). Let Xs be i.dd random matrices of dimensions d2 d2. Assume that each matrix bounded by
Ak. Xx E[ S I.
Consider v(Z)
max EI(X, B[xx))(xR - E[X II Bl(x
x[ R[xx)) []]),, then with probability at least 1 5,
L
d1 + +d2
di + d2
x E
$
log
+
4u lolog
3
8
op
76


Reviews:
[{"review_id": "eftVckih3M", "reviewer": "Reviewer_33AS", "summary": "The paper analyzes the sample complexity of learning single-index models under spherically symmetric input distributions. Unlike most existing results that characterize the sample-complexity (when restricted to a class of algorithms) for Gaussian inputs through Hermite decomposition of targets/likelihood ratio, this work provides such a characterization through a decomposition along radial components and spherical harmonics. This, in turn, subsumes the existing results on Gaussian inputs.\n\nThe main contributions are twofold:\n * Lower bounds for SQ and low-degree polynomial methods.\n* Spectral and online-SGD based algorithms achieving weak-recovery of the target direction with optimal sample-complexity and runtime, respectively. \n\nBoth the above contributions are based on the generalization of existing techniques, such as the analysis of the partial trace estimator and online-SGD from Gaussian to general spherical distributions. By providing run-time lower bounds for SQ and sample-complexity lower bounds through the low-degree polynomial framework, the paper further highlights a trade-off between achieving optimal sample-complexity vs optimal runtime.", "questions": "* Assumption 1 doesn't appear quite transparent. Inclusion of interpretation and examples behind the assumption would strengthen the paper.\n* Definition 1 says $\\mathcal{Y}$ can be an arbitrary-measurable space. Aren't the targets restricted to be real-valued (as specified in equation 1 in the introduction)?\n* Concerning section 4 and observation 2, how does label smoothing exploit the radial components?\n* Why is the SQ-based run-time lower bound expected to hold for a general class of algorithms? The paper would benefit from a brief discussion of the evidence behind this heuristic, as well as a more transparent presentation of it as a conjecture.", "limitations": "The work is primarily theoretical and does not pose direct societal risks. The paper would benefit from a more detailed discussion of the limitations I've listed in the review, such as the conjectural status of the run-time lower-bound prediction from the SQ framework.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strengths:\n\n* The paper is presented and organized well. The definitions are clean, and the setting is quite general. For instance, the non-zero Gegenbauer coefficients are not restricted to be $\\Theta(1)$. Appendix A provides a nice interpretable summary of the central ideas behind the lower bounds and estimators.\n* The ideas behind the extension of the results for Gaussian inputs to general spherically symmetric distributions, in particular the decomposition along irreducible representations of the symmetry group, could allow extension to other interesting distributions with symmetries such as permutationally-invariant data.\n* Certain conclusions, such as the limitations of algorithms not exploiting the radial component, and the sample-complexity/runtime tradeoffs, are insightful and could benefit future related work.\n\n# Weaknesses\n\n* Limited novelty and scope: The analysis is largely based on extensions of existing techniques from Gaussian to spherically symmetric distributions. The paper would benefit from a discussion of the novel insights gained by this extension and the novel ideas/challenges in the proofs. For instance, the proofs for Theorems 1 and the spectral/tensor-based algorithms largely follow Damian et al. 2024, while the analysis of the SGD algorithm is largely based on Zweig et al. 2023.\n\n* Inadequate discussion of literature: The paper does not cite or discuss a number of relevant works:\n\n  Learning multi-index models in polynomial time through an SGD-based algorithm:\n\n  Chen, Sitan, and Raghu Meka. \"Learning polynomials in few relevant dimensions.\" Conference on Learning Theory. PMLR, 2020.\n\n  Another missing line of work shows how the sample complexity of online-SGD can be improved to match the SQ sample-complexity through the re-use of data:\n\n  Dandi, Y., Troiani, E., Arnaboldi, L., Pesce, L., Zdeborova, L., &; Krzakala, F. 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.\n\n  Lee, J. D., Oko, K., Suzuki, T., &amp; Wu, D. (2024). Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit. Advances in Neural Information Processing Systems, 37, 58716-58756.\n\n  Arnaboldi, L., Dandi, Y., Krzakala, F., Pesce, L., &amp; Stephan, L. (2024). Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405.15459.", "was_revised": true, "final_justification": "I recommend acceptance since the work contributes important theoretical insights and directions to the theory of learning in structured data. I expect the reviewers to incorporate the clarifications mentioned in their response in the revised version.", "rebuttal": "We thank the reviewer for their time in reviewing our work and overall positive feedback! Below we address their concerns in the weaknesses.\n \n---\n\nWe kindly disagree that this tensor-based method follows largely from Damian et al. (2024). \nThis algorithm is designed for the cases when the sample optimal frequency $l_{m,\\star}\\geq 3$, which is a novel algorithm inspired from tensor PCA literature and does not follow from partial trace.  In particular, the partial trace algorithm always projects the Hermite tensor onto harmonic frequencies $\\ell=1$ and $\\ell=2$, depending on GE is odd or even. Thus, this algorithmic idea is not sufficient to achieve optimal sample complexity when $l_{m,\\star}\\geq 3$. (Note that this never happens in the Gaussian case cf. lines 105-108, but happens for general single-index models, e.g., with data uniform over the sphere.)  **Our estimator is different: it is based on tensor unfolding and not partial trace.** The dependency structure is much more intricate and requires a different and more involved analysis than for the partial trace estimator. Furthermore, our tensor unfolding estimator is non-standard and requires removing the diagonal. We further introduce **a harmonic tensor, which, to our knowledge, is novel in the machine learning literature and might be of independent interest.**\n\n**Novelty and scope:** We believe there might be some misunderstanding in evaluating our contributions in this work. Below, we list the contributions that we believe are novel and of interest to the community: \n\n* The **main conceptual novelty of this work is the introduction of the harmonic decomposition to study single-index models**. To the best of our knowledge, this is the first work that studies Gaussian single-index models through this lens: the generative exponent and the earlier information exponent are defined with respect to Hermite polynomials. Many analyses, including many works cited by the reviewers and less recent works on GE=2 (phase retrieval), are exploiting this Hermite basis in their proofs. \nWe argue in this paper that the harmonic decomposition is the natural basis to study single index-models as:\n    * **It explicitly exploits the spherical symmetry of the problem.** We believe that this is an important and general observation, which will have important consequences when studying other similar `equivariant’ problems. (See point below on LDP and SQ lower bounds.)\n    * **It gives a more transparent derivation of optimal algorithms in the Gaussian setting**, by making explicit optimal statistics in terms of direction and norm of the Gaussian vector. (See point below on landscape smoothing and partial trace.)\n\n* As a consequence of the harmonic decomposition, we can study **general spherically symmetric input distributions**. To our knowledge, a fine-grained analysis of learning SIMs under general spherical distribution is novel. While this might appear incremental compared to the Gaussian distribution, we argue in the paper that this is not the case. It requires **novel analyses to study (harmonic tensor, Gegenbauer algebra) and it uncovers new and interesting phenomena that don’t appear with Gaussian data:** (1) novel statistical-computational trade-offs, (2) the importance of the norm of the input, (3) exploiting different degree spherical harmonics.  \n\n* **Novel statistical-computational trade-offs in SIMs:** we provide evidence that for non-Gaussian input distributions, new statistical-computational trade-offs appear when optimal harmonic-degree for SQ and LDP are different. In this case, one can either be sample-optimal or runtime-optimal but not both. We further emphasize that this is a different phenomenon than typical smooth trade-offs discussed in the literature, e.g., in tensor PCA, where one can smoothly trade-off the polynomial degree of the estimator with sample complexity (as $m = d^{k} / D^{k/2 - 1}$). \n* **Importance of the norm:** In our opinion, this is the most surprising and novel observation. We provide evidence that In order to learn Gaussian SIM with optimal runtime, **one needs to exploit the norm, despite the norm not carrying any information on  $w_*$ and concentrating on $1$ as $d \\to \\infty$**. Thus, **normalizing the input data—which is a typical preprocessing step in statistics and machine learning—leads to suboptimal performance when learning Gaussian SIMs**. We emphasize that our harmonic analysis framework is necessary to uncover this phenomenon. As a side note, to prove this result required a novel hermite-to-Gegenbauer expansion (Appendix B.2).\n\n* **SQ and LDP lower bounds:** we kindly disagree with the reviewer’s assessment that Theorem 1 largely follows from Damian et al. 2024. While SQ and LDP lower bounds have now become routine computations and we do not deviate from the standard approach, our proofs are based on exploiting Gegenbauer properties and hypercontractivity. Importantly, we present a **novel decoupling of these lower bounds across harmonic subspaces**. To the best of our knowledge, this is a novel phenomenon and we heavily rely on this decomposition to design our optimal algorithms for learning SIMs. The fundamental structure behind this decoupling is that harmonic subspaces are **irreducible representations of the orthogonal group** (e.g., Gegenbauer polynomials can be seen as matrix coefficients of this representation, and the proof reduces to Schur orthogonality relations). Thus, our proof of LDP and SQ lower bounds directly generalizes to abstract groups because of this structure, which is not the case with a proof based on Hermite polynomials.\n\n* **Landscape smoothing and partial trace:** we show that even for Gaussian inputs, our framework offers novel and more transparent justifications for the success of existing algorithms. \n    * The partial trace estimator simply corresponds to projecting on the optimal degree-$1$ or $2$ harmonic subspaces, and is simply a spectral algorithm with the right transformation $T(y,r)$. While this does not modify the algorithm, we argue that **the harmonic decomposition is a particularly transparent derivation of this algorithm that does not require any tensors, Gaussian identities, or knowledge about the partial trace method**.\n    * **Landscape smoothing reweights the harmonic decomposition of the loss.** To the best of our knowledge, this is a novel interpretation of this algorithm that originates in the tensor PCA literature. \n    * Online SGD on hermite neurons **does not seem to be able to exploit the norm of the Gaussian input. It has optimal runtime among algorithms that do not exploit the norm.**\n\n**Despite this model being well-studied, we believe that our paper offers a novel and interesting perspective, rooted in harmonic analysis.** We believe that several aspects of our work—**symmetry-centric decomposition, decoupling into subproblems across irreducible subspaces, and harmonic tensor—will be of independent interest and apply beyond learning SIMs.**\n\n**Missing references:**  We thank the reviewer for providing these references, which we have included in the paper and it will be updated during the final version. A remark about reusing the batch line of work is that, while reusing batches might improve the sample complexity in online-SGD, it is conjectured that it can only improve from the information exponent (CSQ) to the generative exponent (SQ), which is what these three papers show. In our paper, we only consider the SQ: in this case, it is unclear whether multi-pass SGD can improve the sample complexity of our online SGD algorithm. We believe that this is an exciting research direction.\n\n\n**Questions:**\n\n* Assumption 1:  This assumption was confusing and unnecessary for the proof of the lower bound. We have replaced it with a mild (necessary) assumption that the SIM is learnable in polynomial time. Kindly see the response to Reviewer KRnG for the precise assumption.\n* Throughout the paper, we allow the label to live in a general measurable space (the label only appears in equations through $T(y)$, with general transformation $T:\\mathcal{Y} \\to \\mathbb{R}$). We will modify the line below Equation 1, and not restrict $y$ to be a real number, even in this first equation.\n* Label Smoothing will change the decomposition of the link function into Spherical Harmonics. See the discussion in Appendix A.3, especially lines 844-848. For the Gaussian case, this operator essentially reweighs the frequency in the harmonic decomposition of the link function—smooths the higher-degree Gegenbauer and amplifies the contribution from lower-degree Gegenbauer.  Therefore, smoothing the population loss $L(w)=\\mathbb{E}[T(y)He_k(<w,x>)]=\\mathbb{E}[T(y) \\sum_{\\ell=0}^{k} \\beta_{k,\\ell}(r) Q_{\\ell}(< w,z>)) ]$ turns out to be “roughly equivalent” to $\\tilde{L}(w)=\\mathbb{E}[T(Y)\\beta_{k,2}(r)Q_2(<w,z>)]$ or  $\\tilde{L}(w)=\\mathbb{E}[T(y)\\beta_{k,1}(r)Q_1(< w,z>)]$ depending on even or odd $k$. This is how it is able to exploit the norm. However, this turns out to be a highly indirect way of doing so -–the fact that the smoothing has a filtering effect and that it is able to exploit the norm nearly optimally is due to the Gaussianity and the relationship between Hermite and Gegenbauer basis. However, such a phenomenon does not hold more generally. Our online SGD algorithm, thus, directly try to fit the transformation $T(y,r)$ which exploits the norm more directly.\n* Indeed, this is an important point. We only briefly touch on it at the end of Section 2. This heuristic is based on the belief that $1/\\tau^2$ runtime is necessary to compute one query to tolerance $\\tau$. Similar to many other work in ML (which we will cite), we use these lower bounds as an indication of the best achievable runtime. We will expand and clarify this heuristic in the main text."}, {"review_id": "07TWhGRa75", "reviewer": "Reviewer_VyBx", "summary": "The author considers the setting of learning single index models with Gaussian marginals.\nIn particular, the noise model they consider here is kind of between realizable and agnostic, \nin the sense that the distribution of y can only depends on the important direction but need not to labeled by a single target function (equation 1).\nThe authors gave a very novel and insightful observation that the hardness can be more naturally analyzed by spherical harmonics instead of Hermite polynomials (which is the typical choice of basis in previous literature).\nThis can be intuitively explained by that the spherical harmonics are the irreducible representations for the rotation symmetry.\n\nBased on this, the authors proposed the spherical single index model framework (which generalizes the regular single index model).\nWhile the authors did not provide any useful problem/application that fits into this framework but not the previous regular single index model framework.\nThey did show that by analyzing the SQ and LDP complexity of the spherical single index model, not only did they recover the previous results of generative exponents for single index models.\nBut also give some explanation about why online SGP types of algorithm failed to give the right sample complexity in SIM.", "questions": "1. Can the authors give some further high-level comments on why LDP and SQ gives different information-computation trade-off?\nEspecially, if there is any intuition about why they predicts the right sample/time complexity for tensor unfolding and SGD respectively.\n\n2. I'm a bit confused about Lemma 1, from my understanding Lemma 1 only assume that p has generative exponent k^*.\nCombining this with the decomposition of Hermite polynomial into Gegenbauer polynomials.\nShouldn't this only implies that there exists one spherical harmonic (in this decomposition) that has large coefficients? \nInstead, Lemma states that coefficients for all spherical harmonic (in this decomposition) are this stated value (up to constant factor).", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength:\nThe paper offers a very novel and insightful perspective on the single index model.\n\nWeakness:\nFrom what I know, there is also a line of work on agnostic single-index modes, which I think is relevant here and should be cited.\nFor example, here some that I found (I'm sure I'm missing some):\n\n1. I. Diakonikolas, D. M. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnostically learning\nhalfspaces and ReLUs under Gaussian marginals.\n2. S. Goel, A. Gollakota, and A. R. Klivans. Statistical-query lower bounds via functional gradients. \n3. I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial regression for\nagnostic learning under Gaussian marginals in the SQ model. \n4. I. Diakonikolas, D. M. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning\nhalfspaces and ReLU regression under Gaussian marginals.\n5. P. Manurangsi and D. Reichman. The computational complexity of training ReLU(s). \n6. I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren. Hardness of learning a single neuron with\nadversarial label noise.\n7. I. Diakonikolas, S. Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi. Approximation schemes\nfor ReLU regression.\n8. I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning a single neuron with adversarial label\nnoise via gradient descent. \n9. P. Awasthi, A. Tang, and A. Vijayaraghavan. Agnostic learning of general ReLU activation using\ngradient descent.\n10. P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Robustly learning a single neuron via\nsharpness.\n11. A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models\nusing omnipredictors.\n12. N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly learning single-index models via\nalignment sharpness.\n13. A. Guo and A. Vijayaraghavan. Agnostic learning of arbitrary ReLU activation under Gaussian\nmarginals.\n14. N. Zarifis, P. Wang, I. Diakonikolas, and J. Diakonikolas. Robustly Learning Monotone Generalized Linear Models\nvia Data Augmentation", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interest in our work and for the interesting questions.Below we address their concerns in the weaknesses.\n\n\n---\n**Missing references:**\n\n (a) **We agree that our original submission omitted several important references**. We are grateful to the reviewers for pointing out these works. We have now incorporated all the suggested citations, which better situate our paper within the existing literature and significantly strengthen the presentation. Specifically, we **added several references in both the introduction and the technical sections**. Additionally, we have written a \"Related Work\" section now. All this updates will be available in the final version.\n\n(b) We thank the reviewer for suggesting adding the “robust-learning” line of work to our related work section.\n\n\n---\n\n**Answers to the questions are in order.**\n\n**LDP and SQ**: \n*  **LDP:** LDP is used to derive a **lower bound on the sample-size** required to have a polynomial-time algorithm (that is, derive the `computational threshold’ in the sample size). SQ is used to derive a **lower bound on the query complexity**, which we heuristically equate to a **lower bound on the runtime of the algorithm** (see answer to Reviewer 33AS). \n\n*  **SQ:** We can prove an upper bound on the tolerance in SQ—which is used as evidence for a *computational threshold* in the sample size—similarly as in [Damian et al, 2024]. Both predicts $d^{\\ell/2}/\\lVert \\xi_{d,\\ell}\\rVert_2^2$ lower bound on the sample size when restricted to a given harmonic subspace. \n\n* LDP is not designed to give (fine-grained) runtime lower bounds, so we use SQ for this purpose, and we obtain $d^\\ell/\\lVert \\xi_{d,\\ell} \\rVert_2^2$. **LDP and SQ are used to capture two different things and are not in contradiction.**\n\n* When looking for sample-optimal or runtime-optimal algorithms, we consider the subspace that minimizes the sample or runtime lower bound. This might be **two different subspaces**, which we interpret as providing evidence that no single algorithm can be both sample and runtime optimal.\n\n* **Algorithms as LDP and SQ:** Tensor unfolding is a **low-degree polynomial of the data and spectral algorithms fall in the LDP framework**. Thus, it is unsurprising that LDP predicts the correct sample complexity for tensor unfolding. (But there is a priori no reason to expect no detection-recovery gaps).\n**Online SGD is an SQ algorithm**, and it was noticed in several previous papers that **SQ predicts the correct runtime for these algorithms**. We do not know of a priori reason why tensor unfolding should have runtime nearly matching the SQ complexity lower bound.\n\n**Lemma 1:**\nIn the Hermite-to-Gegenbauer expansion, $\\xi_{d,\\ell}$, for $\\ell \\leq k_*$ will **only depend on the $k_*$-th  hermite coefficient to leading order**. This is due to the fact that the projection of an Hermite-k on Gegenbauer of degree $\\ell < k$ has $L^2$-norm vanishing as $d^{-(k-\\ell)/2}$. Thus a likelihood ratio with GE = $k_*$ will have vanishing projections on spherical harmonics of degree $\\ell < k_*$, and Lemma 1 bounds how fast they are vanishing as polynomials in $d$. **Despite the projection vanishing, for Gaussians, it is always optimal to use degree-$1$ or $2$ spherical harmonics.**\n\n[Damian et al, 2024] Computational-statistical gaps in gaussian single-index models A Damian, L Pillaud-Vivien, JD Lee, J Bruna"}, {"review_id": "FJ9N6CaAqU", "reviewer": "Reviewer_KRnG", "summary": "The authors study learning in a **single index model** of the form $x \\mapsto g(w^* \\cdot x)$, where the input distribution over $x$ is **rotation-invariant**. Their analysis leverages the **spherical harmonic decomposition** of the signal to:\n\n- **Characterize the problem difficulty**, via the spectral structure of the signal; (decomposition into the spherical harmonics)\n- **Define the optimal transformation** of the learning task to recover the planted direction $w^*$;\n- **Establish fundamental limits** through minimax **statistical complexity bounds**:\n  - **SQ lower bound** ,\n  - **LDP lower bound**\n- **Analyze the complexity** of different algorithms:\n  -  Spectral algorithm and Tensor Unfolding\n  - **Stochastic Gradient Descent (SGD)** ;\n- **Recover known results in the Gaussian case** when the *generative exponent* rules the complexity of the algorithms derived in the article.", "questions": "- I find the following sentence unclear: \"The SGD algorithm of [2] is dominated by the high-frequency harmonics $V_{d,k}$, while smoothing [10] reweights the loss landscape toward low-frequency harmonics $V_{d,1}$ or $V_{d,2}$.\" It is not obvious to me how to interpret this, since the runtime complexity of SGD depends explicitly on $k^*$, whereas the spaces $V_{d,1}$ and $V_{d,2}$ do not seem to play a direct role in the complexity. Could the authors clarify what is meant here?\n\n- Could you provide some insight on Assumption 1? As stated, it appears to imply that a single harmonic component dominates the others in terms of statistical or algorithmic complexity. Is this the intended meaning?\n\n- In line 200, SGD is defined with respect to some parameter $l$, and a transformation $T_{l}$ that seems to extract the coefficient of the response in the $V_{d,l}$ harmonic. Is this interpretation correct? Also, which value of $l$ is chosen in Corollary 2? Presumably, it should be related to $k^*$; but this is not clearly stated. Could the authors make this connection more explicit?", "limitations": "No limit, I would be nice to have clearer results.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- **Conceptual clarity**: The use of spherical harmonics provides a principled and elegant framework to analyze single index models under rotational symmetry.\n- **Theoretical depth**: The paper offers nontrivial lower bounds (SQ and LDP) that clarify the statistical hardness of the problem.\n- **Unified perspective**: The approach recovers known results in Gaussian settings and discuss the fundamental limits of SGD.\n- **Technically solid**: Proofs appear to be rigorous and well-structured, with clear connections between harmonic properties and learning performance.\n\n### Weaknesses\n\n- **Overloaded presentation**: While the authors make a commendable effort to define concepts precisely and clearly, the paper feels overly dense, with too many results introduced in rapid succession. This makes it hard to follow the central narrative, and the reader may struggle to grasp the key insights. A better organization of the material would help, although it's not immediately obvious how to restructure it. As it stands, the paper sometimes gives the impression of going in too many directions at once.\n\n- **Unclear resolution of the central question**: The paper raises the important question of why SGD-based algorithms are suboptimal, exhibiting a runtime of $d^k$ instead of the optimal $d^{k/2 + 1}$. However, the answer to this question remains hard to extract. In particular, it is unclear where it is precisely stated (or proved) that a regularity assumption on the distribution over $\\nu_{d, R}$ is necessary to halve the complexity exponent. Also, is there a clear intuition or conceptual reason behind this improvement? Making this point more explicit would strengthen the paper.", "was_revised": true, "final_justification": "The authors provides a clear article on single index models providing valuable insights. I thank the authors for their additional comments and the answer they give to the other reviewers. I keep my score.", "rebuttal": "We thank the reviewer for their time and positive feedback! We answer your question in order:\n\n* The landscape smoothing leads to different harmonic decompositions, which can be seen in Observation 3, page 24, and in line 843. So, the landscape smoothing reweights all the signals in the first two frequencies, and adds a normalizing factor depending on the harmonic decomposition of the loss. The spaces of degree 2 spherical harmonics are the effective harmonic decompositions, and our analysis relies on these harmonic decompositions.\n* **Asssumption 1**: We thank the reviewer for this remark. This assumption was indeed confusing and unnecessary for the proof of the lower bound. We have replaced it with a mild (necessary) assumption that the SIM is learnable in polynomial time. Formally\n\n**Assumption 1 (updated):** There exists $p\\in \\mathbb{N}$, such that the sequence $\\{\\nu_d \\}$ satisifes $\\mathsf{M}_\\star(\\nu_d)=O_d(d^{p/2})$.\n\n* This interpretation is correct. The frequency parameter ensures the transformation has a non-zero $\\ell$-frequency. In Corollary 2, we applied Theorem 2 with any $\\ell$ that has the same parity as $k_*$. That can be seen as a consequence of Theorem 1 and Lemma 2, which actually computes the asymptotics of $\\lVert \\xi_{d,\\ell}\\rVert^{2}$ that appears in the harmonic decomposition."}, {"review_id": "zehjpwpzeP", "reviewer": "Reviewer_vFaG", "summary": "The paper studied the problem of learning single index models under rotation-invariant distributions, where the data vector x satisfies $x=rz, r\\sim\\mu_r$ and $z\\sim\\tau_d$, and $\\tau_d = \\mathrm{Unif}(\\mathbb{S}^{d-1})$. The labels y satisfy $y | r,z \\sim \\nu_d(. | r,w^* z)$ where $w^*$ is the unit-norm hidden direction. It is assumed $\\nu_d$ is known. The authors then used spherical harmonics decomposition of the link function rather than hermite polynomials to study the computational complexity. The main contributions of this paper are three-fold:\n1. The authors showed that under the spherical model, using harmonic decomposition, there is a gap between the SQ lower bounds and LDP lower bounds, indicating a 'sample-runtime' trade-off phenomenon. In detail, SQ lower bounds indicate a runtime complexity lower bound that is higher than the sample complexity lower bound implied by LDPs. The authors proposed a characterization of the sample and runtime complexity using the degree of the Gegenbauer polynomial that has the maximum signal from the harmonic decomposition.\n2. The authors provided sample optimal and runtime optimal algorithm respectively, using tensor unfolding and online SGD. The authors conjectured that there is no algorithm that can achieve optimal sample complexity and runtime complexity at the same time.\n3. The authors applied the framework to Gaussian SIMs, i.e., they studied learning SIMs with link function $y|r,z=\\rho(w*\\cdot z)$ where $\\rho$ has generative exponent $k*$ and $r\\sim\\chi_d$ and $z\\sim \\mathrm{Unif}(\\mathbb{S}^{d-1})$. They showed that the optimal harmonic degree is either 1 or 2 (depending on the parity of k^*) and recovers the optimal sample and runtime complexity of learning Gaussian SIMs in prior literature.", "questions": "1. In line 113-119, the authors claimed that the SGD is suboptimal, possibly due to the fact that it does not exploit the radial component $r=||x||$ and claimed that algorithms ignoring r must have runtime $d^{k*}$. Can you provide a pointer to where this claim is justified? I skimmed through section E and did not spot the supporting lemma.\n2. Furthermore, can the authors elaborate on how to exploit the radial exponent?", "limitations": "no negative limitations", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. I think the observations and findings of this paper are very interesting. The paper goes beyond Gaussian distribution and studied the computational complexity of learning SIMs under more general rotational invariant distributions, and discovered a complexity measure that recovers prior complexity results on learning Gaussian SIMs. It is also very interesting to see that there is a gap between SQ and LDPs under the spherical model, indicating a sample-runtime trade-off.\n2. The technical aspect of this paper is solid and strong.\n3. The paper is mostly clearly and fluently written.\n\nWeakness\n1. I think in the introduction section where the authors compared prior works on learning Gaussian SIMs is somewhat confusing, e.g., line 40-47. [Damian et al Neurips] closes the gap in terms of the information exponent (i*) rather than the generative exponent (k*), and I don't think [Damian et al COLT] simply removes the polylog terms. Further, my understanding is that [D et al Neurips] and [D et al COLT] are essentially very different algorithms that tackle different computational barriers.\n\n2. In the comparison to prior work part, I am afraid the authors missed another intensive thread of research on learning SIMs under general or Gaussian distributions with misspecification/agnostic noise, e.g., [DGKK+20], [DKTZ22], [WZDD23],[GGKS23], [ZWDD24], [WZDD24], [GV25], [ZWDD25] and so on. It would be more well-rounded if this thread of research were mentioned in the comparison to prior works part.\n\n[DGKK+20]: Diakonikolas I, Goel S, Karmalkar S, Klivans R, Soltanolkotabi M. Approximation Schemes for ReLU Regression, in COLT 2020\n[DKTZ22]: Diakonikolas I, Kontonis V, Tzamos C, Zarifis N. Learning a single neuron with adversarial label noise via gradient descent, in COLT 2022\n[WZDD23]: Wang P, Zarifis N, Diakonikolas I, Diakonikolas J. Robustly Learning a Single Neuron via Sharpness, in ICML 2023\n[GGKS23]: Gollakota A, Gopalan P, Klivans A, Stavropoulos K. Agnostically learning single-index models using omnipredictors, in Neurips 2023\n[ZWDD24]: Zarifis N, Wang P, Diakonikolas I, Diakonikolas J. Robustly learning single-index models via alignment sharpness, in ICML  2024.\n[WZDD24]: Wang P, Zarifis N, Diakonikolas I, Diakonikolas J. Sample and computationally efficient robust learning of gaussian single-index models, in Neurips 2024.\n[GV25]: Guo A, Vijayaraghavan A. Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals.\n[ZWDD25]: Zarifis N, Wang P, Diakonikolas I, Diakonikolas J. Robustly Learning Monotone Generalized Linear Models via Data Augmentation.", "was_revised": true, "final_justification": "The authors cleared my confusion and I maintain my evaluation.", "rebuttal": "We thank the reviewers for acknowledging the contribution of the work and positive feedback! Below we provide clarifications to the weaknesses.\n\n---\n\n* **A clarification on Damian et al. landscape smoothing vs generative exponent papers:** We are aware that prior to the [Damian et al, 2024] paper, the literature mostly revolved around information exponent (corresponds to CSQ). As mentioned in Lines 32-37, the primary contribution of [Damian et al, 2024] is to **introduce the generative exponent** as the fundamental barrier for computational sample complexity. However, from an **algorithmic** standpoint, the main contribution of [Damian et al, 2024], according to us, is in **matching the complexity removing log factors**—in particular, in our opinion, although information exponent is a fundamentally different complexity measure, it is straightforward to observe that, the landscaped smoothed SGD [Damian et al. 2023], on applying appropriate label transformations, achieves the guarantees where information exponent can be replaced with generative exponent. **This results in basically the optimal sample complexity up to log factors, and from here on the goal of the partial trace estimator is to remove them.**\n\n* Our goal in the main text is to directly focus on generative exponent complexity measure and how different methods like online SGD/ landscape smoothing/ partial trace (after label transformations) achieves different complexities, and to point out that there is **a gap in our understanding despite having tight results**. We tried to credit the original source and analysis of these algorithmic primitives, although this comes with a caveat that the online SGD and the landscape smoothing were only stated for information exponents and a label transformation is required to bring them down to generative exponent. We briefly touch upon this in footnote 1, with more discussion in Appendix A.3. \n\n* **Missing references:** Apologies for missing out on some important lines of work. **We agree that our original submission omitted several important references**. We are grateful to the reviewers for pointing out these works. We have now incorporated all the suggested citations, which better situate our paper within the existing literature and significantly strengthen the presentation. Specifically, we **added several references in both the introduction and the technical sections**. Additionally, we have written a \"Related Work\" section now. All these updates will be available in the final version.\n\n---\n\nWe now answer the questions.\n* **suboptimality of SGD:** All the prior algorithms are informally revisited in Appendix A.2, including the online SGD without norm. We provide a semi-formal justification of these informal claims in the same appendix. (We might further expand them in the final version.)\n\n* **Exploiting the norm:** One obvious way of exploiting the norm is to run online SGD according to Equation SGD-Alg (lines 199-203). This is one of the powers of harmonic decomposition that we can **create a transformation of radial component and label explicitly, and run online SGD with neuron $Q_{\\ell}(\\langle w,z\\rangle )$**. There might be other “natural” ways of exploiting the norm, which we have not invested thoughts in. The purpose of discussing vanilla SGD is to provide a new explanation as to how this method could fall short in achieving the optimal complexity. \n\n--- \n[Damian et al, 2024] Computational-statistical gaps in gaussian single-index models Alex Damian, Loucas Pillaud-Vivien, Jason D Lee, Joan Bruna\n\n[Damian et al, 2023] Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models, Alex Damian, Eshaan Nichani, Rong Ge, Jason D Lee"}, {"review_id": "OUYwbRj5Pq", "reviewer": "Reviewer_91Gz", "summary": "This paper develops a harmonic-decomposition perspective on high-dimensional single-index models (SIMs).  SIMs have attracted intense attention in recent years, with many complementary papers already charting phase transitions, statistical-computational gaps, and learning dynamics.By expanding the likelihood in spherical harmonics rather than Hermite polynomials, the authors (i) derive tight Statistical-Query and Local-Differential-Privacy lower bounds for every harmonic level in the signal; (ii) propose two estimators—harmonic tensor unfolding (which is sample-optimal) and online projected SGD (which is runtime-optimal)—that match those bounds up to logarithmic factors; and (iii) show that the classical Gaussian SIM results emerge as a special case of their framework. The analysis clarifies why landscape-smoothing and partial-trace spectral methods succeed, highlights when vanilla SGD is provably sub-optimal, and unifies several lines of earlier work.", "questions": "Extension to staircase links: Could the harmonic-decomposition framework be adapted to “staircase’’ regressions, i.e. settings where the link function is piece-wise constant rather than smooth?\n\nMulti-index generalisation: Is there a principled way to lift the analysis from single- to multi-index models that involve several latent directions?\n\nNoise robustness: How sensitive are the proposed lower bounds and algorithms to additive observation noise—especially of the type analysed in arXiv:2502.06443v1—and can the theory be modified to accommodate such perturbations?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strenghts: This is a technically strong and unusually original paper: by viewing single-index models through the lens of harmonic decomposition, it unifies a patchwork of open questions—tight lower bounds, sample-optimal versus runtime-optimal algorithms, and the peculiar success of spectral “partial-trace’’ tricks—within a single, coherent framework. The quality of the work is high: the Statistical-Query and Local-DP lower bounds are rigorously proved, the two complementary algorithms meet those bounds up to log factors, and the analysis cleanly recovers the classical Gaussian results as a special case, thereby subsuming several separate lines of literature\n\nWeaknesses: The exposition suffers from a notable gap in citations. The discussion of the easy/hard transition in SIMs references overlooks earlier rigorous work that first established the information-theoretic limit and computational gap; recent rigorous papers on learning dynamics are omitted as well, and the genealogy of spectral methods is incomplete. These omissions currently temper the otherwise excellent contribution.\n\nWhile the paper offers an original and compelling perspective on single-index models through harmonic decomposition, I believe several important references are missing, which would significantly improve the completeness and scholarly context of the discussion. First and foremost, the paper “Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models” (arXiv:1708.03395) deserves to be cited when discussing the GE=2 case and the statistical-to-computational gap. This work rigorously established the information-theoretic limits and the phase transition at Hermite degree 2—what is now often called the “Hermite-2 threshold”—and provided an early and formal treatment of the Parisi–Franz potential and the associated computational gap. While MM18 proposed an important spectral method to approach this threshold, the existence of the transition itself and the structure of the gap were already clearly laid out in this earlier paper. As a point of reference, this work is cited in [DPVLB24] and in several other recent contributions.\n\nIn addition, two more recent papers—arXiv:2202.00293 and arXiv:2406.02157—provide rigorous and contemporary analyses of SIM learning under Gaussian assumptions, focusing in particular on gradient-based algorithms and the implicit regularization they induce. These works are on par with other cited results (e.g., [AGJ21], [DNGL24]) and would be highly relevant to include in the broader discussion. On the spectral side, the paper also omits a key antecedent to MM18: Yue Lu’s 2017 work (arXiv:1702.06435), which provides early results on spectral thresholds in high-dimensional nonconvex estimation problems, including phase retrieval", "was_revised": true, "final_justification": "This paper makes a strong and original contribution by introducing a harmonic-decomposition framework that unifies lower bounds, optimal algorithms, and spectral methods in single-index models. The rebuttal and discussions confirmed the correctness and novelty of the main results, increasing my confidence in the work. The main unresolved issue is the omission of several key citations, which affects scholarly completeness but not the technical contribution. Overall, the paper is rigorous, impactful, and I recommend acceptance.", "rebuttal": "We thank the reviewer for acknowledging the contribution of the work! **We agree that our original submission omitted several important references**. We are grateful to the reviewers for pointing out these works. We have now incorporated all the suggested citations, which better situate our paper within the existing literature and significantly strengthen the presentation. Specifically, we **added several references in both the introduction and the technical sections**. Additionally, we have written a \"Related Work\" section now. All these updates will be available in the final version.\n\nAnswers to the questions are in order. \n\n---\n\n* **Extension to non-smooth link functions:** We allow for **arbitrary link functions in our spherical SIM definition (Definition 1)**, which includes the situation which includes “staircase” type link functions (as long as Radon Nikodym derivative w.r.t. null is bounded in L^2 norm, as defined in Definition 1). \n\n* **Multi-index functions:** We believe that some of our results can be adapted straightforwardly to the multi-index setting. Our SQ and LDP lower bounds directly exploit the $\\mathcal{O}_d$ invariance, and the **Gegenbauer polynomials can be replaced by multivariate spherical harmonics** with little modification. The **harmonic tensor unfolding can be directly applied to the multi-index setting**:  this is in fact the algorithm proposed in a recent work on learning multi-index models [Damian et al. 2025], which appeared after this neurips deadline. \n\n* **Effect of noise:** Our lower bounds are for any spherical SIM over a rotationally symmetric input distribution. In particular, Gaussian SIM $\\nu$ with noise can be seen as the new Gaussian SIM $\\tilde{\\nu}$. The results of [Cornacchia et al.2025] can be interpreted as, in the Gaussian case, under mild assumption most single index model $\\nu$ with “high complexity”, their corresponding $\\tilde{\\nu}$ have low complexity. Whether such separations are there more generally beyond Gaussian cases remains to be seen, but our lower and upper bounds cover them by definition. We believe it is interesting to investigate this question further. \n\n--- \n[Damian et al 2025] The Generative Leap : Sharp Sample Complexity of Efficiently Learning Gaussian Multi-Index Models  , Damian, Bruna, Lee\n\n[Cornacchia et al 2025] Low-dimensional functions are efficiently learnable under randomly biased distributions, E Cornacchia, D Mikulincer, E Mosse"}]

Author rebuttal:

Meta-review: This paper studies the task of learning single-index models under spherically symmetric distributions. Prior work had essentially resolved the complexity of this task under the Gaussian distribution, and this work provides a non-trivial generalization to a broader class of distributions. Specifically, the authors provide both Statistical Query lower bounds (giving evidence of inherent information-computation tradeoffs) and efficient SGD-style algorithms for weak recovery. Overall, this work was deemed interesting and technically worthy for acceptance by the reviewers.
Decision: Accept (poster)