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.

Answers to the questions are in order.

• 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).

• 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.

• 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.

[Damian et al 2025] The Generative Leap : Sharp Sample Complexity of Efficiently Learning Gaussian Multi-Index Models , Damian, Bruna, Lee

[Cornacchia et al 2025] Low-dimensional functions are efficiently learnable under randomly biased distributions, E Cornacchia, D Mikulincer, E Mosse

We thank the reviewers for acknowledging the contribution of the work and positive feedback! Below we provide clarifications to the weaknesses.

• 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.

• 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.

• 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.

We now answer the questions.

• 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.)

• 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.

[Damian et al, 2024] Computational-statistical gaps in gaussian single-index models Alex Damian, Loucas Pillaud-Vivien, Jason D Lee, Joan Bruna

[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

We thank the reviewer for their time and positive feedback! We answer your question in order:

• 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.
• 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

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})$.

• 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.

We thank the reviewer for their interest in our work and for the interesting questions.Below we address their concerns in the weaknesses.

Missing references:

(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.

(b) We thank the reviewer for suggesting adding the “robust-learning” line of work to our related work section.

Answers to the questions are in order.

LDP and SQ:

• 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).

• 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.

• 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.

• 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.

• 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). 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.

Lemma 1: In 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.

[Damian et al, 2024] Computational-statistical gaps in gaussian single-index models A Damian, L Pillaud-Vivien, JD Lee, J Bruna

We thank the reviewer for their time in reviewing our work and overall positive feedback! Below we address their concerns in the weaknesses.

We kindly disagree that this tensor-based method follows largely from Damian et al. (2024). This 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.

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:

• 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. We argue in this paper that the harmonic decomposition is the natural basis to study single index-models as:

  • 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.)
  • 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.)

• 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.

• 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}$).

• 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).

• 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.

• 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.

  • 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.
  • 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.
  • 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.

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.

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.

Questions:

• 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.
• 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.
• 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.
• 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.