# Transformers as Algorithms:
Generalization and Implicit Model Selection in In-context Learning

Yingcong Li University of California, Riverside,
{yli692@,mildi001<EMAIL_ADDRESS>M. Emrullah Ildiz11footnotemark: 1
Dimitris Papailiopoulos University of Wisconsin-Madison<EMAIL_ADDRESS>Samet Oymak11footnotemark: 1

###### Abstract

In-context learning (ICL) is a type of prompting where a transformer model
operates on a sequence of (input, output) examples and performs inference on-
the-fly. This _implicit training_ is in contrast to explicitly tuning the
model weights based on examples. In this work, we formalize in-context
learning as an _algorithm learning_ problem, treating the transformer model as
a learning algorithm that can be specialized via training to implement—at
inference-time—another target algorithm. We first explore the statistical
aspects of this abstraction through the lens of multitask learning: We obtain
generalization bounds for ICL when the input prompt is (1) a sequence of
i.i.d. (input, label) pairs or (2) a trajectory arising from a dynamical
system. The crux of our analysis is relating the excess risk to the stability
of the algorithm implemented by the transformer, which holds under mild
assumptions. Secondly, we use our abstraction to show that transformers can
act as an adaptive learning algorithm and perform model selection across
different hypothesis classes. We provide numerical evaluations that (1)
demonstrate transformers can indeed implement near-optimal algorithms on
classical regression problems with i.i.d. and dynamic data, (2) identify an
inductive bias phenomenon where the transfer risk on unseen tasks is
independent of the transformer complexity, and (3) empirically verify our
theoretical predictions.

Keywords. in-context learning, generalization, model-selection, system
identification, transformers

##  1 Introduction

Figure 1:  Examples of in-context learning. We focus on the lower two settings
in the table where a transformer admits a supervised dataset or dynamical
system trajectory as a prompt. Then, it auto-regressively predicts the output
following an input example $\bm{x}_{i}$ based on the prompt
$(\bm{x}_{1},\dots,\bm{x}_{i})$.

Transformer (TF) models were originally developed for NLP problems to address
long-range dependencies through the attention mechanism. In recent years,
language models have become increasingly large, with some boasting billions of
parameters (e.g., GPT-3 has 175B, and PaLM has 540B parameters [7, 10]). It is
perhaps not surprising that these large language models (LLMs) have achieved
state-of-the-art performance on a wide range of natural language processing
tasks. What is surprising is the ability of some of these LLMs to perform _in-
context learning_(ICL), i.e., to adapt and perform a specific task given a
short prompt, in the form of instructions, and a small number of examples [7].
The ability of ICL to arise in these models without explicit training, allows
them to efficiently perform new tasks without the need for model weight
updates.

Specifically, ICL shows the ability of a TF to provide a prediction on an
example given a few (input, output) examples within a prompt. As depicted in
Figure 1, for NLP, the examples may correspond to pairs of (question,
answer)’s or translations. Recent works [20, 26] demonstrate that ICL can also
be used to infer general functional relationships. For instance, [22] aim to
solve supervised learning problems where we feed an entire training dataset
$(\bm{x}_{i},f(\bm{x}_{i}))_{i=1}^{n-1}$ as the input prompt, expecting that
conditioning the TF model on this prompt would allow it to infer an accurate
prediction for a new input point $\bm{x}_{n}$. As discussed in [20], this
provides a supervised-learning flavor to ICL, where the model _implicitly
trains_ on the data provided within the prompt, and performs inference on test
points.

Our work formalizes in-context learning from a statistical lens, abstracting
the transformer as a learning algorithm where the goal is inferring the
correct (input, ouput) functional relationship from prompts. We focus on a
meta-learning setting where the model is trained on many tasks, allowing ICL
to generalize to both new and previously-seen tasks. Our main contributions
are:

(a) Noisy linear regression

(b) Linear tasks with covariance prior

(c) Partially-observed LDS

Figure 2: Examples of implicit model-selection in three ICL settings: (a)
Noisy linear regression:
$y_{i}\sim{\cal{N}}(\bm{x}_{i}^{\top}{\bm{\beta}},\sigma^{2})$ with
$\bm{x}_{i},{\bm{\beta}}\sim{\cal{N}}(0,{\bm{I}})$. (b) Linear data with
covariance prior: $y_{i}=\bm{x}_{i}^{\top}{\bm{\beta}}$ with
${\bm{\beta}}\sim{\cal{N}}(0,{\bm{{\Sigma}}})$ with non-isotropic
${\bm{{\Sigma}}}$. (c) Partially observed linear dynamics:
$\bm{x}_{t}={\bm{C}}\bm{s}_{t}$ and
$\bm{s}_{t+1}\sim{\cal{N}}({\bm{A}}\bm{s}_{t},\sigma^{2}{\bm{I}})$ with
randomly sampled ${\bm{C}},{\bm{A}}$. Each setting trains a transformer with
large number of random regression tasks and evaluates on a new task from the
same distribution. In (a) and (b), ICL performances match Bayes-optimal
decision (weighted linear ridge regression) that adapt to noise level $\sigma$
and covariance prior ${\bm{{\Sigma}}}$ on the tasks. (c) shows that ICL
outperforms auto-regressive least-squares estimators with varying memory $H$.
Implicit model selection refers to transformer’s ability to implement a
competitive ML algorithm by leveraging the task prior learned during its
training. See Sec 7 for experimental details.

  * $\bullet$

Generalization bounds (Sec. 3 & 6): Suppose the model is trained on $T$ tasks
each with a data-sequence containing $n$ examples. During training, each
sequence is fed to the model auto-regressively as depicted in Figure 1. By
abstracting ICL as an _algorithm learning_ problem, we establish a multitask
(MTL) generalization rate of $1/\sqrt{nT}$. In order to achieve the proper
dependence on the sequence length ($1/\sqrt{n}$ factor), we overcome temporal
dependencies by relating generalization to algorithmic stability and we
provide numerical and theoretical evidence for the stability of transformer-
induced algorithms. Experiments demonstrate that ICL indeed benefits from
learning across the full task sequence in line with theory.

  * $\bullet$

From multitask to meta-learning (Sec. 4): We provide insights into how our MTL
bounds can inform generalization ability of ICL on previously unseen tasks
(i.e. transfer learning). Our experiments reveal an intriguing _inductive bias
phenomenon_ : The gap between the transfer risk and MTL risk is _independent
of the model complexity_ and only depends on the _task complexity_ and the
number of tasks $T$.

  * $\bullet$

Insights on model selection (Sec. 5): The _algorithm learning_ viewpoint
motivates model-selection as a natural feature of in-context learning (e.g.
whether to implement a linear model or neural net for prediction). We discuss
how this enables the selection of the correct hypothesis set for the tasks
when algorithms correspond to empirical risk minimization procedures. We
verify this model-selection ability through extensive experiments as
illustrated in Figure 2. Among others, the experiments reveal that
transformer-based algorithm can learn task covariance as a prior to compete
with optimally-weighted ridge and outperform least-squares of different orders
to learn partially-observed dynamical systems.

The remainder of the paper is organized as follows. The next section discusses
connections to prior art and Section 2 introduces the problem setup. Section 3
provides our main theoretical guarantees for ICL and stability of
transformers. Section 4 extends our arguments and experiments to the transfer
learning setting and Section 5 elucidates the implicit model/algorithm
selection ability of transformers via ICL. Section 6 extends our results to
learning stable dynamical systems where prompts correspond to temporally-
dependent system trajectories. Section 7 provides numerical evaluations, and
we discuss future work in Section 8.

###  1.1 Related work

In-context learning and transformers: With the success of large language
models, prompting methods has witnessed immense interest. ICL [7, 37] is a
prompting strategy where a transformer serves as an on-the-fly predictive
model through conditioning on a sequence of input/output examples
$(\bm{x}_{1},f(\bm{x}_{1}),\dots\bm{x}_{n-1},f(\bm{x}_{n-1}),\bm{x}_{n})$. Our
work is inspired by [20] which studies ICL in synthetic settings and
demonstrates transformers can serve as complex classifiers through ICL. In
parallel, [22] uses ICL as an AutoML (i.e. model-selection, hyperparameter
tuning) framework where they plug in a dataset to transformer and use it as a
classifier for new test points. Our formalism on _algorithm learning_ provides
a justification on how transformers can accomplish this with proper meta-
training. [57] interprets ICL as implicit Bayesian inference and develops
guarantees when the training distribution is a mixture of HMMs. Very recent
works [54, 2, 12] aim to relate ICL to running gradient descent algorithm over
the input prompt. [2] also provides related observations regarding the optimal
decision making ability of ICL for linear models. We remark that, for linear
regression problems, Bayes risk and optimal regularization schemes have been
investigated by earlier works [28, 41, 56]. [14] shows that language models
like GPT3 can be fine-tuned to perform competitively across a variety of non-
NLP tasks (e.g., classification and regression on tabular/vision/synthetic
data) where the training data is provided in the form of a language prompts,
in a similar manner to that of ICL. Unlike prior work, we provide finite
sample generalization guarantees for ICL and our theory extends to temporally-
dependent prompts (e.g. when prompts are trajectories of dynamical systems).
Dynamical systems in turn relate to the recent work by [26] who use ICL for
distilling reinforcement learning algorithms.

Multitask/Meta learning: In order for ICL to work well, the transformer model
needs to train with large amounts of related prompt instances. This makes it
inherently connected to meta learning [18]. However, a key distinction is
that, in ICL, adaptation to a new task happens implicitly through input
prompt. Our analysis has some parallels with recent literature on multitask
representation learning [33, 15, 50, 9, 27, 23, 40, 49, 11, 34, 16] since we
develop excess MTL risk bounds by training the model with $T$ tasks and
quantify these bounds in terms of complexity of the hypothesis space (i.e.
transformer architecture), the number of tasks $T$, and the number of samples
per task. In relation to [48, 8], our experiments on linear regression with
covariance-prior (Figure 2(b)) demonstrate ICL’s ability to implicitly
implement optimally-weighted linear representations.

Learning with temporal dependencies: Finally, our results require statistical
analysis of temporally dependent data as we create $n$ prompts from a dataset
of $n$ examples in an autoregressive fashion. This makes it related to recent
line of work on statistical aspects of time-series prediction and (non)linear
system identification ([46, 30, 13, 43, 25, 31, 52, 51, 44, 38, 19, 42] among
others). Our work has two distinguishing aspects over these. First, in the ICL
setting, the transformer is trained with multiple tasks simultaneously in
contrast to the traditional single-task supervised learning. Secondly, our
_algorithm learning_ formulation leads to new challenges and insights when
verifying the conditions to apply Azuma-type inequalities (e.g. Theorem 2).
Specifically, our results are facilitated through connections to _algorithmic
stability_ conditions [5, 6]. We also provide experiments and theory that
justify our stability conditions for transformer architectures both
empirically and theoretically (see Theorem 1).

##  2 Problem Setup

_Notation._ Let $\mathcal{X}$ be the input feature space, and $\mathcal{Y}$ be
the output/label space. We use boldface for vector variables. $[n]$ denotes
the set $\\{1,2,\dots,n\\}$. $c,C>0$ denote absolute constants and
$\|\cdot\|_{\ell_{p}}$ denotes the $\ell_{p}$-norm.

In-context learning setting: We denote a length-$m$ prompt containing $m-1$
in-context examples and the $m$’th input by
$\bm{x}^{(m)}_{\text{prompt}}=({\bm{z}}_{1},{\bm{z}}_{2},\dots,{\bm{z}}_{m-1},\bm{x}_{m})$.
Here $\bm{x}_{m}\in\mathcal{X}$ is the input to predict and
${\bm{z}}_{i}\in{\cal{Z}}$ is the $i$’th in-context example provided within
prompt. Let ${\texttt{TF}}(\cdot)$ denote a transformer (more generally an
auto-regressive model) that admits $\bm{x}^{(m)}_{\text{prompt}}$ as its input
and outputs a label
$\hat{\bm{y}}_{m}={\texttt{TF}}(\bm{x}^{(m)}_{\text{prompt}})$ in
$\mathcal{Y}$. Then the model aims to predict the next output denoted by
$\hat{\bm{y}}_{m}$. In this work, we investigate two scenarios where prompts
are obtained from a sequence of i.i.d. (input, label) pairs or a trajectory of
a dynamical system.

$\bullet$ _Independent $(\bm{x},\bm{y})$ pairs._ Similar to [20], we draw
i.i.d. samples
$(\bm{x}_{i},\bm{y}_{i})_{i=1}^{n}\in{\cal{Z}}=\mathcal{X}\times{\mathcal{Y}}$
from a data distribution. Then a length-$m$ prompt is written as
$\bm{x}^{(m)}_{\text{prompt}}=(\bm{x}_{1},\bm{y}_{1},\dots\bm{x}_{m-1},\bm{y}_{m-1},\bm{x}_{m})$,
and the model predicts
$\hat{\bm{y}}_{m}={\texttt{TF}}(\bm{x}^{(m)}_{\text{prompt}})\in{\mathcal{Y}}$
for $1\leq m\leq n$.

$\bullet$ _Dynamical systems._ In this setting, the prompt is simply the
trajectory generated by a dynamical system, namely,
$\bm{x}^{(m)}_{\text{prompt}}=(\bm{x}_{1},\dots\bm{x}_{m-1},\bm{x}_{m})$ and
therefore, ${\cal{Z}}=\mathcal{X}=\mathcal{Y}$. Specifically, we investigate
the state observed setting that is governed by dynamics $f(\cdot)$ via
$\bm{x}_{m+1}=f(\bm{x}_{m})+\text{noise}$. Here, $\bm{y}_{m}:=\bm{x}_{m+1}$ is
the label associated to $\bm{x}_{m}$, and the model admits
$\bm{x}^{(m)}_{\text{prompt}}$ as input and predicts the next state
$\hat{\bm{y}}_{m}:=\hat{\bm{x}}_{m+1}={\texttt{TF}}(\bm{x}^{(m)}_{\text{prompt}})\in\mathcal{X}$.

We first consider the training phase of ICL where we wish to learn a good
${\texttt{TF}}(\cdot)$ model through multitask learning (MTL). Suppose we have
$T$ tasks associated with data distributions $\\{{\cal{D}}_{t}\\}_{t=1}^{T}$.
Each task independently samples a training sequence
$\mathcal{S}_{t}=({\bm{z}}_{ti})_{i=1}^{n}$ according to its distribution.
${\mathcal{S}_{\text{all}}}=\\{\mathcal{S}_{t}\\}_{t=1}^{T}$ denote the set of
all training sequences. We use
${{\mathcal{S}}^{(m)}_{t}}=({\bm{z}}_{t1},\dots,{\bm{z}}_{tm})$ to denote a
subsequence of $\mathcal{S}_{t}:={{\mathcal{S}}^{(n)}_{t}}$ for $m\leq n$ and
${{\mathcal{S}}^{(0)}}$ denotes an empty subsequence.

ICL can be interpreted as an implicit optimization on the subsequence
${{\mathcal{S}}^{(m)}}=({\bm{z}}_{1},{\bm{z}}_{2},\dots,{\bm{z}}_{m})$ to make
prediction on $\bm{x}_{m+1}$. To model this, we abstract the transformer model
as a learning algorithm that maps a sequence of data to a prediction function
(e.g. gradient descent, empirical risk minimization). Concretely, let
$\mathcal{A}$ be a set of algorithm hypotheses such that algorithm
$\texttt{Alg}\in\mathcal{A}$ maps a sequence of form ${{\mathcal{S}}^{(m)}}$
into a prediction function
${f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}}}}:\mathcal{X}\rightarrow\mathcal{Y}$.
With this, we represent TF via

$\displaystyle{\texttt{TF}}(\bm{x}^{(m+1)}_{\text{prompt}})={f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}}}}(\bm{x}_{m+1}).$
(1)

This abstraction is without losing generality as we have the explicit relation
${f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}}}}(\bm{x}):={\texttt{TF}}(({{\mathcal{S}}^{(m)}},\bm{x}))$.
Given training sequences ${\mathcal{S}_{\text{all}}}$ and a loss function
$\ell(\bm{y},\hat{\bm{y}})$, the ICL training can be interpreted as searching
for the optimal algorithm $\texttt{Alg}\in\mathcal{A}$, and the training
objective is formulated as follows:

$\displaystyle{\widehat{\texttt{Alg}}}=\arg\min_{\texttt{Alg}\in\mathcal{A}}$
$\displaystyle{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg}):=\frac{1}{T}\sum_{t=1}^{T}{\widehat{\cal{L}}}_{t}(\texttt{Alg})$
(ICL-ERM) where
$\displaystyle{\widehat{\cal{L}}}_{t}(\texttt{Alg})=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{ti},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti})).$

Here, ${\widehat{\cal{L}}}_{t}(\texttt{Alg})$ is the training loss of task $t$
and ${\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg})$ is the
task-averaged MTL loss. Let
${\cal{L}}_{t}(\texttt{Alg})=\operatorname{\mathbb{E}}_{\mathcal{S}_{t}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})]$
and
${\cal{L}}_{\text{MTL}}(\texttt{Alg})=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg})]=\frac{1}{T}\sum_{t=1}^{T}{\cal{L}}_{t}(\texttt{Alg})$
be the corresponding population risks. Observe that, task-specific loss
${\widehat{\cal{L}}}_{t}(\texttt{Alg})$ is an empirical average of $n$ terms,
one for each prompt $\bm{x}^{(i)}_{\text{prompt}}$ and the corresponding label
$\bm{y}_{i}$.

To develop generalization bounds, our primary interest is controlling the gap
between empirical and population risks. For the problem (ICL-ERM), we wish to
bound the excess MTL risk

$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})={\cal{L}}_{\text{MTL}}({\widehat{\texttt{Alg}}})-\min_{\texttt{Alg}\in\mathcal{A}}{\cal{L}}_{\text{MTL}}(\texttt{Alg}).$
(MTL-risk)

Following the MTL training (ICL-ERM), we also evaluate the model on
previously-unseen tasks; this can be thought of as the transfer learning
problem. Concretely, let ${\cal{D}}_{\text{task}}$ be a distribution over
tasks and draw a target task $\mathcal{T}\sim{\cal{D}}_{\text{task}}$ with
data distribution ${\cal{D}}_{\mathcal{T}}$ and a sequence
$\mathcal{S}_{\mathcal{T}}=\\{{\bm{z}}_{i}\\}_{i=1}^{n}\sim{\cal{D}}_{\mathcal{T}}$.
Define the empirical and population risks on $\mathcal{T}$ as
${\widehat{\cal{L}}}_{\mathcal{T}}(\texttt{Alg})=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{i},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{\mathcal{T}}}}}(\bm{x}_{i}))$
and
${\cal{L}}_{\mathcal{T}}(\texttt{Alg})=\operatorname{\mathbb{E}}_{\mathcal{S}_{\mathcal{T}}}[{\widehat{\cal{L}}}_{\mathcal{T}}(\texttt{Alg})]$.
Then the transfer risk of an algorithm Alg is defined as
${\cal{L}}_{\text{TFR}}(\texttt{Alg})=\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})]$.
With this setup, we are ready to state our main contributions.

