# Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2025.

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

- [Optimal scaling laws in learning hierarchical multi-index models](https://mlsanity.com/paper/2602.05846/) (2026)
- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Learning Sparse Compositional Functions with Norm-Constrained Neural Networks](https://mlsanity.com/paper/2605.25608/) (2026)
- [Deep Learning as Neural Low-Degree Filtering: A Spectral Theory of Hierarchical Feature Learning](https://mlsanity.com/paper/2605.13612/) (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)

In deep learning, a central issue is to understand how neural networks efficiently learn high-dimensional features. To this end, we explore the gradient descent learning of a general Gaussian Multi-index model f(boldsymbolx)=g(boldsymbolUboldsymbolx) with hidden subspace boldsymbolU∈ ℝr× d, which is the canonical setup to study representation learning. We prove that under generic non-degenerate assumptions on the link function, a standard two-layer neural network trained via layer-wise gradient descent can agnostically learn the target with od(1) test error using widetildeO(d) samples and widetildeO(d2) time. The sample and time complexity both align with the information-theoretic limit up to leading order and are therefore optimal. During the first stage of gradient descent learning, the proof proceeds via showing that the inner weights can perform a power-iteration process. This process implicitly mimics a spectral start for the whole span of the hidden subspace and eventually eliminates finite-sample noise and recovers this span. It surprisingly indicates that optimal results can only be achieved if the first layer is trained for more than O(1) steps. This work demonstrates the ability of neural networks to effectively learn hierarchical functions with respect to both sample and time efficiency.