# Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 37 references that are in the map.
- First posted on arXiv 13 Nov 2024.

## Builds on (most cited first, 28 of 28)

- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [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)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances](https://mlsanity.com/paper/2105.12221/) (2021)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup](https://mlsanity.com/paper/1906.08632/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [Gradient Descent Quantizes ReLU Network Features](https://mlsanity.com/paper/1803.08367/) (2018)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [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)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [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)
- [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)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions](https://mlsanity.com/paper/2311.03794/) (2023)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [On Single Index Models beyond Gaussian Data](https://mlsanity.com/paper/2307.15804/) (2023)
- [Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II](https://mlsanity.com/paper/2107.10370/) (2021)
- [Expand-and-Cluster: Parameter Recovery of Neural Networks](https://mlsanity.com/paper/2304.12794/) (2023)
- [On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition](https://mlsanity.com/paper/1802.07301/) (2018)
- [Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations](https://mlsanity.com/paper/2406.11828/) (2024)
- [Should Under-parameterized Student Networks Copy or Average Teacher Weights?](https://mlsanity.com/paper/2311.01644/) (2023)

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

- [Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networks](https://mlsanity.com/paper/2506.06489/) (2025)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Flat Channels to Infinity in Neural Loss Landscapes](https://mlsanity.com/paper/2506.14951/) (2025)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Guided by the Experts: Provable Feature Learning Dynamic of Soft-Routed Mixture-of-Experts](https://mlsanity.com/paper/2510.07205/) (2025)
- [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025)
- [Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks](https://mlsanity.com/paper/2604.09412/) (2026)
- [The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledge](https://mlsanity.com/paper/2605.12908/) (2026)
- [Learning Orthogonal Multi-Index Models Beyond Small Initialization: Incremental Learning, Competitive Dynamics and Symmetry](https://mlsanity.com/paper/2609.10879/) (2026)

## Abstract (arXiv)

This work focuses on the gradient flow dynamics of a neural network model that uses correlation loss to approximate a multi-index function on high-dimensional standard Gaussian data. Specifically, the multi-index function we consider is a sum of neurons f^*(x) !=! sumj=1k ! σ^*(vjT x) where v1, dots, vk are unit vectors, and σ^* lacks the first and second Hermite polynomials in its Hermite expansion. It is known that, for the single-index case (k!=!1), overcoming the search phase requires polynomial time complexity. We first generalize this result to multi-index functions characterized by vectors in arbitrary directions. After the search phase, it is not clear whether the network neurons converge to the index vectors, or get stuck at a sub-optimal solution. When the index vectors are orthogonal, we give a complete characterization of the fixed points and prove that neurons converge to the nearest index vectors. Therefore, using n ! asymp ! k log k neurons ensures finding the full set of index vectors with gradient flow with high probability over random initialization. When  viT vj !=! β ! ≥ ! 0 for all i neq j, we prove the existence of a sharp threshold βc !=! c/(c+k) at which the fixed point that computes the average of the index vectors transitions from a saddle point to a minimum. Numerical simulations show that using a correlation loss and a mild overparameterization suffices to learn all of the index vectors when they are nearly orthogonal, however, the correlation loss fails when the dot product between the index vectors exceeds a certain threshold.