  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 higher-order
optimization methods for ICL. For in-context linear regression, Transformers
share a similar convergence rate as Iterative Newton's Method; both are
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.
