mlsanityData to 14 Oct 2026

Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions

arXiv 2405.15459 ↗First posted 24 May 2024stat.ML cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

Neural networks can identify low-dimensional relevant structures within high-dimensional noisy data, yet our mathematical understanding of how they do so remains scarce. Here, we investigate the training dynamics of two-layer shallow neural networks trained with gradient-based algorithms, and discuss how they learn pertinent features in multi-index models, that is target functions with low-dimensional relevant directions. In the high-dimensional regime, where the input dimension d diverges, we show that a simple modification of the idealized single-pass gradient descent training scenario, where data can now be repeated or iterated upon twice, drastically improves its computational efficiency. In particular, it surpasses the limitations previously believed to be dictated by the Information and Leap exponents associated with the target function to be learned. Our results highlight the ability of networks to learn relevant structures from data alone without any pre-processing. More precisely, we show that (almost) all directions are learned with at most O(d log d) steps. Among the exceptions is a set of hard functions that includes sparse parities. In the presence of coupling between directions, however, these can be learned sequentially through a hierarchical mechanism that generalizes the notion of staircase functions. Our results are proven by a rigorous study of the evolution of the relevant statistics for high-dimensional dynamics.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). Builds on 28 of its 42 references that are in the map. First posted on arXiv 24 May 2024.

Builds on

28 of 42 references.

References · 28

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
  3. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  4. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  5. 2019Lookahead Optimizer: k steps forward, 1 step backcited by 336
  6. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  7. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  8. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  9. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  10. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  11. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  12. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
16 more
  1. 2018Mean Field Analysis of Neural Networks: A Central Limit Theoremcited by 107
  2. 2018Trainability and Accuracy of Neural Networks: An Interacting Particle System Approachcited by 106
  3. 2021Neural Networks as Kernel Learners: The Silent Alignment Effectcited by 106
  4. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  5. 2019Do We Train on Test Data? Purging CIFAR of Near-Duplicatescited by 62
  6. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  7. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  8. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  9. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  10. 2023A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networkscited by 49
  11. 2023From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networkscited by 43
  12. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  13. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  14. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  15. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  16. 2022Learning sparse features can lead to overfitting in neural networkscited by 23

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 8; 2025: 15; 2026: 14.

37 papers.

Sort:

By area:

  1. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  2. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  3. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  4. 2025Survey on Algorithms for multi-index modelscited by 15
  5. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 14
  6. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  7. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 9
  8. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  9. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  10. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  11. 2025On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspectivecited by 8
  12. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 7
25 more
  1. 2025Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Modelscited by 6
  2. 2026Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrievalcited by 6
  3. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  4. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  5. 2025Online Learning of Neural Networkscited by 5
  6. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 5
  7. 2025Mixture of Experts Provably Detect and Learn the Latent Cluster Structure in Gradient-Based Learningcited by 4
  8. 2025Martingale Posterior Neural Networks for Fast Sequential Decision Makingcited by 4
  9. 2025Test time training enhances in-context learning of nonlinear functionscited by 3
  10. 2025Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Datacited by 3
  11. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  12. 2024Learning with Hidden Factorial Structurecited by 2
  13. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  14. 2026When pre-training hurts LoRA fine-tuning: a dynamical analysis via single-index modelscited by 2
  15. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  16. 2025Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learningcited by 1
  17. 2026Local EGOP for Continuous Index Learningcited by 1
  18. 2026Improved high-dimensional estimation with Langevin dynamics and stochastic weight averagingcited by 1
  19. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  20. 2026Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index modelscited by 1
  21. 2026Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descentcited by 0
  22. 2026Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biasescited by 0
  23. 2026How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysiscited by 0
  24. 2026Approximate Message Passing with Random Initialization for Phase Retrievalcited by 0
  25. 2026Minibatch persistency, eight years later: what batch reuse costs in steps and joules, and what it saves in datacited by 0