##  3 Generalization Guarantees for In-context Learning

In this section, we study the i.i.d. data setting with training sequences
$\mathcal{S}_{t}=(\bm{x}_{ti},\bm{y}_{ti})_{i=1}^{n}\overset{\text{i.i.d.}}{\sim}{\cal{D}}_{t}$
for $t\in[T]$ and establish generalization bounds for in-context learning.
Section 6 extends our results to dynamical systems.

#### Algorithmic Stability

In ICL a training example $(\bm{x}_{i},\bm{y}_{i})$ in the prompt impacts all
future decisions of the algorithm from predictions $i+1$ to $n$. This
necessitates us to control the stability to input perturbation of the learning
algorithm emulated by the transformer. Our stability condition is borrowed
from the algorithmic stability literature. As stated in [5, 6], the stability
level of an algorithm is typically in the order of $1/m$ (for realistic
generalization guarantees) where $m$ is the training sample size (in our
setting prompt length). This is formalized in the following assumption that
captures the variability of the transformer output.

######  Assumption 1 (Error Stability [6])

Let ${\mathcal{S}}=(\bm{x}_{1},\bm{y}_{1},\dots,\bm{x}_{m},\bm{y}_{m})$ be a
sequence with $m\geq 1$ and ${\mathcal{S}}^{j}$ be the sequence where the
$j$’th sample of ${\mathcal{S}}$ is replaced by
$(\bm{x}^{\prime}_{j},\bm{y}^{\prime}_{j})$. Error stability holds for a
distribution $(\bm{x},\bm{y})\sim{\cal{D}}$ if there exists a constant $K>0$
such that for any
${\mathcal{S}},(\bm{x}_{j}^{\prime},\bm{y}_{j}^{\prime})\in(\mathcal{X}\times\mathcal{Y})$,
$j\in[m]$, and $\texttt{Alg}\in\mathcal{A}$ we have

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\left|\operatorname{\mathbb{E}}_{(\bm{x},\bm{y})}\left[\ell(\bm{y},f^{\texttt{Alg}}_{\mathcal{S}}(\bm{x}))\right]-\operatorname{\mathbb{E}}_{(\bm{x},\bm{y})}\left[\ell(\bm{y},f^{\texttt{Alg}}_{{\mathcal{S}}^{j}}(\bm{x}))\right]\right|\leq\frac{K}{m}$}}.$
(2)

Let $\rho$ be a distance metric on $\mathcal{A}$. Pairwise error stability
holds if for all $\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}$ we have

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\left|\operatorname{\mathbb{E}}_{(\bm{x},\bm{y})}\left[\ell(\bm{y},f^{\texttt{Alg}}_{\mathcal{S}}(\bm{x}))-\ell(\bm{y},f^{\texttt{Alg}^{\prime}}_{\mathcal{S}}(\bm{x}))\right]-\operatorname{\mathbb{E}}_{(\bm{x},\bm{y})}\left[\ell(\bm{y},f^{\texttt{Alg}}_{{\mathcal{S}}^{j}}(\bm{x}))-\ell(\bm{y},f^{\texttt{Alg}^{\prime}}_{{\mathcal{S}}^{j}}(\bm{x}))\right]\right|\leq\frac{K\rho(\texttt{Alg},\texttt{Alg}^{\prime})}{m}$}}.$
(3)

Here (2) is our primary stability condition borrowed from [6] and ensures that
all algorithms $\texttt{Alg}\in\mathcal{A}$ are $K$-stable. We will also use
the stronger pairwise stability condition to develop tighter generalization
bounds. The following theorem shows that, under mild assumptions, a multilayer
transformer obeys the stability condition (2). The proof is deferred to
Appendix A.1 and Theorem 4.

###### Theorem 1

Let $\bm{x}^{(m)}_{\text{prompt}},\bm{x}^{\prime(m)}_{\text{prompt}}$ be two
prompts that differ only at the inputs ${\bm{z}}_{j}=(\bm{x}_{j},\bm{y}_{j})$
with ${\bm{z}}_{j}^{\prime}=(\bm{x}^{\prime}_{j},\bm{y}^{\prime}_{j})$. Assume
inputs and labels lie within the unit Euclidean ball in $\mathbb{R}^{d}$
111Here, we assume $\mathcal{X},\mathcal{Y}\subset\mathbb{R}^{d}$, otherwise,
inputs and labels are both embedded into $d$-dimensional vectors of proper
size.. Shape these prompts into matrices
${\bm{X}}_{\text{prompt}},{\bm{X}}^{\prime}_{\text{prompt}}\in\mathbb{R}^{(2m-1)\times
d}$ respectively. Let ${\texttt{TF}}(\cdot)$ be a transformer composed of $D$
layers followed by a linear head:
${\texttt{TF}}(\bm{x}^{(m)}_{\text{prompt}})=\left<{\bm{H}},{\bm{X}}_{(D)}\right>$.
Here ${\bm{X}}_{(i)}$ denotes the $i$’th layer output with
${\bm{X}}_{(0)}:={\bm{X}}_{\text{prompt}}$ and

${\bm{X}}_{(i)}=\texttt{Parallel\\_MLPs}(\texttt{ATTN}({\bm{X}}_{(i-1)}))\quad\text{where}\quad\texttt{ATTN}({\bm{X}}):=\text{softmax}({\bm{X}}^{\top}\bm{W}_{i}{\bm{X}}){\bm{X}}{\bm{V}}_{i},$

and softmax is row-wise. Assume TF is normalized to output $[-1,1]$ as
follows: $\|{\bm{V}}\|\leq 1$, $\|\bm{W}\|\leq\Gamma/2$, MLPs obey
$\texttt{MLP}(\bm{x})=\text{ReLU}({\bm{M}}\bm{x})$ with $\|{\bm{M}}\|\leq 1$,
and each row of ${\bm{H}}$ has Euclidean norm at most $1/m$. Then,

$|{\texttt{TF}}(\bm{x}^{(m)}_{\text{prompt}})-{\texttt{TF}}(\bm{x}^{\prime(m)}_{\text{prompt}})|\leq\frac{2}{2m-1}((1+\Gamma)e^{\Gamma})^{D}.$

Thus, assuming loss $\ell(\bm{y},\cdot)$ is $L$-Lipschitz, the algorithm
induced by ${\texttt{TF}}(\cdot)$ obeys (2) with
$K=2L((1+\Gamma)e^{\Gamma})^{D}$.

A few remarks are in place. First, the dependence on depth is exponential.
However this is not as prohibitive for typical transformer architectures which
tend to not be very deep. For example the different variants of GPT-2 and BERT
have between 12-48 [1] layers). Secondly, if the altered token has an
excessive influence on the prediction, this would disrupt the stability
condition. Our theorem avoids this via row-wise norm control of the output
layer ${\bm{H}}$ which ensures that input tokens contribute equally. We
anticipate the analysis can be extended to more realistic transformer
architectures (e.g. GPT-2 architecture used in our experiments) by
incorporating multiple attention-heads and causal masks. Finally, Figure 7
provides numerical evidence for multiple ICL settings that demonstrate that
stability of GPT-2 architecture’s predictions with respect to inputs indeed
improves with longer prompt length $m$ in line with our theory.

#### Generalization Bounds

We are ready to establish generalization bounds by leveraging our stability
conditions. We use covering numbers (i.e. metric entropy) to control model
complexity.

######  Definition 1 (Covering number)

Let ${\cal{Q}}$ be any hypothesis set and $d(q,q^{\prime})\geq 0$ be a
distance metric over $q,q^{\prime}\in{\cal{Q}}$. Then,
$\bar{\cal{Q}}=\\{q_{1},\dots,q_{N}\\}$ is an $\varepsilon$-cover of
${\cal{Q}}$ with respect to $d(\cdot,\cdot)$ if for any $q\in{\cal{Q}}$, there
exists $q_{i}\in\bar{\cal{Q}}$ such that $d(q,q_{i})\leq\varepsilon$. The
$\varepsilon$-covering number ${\cal{N}}({\cal{Q}},d,\varepsilon)$ is the
cardinality of the minimal $\varepsilon$-cover.

To cover the algorithm space $\mathcal{A}$, we need to introduce a distance
metric. We formalize this in terms of the prediction difference between two
algorithms on the worst-case data-sequence.

######  Definition 2 (Algorithm distance)

Let $\mathcal{A}$ be an algorithm hypothesis set and
$\mathcal{S}=(\bm{x}_{i},\bm{y}_{i})_{i=1}^{n}$ be a sequence with $n$
examples that is admissible for some task $t\in[T]$. For any pair
$\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}$, define the distance metric
$\rho(\texttt{Alg},\texttt{Alg}^{\prime}):=\sup_{\mathcal{S}}\frac{1}{n}\sum_{i=1}^{n}\|{{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}}}}(\bm{x}_{i})-{f^{\texttt{Alg}^{\prime}}_{{{\mathcal{S}}^{(i-1)}}}}(\bm{x}_{i})}\|_{\ell_{2}}$.

We note that the distance $\rho$ is controlled by the Lipschitz constant of
the transformer architecture (i.e. largest gradient norm with respect to the
model weights). Following Definitions 1&2, the $\varepsilon$-covering number
of the hypothesis set $\mathcal{A}$ is
${\cal{N}}(\mathcal{A},\rho,\varepsilon)$. This brings us to our main result
on MTL risk of (ICL-ERM).

###### Theorem 2

Suppose $\mathcal{A}$ is $K$-stable per Assumption 1 and the loss function
$\ell(\bm{y},\cdot)$ is $L$-Lipschitz for all $\bm{y}\in\mathcal{Y}$ and takes
values over $[0,1]$. Let ${\widehat{\texttt{Alg}}}$ be the empirical solution
of (ICL-ERM). Then, with probability at least $1-2\delta$, the excess MTL test
risk obeys

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq\inf_{\varepsilon>0}\left\\{4L\varepsilon+2(1+K\log
n)\sqrt{\frac{\log{\cal{N}}(\mathcal{A},\rho,\varepsilon)+\log(1/\delta)}{cnT}}\right\\}$}}.$
(4)

Additionally suppose $\mathcal{A}$ is $K$-pairwise-stable and set diameter
$D:=\sup_{\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}}\rho(\texttt{Alg},\texttt{Alg}^{\prime})$.
Using the convention $x_{+}=\max(x,1)$, with probability at least $1-4\delta$,

(5)

The first bound (4) achieves $1/\sqrt{nT}$ rate by covering the algorithm
space with resolution $\varepsilon$. For Lipschitz architectures with
$\text{dim}(\mathcal{A})$ trainable weights we have
$\log{\cal{N}}(\mathcal{A},\rho,\varepsilon)\sim\text{dim}(\mathcal{A})\log(1/\varepsilon)$.
Thus, up to logarithmic factors, the excess risk is bounded by
$\sqrt{\frac{\text{dim}(\mathcal{A})}{nT}}$ and will vanish as $n,T\to\infty$.
Recalling (1), this can also be seen as a generalization bound for general
auto-regressive models that learns from sequential data.

Note that $\rho$ in Def. 2 is task-dependent. For instance, suppose tasks are
realizable with labels $\bm{y}=f(\bm{x})$ and admissible task sequences have
the form $\mathcal{S}=(\bm{x}_{i},f(\bm{x}_{i}))_{i=1}^{n}$. Then, $\rho$ will
depend on the function class of $f$ (e.g. whether tasks $f$ are linear models,
neural nets, etc), specifically, as the function class becomes richer, both
$\rho$ and the covering number becomes larger. Under the stronger pairwise-
stability, we can obtain a bound in terms of the Dudley entropy integral which
arises from a chaining argument. This bound is typically in the same order as
the Rademacher complexity of the function class with $T\times n$ samples [55].
Note that achieving $1/\sqrt{T}$ dependence is rather straightforward as tasks
are sampled independently. Thus, the main feature of Theorem 2 is obtaining
the multiplicative $1/\sqrt{n}$ term by overcoming temporal dependencies.
Figure 3 shows that training with full sequence is indeed critical for ICL
accuracy.

(a) ICL trained with $10$ prompts over a range

(b) ICL with all $n=40$ prompts

Figure 3: The value of learning across the full sequence: Right side: Standard
ICL-ERM where each task trains with all $n=40$ prompts (full task sequence).
Left side: ICL-ERM focuses on different parts of the trajectory by fitting
$n/4=10$ prompts per task over $i\in[1,10]$ to $[31,40]$ (highlighted as the
orange ranges). We train with $T=500000$ random linear regression tasks and
display the performance on new tasks from the same prior (i.e. transfer risk).
Right side learns to solve linear regression via ICL whereas left side fails
to do so even when restricted to their target ranges.

Proof sketch. Let $\texttt{Alg}^{\star}$ be the population MTL minima. We
first decompose ${R_{\text{MTL}}}({\widehat{\texttt{Alg}}})$ as follows:

$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})=\underset{a}{\underbrace{{\cal{L}}_{{\text{MTL}}}({\widehat{\texttt{Alg}}})-{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}({\widehat{\texttt{Alg}}})}}+\underset{b}{\underbrace{{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}({\widehat{\texttt{Alg}}})-{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg}^{\star})}}+\underset{c}{\underbrace{{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg}^{\star})-{\cal{L}}_{{\text{MTL}}}(\texttt{Alg}^{\star})}}$

where $b\leq 0$ by definition. Regarding $(a)$ and $(c)$, we need a
concentration bound on
$|{\cal{L}}_{{\text{MTL}}}(\texttt{Alg})-{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg})|$
for a fixed algorithm $\texttt{Alg}\in\mathcal{A}$. To achieve this bound, we
introduce the sequence of variables
$X_{t,i}=\operatorname{\mathbb{E}}\left[\frac{1}{n}\sum_{j=1}^{n}\ell(\bm{y}_{tj},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}_{t}}}}(\bm{x}_{tj}))~{}\big{|}~{}{{\mathcal{S}}^{(i)}_{t}}\right]$
for $0\leq i\leq n$, which form a martingale by construction.

The critical stage is upper bounding the martingale differences
$|X_{t,i}-X_{t,i-1}|$ through our stability assumption, namely, increments are
at most $1+\sum_{j=i}^{n}\frac{K}{j}\lesssim 1+K\log n$. Then, we utilize
Azuma-Hoeffding’s inequality to achieve a concentration bound on
$\left|\frac{1}{T}\sum_{t=1}^{T}X_{t,0}-X_{t,n}\right|$, which is equivalent
to
$|{\cal{L}}_{{\text{MTL}}}(\texttt{Alg})-{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg})|$.
To conclude, we make use of covering/chaining arguments to establish a uniform
concentration bound on
$|{\cal{L}}_{{\text{MTL}}}(\texttt{Alg})-{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg})|$
for all $\texttt{Alg}\in\mathcal{A}$.

Multiple sequences per task. Finally consider a setting where each task is
associated with $M$ independent sequences with size $n$. This typically arises
in reinforcement learning problems (e.g. dynamical systems in Sec. 6) where we
collect data through multiple rollouts each leading to independent sequences.
In this setting, statistical error rate improves to $1/\sqrt{nMT}$ as
discussed in Appendix B.1. In the next section, we will contrast MTL vs
transfer learning by letting $M\rightarrow\infty$. This way, even if $n$ and
$T$ are fixed, the model will fully learn the $T$ source tasks during the MTL
phase as the excess risk vanishes with $M\rightarrow\infty$.

##  4 Generalization and Inductive Bias on Unseen Tasks

In this section, we explore transfer learning to assess the performance of in-
context learning across new tasks: the MTL phase generates a pretrained model
${\widehat{\texttt{Alg}}}$ trained on $T$ source tasks and we use
${\widehat{\texttt{Alg}}}$ to predict a target task $\mathcal{T}$. To start
with, we consider a standard meta-learning setup where $T$ sources are drawn
from the task distribution ${\cal{D}}_{\text{task}}$ and we evaluate the
transfer risk on new tasks $\mathcal{T}\sim{\cal{D}}_{\text{task}}$. We are
interested in controlling the transfer risk
${\cal{L}}_{\text{TFR}}({\widehat{\texttt{Alg}}})=\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]$
in terms of the MTL risk ${\cal{L}}_{\text{MTL}}({\widehat{\texttt{Alg}}})$.
Since the source tasks are i.i.d, we have
$\operatorname{\mathbb{E}}_{\text{source}}[{\cal{L}}_{\text{MTL}}({\widehat{\texttt{Alg}}})]={\cal{L}}_{\text{TFR}}({\widehat{\texttt{Alg}}})$.
More specifically, one can use a standard generalization analysis to control
the transfer risk in terms of MTL risk as follows

$\left|{\cal{L}}_{\text{TFR}}({\widehat{\texttt{Alg}}})-{\cal{L}}_{\text{MTL}}({\widehat{\texttt{Alg}}})\right|\lesssim\sqrt{\frac{\text{dim}(\mathcal{A})}{T}}.$

Here, $\text{dim}(\mathcal{A})$ captures the complexity of the algorithm space
(e.g. as formalized in Theorem 7 in Appendix B.3, one can use covering numbers
similar to Theorem 2). Here, an important distinction with MTL is that
transfer risk decays as $1/\text{poly}(T)$ because the unseen tasks induce a
distribution shift which, typically, cannot be mitigated with more samples $n$
or more sequences $M$.

(a) $d=5$

(b) $d=10$

(c) $d=20$

(d) $d=5,10,20$ overlayed

Figure 4: In Figures (a,b,c,), we plot the $d\in\\{5,10,20\\}$-dimensional
results for transfer and MTL risk curves. Figure (d) overlays (a,b,c) to
reveal that transfer risks are aligned for fixed $(n/d,T/d^{2})$ choice.

$\bullet$ Inductive Bias in Transfer Risk. Before investigating distribution
shift, let us consider the following question: While $1/\text{poly}(T)$
behavior may be unavoidable, is it possible that dependence on architectural
complexity $\text{dim}(\mathcal{A})$ is avoidable? Perhaps surprisingly, we
answer this question affirmatively through experiments on linear regression.
In what follows, during MTL pretraining, we train with $M\rightarrow\infty$
independent sequences per task to minimize population MTL risk
${\cal{L}}_{\text{MTL}}(\cdot)$. We then evaluate resulting
${\widehat{\texttt{Alg}}}$ on different dimensions $d$ and numbers of MTL
tasks $T$. Figures 4(a,b,c) display the MTL and transfer risks for dimensions
$d=5,10,20$. In each figure, we evaluate the results on $T=\\{1,2,5\\}\times
d^{2}$ and the $x$-axis moves from $0$ to $n=2d$. Each task has isotropic
features, noiseless labels and task vectors
${\bm{\beta}}\sim\mathcal{N}(0,{\bm{I}}_{d})$. Here, our first observation is
that, the Figures 4(a,b,c) seem (almost perfectly) aligned with each other,
that is, each figure exhibits identical MTL and transfer risk curves.

