[2601.16514] Finite-Time Analysis of Gradient Descent for Shallow Transformers

Computer Science > Machine Learning arXiv:2601.16514 (cs) [Submitted on 23 Jan 2026 (v1), last revised 2 Apr 2026 (this version, v2)] Title:Finite-Time Analysis of Gradient Descent for Shallow Transformers Authors:Enes Arda, Semih Cayci, Atilla Eryilmaz View a PDF of the paper titled Finite-Time Analysis of Gradient Descent for Shallow Transformers, by Enes Arda and 2 other authors View PDF HTML (experimental) Abstract: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. Comments: Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC) Cite as: arXiv:2601.16514 [cs.LG]   (or arXiv:2601.16514v2 [cs.LG] for this version)   https://do...