The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
Alex Damian, Jason D. Lee, Joan Bruna · 2025
Read The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models by Alex Damian, Jason D. Lee, Joan Bruna (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05500.txt.
Introduction
Alex Damian, Jason D Lee, and Joan Bruna pin down exactly how many examples an efficient algorithm needs to learn a certain hidden structure. Their 2025 paper studies multi-index models, where a label depends on high-dimensional Gaussian data only through a few hidden directions. The task is to recover those directions without knowing the model in advance.
The team introduces a number, the generative leap exponent, that governs the difficulty. Within a broad framework of low-degree polynomial algorithms, they prove the sample count must grow as a specific power of the dimension set by that exponent. They then give a sequential spectral procedure, built on a statistic over Hermite tensors, that reaches the same count, so the bound is tight. Worked examples cover piecewise linear functions, including biased deep ReLU networks, and general deep networks whose first layer sees the hidden subspace.
Catalog record
| CREATOR | Alex Damian, Jason D. Lee, Joan Bruna |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-05500
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models Alex Damian, Jason D. Lee, Joan Bruna Abstract In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) d d -dimensional inputs through their projection onto a low-dimensional r = O d ( 1 ) r=O_{d}(1) subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the generative leap exponent k ⋆ k^{\star} , a natural extension of the generative exponent from [ 35 ] to the multi-index setting. We first show that a sample complexity of n = Θ ( d 1 ∨ k ⋆ / 2 ) n=\Theta(d^{1\vee{k^{\star}}/2}) is necessary in the class of algorithms captured by the Low-Degree-Polynomial framework. We then establish that this sample complexity is also sufficient, by giving an agnostic sequential estimation procedure (that is, requiring no prior knowledge of the multi-index model) based on a spectral U-statistic over appropriate Hermite tensors. We further compute the generative leap exponent for several examples including piecewise linear functions (deep ReLU networks with bias), and general deep neural networks (with r r -dimensional first hidden layer). 1 Introduction We consider learning Gaussian multi-index models: Definition 1 . We say that (X,Y) follows a Gaussian multi-index model with index r if X\sim N(0,I_{d}):=\gamma_{d} and there exists a subspace U^{\star}\in\mathcal{G}(r,d) such that the conditional law \mathbb{P}[Y|X] only depends on the orthogonal projection P_{U^{\star}}X . A Gaussian multi-index model can be thus specified by choosing a basis W^{\star} of U^{\star} (ie, an element of the Stiefel manifold \mathcal{S}(r,d) ), and the law \mathsf{P} of (Z,Y)\in\mathcal{P}(\mathbb{R}^{r}\times\mathbb{R}) 1 1 1 or, more precisely, the conditional law \mathsf{P}^{Z} of Y|Z , since the marginal of Z is \gamma_{r} . , where Z=(W^{\star})^{\top}X . The subspace U^{\star} is referred as the index space . Given a joint distribution \mathsf{P} of (Z,Y) , a natural statistical task associated with such a model is to plant a subspace W^{\star} , uniformly drawn from the Haar measure of \mathcal{S}(r,d) , and draw n iid samples from the multi-index distribution \mathbb{P}_{W^{\star},\mathsf{P}} parametrized by W^{\star} and \mathsf{P} . Our task will be then to recover U^{\star}=\spn[W^{\star}] given these samples. We note that this task is only well-posed when the ‘intrinsic’ dimension of the model is r , namely that \mathsf{P} does not admit a factorization \mathsf{P}=\gamma_{r^{\prime}}\otimes{\mathsf{P}}_{S} , where {\mathsf{P}}_{S}(z_{S},y) is the marginal of \mathsf{P} over a subspace of \mathbb{R}^{r}\times\mathbb{R} of dimension <r+1 that includes the last coordinate. We will assume this property from now on. We place ourselves in the setting where r=O_{d}(1) , and consider the high-dimensional regime. Since the dimensionality of \mathcal{S}(r,d) is of order rd , one expects that a brute-force estimation procedure that fits \mathbb{P}_{\mathsf{P},W_{j}} over a suitable \epsilon -net of \{W_{j}\}_{j}\subset\mathcal{S}(r,d) requires O(d\epsilon^{-2}) samples to estimate the index space up to accuracy \epsilon . Our main motivation is to understand this question from the lens of computational-statistical gaps: how many samples are needed, as a function of d,\mathsf{P} , to produce an estimate of the planted subspace using polynomial-time algorithms, as opposed to using brute-force? This question enjoys a large literature, spanning high-dimensional statistics and learning theory, starting from the inverse regression methods from [ 46 ] and beyond [ 57 , 58 , 37 , 19 , 21 , 55 , 42 , 49 , 33 ] (see also [ 14 ] for a 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 linear feature learning , in the sense that the index space provides an adapted low-dimensional representation to perform high-dimensional learning. Some notorious examples include • (noisy) Gaussian parity: Y|Z\stackrel{{\scriptstyle d}}{{=}}\xi\sgn[Z_{1}\cdot Z_{2}\dots Z_{r}] , with \mathbb{P}[\xi=-1]=\eta , \mathbb{P}[\xi=1]=1-\eta independent of Z and \eta<1/2 . • Gaussian staircase functions: Y|Z\stackrel{{\scriptstyle d}}{{=}}\phi_{1}(Z_{1})+\phi_{2}(Z_{1},Z_{2})+\ldots+\phi_{r}(Z_{1},\ldots,Z_{r}) . • Intersection of r half-spaces: Y|Z\stackrel{{\scriptstyle d}}{{=}}2\prod_{j=1}^{r}{\bf 1}(v_{j}^{\top}Z>\alpha_{j})-1 . • Low-rank shallow neural network: Y|Z=a^{\top}\rho(V^{\top}Z)+\xi for some a\in\mathbb{R}^{M},V\in\mathbb{R}^{r\times M},\rho:\mathbb{R}\to\mathbb{R} , additive noise \xi independent of Z . • Polynomials: Y|Z=q(Z) where q is a polynomial. Focusing on the Gaussian setting, several works, starting from [ 23 , 7 ] and followed by [ 3 , 2 , 10 , 32 , 13 , 29 ] have built a harmonic analysis framework to analyze a large class of algorithms, including stochastic gradient descent over NN architectures, leading to sample complexities of the form n=\Theta(d^{k}) , where k is an explicit exponent associated with a certain harmonic expansion of \mathsf{P} . In particular, [ 35 ] , focusing on Single-Index models (where r=1 ), identified the generative exponent {k^{\star}}={k^{\star}}(\mathsf{P}) (see Section 2 ) as the fundamental quantity driving the sample complexity, in the sense that n=\Theta(d^{1\vee{k^{\star}}/2}) is both necessary and sufficient in the class of algorithms implemented by SQ (Statistical Queries) and Low-Degree Polynomials. In essence, the generative exponent arises from an expansion of the inverse regression of Z given Y , as put forward in the original [ 46 ] . [ 47 , 4 , 36 ] 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 [ 2 , 9 , 54 , 27 ] , the general r>1 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 saddle-to-saddle dynamics, where the index space is revealed incrementally along specific subspaces, with different timescales associated with each step. Moreover, such incremental alignment requires solving a semi-parametric problem, where both the subspace and the link function need to be estimated jointly. We overcome these additional challenges by identifying a suitable generalization of the generative exponent, the leap generative exponent {k^{\star}} (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 a computational lower bound of n=O(d^{{k^{\star}}/2}) under the Low-degree polynomial (LDP) framework, by extending the previously established lower bound in the single-index setting [ 35 ] to an appropriate detection task that is dominated by the index estimation task ( Theorem 1 ). Next, and more importantly, we provide an algorithm that sequentially estimates the index space along the leap decomposition from the spectrum of a novel kernel U -statistic (see Eq ( 5 )). This algorithm recovers the index space as soon as n\gtrsim d^{{k^{\star}}/2} , thus matching the LDP lower bound, and, crucially, it does not require prior knowledge of the multi-index model \mathsf{P} ( Theorem 3 ). 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^{\star}}>2 , they provide evidence of a computational-to-statistical gap at the polynomial scale. Related Works [ 20 ] show that any polynomial multi-index model can be learned with n=\Theta(d) samples via