mlsanityData to 7 Oct 2026

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

arXiv 2411.08798 ↗First posted 13 Nov 2024cs.LG cs.NE math.AGcited by 8

Not on the map. Why?

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.

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

Builds on

28 of 37 references.

References · 28

  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  2. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  3. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  4. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  5. 2021Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariancescited by 125
  6. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  7. 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
  8. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  9. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  10. 2022Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputscited by 74
  11. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  12. 2018Gradient Descent Quantizes ReLU Network Featurescited by 57
16 more
  1. 2023Learning time-scales in two-layers neural networkscited by 57
  2. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  3. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  4. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  5. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  6. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 35
  7. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  8. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  9. 2023On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensionscited by 21
  10. 2023On Single Index Models beyond Gaussian Datacited by 17
  11. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  12. 2021Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry IIcited by 16
  13. 2023Expand-and-Cluster: Parameter Recovery of Neural Networkscited by 15
  14. 2018On the Connection Between Learning Two-Layers Neural Networks and Tensor Decompositioncited by 14
  15. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  16. 2023Should Under-parameterized Student Networks Copy or Average Teacher Weights?cited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 3.

8 papers.

  1. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 11
  2. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  3. 2025Flat Channels to Infinity in Neural Loss Landscapescited by 3
  4. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  5. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  6. 2026Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networkscited by 2
  7. 2025Guided by the Experts: Provable Feature Learning Dynamic of Soft-Routed Mixture-of-Expertscited by 1
  8. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1