Research map / Learning theory and algorithms / Sample complexity
The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the generative leap exponent for Gaussian multi-index models, proves an LDP lower bound n=d^{k*/2} and an agnostic sequential spectral Hermite-kernel U-statistic estimator matching it.
Problem
Sample complexity of efficiently estimating the hidden index subspace of Gaussian multi-index models (labels depend on a low-dimensional projection of Gaussian inputs), i.e., the computational-statistical gap for multi-index feature learning.
Approach
Generalizes the single-index generative exponent to a generative leap exponent via a leap decomposition of the index space (subspace filtration), and estimates the subspace sequentially with a kernel U-statistic over Hermite tensors, which avoids diagonal-term noise and needs no knowledge of the link function.
Key results
- Shows a low-degree-polynomial lower bound n=d^{k*/2} (up to log factors) for weak detection of the planted multi-index structure.
- Proposes a sequential Hermite kernel U-statistic estimator recovering the index space with n ~ d^{k*/2}/eps + d/eps^2 samples, without knowledge of the link function.
- Shows piecewise linear functions (ReLU networks with biases) have generative leap exponent at most 2, giving n=Theta(d) learning of low-rank ReLU networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the unfolded tensor estimator with a U-statistic that excludes diagonal terms | Single-leap spectral subspace recovery · Gaussian multi-index models | sample complexity: n \gtrsim d^{1 \vee \frac{2k-1}{3}} -> n \gtrsim d^{k/2} | Helped |
| Use the sequential kernel U-statistic estimator | Gaussian multi-index subspace recovery · Gaussian multi-index models | sample complexity: n \ge C(\mathsf{P},K)\qty[\frac{d^{k^\star/2}}{\epsilon} + \frac{d}{\epsilon^2}] | Helped |
| Use a degree-D polynomial test below the generative-leap threshold | Low-degree polynomial detection · Gaussian multi-index models | weak separation: n = O(d^{{k^\star}/2-\gamma}) | Hurt |
| Apply the generative leap method to r-Gaussian Parity | Hermite Kernel U-Statistic · r-Gaussian Parity | sample complexity: n=\Theta(d^{r/2}) | Helped |
| Apply the method to intersections of halfspaces | Hermite Kernel U-Statistic · Intersection of halfspaces | sample complexity: n=\Theta(d) | Helped |
| Apply the method to polynomial links | Hermite Kernel U-Statistic · Polynomials | sample complexity: n=\Theta(d) | Helped |
| Allow non-zero biases in continuous piecewise linear links | Low-rank ReLU subspace recovery · Arbitrary low-rank ReLU networks with biases | sample complexity: n \ge C(\sigma) d/\epsilon^2 | Helped |
| Use a generic linear input transformation | Deterministic multi-index model · Almost all linear transformations | generative leap exponent: k^\star \leq 2 | Helped |
| Use orthogonal weights and a scalar link with all moments | Shallow neural network · Orthogonal shallow neural network | generative leap exponent: k^\star = {k^\star}(\rho) | No clear effect |
Surprising findings
- Almost every linear transformation of a deterministic model yields generative leap at most 2, so models with large leap are brittle.
- The leap constant may be exponentially large in r (conjectured d exp(r) sample complexity for a specific example).
Limitations
- Analysis restricted to isotropic Gaussian inputs.
- Sample complexity constants C(P,K) may be exponentially large in r and are not fine-grained.
- Algorithm assumes knowledge of leap sizes and dimensions (or requires a heuristic to lift).
Experimental setup
Metrics: sample complexity exponent subspace distance
Baselines: brute-force estimation over epsilon-net iterated filtered PCA tensor unfolding Gaussian multi-index subspace conditioning methods
Builds on: generative exponent (Damian et al. 2024) information exponent tensor unfolding iterated filtered PCA
Closest papers by meaning
- Efficient Algorithms for Non-gaussian Single Index Models with Generative Priors (AAAI 2024 · similarity 0.89)
- Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis (NeurIPS 2025 · similarity 0.89)
- Optimal Spectral Transitions in High-Dimensional Multi-Index Models (NeurIPS 2025 · similarity 0.88)
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.87)
- Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.87)
- From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.