mlsanityData to 14 Oct 2026

Survey on Algorithms for multi-index models

arXiv 2504.05426 ↗First posted 7 Apr 2025stat.ML cs.LG stat.MEcited by 15

Not on the map. Why?

Abstract (arXiv)

We review the literature on algorithms for estimating the index space in a multi-index model. The primary focus is on computationally efficient (polynomial-time) algorithms in Gaussian space, the assumptions under which consistency is guaranteed by these methods, and their sample complexity. In many cases, a gap is observed between the sample complexity of the best known computationally efficient methods and the information-theoretical minimum. We also review algorithms based on estimating the span of gradients using nonparametric methods, and algorithms based on fitting neural networks using gradient descent

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 48 of its 96 references that are in the map. First posted on arXiv 7 Apr 2025.

Builds on

48 of 96 references.

References · 48

  1. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  2. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  3. 2020Few-Shot Learning via Learning the Representation, Provablycited by 214
  4. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  5. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  6. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  7. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  8. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  9. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  10. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  11. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  12. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
36 more
  1. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  2. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  3. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  4. 2023Learning time-scales in two-layers neural networkscited by 57
  5. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  6. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  7. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  8. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  9. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
  10. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  11. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  12. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 39
  13. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  14. 2024Asymptotics of feature learning in two-layer networks after one gradient-stepcited by 38
  15. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 37
  16. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  17. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  18. 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
  19. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  20. 2023On Single Index Models beyond Gaussian Datacited by 17
  21. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 16
  22. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  23. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  24. 2019How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCAcited by 14
  25. 2024Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Boundscited by 13
  26. 2022Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexitycited by 12
  27. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  28. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  29. 2024Efficient Discrepancy Testing for Learning with Distribution Shiftcited by 9
  30. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  31. 2022On the symmetries in the dynamics of wide two-layer neural networkscited by 8
  32. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 8
  33. 2023Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Productscited by 7
  34. 2023Nonparametric Linear Feature Learning in Regression Through Regularisationcited by 5
  35. 2020Robust testing of low-dimensional functionscited by 4
  36. 2018Is your function low-dimensional?cited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 9; 2026: 6.

15 papers.

Sort:

By area:

  1. 2025Position: A Theory of Deep Learning Must Include Compositional Sparsitycited by 14
  2. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  3. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  4. 2026Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrievalcited by 6
  5. 2026AI4SLT: Empirical Processes in Lean 4 for Formal Statistical Learning Theorycited by 5
  6. 2025Learning Multi-Index Models with Hyper-Kernel Ridge Regressioncited by 3
  7. 2025Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Datacited by 3
  8. 2025On the Neural Feature Ansatz for Deep Neural Networkscited by 2
  9. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  10. 2025Joint Learning in the Gaussian Single Index Modelcited by 1
  11. 2025Provably Extracting the Features from a General Superpositioncited by 1
  12. 2026Optimal Regret for Single Index Banditscited by 1
3 more
  1. 2025Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Modelscited by 0
  2. 2026Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruptioncited by 0
  3. 2026Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Methodcited by 0