mlsanityData to 14 Oct 2026

The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models

arXiv 2506.05500 ↗First posted 5 Jun 2025cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

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 = Od(1) subspace, and we study efficient agnostic estimation procedures for this hidden subspace. We introduce the generative leap exponent k^star, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting. We first show that a sample complexity of n=Theta(d1 vee k/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-dimensional first hidden layer).

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 38 of its 57 references that are in the map. First posted on arXiv 5 Jun 2025.

Builds on

38 of 57 references.

References · 38

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  3. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  4. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  5. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  6. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  7. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  8. 2014A statistical model for tensor PCAcited by 72
  9. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  10. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  11. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  12. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
26 more
  1. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  2. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  3. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  4. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  5. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  6. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  7. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
  8. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 37
  9. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  10. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  11. 2025Emergence and scaling laws in SGD learning of shallow neural networkscited by 32
  12. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  13. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  14. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  15. 2025Survey on Algorithms for multi-index modelscited by 15
  16. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  17. 2024Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Boundscited by 13
  18. 2022Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexitycited by 12
  19. 2020Statistical Query Lower Bounds for Tensor PCAcited by 11
  20. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  21. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 8
  22. 2024Stochastic gradient descent in high dimensions for multi-spiked tensor PCAcited by 7
  23. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 7
  24. 2024Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysiscited by 6
  25. 2025Online Learning of Neural Networkscited by 5
  26. 2025Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Modelscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 7.

9 papers.

  1. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  2. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 2
  3. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  4. 2026The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learningcited by 2
  5. 2026Improved high-dimensional estimation with Langevin dynamics and stochastic weight averagingcited by 1
  6. 2026The two clocks and the innovation window: When and how generative models learn rulescited by 1
  7. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  8. 2026Approximate Message Passing with Random Initialization for Phase Retrievalcited by 0
  9. 2026Revenge of Monosemanticity: Neuron Specialization as a New Form of Feature Learning in MLPscited by 0