mlsanityData to 14 Oct 2026

Implicit Bias and Fast Convergence Rates for Self-attention

arXiv 2402.05738 ↗First posted 8 Feb 2024cs.LG math.OC stat.MLcited by 31

Not on the map. Why?

Abstract (arXiv)

We study the fundamental optimization principles of self-attention, the defining mechanism of transformers, by analyzing the implicit bias of gradient-based optimizers in training a self-attention layer with a linear decoder in binary classification. Building on prior studies in linear logistic regression, recent findings demonstrate that the key-query matrix Wt from gradient-descent (GD) converges in direction towards Wmm, which maximizes the margin between optimal and non-optimal tokens across sequences. However, this convergence is local, dependent on initial conditions, only holds asymptotically as the number of iterations increases, and leaves questions about the potential benefits of adaptive step-size rules unaddressed. To bridge this gap, we first establish scenarios for which convergence is provably global. We then analyze two adaptive step-size strategies: normalized GD and Polyak step-size, demonstrating finite-time convergence rates for Wt to Wmm, and quantifying the sparsification rate of the attention map. These findings not only show that these strategies can accelerate parameter convergence over standard GD in a non-convex setting but also deepen the understanding of the implicit bias in self-attention, linking it more closely to the phenomena observed in linear logistic regression despite its intricate non-convex nature.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). Builds on 66 of its 81 references that are in the map. First posted on arXiv 8 Feb 2024.

Builds on

66 of 81 references.

References · 66

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  4. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  5. 2020Language Models are Few-Shot Learnerscited by 32,419
  6. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  7. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  8. 2020Training data-efficient image transformers & distillation through attentioncited by 4,586
  9. 2017A Broad-Coverage Challenge Corpus for Sentence Understanding through Inferencecited by 2,682
  10. 2020WILDS: A Benchmark of in-the-Wild Distribution Shiftscited by 1,375
  11. 2022Transformers learn in-context by gradient descentcited by 732
  12. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
38 more
  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  2. 2021Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depthcited by 419
  3. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  4. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  5. 2019Nuanced Metrics for Measuring Unintended Bias with Real Data for Text Classificationcited by 404
  6. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  7. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  8. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  9. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  10. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  11. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 222
  12. 2020Directional convergence and alignment in deep learningcited by 178
  13. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 174
  14. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  15. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  16. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  17. 2023Representational Strengths and Limitations of Transformerscited by 133
  18. 2021Vision Transformer for Small-Size Datasetscited by 122
  19. 2019Harmless interpolation of noisy data in regressioncited by 121
  20. 2023Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Becited by 114
  21. 2018Convergence of Gradient Descent on Separable Datacited by 110
  22. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  23. 2022Vision Transformers provably learn spatial structurecited by 93
  24. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  25. 2022On the Implicit Bias in Deep-Learning Algorithmscited by 86
  26. 2018Risk and parameter convergence of logistic regressioncited by 85
  27. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 83
  28. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  29. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  30. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 76
  31. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  32. 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
  33. 2023Max-Margin Token Selection in Attention Mechanismcited by 58
  34. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  35. 2023On the Role of Attention in Prompt-tuningcited by 50
  36. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  37. 2020Implicit Regularization in ReLU Networks with the Square Losscited by 45
  38. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42

50 most cited of 66 All 66 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 9; 2025: 15; 2026: 7.

31 papers.

Sort:

By area:

  1. 2025Training Dynamics of In-Context Learning in Linear Attentioncited by 46
  2. 2025Implicit Bias of Spectral Descent and Muon on Multiclass Separable Datacited by 41
  3. 2024Implicit Regularization of Gradient Flow on One-Layer Softmax Attentioncited by 19
  4. 2024Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Contextcited by 15
  5. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  6. 2024Transformers Learn Low Sensitivity Functions: Investigations and Implicationscited by 14
  7. 2024Non-asymptotic Convergence of Training Transformers for Next-token Predictioncited by 13
  8. 2025The Rich and the Simple: On the Implicit Bias of Adam and SGDcited by 13
  9. 2025Gating is Weighting: Understanding Gated Linear Attention through In-context Learningcited by 12
  10. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 11
  11. 2025Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformerscited by 10
  12. 2024Training Dynamics of Transformers to Recognize Word Co-occurrence via Gradient Flow Analysiscited by 9
19 more
  1. 2024Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selectioncited by 9
  2. 2024How Transformers Get Rich: Approximation and Dynamics Analysiscited by 8
  3. 2025Transformative or Conservative? Conservation laws for ResNets and Transformerscited by 7
  4. 2024On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recoverycited by 6
  5. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 3
  6. 2025Diagonalizing the Softmax: Hadamard Initialization for Tractable Cross-Entropy Dynamicscited by 2
  7. 2026Unlabeled Data Can Provably Enhance In-Context Learning of Transformerscited by 2
  8. 2026Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridgecited by 2
  9. 2025Revisiting Transformers through the Lens of Low Entropy and Dynamic Sparsitycited by 1
  10. 2025How Transformers Learn In-Context Recall Tasks? Optimality, Training Dynamics and Generalizationcited by 1
  11. 2025Attention with Trained Embeddings Provably Selects Important Tokenscited by 1
  12. 2025Learning Linear Regression with Low-Rank Tasks in-Contextcited by 1
  13. 2025Transformers are almost optimal metalearners for linear classificationcited by 1
  14. 2026Finite-Time Analysis of Gradient Descent for Shallow Transformerscited by 1
  15. 2025Variational Deep Learning via Implicit Regularizationcited by 0
  16. 2026Gaussian Match-and-Copy: A Minimalist Benchmark for Studying Transformer Inductioncited by 0
  17. 2026Transformer as an Euler Discretization of Score-based Variational Flowcited by 0
  18. 2026The Implicit Bias of Depth: From Neural Collapse to Softmax Codescited by 0
  19. 2026Relative Positions Generalize, Absolute Positions Memorize: An Implicit-Bias Account of Length Generalization in Attentioncited by 0