  In-context learning is a surprising and important phenomenon that emerged
when modern language models were scaled to billions of learned parameters.
Without modifying a large language model's weights, it can be tuned to perform
various downstream natural language tasks simply by including concatenated
training examples of these tasks in its input. Though disruptive for many
practical applications of large language models, this emergent learning
paradigm is not well understood from a theoretical perspective. In this paper,
we propose a first-of-its-kind PAC based framework for in-context learnability,
and use it to provide the first finite sample complexity results for the
in-context learning setup. Our framework includes an initial pretraining phase,
which fits a function to the pretraining distribution, and then a second
in-context learning phase, which keeps this function constant and concatenates
training examples of the downstream task in its input. We use our framework in
order to prove that, under mild assumptions, when the pretraining distribution
is a mixture of latent tasks (a model often considered for natural language
pretraining), these tasks can be efficiently learned via in-context learning,
even though the model's weights are unchanged and the input significantly
diverges from the pretraining distribution. Our theoretical analysis reveals
that in this setting, in-context learning is more about identifying the task
than about learning it, a result which is in line with a series of recent
empirical findings. We hope that the in-context learnability framework
presented in this paper will facilitate future progress towards a deeper
understanding of this important new learning paradigm.