To further elucidate this, Figure 4(d) integrates the transfer risk curves
from $d=5,10,20$ and overlays them together. This alignment indicates that,
for a fixed point $\alpha=n/d$ and $\beta=T/d^{2}$, the transfer risks remain
unchanged. Here, $n$ proportional to $d$ can be attributed to linearity, thus,
the more surprising aspect is the dependence on number of tasks $T$ since this
indicates that, rather than $\frac{\text{dim}(\mathcal{A})}{T}$, the
generalization risk behaves like $\frac{d^{2}}{T}$. In words, rather than
model complexity, what matters is the problem complexity $d$.

Inductive bias is a natural explanation of this behavior: Intuitively, the MTL
pretraining process identifies a favorable algorithm that lies in the span of
the source tasks ${\bm{\Theta}}_{{\text{MTL}}}=({\bm{\beta}}_{t})_{t=1}^{T}$.
Specifically, while the transformer model can potentially fit MTL tasks
through a variety of algorithms, we speculate that the optimization process is
implicitly biased (akin to implicit regularization literature [47, 36, 3]) to
an algorithm $\texttt{Alg}({\bm{\Theta}}_{{\text{MTL}}})$. Such bias would
explain the lack of $\text{dim}(\mathcal{A})$ dependence since
$\texttt{Alg}({\bm{\Theta}}_{{\text{MTL}}})$ solely depends on the source
tasks. We leave the theoretical exploration of the empirical $d^{2}/T$
behavior to a future work. However, we provide further discussion on why it is
rather surprising both from MTL and transfer learning perspectives.

To this end, let us first introduce the optimal estimator for linear
regression with Gaussian task prior.

_Minimum Bayes risk:_ The optimal prediction in terms of average risk can be
described explicitly [41, 28] under prior
${\bm{\beta}}\sim{\cal{N}}(0,{\bm{{\Sigma}}})$ and is given by the optimally-
weighted ridge regression solution

$\displaystyle\hat{{\bm{\beta}}}=({\bm{X}}^{\top}{\bm{X}}+\sigma^{2}{\bm{{\Sigma}}}^{-1})^{-1}{\bm{X}}^{\top}\bm{y},$
(6)

Here ${\bm{X}}=[\bm{x}_{1},\dots,\bm{x}_{n}]^{\top}\in\mathbb{R}^{n\times
d},\bm{y}=[\bm{y}_{1},\dots,\bm{y}_{n}]^{\top}\in\mathbb{R}^{n}$ are the
concatenated features and labels obtained from the task sequence and
$\sigma^{2}$ is the label noise variance. With this in mind, what is the ideal
algorithm $\texttt{Alg}({\bm{\Theta}}_{{\text{MTL}}})$ based on the (perfect)
knowledge of source tasks? Eqn. (6) crucially requires the knowledge of the
task covariance ${\bm{{\Sigma}}}$ and variance $\sigma^{2}$. Thus, even with
the hindsight knowledge that we are dealing with a linear problem, we have to
estimate the task covariance from source tasks. This can be done by
constructing the empirical covariance
$\hat{{\bm{{\Sigma}}}}=\frac{1}{T}\sum_{i=1}^{T}{\bm{\beta}}_{i}{\bm{\beta}}_{i}^{\top}$.
To make sure that $\hat{{\bm{{\Sigma}}}}$-weighted LS performs
${\cal{O}}(1)$-close to ${\bm{{\Sigma}}}$-weighted LS, we need a spectral norm
control, namely,
${\|{\bm{{\Sigma}}}-\hat{{\bm{{\Sigma}}}}\|}/{\lambda_{\min}({\bm{{\Sigma}}})}\leq{\cal{O}}(1)$.
When ${\bm{{\Sigma}}}={\bm{I}}_{d}$ (as in our experiments) and tasks are
isotropic, the latter condition holds with high probability when
$T=\Omega(d)$. This is also numerically demonstrated in Figure 8 in the
appendix. This behavior is in contrast to the stronger $T\propto d^{2}$
requirement we observe for ICL. For instance, $T\propto d^{2}$ is sufficient
to ensure the stronger entrywise control
$\|{{\bm{{\Sigma}}}-\hat{{\bm{{\Sigma}}}}}\|_{\ell_{\infty}}\leq O(1)$ rather
than spectral norm.

Let us now ask the same question for the MTL algorithm: If the transformer
perfectly learns the MTL tasks
${\bm{\Theta}}_{{\text{MTL}}}=({\bm{\beta}}_{t})_{t=1}^{T}$, it does not
actually need $n=\Omega(d)$ samples to perform well on new prompts drawn from
source tasks. To see this, consider the following algorithm: Given a prompt,
$\texttt{Alg}({\bm{\Theta}}_{{\text{MTL}}})$ conducts a discrete search over
$({\bm{\beta}}_{t})_{t=1}^{T}$ and returns the source task that best fits to
the prompt. Thanks to the discrete search space, it is not hard to see that,
we need $n\propto\log(T)$ samples rather than $n\propto d$ (also see Figure
8). In contrast, based on Figures 4(a,b,c), MTL behaves closer to $n\propto d$
empirically. On the other hand, $\texttt{Alg}({\bm{\Theta}}_{{\text{MTL}}})$
implemented by the transformer is rather intelligent: This is because MTL
risks for $d\in\\{5,10,20\\}$ are all strictly better than implementing least-
squares222Ordinary least-squares achieves the minimum risk for transfer
learning ($T=\infty$) however it is not optimal for finite $T$. and the
performance improves as $T$ gets smaller. We leave the thorough exploration of
the inductive bias of the MTL training and characterization of
$\texttt{Alg}({\bm{\Theta}}_{{\text{MTL}}})$ as an intriguing future
direction.

Figure 5: Transfer risk as a function of distance to the MTL tasks.

$\bullet$ Exploring transfer risk in terms of distance. Besides drawing source
and target tasks from the same ${\cal{D}}_{\text{task}}$, we can also
investigate transfer risk in an instance specific fashion. Specifically, the
population risk of a new task $\mathcal{T}$ can be bounded as
${\cal{L}}_{\mathcal{T}}(\texttt{Alg})\leq{\cal{L}}_{{\text{MTL}}}(\texttt{Alg})+\text{dist}(\mathcal{T},({\cal{D}}_{t})_{t=1}^{T})$.
Here, $\text{dist}(\cdot)$ assesses the (distributional) distance of task
$\mathcal{T}$ to the source tasks $({\cal{D}}_{t})_{t=1}^{T}$ (e.g. [4, 21]).
In case of linear tasks, we can simply use the Euclidean distance between task
vectors, specifically, the distance of target weights
${\bm{\beta}}_{\mathcal{T}}$ to the nearest source task
$\text{dist}(\mathcal{T})=\min_{t\in[T]}\|{{\bm{\beta}}_{\mathcal{T}}-{\bm{\beta}}_{t}}\|_{\ell_{2}}$.
In Fig. 5 we investigate the distance of specific target tasks from source
tasks and how the distance affects the transfer performance. Here, all source
and target tasks have unit Euclidean norms so that closer distance is
equivalent to larger cosine similarity. We again train each MTL task with
multiple sequences $M\rightarrow\infty$ (as in Fig. 4) and use $T=20$ source
tasks with $d=5$ dimensional regression problems. In a nutshell, Figure 5
shows that task similarity (based on $\ell_{2}$ distance) is indeed highly
predictive of transfer performance across different distance slices (namely
$[0,0.2],[0.2,0.6],[0.6,1],[1,2]$). An intriguing question is identifying the
broader conditions under which transfer risk can be rigorously related to the
MTL risk, which is further discussed in Appendix B.2.

##  5 Insights on Model Selection

In Section 3, we study the generalization error of ICL, which can be
eliminated by increasing sample size $n$ or number of sequences $M$ per task.
In this section, we will discuss implicit model selection in ICL building on
the formalism that transformer is a learning algorithm. Following Figure 2 and
prior works [20, 26, 22], a plausible assumption is that, transformer can
implement ERM algorithms up to a certain accuracy. Then, model selection can
be formalized by the selection of the right hypothesis class so that running
ERM on that hypothesis class can strike a good bias-variance tradeoff during
ICL.

To proceed with our discussion, let us consider the following hypothesis which
states that transformer can implement an algorithm competitive with ERM.

###### Hypothesis 1

Let $\mathbb{F}=(\mathcal{F}_{h})_{h=1}^{H}$ be a family of $H$ hypothesis
classes. Let $\mathcal{S}=(\bm{x}_{i},\bm{y}_{i})_{i=1}^{n}$ be a data-
sequence with $n$ examples sampled i.i.d. from ${\cal{D}}$ and let
${{\mathcal{S}}^{(m)}}=(\bm{x}_{i},\bm{y}_{i})_{i=1}^{m}$ be the first $m$
examples. Consider the risk333Since the loss $\ell$ is bounded by $1$,
$0\leq\text{risk}(h,m)\leq 1$ for all $m$ including the scenario $m=0$ and ERM
is vacuous. associated to ERM with $m$ samples over
$\mathcal{F}_{h}\in\mathbb{F}$:

$\text{risk}(h,m)=\operatorname{\mathbb{E}}_{(\bm{x},\bm{y},{{\mathcal{S}}^{(m)}})}[\ell(\bm{y},\hat{f}^{(h)}_{{{\mathcal{S}}^{(m)}}}(\bm{x}))]\quad\text{where}\quad\hat{f}^{(h)}_{{{\mathcal{S}}^{(m)}}}=\arg\min_{f\in\mathcal{F}_{h}}\frac{1}{m}\sum_{i=1}^{m}\ell(\bm{y}_{i},f(\bm{x}_{i})),$

Let $(\varepsilon_{{\texttt{TF}}}^{h,m})>0$ be approximation errors associated
with $(\mathcal{F}_{h})_{h=1}^{H}$. There exists $\texttt{Alg}\in\mathcal{A}$
such that, for any $m\in[n],h\in[H]$,
$f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}}}$ can approximate ERM in terms of
population risk, i.e.

$\operatorname{\mathbb{E}}_{(\bm{x},\bm{y},{{\mathcal{S}}^{(m)}})}[\ell(\bm{y},f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}}}(\bm{x}))]\leq\text{risk}(h,m)+\varepsilon_{{\texttt{TF}}}^{h,m}.$

For model selection purposes, these hypothesis classes can be entirely
different ML models, for instance, $\mathcal{F}_{1}=\\{\text{convolutional-
nets}\\}$, $\mathcal{F}_{2}=\\{\text{fully-connected-nets}\\}$, and
$\mathcal{F}_{3}=\\{\text{decision-trees}\\}$. Alternatively, they can be a
nested family useful for capacity control purposes. For instance, Figures
2(a,b) are learning covariance/noise priors to implement a constrained-ridge
regression. Here $\mathbb{F}$ can be indexed by positive-definite matrices
${\bm{{\Sigma}}}$ with linear classes of the form
$\mathcal{F}_{\bm{{\Sigma}}}=\\{f(\bm{x})=\bm{x}^{\top}{\bm{\beta}}\quad\text{where}\quad{\bm{\beta}}^{\top}{\bm{{\Sigma}}}^{-1}{\bm{\beta}}\leq
1\\}$.

Under Hypothesis 1, ICL selects the most suitable class that minimizes the
excess risk for each $m\in[n]$.

###### Observation 1

Suppose Hypothesis 1 holds for a target distribution
${\cal{D}}_{\mathcal{T}}$. Let
${\cal{L}}_{\mathcal{T}}^{\star}:=\min_{\texttt{Alg}\in\mathcal{A}}{\cal{L}}_{\mathcal{T}}(\texttt{Alg})$
be the risk of the optimal algorithm. We have that

${\cal{L}}_{\mathcal{T}}^{\star}\leq\frac{1}{n}\sum_{m=0}^{n-1}\min_{h\in[H]}\\{\text{risk}(h,m)+\varepsilon_{{\texttt{TF}}}^{h,m}\\}.$

Additionally, denote Rademacher complexity of a class $\mathcal{F}$ by
$\mathcal{R}_{m}(\mathcal{F})$. Define the minimum achievable risk over
function set $\mathcal{F}_{h}$ as
${\cal{L}}^{\star}_{h}:=\min_{f\in\mathcal{F}_{h}}\operatorname{\mathbb{E}}_{{\cal{D}}_{\mathcal{T}}}[\ell(\bm{y},f(\bm{x}))]$.
Since $\text{risk}(h,m)$ is controlled by $\mathcal{R}_{m}(\mathcal{F}_{h})$
[35], we have that

${{\cal{L}}_{\mathcal{T}}^{\star}\leq\frac{1}{n}\sum_{m=0}^{n-1}\min_{h\in[H]}\\{{\cal{L}}^{\star}_{h}+\varepsilon_{{\texttt{TF}}}^{h,m}+{\cal{O}}(\mathcal{R}_{m}(\mathcal{F}_{h}))\\}.}$

Here, ICL adaptively selects the classes
$\arg\min_{h\in[H]}\\{{\cal{L}}^{\star}_{h}+\mathcal{R}_{m}(\mathcal{F}_{h})+\varepsilon_{{\texttt{TF}}}^{h,m}\\}$
to achieve small risk. This is in contrast to training over a single large
class $\mathcal{F}=\bigcup_{i=1}^{H}\mathcal{F}_{i}$, which would result in a
less favorable bound
${\approx\min_{h\in[H]}{\cal{L}}^{\star}_{h}+\frac{1}{n}\sum_{m=0}^{n-1}\mathcal{R}_{m}(\mathcal{F})}$.
A formal version of this statement is provided in Appendix B.4. Hypothesis 1
assumes a discrete family for simpler exposition ($|\mathbb{F}|=H<\infty$),
however, our theory in Section 3 allows for the continuous setting.

We emphasize that, in practice, we need to adapt the hypothesis classes for
different sample sizes $m$ (typically, more complex classes for larger $m$).
With this in mind, while we have $H$ classes in $\mathbb{F}$, in total we have
$H^{n}$ different ERM algorithms to compete against. This means that VC-
dimension of the algorithm class is as large as $n\log H$. This highlights an
insightful benefit of our main result: Theorem 2 would result in an excess
risk $\propto\sqrt{\frac{n\log H}{nT}}=\sqrt{\frac{\log H}{T}}$. In other
words, the additional $\times n$ factor achieved through Theorem 2 facilitates
the adaptive selection of hypothesis classes for each sample size and avoids
requiring unreasonably large $T$.

##  6 Extending Results to Stable Dynamical Systems

Until now, we have studied ICL with sequences of i.i.d. (input, label) pairs.
In this section, we investigate the scenario where prompts are obtained from
the trajectories of stable dynamical systems, thus, they consist of dependent
data. Let $\mathcal{X}\subset\mathbb{R}^{d}$ and
$\mathcal{F}:\mathcal{X}\rightarrow\mathcal{X}$ be a hypothesis class elements
of which are dynamical systems. During MTL phase, suppose that we are given
$T$ tasks associated with $(f_{t})_{t=1}^{T}$ where $f_{t}\in\mathcal{F}$, and
each contains $n$ in-context samples. Then, the data-sequence of $t$’th task
is denoted by $\mathcal{S}_{t}=(\bm{x}_{ti})_{i=0}^{n}$ where
$\bm{x}_{ti}=f_{t}(\bm{x}_{t,i-1})+\bm{w}_{ti}$, $\bm{x}_{t0}$ is the initial
state, and $\bm{w}_{ti}\in{\cal{W}}\subset\mathbb{R}^{d}$ are bounded i.i.d.
random noise following some distribution. Then, prompts are given by
$\bm{x}^{(i)}_{\text{prompt}}:=(\bm{x}_{0},\bm{x}_{1},\dots\bm{x}_{i})$. Let
${{\mathcal{S}}^{(i)}}=\bm{x}^{(i)}_{\text{prompt}}$, and we can make
prediction
$\hat{\bm{x}}_{ti}={f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{t,{i-1}})$.
We consider the similar optimization problem as (ICL-ERM).

In order to perform the analysis of generalization error in a dynamical
system, we need this system to be stable (which differs from algorithmic
stability!). In this work, we use an exponential stability condition that
controls the distance between two trajectories initialized from different
points [45, 24].

######  Definition 3 ($(C_{\rho},\rho)$-stability)

Denote the state of dynamical system resulting from initial state
$\bm{x}_{t0}$ and $(\bm{w}_{ti})_{i=1}^{m}$ by
$f_{t}^{(m)}(\bm{x}_{t0})\in\mathcal{X}$. Let $C_{\rho}\geq 1$ and
$\rho\in(0,1)$ be system related constants. We say that the dynamical system
for the task $t$ is $(C_{\rho},\rho)$-stable if, for all
$\bm{x}_{t0},\bm{x}^{\prime}_{t0}\in\mathcal{X}$, $m\geq 1$, and
$(\bm{w}_{ti})_{i\geq 1}\in{\cal{W}}$, we have

$\displaystyle\left\|f_{t}^{(m)}(\bm{x}_{t0})-f_{t}^{(m)}(\bm{x}^{\prime}_{t0})\right\|_{\ell_{2}}\leq
C_{\rho}\rho^{m}\left\|\bm{x}_{t0}-\bm{x}^{\prime}_{t0}\right\|_{\ell_{2}}$
(7)

###### Assumption 2

There exist $\bar{C}_{\rho}$ and $\bar{\rho}<1$ such that all dynamical
systems $f\in\mathcal{F}$ are $(\bar{C}_{\rho},\bar{\rho})$-stable.

In addition to the stability of the hypothesis set $\mathcal{F}$, we also
leverage the algorithmic-stability of the set $\mathcal{A}$ similar to
Assumption 1. Different from Assumption 1, we restrict the variability of the
transformer with respect to Euclidean distance metric, similar to the
definition of Lipschitz stability.

######  Assumption 3 (Algorithmic-stability for Dynamical Systems)

Let ${\mathcal{S}}=(\bm{x}_{0},\bm{x}_{1},\dots,\bm{x}_{m})$ be any dynamical
sequence with $m\geq 1$ and ${\mathcal{S}}^{j}$ be the sequence such that
$\bm{w}_{j}$ is replaced by $\bm{w}_{j}^{\prime}$ ($j=0$ implies that
$\bm{x}_{0}$ is replaced by $\bm{x}^{\prime}_{0}$). As a result, starting with
the $j$’th until the $m$’th index, the sequence ${\mathcal{S}}^{j}$ has
different samples $(\bm{x}^{\prime}_{j},\dots,\bm{x}^{\prime}_{m})$. There
exists a constant $K>0$ such that for any ${\mathcal{S}}$,
$\bm{x}_{0}^{\prime}\in\mathcal{X}$, $\bm{w}^{\prime}_{j}\in{\cal{W}}$, and
$j\in[m]$, we have

