The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
Authors: Alex Damian
Jason D. Lee
Joan Bruna
Venue: NeurIPS 2025 spotlight ()
Keywords: Multi-Index Models
Low-Degree Polynomials
Computational-Statistical Gaps
Primary area: theory
TL;DR: We define a "generative leap" exponent which tightly captures the sample complexity for efficiently learning Gaussian multi-index models.

Abstract: In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the *generative leap* exponent, a natural extension of the generative exponent from Damian et al. 2024 to the multi-index setting. We show that a sample complexity of $n=\Theta(d^{1 \vee k^\star/2})$ is necessary in the class of algorithms captured by the Low-Degree-Polynomial framework; and also sufficient, by giving a sequential estimation procedure based on a spectral U-statistic over appropriate Hermite tensors.

The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
Alex Damian PACM Princeton University
Jason Lee
Electrical and Computer Engineering Princeton University
Joan Bruna
Courant Institute and Center for Data Science New York University
Abstract
In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) d-dimensional inputs through their projection onto a low-dimensional r = Oa(1) subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the generative leap exponent, natural extension of the generative exponent from Damian et al. [2024] to the multi- index setting.
show that a sample complexity of n = O(d Vi (2) necessary in the class of algorithms captured by the Low-Degree Degree-Polynonee Polynomial framework; and also sufficient, by giving a sequential estimation procedure based on spectral U-statistic over appropriate Hermite tensors.
Introduction
We consider learning Gaussian multi-indes models:
Definition 1. We say that (X,Y) follows a Gaussian multi-index model with index r if X ~ (0, Ia) = "ia and there exists subspace U Grr, d) such that the conditional law [[ only depends on the orthogonal projection Py. X.
A Gaussian multi-index model can be thus specified by choosing basis W of U (ic, element of the Stiefel manifold S(r, d)), and the law P (Z,Y) E P(R" x R) where = (W*) X. The subspace U is referred as the index space.
Given a joint distribution of (Z, Y), natural statistical task associated with such a model is to plant a subspace W*, uniformly drawn from the Haar measure of S(r, d). and draw iid samples from the multi-index distribution Pw-,p parametrized by W' and P. Our task will be then to recover U+= spannWW" given these samples. We note that this task is only well-posed when the 'intrinsic' dimension of the model is r, namely that P does not admit a factorization = 7 @ Ps,, where Ps (s(as,3) y) is the marginal of P over subspace of R" x IR of dimension + 1 that includes the last coordinate. We will assume this property from now on.
We place ourselves in the setting where = Oa(1), and consider the high- nigh-dimensional regime. Since the dimensionality of S(r, d) is of order rd, one expects that brute-force estimation procedure that fits PP, w, over suitable c-net of (W,); C S(r, d) requires (dc samples to estimate the index space up to accuracy c. Our main motivation is understand this question from the lens of computational-statiiicis gaps: how many samples are needed, as a function of d, P, to produce
or, precisely, the conditional law p2 of Z since the marginal of Z is "
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

estimate of the planted subspace using polynomial-ting algorithms, as opposed to using brute-force?
This question enjoys a large literature. spanning -ish-nimennional statistics and learning theory.
starting from the inverse regression methods from Li [191]] and beyond Xial [2008]
, Xia et al.
2002
Hristache et al. [200T], Cook and Li [2002). , Cook 2000], Vempala | Klivans et al. [2008]
Mossel et al.J [2003]. Daniely et al. [2225] (see also Bruna and Hsu [2025] for recent survey),
where efficient algorithms have been developed for specific instances. Multi-index models are an
appealing semiparametric model, and provide arguably the simplest instance of l learning,
in the sense that the index space provides an adapted low-dimensional representation to perform nigh-dimensional learning. Some notorious examples include
(noisy) Gaussian parity: YIZ d {sign| Zi Z2... [,). with PPSs = -1] - 1/. Pls = =] =
1 y) independent of Z and < 1/2.
Gaussian staircase functions: YIZ 4 01 (21) + 02 (2) + .... (Z ...... Zr).
Intersection of half-spaces: Y _ 2 2II j=1 100 2 az) 1.
Low-rank shallow neural network: YIZ = a p(V 2) + & for some a E RMM V e RTXM M .p :RRR- + R. additive noise & independent of Z.
* Polynomials: rIZ= = =(()) where q is a polynomial.
Focusing on the Gaussian setting, several works, starting from Dudeja and Hsu (2018), , Ben Arous et al. [202T] and followed by Abbe et al. [202T] 2023). Bietti et al. [0022] Damian et al. [2022]. Ba et al. 20222, Dandi al. 2024a] have built a harmonic analysis framework analyze large class of algorithms, including stochastic gradient descent over NN architectures, leading to sample complexities of the form
((d)), where k is an explicit exponent associated with a certain harmonic expansion of P. In particular, Damian et al. [2024). focusing on Single-Index models (where r = 1), identified the generative exponent k= (P)P) (see Section 2 as the fundamental quantity driving the sample complexity, in the sense that n
O(d'vk' /2) is both necessary and sufficient in the class of algorithms implemented by SQ (Statistical Queries) and Low-Degree Polynomials. essence, the generative exponent arises from an expansion of the inverse regression of 7 given Y, as put forward in the original Li] [191]. Lee et al. (2024). ; Arnaboldi et al. (2024). Dandi et al. [2024b) showed that SGD with reused samples can learn single index models dependent on the generative exponent, instead of the information exponent.
In this work, we extend this notion of generative exponent to the general multi-index setting. As already pointed out in the literature Abbe et al. 22033. Bietti et al. [2025], Troiani et al. (2024). Diakonikolas et al. [2025b), the general r > setting gives rise to important new phenomena not present in the single-index case. In particular, gradient-based learning exhibits a sequential behavior in the form of suddle-to-sadddee dynamics, where the index space is revealed incrementally along specific subspaces, with different timescales associated with each step. Moreover, such incremental alignment requires solving semi-parametric problem, where both the subspace and the link function need to be estimated jointly. We overcome these additional challenges by identifying suitable generalization of the generative exponent, the leap generative exponent k- (see Definition 3.. arising from a 'canonical' orthogonal decomposition of the index space, the leap decomposition (see Section 2).
We first show that this exponent provides computational lower bound of n = O(dk /2) under the Low-degree polynomial (LDP) framework, by extending the previously established lower bound in the single-index setting Damian et al. (2024) to an appropriate detection task that is dominated by the index estimation task (Theorem T.. Next, and more importantly, we provide an algorithm that sequentially estimates the index space along the leap decomposition from the spectrum of novel
kernel U-statistic (see Eq (5)) This algorithm recovers the index space as soon as n. Z d² /2, thus matching the LDP lower bound, and, crucially, it does not require prior knowledge of the multi-index model P (Theorem B) We complement these general results by several case studies that give novel guarantees on specific multi-index models, such as general ReLU networks or Gaussian Parities; see Section 5 Taken together, our results therefore provide the correct, sharp dimension dependence for any (Gaussian) multi-index model. In particular, as soon as k. > 2, they provide evidence of a computational to-statistical gap at the polynomial scale.

---

Related Works Chen and Meka 2020) show that any polynomial multi index model can be learned with n 2 d samples via an iterated filtered PCA algorithm. Chen al. (2022) extended this to the case of multi-index models with ReL.U activation with a similar algorithm. As we will show in Section 5 the generative exponent satisfies k* - 2, so our algorithm also requires only n 2 d.
Gradient descent on two-layer networks has been extensively studied [Bietti et al. 2025 Ren and Lee 2022 Abbe al. 2023]. these papers typically require least 2024 Ren al. 2025 Damian et
O(d'v--) where 1* is the information exponent [Arous al. 2021]. J. an upper bound of the generative exponent. Abbe et al. [0033] provide a similar definition of leap exponent but tailored to the information exponent, and thus larger than the generative leap exponent. In the setting of sparse juntas, Joshi et al. (0024) showed that by changing the loss function from square loss to another loss, gradient queries learn with complexity governed by the SQ-exponent, which is analagous the generative exponent but restricted to juntas. Troiani et al. [2024] characterize the generative leap exponent for leaps S Defilippis al. [2025]. Kovačević et 2025 give spectral estimators for the special case when the subspace is fully identified in the first leap of generative exponent < 2. See Section for further discussion.
Tensor PCA. In the context of Tensor PCA. Montanari and Richard 2014] proposed the Tensor
PCA model and presented several algorithms including tensor unfolding. Zheng and Tomioka [2015)
proposed a rectangular unfolding algorithm closely related single step of our algorithm, and showed it attain the conjectured optimal sample complexity of O(d /2). Dudeja and Hsu [202T) provided statistical query lower bounds for the symmetric and asymmetric Tensor PCA model, and Hopkins et al. [2015] 2017] gave the corresponding lower bound in the low-degree SOS models. Dudeja and Hsu [2024) provided a comprehensive study of communication lower bounds and efficient algorithms for Tensor PCA and the related problem of Non-Gaussien Component Analysis,
Arous et al. [024] initiated the study of stochastic gradient descent over the Stiefel manifold for the multi-spike Tensor PCA model, showing time complexity of d2 where ks is the order of the tensor (analogous to the generative exponent).
Chen et al. [2020] show that deep neural networks can simulate unfolding- like algorithms and learn multi-index functions with n = ((((A/2) where l the degree of the polynomial approximation to the groundtruth function. This method requires that the groundtruth is close to polynomial.
Vempala 2010). Klivans et al. (2024) provides the current best known result for learning intersection of h-halisppces in d-dimensions with n = (d).. Vempala and Xiao [0022] provide a moment-based algorithm for learning multi-index models when the first leap learns all relevant variables.
While this work was being finalized, we became aware of Diakonikolas et al. 2025b which introduces a similar estimation procedure based on subspace conditioning. They define the class of m-well-behaved multi-indes models. For the special case of single index models with generative exponent k*, Diakonikolas et al. [0255] C.3.2] show m = k*: we believe similar equivalence holds also for multi-index models. However the proposed algorithm requires sample complexity d((kk)) even in the realizable setting, whereas the algorithm of Damian et al. [2024] and this work, require only
D.2] and Diakonikolas et al. [2025a [Appendix
((d*" and apply when y is either continuous or discrete. On the other hand, Diakonikolas et al. [0255bla al algorithms aim for agnostic PAC learning, not just recovery of the subspace, and thus are able to explicitly characterize
the dependence in the hidden constant C(P) in C(P)dLVk* /2, By building an explicit piecewise constant discretization the subspace, they explicitly characterize the dependence on r, e, and Lipschitz parameters. We expect that our subspace recovery algorithm can be combined with discretization algorithm to attain similar guarantees, but with improved dependence on d. We also study several examples of the leap generative exponents in Section 5 including piecewise linear functions (deep ReLU Networks with bias) and general deep neural networks with r-dimensional first hidden layer, improving upon previous results specific to multi-index polynomials and homogeneous piecewise linear functions Chen and Meka 2200)), Chen et al. 2022
Notation by denotes the normalized k-th Hermite tensor, defined as h2 (u) = (-11* vokza(u) for Vkl ya(u)
M E RRd. S(r, d) is the Stiefiel manifold of r x orthogonal matrices, and g(r, d) the Grassman manifold, obtained by quotienting S(r, d) by r-dimensional basis transformations. For two subspaces
3

---

T S T", we write T" \\ T as the orthogonal complement of T in T". For two subspaces T, T" we define their distance dT) to be ||I ITrlloo where II, the orthogonal projection onto T.
Paper outline. Section 2 recalls the generative exponent for single-index models and shows how to generalize the definition to multi-index models via the leap generative exponent, and discuss the relation to the leap information exponent. Section B gives the main computational lower bound result which shows that in the low-degree polynomial framework the multi-index model with leap generative exponent k* requires 2 Q(dd5//) Section 4 gives our main algorithm, an iterative spectral method based on a Hermite Kernel U-statistic, that recovers the subspace with the optimal sample complexity, Finally in Section [5] we study the leap generative exponents of several function classes including piecewise linear functions and general neural networks with r-dimensional first hidden layer.
2 The Leap Decomposition
Preliminaries:
The Generative Exponent for Single-Index Models We start by recalling the
generative exponent for single-index models Damian et [022)]. Given (Z, Y) drawn from a joint
distribution P E P(R x I) with first marginal equal to a Gaussian, and such that P * 71 @ P... we
define for each integer k 2 1, Sk == E (Z) E (PgP)), y). and k* = inf |(a]] Equivalently, k* is the smallest integer & such that there exists a measurable function T R - E and mean-zero k-th degree polynomial such that (YY((Y)u()) Z)) * O. The main takeaway from Damian
0}.
et al. 2024] is that (dt (2v1) is both necessary (under the SQ and the LDP frameworks) and
sufficient for recovery of the planted direction
Subspace Filtration and Leap exponents: We begin by generalizing the coefficients } from
Damian et al. 2024]. The key novel ingredient is the notion of subspace filtration, capturing the sequential nature of the multi-index estimation, and which appears in several existing multi-index estimation procedures Abbbe et al. [2022] 2023), Bietti et al. [2025). Diakonikolas et al. (2025)). In essence, we now need extend the expectations (R. which were conditional on the label y. to
conditional expectations on an "augmented label' that includes all the previously estimated directions of the index space. More formally, let S G(r', r)) be a subspace, and for E I' let æs E S denote the orthogonal projection of z onto S. We write Øs = (zs; y) E RR+tr' and Es = 2ş E RR-
For any S E G(r',r), r), we then define:
Ck.s == (1 (Ts) (3(tttr'' , (8 .Pr),
As(S)= Ey, (Ys) & (Ys)( (S y022 xz(() = Ey, lk ((s)),,s((sss(]]))
Intuitively, these tensors capture whether there is any information "of order k- that can be captured, given knowledge of the subspace S. When S = and r = 1, these definitions reduce to those in Damian al. 2024). Finally, we note that these definitions only depend on the joint distribution P of (2, Y) and are independent of the choice of W*
Given subspace S, define the associated null distribution Ps by:
dP dP Y! dP[ Y]
Under Ps. (Y, 2s) and Zg have the same marginals as under P, but are independent. The label transformations Ça appear as the Hermite coefficients of the density ratio aps.
Lemma (Density Ratio expansion). We have the following formal expansion in T.2 (P2sss):
dP
1z. Y
Σ (a A00
dP s
This implies the following decomposition of x=(Pl(Pss) whenever this divergence exists:
Lemma 2 (Mutual Information Expansion). If x (P)(Ps) < x,, (P|[Ps)) = Σ (S).
and also to learn the target, by performing subsequent dimension- free non con-aarmettri regression.

---

Notice that while (P|(sss) may be infinite in some cases, e.g. in deterministic models where Y oZ), the quantities (S) are well-defined for all k. since (E.S E (P(PPr)) Given this expansion, we can immediately define the leap ((S) of a subset S:
Definition (Generative Leap relative to S). (s)) is the smallest k 2 1 such that 25 > O.
Note that k(S) < long P A Ps.
The Leap Decomposition: We will define the flag F = {0 = So C Si ....
... & Sr = IR))
inductively as follows. Given subspace S₁, i 0, we define ki+1 k(s)) and S,+1 by:
S411 == S @ span[AAu11S))))
(1)
Here, we have defined the span of symmetric tensor T (R)) as span
span ( [T]] where Mat,, [T] denotes T reshaped as an x p matrix.
Definition (Generative Leap Exponent). Let k,, i = 1....,L L be defined as above. The generative leap exponent is defined k- max; kis
We now verify that the Leap decomposition is well-defined, and give variational representation.
Definition Given two subspaces S T, we define the relative eap TT) of a subspace lowards T as
k(S,T) == [n; TV (
(2)
In words, the relative lapp measures the order of the Hermite tensor needed to 'reach' the subspace T from conditional expectations over y and zg. Observe that we can relate the leaps k(S) and k(S,T) as k(S)= infr:sçr T).
Proposition 1 (Variational Characterization of Leap Generative Exponent). The leap decomposition terminates in a finite number of steps L S Moreover, we have
k*
inf F=((=RoC...C3"
max k( R2 Ryt1).
Finally, k² is invariant to rotation: if = (U @ & where U E O, any rotation of the model, we have k* (P) -P)))
Relationship with Information Leap Exponent the information leap exponent, first introduced in Abbe et al. [2023) (referred to as IsoLeap in the setting of Gaussian input data); also Bietti et al. [2025] and Dandi et al. [2024a] Let first recall its definition in our context. For any S E (( r), we define:
Finally, relate the generative leap exponent to
Č.. == EY (Zs)
(R (S (S+)) Pzs)
AR(S) = Ez (Z.) Č.. [ss)
XR 122
13zs
[(i..s(2))
By analogy with Definition 2 we define ((S) to be the smallest & such that (²( > 0. Equipped with this object, the information leap exponent is recovered as follows.
Definition 5 (Information Leap Exponent, Abbe al. 2023 Bietti et al. [2025] ). The information
leap exponent of the multi-index model P is given by 1* = max; 4 where 4,+1 = I(S.) and ($:); is
defined recursively by 5. = 0 and 5,41 S, @ span|A,... (8.)).
Let us now relate the Information Leap exponent to the generative leap. We start with a direct generalization of (Damian et al. 2024 Prop 2.6]:
Proposition 2 (Generative and Information Exponents relative to subspaces). For any subspace S,
A(S)PP
inf ((S) @ P].
TELP(P Rs)
In particular we have k(S) < ((S))() for any subspace S.
3 oone explicitly control ||||| see Lemma 14
5

---

In words, the generative exponent relative to subspace S is the largest k such that Ep[7(y: 25) )] for any measurable function and any polynomial q of degree This provides useful characterization, as illustrated in the examples of Section 5
As expected, the generative leap is upper bounded by the information leap: Proposition 3 (Relationship with Leap Information Exponent). We have k* S 1*
Proofs of these results are deferred to Appendix
B
3 Computational Lower Bounds in the Low-Degree Polynomial Class
Let us first establish computational lower bound for the estimation of a multi-index model. Following Damian al. (2024), and relying on the fact that detecting planted structure a necessary byproduct of estimating the index space, we instantiate a hypothesis testing adapted to the leap decomposition.
Given P and its associated leap decomposition 11. we consider S the subspace of dimension ro associated with the generative leap, ie ks = A(S). Let y (Sz, y) be the effective label, with y E go+t W = =SW** W* the planted subspace associated with and ã = W-r E Rd- the effective input. Viewing P as the joint distribution of (S+ v) we define Py as the marginal over y- Note that < r by definition. We consider the following detection problem, conditional on W:
Hj there is a planted model of dimension > ro using P as link function and y as label. Specifically, (z. () ~ Ew Pww where P W (7) Φ) = P W x).
Ho there is only planted structure up to dimension ro: i..., (z. () ~ Po == Yd-ro @ pg-
dis and its orthogonal projection R&D D in (Ho) onto By considering the likelihood ratio R = d:to
polynomials of degree at most D, one can assess the ability of low-degree polynomials to solve this [2018). Specifically, if
hypothesis testing problem Bandeira al. [2022] Hopkins
1 + oa(1), then degree-D polynomial in the input samples weakly separate IHg from IH, ie
satisfy max (Varo[]]), Var, [5] O() Ro [/] [f](]) as oo [Bandeira et al. 2022 Proposition 6.2].
Theorem 1 (Weak separation lower bound). Consider > max(r, D = O(log(d))) and n = 0(d for any 7 > Then [RRg]lla(E.) = oa(1).
In other words, any degree-1) D polynomial test needs > (2(xt//2) samples to weakly detect Hi] from HHg. Polynomial tests of degree w w(log d) are considered a powerful step towards ruling out all noise-tolerant polynomial-time algorithms Bandeira et al. [022] Kunisky et al. [2119) The proof can be found in Appendix
This low- degree lower bound extends the previous LDP lower-bound from the single-index setting Damian 2024). In that single-index setting, this LDP lower bound agrees with SQ lower bound of (dd (2) samples. While is possible to translate our LDP lower bounds SQ lower bounds, eg via Brennan et al. 2002]] we note that there is fundamental distinction arising in the multi-index setting, stemming from the inherent inability to perform certain spectral tasks in SQ. Dudeja and Hsu [202]] illustrated this mismatch in the setting of Tensor PCA, where asymmetric structures (such as the ones faced by multi-index model estimation) incur in additional ciinension-factorr That said, some SQ lower bounds are known for the multi-index setting. Joshi et al. [2024] establishes SQ lower bounds for the number of queries of order (ddk) ), and Diakonikolas et al. 2202bb al obtains sample complexity lower bounds of order (dt /2) (where the generative leap is replaced by the equivalent m in their notation), thus matching our LDP lower bounds.
Upper Bound via Hermite Kernel U-Statistic
We begin by describing a spectral estimator that works for a single leap. To motivate it, recall that the spectral estimator for single index models in Damian al. (2024) began by estimating the tensor:
T Ex, h)

---

For suitable label transformation T. the true expectation is proportional to (w*)&*, estimating w" is similar to single-spike tensor PCA problem. For this problem, the partial trace estimator an effective way to estimate w". This estimator consists in repeatedly contracting indices 7 イ- T until you are left with a vector whose expectation is w" or a matrix whose expectation is w- (w") However, this trick does work in the multi-index setting. For example, consider Gaussian k-parity: s2gn(21 .. 2z). For this problem, we can compute the population mean of an order lo estimator
T = ( (2) 6/2 Vi! Sym(wī @ ..... w.))-
Thus, this behaves like a symmetric multi-spike tensor PCA problem. For this problem, note that because the {w;} are mutually orthogonal, T[ = so taking any partial traces of this tensor will fail to produce consistent estimator. For standard tensor PCA, this can be solved by tensor unfolding Montanari and Richard (2014). For example, /Zheng and Tomioka| [2015] showed it was sufficient to unfold T into d x d=1 matrix and compute the left singular vectors. Explicitly if
Mai [T] denotes T reshaped as d x d matrix, then you can perform spectral decomposition of AAT E Rdxdd and the top eigenvectors will recover the hidden directions.
Returning the multi-index setting, this would motivate the following estimator. Given samples {( 3:) we define the embedding o, the flattened tensor & and the matrix estimator M, by:
72 Σ
((x) = Mate
+
(T)))d(a)) E BRdxd" M, == ΦΦ E Rddd n
We can then perform a spectral decomposition of M,. Note that this is exactly equivalent to estimating the tensor 1 Ei= hy (z;), unfolding it into d d matrix, and computing its left singular vectors. However, this strategy cannot achieve the optimal threshold of n. Z d because the "diagonal" expand M, as:
terms dominate the matrix and destroy the concentration. More specifically,
Mn =
Σ
n
Σ
Σ i73
+ n
n
(n)
(TT)
For this estimator, one can show that the spikes in E Mn get lost in the bulk of the eigenvalues corresponding (I) unless 2 dlv"'' which falls short of the optimal threshold d=v3, To improve this estimator, we therefore isolate the second term (II):
Un nlnn - Σ (())T())(())))e) {tj
This is an order 2 matrix U-statistic which only sums over the disjoint pairs i + j. As result the E T and we prove that Un does concentrate to its expectation dk/2 samples (Theorem 2).
expectation is preserved: E EU, in operator norm with
However, it is not true in general that single label transformation T is enough for E Un to span the entire space when there are multiple leaps i.c. it may be necessary to use label transformation Ti to estimate the first direction wi and To to estimate w². Rather than computing the top eigenvector of this matrix U-statistic for each label transformation T, could simply add them together into T(Y)= = (Y), Ti (Y))
] E R. and form an aggregate matrix:
Un n(n 1)
1
Σ (a)))();)) T(;)) {g)
Because T only enters the U-statistic through inner products, we can use the kernel trick and replace with general PSD kernel K:
1
Σ ((I,)((z)) K K(y.
Un nnn
(5)
We note that because the labels lie in (0, 1) for Gaussian parity, applying label transformation is equivalent affine transformation of I and therefore cannot help estimate the hidden directions.
7

---

Algorithm 1: A Single Leap
Input: dataset D {(T, y:) moment k recovery dimension PSD Kernel K Φi axat-x (2:) for Soril1.... I.....
Un m[n-1] Eny $10 K()..1)) [S < eig(Un)
Output: span span(y)......
which reduces the above setting by taking K(y.: Uj) more general kernels K which correspond to "infinite" embedding vectors T, this allows to automati- cally average over an "infinite number" of label transformations. We will show that this allows to learn the subspace corresponding to the next leap with the optimal sample complexity of n 2 d without any knowledge of the multi-index model P. To begin, we prove the following lemma which controls the expectation of this matrix U-statistic:
(T(v)), T(p))). However, by allowing
Lemma 3. If K is integrally strictly positive definite Ihhre exist c(P, C(P, K) 0 independent of d such that if S == (U*)T span A&] denotes the subspace corresponding to the next leap then
c(P, KYIls 3 EU,, = C(P,K)II,
We note that commonly used kernels like the RBF kernel automatically satisfy the assumption in Lemma 3 This implies that if we could estimate the span of E Un. we could recover the next leap. To estimate the span, use the following theorem which bounds U,. BU, in operator norm:
Theorem 2 (Concentration of U-Statistic). Let K be PSD kernel with K (y, y) S 1 for all Then i Zx d /e + dr f we have that |U, - EE Unllop S e with probability at least 1 - exp(-d") for an absolute constant c > O.
As corollary, by Davis-Kahan we can recover the subspace up error with 2 /2/3/e d/e² samples where the hidden constant is independent of and depends only on the multi-inde indexxiiexxxxxii model P: Corollary 1 (Subspace Recovery). For any multi-index model P, there exists constant C(P, K) independent of d such that if n 2 C(P, dh/2 + ++]] then the output S C TR& of Algorithm / satisfies d(S, (U+)T span[As]) S with probability at least 1 exp(-dd) for absolute constant e O.
4.1 Iterating over Leaps
Once we have recovered an partial subspace S, which we hope is approximately contained in span[(U')T]] we need to continue this process to take the next leap. We can consider the augmented label Ys (Y, Il Then X, Y again form a multi-index model with hidden dimension at most so we can repeat our matrix U-statistic estimator from the previous section. Note that the kernel K
now maps SS| x R[ + R. We will denote the resulting kernel by U (8))
U(
6:0e K[VV,, Usa;;, (Jj, Isæ,l))
n(n 1)
We can directly apply Corollary to show that for any subspace S, we recover the span of (U*)T (S) up to error with n 2 dd /c d/c² samples. We will now control the accumulation of errors to show that we can recover the full multi-index model with 2 C(P, K)dk" /2/6 samples: Lemma 4. If the kernel K is L-Lipschitz, then there exists a constant C(P, K) such that the map S + (U is C(P, K) L-L-ssssc in operator norm.
common example of a Lipschitz kernel is the RBF kernel which is 1/ L/isshiih Therefore if we run this estimator starting with the wrong subspace Š with d(S, S) S e, then the span of our estimator
'ee say that K is integrally strictly positive definite for all finite non-zero signed Borel measures p. K (z, y)du(z)du(()) > 0. We remark that many commonly used kernels, including the RBF and Laplacian kernels, satisfy this assumption (Sriperumbudur al. 2010

---

Algorithm 2: lterating over Leaps
Input: dataset D {(T.. W:) moments (k: ) subspace dimensions {& Kernels { S
for = 1,... m do
Draw |n/ m//m fresh samples D, from D
y - y. Mg R181+1 for (a, y) E D
S + 5th Algorithm (i,,,,
end
Output: S
only change by C(P, KLL.. By iterating this argument, Theorem 2 implies that Algorithm 2 will succeed in recovering span[U-T] up error given 2 d + d/e² samples:
Theorem 3 (Main Result), For any multi-index model P. there exists a constant C(P,
((P,A) K) independent
of d such that if n 2 C(P, K) d²'/2 + + then the output c Rd of Algorithm satisfies
d(S, (ps-s)))((U))T)) S E with probability at least 111-xxpp exp(-dd)) for some c c= ==cck²) >0. O.
Remark 4. Our main upper bound, Algorithm requires knowledge of the sizes of each leap (k.) and the dimension of each leap {si}- However, these restrictions can be easily lifted, in the spirit of Dudeja and Hsu (018]). Using the guarantee in Theorem 2 we could start with k = 1 for each leap and increase k until detect outlier eigenvalues outside of the /d//2 /n-bulk.. However, for simplicity we have written the algorithm assuming knowledge of both {k;} and {st}-
Our Algorithm 2 is thus a streamlined version of a subspace conditioned spectral method. While it shares similarities with recent methods in the literature Chen and Meka (2020). , Chen al. [2022). Diakonikolas et al. [2025b]a] a. Troiani et al. [2024), it crucially relies on a U-statistic in order to An additional feature of our algorithm that to our
reach the optimal sample complexity of d knowledge is novel in the literature is the use of a generic kernel over the already discovered labels, which eliminates the need to perform successive non- parametric regressions during the subspace recovery. At the technical level, the concentration of the U-statistic is priori challenging due the heavy tails of the associated Hermite tensors; this is addressed using Gaussian universality results from Brailovskaya and van Handel [Brailovskaya and van Handel 2022). with dedicated analysis in the setting where k' < to avoid spurious log-factors.
5
Case Studies
We conclude this article by computing the generative leap exponent of representative multi-index models. For some of these models our upper and lower bounds recover known results in the literature, but some are new, For simplicity, we focus here on noiseless models where YIZ = o()) for a given
link function gr + R. Proofs for this section can be found in Appendix B
5.1 Polynomial and Threshold Functions
We start by computing the generative leap for 'classic' multi-index classes given by parities, intersec- tion of half-spaces and polynomials. Proposition 4 (Generative Leaps for representative models). We have:
(i) r-Gaussian Parity has k* = ---
(ii) Staircase Parity functions have k* < 1,
(iii) Intersection of halfspaces have k* 2,
(iv) Polynomials have ks <
For r-Gaussian parity, we thus obtain an efficient learning algorithm that requires n ( samples (which is optimal within the LDP class), and is to the best of our knowledge the first resul
'The agnostic improper learning algorithm of Chen et al. 2020 can potentially attain I(d(=/22) since the information exponent this implies that there is degree polynomial with non trivtrival correlation with

---

that succeeds with (2) samples. The sample complexity of learning intersection of half-spaces is thus linear in dimension: this was known since Vempala (2010), Diakonikolas al. [2017] Klivans et al. [2024), and for polynomials the same conclusion was established in CChen and Meka [2020]
We emphasize that while our results do capture the correct dependency in d, they are not fine-grained enough to provide the correct dependencies in r.
5.2 Piecewise Linear Functions
Piecewise linear continuous functions, part motivated by ReLU architectures, have been extensively studied in the context of Gaussian Multi-index models Chen et al. [022 2023]. Diakonikolas and models[Chen
Kane [0024). When a is 1-homogeneous, as in bias-free ReLU networks, it is not hard to see that
k S 2, by considering diverging level sets {z; [=)) 2 }} with À + co. Here we extend this result to the general piece-wise linear setting, including arbitrary ReLU networks with non-zero biases.
Proposition 5 (Generative Leap for Piecewise Linear Functions). If continuous and piece-wise
linear then (a) < 2.
The proof exploits the analytic properties of Hermite functions, i.e. functions of the form f()) pz)) As an immediate corollary, Algorithm from Section 4 learns arbitrary ReLU networks low-rank arbitrary ReLU networks in the proportional regime n (dd): This improves the result Chen et al. [2022] by allowing biases. Once the subspace is recovered, one could 'upgrade' to PAC learning the model using a standard non-parametric method, by regressing over the covariates S This would incur in an additional sample complexity with potentially exponential dependencies in and 1. but, importantly, independent of d.
5.3 Generative Leap under Linear Transformations
An important feature of the generative leap exponent is that the statement "k* (P) S k² is an 'open' property, meaning that one should expect the leap exponent be preserved reduced by slightly perturbing the distribution P. We formalize this intuition in the following result which shows that for almost all weight matrices, the generative leap is S
Proposition 6 (Generative Leap under linear transformations). Let Let :R RE (.E.)())) a and let Mr denote the set of r x r real matrices.
(i) For O MM, define ye =0TT)) except possibly for set of r2 dimensional Lebesgue measure zero,
2). Then (z, ye) ~ Pe satisfies k- (Pe) S for every θ
(ii) Assume that (z))(z)) ~ P has single leap with generative exponent k*. Ler D C I +M, be any analytic map such that I, E Im([') and I'(0) is invertible for all D. For 0 E D, define ys (I Then (z, (e) ~ P9 satisfies k* (Pa) S k* for every 0, except possibly for a set of s-dimensional Lebesgue measure zero
5.4 Shallow Neural Networks
Finally, we study two layer neural networks of the form a(2) Ei (z 02). When the O, are orthogonal, estimating the index space requires estimating each neuron, and k²((a) = kp):::: Proposition (Generative Leap for Orthogonal Weights). Let y E)m (z(())) Then k* 2 (p). Moreover, if all moments of p(Z) exist, then ks* 1:* (p).
We extend this result to almost all networks with unit norm, linearly independent columns: Corollary 2 (Non-orthogonal, invertible weights). Let yv Σj= ajp(y]] with ||,y|l 1. Then k"v I k*t (p) for all V, except possibly for a set of r(r 1) dimeensiio measure 0.
An interesting question left for future work is whether this uniform control of the generative exponent by ks* (p) for any V could be extended general link functions; in other words whether the exclusion of these zero-measure sets is necessary in Proposition 6
the r Gaussian parity. Thus Chen et al. 2020 can be used to get error better than random guessing. but not vanishing error.
10

---

References
E. Abbe, E. Boix-Adsera, M. S. Brennan, G. Bresler, and D. Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems, 34:26989-2787 2021.
E. Abbe, E. B. Adsera, and Misiakiewicz. The merged-staine -taircs property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks, In Conference on Learning Theory, pages 4782-4887. PMLR, 2022.
E. Abbe, E. Adsera, and T. Misiakiewicz. Sgd learning on neural networks: leap complexity and maddle-to-saddie dynamics. In The Thirty Sixth Annual Conference Learning Theory, pages 2552-2623 PMLR, 2023.
L. Amaboldi, Y. Dandi, F. Krzakala, Pesce, and Stephan. Repetita iuvant: Data repetition allows sgd to learn fighddimessionl multi-index functions, 2024. URL httts:://rxxi org/ abs/2405.15455
G. B. Arous, Gheissari, and A. Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1-51, 2021.
G. B. Arous, C. Gerbelot, and V. Piccolo. Stochastic gradient descent in high dimensions for multi-spiked tensor pea, 2024. URL htt.httss////xiii.. http:/i..orggab/////11/ abwp//a/..... 18162.
J. Ba, M. A. Erdogdu, T. Suzuki, Z. Wang, D. Wu, and G. Yang. High-dimensional asymptotics of fea- ture learning: How one gradient step improves the representation. arXiv preprint arX1v:2205.01445, 2022.
A. S. Bandeira, A. El Alaoui, S. Hopkins, T. Schramm, A. S. Wein, and I. Zadik. The franz- parisi criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems, 35:33831-33888 2022.
A. S. Bandeira, M. T. Boedihardjo, and R. van Handel. Matrix concentration inequalities and free probability. Inventiones mathematicae, 234(1):419-48) June 2023. ISSN 1432-1297. doi: 1011077/40022--22--000444
URL / doi orw...gg//11. 1007/ 0200002222022--2000 020-2222222-010-----00
G. Ben Arous, R. Gheissari, and A. Jagannath. Online stochastic gradient descent on non-convex losses from dith-iimensional inference. Journal of Machine Learning Research (JMLR), 22: 106-1, 2021.
A. Bietti, J. Bruna, C. Sanford, and M. Song. Learning single-index models with shallow neural networks. Advances in neural information processing systems, 35:9768-9783, 2022.
A. Bietti, J. Bruna, and L. Pillaud-Vivise On learning gaussian multi-inde models with gradient flow. Communications in Pure and Applied Mathematics, 2025.
Brailovskaya and R. van Handel. Universality and sharp matrix concentration inequalities. Geometric and Functional Analysis, 34(6):1334-1838 2024.
M. Brennan, G. Bresler, S. Hopkins, J. Li, and T. Schramm. Statistical query algorithms and low-degree tests are almost equivalent. In Conference on Learning Theory, 2021.
J. Bruna and D. Hsu. Survey algorithms for multi-index models. arXiv preprint arX1v:2504.05426, 2025.
M. Chen, Bai, J. D. Lee, T. Zhao, H. Wang, C. Xiong, and R. Socher. Towards understanding hier- archical learning: Benefits of neural representations. Advances in Neural Information Processing Systems, 2020.
Chen and R. Meka. Learning polynomials in few relevant dimensions. Conference on Learning Theory, pages 1161-1227. PMLR, 2020.
S. Chen, A. R. Klivans, and R. Meka. Learning deep relu networks is fixed- rred-parameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707. IEEE, 2022.
11

---

S. Chen, Z. Dou, S. Goel. A. Klivans, and R. Meka. Learning narrow oaye relu networks. In The Thirty Sixth Annual Conference on Learning Theory, pages 5580-5614. PMLR, 2023.
R. D. Cook. SAVE: method for dimension reduction and graphics in regression. Communications in Statistics Theory and Methods, 29(9-10):209-21221 2000.
R. D. Cook and B. Li. Dimension reduction for conditional mean in regression. The Annals of Statistics, 30(2)455-474, 2002.
A. Damian, J. Lee, and M. Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, 2022.
A. Damian, E. Nichani, R. Ge, and D. Lee. Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. Advances in Neural Information Processing Systems, 36:752-784, 2023.
A. Damian, L. Pillaud-Vivien, J. Lee, and J. Bruna. Computationall-tatisse gaps in gaussian single- index models. In The Thirty Seventh Anmual Conference on Learning Theory, pages 262--1662. PMLR, 2024.
Y. Dandi, F. Krzakala, B. Loureiro, L. Pesce, and L. Stephan. How two-layer neural networks leam, one (giant) step at time. Journal of Machine Learning Research, 25(349):1-65, 2024a.
Y. Dandi, E. Troiani, L. Amaboldi, L. Pesce, L. Zdeborova, and F. Krzakala. The benefits of reusing batches for gradient descent two-layer networks: breaking the curse of information and leap exponents. In Proceedings of the 41st International Conference on Machine Learning, pages 9991-10016, 2024b.
A. Daniely, Mchalel, and E. Mossel. Online learning of neural networks. arXiv preprint arXiv:2505.09 167,, 2025.
V. H. de la Peña and E. Giné. Decoupling of U-Statistics and U-Processes, pages 97-152. Springer New York, New York, NY, 1999. ISBN 978- 178-1--411-- doi: URL https: //doi.. org/10.
L. Defilippis, Y. Dandi, P. Mergny, F. Krzakala, and B. Loureiro. Optimal spectral transitions in high-dimensional multi-index models. arXiv preprint arXiv:2502.02545, 2025.
I. Diakonikolas and D. M. Kane. Efficiently learning one-hidden-layer relu networks via schur polynomials. In The Thirty Seventh Anmual Conference on Learning Theory, pages 1364-1378. PMLR, 2024.
I. Diakonikolas, M. Kane, and A. Stewart. Learning geometric concepts with nasty noise, 2017. URL httts::/aaxiisi wwwps/iii.rrr/eeooooeeeee abs/1707 01242
I. Diakonikolas, G. lakovidis, D. M. Kane, and L. Ren. Algorithms and sq lower bounds for robustly learning real-valued multi-index models, 2025a. URL ftttp:://arxiivoor//abbaa 2505. 21475
I. Diakonikolas, G. Iakovidis, D. M. Kane, and N. Zarifis. Robust learning of multi-index models via iterative subspace approximation, 2025b. URL
wwtp:////.aaaaa//2..././// 09525
R. Dudeja and D. Hsu. Learning single-index models in gaussian space. In Thirty-First Annual Conference on Learning Theory, 2018.
R. Dudeja and D. Hsu. Statistical query lower bounds for tensor pea. Journal of Machine Learning Research, 22(83):1-51, 2021.
R. Dudeja and D. Hsu. Statistical computatiol trade-offs tensor PCA and related problems via communication complexity. The Annals of Statistics, 52(1):131-156, 2024.
S. Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.
B. Hopkins, J. Shi, and Steurer. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory, pages 956-1006. PMLR, 2015.
12

---

S. B. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer. The power of sum-of-squares for detecting hidden structures. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720-731. IEEE, 2017.
M. Hristache, A. Juditsky, J. Polzehl, and V. Spokoiny. Structure adaptive approach for dimension reduction. The Annals of Statistics, 29(6):1577-1666, 2001.
N. Joshi, T. Misiakiewicz, and N. Srebro. On the complexity of learning sparse functions with statistical and gradient queries. Advances in Neural Information Processing Systems, 37:103198- 103241, 2024.
A. Klivans, K. Stavropoulos, and A. Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds. In The Thirty Seventh Annual Conference Learning Theory, pages
PMLR, 2024.
A. R. Klivans, R. O'Donnell, and R. A. Servedio. Learning geometric concepts via gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science, pages 541-550, 2008.
Kovačević, Y. Zhang, and M. Mondelli. Spectral estimators for multi-index models: Precise asymptotics and optimal weak recovery. arXiv preprini arXiv:2502.01588, 2025.
D. Kumisky, A. S. Wein, and A. S. Bandcira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv: / 1636, 2019.
J. D. Lee, K. Oko, T. Suzuki, and D. Wu. Neural network learns low-dimensional polynomials with sgd near the information theorreti limit. Advances Neural Information Processing Systems, 37: 58716-587555 117766586661 2024.
K.-C. Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, 86(414):316-22,, 1991.
B. Mityagin. The zero set of a real analytic function. arXiv preprint arXiv:1512.07276 2015.
A. Montanari and E. Richard, A statistical model for tensor pea. Advances neural information processing systems, 27, 2014.
E. Mossel, R. O'Donnell, and R. P. Servedio. Learning juntas. In Proceedings of the thirty-fifth annual ACM symposium Theory of computing, pages
2003.
Y. Ren and J. D. Lee. Learning orthogonal multi-index models: A fine-grained information exponent analysis. arXiv preprint arXiv:24100 240.099780 2024.
Y. Ren, E. Nichani, D. Wu, and J. D. Lee. Emergence and scaling laws in sgd learning of shallow neural networks. arXiv preprint arXiv:2504. 19983, 2025.
B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. G. Lanckriet. Hilbert Space Embeddings and Metrics on Probability Measures. Journal of Machine Learning Research (JMLR), 11:1517-1561, 2010.
E. Troiani, Y. Dandi, L. Defilippis, L. Zdeborová, B. Loureiro, and F. Krzakala. Fundamental limits of weak learnability in high-dimensional multi-index models, 2024. /Rtpattss///arxxi..oo abs/2405, 15480.
S. S. Vempala. Learning convex concepts from gaussian distributions with pca. In 5 Annual IEEE Symposium Foundations of Computer Science, pages 124-130, 2010.
S. S. Vempala and Y. Xiao. Structure from local optima: Learning subspace juntas via higher order pea, 2012. (Rtppttt:///arttt http:///////aaaaaaaaaaa/ wwt.ab//.......... 3329
Y. Xia. A multiple-index model and dimension reduction. Journal of the American Statistical Association, 103(484):1631-1160, 2008
Y. Xia, H. Tong, W. K. Li, and L.-X. Zhu. An adaptive estimation of dimension reduction space. Journal of the Royal Statistical Society Series B: Statistical Methodology, 64(3):363-410, 2002.
Q. Zheng and R. Tomioka. Interpolating convex and non-convex tensor decompositions via the subspace norm. Advances in Neural Information Processing Systems, 28, 2015.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We define the generative leap in Definition B We prove sample complexity
lower bound in Theorem and we prove a matching upper bound Theorem 3
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
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long 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: See Appendix
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 out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: The proof of Theorem | can be found in Appendix C The proof of Theorem can be found in Appendix D
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged 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 be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not contain experiments.
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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 to replicate the results, access to a hosted model (e.g.. 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 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not provide experiments.
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 NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttae//gguddeeeeeSouuuuumbbbba ssionPolicy) 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 omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not provide experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not provide experiments.
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, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not provide experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http://///rrrpppppppppccee/e/e//
Answer: [Yes]
Justification:
This research conforms to the NeurlPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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: This work purely theoretical and is focused on understanding the fundamental limitations of learning with synthetic Gaussian data.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We are not releasing data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not any original assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part 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 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We did not conduct any crowdsourcing experiments or research with human
subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 the institution conducting the review.
19

---

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 did not use LLMs as any important, original, or non-standard component.
Guidelines:
The answer NA means that the core method development in this research does not non Please refer to our L.LM policy Doctps://neurige http://eeuurpp..eeeoeeeeeeeeeeee wcc/onnerences//0000 for what should or should not be described.
involve LLMs as any important, original, non sta-standard components.
A Conclusions
In this work, we have extended the generative exponent k- to the general class of Gaussian multi-index models, and established tight sample complexity index space under no prior knowledge of the link function. We provide lower bound based on the low-degree polynomial framework, and a matching upper bound obtained with novel spectral method that incrementally reveals directions of the index space from a kernel U-statistic. The resulting upper bound recovers and extends several dedicated estimation procedures for specific families of multi-index models, such as ReLU networks or intersection of half-spaces.
(dd /2^1) for learning their associated
There are several avenues for future work. First, this paper focuses on the simple setting of isotropic Gaussian data. Extending both the information leap and generative leap more complicated data distributions is left to future work. Next, we focus on deriving estimators that work with minimal information about the multi-index model P, and which succeed with the optimal sample complexity in the ambient dimension d. As result, our sample complexity guarantees scale with constants C(P) which could potentially exponentially large in the hidden dimension r. Finally, we focus primarily on subspace estimation, as it is requirement for full end-to-end learning.
B Proofs of Section
Proof of Lemmal 7 This is direct generalization of [Damian et al. 2024 Lemma D.1]. The k-th Hermite expansion of the likelihood ratio, viewed function of the label Ys. is directly
dP dPs s
Eps
(Zs, Vs)hu ( 8s
( Cr.8
(6)
and thus, in (P(Pss), have
dP (Es. ūs) Σ (Gr,s(Ds),
dPs
Proof of Lemma
2
By orthogonality of Hermite polynomials:
(P = Ep:
dP
X 2
Ev.z,
[I<a(1=ss)]]] => (S A2
dPs
Proof of Proposition 7 The first statement follows immediately from the definition. To prove 3] we need to show that k- max, 1s R2, Rz+1) for any flag F. Let S the subspace associated with the generative leap k*, and let j' be the largest index such that R, C S.
20

---

We claim that for any &o and any pair of subspaces T S T', we have span A (x S T span A (T)). Indeed, writing Y' E T" as Y" (Y with Y E T and Y E T,, we have SA.7 (Y) By SR. (Y, Y) when restricted to (T') (a subset of T+). Now, suppose towards contra- diction that kn k( (Ry,, Ry+1) < k Since R2 S S, we have span( (Ry))) S $ ( span(A for l: & ky. But from the definition of k- we have apan(A((5)) = 9 for l S ky, which implies that Ry+1 C S, which is contradiction.
Finally, verify that the generative leap is invariant to rotation by observing that A₃ covariant to rotations, and therefore their associated spans preserve the same dimensions for all k.
Proof of Proposition The proof is an extension of DDmiian et al. 2024 Prop 2.6].
To prove ((S)[P] & infre ([S) @ +) consider < k(S) and any T E (P)
We have
T(Y, hz
By (BI (Y, (s 2ssl) = By (T(Ys)(..(Yss) = 0, (8)
since CR.s = 0. To prove (PS) > infTeL (Td; @ Ty) # P) consider T (GK(S).))
where 3 is multiindex such that (Su(s),s)s + 0 (this B must exist by definition of k(5)). We verify that
(T(Y)Ha(2))
= =Ey [ = =Ey [I({(())s)) (F) 0,
(9)
(10)
which shows that (u(S),s # 0 for the model with label transformation T.
Proof of Proposition Consider the flag F {0, S, 1....., S, TR' associated with the leap information exponent. We claim that k(S,, S)+1) ((5)) for all [J]. or equivalently that
span (Sa(())))))) C (Aan())(S,))
for h < I($)). Indeed, observe that ČR.s = Ev Ev (e,s). As a consequence, from Proposition | we have that k- S max, I(S)) = 1
C Proofs of Section 3
Proof of Theorem 7 Let Rwy ==
Fi
denote the likelihood ratio conditioned on W. We begin by aPo
computing the full likelihood ratio:
E W
I| i= Pw [2.,
vill
Rw (0 v
(((1118)),... (Zn, vn))
EE II PP P|c,|||ys
Then by Lemma] 1 we can expand this
R E
II
Σ (C)())) ha (W 2:))
We will isolate the low degree part with respect to { F.), which we denote by R&D. To compute this, we need to switch the product and the summation:
I (Sx, (7.), b (W Ta.)) ]
R = Ew
Σ
Σ
p=0
21

---

We note that each term on the right hand side is polynomial in T1,.... En of degree which is orthogonal all polynomials of degree less than p. Therefore Rgn given by:
Rg W
Σ Σ
(A. be (W zz))
p=o + mp
We can now use the orthogonality property of Hermite polynomials compute the norms with respect to the null distribution Po. If if W, W' are independent draws from the prior on W then:
A W=l
||Rgoll = Ew w
Σ
Σ
Er (5x) 60 Ck. (T:), ba, (W T.) 80 ha, (WW) Tz)))
p k1 +... tha=p
Σ
Σ
E
I EiCc. @ Ss,l (WTx)) @ hy ((W) ((('))))))))))))))))))))
= -E w
p=u Rq th, mp
For pair 2; E of operators where 2 is PSD, observe that
122, >> s T+22H//Elopp
thus
D
2 B hs. (W T T.) @ ha, (WW) =.i1l) ((7)=>)))))
R ( S Ew. w
Σ
Σ
II
p=0
Now, let M = WTTW E Rexr, We have the following control the Hermite correlation term: Lemma 5.
Biha (W 2) @ (=W" 2)
|| l1.p
(11)
Let z be random variable with distribution || WI], where W, W are drawn independently from the uniform prior on W, and let P&D be the projection operator onto polynomials of degree at most D in z. Note that is subgaussian satisfying P
(b 1 S S a < c,b e aa/ /1 for
explicit constants Cr, Cri see eg [Bietti et al. 2025 Lemma 3.14]. Then we can upper bound the above expression as:
I I Eg
P&D
k20
By linearity of expectation and of the projection operator P.DDD we can expand this using the binomial theorem:
R
R
Σ
E
Pen
12
120
We can further upper bound this expression by using that A2 S (r+b-1) (Lemma 14). Plugging this in for & 2 ks gives:
[D
|RRD - -
Σ
Y1
E2
PSD
Σ 1 1
j=1
[D/K*]
Σ
P&D ( zi2²" (1 2) -ir]
24
E2
(k+)((r-1)
B (2(25k1)
i
22

---

where the last line follows from Lemma 6 Finally, since 2 is ol we have
B| x /d)ik
Now, if n = (d with y > 0 and D = =[(log d) we have
[D/k"]
|RgD - -1
Σ
n1
(iK 12]
==1
S n DIk k-(r-1)D/k (D/d)o/2
- (D)0/(n)//
=1()
Proof of Lemma 5 Let M qddxxd" be the matrix representation (W @ hwW' x)].
Let Hx C (RR 7) be the space spanned by harmonics of degree k. Observe that for f. He. 1 caho. 2 Eahi with cg = (f. Eo = (f, h2) we have
c Mè = (Pw f. Pwi frra
(12)
where f() = [(WT()]))))) x). We deduce that M is the "averaging operator' AM from
Bietti et al.
2025
Definition 1. restricted at harmonic k. From the SVD of M U UAVT, T, we have Bietti et
2025
Corollary 2.8] that
M
Σ HH)(UU) & Hz(V), 1
(13)
with 0 = -I1, > We thus conclude that || Amax ||M]
Lemma 6. Let WWTTWlle where W, W are drawn iid from the Haar measure of S(r, d).
Then, 1, d/4, we have
Eg F - 2) S E 12
(14)
Proof. The proof adapted from [Damian al. 2023 Lemma 26) the r > 1 setting. From Biett
et al. 2025 Eq (197)1, the joint distribution of singular values 0 I X, I \ S A1 of M is
given by
Pr.d Pr.a(A1,..... ,r) Z
II
X3 II x2) 22) S dr ... s.. S1), (15)
<<j
(2(r/2) r. (r((-r)/2)
with
Zr,
We have
1/2/2
T-(d/2)
E 22 2) / 21(11-1)) A1) -1) ..., Ar)dd
(1(1-11)
.)).prd( ...dddddd dd,
(16)
From A < we have - x9 2(1
- A1) so (1- < 2((1 23) thus
E (1 2)-r) 2² / 11(1 - --) Pr.((d ddr
(17)
/ X (A II - (2 ....
2 1
\ S 1)dX; ... ..d
rdd
(18)
Z 2-2 B3 2
(19)
Znd
where & is the largest singular value of M = WTW with W, W'w's E S(r, 21). For d > 1, we
thus conclude that E (z'(1 - -=)- $ E2(=')
23

---

D Proofs of Section 4
C.. C(P, independent Lemma 3. K is integrally strictly positive definite 2 there exist c(P, K), of d such that if (U*)* span [p]n[Ag] denotes the subspace corresponding to the next leap then
(P,K)Ts EU,, 3 (C(P,K)
Proof. Let be the kernel operator:
(KF)))) = By ( 8)
Using that (X)]x, o88) (Y), ) where U 18, we have that for any us
U EM,, u Maa K(Y,Y))u
(-u,,, (CCx
First, because K(y.v) v) s we have that || lop this is upper bounded by
Ey (Y) = A ||u||
Therefore M.M 3 C(P, K)Tls with C(P, K) = 2 Next, let E S with |||||| 1 so that [x f 40 E (P)),). Then because K is injective we have that
c(u) = KCG > O.
Therefore by compactness, if C(P, K) denotes the minimum value of c(v) over the unit vectors in S, we have that C(P,, K) > In addition we have that E M, 2 C(P, Kills which completes the proof.
Theorem 2 (Concentration of U-Statistic). Let K be PSD kernel with K(y.y) S for all y. Then n Zs db/2//e + dr /e², we have that ||U, - IE Unllop S e with probability at least 1 - exp(-dd) for an absolute constant > O.
Proof. The cases 1,2 are deffered to Proposition 8 so we will assume that k > 2. Note that by the standard decoupling argument (fde la Peña and Giné 1999 Theorem 3.4.1J), it suffices control the tails of the decoupled Utstaiistic:
Mn = n(n - 1)
Σ (Zx))(xx))"K( (t)
where {(16, v/ are an i.i.d. copy of (( HE We will begin by applying Corollary 3 with respect to the randomness in {(x,, u) 1 treating the replicas {00 1/ as fixed. Define
V(())
Σ
(at))((Y.))
so that
Mn Σ
(T) 1 -
Σ 2.
where Z, (w.) Then:
| 1
(o(x)"eu en, (((Y))=o))? abb=1
"e say that K is integrally strictly positive definite for all finite non zoro signed Borel measures μ. K (z, y)dz(r)duuy)) > 0. We remark that many commonly used kernels, including the RBF and Laplacian kernels, satisfy this assumption (Sriperumbudur al. 2010
24

---

Taking 2/2 norms and using Lemma 9 gives for 2 r rogg::
2
op
p/2
Σ
(0()) V1( ((
a,b=1
Σ |K0(X) Ea, ea)
a,b=1
Sk
To0ll
n.b=l
S p d2 (X) 1
Next we will compute o- (Z,):
(Z,)²
sup M| ||||=
E [ u, V()
u)²
S*
[1 1op
by the same argument as above. Therefore applying Corollary for S d".
gives that if
k-2 2(h+4)
then
Now let E' denote the expectation with respect to the replicas &1110
|IM. E Ma
$
d
2p
{(1 V Then by Corollary
E |1130000000 1/p d
(E' B UIU EUl 1/0 x sup
(By E' (V)())))
2p
2
d
sup
V
71
Now decompose:
[V) < + -V(()))
Because K(Y, S 1, we can use Lemma 8 and standard symmetrization argument to show that the second term has p-norms bounded by O (mmxxx, dk-xxd for d", For the first term have
op E' V S (VV(())) F = |Ey, (XY)) S Ey (Ilss s k/2,
Combining everything and applying Markov's inequality gives that with probability least 1 poly(n)e "
IU E EUllopp & ,//2 + max(d, dk-1)
d
dk/2
d
V
k/2
n
Proposition 8. 1fk: < 2 and n 2 d, we have with probability at least 1 2ne
d
U
EU S 7 k/2
Proof. We can use de la Peña and Gine 1999
Theorem 3.4.1] to reduce the problem to concentrating:
M, n(n
Droyy I
K(ys. V/).
1)
25

---

where D U/ are an i.d. copy of D (1))- If we define Vi(y) =
1 n- E jzl 0 K (y, Vfy, we can rewrite this as:
Mn - ViV((())
- Σ
Now let R be a truncation radius to be chosen later and let pi := 1 [| SR Then define:
Mr = Σ h2 h2
First, we have that for any unit vectors u, v and any p 2 r2,
x2) Ep [(u o, (Z 1/8 (2p (2p 1) + 2p)
(*+22))
Epi(u V((us) & Rp.
Therefore the summands in x² M, u are subexponential by Bernstein's 's inequality we have that with probability at least - 8 over the randomness in D
log(2/0) log(2/6) &
MM, E M.Iu
"
7
We now union bound over 1/4-net of S
to get that with probability at least 1 8 over D,
|Mtn - E EMA S R
+ log(2/6)
d log(6/))
n
Taking 5 e-d and using n 2 d gives that with probability least e-od
d
Mn - ME <
Next, note that for any fixed unit vectors u, v (possibly degenerate if = 1), x² o''d'KK (y, v/)) is -ub-eexpnential random variable by Bernstein's 's inequality we have with probability at least 1 5 over the randomness in {(1/1 v6)).
log (2/5) log(2/0)
I T -V EV(()))
Taking union bound over 1/4-net of s gives that with probability at least 1 ō over the randomness in D',
(v) - - (V $ + log(2/0) d + log(2/0)
In addition, as in the proof of Theorem we have that ||E Vi < A/2 Therefore if we take R = C2//2 for a sufficiently large constant C, we have that with probability at least 1 - e-ed that [VV(())) < R. Therefore with probability at least 1 - ne-od M Mn Furthermore, if ne > 0 so that the theorem is not vacuous,
E MM
E Mr
V
T Oe Ve (y:))) (1)-
Σ
[uT T di
V V' Σ
P(IV 2 R)
(Cauchy)
11
k/2
k/2
(ne-od -ed <))
Vn
26

---

Putting everything together gives that with probability at least
2ne od
M MaMllopp & k/2
Lemma 4. If the kernel K L-Lipschitz, then there exists a constant C(P, K) such that the map S + E EUA) (8) is C(P, K) L-Lipschitz in operator norm.
Proof. Let Z(Y; x): (1 X Then,
- EU || = ||x XX;
| -
where
B(Y,X)= = K(I, Xs), ((), (((Y)s));; ('ss))
Note that
X(Y,X) S LV IXs 11 + 1|X's X 12 s 2d(S, S max XII (I-)))
Then by Holder's inequality,
(S) BU/ S <11IZ(Y:
: x x| [[E(,
23rr R VFLd(S,S")
Sx per++ILd( Ld(S,S).
Theorem 3 (Main Result). For any multi-indee indexx model P, there exists a constant C(P, K) independent -" /2 + $ then the output S =R of Algorithm satisfies
of d such that if n 2 C(P, K) d(S, TT) S e with probability at least exp(-dd) ) some c = c(k') > 0.
Proof. Recall the leap decomposition J (0- S S Sj ç.. = We will prove by
induction that for any > 0, there exists a constant C(P, K) such that the output S, of Algorithm at step i satisfies d(S,, (U+)²' ()) with high probability whenever
2/2
n N C(P, K)
2
Note that for i the result is implied directly by Corollary Lemma 3
Now assume the result for > By
EU 55 2 c(P, K
K)
In addition we have by Theorem 2
Sx db/2
n - EU(Si)
+ p k/2
Finally by Lemma 4
EUS EU
Se rktl x d(S;, ST).
Putting it all together we have that:
(1sa) -BU!" So d²/2 + 4/2
d + + 1 x L x d(S,, (t)) V n
n
In addition, by the induction hypothesis, d(S,, (U+)T 5t) < C(P, K)
1//2 +
Therefore,
(ل - -UU
Sa C(P, K)
dt/2
d k/2
71
and the result again follows from the Kahis-Kahan inequality.
27

---

D.1 Auxiliary Lemmas for Concentration
We will start with this simple inequality on the Frobenius norm of Hermite tensor:
Lemma 7. (X)ll S& || + dk/4.
Proof.
We will use the identity:
hx(X)= = Vkl
Therefore,
h1x(()1
[(X +iZ). (X + +
kd
Rz.z2
(11x1)² - 7. 7 +ix (Z + 2*)
K-
3/-1
||Ix| + -Z 112 211²] Ez,z' ||X (Z =²
k!
SA
|| 122h
d= + ||
Sx X| 2k + 1222
We can use this to concentrate sums of Σx= ccb(2)) in operator norm:
Lemma 8. There exists an absolute constant C₃ such that if d' with > 0 and for any constants O with |cal S and p d' where e/4))
1/P
72
max (1xx(ddd--1)
E
Σ
S C.V
n
71
Proof. Note that for & = 2, this follows from the standard bounds for a Gaussian covariance matrix (k = 2) and norm of a Gaussian vector (k: = 1). Therefore we will assume k: > 2. We will begin by computing a. (Ø):
(Ø)
Ei(u² Φv) = E (voo[he((X),, vecfu @ v)}² < 1. ||||=||||||=
sup
Next, 11pllop S || Sx ||-||* + d/4 Therefore the p-norms of [lóllop are bounded by d for any p S d. Plugging this into Lemma 12 gives that for p S d,
-
////2
1/3 k-
1/3
/bppp
c(d(1;)
p
2/3
n
n
72
72
n
lpppp
Plugging in p de gives that the second and third terms are dominated by the first which completes the proof.
We will also use the following simple lemma:
Lemma 9. Let (X, Y) follow a Gaussian multi-ine index model with hidden dimension Then for any
k-tensor-valued random variable F(Y),
(1), s (2p (2p-11 1)
("+
(r
kp I1)
r
Proof. Without loss of generality can assume p even. Now f(Y)) polynomial of degree kp in X. Therefore by Lemma 15
f(Y))*
(+++ kp) S (2p 1) v ((++ Ey )
(r+
(X), s / Eo ((L())))(())) 2(Y))
r
28

---

Taking pth roots gives:
[X)x(X (2p 1) (r+ kp
(p+ 5 11I) || 1lpp
Lemma 10 (Gaussian hypercontracttiitty). Let f be a polynomial of degree k and let X Ia). Then for p 2 2.
ExI1 S (p- -
Lemma 11. Let X, Y be random variables with || S Bp for
|
))
== mimin
2, log
Then,
E X s [X]I B (ep)*/2.
For any mean zero random matrix Y we define:
oYY) == max (||E|YY || 1|B T (111)) 1/2
(Y( |||||=|||||=
sup
E[(u Yu)
For non-centered matrices, we define (YY o EY) and a. (Y) = o. RY).
We will rely on the following simple corollary of [Brailovskaya and van Handel 2024 Theorem 2.6]: Lemma 12. Let = Ei= Z; where Z, are mean zero independent random matrices. Assume that for all i, P[||z R] S Then there exists an absolute constant C such that for any 2 with probability at least nd- de
||||| s c(o(M) oY)())1 R²/3 (1) Rt
Proof. Define 2, = Z,112 SR and let = Ei 7, Then,
a(Y) o() 12
oYY
and similarly for a.. In addition, by definition,
< R. Therefore, by BBailovskaya and van
Handel 2024 Theorem 2.6] and [Bandeira et al. that for any 2 0, with probability at least 1 de
2023
Lemma 4.10], there exists a constant such
> -Y-EÝ EÝ
s c((()) +o.)))) + 12 (Y)22/33333 + Rd
Next, note that
EY - -EY
Σ 1 12, n
S
op
Now if 8 > 1/n, then - nă < 0 so the result is trivially true. Otherwise, |EY - EyI S (Y).
Finally, Y = Y on the event that max; | < R, union bound completes the proof.
We will use the following simple lemmas about .T.:
Lemma 13. For any random matrix A I aAA)² max(d, s).
29

---

Proof. Without loss of generality we can assume E[A] = O. Expanding the definition gives:
oAA)² max (| [[AA ]| [AA[AT]]]]]
First,
||[[A]]]||
sup Blu AA b] = sup E
|| m1 - sup
E [ee A oTT) S so, (A)?.
|
|||||=1
|
==1
S do (A)2. Combining Performing the same calculation for A in place of gives that E EE these inqqualities gives the desired result.
Corollary 3. Let Y x -ニ Zi where Z, E Rdxd are mean zero independent random matrices.
Assume that for some R, k, Zilpop I <Rth/2 with probability at least - - for all t 2 0. Then if
t with > 0 and = min(1, (1, R41). then for all S d.
1/p
R CCmax (.)
d
E
[
d n
where C. an absolute constant.
Proof. First by union bound, we have that max, 112l S Rt with probability at least 1 ne
Substituting this and Lemma 13 into Lemma 12 gives that with probability at least 1 - 2ne
|| < C' max (o.(Z),
R d d+t +
dt//2
1/3
d
1/3
dt $ +1
7
2/3 +
We can factorize this by pulling out the vd/n and using n 2
dl
|| Cax (o.(2))
R
d
11/2
6
1
+
d
n
d1/2
d8
n1
We convert this an p-norm bound for p 2 log
Bijl||i < CC max (z), R
d
11/2
p 6
p2+1
1
+
d1/2
dé
n2
Now if d' where min(1, ) then the error terms all less than 1 so we are done.
Lemma 14. For any p 2 2, [Y) < (p 1)- S (0p 1)r)*.
Proof. By Jensen's inequality and Gaussian hypercontractivity we have
[||[(Hee =1
$ (p E (Z)
r k: - 1 k
= (p - 1>*
Dividing by k! to revert to the normalized Hermite polynomials {h₂} completes the proof.
We will now bound the low-degree density ratio between the joint distribution of (X, Y) and the null distribution Po : Px & Py:
Lemma 15. Let Fo == Fx @ Py be the null distribution and let PgD denote the orthogonal
projection onto polynomials in X of degree at most D. Then:
dPP
PSD D
X Y
Σ
dPo
k=O
and
dP
rr+ D
PSD
dPP
r
30

---

Proof. Note that the density ratio is invariant to X conditioned on Z so we can Hermite expand directly in Z:
dP X 1. Y =B -B(hx()) (x(Y)
Eg
(Z)
dFo
which implies that the Hermite coefficients of dPo in Z are given by SA- For the second equality, we have by Lemma
14
dP
D Σ
r r -
k 1) ( ("b))
PDD
E [Y)
dP
E Proofs of Section S
Proof of Proposition
We write y = (z) denote the deterministic link functions above.
Let = (<)
+1}. Let k < r and consider (z))= S] 2 (1) S)J. Any coordinate of this tensor corresponds to multivariate Hermite polynomial ha (2) (2.))...bp h.....hg,.. (g, (z,), with $1 +.... + 8 k. Since < r, there must exist a coordinate s.t. By O. By noting that Es3 1(2 E S) = 1 and E [hg, (=1) hg, (z+)] O, conclude that E(h, we easily verify that (l ... 2,] 0, which shows that 1 and hence k
S)] = 0 whenever ie < and analogously for I"' \ S. Finally,
2. This follows directly from k* <t.
3. Define K the intersection of the half-spaces, determined by normals w1,.... UM- From the assumption that is a r-dimensional multi-index model, V = [on... [w]] has rank r. Any unit norm vector
e >>> 0 for some e > Let Σg [2 2 K] E[z|2 K E[2 K] be the covariance conditional on K. From Klivans et al. 2024, Lemma B1], [Vempala 2010 Lemma 4.7], for any u as above
span(V) thus satisfies max, |2
holds that Σxu which implies that span
span(A²) R".
4. The argument appears already in Chen and Mcka 2020). but reproduce it here in language for completeness.
We will use induction over the leaps. Suppose first S = 0. and consider the level sets BA {2: ly| 2 A}. Since y = (z)) is continuous and lim (o(2) 3o for any 2, for any R > 0 there exists À such that Bx does not contain the ball centered at 0 of radius R.
Thus
Tr(E|ZZ T Z E Bx)) = E[] Z Bx) R²
so if 12 > we must have E[h2(2)|Z E Bx] A O. and hence A2 + 0.
Let now iterate over leaps. Let S' be the span of A2. We now consider the sets
Bx., (ās: lvl 2 X, ||= S n) C-
By now viewing (=2) ogg, 28) as a polynomial in ăg, we again argue that for any R > there exists À such that Bx,y.s does not contain ball of radius R. and therefore can identify another direction using the previous argument. Iterating this procedure until S spans the whole H' shows that A* 2.
Proof of Proposition Suppose towards contradiction that k* > 2. Then for any g E L3, we have (2)(o()))22(2)) = 0. Applying the coarea formula obtain
0 =f0l1) g(v)) (1
h (2(2)((z) dH ( dy [[o())]
(20)
31

---

where 7tth is the k-dimensional Hausdorff measure. Since this must be true for any measurable g. we conclude that
h2(=)((z) I(y) = [ (o-1(w) [[oo d7' (z) = 0 -a- a.e.
(21)
We write (2) = > RER (uA= + bR) 1(2 E R), where R are the different linear regions.
Case r = 1: Suppose first that there exists y and e > such that the level sets o -(() contain no y + e). The level sets o o (u) are discrete, and we claim that we can
critical points for represent them as
(u) (4 + 0.(u - 7)} where o (g) {4))EI, and 0, 1/4) + have alternating sign. We thus have, for u E (ū 6, + e),
L(u)= Σ
10:|ha(4 + 0,(u 7)) + 0;(u 5))
(22)
SEZ
Let us integrate this quantity twice now. Using the fact that (hg- h we have
[(u)= =
L(v)dv
(23)
g-
+0,(u - 0))x(t + +C,
(24)
iET
[(u)= =
L(v)du
(25)
g-
Σ sign (1: (0:)0, (yt + 0,(u - 0) +
(26)
TET
10.1 10.1-1 (t, + 0.(u - 0) + C(u - +)) +
(27)
TEI
From L(u)= = 0 a.c. on (g + E) we have [(u) = 0 for all u E (y = c). leading to
Σ (t.1- + 0, 7) C(uu - 7 +) C, Vue (j
(28)
Since all terms analytic, must have this equality for all u, which implies C Ō 0, but this is a contradiction, since the LHS is a sum of positive terms.
Case >>> We can represent piece-wise linear continuous function in terms of simplex triangulation, and the values of the function at its vertices. Consider M sup, {a(()} the maximum of a. attained at discrete set of global maxima. Now, let us start decreasing the level set until we reach another vertex, to say M', We will study the family of level sets o (g) for E [M', M.. We reparametrize y as y = M u(M' M). this family can now be indexed with a E [0. 1].
For 0 E g and E IR, let E t) {z; 0 t denote hyperplane normal to 0 and passing at distance to the origin. We can then write
( @
where Sp( E(ve //lll, ||v lu + bR) n R. and where R the subset of linear regions crossed by these level sets. Note that by construction this family R does not depend on u.
For (e, 1 e). e). and for each R R. we have the following homotecy representation of the level set regions:
SR(u)= = {a = In + u(2 - IR); 2 E Sx(1)}
(29)
Here, R denotes a local maximum of a, which also a vertex of the corresponding simplex region R. Consider now L(u)= [r][)u)). By introducing the local change of variables E v (2) ==
32

---

+ u(z - FR) for each region, we have
[(u)
Σ
On
(1|=1 - (r)r(2)d
(30)
Sn(w)
RER
w'
Σ R
OR
(1|ER + uuzz =xR)]l² - -r) 7(IR + u(z - TR))dz,
(31)
(x(1)
where 0R = [[Vo[2)]]| for E R. Observe that is analytic in R, since it is linear combination of products of analytic functions. By assumption we have that [(u) 0 for E (0, (),1), which implies that L should vanish everywhere. But for sufficiently large, observe that L(u) is a sum of strictly positive terms, which a contradiction.
This shows that A₂ # O. Let 5 = span(A2), and write : = (2g, 3), y (2s, y). We can now again suppose towards contradiction that for any g E L2((p)) we have E[g(o as =s) = 0. Defining
( { (25, 2) y) applying again the coarea formula leads to
(2(3)(() dH 1 = Pg a.c.
Ls Lū
(32)
( (E)|
The piece-wise linear, continuous structure is still preserved in o, and therefore by iteratively applying the previous argument shows that all directions will be captured with generative leaps of at most
k* < 2.
Proof of Proposition 7 Let (z) = Ej azp(zz). By definition, we have that (i) for any T R TR and any polynomial q of degree < k- (p),,, B[T (M(((((()))))) = 0, and (ii) there exist transformation
(ly) such that (h
Let first show that k- 2 (p). Suppose towards contradiction that we had measurable U and multi-indices (Bi...., with |3] < k* (p) such that [[) # 0. Then, denoting
Hz(²) = Ho (2-1) (2z), we have
ENg R ( hap (z # 0
(33)
Ex, E Ex
U
aglli Σ Caypley) j'サj
h3 (2z)
40
(34)
[w: (2z)
#0,
(35)
where we defined the label transformation T0()) = E. [(a, By We have thus reached contradiction. Observe that the same argument also applies if one replaces (=)) by (()) = F(p(()) ) for arbitrary F.
Let us now show k* < (p) == k* We focus Hermite moment along single variable, say Z1. given by hag (=,)..)))))))))))) Let y Let find a measurable function 2 such that
p(21) and 17 = aj' Σ,>1 azp(2z). y and are independent. We will
Exy [(((zz) + 1)) (=1) + O.
(36)
We will consider a Fourier atom for V/ of the form U(I) eift for an appropriately chosen frequency
For that purpose, let us first reproduce an argument from Damian al. 2024 Theorem 5.2]. By
DDamian et al. 2024, Lemma F.2] there exists R -> [-1, such that E gg( Tha (Z)] # 0. We
consider TR(y) := g(y)1 visa. For It sufficiently large, we claim that BE C[gR (Y hig- (2) # 0. We
have that
BlgR(Y) (Y) (2) hL (2)]1 = |ig (Y) (2)
S E[g(Y))2h (Z) R
< E[Y
(37)
33

---

which vanishes as R + oo. Therefore for sufficiently large R we have EY (Y) }b (2) * 0. Now OR E (R) (2). Let us consider its Fourier representation 9R = f gR dgd.. Then
EYgn(Y)) (Z)) - 9r((E) BlekkY hg- (Z)]dE
(38)
which shows that there must exist Eo such that Eple hgs (2)] * 0. Moreover, observe that E + Ep (e hg- (Z)] := (t) is |lell since
(e Eiiye K hg (Z)ll S VE[YT < 2| |Iell?
(39)
so we can define > 0 and 8 > 0 such that (x(E)) 2 á for all & E (Eo Eo + e).
Now, let evaluate 366 with the Fourier atom. We have
Ean [((pzz)) + (0))==((11)) Ex,, ((llo(z)) ho [21)]
(40)
Ezz (e (21) B Bypleken)
(41)
(E) (p)())
(42)
where (5) = E, E is the characteristic function of Assume, towards contradiction, that (E) for all & E (Eo - c, + e). By definition, we have that (c)(E) [[ a1 ((()) E[e(éo(=)] is the characteristic function of p(z). We thus deduce that pP(E) must vanish on an interval & I S (Eu Eu + c). Since all the moments Bly"1 exist by assumption, this means that
az vp( () {). where
AE I, m EN 0 0= (m)) Ep, (e
(43)
In particular, given any f E (P()))). with expansion f(v) = Ex (n) where (gehs is an orthonormal basis of polynomials, we deduce from (43) that ([f(y)e**] 0 for any S. which would mean that e = in (P which is a contradiction. We have thus shown that there must exist É E (Eu - Eu + <) where both (ε)( and v5)) are non-zero, proving (3)..
This shows that [A * O. Applying the same reasoning to 2j. [r] thus shows that [Ak+ * 0. On the other hand, if we consider B with [3| = k= but 3 not of the form 3 = (0,.., ktt ........ 0), applying again (3) shows that [A O, ie Ak is diagonal. We conclude that span(Ax=) = R'
and thus that k+ < (p).
Lemma 16 (Truncated and Fourier Label Transformations [Damian et al. 2024 Theorem 5.2]). Let P P P(R x IR) with P= = and let k* = k** (P). Then there exists Ry, Eo. Eo > and 8 > 0, and label transformations Ta. Te of the form Tu(2) + SR and Te (v( dıt such that
|Ep (TR(Y)) (Z)] 2 80 and Ep Te(Y))xx (2) 2 80
for R Ro and I6 - Eol S ED.
As the Shallow NN becomes more overparametrised (and thus less well-conditioned), the generative leap is no longer 'related' to k (p). Indeed, provided p is not a polynomial, we can use the shallow NN to approximate any desired link function ē with prescribed generative leap exponent. Since the generative exponent is characterized as the first non-zero of an expansion, k (ō)) < is an open property, meaning it is stable to small perturbations of ō. This directly leads to the following:
Proposition 9 (Generative Leap under Universal Approximation). For any non-polynomial p and any integer 2 1, there exisis shallow neural network of the form y Σ d,p(o] + bj) such that (Z, Y) P has generative leap exponent ks (P) e.
Proof of Proposition 9
By Proposition] 7
we can reduce ourselves to the univariate case. We first 0 such that if
verify that, given R
IR, there exists
||o H م|ا S
(44)
34

---

then (ō) - (0) =
sinusoid label transformation Φ(y) cos(Ey) for & that depends on such that [6 (2))) (z)] = C #
From Lemma 16
It suffices to verify that E[)(ō(z))kx Mx (z)] * O. Let a(z) o(z) 5(2). Indeed, since ø is E-Lipschitz, we have
v2 ((ō(z)) o(o(=)) a(=),
(45)
with [(x)] S Ela(z)) Thus
[lo( (+)] E[((a(2))) (=)]] = [z( (2]]l ||ا|| S E||||||2 = Ello ع||2
(46)
(47)
so i C/ we have (ō) S (a).
Finally, using standard universal approximation theorem, e.g using the integral representation
a<)) cp(az b)dv(a, b, (co.ber=/lpp(az + b)]
(48)
for v E P(RR)), we can obtain ā satisfying (4 by doing a Monte-Carlo approximation.
Proposition (Generative Leap under linear transformations), Leto(z): + =RE) and let M, denote the set of r real matrices.
(i) For E Mr, define ye = (o(T2)) 2). Then (z, ye) ~ Pe satisfies ks (Pe) S 2or every O except possibly for set o dimeensiin Lebesgue measure zero,
(it) Assume that (z))(zz) P has single leap with generative exponent k*. Let D C TR. > MM be any analytic map such that I, E Im(T) and [(0) is invertible for all D. For 0 E D, define ye o (T z). Then (z, yo) ~ P9 satisfies (Pa) S k- for every
except possibly for set of s-dimensional Lebesgue measure zero.
Proof. We will again exploit analytic properties. Let first prove (i).
Let us consider a threshold function of the form Tςy) = 1(a1 S y S a2), and its associated level set Ω {2; a1 I (2) < a2 Suppose first that we have f2 C (R).) the ball radius R, for some R > 0.
pick 01, 02 such that Q is compact. Then
For M E "R" consider the function
((M) == det [M M
(L/ 22 M Ma MMM MT OOT((/
Ms dz }1
(49)
Let us now consider Σ 0T0 VA and 2 N0, E). Observe that if θ invertible and ( / 0, then
det (ct((A((P)) det [B[(2z TYT(
det
[B[(zz - T) E [)]]
det
( -E2(22 1(2 - @N]]r
det(O]" det ( (/ z2 T dz (1
--
-
- dz I
(50)
showing that det[[A((P))] 0. and thus k-t (Po) 2.
Let us now argue that d is analytic in Tr Indeed, the determinant is analytic, and composi- tions preserve the analytic property, it suffices to check that the functions M + (M(M)
35

---

Jn = Mr Ma dz and M + (s( = So Zizze $= M Mada are analytic. Since f2 is compact, we have that
(M) S R R
(51)
for any multi-index B, and analogously for the terms Φb.
Now, observe that (0) (Jn dz)" * O, which implies that ø cannot be identically zero. From Mityagin 2015 we then deduce that ø can only vanish on a set measure O.
Let us now extend this argument to the setting where Ω is not compact. For any > 0, we claim that ((M) is analytic S = (M E IR"x;; Amin (M) 2 eJ. Indeed, now & is infinitely differentiable in S, and its components @a. Φb satisfy
0 Φ 0M5
(M)
2 | 1 -101-,
(52)
and similarly for ob. Since now have <(0) oc, for small enough we must have ((M) o 0 for some M E S, which implies again that Φ cannot be identically zero. It can therefore only vanish on set of measure
inside S, for any 0.
Let us now prove part (ii) by adapting the previous argument. Since here we are assuming a single leap, there exists a tensor-valued label transformation (RR, (RR))k" Pyy such that det F F] # where
F = Mal
(53)
For θ E Rrxr let now define
v(+) == det [F())F(O)*] with
(54)
F(O)= = (1)+- [o Z)) ())0))))))))---)) (2)!
(55)
Using again Σ = - = VARVT and 7 ~ NV( E), we can rewrite this last expectation
F(O) -at,,
E Ez(T(a(2))hb- (0-
(56)
-1 ( | (( (0- (0- 3= (o 's dz
(57)
We argue again that F(O) is analytic in the domain (0:Σ > cT,} for any since it is linear combination products of analytic functions. This implies that (() is also analytic in this domain. Finally, since the parametrization 8 + r(0) is analytic by assumption, also analytic. We know that & is not identically zero, therefore we conclude that it can only vanish on of s-dimensional Lebesgue measure zero
deduce that & & o I is
36


Reviews:
[{"review_id": "WJzBrrb8Nl", "reviewer": "Reviewer_s6Px", "summary": "The paper considers multi-index models with Gaussian inputs in high dimensions and a finite number of indices. For this model, the authors show that one can estimate the hidden subspaces in the model with a sample complexity $n = \\Theta(d^{1\\lor k^*/2})$, where $k^*$, the generative leap, depends on the model. This is a necessary and sufficient condition.", "questions": "1. In 4.2 you discussed a fine-grained analysis, in the sense of finding the minimal constant $\\lim_{n,d\\to\\infty} n/d^{1\\lor k^*/2}$ such that the hidden subspaces can be recovered. In particular you state that the dependance on the number of indices can be exponentially bad. Can you provide a more comprehensive classification?\n2. In 5.3 you state that while shallow networks have a generative leap at least as large as the generative exponent, wider networks might not have this bound. Is there a practical example of this with some activations?\n3. Is there some way to salvage any of this theory in the case of $r = \\Theta(d)$ indices?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is detailed, clear and extremely well written. The proofs are clear, and the technique is interesting, although similar in essence to the one for generative exponents. The main contribution of this paper, the description of the generative leap, is a fundamental contribution to the field and will surely have a big impact in the theory community. As the authors correctly state, most cases of practical interest have generative exponent less then or equal to 2, which were already studied in several previous works, so its fundamental limitation lies in the limited applicability of the results.", "was_revised": true, "final_justification": "I believe this to be an incredibly solid paper. My doubts were cleared by the rebuttal and I happily raised my score to full acceptance.", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and address each point below.\n\n> In 4.2 you discussed a fine-grained analysis, in the sense of finding the minimal constant $\\lim_{n,d\\to\\infty} n/d^{1\\lor k^*/2}$ such that the hidden subspaces can be recovered. In particular you state that the dependance on the number of indices can be exponentially bad. Can you provide a more comprehensive classification?\n\nThe tight constant will depend significantly on whether or not the learner has knowledge of the link function. For example, when $k^\\star \\le 2$, [Troiani et al. 2024] computed the tight constants for AMP, and we believe it is likely that a more careful low-degree polynomial lower bound would match these constants. Tight constants do not generally exist for $k^\\star > 2$ since runtime and sample complexity can be continuously traded off. However, we can compute the exact weak-recovery threshold for our matrix U-statistic estimator when the optimal label transformation $\\zeta_k$ is used. For Gaussian $k$-parity, this constant is:\n$$\nn \\ge C_k d^{k/2} \\quad\\text{where}\\quad C_k = \\left(\\frac{\\pi}{2}\\right)^k \\cdot \\frac{1}{\\sqrt{(k-1)!}}\n$$\nwhich scales like $(\\pi^2 e/k)^{\\frac{k}{2}}$. In particular, for Gaussian $k$-parity, this constant is exponentially small in $r=k$.\n\nMore generally when the learner does not have knowledge of the link function, the constants (and $r$ dependencies) will generally be worse, and the constants will depend on the prior over link functions.\n\n> In 5.3 you state that while shallow networks have a generative leap at least as large as the generative exponent, wider networks might not have this bound. Is there a practical example of this with some activations?\n\nThe key difference between Proposition 6 and Proposition 7 is that the weights are restricted to be orthogonal in Proposition 6. In addition, we apologize for a typo in Proposition 7 which we have fixed in a revision – the corrected statement is that for any non-polynomial $\\rho$ and integer $C \\in [1,k^\\star(\\rho)]$, there exists a shallow neural network with $k^\\star \\le C$.\n\n> Is there some way to salvage any of this theory in the case of $r = \\Theta(d)$ indices?\n\nOur paper is focused on the setting in which $r = O(1)$ and $d \\to \\infty$. When $r = \\Theta(d)$, the function is in a sense \"generic\" since it can depend on almost all of the coordinates, and getting learning guarantees in this setting would require imposing additional assumptions on $y = f^\\star(x)$. However, it may be possible to salvage the theory when $r = d^{\\alpha}$ for some $\\alpha < 1$. This would require developing more fine-grained estimates of the $r$-dependencies in both our upper and lower bounds. For $k^\\star = 1,2$ the tight constants (assuming knowledge of the link function) were computed in [Troiani et al. 2024], however we leave extending this to larger $k^\\star$ to future work."}, {"review_id": "tSSMKMbbdt", "reviewer": "Reviewer_buZ9", "summary": "The authors investigated the computationally optimal sample complexities to learn the intrinsic features of multi-index models.\n\nThe authors first generalized the generative exponent (from single index models) to generative leap exponent $k^\\star$ with leap decomposition, which relates to the nested easy-to-hard subspace structure & leap exponent. \n\nThen they characterized the hardness of learning a multi-index models by proving that a sample complexity of $\\Omega(d^{k^\\star/2} )$ is essential for the low-degree polynomial test to have non-trivial power in detecting the planted subspace. \n\nFor a matching upper bound, the authors propose to use a U-statistics that resembles the unfolding technique in the multi-spike tensor PCA and proved that $O(d^{k^\\star/2})$ is essential for this algorithm to learn the planted direction.", "questions": "1. In the upper bound algorithm, you proposed a kernel-based algorithm that implements the label transformation of potentially infinite order and the conditions for the kernel seems to be very weak. However, in the problem of learning single-index models, batch-reusing / explicit label transformation are deployed to go beyond the CSQ queries[1,2] and certain conditions are required for general gradients to attain the optimal sample complexities [e.g. Assumpion 4.1 (b), 2]. Does this kernel trick automatically select such label transformations? Or is there a way that we can use this method in iterative algorithms to achieve optimal guarantee? \n2. Does the sub-space filtration (or flag, in (1)) from the generative leap exactly equal to the filtration defined for the information leap?  To put in other way, does the direction that is easier to learn in the notion of generative exponent necessarily easier to learn in the notion of information exponent? \n\n[1] Lee, Jason D., Kazusato Oko, Taiji Suzuki, and Denny Wu. \"Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit.\" Advances in Neural Information Processing Systems 37 (2024): 58716-58756.\n\n[2] Chen, Siyu, Beining Wu, Miao Lu, Zhuoran Yang, and Tianhao Wang. \"Can neural networks achieve optimal computational-statistical tradeoff? an analysis on single-index model.\" In The Thirteenth International Conference on Learning Representations. 2025.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Pros\n1. The paper is mathematically rigorous and well organized. \n2. The content is quite complete and novel, by fully settling the low-degree detection lower bound and a matching upper bound. Several examples are provided to help readers with understanding the notion of generative leap and the hardness of the multi-index models.  \n3. The proof sketch for the upper bound is very clean, easy to follow and sufficient to cover the main idea. \n\nCons \n1. The layout, definitions and results seem to be a bit dense for readers.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and address each point below.\n\n> In the upper bound algorithm, you proposed a kernel-based algorithm that implements the label transformation of potentially infinite order and the conditions for the kernel seems to be very weak. However, in the problem of learning single-index models, batch-reusing / explicit label transformation are deployed to go beyond the CSQ queries[1,2] and certain conditions are required for general gradients to attain the optimal sample complexities [e.g. Assumpion 4.1 (b), 2]. Does this kernel trick automatically select such label transformations? Or is there a way that we can use this method in iterative algorithms to achieve optimal guarantee?\n\nYes, this kernel trick automatically selects such label transformations. In fact, what this implicitly relies on is that it suffices to use a *random* label transformation. For example:\n\n- uniformly sample $q \\in [0,1]$, and then threshold the labels $y_1,\\ldots,y_n$ at the $q$-th quantile, i.e. if $y_1 \\le \\ldots, \\le y_n$ then $y_1,\\ldots,y_{\\lfloor q n \\rfloor} = 0$ and $y_{\\lfloor qn \\rfloor}, \\ldots, y_n = 1$ (min CDF kernel)\n\n- transform $y \\to \\cos(w y + b)$ where $w \\sim N(0,1)$ and $b \\sim \\mathrm{Unif}([0,2\\pi])$ (RBF kernel)\n\nEither of these choices would succeed with probability $1$. Our kernel estimator can be interpreted as \"averaging\" over the randomness in such a label transformation. Therefore, to use this method in an iterative algorithm (e.g. batch re-use) it suffices to show that the dynamics apply a sufficiently random label transformation to the labels. While this has been analyzed in the single-index setting (e.g. [1,2] above), we are not aware of any results that imply learnability of general multi-index functions using gradient descent given $n \\gtrsim d^{O(k^\\star)}$ samples where $k^\\star$ is the generative leap.\n\n> Does the sub-space filtration (or flag, in (1)) from the generative leap exactly equal to the filtration defined for the information leap? To put in other way, does the direction that is easier to learn in the notion of generative exponent necessarily easier to learn in the notion of information exponent?\n\nNo, in general these filtrations can be quite different. As a simple example, consider:\n$$\ny = h_5(z_1) + \\mathrm{sign}(z_1 z_2).\n$$\nThe filtration for the generative leap is $\\emptyset \\subset \\mathrm{span}[z_1] \\subset \\mathrm{span}[z_1,z_2]$ since we can apply a label transformation to lower the exponent in the $z_1$ direction to $1$ (for example $y \\leftarrow y^3$ works here), and then condition on $z_1$ to learn $z_2$. This corresponds to two leaps of size $1$.\n\nOn the other hand, the filtration for the information leap is just $\\emptyset \\subset \\mathrm{span}[z_1,z_2]$ directly since directly learning $h_5(z_1)$ is leap 4 so the learner is forced to learn both coordinates from $\\mathrm{sign}(z_1z_2)$, which is a single leap of size $2$."}, {"review_id": "iviI5EV9MM", "reviewer": "Reviewer_xViU", "summary": "This paper studies the complexity of learning Gaussian multi-index models, where the authors generalize the notion of the generative exponent for single-index models to generative leap exponent. They prove that this exponent controls the low-degree-polynomial lower bound for sample complexity, and prove a polynomial-time algorithm with the same sample complexity as a function of $d$. They thus show that the generative leap exponent provides a tight characterization of the sample complexity for efficient learning of Gaussian multi-index models in high dimensions. The authors also establish links between the generative and information leap exponents, and show that their framework covers several examples of popular Gaussian multi-index models studied in the literature.", "questions": "* What does $\\mathrm{span}(\\Gamma)$ mean for a tensor $\\Gamma \\in (S^\\perp)^{\\otimes 2k}$?\n\n* I believe the union in Equation (1) is meant to be direct sum? In particular $S_i$ live in different subspaces, I’m not sure how one can take unions of them and end up with a new subspace.\n\n* I’m a bit confused about Proposition 2. It seems that $\\mathcal{T}$ acts on $(y,z_S)$, then shouldn't the push forward map be $\\mathrm{Id}\\_{\\bar{z}\\_S} \\otimes \\mathcal{T}$ instead of $\\operatorname{Id}\\_z \\otimes \\mathcal{T}$?\n\n* From my understanding, not every subspace $S$ of the index space $U^\\*$ is seen when defining the generative leap. However, for the lower bound of Section 3, are we free to choose any subspace $\\bar{S}$ of $U^\\*$? Then would we be able to choose a subspace whose leap exponent is even larger than the one seen during Definition 3? I don’t see why we would necessarily pick the one that corresponds to the maximizer of Definition 3.\n\n* The authors mention in the paragraph starting from Line 25 that to achieve the information-theoretically optimal sample complexity of $d$, one needs to have a brute force estimator over an $\\epsilon$-net which will necessarily have an exponential computational complexity in high dimensions. However, if we assume the Gaussian multi-index model has a structured covariance, it is possible to obtain an improved computational complexity (even sub-exponential) while maintaining the same linear sample complexity (in some lower effective dimension). [1] presents an example of how gradient-based learning can achieve this computational adaptivity for multi-index models (which is absent from fixed-grid optimization over $\\epsilon$ nets). It is generally interesting to know how the picture here would change once we have a structured covariance, which is known to improve the dependence on information exponent for algorithms in the correlational statistical query class [2, 3].\n\n* The discussion in Section 4.2 can of course be extended to non-polynomial time algorithms. Without any assumptions on $P$, learning the regression function when $Y$ depends on $r$ directions could have a minimax optimal rate that looks like $(1/n)^{O(1/r)}$.\n\n* The authors may want to use $s_i$ in the 3rd line of Algorithm 1.\n\nReferences:\n\n[1] A. Mousavi-Hosseini et al. \"Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics.\" ICLR 2025.\n\n[2] J. Ba et al. \"Learning in the presence of low-dimensional structure: a spiked random matrix perspective.\" NeurIPS 2023.\n\n[3] A. Mousavi-Hosseini et al. \"Gradient-Based Feature Learning under Structured Data.\" NeurIPS 2023.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This is a technically strong paper with many novel and interesting results, and provides a complete picture of the complexity of learning Gaussian multi-index models, a problem that has received a lot of attention from the community as an example where learners can adapt to a latent low-dimensional structure in a high-dimensional ambient space and perform feature learning with non-linear predictors.\n\n The paper is generally well-written and easy to read, but there are a few points that can improve the readability. In particular, I think that the readers could have a better intuition of the constructions in Section 2 if the authors present the example of staircase functions and how it leads to concrete instantiations of Definitions 3, 4, and Proposition 1. Also the authors could explain a bit more about certain notations, discussed below.", "was_revised": true, "final_justification": "Per my original review this is a strong contribution and all reviewers are in agreement.", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and address each point below.\n\n> The paper is generally well-written and easy to read, but there are a few points that can improve the readability. In particular, I think that the readers could have a better intuition of the constructions in Section 2 if the authors present the example of staircase functions and how it leads to concrete instantiations of Definitions 3, 4, and Proposition 1.\n\nWe agree with the reviewer's recommendation and will include some explicit examples for the filtration corresponding to the generative leap and how it differs from the information leap. We believe that a good example to highlight is $y = h_5(z_1) + \\mathrm{sign}(z_1 z_2)$. The filtration for the generative leap is $\\emptyset \\subset \\mathrm{span}[z_1] \\subset \\mathrm{span}[z_1,z_2]$ since we can apply a label transformation to lower the exponent in the $z_1$ direction to $1$ (for example $y \\leftarrow y^3$ works here), and then condition on $z_1$ to learn $z_2$. This corresponds to two leaps of size $1$. On the other hand, the filtration for the information leap is just $\\emptyset \\subset \\mathrm{span}[z_1,z_2]$ directly since directly learning $h_5(z_1)$ is leap 4 so the learner is forced to learn both coordinates from $\\mathrm{sign}(z_1z_2)$, which is a single leap of size $2$.\n\n> What does $\\mathrm{span}(\\Gamma)$ mean for a tensor $\\Gamma \\in (S^\\perp)^{\\otimes 2k}$?\n\nWe apologize for the confusion and have added a section to the paper clarifying our tensor notation, including the definition of $\\mathrm{span}(\\Gamma)$. In general we can define the span of a tensor at an index $l \\in [0,2k]$ by:\n$$\n\\mathrm{span}\\_l(\\Gamma) = \\left\\\\{\\Gamma[v\\_1,\\ldots,v\\_{l-1},\\cdot,v\\_{l+1},\\ldots,v\\_{2k}] | v\\_{1,\\ldots,2k} \\in S^\\perp\\right\\\\}\n$$\nThis is equivalent to the span of the flattened version of $\\Gamma$ where the $l$-th index is pulled out:\n$$\n\\mathrm{span}\\_l(\\Gamma) = \\mathrm{span}[M] \\quad\\text{where}\\quad M\\_{i,(j\\_1,\\ldots,j\\_{2k-1})} = \\Gamma\\_{j\\_1,\\ldots,j\\_{\\ell-1},i,j\\_\\ell,\\ldots,j\\_{2k-1}}.\n$$\nDue to the symmetries in $\\Lambda$, $\\mathrm{span}_l(\\Gamma)$ is independent of $l \\in [0,2k]$ so we simply write $\\mathrm{span}(\\Lambda)$. In this case it's simplest to think of reshaping $\\Lambda$ as an element of $S^\\perp \\otimes (S^\\perp)^{\\otimes 2k-1}$ and then computing the span of this matrix.\n\n> I believe the union in Equation (1) is meant to be direct sum? In particular $S_i$ live in different subspaces, I’m not sure how one can take unions of them and end up with a new subspace.\n\nYes, you are correct that equation (1) should be a direct sum. We used $S \\cup S'$ to represent $S \\oplus S'$ at various points throughout the paper and will correct this for the camera ready.\n\n> I’m a bit confused about Proposition 2. It seems that $\\mathcal{T}$ acts on $(y,z_S)$, then shouldn't the push forward map be $\\mathrm{Id}_{\\bar{z}_S} \\otimes \\mathcal{T}$ instead of $\\operatorname{Id}_z \\otimes \\mathcal{T}$?\n\nThe pushforward map should indeed read $\\mathrm{Id}\\_{\\overline{z}\\_S} \\otimes \\mathcal{T}$, rather than $\\mathrm{Id}\\_{\\overline{z}\\_S} \\otimes \\mathcal{T}$. Thank you for catching this typo, we will correct it in our next revision.\n\n> From my understanding, not every subspace $S$ of the index set $U^\\star$ is seen when defining the generative leap. However, for the lower bound of Section 3, are we free to choose any subspace $\\bar{S}$ of $U^\\star$? Then would we be able to choose a subspace whose leap exponent is even larger than the one seen during Definition 3? I don’t see why we would necessarily pick the one that corresponds to the maximizer of Definition 3.\n\nTheorem 1 is stated for picking the subspace $\\overline{S}$ that corresponds to the filtration just before the leap corresponding to the generative leap (specifically, a choice of $\\overline{S}$ that is seen in Definition 3). However we could easily generalize it to the following statement: for any subspace $S$, distinguishing $\\mathbb{H}_0,\\mathbb{H}_1$ requires $n \\gtrsim d^{k(\\overline{S})/2}$ samples. As $\\overline{S}$ was chosen such that $k(\\overline{S}) = k^\\star$, this would imply Theorem 1.\n\nYou are indeed correct that we could apply this to any subspace $\\overline{S}$, including those not seen during Definition 3. Arguing that $n \\ge d^{k^\\star/2}$ samples are necessary for *estimation*, therefore follows from this inductive argument:\n\n- At the start you have no information ($\\overline{S} = \\emptyset$), and you can prove that you need $n \\gtrsim d^{k(\\emptyset)/2} = d^{k_1/2}$ samples to detect the planted model, and therefore to estimate any additional directions.\n- If the learner has more than $d^{k_1/2}$ samples, we will generously provide them with all of $S_1$. Given $S_1$, detecting the planted model learning any additional directions requires $n \\gtrsim d^{k(S_1)/2} = d^{k_2/2}$ samples.\n- ...\n\nThis induction shows that recovering any direction in $S_{i+1} \\setminus S_i$ requires $n \\gtrsim d^{\\max(k_1,\\ldots,k_i)/2}$ samples and since $k^\\star = \\max_i k_i$, it demonstrates that recovering the index set requires $n \\gtrsim d^{k^\\star/2}$ samples. We will add the generalized version of Theorem 1 in terms of $k(S)$ and the discussion connecting estimation with this series of decision problems to Section 3.\n\n> The authors mention in the paragraph starting from Line 25 that to achieve the information-theoretically optimal sample complexity of $d$, one needs to have a brute force estimator over an -net which will necessarily have an exponential computational complexity in high dimensions. However, if we assume the Gaussian multi-index model has a structured covariance, it is possible to obtain an improved computational complexity (even sub-exponential) while maintaining the same linear sample complexity (in some lower effective dimension). [1] presents an example of how gradient-based learning can achieve this computational adaptivity for multi-index models (which is absent from fixed-grid optimization over  nets). It is generally interesting to know how the picture here would change once we have a structured covariance, which is known to improve the dependence on information exponent for algorithms in the correlational statistical query class [2, 3].\n\nWe definitely agree with the reviewer that the picture gets much more interesting when there is additional structure in the input data. The generative leap directly extends to the setting of non-isotropic covariances so long as this covariance is fixed in advance. For example, for a single index model if $x \\sim N(0,\\Sigma)$ and $w^\\star$ is chosen such that $\\mathbb{E}_x (x \\cdot w^\\star)^2 = 1$, then we can just transform $(x,w^\\star) \\to (\\Sigma^{-1/2} x, \\Sigma^{1/2} w^\\star)$ and then $x$ will be isotropic and $w^\\star$ will be uniform on the sphere so the generative exponent still applies. However, if $\\Sigma$ and $w^\\star$ are correlated (as in [2,3]), then the learner can certainly leverage this information to learn more efficiently. We will add a section in the paper discussing possible extensions of our framework to more structured inputs.\n\n> The discussion in Section 4.2 can of course be extended to non-polynomial time algorithms. Without any assumptions on $P$,  learning the regression function when $Y$ depends on $r$ directions could have a minimax optimal rate that looks like $1/n^{O(1/r)}$.\n\nWe agree that the minimax rate for estimation is $1/n^{O(1/r)}$. However, it's not immediately clear that this is necessary for subspace recovery. One could potentially hope that subspace recovery is an easier task. The purpose of section 4.2 is to give an example where it is actually necessary to find the right function on $z_1,\\ldots,z_{r-1}$ before you can apply the right label transformation to identify $z_r$.\n\n> The authors may want to use $s_i$ in the 3rd line of Algorithm 1.\n\nCould you clarify which line you are referring to? Are you referring to the line $y \\gets [y,\\Pi_S x] \\in \\mathbb{R}^{|S| + 1}$ in Algorithm 2?"}, {"review_id": "OlmoQi9Vtv", "reviewer": "Reviewer_DPCL", "summary": "This paper introduces the generative leap exponent, extending the generative exponent from single-index to multi-index Gaussian models. The authors establish a computational lower bound of under the Low-Degree Polynomial (LDP) framework for agnostically learning the hidden subspace. They also propose a sequential spectral estimator which achieves a matching upper bound.", "questions": "1. L115: k-th Hermite tensor uses bold type here but not in the following texts. The authors can also emphaize that $\\gamma_d$ represents Gaussian distribution.\n\n2. L150: What does $span(\\Lambda)$ mean when $\\Lambda$ is a tensor?\n\n3. It might be good to explain the meaning of generative leap exponent, as in L175-177 for generative exponent to better understand their difference. The authors can also explain the leap decomposition (L149) in more details to understand the intuition and difficulty to generalize the leap exponent from single index models to multi-index models.\n\n4. In Proposition 4, why do we only have the upper bound of $k^*$ but not its value?\n\n5. The authors mention that GD needs $\\Theta(d^k)$ samples. Is it suboptimal?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is theoretically sound and well organized. It is significant to find the tight sample complexity for Gaussian multi-index models and the authors propose a novel algorithm to match the sample complexity. Some sections could be more accessible, especially the leap decomposition which is quite dense, but in general core claims are well-supported.", "was_revised": true, "final_justification": "This is a strong paper and I recommend acceptance.", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and address each point below.\n\n> L115: k-th Hermite tensor uses bold type here but not in the following texts. The authors can also emphaize that $\\gamma_d$ represents Gaussian distribution.\n\nThank you for catching these – we will correct them for the camera ready.\n\n> L150: What does $span(\\Lambda)$ mean when $\\Lambda$ is a tensor?\n\nWe apologize for the confusion and have added a section to the paper clarifying our tensor notation, including the definition of $\\mathrm{span}(\\Gamma)$. In general we can define the span of a tensor at an index $l \\in [0,2k]$ by:\n$$\n\\mathrm{span}\\_l(\\Gamma) = \\left\\\\{\\Gamma[v\\_1,\\ldots,v\\_{l-1},\\cdot,v\\_{l+1},\\ldots,v\\_{2k}] | v\\_{1,\\ldots,2k} \\in S^\\perp\\right\\\\}\n$$\nThis is equivalent to the span of the flattened version of $\\Gamma$ where the $l$-th index is pulled out:\n$$\n\\mathrm{span}\\_l(\\Gamma) = \\mathrm{span}[M] \\quad\\text{where}\\quad M\\_{i,(j\\_1,\\ldots,j\\_{2k-1})} = \\Gamma\\_{j\\_1,\\ldots,j\\_{\\ell-1},i,j\\_\\ell,\\ldots,j\\_{2k-1}}.\n$$\nDue to the symmetries in $\\Lambda$, $\\mathrm{span}_l(\\Gamma)$ is independent of $l \\in [0,2k]$ so we simply write $\\mathrm{span}(\\Lambda)$. In this case it's simplest to think of reshaping $\\Lambda$ as an element of $S^\\perp \\otimes (S^\\perp)^{\\otimes 2k-1}$ and then computing the span of this matrix.\n\n> It might be good to explain the meaning of generative leap exponent, as in L175-177 for generative exponent to better understand their difference. The authors can also explain the leap decomposition (L149) in more details to understand the intuition and difficulty to generalize the leap exponent from single index models to multi-index models.\n\nWe agree with the reviewer's recommendation and will include some explicit examples for the filtration corresponding to the generative leap and how it differs from the information leap. We believe that a good example to highlight is $y = h_5(z_1) + \\mathrm{sign}(z_1 z_2)$. The filtration for the generative leap is $\\emptyset \\subset \\mathrm{span}[z_1] \\subset \\mathrm{span}[z_1,z_2]$ since we can apply a label transformation to lower the exponent in the $z_1$ direction to $1$ (for example $y \\leftarrow y^3$ works here), and then condition on $z_1$ to learn $z_2$. This corresponds to two leaps of size $1$. On the other hand, the filtration for the information leap is just $\\emptyset \\subset \\mathrm{span}[z_1,z_2]$ directly since directly learning $h_5(z_1)$ is leap 4 so the learner is forced to learn both coordinates from $\\mathrm{sign}(z_1z_2)$, which is a single leap of size $2$.\n\n> In Proposition 4, why do we only have the upper bound of $k^*$ but not its value?\n\nProposition 4 uniquely determines $k^\\star = k$ for Gaussian $k$-parity and $k^\\star = 1$ for staircase functions. For intersections of halfspaces and general polynomials, we showed $k^\\star \\in \\{1,2\\}$ and this depends on the specific halfspaces/polynomials. For example, in the single-index setting, $k^\\star = 1$ for any polynomial unless it is even, i.e. $p(x) = p(-x)$, in which case $k^\\star = 2$. Thus, $p(x) = x^4 + x^2$ has $k^\\star = 2$ while $p(x) = x^4 + x^2 + x$ has $k^\\star = 1$. \n\n> The authors mention that GD needs $\\Theta(d^k)$ samples. Is it suboptimal?\n\nWe believe the reviewer is referring to our comment on line 50. Our goal here was simply to set the stage that the sample complexities in this line of work are of the form $n = d^p$ where the exponent $p$ depends on both the algorithm and the link function (e.g. $p = \\max(1,\\ell^\\star-1)$ for online SGD and $p = \\max(1,\\ell^\\star/2)$ for smoothed online SGD). We unfortunately re-used the letter $k$ in the manuscript for the generative exponent which may have led to confusion in line 50 so we will rename $k \\to p$ for this line. We are still unsure what the optimal rate for gradient descent is and whether it can achieve $n = d^{\\max(1,k^\\star-1)}$ sample complexity with batch reuse for general multi-index models."}]

Author rebuttal:

Meta-review: The goal of the paper is the analysis of learning in generic Gaussian multi-index models. The investigation generalises the notion of generative exponent to generative leap exponent, proving that this quantity is crucial in the scaling of the sample complexity scaling for learning. The paper collected unanimous positive feedbacks: its novelty and soundness have been appreciated by all Reviewers, in particular with respect to the introduction of the aforementioned generative leap exponent as informative complexity measure. As considerable effort has been put by the theoretical community in the study of single index and multi index model, the paper provides a significant step forward in such a line of research and might be a reference for further investigations on such a prototipical setups. I therefore recommend its acceptance in NeurIPS, possibly as *spotlight*.
Decision: Accept (spotlight)