mlsanityData to 7 Oct 2026

How Well Can Transformers Emulate In-context Newton's Method?

arXiv 2403.03183 ↗First posted 5 Mar 2024cs.LG cs.AI math.OCcited by 23

Not on the map. Why?

Abstract (arXiv)

Transformer-based models have demonstrated remarkable in-context learning capabilities, prompting extensive research into its underlying mechanisms. Recent studies have suggested that Transformers can implement first-order optimization algorithms for in-context learning and even second order ones for the case of linear regression. In this work, we study whether Transformers can perform higher order optimization methods, beyond the case of linear regression. We establish that linear attention Transformers with ReLU layers can approximate second order optimization algorithms for the task of logistic regression and achieve ε error with only a logarithmic to the error more layers. As a by-product we demonstrate the ability of even linear attention-only Transformers in implementing a single step of Newton's iteration for matrix inversion with merely two layers. These results suggest the ability of the Transformer architecture to implement complex algorithms, beyond gradient descent.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 29 of its 38 references that are in the map. First posted on arXiv 5 Mar 2024.

Builds on

29 of 38 references.

References · 29

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  6. 2022Emergent Abilities of Large Language Modelscited by 2,483
  7. 2021Convex optimizationcited by 2,479
  8. 2021Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNetcited by 1,096
  9. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  10. 2022Transformers learn in-context by gradient descentcited by 714
  11. 2022GPT-NeoX-20B: An Open-Source Autoregressive Language Modelcited by 711
  12. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
17 more
  1. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  2. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  3. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  4. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 274
  5. 2023Looped Transformers as Programmable Computerscited by 224
  6. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  7. 2022Language models show human-like content effects on reasoning taskscited by 171
  8. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 168
  9. 2023In-Context Convergence of Transformerscited by 112
  10. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 111
  11. 2023Uncovering mesa-optimization algorithms in Transformerscited by 94
  12. 2023How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representationscited by 72
  13. 2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimalitycited by 71
  14. 2023Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Contextcited by 63
  15. 2023Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regressioncited by 47
  16. 2015Communication-Efficient Distributed Optimization of Self-Concordant Empirical Losscited by 7
  17. 2018Composite Convex Optimization with Global and Local Inexact Oraclescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 11; 2025: 10; 2026: 2.

23 papers.

Sort:

By area:

  1. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 28
  2. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  3. 2024On the Training Convergence of Transformers for In-Context Classification of Gaussian Mixturescited by 15
  4. 2024One-Layer Transformer Provably Learns One-Nearest Neighbor In Contextcited by 14
  5. 2024How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regressioncited by 13
  6. 2024Vector-ICL: In-context Learning with Continuous Vector Representationscited by 13
  7. 2024Transformers Handle Endogeneity in In-Context Linear Regressioncited by 8
  8. 2025Analyzing limits for in-context learningcited by 6
  9. 2024On Mesa-Optimization in Autoregressively Trained Transformers: Emergence and Capabilitycited by 5
  10. 2024Task Diversity Shortens the ICL Plateaucited by 5
  11. 2024Re-examining learning linear functions in contextcited by 5
  12. 2025Transformers Meet In-Context Learning: A Universal Approximation Theorycited by 4
11 more
  1. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  2. 2025Transformers versus the EM Algorithm in Multi-class Clusteringcited by 3
  3. 2025The Initialization Determines Whether In-Context Learning Is Gradient Descentcited by 3
  4. 2025Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixturescited by 2
  5. 2025Adversarially Pretrained Transformers May Be Universally Robust In-Context Learnerscited by 2
  6. 2025In-Context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-Separationcited by 1
  7. 2025On the Existence of Universal Simulators of Attentioncited by 1
  8. 2025Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regressioncited by 1
  9. 2026Bayesian Optimality of In-Context Learning with Selective State Spacescited by 1
  10. 2024Toward generalizable learning of all (linear) first-order methods via memory augmented Transformerscited by 0
  11. 2026In-Context Reward Adaptation for Robust Preference Modelingcited by 0