$\displaystyle\left|\operatorname{\mathbb{E}}_{\bm{w}_{m+1}}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{\mathcal{S}}}(\bm{x}_{m}))\right]-\operatorname{\mathbb{E}}_{\bm{w}_{m+1}}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{\mathcal{S}}^{j}}(\bm{x}_{m^{\prime}}))\right]\right|\leq\frac{K}{m}\sum_{i=j}^{m}\left\|\bm{x}_{i}-\bm{x}^{\prime}_{i}\right\|_{\ell_{2}}.$
(8)

Theorem 4 in the appendix justifies this assumption for multilayer transformer
architectures. To proceed, we state the main result of this section.

###### Theorem 3

Suppose the loss function
$\ell(\bm{x},\cdot):\mathcal{X}\times\mathcal{X}\rightarrow[0,1]$ is
$L$-Lipschitz for all $\bm{x}\in\mathcal{X}$ and Assumptions 2&3 hold. Assume
$\mathcal{X}$ and ${\cal{W}}$ are bounded by $\bar{x},\bar{w}$, respectively.
Then, with the same probability, the identical bound as in Theorem 2 Eqn. (4)
holds after updating $K$ to be
$\bar{K}=2K\frac{\bar{C}_{\rho}}{1-\bar{\rho}}(\bar{w}+\bar{x}/\sqrt{n})$.

The proof of this result is similar to that of Theorem 2 and can be found in
Appendix C. The primary difference occurs when bounding the martingale
differences $|X_{t,i}-X_{t,i-1}|$. In the stable dynamical settings, to bound
Martingale’s increments, we utilize independence of noise and stability of the
system instead of using the independence of input and output pairs. One can
also obtain an entropy integral bound akin to (5) using a proper variation of
the pairwise algorithmic-stability condition in Assumption 1 Eqn. (3).

##  7 Numerical Evaluations

Our experimental setup follows [20]: All ICL experiments are trained and
evaluated using the same GPT-2 architecture with 12 layers, 8 attention heads,
and 256 dimensional embeddings. Most of our experiments are based on linear
regression problems and linear dynamics. We first provide the details and
discussions of Figure 2 and then provide additional experiments aligned with
our findings.

$\bullet$ Linear regression (Figures 2(a,b)). We consider a $d$-dimensional
linear regression tasks with in-context examples of the form
${\bm{z}}=(\bm{x},y)\in\mathbb{R}^{d}\times\mathbb{R}$. Given $t$’th task
${\bm{\beta}}_{t}$, we generate $n$ i.i.d. samples via
$y={\bm{\beta}}_{t}^{\top}\bm{x}+\xi$, where
$\bm{x}\sim{\cal{N}}(0,{\bm{I}}),~{}\xi\sim{\cal{N}}(0,\sigma^{2})$ and
$\sigma$ is the noise level. Tasks are sampled i.i.d. via
${\bm{\beta}}_{t}\sim{\cal{N}}(0,{\bm{{\Sigma}}}),~{}t\in[T]$. Results are
displayed in Figures 2(a)&(b). We set $d=20$, $n=40$ and significantly larger
$T$ to make sure model is sufficiently trained and we display meta learning
results (i.e. on unseen tasks) for both experiments. In Fig. 2(a), $\sigma=1$
and ${\bm{{\Sigma}}}={\bm{I}}$. We also solve ridge-regularized linear
regression (with sample size from $1$ to $n$) over the grid
$\lambda=[0.01,0.05,0.1,0.5,1]$ and display the results of the best $\lambda$
selection as the optimal ridge curve (Black dotted). Recall from (6) that
ridge regression is optimal for isotropic task covariance. In Fig. 2(b), we
set $\sigma=0$ and
${\bm{{\Sigma}}}=\text{diag}(\left[1,\frac{1}{2^{2}},\frac{1}{3^{2}},\dots,\frac{1}{20^{2}}\right])$.
Besides ordinary least squares (Green curve), we also display the optimally-
weighted regression according to (6) (dotted curve) as $\sigma\rightarrow 0$.
In both figures, in-context learning results (Red) outperform the least
squares results (Green) and are perfectly aligned with optimal ridge/weighted
solutions (Black dotted). This in turn provides evidence for the automated
model selection ability of transformers by learning task priors.

$\bullet$ Partially-observed dynamical systems (Figures 2(c) & 6). We generate
in-context examples ${\bm{z}}_{i}=\bm{x}_{i}\in\mathbb{R}^{r},~{}i\in[n]$ via
the partially-observed linear dynamics $\bm{x}_{i}={\bm{C}}\bm{s}_{i}$,
$\bm{s}_{i}={\bm{A}}\bm{s}_{i-1}+\bm{\xi}_{i}$ with noise
$\bm{\xi}_{i}\sim{\cal{N}}(0,\sigma^{2}{\bm{I}}_{d})$ and initial state
$\bm{s}_{0}=\bm{0}$. Each task is parameterized by
${\bm{C}}\in\mathbb{R}^{r\times d}$ and ${\bm{A}}\in\mathbb{R}^{d\times d}$
which are drawn with i.i.d. ${\cal{N}}(0,1)$ entries and ${\bm{A}}$ is
normalized to have spectral radius $0.9$. In Fig. 2(c), we set $d=10$, $r=4$,
$\sigma=0$, $n=20$ and use sufficiently large $T$ to train the transformer.
For comparison, we solve least-squares regression to predict new observations
$\bm{x}_{i}$ via the most recent $H$ observations for varying window sizes
$H$. Results show that in-context learning outperforms the least-squares
results of all orders $H=1,2,3,4$.

Figure 6: Dynamical system experiments. The difference from Fig. 2(c) is that
we compare ICL to the optimally-tuned ridge regression with different history
windows $H$.

In Figure 6, we also solve the dynamical problem using optimal ridge
regression for different window sizes. This reveals that ICL can also
outperform auto-regressive models with optimal ridge tuning, albeit the
performance gap is much narrower444We note that Kalman filter can be used to
achieve optimal state estimation (which leverages the full history i.e.
$H\rightarrow\infty$). However it would require the knowledge of the ground-
truth dynamics unlike ICL.. It would be interesting to compare ICL performance
to a broader class of system identification algorithms (e.g. Hankel nuclear
norm, kernel-based, atomic norm [29, 17, 39]) and more broadly understand the
extent ICL can inform practically-relevant system identification.

Figure 7: Experiments to assess the algorithmic stability Assumption 1. Each
figure shows the increase in the risk for varying ICL sample sizes after an
example in the prompt is modified. We swap an input example in the prompt and
assign a flipped label to this new input, e.g., we move from
$(\bm{x},f(\bm{x}))$ to $(\bm{x}^{\prime},-f(\bm{x}^{\prime}))$.

$\bullet$ Stability analysis. In Assumption 1, we require that transformer-
induced algorithms are stable to input perturbations, specifically, we require
predictions to vary by at most ${\cal{O}}(1/m)$ where $m$ is the sample size.
This was justified in part by Theorem 1. To understand empirical stability, we
run additional experiments where the results are displayed in Fig. 7. We study
stability of four function classes: linear models, $3$-sparse linear models,
decision trees with depth $4$, and 2-layer ReLU networks with 100 hidden
units, all with input dimension of $20$. For each class $\mathcal{F}$, a GPT-2
architecture is trained with large number of random tasks $f\in\mathcal{F}$
and evaluate on new tasks. With the exception of Fig. 2(a), we use the
pretrained models provided by [20] and the task sequences are noiseless i.e.
sequences obey $y_{i}=f(\bm{x}_{i})$. As a coarse approximation of the _worst-
case_ perturbation, we perturb a prompt
$\bm{x}^{(m)}_{\text{prompt}}=(\bm{x}_{1},y_{1},\cdots,\bm{x}_{m-1},y_{m-1},\bm{x}_{m})$
as follows. Draw a random point
$(\bm{x}^{\prime}_{1},y^{\prime}_{1})\sim(\bm{x}_{1},y_{1})$ and flip its
label to obtain $(\bm{x}^{\prime}_{1},-y^{\prime}_{1})$. We obtain the
adversarial prompt via
$\bar{\bm{x}}_{\text{prompt}}^{(m)}=(\bm{x}^{\prime}_{1},-y^{\prime}_{1},\cdots,\bm{x}_{m-1},y_{m-1},\bm{x}_{m})$555To
properly verify Assumption 1 one should adversarially optimize
$\bm{x}^{\prime}_{1},\bm{y}^{\prime}_{1}$ and also swap the other indices
$m>i>1$.. In Figure 7, we plot the test risk change between the adversarial
and standard prompts. All figures corroborate that, after a certain sample
size, the risk change noticeably decreases as the in-context sample size
increases. This behavior is in line with Assumption 1; however, further
investigation and longer context window are required to accurately
characterize the stability profile (e.g. to verify whether stability is
${\cal{O}}(1/m)$ or not).

##  8 Conclusions and Future Directions

In this work, we approach prompt-based in-context learning as an algorithm
learning problem from a statistical perspective. Through this view, we
presented generalization bounds for MTL where the model is trained with $T$
tasks each mapped to a sequence containing $n$ examples. We analyzed
generalization bounds for two fundamental scenarios in which the prompts are
obtained from a sequence of i.i.d. (input, output) pairs or a trajectory of a
dynamical systems. Additionally, we have discussed generalization guarantees
on new tasks with respect to excess MTL risk and presented numerical
simulations supporting our hypothesis. Finally, we have discussed how in-
context learning can select the correct hypothesis set over different function
classes by implicitly solving empirical risk minimization over the data
provided within the prompt.

There are multiple interesting questions related to our findings: (1) Our
bounds are mainly useful for capturing multitask learning risk, which
motivates us to study the question: How can we control generalization on
individual tasks or prompts with specific lengths (rather than average risk)?
(2) We provided guarantees for dynamical systems with full-state observations.
Can we extend such results to more general dynamic settings such as
reinforcement learning or system identification with partial state
observations? (3) Our investigation of transfer learning in Section 4 revealed
that transfer risk is governed by the number of MTL tasks and task complexity
however it seems to be independent of the model complexity. It would be
interesting to characterize this inductive bias during pretraining and
characterize exactly what algorithm is learned by the transformer.

## Acknowledgements

This work was supported in part by the NSF grants CCF-2046816 and CCF-2212426,
Google Research Scholar award, and Army Research Office grant W911NF2110312.

## References

  * [1] Huggingface pretrained models, 2023.
  * [2] Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou.  What learning algorithm is in-context learning? investigations with linear models.  arXiv preprint arXiv:2211.15661, 2022.
  * [3] Navid Azizan and Babak Hassibi.  Stochastic gradient/mirror descent: Minimax optimality and implicit regularization.  In International Conference on Learning Representations, 2019.
  * [4] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  Machine learning, 79(1):151–175, 2010.
  * [5] Olivier Bousquet and André Elisseeff.  Algorithmic stability and generalization performance.  Advances in Neural Information Processing Systems, 13, 2000.
  * [6] Olivier Bousquet and André Elisseeff.  Stability and generalization.  The Journal of Machine Learning Research, 2:499–526, 2002.
  * [7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [8] Lisha Chen, Songtao Lu, and Tianyi Chen.  Understanding benign overfitting in gradient-based meta learning.  In Advances in Neural Information Processing Systems, 2022.
  * [9] Yuan Cheng, Songtao Feng, Jing Yang, Hong Zhang, and Yingbin Liang.  Provable benefit of multitask representation learning in reinforcement learning.  arXiv preprint arXiv:2206.05900, 2022.
  * [10] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al.  Palm: Scaling language modeling with pathways.  arXiv preprint arXiv:2204.02311, 2022.
  * [11] Liam Collins, Aryan Mokhtari, Sewoong Oh, and Sanjay Shakkottai.  Maml and anil provably learn representations.  arXiv preprint arXiv:2202.03483, 2022.
  * [12] Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Zhifang Sui, and Furu Wei.  Why can gpt learn in-context? language models secretly perform gradient descent as meta optimizers.  arXiv preprint arXiv:2212.10559, 2022.
  * [13] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu.  On the sample complexity of the linear quadratic regulator.  Foundations of Computational Mathematics, 20(4):633–679, 2020.
  * [14] Tuan Dinh, Yuchen Zeng, Ruisu Zhang, Ziqian Lin, Shashank Rajput, Michael Gira, Jy-yong Sohn, Dimitris Papailiopoulos, and Kangwook Lee.  Lift: Language-interfaced fine-tuning for non-language machine learning tasks.  arXiv preprint arXiv:2206.06565, 2022.
  * [15] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei.  Few-shot learning via learning the representation, provably.  arXiv preprint arXiv:2002.09434, 2020.
  * [16] Mohamad Kazem Shirani Faradonbeh and Aditya Modi.  Joint learning-based stabilization of multiple unknown linear systems.  arXiv preprint arXiv:2201.01387, 2022.
  * [17] Maryam Fazel, Ting Kei Pong, Defeng Sun, and Paul Tseng.  Hankel matrix rank minimization with applications to system identification and realization.  SIAM Journal on Matrix Analysis and Applications, 34(3):946–977, 2013.
  * [18] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In International conference on machine learning, pages 1126–1135. PMLR, 2017.
  * [19] Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin.  Learning nonlinear dynamical systems from a single trajectory.  In Learning for Dynamics and Control, pages 851–861. PMLR, 2020\.
  * [20] Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant.  What can transformers learn in-context? a case study of simple function classes.  Neural Information Processing Systems, 2022.
  * [21] Steve Hanneke and Samory Kpotufe.  On the value of target data in transfer learning.  Advances in Neural Information Processing Systems, 32, 2019.
  * [22] Noah Hollmann, Samuel Müller, Katharina Eggensperger, and Frank Hutter.  Tabpfn: A transformer that solves small tabular classification problems in a second.  arXiv preprint arXiv:2207.01848, 2022.
  * [23] Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh.  Meta-learning for mixed linear regression.  In International Conference on Machine Learning, pages 5394–5404. PMLR, 2020.
  * [24] Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli.  Near-optimal offline and streaming algorithms for learning non-linear dynamical systems.  Advances in Neural Information Processing Systems, 34:8518–8531, 2021.
  * [25] Vitaly Kuznetsov and Mehryar Mohri.  Time series prediction and online learning.  In Conference on Learning Theory, pages 1190–1213. PMLR, 2016.
  * [26] Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, DJ Strouse, Steven Hansen, Angelos Filos, Ethan Brooks, et al.  In-context reinforcement learning with algorithm distillation.  arXiv preprint arXiv:2210.14215, 2022.
  * [27] Yingcong Li, Mingchen Li, M Salman Asif, and Samet Oymak.  Provable and efficient continual representation learning.  arXiv preprint arXiv:2203.02026, 2022.
  * [28] Dennis V Lindley and Adrian FM Smith.  Bayes estimates for the linear model.  Journal of the Royal Statistical Society: Series B (Methodological), 34(1):1–18, 1972.
  * [29] Lennart Ljung.  System identification.  In Signal analysis and prediction, pages 163–173. Springer, 1998\.
  * [30] Horia Mania, Michael I Jordan, and Benjamin Recht.  Active learning for nonlinear system identification with guarantees.  arXiv preprint arXiv:2006.10277, 2020.
  * [31] Nikolai Matni and Stephen Tu.  A tutorial on concentration bounds for system identification.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3741–3749. IEEE, 2019.
  * [32] Andreas Maurer.  A vector-contraction inequality for rademacher complexities.  In International Conference on Algorithmic Learning Theory, pages 3–17. Springer, 2016.
  * [33] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes.  The benefit of multitask representation learning.  Journal of Machine Learning Research, 17(81):1–32, 2016.
  * [34] Aditya Modi, Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Joint learning of linear time-invariant dynamical systems.  arXiv preprint arXiv:2112.10955, 2021.
  * [35] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of machine learning.  MIT press, 2018.
  * [36] Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro.  Geometry of optimization and implicit regularization in deep learning.  arXiv preprint arXiv:1705.03071, 2017.
  * [37] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al.  In-context learning and induction heads.  arXiv preprint arXiv:2209.11895, 2022.
  * [38] Samet Oymak and Necmiye Ozay.  Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.  IEEE Transactions on Automatic Control, 67(4):1914–1928, 2021.
  * [39] Gianluigi Pillonetto, Tianshi Chen, Alessandro Chiuso, Giuseppe De Nicolao, and Lennart Ljung.  Regularized linear system identification using atomic, nuclear and kernel-based norms: The role of the stability constraint.  Automatica, 69:137–149, 2016.
  * [40] Yuzhen Qin, Tommaso Menara, Samet Oymak, Shinung Ching, and Fabio Pasqualetti.  Non-stationary representation learning in sequential linear bandits.  IEEE Open Journal of Control Systems, 2022.
  * [41] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco.  Asymptotics of ridge (less) regression under general source condition.  In International Conference on Artificial Intelligence and Statistics, pages 3889–3897. PMLR, 2021.
  * [42] Tuhin Sarkar and Alexander Rakhlin.  Near optimal finite time identification of arbitrary linear dynamical systems.  In International Conference on Machine Learning, pages 5610–5618. PMLR, 2019.
  * [43] Yahya Sattar, Zhe Du, Davoud Ataee Tarzanagh, Laura Balzano, Necmiye Ozay, and Samet Oymak.  Identification and adaptive control of markov jump systems: Sample complexity and regret bounds.  arXiv preprint arXiv:2111.07018, 2021.
  * [44] Yahya Sattar and Samet Oymak.  Non-asymptotic and accurate learning of nonlinear dynamical systems.  Journal of Machine Learning Research, 23(140):1–49, 2022.
  * [45] Yahya Sattar and Samet Oymak.  Non-asymptotic and accurate learning of nonlinear dynamical systems.  Journal of Machine Learning Research, 23(140):1–49, 2022.
  * [46] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht.  Learning without mixing: Towards a sharp analysis of linear system identification.  In Conference On Learning Theory, pages 439–473. PMLR, 2018.
  * [47] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  The Journal of Machine Learning Research, 19(1):2822–2878, 2018\.
  * [48] Yue Sun, Adhyyan Narang, Ibrahim Gulluk, Samet Oymak, and Maryam Fazel.  Towards sample-efficient overparameterized meta-learning.  Advances in Neural Information Processing Systems, 34:28156–28168, 2021.
  * [49] Nilesh Tripuraneni, Chi Jin, and Michael Jordan.  Provable meta-learning of linear representations.  In International Conference on Machine Learning, pages 10434–10443. PMLR, 2021.
  * [50] Nilesh Tripuraneni, Michael Jordan, and Chi Jin.  On the theory of transfer learning: The importance of task diversity.  Advances in Neural Information Processing Systems, 33:7852–7862, 2020.
  * [51] Anastasios Tsiamis and George J Pappas.  Finite sample analysis of stochastic system identification.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3648–3654. IEEE, 2019.
  * [52] Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas.  Statistical learning theory for control: A finite sample perspective.  arXiv preprint arXiv:2209.05423, 2022.
  * [53] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [54] Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov.  Transformers learn in-context by gradient descent.  arXiv preprint arXiv:2212.07677, 2022.
  * [55] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * [56] Denny Wu and Ji Xu.  On the optimal weighted $\ell_{2}$ regularization in overparameterized linear regression.  Advances in Neural Information Processing Systems, 33:10112–10123, 2020.
  * [57] Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma.  An explanation of in-context learning as implicit bayesian inference.  arXiv preprint arXiv:2111.02080, 2021.

##  Appendix A Stability of Transformer-based ICL

###### Lemma 1

Let $\bm{x},\bm{\varepsilon}\in\mathbb{R}^{n}$ be vectors obeying
$\|{\bm{x}}\|_{\ell_{\infty}},\|{\bm{x}+\bm{\varepsilon}}\|_{\ell_{\infty}}\leq
c$. Then, there exists a constant $C=C(c)$, such that

$\|{\text{softmax}(\bm{x})}\|_{\ell_{\infty}}\leq
e^{2c}/n\quad\text{and}\quad\|{\text{softmax}(\bm{x})-\text{softmax}(\bm{x}+\bm{\varepsilon})}\|_{\ell_{1}}\leq
e^{2c}\|{\bm{\varepsilon}}\|_{\ell_{1}}/n.$

Proof. Without losing generality, assume the first coordinate is the largest.
Using monotonicity of softmax, we obtain
$\|{\text{softmax}(\bm{x})}\|_{\ell_{\infty}}\leq\frac{e^{c}}{e^{c}+\sum_{i=2}^{n}e^{-c}}\leq\frac{e^{2c}}{n}$.
Say $\|{\bm{\varepsilon}}\|_{\ell_{2}}=\varepsilon$. As
$\bm{\varepsilon}\rightarrow 0$, we have

$\lim_{\varepsilon\rightarrow
0}[\text{softmax}(\bm{x}+\bm{\varepsilon})-\text{softmax}(\bm{x})]/\varepsilon=[\text{diag}(\text{softmax}(\bm{x}))-\text{softmax}(\bm{x})\text{softmax}(\bm{x})^{\top}]\bm{\varepsilon}/\varepsilon$

$\|{[\text{diag}(\text{softmax}(\bm{x}))-\text{softmax}(\bm{x})\text{softmax}(\bm{x})^{\top}]\bm{\varepsilon}}\|_{\ell_{1}}\leq
e^{2c}\|{\bm{\varepsilon}}\|_{\ell_{1}}/n$. Integrating the derivative along
$\bm{\varepsilon}$, we obtain the result.

For a matrix ${\bm{A}}$, let $\|{\bm{A}}\|_{2,p}$ denote the $\ell_{p}$ norm
of the vector obtained by the $\ell_{2}$ norms of its rows.

###### Lemma 2

Let ${\bm{X}}=[\bm{x}_{1}~{}\dots~{}\bm{x}_{n}]^{\top}$ and
${\bm{E}}=[\bm{\varepsilon}_{1}~{}\dots~{}\bm{\varepsilon}_{n}]^{\top}$ be the
input and perturbation matrices respectively. Assume that the tokens
($\bm{x}_{i},\bm{x}_{i}+\bm{\varepsilon}_{i}$) lie in unit ball i.e.
$\|{\bm{X}}\|_{2,\infty},\|{\bm{X}}+{\bm{E}}\|_{2,\infty}\leq 1$. Let
${\bm{V}},\bm{W}\in\mathbb{R}^{d\times d}$ be the weights of the self-
attention layer obeying $\|{\bm{V}}\|\leq 1$ and $\|\bm{W}\|\leq\Gamma$.
Define the attention outputs
${\bm{A}}=\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top}){\bm{X}}$ and
${\bm{\bar{A}}}=\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})\bm{\bar{X}}$.
We have that

