Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression
This provides insight into the internal mechanisms of Transformers for in-context learning, which is incremental but addresses a key bottleneck in understanding their efficiency.
The paper tackles the problem of understanding how Transformers achieve in-context learning by demonstrating that they approximate second-order optimization methods, specifically Iterative Newton's Method, for linear regression, resulting in exponential speedup over Gradient Descent with each middle layer computing roughly 3 iterations.
Transformers excel at in-context learning (ICL) -- learning from demonstrations without parameter updates -- but how they do so remains a mystery. Recent work suggests that Transformers may internally run Gradient Descent (GD), a first-order optimization method, to perform ICL. In this paper, we instead demonstrate that Transformers learn to approximate second-order optimization methods for ICL. For in-context linear regression, Transformers share a similar convergence rate as Iterative Newton's Method, both exponentially faster than GD. Empirically, predictions from successive Transformer layers closely match different iterations of Newton's Method linearly, with each middle layer roughly computing 3 iterations; thus, Transformers and Newton's method converge at roughly the same rate. In contrast, Gradient Descent converges exponentially more slowly. We also show that Transformers can learn in-context on ill-conditioned data, a setting where Gradient Descent struggles but Iterative Newton succeeds. Finally, to corroborate our empirical findings, we prove that Transformers can implement $k$ iterations of Newton's method with $k + \mathcal{O}(1)$ layers.