  Neural sequence models based on the transformer architecture have
demonstrated remarkable \emph{in-context learning} (ICL) abilities, where they
can perform new tasks when prompted with training and test examples, without
any parameter update to the model. This work first provides a comprehensive
statistical theory for transformers to perform ICL. Concretely, we show that
transformers can implement a broad class of standard machine learning
algorithms in context, such as least squares, ridge regression, Lasso, learning
generalized linear models, and gradient descent on two-layer neural networks,
with near-optimal predictive power on various in-context data distributions.
Using an efficient implementation of in-context gradient descent as the
underlying mechanism, our transformer constructions admit mild size bounds, and
can be learned with polynomially many pretraining sequences.
  Building on these ``base'' ICL algorithms, intriguingly, we show that
transformers can implement more complex ICL procedures involving
\emph{in-context algorithm selection}, akin to what a statistician can do in
real life -- A \emph{single} transformer can adaptively select different base
ICL algorithms -- or even perform qualitatively different tasks -- on different
input sequences, without any explicit prompting of the right algorithm or task.
We both establish this in theory by explicit constructions, and also observe
this phenomenon experimentally. In theory, we construct two general mechanisms
for algorithm selection with concrete examples: pre-ICL testing, and post-ICL
validation. As an example, we use the post-ICL validation mechanism to
construct a transformer that can perform nearly Bayes-optimal ICL on a
challenging task -- noisy linear models with mixed noise levels.
Experimentally, we demonstrate the strong in-context algorithm selection
capabilities of standard transformer architectures.