$\|{\bm{A}}\|_{2,\infty},\|{\bm{\bar{A}}}\|_{2,\infty}\leq
1,\quad\|{\bm{A}}-{\bm{\bar{A}}}\|_{2,1}\leq(2\Gamma+1)e^{2\Gamma}\|{\bm{E}}\|_{2,1}.$

Proof. First Observe that ${\bm{V}}$ preserves norms i.e. ${\bm{X}}{\bm{V}}$
obeys $\|{\bm{X}}{\bm{V}}\|_{2,\infty}\leq\|{\bm{X}}\|_{2,\infty}\leq 1$ and
$\|{\bm{E}}{\bm{V}}\|_{2,1}\leq\|{\bm{E}}\|_{2,1}$.

Next, set $\bm{\bar{X}}={\bm{X}}+{\bm{E}}$ and define attention outputs
${\bm{A}}=\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top}){\bm{X}}{\bm{V}}$,
${\bm{\bar{A}}}=\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})\bm{\bar{X}}{\bm{V}}$.
Observe that, since softmax applies row-wise to the similarities (e.g.
${\bm{X}}\bm{W}{\bm{X}}$), we preserve the feature norms i.e.
$\|{\bm{A}}\|_{2,\infty},\|{\bm{\bar{A}}}\|_{2,\infty}\leq 1$ as advertised.

Now, consider the attention output difference
${\bm{P}}={\bm{\bar{A}}}-{\bm{A}}$

${\bm{P}}=[\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})]{\bm{X}}{\bm{V}}+\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top}){\bm{E}}{\bm{V}}.$

For any pairs of tokens, we have
$|\bm{x}_{i}^{\top}\bm{W}\bm{x}_{j}|\leq\Gamma$. Using Lemma 1

$\|{\bm{P}}_{2}\|_{2,1}=\|\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top}){\bm{E}}{\bm{V}}\|_{2,1}\leq
n\|\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})\|_{\infty}\|{\bm{E}}\|_{2,1}\leq
e^{2\Gamma}\|{\bm{E}}\|_{2,1}.$

Secondly, set
${\bm{P}}_{1}=[\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})]{\bm{X}}{\bm{V}}$.
We have that

$\displaystyle\|{\bm{P}}_{1}\|_{2,1}$
$\displaystyle\leq\|{\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}\|{\bm{X}}{\bm{V}}\|_{2,\infty}$
$\displaystyle\leq\|{\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}.$

To proceed, let us control the derivative by letting the perturbation
${\bm{E}}\rightarrow 0$ and then integrate the derivative along ${\bm{E}}$.
Clearly, as ${\bm{E}}\rightarrow 0$, the quadratic-terms involving ${\bm{E}}$
disappear and
$\|{\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}$

$\leq\|{\text{softmax}(\bm{\bar{X}}\bm{W}{\bm{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}+\|{\text{softmax}({\bm{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}.$

To bound the latter, consider each row individually, namely pick a row from
${\bm{X}},{\bm{X}}+{\bm{E}}$ each denoted by the pair
$(\bm{x},\bm{x}+\bm{\varepsilon})$. Note that for any cross-product, we are
guaranteed to have
$|(\bm{x}+\bm{\varepsilon})^{\top}\bm{W}\bm{x}_{i}|,|\bm{x}^{\top}\bm{W}\bm{x}_{i}|\leq\Gamma,\|{\bm{\varepsilon}^{\top}\bm{W}{\bm{X}}}\|_{\ell_{1}}\leq\Gamma
n\|{\bm{\varepsilon}}\|_{\ell_{2}}$,
$\|{\bm{x}^{\top}\bm{W}{\bm{E}}^{\top}}\|_{\ell_{1}}\leq\Gamma\|{\bm{E}}\|_{2,1}$.
Applying perturbation bound of Lemma 1, we get

$\displaystyle\|{\text{softmax}((\bm{x}+\bm{\varepsilon})^{\top}\bm{W}{\bm{X}}^{\top})-\text{softmax}(\bm{x}^{\top}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}\leq\Gamma
e^{2\Gamma}\|{\bm{\varepsilon}}\|_{\ell_{1}}$ (9)
$\displaystyle\|{\text{softmax}(\bm{x}^{\top}\bm{W}({\bm{X}}+{\bm{E}})^{\top})-\text{softmax}(\bm{x}^{\top}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}\leq\Gamma
e^{2\Gamma}\|{\bm{E}}\|_{2,1}/n.$ (10)

Adding up all $n$ rows, we obtain (denoting $\varepsilon=\|{\bm{E}}\|)$

$\lim_{\varepsilon\rightarrow
0}\|{\text{softmax}(\bm{\bar{X}}\bm{W}\bm{\bar{X}}^{\top})-\text{softmax}({\bm{X}}\bm{W}{\bm{X}}^{\top})}\|_{\ell_{1}}/\varepsilon\leq
2\Gamma e^{2\Gamma}\|{\bm{E}}\|_{2,1}/\varepsilon.$

Integrating the derivative along ${\bm{E}}$, we obtain
$\|{\bm{P}}_{1}\|_{2,1}\leq 2\Gamma e^{2\Gamma}\|{\bm{E}}\|_{2,1}$.
Cumulatively, we obtain the main claim
$\|{\bm{P}}\|_{2,1}\leq(2\Gamma+1)e^{2\Gamma}\|{\bm{E}}\|_{2,1}$.

######  Lemma 3 (Single-layer transformer stability)

Consider the setup of Lemma 2. Let $\phi$ be a $1$-Lipschitz activation
function with $\phi(0)=0$ (e.g. ReLU or Identity). Let
$({\bm{M}}_{i})_{i=1}^{n}\in\mathbb{R}^{d\times d}$ be weights of the parallel
MLPs following self-attention. Suppose $\|{\bm{M}}_{i}\|\leq 1$ and denote the
MLP outputs associated to ${\bm{A}},{\bm{\bar{A}}}$ by
${{\bm{B}}},{\bm{\bar{B}}}$. We have that

$\|{{\bm{B}}}\|_{2,\infty},\|{\bm{\bar{B}}}\|_{2,\infty}\leq
1,\quad\|{{\bm{B}}}-{\bm{\bar{B}}}\|_{2,1}\leq(2\Gamma+1)e^{2\Gamma}\|{\bm{E}}\|_{2,1}.$

Proof. First note that each row of ${\bm{\bar{B}}}$ is given by
$\bm{b}_{i}=\phi({\bm{M}}_{i}\bm{a}_{i})$ thus
$\|{\bm{b}_{i}}\|_{\ell_{2}}\leq\|{\phi({\bm{M}}_{i}\bm{a}_{i})}\|_{\ell_{2}}\leq\|{{\bm{M}}_{i}\bm{a}_{i}}\|_{\ell_{2}}\leq\|{\bm{a}_{i}}\|_{\ell_{2}}\leq
1$. Secondly, we can write
$\|{\bm{b}_{i}-\bar{\bm{b}}_{i}}\|_{\ell_{2}}\leq\|{\phi({\bm{M}}_{i}\bm{a}_{i})-\phi({\bm{M}}_{i}\bar{\bm{a}}_{i})}\|_{\ell_{2}}\leq\|{{\bm{M}}_{i}(\bm{a}_{i}-\bar{\bm{a}}_{i})}\|_{\ell_{2}}\leq\|{\bm{a}_{i}-\bar{\bm{a}}_{i}}\|_{\ell_{2}}$.
Thus,
$\|{{\bm{B}}}-{\bm{\bar{B}}}\|_{2,1}\leq\|{\bm{A}}-{\bm{\bar{A}}}\|_{2,1}$ and
we conclude via Lemma 2.

###### Theorem 4

Consider a transformer composed of $L$ layers with (1) output weights:
${\bm{H}}\in\mathbb{R}^{m\times d}$, (2) self-attention weights: combined key-
query weights $(\bm{W}_{i})_{i=1}^{L}\in\mathbb{R}^{d\times d}$ and value
weights $({\bm{V}}_{i})_{i=1}^{L}\in\mathbb{R}^{d\times d}$, (3) MLP weights:
$({\bm{M}}^{(i)}_{j})_{i=1,j=1}^{L,m}\in\mathbb{R}^{d\times d}$ and activation
$\phi\in\\{\text{ReLU},\text{Identity}\\}$. For some $\Gamma>0$, assume
$\|{\bm{V}}_{i}\|\leq 1,\|{\bm{M}}^{(i)}_{j}\|\leq
1,\|\bm{W}_{i}\|\leq\Gamma/2$ and $\|{\bm{H}}\|_{2,\infty}\leq c/m$. Suppose
input space is
${\mathcal{S}}=({\bm{z}}_{1},~{}{\bm{z}}_{2}\dots,~{}{\bm{z}}_{m})$ with
$\|{{\bm{z}}_{i}}\|_{\ell_{2}}\leq 1$. The model prediction is given as
follows

  * •

${\mathcal{S}}_{(0)}={\mathcal{S}}$. Layer $i$ outputs
${\mathcal{S}}_{(i)}=\texttt{Parallel\\_MLP}_{{\bm{M}}^{(i)}}(\texttt{Att}_{\bm{W}_{i},{\bm{V}}_{i}}({\mathcal{S}}_{(i-1)})))$.
Here the self-attention layer is given by
$\texttt{Att}_{\bm{W}_{i},{\bm{V}}_{i}}({\mathcal{S}})=\text{softmax}({\mathcal{S}}^{\top}\bm{W}_{i}{\mathcal{S}}){\mathcal{S}}{\bm{V}}$
and Parallel_MLP applies $f(\bm{x})=\phi({\bm{M}}^{(i)}_{j}\bm{x})$ on
$j^{th}$ token of the Att output.

  * •

${\texttt{TF}}({\mathcal{S}})=\left<{\bm{H}},{\mathcal{S}}_{(L)}\right>$.

First, this model is properly normalized in the sense that it can attain
${\texttt{TF}}({\mathcal{S}})=\pm c$. Second, this model obeys the stability
guarantee

$|{\texttt{TF}}({\mathcal{S}})-{\texttt{TF}}({\mathcal{S}}^{\prime})|\leq\frac{c}{m}((1+\Gamma)e^{\Gamma})^{L}\|{\mathcal{S}}-{\mathcal{S}}^{\prime}\|_{2,1}.$

Proof. To see the first claim, let us set
${\bm{V}}_{i}={\bm{M}}_{i,l}={\bm{I}}$ and set all tokens ${\bm{z}}_{i}$ to be
identical i.e. ${\mathcal{S}}={\mathbf{1}}_{n}{\bm{z}}^{\top}$. Additionally
choose a ${\bm{z}}$ with $\|{{\bm{z}}}\|_{\ell_{2}}=1$ and nonnegative
entries. Observe that, thanks to the softmax structure, regardless of
$\bm{W}_{i}$, we have that
${\mathcal{S}}=\texttt{Att}_{\bm{W}_{i},{\bm{V}}_{i}}({\mathcal{S}})=\text{softmax}({\mathcal{S}}^{\top}\bm{W}_{i}{\mathcal{S}}){\mathcal{S}}$.
After attention, MLPs again preserves the tokens i.e.
$\phi({\bm{M}}_{i,l}{\bm{z}}_{i})={\bm{z}}$ for
$\phi\in\\{\text{ReLU},\text{Identity}\\}$. Thus, after proceeding $L$ layers
of this, we find that
${\texttt{TF}}({\mathcal{S}})=\left<{\bm{H}},{\mathcal{S}}\right>=\sum_{i=1}^{n}h_{i}^{\top}{\bm{z}}$.
To conclude, by setting all tokens $h_{i}=c{\bm{z}}/m$ or
$h_{i}=-c{\bm{z}}/m$, we obtain the claim. Note that, in general
${\mathcal{S}}$ can be arbitrary (they don’t have to be all same tokens): We
can let $\bm{W}\rightarrow\infty$ (by allowing a larger $\Gamma$). This way
the attention matrix
$\text{softmax}({\mathcal{S}}^{\top}\bm{W}{\mathcal{S}})\rightarrow{\bm{I}}$
so that we end up with the same argument of ${\mathcal{S}}$ being (almost
perfectly) transmitted across the layers and we obtain $\pm c$ output by
setting ${\bm{H}}={\mathcal{S}}/m$.

To show the stability guarantee, we use Lemmas 2 and 3. Specifically, Lemma 3
guarantees that

  * •

After each layer we are guaranteed to have
$\|{\mathcal{S}}_{(i)}\|_{2,\infty},\|{\mathcal{S}}^{\prime}_{(i)}\|_{2,\infty}\leq
1$.

  * •

After each layer we are guaranteed to have
$\|{\mathcal{S}}_{(i)}-{\mathcal{S}}^{\prime}_{(i)}\|_{2,1}\leq(1+\Gamma)e^{\Gamma}\|{\mathcal{S}}_{(i-1)}-{\mathcal{S}}^{\prime}_{(i-1)}\|_{2,1}$.

This means that, at the end of the final layer, we have

$\|{\mathcal{S}}_{(L)}-{\mathcal{S}}^{\prime}_{(L)}\|_{2,1}\leq((1+\Gamma)e^{\Gamma})^{L}\|{\mathcal{S}}-{\mathcal{S}}^{\prime}\|_{2,1}.$

Collapsing these by the linear ${\bm{H}}$, we find that
$|{\texttt{TF}}({\mathcal{S}}^{\prime})-{\texttt{TF}}({\mathcal{S}})|\leq\left<{\bm{H}},{\mathcal{S}}_{(L)}-{\mathcal{S}}^{\prime}_{(L)}\right>\leq\|{\bm{H}}\|_{2,\infty}\|{\mathcal{S}}_{(L)}-{\mathcal{S}}^{\prime}_{(L)}\|_{2,1}$
concluding the proof.

###  A.1 Proof of Theorem 1

Proof. We need to specialize Theorem 4 to obtain the result. Observe that when
prompts differ only at the inputs ${\bm{z}}_{j}=(\bm{x}_{j},y_{j})$ with
${\bm{z}}_{j}^{\prime}=(\bm{x}^{\prime}_{j},y^{\prime}_{j})$, we have that
$\|{\bm{X}}_{\text{prompt}}-{\bm{X}}^{\prime}_{\text{prompt}}\|_{2,1}\leq 2$.
This implies that
$|{\texttt{TF}}({\bm{X}}_{\text{prompt}})-{\texttt{TF}}({\bm{X}}^{\prime}_{\text{prompt}})|\leq\frac{2}{2m-1}((1+\Gamma)e^{\Gamma})^{D}$
for a depth $D$ transformer. Finally, since the loss function $\ell$ is
$L$-Lipschitz, we obtain the result $K=2L((1+\Gamma)e^{\Gamma})^{D}$.

##  Appendix B Proofs and Supplementary Results for Sections 3,4,5

###  B.1 Proof of Theorem 2

######  Theorem 5 (Theorem 2 restated)

Suppose Assumption 1 holds and assume loss function
$\ell(\bm{y},\hat{\bm{y}})$ is $L$-Lipschitz for all $\bm{y}\in\mathcal{Y}$
and takes values in $[0,B]$. Let ${\widehat{\texttt{Alg}}}$ be the empirical
solution of (ICL-ERM) and ${\cal{N}}(\mathcal{A},\rho,u)$ be the covering
number of the algorithm space $\mathcal{A}$ following Definition 1&2. Then
with probability at least $1-2\delta$, the excess MTL risk in (MTL-risk) obeys

$\scalebox{1.0}{\mbox{$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq\inf_{\varepsilon>0}\left\\{4L\varepsilon+2(B+K\log
n)\sqrt{\frac{\log({\cal{N}}(\mathcal{A},\rho,\varepsilon)/\delta)}{cnT}}\right\\}$}}.$

Additionally, set
$D:=\sup_{\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}}\rho(\texttt{Alg},\texttt{Alg}^{\prime})$
and assume $D<\infty$. With probability at least $1-4\delta$,

$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq\inf_{\varepsilon>0}\left\\{8L\varepsilon+8(2L+K\log
n)\int_{\varepsilon}^{D/2}\sqrt{\frac{\log\left(\log\frac{D}{\varepsilon}\cdot{\cal{N}}(\mathcal{A},\rho,u)/\delta\right)}{c^{\prime}nT}}du\right\\}+2(B+K\log
n)\sqrt{\frac{\log(1/\delta)}{cnT}}.$

Proof. Recall the MTL problem setting of independent (input, label) pairs in
Section 2: There are $T$ tasks each with $n$ in-context training samples
denoted by
$(\mathcal{S}_{t})_{t=1}^{T}\overset{\text{i.i.d.}}{\sim}({\cal{D}}_{t})_{t=1}^{T}$
where $\mathcal{S}_{t}=\\{(\bm{x}_{ti},\bm{y}_{ti})\\}_{i=1}^{n}$, and let
${\mathcal{S}_{\text{all}}}=\bigcup_{t=1}^{T}\mathcal{S}_{t}$. We use
$\mathcal{A}$ to denote the algorithm set. For a $\texttt{Alg}\in\mathcal{A}$,
we define the training risk
${\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg})=\frac{1}{nT}\sum_{t=1}^{T}\sum_{i=1}^{n}\ell(\bm{y}_{ti},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti}))$,
and the test risk
${\cal{L}}_{\text{MTL}}(\texttt{Alg})=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg})]$.
Define empirical risk minima
${\widehat{\texttt{Alg}}}=\arg\min_{\texttt{Alg}\in\mathcal{A}}{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg})$
and population minima
$\texttt{Alg}^{\star}=\arg\min_{\texttt{Alg}\in\mathcal{A}}{\cal{L}}_{\text{MTL}}(\texttt{Alg})$.
For cleaner exposition, in the following discussion, we drop the subscripts
MTL and ${\mathcal{S}_{\text{all}}}$. The excess MTL risk is decomposed as
follows:

