# Finite-Time Analysis of Gradient Descent for Shallow Transformers

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

## Key facts

- Cited by 1 papers 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 (most cited first, 30 of 43)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Independently Recurrent Neural Network (IndRNN): Building A Longer and Deeper RNN](https://mlsanity.com/paper/1803.04831/) (2018)
- [Tensor Programs II: Neural Tangent Kernel for Any Architecture](https://mlsanity.com/paper/2006.14548/) (2020)
- [Deep Convolutional Networks as shallow Gaussian Processes](https://mlsanity.com/paper/1808.05587/) (2018)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Infinite attention: NNGP and NTK for deep attention networks](https://mlsanity.com/paper/2006.10540/) (2020)
- [How Transformers Learn Causal Structure with Gradient Descent](https://mlsanity.com/paper/2402.14735/) (2024)
- [In-Context Convergence of Transformers](https://mlsanity.com/paper/2310.05249/) (2023)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [The Recurrent Neural Tangent Kernel](https://mlsanity.com/paper/2006.10246/) (2020)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [On the Role of Attention in Prompt-tuning](https://mlsanity.com/paper/2306.03435/) (2023)

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

- [Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learning](https://mlsanity.com/paper/2610.20337/) (2026)

## 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.