mlsanityData to 14 Oct 2026

Finite-Time Analysis of Gradient Descent for Shallow Transformers

arXiv 2601.16514 ↗First posted 23 Jan 2026cs.LG cs.AI math.OCcited by 1

Not on the map. Why?

Abstract (arXiv)

Understanding why Transformers perform so well remains challenging due to their non-convex optimization landscape. In this work, we analyze a shallow Transformer with m independent heads trained by projected gradient descent in the kernel regime. Our analysis reveals two main findings: (i) the width required for nonasymptotic guarantees scales only logarithmically with the sample size n, and (ii) the optimization error is independent of the sequence length T. This contrasts sharply with recurrent architectures, where the optimization error can grow exponentially with T. The trade-off is memory: to keep the full context, the Transformer's memory requirement grows with the sequence length. We validate our theoretical results numerically in a teacher-student setting and compare Transformers with recurrent architectures on an autoregressive task.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 43 of its 59 references that are in the map. First posted on arXiv 23 Jan 2026.

Builds on

43 of 59 references.

References · 43

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  5. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  6. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  7. 2020Rethinking Attention with Performerscited by 1,601
  8. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  9. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  10. 2018On Lazy Training in Differentiable Programmingcited by 675
  11. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  12. 2021Perceiver IO: A General Architecture for Structured Inputs & Outputscited by 629
31 more
  1. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  2. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  3. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  4. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  5. 2018Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processescited by 167
  6. 2018Independently Recurrent Neural Network (IndRNN): Building A Longer and Deeper RNNcited by 143
  7. 2020Tensor Programs II: Neural Tangent Kernel for Any Architecturecited by 143
  8. 2018Deep Convolutional Networks as shallow Gaussian Processescited by 138
  9. 2021SOFT: Softmax-free Transformer with Linear Complexitycited by 128
  10. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  11. 2020Infinite attention: NNGP and NTK for deep attention networkscited by 121
  12. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  13. 2023In-Context Convergence of Transformerscited by 115
  14. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  15. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  16. 2020The Recurrent Neural Tangent Kernelcited by 67
  17. 2023Max-Margin Token Selection in Attention Mechanismcited by 58
  18. 2023On the Role of Attention in Prompt-tuningcited by 50
  19. 2023The Shaped Transformer: Attention Models in the Infinite Depth-and-Width Limitcited by 47
  20. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  21. 2023Replacing softmax with ReLU in Vision Transformerscited by 44
  22. 2024Infinite Limits of Multi-head Transformer Dynamicscited by 39
  23. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  24. 2022Linear Complexity Randomized Self-attention Mechanismcited by 31
  25. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  26. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  27. 2024On the Training Convergence of Transformers for In-Context Classification of Gaussian Mixturescited by 15
  28. 2023On the Convergence of Encoder-only Shallow Transformerscited by 13
  29. 2024Unraveling the Gradient Descent Dynamics of Transformerscited by 11
  30. 2024Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysiscited by 8
  31. 2024Recurrent Natural Policy Gradient for POMDPscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026PowerStep: Memory-Efficient Adaptive Optimization via ℓp-Norm Steepest Descent
  2. 2023Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression
  3. 2024Resource-Efficient Transformer Architecture: Optimizing Memory and Execution Time for Real-Time Applications
  4. 2026The Recurrent Transformer: Greater Effective Depth and Efficient Decoding
  5. 2026Energy-Entropy Regularization: The True Power of Minimal Looped Transformers
  6. 2025Dynamical Properties of Tokens in Self-Attention and Effects of Positional Encoding
  7. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformers
  8. 2025Two-Scale Latent Dynamics for Recurrent-Depth Transformers