$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})$
$\displaystyle={\cal{L}}({\widehat{\texttt{Alg}}})-{\cal{L}}(\texttt{Alg}^{\star})$
$\displaystyle=\underset{a}{\underbrace{{\cal{L}}({\widehat{\texttt{Alg}}})-{\widehat{\cal{L}}}({\widehat{\texttt{Alg}}})}}+\underset{b}{\underbrace{{\widehat{\cal{L}}}({\widehat{\texttt{Alg}}})-{\widehat{\cal{L}}}(\texttt{Alg}^{\star})}}+\underset{c}{\underbrace{{\widehat{\cal{L}}}(\texttt{Alg}^{\star})-{\cal{L}}(\texttt{Alg}^{\star})}}.$

Since ${\widehat{\texttt{Alg}}}$ is the minimizer of empirical risk, we have
$b\leq 0$. To proceed, we consider the concentration problem of upper bounding
$\sup_{\texttt{Alg}\in\mathcal{A}}|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|$.

Step 1: We start with a concentration bound
$|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|$ for a fixed
$\texttt{Alg}\in\mathcal{A}$. Recall that we define the test/train risks of
each task as follows:

$\displaystyle{\widehat{\cal{L}}}_{t}(\texttt{Alg}):=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{ti},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti})),\quad\text{and}$
$\displaystyle{\cal{L}}_{t}(\texttt{Alg}):=\operatorname{\mathbb{E}}_{\mathcal{S}_{t}}\left[{\widehat{\cal{L}}}_{t}(\texttt{Alg})\right]=\operatorname{\mathbb{E}}_{\mathcal{S}_{t}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{ti},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti}))\right],\quad\forall
t\in[T].$

Define the random variables
$X_{t,i}=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})|{{\mathcal{S}}^{(i)}_{t}}]$
for $i\in[n]$ and $t\in[T]$, that is, $X_{t,i}$ is the expectation over
${\widehat{\cal{L}}}_{t}(\texttt{Alg})$ given training sequence
${{\mathcal{S}}^{(i)}_{t}}=\\{(\bm{x}_{tj},\bm{y}_{tj})\\}_{j=1}^{i}$ (which
are the filtrations). With this, we have that
$X_{t,n}=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})|{{\mathcal{S}}^{(n)}_{t}}]={\widehat{\cal{L}}}_{t}(\texttt{Alg})$
and
$X_{t,0}=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})]={\cal{L}}_{t}(\texttt{Alg})$.
More generally, $(X_{t,0},X_{t,1},\dots,X_{t,n})$ is a martingale sequence
since, for every $t$ in $[T]$, we have that
$\operatorname{\mathbb{E}}[X_{t,i}|{{\mathcal{S}}^{(i-1)}_{t}}]=X_{t,i-1}$.

For notational simplicitly, in the following discussion, we omit the subscript
$t$ from $\bm{x},\bm{y}$ and $\bm{Z}$ as they will be clear from left hand-
side variable $X_{t,i}$. We have that

$\displaystyle X_{t,i}$
$\displaystyle=\operatorname{\mathbb{E}}\bigg{[}\frac{1}{n}\sum_{j=1}^{n}\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\bigg{|}{{\mathcal{S}}^{(i)}}\bigg{]}$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{i}\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))+\frac{1}{n}\sum_{j=i+1}^{n}\operatorname{\mathbb{E}}\left[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\bigg{|}{{\mathcal{S}}^{(i)}}\right]$

Next, we wish to upper bound the martingale increments i.e. the difference of
neighbors. Let
${{\mathcal{S}}^{(i:i)}}={{\mathcal{S}}^{(i)}}-{{\mathcal{S}}^{(i-1)}}$ denote
the $i$’th element.

$\displaystyle|X_{t,i}-X_{t,i-1}|$
$\displaystyle=\left|\operatorname{\mathbb{E}}\bigg{[}\frac{1}{n}\sum_{j=1}^{n}\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\bigg{|}{{\mathcal{S}}^{(i)}}\bigg{]}-\operatorname{\mathbb{E}}\bigg{[}\frac{1}{n}\sum_{j=1}^{n}\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\bigg{|}{{\mathcal{S}}^{(i-1)}}\bigg{]}\right|$
$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{B}{n}+\frac{1}{n}\sum_{j=i+1}^{n}\left|\operatorname{\mathbb{E}}\left[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\bigg{|}{{\mathcal{S}}^{(i)}}\right]-\operatorname{\mathbb{E}}\left[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\bigg{|}{{\mathcal{S}}^{(i-1)}}\right]\right|$}}.$

Here, $(a)$ follows from the fact that loss function $\ell(\cdot,\cdot)$ is
bounded by $B$. To proceed, call the right side terms
$D_{j}:=|\operatorname{\mathbb{E}}[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\big{|}{{\mathcal{S}}^{(i)}}]-\operatorname{\mathbb{E}}[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(j-1)}}}}(\bm{x}_{j}))\big{|}{{\mathcal{S}}^{(i-1)}}]|$.
Denote ${\bm{z}}^{\prime}_{\ell}$ to be the realized values of
${\bm{z}}_{\ell}=(\bm{y}_{\ell},\bm{x}_{\ell})$ given ${{\mathcal{S}}^{(i)}}$.
Let
$\mathcal{S}:=({\bm{z}}^{\prime}_{1},\dots,{\bm{z}}^{\prime}_{i},{\bm{z}}_{i+1},\dots,{\bm{z}}_{j})$
and
$\mathcal{S}^{\prime}:=({\bm{z}}^{\prime}_{1},\dots,{\bm{z}}^{\prime}_{i-1},{\bm{z}}_{i},\dots,{\bm{z}}_{j})$.
Observe that, $\mathcal{S}^{\prime}$ and $\mathcal{S}$ differs in only at
$i$th index and $i<j$, thus, utilizing Assumption 1,

$\displaystyle
D_{j}:=|\operatorname{\mathbb{E}}[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{\mathcal{S}{}{}}}(\bm{x}_{j}))]-\operatorname{\mathbb{E}}[\ell(\bm{y}_{j},{f^{\texttt{Alg}}_{\mathcal{S}{{}^{\prime}}{}}}(\bm{x}_{j}))]|\leq\frac{K}{j}.$
(11)

Combining above, for any $n\geq i\geq 1$, we obtain

$|X_{t,i}-X_{t,i-1}|\leq\frac{B}{n}+\sum_{j=i+1}^{n}\frac{K}{jn}\leq\frac{B+K\log
n}{n}.$

Recall that
$|{\cal{L}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg})|=|X_{t,0}-X_{t,n}|$
and for every $t\in[T]$, we have
$\sum_{i=1}^{n}|X_{t,i}-X_{t,i-1}|^{2}\leq\frac{(B+K\log n)^{2}}{n}$. As a
result, applying Azuma-Hoeffding’s inequality, we obtain

$\displaystyle\operatorname{\mathbb{P}}(|{\cal{L}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg})|\geq\tau)\leq
2e^{-\frac{n\tau^{2}}{2(B+K\log n)^{2}}},\quad\forall t\in[T].$ (12)

Let us consider
$Y_{t}:={\cal{L}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg})$ for
$t\in[T]$. Then, $(Y_{t})_{t=1}^{T}$ are i.i.d. zero mean sub-Gaussian random
variables. There exists an absolute constant $c_{1}>0$ such that, the
subgaussian norm, denoted by $\|{\cdot}\|_{\psi_{2}}$, obeys
$\|{Y_{t}}\|_{\psi_{2}}^{2}<\frac{c_{1}(B+K\log n)^{2}}{n}$ by [53,
Proposition 2.5.2]. Applying Hoeffding’s inequality, we derive

$\displaystyle\operatorname{\mathbb{P}}\left(\bigg{|}\frac{1}{T}\sum_{t=1}^{T}Y_{t}\bigg{|}\geq\tau\right)\leq
2e^{-\frac{cnT\tau^{2}}{(B+K\log
n)^{2}}}\Longrightarrow\operatorname{\mathbb{P}}(|{\widehat{\cal{L}}}(\texttt{Alg})-{\cal{L}}(\texttt{Alg})|\geq\tau)\leq
2e^{-\frac{cnT\tau^{2}}{(B+K\log n)^{2}}}$ (13)

where $c>0$ is an absolute constant. Therefore, we have that for any
$\texttt{Alg}\in\mathcal{A}$, with probability at least $1-2\delta$,

$\displaystyle|{\widehat{\cal{L}}}(\texttt{Alg})-{\cal{L}}(\texttt{Alg})|\leq(B+K\log
n)\sqrt{\frac{\log(1/\delta)}{cnT}}.$ (14)

Step 2: Next, we turn to bound
$\sup_{\texttt{Alg}\in\mathcal{A}}|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|$
where $\mathcal{A}$ is assumed to be a continuous search space. To start with,
set
$g(\texttt{Alg}):={\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})$
and we aim to bound $\sup_{\texttt{Alg}\in\mathcal{A}}|g(\texttt{Alg})|$.
Following Definition 2, for $\varepsilon>0$, let $\mathcal{A}_{\varepsilon}$
be a minimal $\varepsilon$-cover of $\mathcal{A}$ in terms of distance metric
$\rho$. Therefore, $\mathcal{A}_{\varepsilon}$ is a discrete set with
cardinality
$|\mathcal{A}_{\varepsilon}|:={\cal{N}}(\mathcal{A},\rho,\varepsilon)$. Then,
we have

$\sup_{\texttt{Alg}\in\mathcal{A}}|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|\leq\sup_{\texttt{Alg}\in\mathcal{A}}\min_{\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})\right|+\max_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})\right|.$

$\bullet$ We start by bounding
$\sup_{\texttt{Alg}\in\mathcal{A}}\min_{\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})\right|$.
We will utilize that loss function $\ell(\cdot,\cdot)$ is $L$-Lipschitz. For
any $\texttt{Alg}\in\mathcal{A}$, let
$\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}$ be its neighbor following
Definition 2. We have that

$\displaystyle\left|{\widehat{\cal{L}}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg}^{\prime})\right|$
$\displaystyle=\left|\frac{1}{nT}\sum_{t=1}^{T}\sum_{i=1}^{n}\left(\ell(\bm{y}_{ti},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti}))-\ell(\bm{y}_{ti},{f^{\texttt{Alg}^{\prime}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti}))\right)\right|$
$\displaystyle\leq\frac{L}{nT}\sum_{t=1}^{T}\sum_{i=1}^{n}\left\|{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti})-{f^{\texttt{Alg}^{\prime}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{ti})\right\|_{\ell_{2}}$
$\displaystyle\leq L\varepsilon.$

Since the same bound applies to all data-sequences, we also obtain that for
any $\texttt{Alg}\in\mathcal{A}$,

$\left|{\cal{L}}(\texttt{Alg})-{\cal{L}}(\texttt{Alg}^{\prime})\right|\leq
L\varepsilon.$

Therefore,

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\sup_{\texttt{Alg}\in\mathcal{A}}\min_{\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})\right|\leq\sup_{\texttt{Alg}\in\mathcal{A}}\min_{\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}}\left|{\widehat{\cal{L}}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg}^{\prime})\right|+\left|{\cal{L}}(\texttt{Alg})-{\cal{L}}(\texttt{Alg}^{\prime})\right|\leq
2L\varepsilon$}}.$ (15)

$\bullet$ Next, we turn to bound the second term
$\max_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})\right|$.
Applying union bound directly on $\mathcal{A}_{\varepsilon}$ and combining it
with (14), then we will have that with probability at least $1-2\delta$,

$\displaystyle\max_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})\right|\leq(B+K\log
n)\sqrt{\frac{\log({\cal{N}}(\mathcal{A},\rho,\varepsilon)/\delta)}{cnT}}.$
(16)

Proof of Eq. (4): Combining the upper bound above with the perturbation bound
(15), we obtain that

$\max_{\texttt{Alg}\in\mathcal{A}}\left|g(\texttt{Alg})\right|\leq
2L\varepsilon+(B+K\log
n)\sqrt{\frac{\log({\cal{N}}(\mathcal{A},\rho,\varepsilon)/\delta)}{cnT}}.$

This in turn concludes the proof of (4) since
${R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq
2\sup_{\texttt{Alg}\in\mathcal{A}}|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|.$

Proof of Eq. (5): To conclude, we aim to establish (5). To this end, we will
bound
$\max_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})\right|$
via successive $\varepsilon$-covers which is the chaining argument. Following
Definition 2, let
$D:=\sup_{\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}}\rho(\texttt{Alg},\texttt{Alg}^{\prime})$.
Define $M:=\min\\{m:2^{m}\varepsilon\geq D\\}$, and for any $m\in[M]$, let
$\mathcal{U}_{m}$ denote the minimal $2^{m}\varepsilon$-cover of
$\mathcal{U}_{m-1}$, where $\mathcal{U}_{0}:=\mathcal{A}_{\varepsilon}$. Since
$\mathcal{U}_{M}\subseteq\mathcal{U}_{M-1}\cdots\subseteq\mathcal{U}_{0}\subset\mathcal{A}$,
we have
$|\mathcal{U}_{m}|={\cal{N}}(\mathcal{U}_{m-1},\rho,2^{m}\varepsilon)\leq{\cal{N}}(\mathcal{A},\rho,2^{m}\varepsilon)$
and $|\mathcal{U}_{M}|\leq{\cal{N}}(\mathcal{A},\rho,D)=1$. Let
$\texttt{Alg}^{M}\in\mathcal{U}_{M}$ denote the unique algorithm hypothesis in
$\mathcal{U}_{M}$. We have that

$\displaystyle\max_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})\right|$
$\displaystyle\leq\max_{\texttt{Alg}\in\mathcal{U}_{0}}\left|g(\texttt{Alg})-g(\texttt{Alg}^{M})\right|+\left|g(\texttt{Alg}^{M})\right|$
$\displaystyle\leq\sum_{m=0}^{M-1}\max_{\texttt{Alg}\in\mathcal{U}_{m}}\min_{\texttt{Alg}^{\prime}\in\mathcal{U}_{m+1}}\left|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})\right|+\left|g(\texttt{Alg}^{M})\right|.$
(17)

In what follows, we will prove that for any
$\texttt{Alg},\texttt{Alg}^{\prime}$ satisfying
$\rho(\texttt{Alg},\texttt{Alg}^{\prime})\leq u~{}(u>0)$, with high
probability, $\left|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})\right|$ is
bounded by $\frac{u}{\sqrt{nT}}$ up to logarithmic terms.

Apply similar martingale sequence analysis as in Step 1. This time, we set
$X_{t,i}=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg}^{\prime})|{{\mathcal{S}}^{(i)}_{t}}]$
where we assume $\rho(\texttt{Alg},\texttt{Alg}^{\prime})\leq u$. Similarly,
we have that
$X_{t,n}={\widehat{\cal{L}}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg}^{\prime})$,
and
$X_{t,0}=\operatorname{\mathbb{E}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg}^{\prime})]={\cal{L}}_{t}(\texttt{Alg})-{\cal{L}}_{t}(\texttt{Alg}^{\prime})$.
Therefore, the sequences $\\{X_{t,0},\dots,X_{t,n}\\},t\in[T]$ are Martingale
sequences with respect to
$\operatorname{\mathbb{E}}[X_{t,i}|{{\mathcal{S}}^{(i-1)}_{t}}]=X_{t,i-1}$. We
again omit the subscript $t$ for $\bm{x},\bm{y}$ and $\mathcal{S}$ in the
following and try to bound the difference of neighbors.

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\frac{2Lu}{n}+\frac{1}{n}\sum_{j=i+1}^{n}\frac{Ku}{j}<\frac{2Lu+Ku\log
n}{n}$}}.$

for $i<n$. Here, $(d)$ is from the facts that loss function
$\ell(\cdot,\cdot)$ is $L$-Lipschitzness and
$\rho(\texttt{Alg},\texttt{Alg}^{\prime})\leq u$ by following the same
analysis in deriving (15), and $(e)$ follows the Assumption 1. Then we have

$|X_{t,n}-X_{t,n-1}|\leq\frac{2Lu}{n}<\frac{2Lu+Ku\log n}{n}.$

