# Survey on Algorithms for multi-index models

arXiv: https://arxiv.org/abs/2504.05426 · HTML: https://mlsanity.com/paper/2504.05426/

## 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 (most cited first, 30 of 48)

- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [The committee machine: Computational to statistical gaps in learning a two-layers neural network](https://mlsanity.com/paper/1806.05451/) (2018)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Fundamental Limits of Weak Recovery with Applications to Phase Retrieval](https://mlsanity.com/paper/1708.05932/) (2017)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Asymptotics of feature learning in two-layer networks after one gradient-step](https://mlsanity.com/paper/2402.04980/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Learning Polynomials of Few Relevant Dimensions](https://mlsanity.com/paper/2004.13748/) (2020)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation](https://mlsanity.com/paper/1702.06435/) (2017)

## Built on by (most cited first, 15 of 15)

- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval](https://mlsanity.com/paper/2601.22652/) (2026)
- [AI4SLT: Empirical Processes in Lean 4 for Formal Statistical Learning Theory](https://mlsanity.com/paper/2602.02285/) (2026)
- [Learning Multi-Index Models with Hyper-Kernel Ridge Regression](https://mlsanity.com/paper/2510.02532/) (2025)
- [Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data](https://mlsanity.com/paper/2511.18661/) (2025)
- [On the Neural Feature Ansatz for Deep Neural Networks](https://mlsanity.com/paper/2510.15563/) (2025)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [Joint Learning in the Gaussian Single Index Model](https://mlsanity.com/paper/2505.21336/) (2025)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)
- [Optimal Regret for Single Index Bandits](https://mlsanity.com/paper/2605.09454/) (2026)
- [Dual Filter: A Transformer-like Inference Architecture for Hidden Markov Models](https://mlsanity.com/paper/2505.00818/) (2025)
- [Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption](https://mlsanity.com/paper/2605.29497/) (2026)
- [Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Method](https://mlsanity.com/paper/2607.06369/) (2026)

## 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