mlsanityData to 7 Oct 2026

Optimal Spectral Transitions in High-Dimensional Multi-Index Models

arXiv 2502.02545 ↗First posted 4 Feb 2025cs.LG cond-mat.dis-nncited by 6

Not on the map. Why?

Abstract (arXiv)

We consider the problem of how many samples from a Gaussian multi-index model are required to weakly reconstruct the relevant index subspace. Despite its increasing popularity as a testbed for investigating the computational complexity of neural networks, results beyond the single-index setting remain elusive. In this work, we introduce spectral algorithms based on the linearization of a message passing scheme tailored to this problem. Our main contribution is to show that the proposed methods achieve the optimal reconstruction threshold. Leveraging a high-dimensional characterization of the algorithms, we show that above the critical threshold the leading eigenvector correlates with the relevant index subspace, a phenomenon reminiscent of the Baik-Ben Arous-Peche (BBP) transition in spiked models arising in random matrix theory. Supported by numerical experiments and a rigorous theoretical framework, our work bridges critical gaps in the computational limits of weak learnability in multi-index model.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 37 of its 60 references that are in the map. First posted on arXiv 4 Feb 2025.

Builds on

37 of 60 references.

References · 37

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  3. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  4. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  5. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  6. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 67
  7. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  8. 2023Learning time-scales in two-layers neural networkscited by 57
  9. 2013Spectral redemption: clustering sparse networkscited by 54
  10. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  11. 2022Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networkscited by 50
  12. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
25 more
  1. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  2. 2023From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networkscited by 42
  3. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  4. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 39
  5. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 35
  6. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  7. 2020The estimation error of general first order methodscited by 33
  8. 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
  9. 2020Approximate Message Passing with Spectral Initialization for Generalized Linear Modelscited by 22
  10. 2016Finite Sample Analysis of Approximate Message Passing Algorithmscited by 20
  11. 2019The spiked matrix model with generative priorscited by 20
  12. 2021Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passingcited by 18
  13. 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 18
  14. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  15. 2019The Kikuchi Hierarchy and Tensor PCAcited by 15
  16. 2020Optimal Combination of Linear and Spectral Estimators for Generalized Linear Modelscited by 15
  17. 2023Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGDcited by 14
  18. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 14
  19. 2023Approximate message passing from random initialization with applications to mathbbZ2 synchronizationcited by 9
  20. 2023Optimal Algorithms for the Inhomogeneous Spiked Wigner Modelcited by 8
  21. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 8
  22. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 6
  23. 2023Mixed Regression via Approximate Message Passingcited by 3
  24. 2014Spectral density of the non-backtracking operatorcited by 2
  25. 2022A simple and sharper proof of the hypergraph Moore boundcited by 2

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 11
  2. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  3. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 6
  4. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 6
  5. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 2
  6. 2025Spectral Thresholds for Identifiability and Stability:Finite-Sample Phase Transitions in High-Dimensional Learningcited by 0