Note that
$|{\cal{L}}_{t}(\texttt{Alg})-{\cal{L}}_{t}(\texttt{Alg}^{\prime})-({\widehat{\cal{L}}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg}^{\prime}))|=|X_{t,0}-X_{t,n}|$
and for every $t\in[T]$, we have
$\sum_{i=1}^{n}|X_{t,i}-X_{t,i-1}|^{2}\leq\frac{u^{2}(2L+K\log n)^{2}}{n}$. As
a result of applying Azuma-Hoeffding’s inequality, we obtain

$\displaystyle\operatorname{\mathbb{P}}(|{\cal{L}}_{t}(\texttt{Alg})-{\cal{L}}_{t}(\texttt{Alg}^{\prime})-({\widehat{\cal{L}}}_{t}(\texttt{Alg})-{\widehat{\cal{L}}}_{t}(\texttt{Alg}^{\prime}))|\geq\tau)\leq
2e^{-\frac{n\tau^{2}}{2u^{2}(2L+K\log n)^{2}}},\quad\forall t\in[T].$

Now let us instead consider $Y_{t}:=g(\texttt{Alg})-g(\texttt{Alg}^{\prime})$
for $t\in[T]$. Then following proof as in Step 1, we derive

$\displaystyle\operatorname{\mathbb{P}}\left(\bigg{|}\frac{1}{T}\sum_{t=1}^{T}Y_{t}\bigg{|}\geq\tau\right)<2e^{-\frac{c^{\prime}nT\tau^{2}}{u^{2}(2L+K\log
n)^{2}}}\Longrightarrow\operatorname{\mathbb{P}}(|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})|\geq\tau)\leq
2e^{-\frac{c^{\prime}nT\tau^{2}}{u^{2}(2L+K\log n)^{2}}}$

where $c^{\prime}>0$ is an absolute constant. Consider the discrete set
$\mathcal{U}_{m}$ with cardinality
$|\mathcal{U}_{m}|={\cal{N}}(\mathcal{U}_{m},\rho,2^{m}\varepsilon)\leq{\cal{N}}(\mathcal{A},\rho,2^{m}\varepsilon)$
and its $2^{m+1}\varepsilon$-cover $\mathcal{U}_{m+1}$. Applying union bound
over $\mathcal{U}_{m}$, we have that with probability at least $1-2\delta$,

$\displaystyle\max_{\texttt{Alg}\in\mathcal{U}_{m}}\min_{\texttt{Alg}^{\prime}\in\mathcal{U}_{m+1}}|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})|$
$\displaystyle\leq 2^{m+1}\varepsilon(2L+K\log
n)\sqrt{\frac{\log({\cal{N}}(\mathcal{A},\rho,2^{m}\varepsilon)/\delta)}{c^{\prime}nT}}.$

Now by again applying union bound, with probability at least $1-2\delta$, the
first term in (17) is bounded by

$\displaystyle\sum_{m=0}^{M-1}\max_{\texttt{Alg}\in\mathcal{U}_{m}}\min_{\texttt{Alg}^{\prime}\in\mathcal{U}_{m+1}}\left|g(\texttt{Alg})-g(\texttt{Alg}^{\prime})\right|$
$\displaystyle\leq(2L+K\log
n)\sum_{m=0}^{M-1}2^{m+1}\varepsilon\sqrt{\frac{\log(M\cdot{\cal{N}}(\mathcal{A},\rho,2^{m}\varepsilon)/\delta)}{c^{\prime}nT}}$
$\displaystyle\leq 4(2L+K\log
n)\int_{\varepsilon/2}^{D/2}\sqrt{\frac{\log(M\cdot{\cal{N}}(\mathcal{A},\rho,u)/\delta)}{c^{\prime}nT}}du.$
(18)

Now combining the results of (14), (17) and (18), and following the evidence
that $\texttt{Alg}^{M}\in\mathcal{U}_{M}$ is unique, we bound
$\sup_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}|g(\texttt{Alg})|$ as follows,
that with probability at least $1-4\delta$

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\sup_{\texttt{Alg}\in\mathcal{A}_{\varepsilon}}\left|g(\texttt{Alg})\right|\leq
4(2L+K\log
n)\int_{\varepsilon/2}^{D/2}\sqrt{\frac{\log(M\cdot{\cal{N}}(\mathcal{A},\rho,u)/\delta)}{c^{\prime}nT}}du+(B+K\log
n)\sqrt{\frac{\log(1/\delta)}{cnT}}$}}.$ (19)

Here
$D:=\sup_{\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}}\rho(\texttt{Alg},\texttt{Alg}^{\prime})$
and $M:=\min\\{m:2^{m}\varepsilon\geq D\\}$.

$\bullet$ Combining (15) and (19), we obtain that with probability at least
$1-4\delta$,

$\displaystyle\scalebox{1.0}{\mbox{$\displaystyle\sup_{\texttt{Alg}\in\mathcal{A}}\left|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})\right|\leq\inf_{\varepsilon>0}\left\\{4L\varepsilon+4(2L+K\log
n)\int_{\varepsilon}^{D/2}\sqrt{\frac{\log(M\cdot{\cal{N}}(\mathcal{A},\rho,u)/\delta)}{c^{\prime}nT}}du+(B+K\log
n)\sqrt{\frac{\log(1/\delta)}{cnT}}\right\\}$}},$

where
$D:=\sup_{\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}}\rho(\texttt{Alg},\texttt{Alg}^{\prime})$
and $M:=\min\\{m:2^{m+1}\varepsilon\geq D\\}\leq\log\frac{D}{\varepsilon}$.

Applying ${R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq
2\sup_{\texttt{Alg}\in\mathcal{A}}\left|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})\right|$
completes the proof.

Till now, we consider the setting where each task is trained with only one
trajectory. In the following, we also consider the case where each task
contains multiple trajectories. To start with, we define the following
objective function as an extension of (ICL-ERM) to the multi-trajectory
setting.

$\displaystyle\
{\widehat{\texttt{Alg}}}=\arg\min_{\texttt{Alg}\in\mathcal{A}}$
$\displaystyle{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg}):=\frac{1}{TM}\sum_{t=1}^{T}\sum_{m=1}^{M}{\widehat{\cal{L}}}_{t,m}(\texttt{Alg})$
(20) where
$\displaystyle{\widehat{\cal{L}}}_{t,m}(\texttt{Alg})=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{tmi},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{tmi})).$

Here, we assume each task $t\in[T]$ contains $M$ trajectories, and
${\mathcal{S}_{\text{all}}}=\\{\\{\mathcal{S}_{t,m}\\}_{m=1}^{M}\\}_{t=1}^{T}$
where $\mathcal{S}_{t,m}=\\{(\bm{x}_{tmi},\bm{y}_{tmi})\\}_{i=1}^{n}$ and
$(\bm{x}_{tmi},\bm{y}_{tmi})\overset{\text{i.i.d.}}{\sim}{\cal{D}}_{t}$. Then
the following theorem states a more general version of Theorem 2.

###### Theorem 6

Suppose the same assumptions as in Theorem 2 hold and let
${\widehat{\texttt{Alg}}}$ be the empirical solution of (20). Then, with the
same probability, we obtain identical bounds to Theorem 2 by updating $T$ with
$TM$ in Equations (4) and (5).

Choosing $M=1$ results in the exactly same bound as in Theorem 2.

Proof. Following the same proof steps, and then we derive similar result as
(12):

$\displaystyle\operatorname{\mathbb{P}}(|{\cal{L}}_{t,m}(\texttt{Alg})-{\widehat{\cal{L}}}_{t,m}(\texttt{Alg})|\geq\tau)\leq
2e^{-\frac{n\tau^{2}}{2(B+K\log n)^{2}}},\quad\forall t\in[T],m\in[M].$ (21)

Let
$Y_{t,m}:={\cal{L}}_{t,m}(\texttt{Alg})-{\widehat{\cal{L}}}_{t,m}(\texttt{Alg})$.
Since in-context samples are independent, $((Y_{t,m})_{m=1}^{M})_{t=1}^{T}$
are independent zero mean sub-Gaussian random variables, with norm
$\|{Y_{t,m}}\|_{\psi_{2}}<\frac{c_{1}(B+K\log n)^{2}}{n}$. Applying
Hoeffding’s inequality, we derive

$\displaystyle\operatorname{\mathbb{P}}(|{\widehat{\cal{L}}}(\texttt{Alg})-{\cal{L}}(\texttt{Alg})|\geq\tau)\leq
2e^{-\frac{cnMT\tau^{2}}{(B+K\log n)^{2}}}$ (22)

where $c>0$ is an absolute constant. Therefore, we have that for any
$\texttt{Alg}\in\mathcal{A}$, with probability at least $1-2\delta$,

$\displaystyle|{\widehat{\cal{L}}}(\texttt{Alg})-{\cal{L}}(\texttt{Alg})|\leq(B+K\log
n)\sqrt{\frac{\log(1/\delta)}{cnMT}}.$ (23)

The result is simply replacing $T$ with $MT$ in (14). It is from the fact that
trajectories are all independent no matter they are from the same task or not.
By applying the similar analysis, the proof is competed.

###  B.2 Transfer Discussion from the Lens of Task Diversity

In Section 4, we motivated the fact that transfer risk is controlled in terms
of MTL risk and an additive term that captures the distributional distance
i.e.
${\cal{L}}_{\mathcal{T}}(\texttt{Alg})\leq{\cal{L}}_{{\text{MTL}}}(\texttt{Alg})+\text{dist}(\mathcal{T},({\cal{D}}_{t})_{t=1}^{T})$.
The following definition is a generalization of this relation which can be
used to formally control the transfer risk in terms of MTL risk.

######  Definition 4 (Task diversity)

Following Section 2, we say that task $\mathcal{T}$ is
$(\nu,\epsilon)$-diverse over the $T$ source tasks if for any
$\texttt{Alg},\texttt{Alg}^{\prime}\in\mathcal{A}$,

$\displaystyle{\cal{L}}_{\mathcal{T}}(\texttt{Alg})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\prime})\leq\left(\frac{1}{T}\sum_{t=1}^{T}\left({\cal{L}}_{t}(\texttt{Alg})-{\cal{L}}_{t}(\texttt{Alg}^{\prime})\right)\right)/{\nu}+\epsilon.$

Now let us discuss transferability in light of this assumption and Thm 2.
Consider the scenario where $n$ is small and $T\to\infty$. The excess MTL risk
will be small thanks to infinitely many tasks. The transfer risk would also be
small because larger $T$ results in higher diversity covering the task space.
However, if the target task uses a different/longer prompt length, transfer
may fail since the model never saw prompts longer than $n$. Conversely, if we
let $n\to\infty$ and $T$ to be small, although the MTL risk is again zero, due
to lack of diversity, it may not benefit transfer learning strongly. Task
diversity assumption leads to the following lemma that bounds transfer
learning in terms of MTL risk.

###### Lemma 4

Consider the setting of Theorem 2. Let ${\widehat{\texttt{Alg}}}$ be the
solution of (ICL-ERM) and assume that target task $\mathcal{T}$ is
$(\nu,\epsilon)$-diverse over $T$ source tasks. Then with the same probability
as in Theorem 2, the excess transfer learning risk
$R_{\mathcal{T}}({\widehat{\texttt{Alg}}})={\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})-\min_{\texttt{Alg}\in\mathcal{A}}{\cal{L}}_{\mathcal{T}}(\texttt{Alg})$
obeys
$R_{\mathcal{T}}({\widehat{\texttt{Alg}}})\leq\frac{{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})}{\nu}+2\epsilon$.

Here we emphasize that the statement holds for arbitrary source and target
tasks; however the challenge is verifying the assumption which is left as an
interesting and challenging future direction. On the bright side, as
illustrated in Figures 4&5, we indeed observe that, transfer learning can work
with reasonably small $T$ and it works better if the target task is closer to
the source tasks.

Proof. Let ${\widehat{\texttt{Alg}}},\texttt{Alg}^{\star}$ be the empirical
and population solutions of (ICL-ERM) and let
$\texttt{Alg}^{\dagger}:=\underset{\texttt{Alg}\in\mathcal{A}}{\arg\min}{\cal{L}}_{\mathcal{T}}(\texttt{Alg})$.
Then the transfer learning excess test risk of given algorithm
${\widehat{\texttt{Alg}}}\in\mathcal{A}$ is formulated as

$\displaystyle R_{\mathcal{T}}({\widehat{\texttt{Alg}}})$
$\displaystyle={\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\dagger})$
$\displaystyle={\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\star})+{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\star})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\dagger}).$

Since target task $\mathcal{T}$ is $(\nu,\varepsilon)$-diverse over source
tasks, following Definition 4, we derive that

$\displaystyle{\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\star})\leq\frac{{\cal{L}}_{\text{MTL}}({\widehat{\texttt{Alg}}})-{\cal{L}}_{\text{MTL}}(\texttt{Alg}^{\star})}{\nu}+\varepsilon=\frac{{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})}{\nu}+\varepsilon$
$\displaystyle{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\star})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\dagger})\leq\frac{{\cal{L}}_{\text{MTL}}(\texttt{Alg}^{\star})-{\cal{L}}_{\text{MTL}}(\texttt{Alg}^{\dagger})}{\nu}+\varepsilon\leq\varepsilon.$

Here, since $\texttt{Alg}^{\star}$ is the minimizer of
${\cal{L}}_{\text{MTL}}(\texttt{Alg})$,
${\cal{L}}_{\text{MTL}}(\texttt{Alg}^{\star})-{\cal{L}}_{\text{MTL}}(\texttt{Alg}^{\dagger})\leq
0$. Then, Lemma 4 is easily proved by combining the above two inequalities.

###  B.3 Transfer Learning Bound with i.i.d. Tasks

Following training with (ICL-ERM), suppose source tasks are i.i.d. sampled
from a task distribution ${\cal{D}}_{\text{task}}$, and let
${\widehat{\texttt{Alg}}}$ be the empirical MTL solution. We consider the
following transfer learning problem. Concretely, assume a target task
$\mathcal{T}$ with a distribution $\mathcal{T}\sim{\cal{D}}_{\text{task}}$ and
training sequence
$\mathcal{S}_{\mathcal{T}}=({\bm{z}}_{i})_{i=1}^{n}\sim{\cal{D}}_{\mathcal{T}}$.
Define the empirical and population risks on $\mathcal{T}$ as
${\widehat{\cal{L}}}_{\mathcal{T}}(\texttt{Alg})=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{i},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{\mathcal{T}}}}}(\bm{x}_{i}))$
and
${\cal{L}}_{\mathcal{T}}(\texttt{Alg})=\operatorname{\mathbb{E}}_{\mathcal{S}_{\mathcal{T}}}[{\widehat{\cal{L}}}_{\mathcal{T}}(\texttt{Alg})]$.
Then the expected excess transfer risk following (ICL-ERM) is defined as

$\displaystyle\operatorname{\mathbb{E}}_{\mathcal{T}}[\mathcal{R}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]=\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]-\arg\min_{\texttt{Alg}\in\mathcal{A}}\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})].$
(24)

###### Theorem 7

Consider the setting of Theorem 2 and assume the source tasks are
independently drawn from task distribution ${\cal{D}}_{\text{task}}$. Let
${\widehat{\texttt{Alg}}}$ be the empirical solution of (ICL-ERM) and
$\mathcal{T}\sim{\cal{D}}_{\text{task}}$. Then with probability at least
$1-2\delta$, the expected excess transfer learning risk (24) obeys

$\displaystyle\operatorname{\mathbb{E}}_{\mathcal{T}}[\mathcal{R}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]\leq\min_{\varepsilon\geq
0}\left\\{4L\varepsilon+B\sqrt{\frac{2\log({\cal{N}}(\mathcal{A},\rho,\varepsilon)/\delta)}{T}}\right\\}.$
(25)

Proof. Recap the problem setting in Section 2 and let
$\texttt{Alg}^{\dagger}=\arg\min_{\texttt{Alg}\in\mathcal{A}}\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})]$.
The expected transfer learning excess test risk of given algorithm
${\widehat{\texttt{Alg}}}\in\mathcal{A}$ is formulated as

$\displaystyle\operatorname{\mathbb{E}}_{\mathcal{T}}[\mathcal{R}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]-\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\dagger})]$
(26)
$\displaystyle=\underset{a}{\underbrace{\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]-{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}({\widehat{\texttt{Alg}}})}}+\underset{b}{\underbrace{{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}({\widehat{\texttt{Alg}}})-{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg}^{\dagger})}}+\underset{c}{\underbrace{{\widehat{\cal{L}}}_{\mathcal{S}_{\text{all}}}(\texttt{Alg}^{\dagger})-\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\dagger})]}}.$
(27)

Here since ${\widehat{\texttt{Alg}}}$ is the minimizer of training risk,
$b<0$. Then we obtain

$\displaystyle\operatorname{\mathbb{E}}_{\mathcal{T}}[\mathcal{R}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]\leq
2\sup_{\texttt{Alg}\in\mathcal{A}}\left|\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})]-\frac{1}{T}\sum_{t=1}^{T}{\widehat{\cal{L}}}_{t}(\texttt{Alg})\right|.$
(28)

For any $\texttt{Alg}\in\mathcal{A}$, let
$X_{t}={\widehat{\cal{L}}}_{t}(\texttt{Alg})$ and we observe that

$\operatorname{\mathbb{E}}_{t\sim{\cal{D}}_{\text{task}}}[X_{t}]=\operatorname{\mathbb{E}}_{t\sim{\cal{D}}_{\text{task}}}[{\widehat{\cal{L}}}_{t}(\texttt{Alg})]=\operatorname{\mathbb{E}}_{t\sim{\cal{D}}_{\text{task}}}[{\cal{L}}_{t}(\texttt{Alg})]=\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})].$

Since $X_{t}$, $t\in[T]$ are independent, and $0\leq X_{t}\leq B$, applying
Hoeffding’s inequality obeys

$\displaystyle\operatorname{\mathbb{P}}\left(\left|\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})]-\frac{1}{T}\sum_{t=1}^{T}{\widehat{\cal{L}}}_{t}(\texttt{Alg})\right|\geq\tau\right)\leq
2e^{-\frac{2T\tau^{2}}{B^{2}}}.$ (29)

Then with probability at least $1-2\delta$, we have that for any
$\texttt{Alg}\in\mathcal{A}$,

$\displaystyle\left|\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})]-\frac{1}{T}\sum_{t=1}^{T}{\widehat{\cal{L}}}_{t}(\texttt{Alg})\right|\leq
B\sqrt{\frac{\log(1/\delta)}{2T}}.$ (30)

Next, let $\mathcal{A}_{\varepsilon}$ be the minimal $\varepsilon$-cover of
$\mathcal{A}$ following Definition 1, which implies that for any task
$\mathcal{T}\sim{\cal{D}}_{\text{task}}$, and any
$\texttt{Alg}\in\mathcal{A}$, there exists
$\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}$

