# Fundamental computational limits of weak learnability in high-dimensional multi-index models

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 67 references that are in the map.
- First posted on arXiv 24 May 2024.

## Builds on (most cited first, 30 of 35)

- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (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)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [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)
- [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)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [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)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [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)
- [Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization](https://mlsanity.com/paper/2006.06560/) (2020)
- [Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks](https://mlsanity.com/paper/2202.00293/) (2022)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks](https://mlsanity.com/paper/2310.07891/) (2023)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks](https://mlsanity.com/paper/2302.05882/) (2023)
- [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)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [Learning Polynomials of Few Relevant Dimensions](https://mlsanity.com/paper/2004.13748/) (2020)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation](https://mlsanity.com/paper/1702.06435/) (2017)
- [Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models](https://mlsanity.com/paper/2308.08977/) (2023)
- [Notes on computational-to-statistical gaps: predictions using statistical physics](https://mlsanity.com/paper/1803.11132/) (2018)

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

- [Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networks](https://mlsanity.com/paper/2506.06489/) (2025)
- [Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence](https://mlsanity.com/paper/2411.08798/) (2024)
- [Statistical mechanics of extensive-width Bayesian neural networks near interpolation](https://mlsanity.com/paper/2505.24849/) (2025)
- [Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression](https://mlsanity.com/paper/2509.22341/) (2025)
- [Optimal scaling laws in learning hierarchical multi-index models](https://mlsanity.com/paper/2602.05846/) (2026)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Bayes optimal learning of attention-indexed models](https://mlsanity.com/paper/2506.01582/) (2025)
- [Transfer Learning in Infinite Width Feature Learning Networks](https://mlsanity.com/paper/2507.04448/) (2025)
- [Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling](https://mlsanity.com/paper/2502.15131/) (2025)
- [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation](https://mlsanity.com/paper/2501.18530/) (2025)
- [Feature learning is decoupled from generalization in high capacity neural networks](https://mlsanity.com/paper/2507.19680/) (2025)
- [Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging](https://mlsanity.com/paper/2603.06028/) (2026)
- [Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation](https://mlsanity.com/paper/2510.24616/) (2025)
- [Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks](https://mlsanity.com/paper/2605.10395/) (2026)
- [Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descent](https://mlsanity.com/paper/2605.17767/) (2026)
- [Approximate Message Passing with Random Initialization for Phase Retrieval](https://mlsanity.com/paper/2608.01654/) (2026)
- [Learning Orthogonal Multi-Index Models Beyond Small Initialization: Incremental Learning, Competitive Dynamics and Symmetry](https://mlsanity.com/paper/2609.10879/) (2026)

## Abstract (arXiv)

Multi-index models - functions which only depend on the covariates through a non-linear transformation of their projection on a subspace - are a useful benchmark for investigating feature learning with neural nets. This paper examines the theoretical boundaries of efficient learnability in this hypothesis class, focusing on the minimum sample complexity required for weakly recovering their low-dimensional structure with first-order iterative algorithms, in the high-dimensional regime where the number of samples n!=!α d is proportional to the covariate dimension d. Our findings unfold in three parts: (i) we identify under which conditions a trivial subspace can be learned with a single step of a first-order algorithm for any α!>!0; (ii) if the trivial subspace is empty, we provide necessary and sufficient conditions for the existence of an easy subspace where directions that can be learned only above a certain sample complexity α!>!αc, where αc marks a computational phase transition. In a limited but interesting set of really hard directions -- akin to the parity problem -- αc is found to diverge. Finally, (iii) we show that interactions between different directions can result in an intricate hierarchical learning phenomenon, where directions can be learned sequentially when coupled to easier ones. We discuss in detail the grand staircase picture associated to these functions (and contrast it with the original staircase one). Our theory builds on the optimality of approximate message-passing among first-order iterative methods, delineating the fundamental learnability limit across a broad spectrum of algorithms, including neural networks trained with gradient descent, which we discuss in this context.