$|{\cal{L}}_{\mathcal{T}}(\texttt{Alg})-{\cal{L}}_{\mathcal{T}}(\texttt{Alg}^{\prime})|,|{\widehat{\cal{L}}}_{\mathcal{T}}(\texttt{Alg})-{\widehat{\cal{L}}}_{\mathcal{T}}(\texttt{Alg}^{\prime})|\leq
L\varepsilon.$

Since the distance metric following Definition 2 is defined by the worst-case
datasets, then there exists
$\texttt{Alg}^{\prime}\in\mathcal{A}_{\varepsilon}$ such that

$\displaystyle\left|\operatorname{\mathbb{E}}_{\mathcal{T}}[{\cal{L}}_{\mathcal{T}}(\texttt{Alg})]-\frac{1}{T}\sum_{t=1}^{T}{\widehat{\cal{L}}}_{t}(\texttt{Alg})\right|\leq
2L\varepsilon.$ (31)

Let ${\cal{N}}(\mathcal{A},\rho,\varepsilon)=|\mathcal{A}_{\varepsilon}|$ be
the $\varepsilon$-covering number. Combining the above inequalities ((28),
(30) and (31)), and applying union bound, we have that with probability at
least $1-2\delta$,

$\operatorname{\mathbb{E}}_{\mathcal{T}}[\mathcal{R}_{\mathcal{T}}({\widehat{\texttt{Alg}}})]\leq\min_{\varepsilon\geq
0}\left\\{4L\varepsilon+B\sqrt{\frac{2\log({\cal{N}}(\mathcal{A},\rho,\varepsilon)/\delta)}{T}}\right\\}.$

###  B.4 Model Selection and Approximation Error Analysis

To proceed with our analysis, we need to make assumptions about what kind of
algorithms are realizable by transformers. Given ERM is the work-horse of
modern machine learning with general hypothesis classes, we assume that
transformers can approximately perform in-context ERM. Hypothesis 1 states
that the algorithms induced by the transformer can compete with empirical risk
minimization over a family of hypothesis classes.

With this hypothesis, instead of searching over the entire hypothesis space
${\mathcal{F}_{\text{all}}}:=\bigcup_{i=1}^{H}\mathcal{F}_{i}$, given prompt
length $m$ we search over the hypothesis space $\mathcal{F}_{h_{m}}$ only, and
${\text{comp}}(\mathcal{F}_{m})\leq{\text{comp}}({\mathcal{F}_{\text{all}}})$
where ${\text{comp}}(\cdot)$ captures the complexity of a hypothesis class.

In Hypothesis 1, we assume that $\mathbb{F}$ is a family of countable
hypothesis classes with $|\bm{F}|=H$. As stated in Section 5, $\mathbb{F}$ is
not necessary to be discrete. The following provides some examples of
$\mathbb{F}$, where the first three correspond to discrete model selection
whereas the left are continuous.

  * •

$\mathbb{F}^{\text{sparse}}=\\{\mathcal{F}_{s}:s\text{-sparse linear
model}\\}$,

  * •

$\mathbb{F}^{\text{NN}}=\\{\mathcal{F}_{s}:2\text{-layer neural net with width
$s$}\\}$,

  * •

$\mathbb{F}^{\text{RF}}=\\{\mathcal{F}_{s}:\text{Random forest with $s$
trees}\\}$,

  * •

$\mathbb{F}^{\text{ridge}}=\\{\mathcal{F}_{\lambda}:\text{Linear model with
parameter bounded by $\|{{\bm{\beta}}}\|_{\ell_{2}}\leq\lambda$}\\}$ (akin to
ridge regression)

  * •

$\mathbb{F}^{\text{weighted}}=\\{\mathcal{F}_{\bm{{\Sigma}}}:\text{Linear
model with covariance-prior ${\bm{{\Sigma}}}$,
${\bm{\beta}}^{\top}{\bm{{\Sigma}}}^{-1}{\bm{\beta}}\leq 1$}\\}$ (akin to
weighted ridge).

To proceed, let us introduce the following classical result that controls the
test risk of an ERM solution in terms of the Rademacher complexity [35, 32].

###### Theorem 8

Let $\mathcal{F}:\mathcal{X}\rightarrow\mathcal{Y}$ be a hypothesis set and
let
$\mathcal{S}=(\bm{x}_{i},\bm{y}_{i})_{i=1}^{n}\in\mathcal{X}\times\mathcal{Y}$
be a dataset sampled i.i.d. from distribution ${\cal{D}}$. Let
$\ell(\bm{y},\hat{\bm{y}})$ be a loss function takes values in $[0,B]$. Here
$\ell(\bm{y},\cdot)$ is $L$-Lipschitz in terms of Euclidean norm for all
$\bm{y}\in\mathcal{Y}$. Consider a learning problem that

$\displaystyle\hat{f}:=\arg\min_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{i},f(\bm{x}_{i})).$
(32)

Let ${\cal{L}}^{\star}=\min_{f\in\mathcal{F}}{\cal{L}}(f)$ where
${\cal{L}}(f)=\operatorname{\mathbb{E}}[\ell(\bm{y},f(\bm{x}))]$. Then we have
that with probability at least $1-2\delta$, the excess test risk obeys

${\cal{L}}(\hat{f})-{\cal{L}}^{\star}\leq
8L\mathcal{R}_{n}(\mathcal{F})+4B\sqrt{\frac{\log\frac{1}{\delta}}{n}},$

where
$\mathcal{R}_{n}(\mathcal{F})=\operatorname{\mathbb{E}}_{\mathcal{S}}\operatorname{\mathbb{E}}_{{\bm{{\sigma}}}_{i}}[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}{\bm{{\sigma}}}_{i}^{\top}f(\bm{x}_{i})]$
is the Rademacher complexity of $\mathcal{F}$ [35] and ${\bm{{\sigma}}}_{i}$’s
are vectors with Rademacher random variable in each entry.

######  Lemma 5 (Formal version of Observation 1)

Let
${\cal{L}}_{\mathcal{T}}^{\star}:=\min_{\texttt{Alg}\in\mathcal{A}}{\cal{L}}_{\mathcal{T}}(\texttt{Alg})$
be the optimal target risk as stated in Section 2. Assume that Hypothesis 1
holds, then the approximation error obeys

$\displaystyle{\cal{L}}_{\mathcal{T}}^{\star}\leq\frac{1}{n}\sum_{m=1}^{n-1}\min_{h\in[H]}\left\\{{\cal{L}}_{h}^{\star}+8L\mathcal{R}_{m}(\mathcal{F}_{h})+\varepsilon_{{\texttt{TF}}}^{h,m}\right\\}+\frac{cB}{\sqrt{n}},$
(33)

where $\mathcal{R}_{m}(\mathcal{F})$ is the Rademacher complexity over data
distribution ${\cal{D}}_{\mathcal{T}}$, and
${\cal{L}}^{\star}_{{h}}=\min_{f\in\mathcal{F}_{h}}\operatorname{\mathbb{E}}[\ell(\bm{y},f(\bm{x}))]$.

Proof. Let us assume Hypothesis 1 holds for algorithm
${\widetilde{\texttt{Alg}}}\in\mathcal{A}$. Since
${\cal{L}}^{\star}_{\mathcal{T}}$ is the minimal test loss, we have that

$\displaystyle{\cal{L}}_{\mathcal{T}}^{\star}\leq{\cal{L}}_{\mathcal{T}}({\widetilde{\texttt{Alg}}})=\operatorname{\mathbb{E}}_{\mathcal{S}_{\mathcal{T}}}\left[\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{y}_{i},f^{\widetilde{\texttt{Alg}}}_{{{\mathcal{S}}^{(i-1)}}}(\bm{x}_{i}))\right]=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{(\bm{x},\bm{y},{{\mathcal{S}}^{(i-1)}})}\left[\ell(\bm{y},f^{\widetilde{\texttt{Alg}}}_{{{\mathcal{S}}^{(i-1)}}}(\bm{x}))\right].$

Then by directly applying Hypothesis 1 we have that

$\displaystyle{\cal{L}}_{\mathcal{T}}^{\star}$
$\displaystyle\leq\frac{1}{n}\operatorname{\mathbb{E}}_{(\bm{x},\bm{y})}\left[\ell(\bm{y},f^{\widetilde{\texttt{Alg}}}_{{{\mathcal{S}}^{(0)}}}(\bm{x}))\right]+\frac{1}{n}\sum_{i=1}^{n-1}\operatorname{\mathbb{E}}_{(\bm{x},\bm{y},{{\mathcal{S}}^{(i)}})}\left[\ell(\bm{y},f^{\widetilde{\texttt{Alg}}}_{{{\mathcal{S}}^{(i)}}}(\bm{x}))\right]$
(34)
$\displaystyle\leq\frac{B}{n}+\frac{1}{n}\sum_{m=1}^{n-1}\min_{h\in[H]}\left\\{\text{risk}(h,m)+\varepsilon_{{\texttt{TF}}}^{h,m}\right\\}.$
(35)

Here the first term in (35) comes from the fact that loss function is bounded
by $B$, and we assume ${{\mathcal{S}}^{(0)}}=\emptyset$, and the second term
follows the Hypothesis 1. Next, we turn to bound $\text{risk}(h,m)$. To
proceed, let
$X^{h,m}:=\operatorname{\mathbb{E}}_{(\bm{x},\bm{y})}\left[\ell(\bm{y},\hat{f}^{(h)}_{{{\mathcal{S}}^{(m)}}}(\bm{x}))\right]$
be the random variables, where we have $|X^{h,m}|\leq B$. Following Theorem 8,
we have that for any $m\in[n],h\in[H]$

$\displaystyle\operatorname{\mathbb{P}}\left(X^{h,m}-{\cal{L}}^{\star}_{h}-8L\mathcal{R}_{m}(\mathcal{F}_{h})\geq\tau\right)\leq
2e^{-\frac{m\tau^{2}}{16B^{2}}}.$

The upper-tail bound of the last line implies that there exists an absolute
constant $c>0$ such that

$\displaystyle\text{risk}(h,m)=\operatorname{\mathbb{E}}_{{{\mathcal{S}}^{(m)}}}\left[X^{h,m}\right]\leq{\cal{L}}^{\star}_{h}+8L\mathcal{R}_{m}(\mathcal{F}_{h})+\frac{cB}{\sqrt{m}}.$

Combining it with (35) and following the evidence
$\sum_{m=1}^{n}\frac{1}{\sqrt{m}}\leq 2\sqrt{n}$ complete the proof.

##  Appendix C Proof of Theorem 3

###### Lemma 6

Suppose Assumptions 2 and 3 hold. Assume input and noise spaces
$\mathcal{X},{\cal{W}}$ are bounded by $\bar{x},\bar{w}$. Let
$W=(\bm{w}_{1},\dots,\bm{w}_{j},\bm{w}_{j+1},\dots,\bm{w}_{m})$ and
$W^{\prime}=(\bm{w}_{1},\dots,\bm{w}_{j-1},\bm{w}^{\prime}_{j},\bm{w}_{j+1},\dots,\bm{w}_{m})$
be two arbitrary sequences and the only difference between $W$ and
$W^{\prime}$ is the $j$’th term of the sequence. Then, for any
$f\in\mathcal{F}$, $\texttt{Alg}\in\mathcal{A}$, $W$, $W^{\prime}$, $m$, and
$j<m$, we have the following:

$\displaystyle\Bigg{|}\operatorname{\mathbb{E}}_{\bm{x}_{m+1}}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{\mathcal{S}}^{(m)}}(\bm{x}_{m}))\right]-\operatorname{\mathbb{E}}_{\bm{x}_{m+1}}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}_{j}}}(\bm{x}^{\prime}_{m}))\right]\Bigg{|}<\frac{K}{m}\frac{2\bar{C}_{\rho}\bar{w}}{1-\bar{\rho}}.$

Additionally, focusing on the sequences that differ only at their initial
states, for any $\bm{x}_{0},\bm{x}_{0}^{\prime}\in\mathcal{X}$, we have

$\displaystyle\Bigg{|}\operatorname{\mathbb{E}}_{\bm{x}_{m+1}}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{\mathcal{S}}^{(m)}}(\bm{x}_{m}))\right]-\operatorname{\mathbb{E}}_{\bm{x}_{m+1}}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}_{j}}}(\bm{x}^{\prime}_{m}))\right]\Bigg{|}<\frac{K}{m}\frac{2\bar{C}_{\rho}\bar{x}}{1-\bar{\rho}}.$

Proof. First, let us bound $\left\|\bm{x}_{i}-\bm{x}_{i}^{\prime}\right\|_{2}$
for every $i=j,\dots,n$. For $i=j$, since ${\cal{W}}$ is bounded by $\bar{w}$,
we have

$\displaystyle\left\|\bm{x}_{j}-\bm{x}_{j}^{\prime}\right\|_{2}=\left\|f(\bm{x}_{j-1})+\bm{w}_{j}-f(\bm{x}_{j-1})-\bm{w}_{j}^{\prime}\right\|_{2}\leq
2\bar{w}.$

For $i>j$, we have the following from Assumption 2:

$\displaystyle\left\|\bm{x}_{i}-\bm{x}_{i}^{\prime}\right\|_{2}\leq\bar{C}_{\rho}\bar{\rho}^{(i-j)}\left\|\bm{x}_{j}-\bm{x}_{j}^{\prime}\right\|_{2}\leq
2\bar{C}_{\rho}\bar{\rho}^{(i-j)}\bar{w}.$

Finally, using Assumption 3, we obtain

$\displaystyle\Bigg{|}\operatorname{\mathbb{E}}_{(\bm{x}_{m+1})}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{\mathcal{S}}^{(m)}}(\bm{x}_{m}))\right]-$
$\displaystyle\operatorname{\mathbb{E}}_{(\bm{x}_{m+1})}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}_{j}}}(\bm{x}_{m}^{\prime}))\right]\Bigg{|}$
$\displaystyle\leq\frac{K}{m}\sum_{i=j}^{m}\left\|\bm{x}_{i}-\bm{x}^{\prime}_{i}\right\|_{2}$
$\displaystyle\leq\frac{K}{m}2\bar{C}_{\rho}\bar{w}\sum_{i=j}^{m}\bar{\rho}^{i-j}<\frac{K}{m}\frac{2\bar{C}_{\rho}\bar{w}}{1-\bar{\rho}}.$

To prove the second part of the lemma, similarly we have

$\left\|\bm{x}_{0}-\bm{x}_{0}^{\prime}\right\|_{2}\leq 2\bar{x}\quad\text{and
then,}\quad\left\|\bm{x}_{i}-\bm{x}_{i}^{\prime}\right\|_{2}\leq
2\bar{C}_{\rho}\bar{\rho}^{i}\bar{x}.$

Again using Assumption 3, we obtain

$\displaystyle\Bigg{|}\operatorname{\mathbb{E}}_{(\bm{x}_{m+1})}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{\mathcal{S}}^{(m)}}(\bm{x}_{m}))\right]-$
$\displaystyle\operatorname{\mathbb{E}}_{(\bm{x}_{m+1})}\left[\ell(\bm{x}_{m+1},f^{\texttt{Alg}}_{{{\mathcal{S}}^{(m)}_{j}}}(\bm{x}_{m}^{\prime}))\right]\Bigg{|}$
$\displaystyle\leq\frac{K}{m}\sum_{i=0}^{m}\left\|\bm{x}_{i}-\bm{x}^{\prime}_{i}\right\|_{2}$
$\displaystyle\leq\frac{K}{m}2\bar{C}_{\rho}\bar{x}\sum_{i=0}^{m}\bar{\rho}^{i}<\frac{K}{m}\frac{2\bar{C}_{\rho}\bar{x}}{1-\bar{\rho}}.$

######  Theorem 9 (Theorem 3 restated)

Suppose Assumptions 2 and 3 hold and assume loss function
$\ell(\bm{x},\hat{\bm{x}}):\mathcal{X}\times\mathcal{X}\to[0,B]$ is an
$L$-Lipschitz function for all $\bm{x}\in\mathcal{X}$. Let
${\widehat{\texttt{Alg}}}$ be the empirical solutions of (ICL-ERM) under
dynamical setting as described in Section 2&6. Then with probability at least
$1-2\delta$, the excess MTL test risk (MTL-risk) obeys

$\scalebox{1.0}{\mbox{$\displaystyle{R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq\inf_{\varepsilon>0}\left\\{4L\varepsilon+2(B+\bar{K}\log
n)\sqrt{\frac{\log({\cal{N}}(\mathcal{A},\rho,\varepsilon)/\delta)}{cnT}}\right\\}$}}.$

where
$\bar{K}=2K\frac{{\bar{C}}_{\rho}}{1-\bar{\rho}}(\bar{w}+\bar{x}/\sqrt{n})$.

Proof. We follow the similar strategy as in the proof of Theorem 2. The main
difference is that we need to consider the dynamical system setting.
Therefore, to start with, let us recap the dynamical problem setting in
Sections 2&6. Suppose there are $T$ independent trajectories generated by $T$
dynamical systems, denoted by
$\mathcal{S}_{t}=(\bm{x}_{t0},\bm{x}_{t1},\cdots,\bm{x}_{tn})$, $t\in[T]$
where $\bm{x}_{ti}=f_{t}(\bm{x}_{t,i-1})+\bm{w}_{ti}$. Here, we consider the
prediction function
${f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i)}}}}:\mathcal{X}\rightarrow\mathcal{X}$,
and denote the previously observed sequences with
${{\mathcal{S}}^{(i)}_{t}}:=(\bm{x}_{t0},\cdots,\bm{x}_{ti})$. The objective
function in (ICL-ERM) can be rewritten as follows:

$\displaystyle{\widehat{\texttt{Alg}}}=\arg\min_{\texttt{Alg}\in\mathcal{A}}$
$\displaystyle{\widehat{\cal{L}}}_{{\mathcal{S}_{\text{all}}}}(\texttt{Alg}):=\frac{1}{T}\sum_{t=1}^{T}{\widehat{\cal{L}}}_{t}(\texttt{Alg})$
(36) where
$\displaystyle{\widehat{\cal{L}}}_{t}(\texttt{Alg})=\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{x}_{ti},{f^{\texttt{Alg}}_{{{\mathcal{S}}^{(i-1)}_{t}}}}(\bm{x}_{t,i-1})).$

Following the same argument as in the proof of Theorem 2, excess MTL risk is
bounded by:

${R_{\text{MTL}}}({\widehat{\texttt{Alg}}})\leq
2\sup_{\texttt{Alg}\in\mathcal{A}}|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|.$

Step 1: We start with the concentration bound
$|{\cal{L}}(\texttt{Alg})-{\widehat{\cal{L}}}(\texttt{Alg})|$ for any
$\texttt{Alg}\in\mathcal{A}$. Define the random variables