marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the arxiv style. Please do not change the page
layout, or include packages like geometry, savetrees, or fullpage, which
change it for you. We’re not able to reliably undo arbitrary changes to the
style. Please remove the offending package(s), or layout-changing commands and
try again.

An Information-Theoretic Analysis of
In-Context Learning

Hong Jun Jeon 1  Jason D. Lee 2  Qi Lei 3  Benjamin Van Roy 4

.

An Information-Theoretic Analysis of
In-Context Learning

Hong Jun Jeon 1  Jason D. Lee 2  Qi Lei 3  Benjamin Van Roy 4

††footnotetext:  1Department of Computer Science, Stanford University,
Stanford, CA, USA 2Princeton University, Princeton, NJ, USA 3New York
University, New York City, NY, USA 4Stanford University, Stanford, CA, USA.
Correspondence to: Hong Jun Jeon<EMAIL_ADDRESS>Hong Jun Jeon
<EMAIL_ADDRESS>

###### Abstract

Previous theoretical results pertaining to meta-learning on sequences build on
contrived assumptions and are somewhat convoluted. We introduce new
information-theoretic tools that lead to an elegant and very general
decomposition of error into three components: irreducible error, meta-learning
error, and intra-task error. These tools unify analyses across many meta-
learning challenges. To illustrate, we apply them to establish new results
about in-context learning with transformers. Our theoretical results
characterizes how error decays in both the number of training sequences and
sequence lengths. Our results are very general; for example, they avoid
contrived mixing time assumptions made by all prior results that establish
decay of error with sequence length.

##  1 Introduction

In recent years, we have observed the capability of large language models
(LLMs) to learn from data within just its context window. This puzzling
phenomenon referred to as in-context learning (ICL) (Brown et al., 2020), has
captured the attention of the theoretical machine learning community. As the
data available in-context is dwarfed by the extensive pretraining set, meta-
learning stands as a prevailing explanation for ICL Xie et al. (2022).

As aforementioned, Xie et al. (2022) introduced the idea that ICL could be
interpreted as implicit Bayesian inference within a mixture of HMMs. While
their theoretical results rely on contrived assumptions and fail to explain
how ICL is possible with such short sequences, their work _initiated_ the
study of modeling ICL as Bayesian inference or other thoroughly studied
learning processes such as empirical risk minimization. As much of the
theoretical community is most familiar with error analyses of empirical risk
minimization, much of the existing results (Li et al., 2023a; Bai et al.,
2023; Edelman et al., 2021) study the error of an ICL under the assumption
that ICL is competitive in out-of-sample performance with empirical risk
minimization. However, each of these error bounds is limited in some way such
as exponential depth dependence (Edelman et al., 2021; Li et al., 2023a) or
error which decays only with the number of sequences and not the length of the
sequences (Edelman et al., 2021; Bai et al., 2023). The results which do
demonstrate that error decays in both the number of training sequences and
sequence length often rely on contrived mixing time assumptions (Zhang et al.,
2023b) or stability conditions which are equivalent to fast mixing (Li et al.,
2023a).

Our work revisits the idea of modeling ICL as Bayesian inference. In this
work, we introduce new information-theoretic tools based on work by Jeon et
al. (2023) which lead to an elegant and very general decomposition of error in
meta-learning from sequences. This decomposition consists of three components:
irreducible error, meta-learning error, and intra-task error. This unifies
theoretical error analyses across many meta-learning challenges. Notably, our
results provide an error bound which decays linearly in both the number of
sequences and the lengths of the sequences without explicit reliance on any
stability or mixing assumptions within the sequence. To demonstrate the use of
our results, we specialize our theory to reproduce existing results in linear
representation learning and to produce new results pertaining to a sparse
mixture of transformer models. The latter result provides a compelling
narrative as to how ICL is possible with such few examples.

As some of our tools are non-standard to much of the community, we begin by
introducing our framework in the simpler setting of learning from a single
sequence of data. In the following section, we naturally extend the analysis
to meta-learning from many sequences and present our main result (Theorem
4.2). Since our results are very general and abstract, we demonstrate the
application of these results to several concrete problem instances. In the
main text, we provide concrete examples which resemble learning from data
generated by a deep transformer model and in the appendix we provide simpler
problem instances for reference (logistic regression, linear representation
learning).

##  2 Related Works

#### In-context Learning and Transformer.

LLMs based on the transformer architecture (Vaswani et al., 2023) have
exhibited the ability to learn from data within the context of a prompt (Brown
et al., 2020). This phenomenon, referred to as in-context learning (ICL), has
received significant empirical investigation (Liu et al., 2021; Min et al.,
2021; Lu et al., 2021; Zhao et al., 2021; Rubin et al., 2021; Elhage et al.,
2021; Kirsch et al., 2022; Wei et al., 2023; Brown et al., 2020; Dong et al.,
2022).

However, theoretical understanding of ICL is still relatively nascent (Xie et
al., 2022; Garg et al., 2022; Von Oswald et al., 2023; Dai et al., 2022;
Giannou et al., 2023; Li et al., 2023a; Raventos et al., 2023). Among the
existing theoretical work, most focuses on the optimization dynamics (Tian et
al., 2023a; b; Jelassi et al., 2022; Li et al., 2023b; Tarzanagh et al., 2023;
Zhang et al., 2023a; Huang et al., 2023; Ahn et al., 2023; Mahankali et al.,
2023) or the representation power (Sanford et al., 2023; Song & Zhong, 2023;
Von Oswald et al., 2023; Giannou et al., 2023; Liu et al., 2022) regarding the
transformer architecture. In the realm of statistical results, much of the
existing work is confined to how transformers can perform ICL by simulating
gradient descent (Von Oswald et al., 2023; Akyürek et al., 2022; Dai et al.,
2022; Giannou et al., 2023). However, as they provide no concrete sample
complexity results, they are therefore not directly comparable to our work.
The work that is perhaps most relevant to ours include those which analyze the
sample complexity of ICL under the assumption that its performance is
comparable to empirical risk minimization or Bayesian inference Xie et al.
(2022); Li et al. (2023a); Bai et al. (2023); Edelman et al. (2021); Zhang et
al. (2023b). Despite their quantitative sample complexity results, as
mentioned in the introduction, these results are ultimately limited by either
their restrictive assumptions on mixing times of the data sequence or their
inability to capture how sequence length contributes to reduction in error.

#### Meta-learning.

As our work analyzes ICL under the lens of meta-learning, we provide a brief
exposition of its existing work. Recent empirical advancements have sparked
interest in the theoretical foundations of meta-learning (Baxter, 2000; Denevi
et al., 2018; Finn et al., 2019). In settings such as tasks drawn from a
shared meta-distribution, several works (Maurer, 2009; Pontil & Maurer, 2013;
Maurer et al., 2016) have derived generalization bounds albeit for simplistic
settings such as linear representation or linear classifiers. Under strong
assumptions such as large margin or large number of tasks Srebro & Ben-David
(2006); Aliakbarpour et al. (2023) were also able to establish such bounds.
However, these results all rely on the assumption that the data _within_ each
meta-task is independently and identically distributed (iid) under an
(unknown) probability distribution. However, in the context of LLMs, for which
the meta-tasks are separate documents, the sequence of tokens within each
document is certainly not iid. Our work provides novel theoretical tools which
facilitate the analysis of meta-learning from sequential data which may not be
iid.

##  3 Learning from Sequential Data

For exposition, we begin by introducing our general information-theoretic
tools for the analysis of standard _supervised learning_ on sequential data.
Examples of such learning problems include but are not limited to natural
language modeling and learning from video/audio data. Phenomena such as ICL in
LLMs is another fascinating instance of machine learning from sequential data.
Results from this section draw inspiration from (Jeon et al., 2023) which
focused on the analysis of supervised learning from _iid_ data.

We model all uncertain quantities as random variables. Each random variable we
consider is defined with respect to a common probability space
$(\Omega,\mathbb{F},\mathbb{P})$. Of particular interest to our analysis is a
sequence $X_{1},X_{2},\ldots,X_{T}$ of discrete random variables which
represent observations. This sequence is generated by an autoregressive model
parameterized by a random variable $\theta$ such that for all
$t\in\mathbb{Z}_{+}$, $X_{t+1}$ may depend on $\theta$ and the entire history
$X_{1},\ldots,X_{t}$, which we abbreviate as $H_{t}$.

###  3.1 Bayesian Error

Our framework is Bayesian in the sense that it treats learning as the process
of reducing uncertainty about $\theta$, which is taken to be a random
variable. A learning algorithm produces, for each $t$, a _predictive
distribution_ $P_{t}$ of $X_{t+1}$ after observing the history $H_{t}$. We
express such an algorithm in terms of a function $\pi$ for which
$P_{t}=\pi(H_{t})$. For a horizon $T\in\mathbb{Z}_{++}$, we quantify the error
realized by predictions $P_{t}$ for $t<T$ in terms of the average cumulative
expected log-loss:

$\mathbb{L}_{T,\pi}=\frac{1}{T}\sum_{t=0}^{T-1}\ \mathbb{E}_{\pi}\left[-\ln
P_{t}(X_{t+1})\right].$

###  3.2 Achievable Bayesian Error

A natural question is: which $\pi$ minimizes the Bayesian error? The following
result establishes that across all problem instances, the optimal algorithm
$\pi$ sets $P_{t}=\mathbb{P}(X_{t+1}\in\cdot|H_{t})$ for all $t$. We denote
this _Bayesian posterior_ by $\hat{P}_{t}$.

######  Lemma 3.1.

(Bayesian posterior is optimal) For all $t\in\mathbb{Z}_{+}$,

$\mathbb{E}\left[-\ln\hat{P}_{t}(X_{t+1})\big{|}H_{t}\right]\
\overset{a.s.}{=}\ \min_{\pi}\ \mathbb{E}_{\pi}\left[-\ln
P_{t}(X_{t+1})|H_{t}\right].$

###### Proof.

In the below proof take all equality to hold _almost surely_.

$\displaystyle\ \mathbb{E}\left[-\ln P_{t}(X_{t+1})|H_{t}\right]$
$\displaystyle=\mathbb{E}\left[-\ln\hat{P}_{t}(X_{t+1})+\ln\frac{\hat{P}_{t}(X_{t+1})}{P_{t}(X_{t+1})}\Big{|}H_{t}\right]$
$\displaystyle=\mathbb{E}\left[-\ln\hat{P}_{t}(X_{t+1})\Big{|}H_{t}\right]+\mathbf{d}_{\mathrm{KL}}(\hat{P}_{t}\|P_{t}).$

The result follows from the fact that
$\mathbf{d}_{\mathrm{KL}}(\hat{P}_{t}\|P_{t})>0$ for all
$P_{t}\neq\hat{P}_{t}$. ∎

We use $\mathbb{L}_{T}$ to denote the _optimal_ achievable Bayesian error:

$\displaystyle\mathbb{L}_{T}$ $\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\hat{P}_{t}(X_{t+1})\right].$

In the main text we restrict our attention to the study of _optimal_
achievable Bayesian error but we provide an extension to arbitrary predictors
which depend on the history $H_{t}$ in Appendix C. The following result
provides an exact characterization of the optimal cumulated expected log-loss.

######  Theorem 3.2.

(Bayesian error) For all $T\in\mathbb{Z}_{+}$,

$\mathbb{L}_{T}=\underbrace{\frac{\mathbb{H}(H_{T}|\theta)}{T}}_{\begin{subarray}{c}\text{irreducible}\\\
\text{error}\end{subarray}}+\underbrace{\frac{\mathbb{I}(H_{T};\theta)}{T}}_{\begin{subarray}{c}\text{estimation}\\\
\text{error}\end{subarray}}.$

###### Proof.

$\displaystyle\mathbb{L}_{T}$ $\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\hat{P}_{j}(X_{t+1})\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\
\mathbb{E}\left[\ln\frac{1}{\mathbb{P}(X_{t+1}|H_{t},\theta)}+\ln\frac{\mathbb{P}(X_{t+1}|H_{t},\theta)}{\hat{P}_{t}(X_{t+1})}\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\ \mathbb{H}(X_{t+1}|\theta,H_{t})$
$\displaystyle\
+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(X_{t+1}\in\cdot|H_{t},\theta)\|\hat{P}_{t}(X_{t+1}\in\cdot))\right]$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{H}(H_{T}|\theta)}{T}+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|H_{t})$
$\displaystyle\overset{(b)}{=}\frac{\mathbb{H}(H_{T}|\theta)}{T}+\frac{\mathbb{I}(H_{T};\theta)}{T},$

where $(a)$ and $(b)$ follow from the chain rule of conditional mutual
information. ∎

Jeon et al. (2023) establish Theorem 3.2 in the setting in which the sequence
is iid when conditioned on $\theta$. We refer to $\mathbb{H}(H_{T}|\theta)$ as
the _irreducible error_ because it is the error incurred by even the
_omniscient_ predictor $\mathbb{P}(X_{t+1}\in\cdot|\theta,H_{t})$. The
_estimation error_ represents statistical error incurred by an agent that
produces estimates of the future $X_{t+1}$ from the past sequence $H_{t}$.
Since estimation error encompasses error which is _reducible_ via learning,
our analysis will focus on characterizing this quantity. We use

$\displaystyle\mathcal{L}_{T}$
$\displaystyle=\frac{\mathbb{I}(H_{T};\theta)}{T},$

to denote the estimation error. $\mathcal{L}_{T}$ will often vanish as
$n\to\infty$. For instance, if $\mathbb{H}(\theta)<\infty$, then this will
trivially be the case as $\mathbb{I}(H_{t};\theta)\leq\mathbb{H}(\theta)$ for
all $t$. However, even in problems for which $\mathbb{H}(\theta)=\infty$, for
example if $\theta$ is a continuous random variable, the estimation error will
still often vanish as $n\to\infty$. Note that $\mathbb{H}(\theta)$ should not
be confused with $\mathbf{h}(\theta)$, the _differential entropy_ of $\theta$.
The differential entropy does not capture the same qualitative properties as
discrete entropy, namely $1)$ invariance under change of variables, $2)$ non-
negativity. While _differences_ in differential entropy still provide
meaningful insight via mutual information
$(\mathbb{I}(X;Y)=\mathbf{h}(X)-\mathbf{h}(X|Y))$, the quantity itself is
largely vacuous for the purposes of measuring information content and
therefore deriving error bounds. The appropriate extension of discrete entropy
to continuous random variables can be made via _rate-distortion theory_.

######  Definition 3.3.

(rate-distortion function) Let $\epsilon\geq 0$, $\theta:\Omega\mapsto\Theta$
be a random variable, and $\rho$ a distortion function which maps $\theta$ and
a random variable $\tilde{\theta}$ to $\Re$. The rate-distortion function
evaluated for random variable $\theta$ at tolerance $\epsilon$ takes the
value:

$\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon}}\
\mathbb{I}(\theta;\tilde{\theta}),$

where

$\tilde{\Theta}_{\epsilon}=\left\\{\tilde{\theta}:\rho(\theta,\tilde{\theta})\leq\epsilon\right\\}.$

One can think of $\tilde{\theta}$ as a lossy _compression_ of the random
variable $\theta$. The objective $\mathbb{I}(\theta;\tilde{\theta})$, referred
to as the _rate_ , characterizes the number of nats that $\tilde{\theta}$
retains about $\theta$. Meanwhile, the distortion function $\rho$
characterizes how lossy the compression is. When we apply rate-distortion
theory to the analysis of machine learning, we restrict our attention to the
case in which

$\displaystyle\rho(\theta,\tilde{\theta})$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(X_{t+1}\in\cdot|\theta,H_{t})\|\mathbb{P}(X_{t+1}\in\cdot|\tilde{\theta},H_{t}))\right]$
$\displaystyle=\mathbb{I}(X_{t+1};\theta|\tilde{\theta},H_{t}).$

We assume that $\tilde{\theta}\perp X_{t+1}|(\theta,H_{t})$ (the compression
$\tilde{\theta}$ does not contain exogenous information about $X_{t+1}$, such
as aleatoric noise, which cannot be determined from $(\theta,H_{t})$). We use
the notation $\mathbb{H}_{\epsilon,T}(\theta)$ to denote the rate-distortion
function w.r.t. this KL-divergence distortion function averaged across horizon
$T$:

$\mathbb{H}_{\epsilon,T}(\theta)=\inf_{\tilde{\theta}\in\tilde{\Theta}_{\epsilon.T}}\
\mathbb{I}(\theta;\tilde{\theta}),$

where

$\displaystyle\tilde{\Theta}_{\epsilon,T}$
$\displaystyle=\left\\{\tilde{\theta}:\tilde{\theta}\perp
H_{T}|\theta;\quad\frac{\mathbb{I}(H_{T};\theta|\tilde{\theta})}{T}\leq\epsilon\right\\}.$

With this notation established, we present the following result for sequential
learning. The proof can be found in Appendix A.

######  Theorem 3.4.

(rate-distortion estimation error bound) For all $T\in\mathbb{Z}_{+}$,

$\sup_{\epsilon\geq 0}\
\min\left\\{\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T},\epsilon\right\\}\ \leq\
\mathcal{L}_{T}\ \leq\ \inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon.$

An interpretation of the above result is that the Bayesian posterior
implicitly finds the compression $\tilde{\theta}$ that optimally trades off
learning complexity $\mathbb{I}(\theta;\tilde{\theta})$ and distortion
$\mathbb{I}(H_{T};\theta|\tilde{\theta})$. While these results are very
general, they remain abstract. In Appendix A.1 we provide a simple logistic
regression example. In the main text, we provide an analysis for learning from
a sequence generated by a deep transformer model.

###  3.3 Deep Transformer

In the transformer environment, we let $(X_{1},X_{2},\ldots)$ be a sequence in
$\\{1,\ldots,d\\}$, where $d$ denotes the size of the vocabulary. Each of the
$d$ outcomes is associated with a _known_ embedding vector which we denote as
$\Phi_{j}$ for $j\in\\{1,\ldots,d\\}$. We assume that for all $j$,
$\|\Phi_{j}\|_{2}=1$. For brevity of notation, we let $\phi_{t}=\Phi_{X_{t}}$
i.e. the embedding associated with token $X_{t}$.

Let $K$ denote the context length of the transformer, $L$ denote it’s depth,
and $r$ denote the attention dimension. We assume that the first token $X_{1}$
is sampled from an arbitrary pmf on $\\{1,\ldots,d\\}$ but subsequent tokens
are sampled based on the previous $K$ tokens within the context window and the
weights of a depth $L$ transformer model.

We use $U_{t,i}$ to denote the output of layer $i$ at time $t$
$(U_{t,0}=\phi_{t-K+1:t})$ (the embeddings associated with the past $K$
tokens). For all $t\leq T,i<L$, let

$\text{Attn}_{i}(U_{t,i-1})=\sigma\left(\frac{U^{\top}_{t,i-1}A_{i}U_{t,i-1}}{\sqrt{r}}\right)$

denote the attention matrix of layer $i$ where $\sigma$ denotes the softmax
function applied elementwise along the columns. The matrix
$A_{i}\in\Re^{r\times r}$ can be interpreted as the product of the key and
query matrices and without loss of generality, we assume that the elements of
the matrices $A_{i}$ are distributed iid $\mathcal{N}(0,1)$ (Gaussian
assumption is not crucial but known mean and unit variance is).

Subsequently, we let

$U_{t,i}=\text{Clip}\left(V_{i}U_{t,i-1}\text{Attn}_{i}(U_{t,i-1})\right),$

where Clip ensures that each column of the matrix input has $L2$ norm at most
$1$. The matrix $V_{i}$ resembles the value matrix and without loss of
generality, we assume that the elements of $V_{i}$ are distributed iid
$\mathcal{N}(0,1/d)$ (same generality conditions as above).

Finally, the next token is generated via sampling from the softmax of the
final layer:

$X_{t+1}\sim\sigma\left(U_{t,L}[-1]\right),$

where $U_{t,L}[-1]$ denotes the right-most column of $U_{t,L}$. At each layer
$i$, the parameters $\theta_{i}$ consist of the matrices $A_{i},V_{i}$. We
will use the notation $\theta_{i:j}$ for $i\leq j$ to denote the collection
$(\theta_{i},\theta_{i+1},\ldots,\theta_{j})$.

######  Theorem 3.5.

(transformer estimation error bound) For all $d,r,L,K$, if $\theta_{1:L}$ is
the transformer environment, then

$\displaystyle\mathcal{L}_{T}$
$\displaystyle\leq\frac{(d^{2}+r^{2})L^{2}\log(4K^{2})}{T}+\frac{(d^{2}+r^{2})L\log\left(\frac{2KT^{2}}{L}\right)}{2T}.$

We note that even if the sequence generated by the transformer is not iid, we
observe that $\mathcal{L}_{T}$ decays linearly in $T$, the length of the
sequence. Furthermore, we observe that $\mathcal{L}_{T}$ is upper bounded
linearly in the product of parameter count and depth of the transformer model
as in Bai et al. (2023). In the following section, we will draw the connection
to ICL by studying meta-learning in a data generating process which resembles
a sparse _mixture_ of deep transformers.

##  4 Meta-Learning from Sequential Data

In this section, we analyze the achievable performance of _meta-learning_ from
sequences. The tools of the Bayesian framework apply exactly as they do in
standard supervised learning from sequences. An example of meta-learning from
sequences includes language model pretraining in which each “meta-task” can be
interpreted as a separate document and the “sequence” as the tokens which
comprise the document. We will use the terminology _document_ going forward to
refer to a “meta-task” in meta-learning.

###  4.1 Data Generating Process

We now consider sequential data which resembles a _corpus_ of text documents.
We assume that all documents in the corpus have an identical length wich we
denote by $T$. For each document $m$, we let
$D_{m}=X^{(m)}_{1},\ldots,X^{(m)}_{T}$ be the sequence of discrete random
variables which resembles its constituent tokens.

Each document is associated with a random variable $\theta_{m}$ which encodes
information that is specific to document $m$. As in the previous section, we
assume that the sequence $D_{m}$ is produced by an autoregressive process. As
such, for all $t$, the value of $X^{(m)}_{t+1}$ depends on $\theta_{m}$ and
the prior tokens $(X^{(m)}_{1},\ldots,X^{(m)}_{t})$ in $D_{m}$.

Finally, we assume that there exists a random variable $\psi$ such that
conditioned on $\psi$, $(\theta_{1},\theta_{2},\ldots)$ is an iid sequence.
Note that $\psi$ encodes information which learnable _across_ documents in a
corpus. As such, $\psi$ represent the _meta_ parameters while
$(\theta_{1},\theta_{2},\ldots)$ represent the _intra-task_ parameters. Two
natural conditional independence results follow from our formulation. $1)$ for
all $m$, $D_{m}\perp\psi|\theta_{m}$; the meta parameters do not contain
information about $D_{m}$ beyond what is contained in $\theta_{m}$. $2)$
$X^{(m)}_{t}\perp X^{(n)}_{t}|\psi$ for all $m\neq n$; tokens _across_
documents do not contain information about each other beyond what is contained
in $\psi$.

###  4.2 Bayesian Error

Our framework is Bayesian in the sense that it treats learning as the process
of reducing uncertainty about $\theta_{1},\ldots,\theta_{m},\psi$, which are
taken to be random variables. For a meta-learning problem with $M$ documents
each of length $T$, a learning algorithm produces, for each
$(m,t)\in[M]\times[T]$, a _predictive distribution_ $P_{m,t}$ of
$X^{(m)}_{t+1}$ after observing the concatenated history which we denote by

$H_{m,t}=(D_{1},D_{2},\ldots,D_{m-1},X^{(m)}_{1},\ldots,X^{(m)}_{t}).$

$H_{m,t}$ consists of _all_ tokens from documents $1,\ldots,m-1$ and up to the
$t$th token of document $m$. We express our meta-learning algorithm in terms
of a function $\pi$ for which $P_{m,t}=\pi(H_{m,t})$. For all
$M,T\in\mathbb{Z}_{++}$, we quantify the error realized by predictions
$P_{m,t}$ for $(m,t)\in[M]\times[T]$ in terms of the average cumulative
expected log-loss:

$\mathbb{L}_{M,T,\pi}=\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{E}_{\pi}\left[-\ln P_{m,t}\left(X^{(m)}_{t+1}\right)\right].$

We note that this objective largely resembles the objective LLMs minimize in
the process of pre-training.

###  4.3 Achievable Bayesian Error

We are in particular interested in the algorithm $\pi$ which minimizes
Bayesian error. Just as in supervised learning from sequences, across all
problem instances, the optimal algorithm $\pi$ sets
$P_{m,t}=\mathbb{P}(X^{(m)}_{t+1}\in\cdot|H_{m,t})$ for all $m,t$. We denote
this _Bayesian posterior_ by $\hat{P}_{m,t}$.

######  Lemma 4.1.

(Bayesian posterior is optimal) For all $m,t\in\mathbb{Z}_{+}$,

$\displaystyle\
\mathbb{E}\left[-\ln\hat{P}_{m,t}\left(X^{(m)}_{t+1}\right)\big{|}H_{m,t}\right]$
$\displaystyle\overset{a.s.}{=}\ \min_{\pi}\ \mathbb{E}_{\pi}\left[-\ln
P_{m,t}\left(X_{t+1}^{(m)}\right)|H_{m,t}\right].$

We use $\mathbb{L}_{M,T}$ to denote the _optimal_ achievable Bayesian error:

$\displaystyle\mathbb{L}_{M,T}$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\hat{P}_{m,t}\left(X^{(m)}_{t+1}\right)\right].$

We will restrict our attention to the performance of the optimal predictor
$\hat{P}_{t}$. We now present the main result of this paper which decomposes
optimal Bayesian error into 3 intuitive terms. The following result provides
an exact characterization of $\mathbb{L}_{M,T}$.

######  Theorem 4.2.

(Main Result) For all $M,T\in\mathbb{Z}_{+}$ and $m\in\\{1,2,\ldots,M\\}$,

$\displaystyle\mathbb{L}_{M,T}$
$\displaystyle=\underbrace{\frac{\mathbb{H}(H_{M,T}|\theta_{1:M})}{MT}}_{\begin{subarray}{c}\text{irreducible}\\\
\text{error}\end{subarray}}+\underbrace{\frac{\mathbb{I}(H_{M,T};\psi)}{MT}}_{\begin{subarray}{c}\text{meta}\\\
\text{estimation}\\\ \text{error}\end{subarray}}$
$\displaystyle\quad+\underbrace{\frac{\mathbb{I}(D_{m};\theta_{m}|\psi)}{T}}_{\begin{subarray}{c}\text{intra-
document}\\\ \text{estimation}\\\ \text{error}\end{subarray}}.$

###### Proof.

$\displaystyle\mathbb{L}_{M,T}$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\hat{P}_{m,t}(X^{(m)}_{t+1})\right]$
$\displaystyle\overset{(a)}{=}\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{H}(X_{t+1}^{(m)}|\theta_{m},H_{m,t})$
$\displaystyle\quad+\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{I}(X_{t+1}^{(m)};\psi,\theta_{m}|H_{m,t})$
$\displaystyle\overset{(b)}{=}\frac{1}{MT}\sum_{m=1}^{M}\mathbb{H}(D_{m}|\theta_{m},H_{m-1,T})$
$\displaystyle\quad+\frac{1}{MT}\sum_{m=1}^{M}\mathbb{I}(D_{m};\psi,\theta_{m}|H_{m-1,T})$
$\displaystyle\overset{(c)}{=}\frac{\mathbb{H}(H_{M,T}|\theta_{1:M})}{MT}+\frac{1}{MT}\sum_{m=1}^{M}\mathbb{I}(D_{m};\psi|H_{m-1,T})$
$\displaystyle\quad+\frac{1}{MT}\sum_{m=1}^{M}\mathbb{I}(D_{m};\theta_{m}|\psi,H_{m-1,T})$
$\displaystyle\overset{(d)}{=}\frac{\mathbb{H}(H_{M,T}|\theta_{1:M})}{MT}+\frac{\mathbb{I}(H_{M,T};\psi)}{MT}+\frac{\mathbb{I}(D_{m};\theta_{m}|\psi)}{T},$

where $(a)$ follows from Theorem 3.2, and $(b),(c),(d)$ follow from the chain
rule of mutual information. ∎

The irreducible error represents the Bayesian error incurred by even the
omniscent predictor $\mathbb{P}(X^{(m)}_{t+1}\in\cdot|\theta_{m},H_{m,t})$
which conditions on document-specific information $\theta_{m}$ and the
document history $H_{m,t}$.

The meta-estimation error represents the statistical error incurred in the
process of estimating the meta parameters $\psi$. Since all tokens across all
documents contain information about $\psi$, it is intuitive that meta-
estimation error term decays linearly in $MT$. Since $M$ could in practice be
very large (for example in a pretraining dataset), $\mathbb{L}_{M,T}$ could be
small even for small $T$ if significant learning complexity is contained in
$\psi$.

Finally, the intra-document estimation error represents the statistical error
incurred in the process of learning $\theta_{m}$ after already conditioning on
$\psi$. As only the data from document $m$ $(D_{m})$ pertains to $\theta_{m}$,
this error intuitively decays linearly in $T$, the length of the document. As
mentioned before, if much of the learning complexity is contained in $\psi$,
then $\mathbb{I}(H^{(1)}_{T};\theta_{m}|\psi)$ will be small and therefore the
intra-document estimation error may be small even for short document length
$T$. We will revisit this idea in section 4.5 when we analyze ICL within this
framework.

Our subsequent analysis will focus on estimation error as it represents error
which is reducible via learning. In meta-learning, the total estimation error
is:

$\mathcal{L}_{M,T}=\frac{\mathbb{I}(H_{M,T};\psi)}{MT}+\frac{\mathbb{I}(D_{m};\theta_{m}|\psi)}{T},$

i.e. the sum of meta and intra-document estimation errors.

We note that Theorem 4.2 holds for all data generating processes which meet
the natural assumptions made in subsection 4.1. It is surprising that we can
arrive at such a result which decays linearly in both $M$, the number of
documents, and $T$, the lengths of the documents without any explicit reliance
on stability or mixing assumptions.

While the main result is useful for conceptual understanding, we need further
tools to facilitate the theoretical analysis of concrete meta-learning problem
instances. To extend this result, we again use rate-distortion theory under
the following modified rate-distortion functions:

$\displaystyle\mathbb{H}_{\epsilon,T}(\theta_{m}|\psi)$
$\displaystyle=\inf_{\tilde{\theta}_{m}\in\tilde{\Theta}_{\epsilon,T}}\
\mathbb{I}(\theta_{m};\tilde{\theta}_{m}|\psi),$

where

$\displaystyle\tilde{\Theta}_{\epsilon,T}$
$\displaystyle=\left\\{\tilde{\theta}:\tilde{\theta}\perp
H_{M,T}|\theta_{m};\quad\frac{\mathbb{I}(D_{m};\theta_{m}|\tilde{\theta},\psi)}{T}\leq\epsilon\right\\},$

and

$\mathbb{H}_{\epsilon,M,T}(\psi)=\inf_{\tilde{\psi}\in\tilde{\Psi}_{\epsilon,M,T}}\
\mathbb{I}(\psi;\tilde{\psi}),$

where

$\tilde{\Psi}_{\epsilon,M,T}=\left\\{\tilde{\psi}:\tilde{\psi}\perp
H_{M,T}|\psi;\quad\frac{\mathbb{I}(H_{M,T};\psi|\tilde{\psi})}{MT}\leq\epsilon\right\\}.$

With this notation in place, we establish the following upper and lower bounds
on $\mathcal{L}_{M,T}$ in terms of the above rate distortion functions.

######  Theorem 4.3.

(rate-distortion estimation error bound) For all $M,T\in\mathbb{Z}_{+}$, and
$m\in\\{1,\ldots,M\\}$,

$\displaystyle\mathcal{L}_{M,T}$ $\displaystyle\leq\inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,M,T}(\psi)}{MT}+\epsilon+\inf_{\epsilon^{\prime}\geq
0}\
\frac{\mathbb{H}_{\epsilon^{\prime},T}(\theta_{m}|\psi)}{T}+\epsilon^{\prime},$

and

$\displaystyle\mathcal{L}_{M,T}$ $\displaystyle\geq\sup_{\epsilon\geq
0}\min\left\\{\frac{\mathbb{H}_{\epsilon,M,T}(\psi)}{MT},\epsilon\right\\}$
$\displaystyle\quad+\sup_{\epsilon^{\prime}\geq
0}\min\left\\{\frac{\mathbb{H}_{\epsilon^{\prime},T}(\theta_{m}|\psi)}{T},\epsilon^{\prime}\right\\}.$

A direct consequence of Theorem 4.3 is an upper bound on Bayesan error with
respect to _entropy_ (by setting $\epsilon,\epsilon^{\prime}$ to $0$). While
the utility of such a bound is limited to settings in which
$\psi,\theta_{1:M}$ are discrete random variables, it may be useful to the
reader conceptually. The bound is captured in the following Corollary:

######  Corollary 4.4.

(entropy estimation error bound) For all $M,T\in\mathbb{Z}_{+}$, and
$m\in\\{1,\ldots,M\\}$

$\mathcal{L}_{M,T}\leq\frac{\mathbb{H}(\psi)}{MT}+\frac{\mathbb{H}(\theta_{m}|\psi)}{T}.$

In the following section, we will apply Theorem 4.3 to derive error bounds for
a sparse mixture of (deep) transformers. For a simpler linear representation
learning example, we refer the reader to Appendix B.1.

###  4.4 Sparse Mixture of Transformers

In the sparse mixture of transformers environment, for all documents $m$, we
let its tokens $(X^{(m)}_{1},X^{(m)}_{2},\ldots)$ be a sequence in
$\\{1,\ldots,d\\}$, where $d$ denotes the size of the vocabulary. Each of the
$d$ outcomes is associated with a _known_ embedding vector which we denote as
$\Phi_{j}$ for $j\in\\{1,\ldots,d\\}$. We assume that for all $j$,
$\|\Phi_{j}\|_{2}=1$. For brevity of notation, we let
$\phi_{t}^{(m)}=\Phi_{X^{(m)}_{t}}$ i.e. the embedding associated with token
$X^{(m)}_{t}$.

Each document is generated by a transformer model which is sampled iid from a
mixture. We assume that sampling is performed according to a categorical
distribution parameterized by $\psi$ with prior distribution
$\mathbb{P}(\psi\in\cdot)=\text{Dirichlet}(N,[R/N,\ldots,R/N])$ for a scale
parameter $R\ll N$. Under this prior distribution, the expected number of
unique outcomes grows linearly in $R$ and only logarithmically in the number
of draws ($M$ in our case). As a result, we permit the size of the mixture $N$
to potentially be exponentially large, but we assume that the mixture’s
complexity is controlled by the sparsity parameter $R$.

Each of the $N$ elements of the mixture corresponds to a deep transformer
network as outlined in Section 3.3. Let $K$ denote the context lengths of the
transformers, $L$ denote their depths, and $r$ their attention dimensions. We
assume that for all documents, the first token $X^{(m)}_{1}$ is sampled from
an arbitrary pmf on $\\{1,\ldots,d\\}$ but subsequent tokens are sampled based
on the previous $K$ tokens within the context window and the weights of the
sampled transformer model.

The tokens of each document are generated according to the weights of the
sampled transformer and the previous $K$ tokens. The generation of token
$X^{(m)}_{t+1}$ will depend on $\theta_{m}$ and
$X^{(m)}_{t-K+1},\ldots,X^{(m)}_{t}$. For all $m,t$, we let
$(U^{(m)}_{t,0}=\phi_{t-K+1:t})$ refer to the embeddings associated with the
past $K$ tokens. For $i>0$, we let $U^{(m)}_{t,i}$ denote the output of layer
$i$ of the transformer with input $U^{(m)}_{t,0}$. For all $t\leq T,i<L,m\leq
M$, let

$\text{Attn}_{i}(U^{(m)}_{t,i-1})=\sigma\left(\frac{U^{(m)\top}_{t,i-1}A^{(m)}_{i}U^{(m)}_{t,i-1}}{\sqrt{r}}\right)$

denote the attention matrix of layer $i$ for document $m$ where $\sigma$
denotes the softmax function applied elementwise along the columns. The matrix
$A^{(m)}_{i}\in\Re^{r\times r}$ can be interpreted as the product of the key
and query matrices and without loss of generality, we assume that the elements
of the matrices $A^{(m)}_{i}$ are distributed iid $\mathcal{N}(0,1)$ (Gaussian
assumption is not crucial but known mean and unit variance is).

Subsequently, we let

$U^{(m)}_{t,i}=\text{Clip}\left(V^{(m)}_{i}U^{(m)}_{t,i-1}\text{Attn}_{i}(U^{(m)}_{t,i-1})\right),$

where Clip ensures that each column of the matrix input has $L2$ norm at most
$1$. The matrix $V^{(m)}_{i}$ resembles the value matrix and without loss of
generality, we assume that the elements of $V^{(m)}_{i}$ are distributed iid
$\mathcal{N}(0,1/d)$ (same generality conditions as above).

Finally, the next token is generated via sampling from the softmax of the
final layer:

$X^{(m)}_{t+1}\sim\sigma\left(U^{(m)}_{t,L}[-1]\right),$

where $U^{(m)}_{t,L}[-1]$ denotes the right-most column of $U^{(m)}_{t,L}$. At
each layer $i$, the parameters $\theta_{m,i}$ consist of the matrices
$A^{(m)}_{i},V^{(m)}_{i}$.

We provide the following novel result which upper bounds the error of the
optimal Bayesian learner when learning from data generated by the sparse
mixture of transformers.

######  Theorem 4.5.

(mixture of transformers estimation error bound) For all
$d,r,K,L,M,T\in\mathbb{Z}_{++}$, if $\theta_{1},\ldots,\theta_{M},\psi$ are
the sparse mixture of transformers environment and $r\leq d$, then

$\displaystyle\mathcal{L}_{M,T}$
$\displaystyle\leq\frac{R\log\left(1+\frac{M}{R}\right)\log(MN)}{MT}$
$\displaystyle\
+\frac{R\log\left(1+\frac{M}{R}\right)(d^{2}+r^{2})L^{2}\log\left(4K^{2}MT^{2}\right)}{MT}$
$\displaystyle\ +\frac{\log(N)}{T}.$

We now provide some qualitative comments about this result. The first and
second terms denote the meta estimation error, and the third term denotes the
intra-document estimation error.

The first term is the error incurred in the process of learning $\psi$, the
probabilities by which the models of the mixture are sampled. Note that even
if there are $N$ models in the mixture, due to the Dirichlet assumption, the
error depends linearly on $R$ the sparsity parameter and only logarithmically
on $N$. Note that this term decays linearly in $MT$ since data across
documents provide information about $\psi$.

The second term measures the error incurred from learning the weights of the
sampled models within the mixture. Note that again, due to the Dirichlet
assumption, this term scales only logarithmically in $M$. This is because even
if a model is resampled for every document, several documents may still be
generated by the _same_ model from the mixture. As a result, the dependence is
linear in $R$ and only logarithmic in $M$. The remaining terms are linear in
the product of parameter count and depth, which corroborates the results of
Bai et al. (2023). However, our result decays linearly in $MT$ as opposed to
just $M$ as in (Bai et al., 2023). This is intuitive as the error ought to
decrease in both the number of documents $M$ and the _length_ of the documents
$T$. This is an advantage of the Bayesian framework as it does not rely on a
uniform convergence argument which requires mixing time assumption on the
tokens within the document to obtain linear decay in $T$.

Finally, the third term is the intra-document estimation error which is the
error incurred in the process of learning which model from the mixture
generated each document. Since there are $N$ different elements in the
mixture, the $\log(N)/T$ is straightforward. The longer the document length
$T$, the more certain we should be about which model generated the document,
hence lower error. In the following section, we explicitly outline the
connection between this example and ICL.

###  4.5 In-context Learning as Meta-Learning from Sequences

We now explicitly draw the connection between ICL and meta-learning from
sequences. We assume that the pretraining dataset consists of $M$ documents,
each of length $T$. We assume that a new $M+1$th document type is drawn and an
in-context learner is described by an algorithm which produces for each $t$ a
predictive distribution $P^{in}_{t}$ of $X_{t+1}^{(M+1)}$ after observing the
history $H_{M+1,t}$ which consists of the pretraining data an the $t$ provided
in the current context. We let
$D_{M+1}=(X^{(M+1)}_{1},\ldots,X^{(M+1)}_{\tau})$ denote the entire in-context
sequence. Note that we have summarize the effect of pretraining by allowing
$P^{(in)}_{t}$ to depend on the pretraining history $H_{M,T}$. We quantify
error realized by predictions $P^{in}_{t}$ in terms of the average cumulative
expected log-loss:

$\mathbb{L}_{M,T,\tau,\pi}=\frac{1}{\tau}\sum_{t=0}^{\tau-1}\mathbb{E}_{\pi}\left[-\log
P^{in}_{t}\left(X_{t+1}^{(M+1)}\right)\right],$

where $\tau$ denotes the full length of the in-context sequence. We assume
that $\tau\leq T$ as $\tau$ can be at most $K$, the context-length of the
transformer and the document lengths $T$ in pretraining are often much larger
than $K$. As before, we establish that
$\hat{P}_{t}(X_{t+1}^{(M+1)}\in\cdot)=\mathbb{P}(X_{t+1}^{(M+1)}\in\cdot|H_{M+1,t})$
minimizes this loss almost surely.

######  Theorem 4.6.

For all $M,T,t\in\mathbb{Z}_{+}$,

$\displaystyle\mathbb{E}\left[-\log\hat{P}_{t}(X_{t+1}^{(M+1)})|H_{M+1,t}\right]$
$\displaystyle\overset{a.s.}{=}\min_{\pi}\ \mathbb{E}_{\pi}\left[\\-\log
P^{in}_{t}(X^{(M+1)}_{t+1})|H_{M+1,t}\right].$

Going forward, we will restrict our attention to the performance of
$\hat{P}_{t}$ which we denote as:

$\displaystyle\mathbb{L}_{M,T,\tau}$
$\displaystyle=\frac{1}{\tau}\sum_{t=0}^{\tau-1}\mathbb{E}\left[-\log\hat{P}_{t}(X_{t+1}^{(M+1)})\right].$

With this notation in place, we present an upper bound for the ICL error. A
proof can be found in Appendix B.3.

######  Theorem 4.7.

(in context learning error bound) For all $M,T,\tau\in\mathbb{Z}_{++}$, if
$\tau\leq T$, then

$\displaystyle\mathbb{L}_{M,T,\tau}$
$\displaystyle\leq\underbrace{\frac{\mathbb{H}\left(D_{M+1}|\theta_{M+1}\right)}{\tau}}_{\begin{subarray}{c}\text{irreducible}\\\
\text{error}\end{subarray}}+\underbrace{\frac{\mathbb{I}(H_{M,T};\psi)}{M\tau}}_{\begin{subarray}{c}\text{meta}\\\
\text{estimation}\\\ \text{error}\end{subarray}}$
$\displaystyle\quad+\underbrace{\frac{\mathbb{I}(D_{M+1};\theta_{M+1}|\psi)}{\tau}}_{\begin{subarray}{c}\text{in-
context}\\\ \text{estimation}\\\ \text{error}\end{subarray}}.$

Note that if $M$ is large i.e. the number of pretraining documents is large,
then almost all of the error will be attributed to the in-context estimation
error:

######  Remark 4.8.

For sufficiently large $M$ (number of pretraining documents),

$\mathbb{L}_{M,T,\tau}\ \lesssim\
\underbrace{\frac{\mathbb{H}\left(D_{M+1}|\theta_{M+1}\right)}{\tau}}_{\begin{subarray}{c}\text{irreducible}\\\
\text{error}\end{subarray}}+\frac{\mathbb{I}(D_{M+1};\theta_{M+1}|\psi)}{\tau}.$

###  4.6 Discussion of Results

If each pretraining document is generated by a transformer model which is
drawn from a mixture as in the previous section, the above remark suggests for
a sufficiently large pretraining set, the in-context error can be small for
even modest values of $\tau$. The in-context error is upper bounded by
$\log(N)/\tau$ where $N$ is the size of the mixture. Effectively, the in-
context data only needs to distinguish which model from the mixture generated
the current sequence. As a result, the complexity is at most $\log(N)$ and the
error decays linearly in the length of the in-context sequence $\tau$. This
corroborates work by Min et al. (2022) which established that an in-context
sequence largely augments performance via providing information about the
distributions of the inputs and labels as well as the format of the sequence.
The LLMs is not literally learning from the examples, as even when the labels
of examples were randomly scrambled, performance on downstream tasks was only
marginally impacted. This lends credence to the hypothesis that ICL pinpoints
which model from the mixture is most suitable for the given in-context
sequence.

##  5 Conclusion

In this work, we introduced novel information-theoretic tools to analyze the
error of meta-learning from sequences. Our tools produced very general and
intuitive results which suggest that the error should decay in both the number
of training sequences and the sequence lengths. Notably, these results hold
without relying on contrived mixing time assumptions as common in existing
work. By applying these tools, we developed novel results about ICL in
transformers and a plausible mathematical hypothesis for how learning is
possible even when only a small amount of data is provided in-context. While
the results of the main text are limited to exact Bayesian inference, we
provide results in the Appendix which extend to _suboptimal_ algorithms as
well. A further rigorous investigation into the mechanisms by which
transformers may be implementing a mixture of models would provide stronger
credence to the hypothesis and results provided in this work.

## References

  * Ahn et al. (2023) Ahn, K., Cheng, X., Daneshmand, H., and Sra, S.  Transformers learn to implement preconditioned gradient descent for in-context learning.  _arXiv preprint arXiv:2306.00297_ , 2023.
  * Akyürek et al. (2022) Akyürek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D.  What learning algorithm is in-context learning? investigations with linear models.  _arXiv preprint arXiv:2211.15661_ , 2022.
  * Aliakbarpour et al. (2023) Aliakbarpour, M., Bairaktari, K., Brown, G., Smith, A., and Ullman, J.  Metalearning with very few samples per task.  _arXiv preprint arXiv:2312.13978_ , 2023.
  * Bai et al. (2023) Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S.  Transformers as statisticians: Provable in-context learning with in-context algorithm selection, 2023.
  * Baxter (2000) Baxter, J.  A model of inductive bias learning.  _Journal of artificial intelligence research_ , 12:149–198, 2000.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Dai et al. (2022) Dai, D., Sun, Y., Dong, L., Hao, Y., Sui, Z., and Wei, F.  Why can gpt learn in-context? language models secretly perform gradient descent as meta optimizers.  _arXiv preprint arXiv:2212.10559_ , 2022.
  * Denevi et al. (2018) Denevi, G., Ciliberto, C., Stamos, D., and Pontil, M.  Incremental learning-to-learn with statistical guarantees.  _arXiv preprint arXiv:1803.08089_ , 2018.
  * Dong et al. (2022) Dong, Q., Li, L., Dai, D., Zheng, C., Wu, Z., Chang, B., Sun, X., Xu, J., and Sui, Z.  A survey for in-context learning.  _arXiv preprint arXiv:2301.00234_ , 2022.
  * Edelman et al. (2021) Edelman, B. L., Goel, S., Kakade, S. M., and Zhang, C.  Inductive biases and variable creation in self-attention mechanisms.  _CoRR_ , abs/2110.10090, 2021.  URL https://arxiv.org/abs/2110.10090.
  * Elhage et al. (2021) Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., et al.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 1, 2021.
  * Finn et al. (2019) Finn, C., Rajeswaran, A., Kakade, S., and Levine, S.  Online meta-learning.  In _International Conference on Machine Learning_ , pp. 1920–1930. PMLR, 2019.
  * Garg et al. (2022) Garg, S., Tsipras, D., Liang, P. S., and Valiant, G.  What can transformers learn in-context? a case study of simple function classes.  _Advances in Neural Information Processing Systems_ , 35:30583–30598, 2022.
  * Giannou et al. (2023) Giannou, A., Rajput, S., Sohn, J.-y., Lee, K., Lee, J. D., and Papailiopoulos, D.  Looped transformers as programmable computers.  _arXiv preprint arXiv:2301.13196_ , 2023.
  * Huang et al. (2023) Huang, Y., Cheng, Y., and Liang, Y.  In-context convergence of transformers.  _arXiv preprint arXiv:2310.05249_ , 2023.
  * Jelassi et al. (2022) Jelassi, S., Sander, M., and Li, Y.  Vision transformers provably learn spatial structure.  _Advances in Neural Information Processing Systems_ , 35:37822–37836, 2022.
  * Jeon et al. (2023) Jeon, H. J., Zhu, Y., and Van Roy, B.  An information-theoretic framework for supervised learning, 2023.
  * Kirsch et al. (2022) Kirsch, L., Harrison, J., Sohl-Dickstein, J., and Metz, L.  General-purpose in-context learning by meta-learning transformers.  _arXiv preprint arXiv:2212.04458_ , 2022.
  * Li et al. (2023a) Li, Y., Ildiz, M. E., Papailiopoulos, D., and Oymak, S.  Transformers as algorithms: Generalization and stability in in-context learning.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 19565–19594. PMLR, 23–29 Jul 2023a.  URL https://proceedings.mlr.press/v202/li23l.html.
  * Li et al. (2023b) Li, Y., Li, Y., and Risteski, A.  How do transformers learn topic structure: Towards a mechanistic understanding.  _arXiv preprint arXiv:2303.04245_ , 2023b.
  * Liu et al. (2022) Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C.  Transformers learn shortcuts to automata.  _arXiv preprint arXiv:2210.10749_ , 2022.
  * Liu et al. (2021) Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W.  What makes good in-context examples for gpt-$3$?  _arXiv preprint arXiv:2101.06804_ , 2021.
  * Lu et al. (2021) Lu, Y., Bartolo, M., Moore, A., Riedel, S., and Stenetorp, P.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  _arXiv preprint arXiv:2104.08786_ , 2021.
  * Mahankali et al. (2023) Mahankali, A., Hashimoto, T. B., and Ma, T.  One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.  _arXiv preprint arXiv:2307.03576_ , 2023.
  * Maurer (2009) Maurer, A.  Transfer bounds for linear feature learning.  _Machine learning_ , 75(3):327–350, 2009.
  * Maurer et al. (2016) Maurer, A., Pontil, M., and Romera-Paredes, B.  The benefit of multitask representation learning.  _Journal of Machine Learning Research_ , 17(81):1–32, 2016.
  * Min et al. (2021) Min, S., Lewis, M., Zettlemoyer, L., and Hajishirzi, H.  Metaicl: Learning to learn in context.  _arXiv preprint arXiv:2110.15943_ , 2021.
  * Min et al. (2022) Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L.  Rethinking the role of demonstrations: What makes in-context learning work?, 2022.
  * Pontil & Maurer (2013) Pontil, M. and Maurer, A.  Excess risk bounds for multitask learning with trace norm regularization.  In _Conference on Learning Theory_ , pp. 55–76. PMLR, 2013.
  * Raventos et al. (2023) Raventos, A., Paul, M., Chen, F., and Ganguli, S.  The effects of pretraining task diversity on in-context learning of ridge regression.  In _ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models_ , 2023.
  * Rubin et al. (2021) Rubin, O., Herzig, J., and Berant, J.  Learning to retrieve prompts for in-context learning.  _arXiv preprint arXiv:2112.08633_ , 2021.
  * Sanford et al. (2023) Sanford, C., Hsu, D., and Telgarsky, M.  Representational strengths and limitations of transformers.  _arXiv preprint arXiv:2306.02896_ , 2023.
  * Song & Zhong (2023) Song, J. and Zhong, Y.  Uncovering hidden geometry in transformers via disentangling position and context.  _arXiv preprint arXiv:2310.04861_ , 2023.
  * Srebro & Ben-David (2006) Srebro, N. and Ben-David, S.  Learning bounds for support vector machines with learned kernels.  In _International Conference on Computational Learning Theory_ , pp. 169–183. Springer, 2006.
  * Tarzanagh et al. (2023) Tarzanagh, D. A., Li, Y., Thrampoulidis, C., and Oymak, S.  Transformers as support vector machines.  _arXiv preprint arXiv:2308.16898_ , 2023.
  * Tian et al. (2023a) Tian, Y., Wang, Y., Chen, B., and Du, S.  Scan and snap: Understanding training dynamics and token composition in 1-layer transformer.  _arXiv preprint arXiv:2305.16380_ , 2023a.
  * Tian et al. (2023b) Tian, Y., Wang, Y., Zhang, Z., Chen, B., and Du, S.  Joma: Demystifying multilayer transformers via joint dynamics of mlp and attention.  _arXiv preprint arXiv:2310.00535_ , 2023b.
  * Tripuraneni et al. (2021) Tripuraneni, N., Jin, C., and Jordan, M.  Provable meta-learning of linear representations.  In Meila, M. and Zhang, T. (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 10434–10443. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/tripuraneni21a.html.
  * Vaswani et al. (2023) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.  Attention is all you need, 2023.
  * Von Oswald et al. (2023) Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M.  Transformers learn in-context by gradient descent.  In _International Conference on Machine Learning_ , pp. 35151–35174. PMLR, 2023.
  * Wei et al. (2023) Wei, J., Wei, J., Tay, Y., Tran, D., Webson, A., Lu, Y., Chen, X., Liu, H., Huang, D., Zhou, D., et al.  Larger language models do in-context learning differently.  _arXiv preprint arXiv:2303.03846_ , 2023.
  * Xie et al. (2022) Xie, S. M., Raghunathan, A., Liang, P., and Ma, T.  An explanation of in-context learning as implicit bayesian inference, 2022.
  * Zhang et al. (2023a) Zhang, R., Frei, S., and Bartlett, P. L.  Trained transformers learn linear models in-context.  _arXiv preprint arXiv:2306.09927_ , 2023a.
  * Zhang et al. (2023b) Zhang, Y., Zhang, F., Yang, Z., and Wang, Z.  What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization, 2023b.
  * Zhao et al. (2021) Zhao, Z., Wallace, E., Feng, S., Klein, D., and Singh, S.  Calibrate before use: Improving few-shot performance of language models.  In _International Conference on Machine Learning_ , pp. 12697–12706. PMLR, 2021.

##  Appendix A Learning from Sequential Data

See 3.2

###### Proof.

$\displaystyle\mathbb{L}_{T}$ $\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\hat{P}_{j}(X_{t+1})\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\mathbb{P}(X_{t+1}|H_{t},\theta)+\ln\frac{\mathbb{P}(X_{t+1}|H_{t},\theta)}{\hat{P}_{t}(X_{t+1})}\right]$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\
\mathbb{H}(X_{t+1}|\theta,H_{t})+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(X_{t+1}\in\cdot|H_{t},\theta)\|\hat{P}_{t}(X_{t+1}\in\cdot))\right]$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{H}(H_{T}|\theta)}{T}+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|H_{t})$
$\displaystyle\overset{(b)}{=}\frac{\mathbb{H}(H_{T}|\theta)}{T}+\frac{\mathbb{I}(H_{T};\theta)}{T},$

where $(a)$ and $(b)$ follow from the chain rule of conditional mutual
information. ∎

See 3.4

###### Proof.

$\displaystyle\mathcal{L}_{T}$
$\displaystyle=\frac{\mathbb{I}(H_{T};\theta)}{T}$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|H_{t})$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta,\tilde{\theta}|H_{t})$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\tilde{\theta}|H_{t})+\mathbb{I}(X_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle=\frac{\mathbb{I}(H_{T};\tilde{\theta})}{T}+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle\leq\inf_{\tilde{\theta}}\
\frac{\mathbb{I}(\theta;\tilde{\theta})}{T}+\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle\leq\inf_{\epsilon\geq 0}\
\frac{\mathbb{H}_{\epsilon,T}(\theta)}{T}+\epsilon$

Suppose that $\mathbb{I}(H_{T};\theta)<\mathbb{H}_{\epsilon,T}$. Let
$\tilde{\theta}=\tilde{H}_{T}\notin\tilde{\Theta}_{\epsilon,T}$ where
$\tilde{H}_{T}$ is another history sampled in the same manner as $H_{T}$.

$\displaystyle\mathbb{I}(H_{T};\theta)$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|H_{t})$
$\displaystyle\overset{(a)}{\geq}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|\tilde{H}_{t},H_{t})$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1};\theta|\tilde{\theta},H_{t})$
$\displaystyle\overset{(b)}{\geq}\epsilon T,$

where $(a)$ follows from the fact that conditioning reduces entropy and that
$X_{t+1}\perp\tilde{H}_{t}|(\theta,H_{t})$ and $(b)$ follows from the fact
that $\tilde{\theta}\notin\tilde{\Theta}_{\epsilon,T}$. Therefore, for all
$\epsilon\geq 0$, $\mathbb{I}(H_{T};\theta)\geq\min\\{H_{\epsilon,T},\epsilon
T\\}$. The result follows. ∎

###  A.1 Logistic Regression

We introduce a simple logistic regression problem as a concrete instance to
demonstrate an application of the general aforementioned results. We assume
that $X_{0}=\bar{X}_{0}$ and $X_{t}=(Y_{t},\bar{X}_{t})$ for all $t\geq 1$.
The “inputs” $(\bar{X}_{0},\ldots,\bar{X}_{T})$ are generated according to an
iid random process for which $X_{j}\sim\mathcal{N}(0,I_{d})$. Meanwhile, we
assume that $Y_{t+1}$ is generated by the following process:

$Y_{t+1}=\begin{cases}1&\text{ w.p. }\frac{1}{1+e^{-\theta^{\top}X_{t}}}\\\
-1&\text{ otherwise }\\\ \end{cases},$

where $\theta$ denotes the parameters of the logistic model and we assume the
prior distribution
$\mathbb{P}(\theta\in\cdot)=\text{Unif}(\\{\nu\in\Re^{d}:\|\nu\|_{2}\leq
1\\})$.

In this environment, $\theta$ is the only unknown quantity and as such, the
distributions of all random variables are _known_ to the algorithm designer.
In this example, the sequence is iid once conditioned on $\theta$. We begin
with this example for simplicity and to demonstrate that our analytical tools
are general enough to subsume the analysis of supervised learning from iid
data.

######  Theorem A.1.

(logistic regression Bayesian error bounds) For all $d,T\in\mathbb{Z}_{++}$,
if $\theta,H_{T}$ follow the logistic regression environment, then

$\mathcal{L}_{T}\ \leq\
\frac{d}{2T}\left(1+\ln\left(1+\frac{T}{4d}\right)\right).$

###### Proof.

From Theorem 3.4, it suffices to upper bound the rate-distortion function. Let
$\tilde{\theta}=\theta+Z$ where $Z\perp\theta$ and
$Z\sim\mathcal{N}(0,8\epsilon/d)$. Then,

$\displaystyle\mathbb{I}(Y;\theta|\tilde{\theta},X)$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta,X)\|\mathbb{P}(Y\in\cdot|\tilde{\theta},X))\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta,X)\|\mathbb{P}(Y\in\cdot|\theta\leftarrow\tilde{\theta},X))\right]$
$\displaystyle=\mathbb{E}\left[\frac{\ln\left(\frac{e^{-\tilde{\theta}^{\top}X}}{e^{-\theta^{\top}X}}\right)}{1+e^{-\theta^{\top}X}}+\frac{\ln\left(\frac{e^{\theta^{\top}X}}{e^{\tilde{\theta}^{\top}X}}\right)}{1+e^{\theta^{\top}X}}\right]$
$\displaystyle\overset{(b)}{\leq}\frac{\mathbb{E}\left[\left(\theta^{\top}X-\tilde{\theta}^{\top}X\right)^{2}\right]}{8}$
$\displaystyle=\frac{\mathbb{E}\left[\|\theta-\tilde{\theta}\|^{2}_{2}\right]}{8}$
$\displaystyle=\epsilon,$

where $(a)$ follows from Lemma 3.1 and $(b)$ follows from the fact that for
all $x,y\in\Re$,

$\frac{\ln\left(\frac{1+e^{-y}}{1+e^{-x}}\right)}{1+e^{-x}}+\frac{\ln\left(\frac{1+e^{y}}{1+e^{x}}\right)}{1+e^{x}}\leq(x-y)^{2}.$

Therefore, $\theta\in\Theta_{\epsilon}$ so it suffices to upper bound the rate
$\mathbb{I}(\theta;\tilde{\theta})$.

$\displaystyle\mathbb{I}(\theta;\tilde{\theta})$
$\displaystyle=\mathbf{h}(\tilde{\theta})-\mathbf{h}(\tilde{\theta}|\theta)$
$\displaystyle=\mathbf{h}(\tilde{\theta})-\mathbf{h}(Z|\theta)$
$\displaystyle=\mathbf{h}(\tilde{\theta})-\mathbf{h}(Z)$
$\displaystyle\leq\frac{d}{2}\ln\left(2\pi
e\left(\frac{1+8\epsilon}{d}\right)\right)-\frac{d}{2}\ln\left(2\pi
e\frac{8\epsilon}{d}\right)$
$\displaystyle=\frac{d}{2}\ln\left(1+\frac{1}{8\epsilon}\right).$

Therefore,

$\displaystyle\mathcal{L}_{n}$
$\displaystyle\overset{(a)}{\leq}\inf_{\epsilon\geq
0}\left(\frac{d}{2n}\ln\left(1+\frac{1}{8\epsilon}\right)+\epsilon\right)$
$\displaystyle\overset{(b)}{\leq}\frac{d}{2n}\ln\left(1+\frac{n}{4d}\right)+\frac{d}{2n},$

where $(a)$ follows from Theorem 3.4 and $(b)$ follows by setting
$\epsilon=d/(2n)$. ∎

As one would expect, the above result establishes that the Bayesian error of
an optimal learning algorithm is $\mathcal{O}(\frac{d}{n}\log\frac{n}{d})$.
The proof illustrates a common technique for bounding the rate-distortion
function i.e. considering a compression $\tilde{\theta}=\theta+Z$ where $Z$ is
independent zero-mean Gaussian noise with tunable variance. In the following
section, we use the same set of tools to analyze a much more complex
supervised learning problem involving a sequence generated by a deep
transformer model.

###  A.2 Transformers

######  Lemma A.2.

For all $L\in\mathbb{Z}_{++}$ and $i\in\\{1,\ldots,L\\}$, if
$\theta_{i}\perp\theta_{j}$, $\tilde{\theta}_{i}\perp\tilde{\theta}_{j}$, and
$\theta_{i}\perp\tilde{\theta}_{j}$ for $i\neq j$, then

$\mathbb{I}(X_{t+1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{1:i},H_{t})\leq\mathbb{I}(H_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},X_{0}).$

###### Proof.

$\displaystyle\mathbb{I}(X_{t+1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{1:i},H_{t})$
$\displaystyle\overset{(a)}{=}\mathbb{I}(H_{t+1},\tilde{\theta}_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i})-\mathbb{I}(H_{t},\tilde{\theta}_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i})$
$\displaystyle\overset{(b)}{\leq}\mathbb{I}(H_{t+1},\tilde{\theta}_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i},X_{0})$
$\displaystyle\overset{(c)}{\leq}\mathbb{I}(H_{t+1},\theta_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i},X_{0})$
$\displaystyle\overset{(d)}{=}\mathbb{I}(H_{t+1},\theta_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i},X_{0})-\mathbb{I}(\theta_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i},X_{0})$
$\displaystyle\overset{(e)}{=}\mathbb{I}(H_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},X_{0})$

where $(a)$ follows from the chain rule of mutual information, $(b)$ follows
from the independence assumptions, $(c)$ follows from the data processing
inequality applied to the markov chain
$\theta_{i}\perp\tilde{\theta}_{1:i-1}|(H_{t+1},\theta_{i+1:L},\theta_{1:i-1},X_{0}^{K})$,
$(d)$ follows from the fact that
$\mathbb{I}(\theta_{1:i-1};\theta_{i}|\theta_{i+1:L},\tilde{\theta}_{i},X_{0})=0$,
and $(e)$ follows from the chain rule of mutual information. ∎

######  Lemma A.3.

(transformer layer Lipschitz constant) For all $d,r,K\in\mathbb{Z}_{++}$,

$\mathbb{E}\left[\|f_{\theta_{i}}(X)-f_{\theta_{i}}(\tilde{X})\|^{2}_{F}|X,\tilde{X}\right]\
\overset{a.s.}{\leq}\ 2(K+K^{2})\cdot\|X-\tilde{X}\|^{2}_{F}.$

###### Proof.

Take all equality and inequality below to hold almost surely.

$\displaystyle\
\mathbb{E}\left[\|f_{i}(X)-f_{i}(\tilde{X})\|^{2}_{F}|X,\tilde{X}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\text{Clip}\left(V_{i}X\sigma\left(\frac{X^{\top}A_{i}X}{\sqrt{r}}\right)\right)-\text{Clip}\left(V_{i}\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}}{\sqrt{r}}\right)\right)\right\|^{2}_{F}\bigg{|}X,\tilde{X}\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\left\|V_{i}X\sigma\left(\frac{X^{\top}A_{i}X}{\sqrt{r}}\right)-V_{i}\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}}{\sqrt{r}}\right)\right\|^{2}_{F}\bigg{|}X,\tilde{X}\right]$
$\displaystyle\overset{(b)}{=}\mathbb{E}\left[\sum_{k=1}^{K}\left\|V_{i}\left(X\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}_{k}}{\sqrt{r}}\right)\right)\right\|^{2}_{2}\bigg{|}X,\tilde{X}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{K}\left(X\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}_{k}}{\sqrt{r}}\right)\right)^{\top}V_{i}^{\top}V_{i}\left(X\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}_{k}}{\sqrt{r}}\right)\right)\bigg{|}X,\tilde{X}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{K}\left(X\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}_{k}}{\sqrt{r}}\right)\right)^{\top}\left(X\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}_{k}}{\sqrt{r}}\right)\right)\bigg{|}X,\tilde{X}\right]$
$\displaystyle\leq\sum_{k=1}^{K}\mathbb{E}\left[2\left\|X\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)\right\|^{2}_{2}+2\left\|\tilde{X}\sigma\left(\frac{X^{\top}A_{i}X_{k}}{\sqrt{r}}\right)-\tilde{X}\sigma\left(\frac{\tilde{X}^{\top}A_{i}\tilde{X}_{k}}{\sqrt{r}}\right)\right\|^{2}_{2}\bigg{|}X,\tilde{X}\right]$
$\displaystyle\overset{(c)}{\leq}\sum_{k=1}^{K}\mathbb{E}\left[2\|X-\tilde{X}\|^{2}_{F}+\frac{2K}{r}\left\|X^{\top}A_{i}X_{k}-\tilde{X}^{\top}A_{i}\tilde{X}_{k}\right\|^{2}_{2}\big{|}X,\tilde{X}\right]$
$\displaystyle\overset{(d)}{\leq}\sum_{k=1}^{K}\mathbb{E}\left[2\|X-\tilde{X}\|^{2}_{F}+2K^{2}\left\|X_{k}-\tilde{X}_{k}\right\|^{2}_{2}\big{|}X,\tilde{X}\right]$
$\displaystyle=2\left(K+K^{2}\right)\cdot\|X-\tilde{X}\|^{2}_{F},$

where $(a)$ follows from the fact that Clip is a contraction mapping, where in
$(b)$, $X_{k}$ denotes the $k$th column of $X\in\Re^{d\times K}$, $(c)$
follows from the fact that softmax is $1$-Lipschitz and $(d)$ follows from the
fact that for all $k$, $\|\tilde{X}_{k}\|^{2}_{2}\leq 1$. ∎

######  Lemma A.4.

For all $d,r,K\in\mathbb{Z}_{++}$ and $\epsilon\geq 0$, if $V\in\Re^{d\times
d}$ consists of elements distributed iid $\mathcal{N}(0,1/d)$,
$A\in\Re^{r\times r}$ consists of elements distributed $\mathcal{N}(0,1)$,
$\mathbb{E}[\|V-\tilde{V}\|^{2}_{F}]\leq\epsilon$, and
$\mathbb{E}[\|A-\tilde{A}\|^{2}_{F}]\leq\epsilon/r$, then

$\mathbb{E}\left[\|f_{\theta}(X)-f_{\tilde{\theta}}(X)\|^{2}_{F}\right]\ \leq\
2K^{2}\epsilon\left(1+Kd\right),$

where $\theta=(V,A),\tilde{\theta}=(\tilde{V},\tilde{A})$.

###### Proof.

$\displaystyle\
\mathbb{E}\left[\left\|f_{\theta}(X)-f_{\tilde{\theta}}(X)\right\|^{2}_{F}\right]$
$\displaystyle\leq\mathbb{E}\left[\sup_{x\in\mathcal{X}}\
\|f_{\theta}(x)-f_{\tilde{\theta}}(x)\|^{2}_{F}\right]$
$\displaystyle=\mathbb{E}\left[\sup_{x\in\mathcal{X}}\left\|Vx\sigma\left(\frac{x^{\top}Ax}{\sqrt{r}}\right)-\tilde{V}x\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right\|^{2}_{F}\right]$
$\displaystyle\overset{(a)}{\leq}2\mathbb{E}\left[\sup_{x\in\mathcal{X}}\left\|\left(V-\tilde{V}\right)x\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right\|^{2}_{F}\right]+2\mathbb{E}\left[\sup_{x\in\mathcal{X}}\left\|Vx\left(\sigma\left(\frac{x^{\top}Ax}{\sqrt{r}}\right)-\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right)\right\|^{2}_{F}\right]$
$\displaystyle\overset{(b)}{\leq}2\mathbb{E}\left[\sup_{x\in\mathcal{X}}\left\|V-\tilde{V}\right\|^{2}_{F}\left\|x\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right\|^{2}_{F}\right]+2\mathbb{E}\left[\sup_{x\in\mathcal{X}}\left\|V\right\|^{2}_{F}\left\|x\sigma\left(\frac{x^{\top}Ax}{\sqrt{r}}\right)-x\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right\|^{2}_{F}\right]$
$\displaystyle\overset{(c)}{\leq}2\epsilon\cdot\sup_{x\in\mathcal{X}}\|x\|^{2}_{F}\cdot\left\|\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right\|^{2}_{F}+2\mathbb{E}\left[\|V\|^{2}_{F}\cdot\sup_{x\in\mathcal{X}}\|x\|^{2}_{F}\left\|\sigma\left(\frac{x^{\top}Ax}{\sqrt{r}}\right)-\sigma\left(\frac{x^{\top}\tilde{A}x}{\sqrt{r}}\right)\right\|^{2}_{F}\right]$
$\displaystyle\overset{(d)}{\leq}2\epsilon
K^{2}+2\mathbb{E}\left[\frac{dK}{r}\cdot\sup_{x\in\mathcal{X}}\left\|x^{\top}Ax-x^{\top}\tilde{A}x\right\|^{2}_{F}\right]$
$\displaystyle\overset{(e)}{\leq}2\epsilon
K^{2}+\frac{2Kd}{r}\cdot\mathbb{E}\left[\sum_{i=1}^{K}\sum_{j=1}^{K}\left(x_{i}^{\top}(A-\tilde{A})x_{j}\right)^{2}\right]$
$\displaystyle\leq 2\epsilon
K^{2}+\frac{2Kd}{r}\cdot\mathbb{E}\left[\sup_{x\in\mathcal{X}}\
\sum_{i=1}^{K}\sum_{j=1}^{K}\left\|A-\tilde{A}\right\|^{2}_{F}\right]$
$\displaystyle=2\epsilon K^{2}+2K^{3}d\epsilon,$

where $(a)$ follows from the fact that $\|a+b\|^{2}_{F}\leq
2\|a\|^{2}_{F}+2\|b\|^{2}_{F}$ for all matrices $a,b$, $(b)$ follows from the
fact that $\|ab\|^{2}_{F}\leq\|a\|^{2}_{\sigma}\|b\|^{2}_{F}$ and
$\|a\|^{2}_{\sigma}\leq\|a\|^{2}_{F}$ for all matrices $a,b$, $(c)$ follows
from the fact that $\mathbb{E}\left[\|V-\tilde{V}\|^{2}_{F}\right]=\epsilon$,
$(d)$ follows from the fact that $\mathbb{E}[\|V\|^{2}_{F}]=d$, and the fact
that softmax is $1$-Lipschitz, and where in $(e)$, $x_{i}$ denotes the $i$th
column of matrix $x$. ∎

######  Lemma A.5.

(sequence transformer distortion bound) For all $d,r,t,K,L\in\mathbb{Z}_{++}$,
$0\leq\epsilon\leq 2d$, and $i\leq L$, if
$\tilde{\theta}_{i}=(\tilde{V}_{i},\tilde{A}_{i})$ for which
$\tilde{V}_{i}=V_{i}+Z^{V}_{i},\tilde{A}_{i}=A_{i}+Z^{A}_{i}$,
$(V_{i},A_{i})\perp(Z^{V}_{i},Z^{A}_{i})$, $Z^{V}_{i}$ consists of elements
distributed iid $\mathcal{N}(0,\epsilon/d^{2})$, and $Z^{A}_{i}$ consists of
elements distributed iid $\mathcal{N}(0,\epsilon/r)$, then

$\mathbb{I}(X_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},H_{t})\leq\epsilon
Kd\left(2K+2K^{2}\right)^{L-i+1}.$

###### Proof.

$\displaystyle\mathbb{I}(X_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},H_{t})$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(X_{t+1}\in\cdot|\theta_{1:L},H_{t})\
\|\
\mathbb{P}(X_{t+1}\in\cdot|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},H_{t})\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(X_{t+1}\in\cdot|\theta_{1:L},H_{t})\
\|\
\mathbb{P}(X_{t+1}\in\cdot|\theta_{i+1:L},\theta_{1:i-1},\theta_{i}\leftarrow\tilde{\theta}_{i},H_{t})\right)\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[\left\|f_{\theta_{1:L}}(H_{t})-f_{\theta_{i+1:L}}(f_{\tilde{\theta}_{i}}(f_{\theta_{1:i-1}}(H_{t})))\right\|^{2}_{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|f_{\theta_{i+1:L}}(f_{\theta_{i}}(f_{\theta_{1:i-1}}(H_{t})))-f_{\theta_{i+1:L}}(f_{\tilde{\theta}_{i}}(f_{\theta_{1:i-1}}(H_{t})))\right\|^{2}_{2}\right]$
$\displaystyle\overset{(c)}{=}\mathbb{E}\left[\left\|f_{\theta_{i+1:L}}(f_{\theta_{i}}(U_{t,i-1}))-f_{\theta_{i+1:L}}(f_{\tilde{\theta}_{i}}(U_{t,i-1}))\right\|^{2}_{2}\right]$
$\displaystyle=\mathbb{E}\left[\frac{\left\|f_{\theta_{i+1:L}}(f_{\theta_{i}}(U_{t,i-1}))-f_{\theta_{i+1:L}}(f_{\tilde{\theta}_{i}}(U_{t,i-1}))\right\|^{2}_{2}}{\left\|f_{\theta_{i}}(U_{t,i-1})-f_{\tilde{\theta}_{i}}(U_{t,i-1})\right\|^{2}_{2}}\cdot\left\|f_{\theta_{i}}(U_{t,i-1})-f_{\tilde{\theta}_{i}}(U_{t,i-1})\right\|^{2}_{2}\right]$
$\displaystyle\overset{(d)}{\leq}\mathbb{E}\left[\left(2K+2K^{2}\right)^{L-i}\cdot\left\|f_{\theta_{i}}(U_{t,i-1})-f_{\tilde{\theta}_{i}}(U_{t,i-1})\right\|^{2}_{2}\right]$
$\displaystyle\overset{(e)}{\leq}\left(2K+2K^{2}\right)^{L-i}\cdot\epsilon
K\left(2K+2K^{2}d\right)$ $\displaystyle\leq\epsilon
Kd\left(2K+2K^{2}\right)^{L-i+1},$

where $(a)$ follows from Lemma 3.1, $(b)$ follows from Lemma B.2, where in
$(c)$, $U_{t,i}=f_{\theta_{1:i}}(H_{t})$, $(d)$ follows from Lemma A.3, and
$(e)$ follows from Lemma A.4. ∎

######  Lemma A.6.

(sequence transformer distortion bound) For all $d,r,K,L\in\mathbb{Z}_{++}$,
$0\leq\epsilon\leq 2d$ and $i\leq L$, if
$\tilde{\theta}_{i}=(\tilde{V}_{i},\tilde{A}_{i})$ for which
$\tilde{V}_{i}=V_{i}+Z^{V}_{i},\tilde{A}_{i}=A_{i}+Z^{A}_{i}$,
$(V_{i},A_{i})\perp(Z^{V}_{i},Z^{A}_{i})$, $Z^{V}_{i}$ consists of elements
distributed iid $\mathcal{N}(0,\epsilon/d^{2})$, and $Z^{A}_{i}$ consists of
elements distributed iid $\mathcal{N}(0,\epsilon/r)$, then

$\mathbb{I}(H_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i})\
\leq\ \epsilon K(t+1)d\left(2K+2K^{2}\right)^{L-i+1}.$

###### Proof.

$\displaystyle\mathbb{I}(H_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i})$
$\displaystyle=\sum_{k=0}^{t}\mathbb{I}(X_{k+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},H_{k})$
$\displaystyle\overset{(a)}{\leq}\sum_{k=0}^{t}\epsilon
Kd\left(2K+2K^{2}\right)^{L-i+1}$ $\displaystyle=\epsilon
K(t+1)d\left(2K+2K^{2}\right)^{L-i+1},$

where $(a)$ follows from Lemma A.5. ∎

######  Lemma A.7.

For all $d,r,t,K,L\in\mathbb{Z}_{++}$, if for all $i\leq L$,
$\tilde{\theta}_{i}=(\tilde{V}_{i},\tilde{A}_{i})$ for which
$\tilde{V}_{i}=V_{i}+Z^{V}_{i},\tilde{A}_{i}=A_{i}+Z^{A}_{i}$,
$(V_{i},A_{i})\perp(Z^{V}_{i},Z^{A}_{i})$, $Z^{V}_{i}$ consists of elements
distributed iid $\mathcal{N}(0,\epsilon/d^{2})$,
$\tilde{A}_{i}=A_{i}+Z^{A}_{i}$, $(V_{i},A_{i})\perp(Z^{V}_{i},Z^{A}_{i})$,
$Z^{V}_{i}$ consists of elements distributed iid
$\mathcal{N}(0,\epsilon/d^{2})$, and $Z^{A}_{i}$ consists of elements
distributed iid $\mathcal{N}(0,\epsilon/r)$, then

$\mathbb{I}(X_{t+1};\theta_{1:L}|\tilde{\theta}_{1:L},H_{t})\ \leq\ \epsilon
KL(t+1)d\left(2K+2K^{2}\right)^{L}.$

###### Proof.

$\displaystyle\mathbb{I}(X_{t+1};\theta_{1:L}|\tilde{\theta}_{1:L},H_{t})$
$\displaystyle=\sum_{i=1}^{L}\
\mathbb{I}(X_{t+1};\theta_{i}|\tilde{\theta}_{1:L},\theta_{i+1:L}H_{t})$
$\displaystyle\overset{(a)}{\leq}\sum_{i=1}^{L}\
\mathbb{I}(H_{t+1};\theta_{i}|\theta_{i+1:L},\theta_{1:i-1},\tilde{\theta}_{i},X_{0})$
$\displaystyle\overset{(b)}{\leq}\epsilon KL(t+1)d\left(2K+2K^{2}\right)^{L},$

where $(a)$ follows from Lemma A.2, and $(b)$ follows from Lemma A.6. ∎

See 3.5

###### Proof.

Let $\epsilon=\frac{\epsilon^{\prime}}{dKLT(2K+2K^{2})^{L}}$.

$\displaystyle\mathbb{I}(\theta_{1:L};\tilde{\theta}_{1:L})$
$\displaystyle=\mathbf{h}(\tilde{\theta}_{1:L})-\mathbf{h}(\tilde{\theta}_{1:L}|\theta_{1:L})$
$\displaystyle=\sum_{i=1}^{L}\mathbf{h}(\tilde{\theta}_{i})-\mathbf{h}(\tilde{\theta}_{i}|\theta_{i})$
$\displaystyle=L\left(\mathbf{h}(\tilde{V}_{i})-\mathbf{h}(\tilde{V}_{i}|V_{i})+\mathbf{h}(\tilde{A}_{i})-\mathbf{h}(\tilde{A}_{i}|A_{i})\right)$
$\displaystyle\leq
L\left(\frac{d^{2}}{2}\log\left(1+\frac{d^{2}KLT(2K+2K^{2})^{L})}{\epsilon^{\prime}}\right)+\frac{r^{2}}{2}\log\left(1+\frac{drKLT(2K+2K^{2})^{L}}{\epsilon^{\prime}}\right)\right)$
$\displaystyle\overset{(a)}{\leq}\frac{(d^{2}+r^{2})L^{2}\log\left(2K+2K^{2}\right)}{2}+\frac{(d^{2}+r^{2})L\log\left(\frac{2dKLT}{\epsilon^{\prime}}\right)}{2}+\frac{d^{2}L\log(d)+r^{2}L\log(r)}{2},$
$\displaystyle\leq\frac{(d^{2}+r^{2})L^{2}\log\left(2K+2K^{2}\right)}{2}+\frac{(d^{2}+r^{2})L\log\left(\frac{2\max\\{d,r\\}\cdot
dKLT}{\epsilon^{\prime}}\right)}{2}$
$\displaystyle\leq\frac{(d^{2}+r^{2})L^{2}\log\left(2K+2K^{2}\right)}{2}+\frac{(d^{2}+r^{2})L\log\left(\frac{2\max\\{d,r\\}\cdot
dKLT}{\epsilon^{\prime}}\right)}{2},$

where $(a)$ holds for $\epsilon^{\prime}<d^{2}KLT(2K+2K^{2})^{L}$. Setting
$\epsilon^{\prime}=(d^{2}+r^{2})L^{2}\log(2K+2K^{2})/2T$ gives the result. ∎

##  Appendix B Meta-Learning from Sequential Data

See 4.1

###### Proof.

In the below proof take all equality to hold _almost surely_.

$\displaystyle\ \mathbb{E}\left[-\ln
P_{m,t}\left(X^{(m)}_{t+1}\right)|H_{m,t}\right]$
$\displaystyle=\mathbb{E}\left[-\ln\hat{P}_{m,t}\left(X^{(m)}_{t+1}\right)+\ln\frac{\hat{P}_{m,t}(X^{(m)}_{t+1})}{P_{m,t}(X^{(m)}_{t+1})}\Big{|}H_{m,t}\right]$
$\displaystyle=\mathbb{E}\left[-\ln\hat{P}_{m,t}\left(X^{(m)}_{t+1}\right)\Big{|}H_{m,t}\right]+\mathbf{d}_{\mathrm{KL}}(\hat{P}_{m,t}\|P_{m,t}).$

The result follows from the fact that
$\mathbf{d}_{\mathrm{KL}}(\hat{P}_{m,t}\|P_{m,t})>0$ for all
$P_{m,t}\neq\hat{P}_{m,t}$. ∎

See 4.2

###### Proof.

$\displaystyle\mathbb{L}_{M,T}$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{E}\left[-\ln\hat{P}_{m,t}(X^{(m)}_{t+1})\right]$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{H}(X_{t+1}^{(m)}|\theta_{m},H_{t}^{(m)})+\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(X_{t+1}^{(m)}\in\cdot|\psi,\theta_{m},H^{(m)}_{t})\|\mathbb{P}(X_{t+1}^{(m)}\in\cdot|H_{m,t})\right)\right]$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\
\mathbb{I}(X_{t+1}^{(m)};\psi,\theta_{m}|H_{m,t})+\mathbb{H}(X_{t+1}^{(m)}|\theta_{m},H_{t}^{(m)})$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\mathbb{I}(H^{(m)}_{T};\psi,\theta_{m}|H_{m-1,T})+\mathbb{H}(H_{T}^{(m)}|\theta_{m})$
$\displaystyle=\frac{1}{MT}\sum_{m=1}^{M}\mathbb{I}(H^{(m)}_{T};\psi|H_{m-1,T})+\mathbb{I}(H_{T}^{(m)};\theta_{m}|\psi,H_{m-1,T})+\mathbb{H}(H_{T}^{(m)}|\theta_{m})$
$\displaystyle=\frac{\mathbb{I}(H_{M,T};\psi)}{MT}+\frac{\mathbb{I}(H^{(1)}_{T};\theta_{1}|\psi)}{T}+\frac{1}{MT}\sum_{m=1}^{M}\mathbb{H}(H_{T}^{(m)}|\theta_{m}).$

∎

See 4.3

###### Proof.

We begin by showing the upper bound:

$\displaystyle\mathcal{L}_{M,T}$
$\displaystyle=\frac{\mathbb{I}(H_{M,T};\psi)}{MT}+\frac{\mathbb{I}(D_{m};\theta_{m}|\psi)}{T}$
$\displaystyle=\frac{\mathbb{I}(H_{M,T};\psi,\tilde{\psi})}{MT}+\frac{\mathbb{I}(D_{m};\theta_{m},\tilde{\theta}_{m}|\psi)}{T}$
$\displaystyle=\frac{\mathbb{I}(H_{M,T};\tilde{\psi})}{MT}+\frac{\mathbb{I}(H_{M,T};\psi|\tilde{\psi})}{MT}+\frac{\mathbb{I}(D_{m};\theta_{m},\tilde{\theta}_{m}|\psi)}{T}$
$\displaystyle\overset{(a)}{\leq}\frac{\mathbb{I}(\psi;\tilde{\psi})}{MT}+\frac{\mathbb{I}(H_{M,T};\psi|\tilde{\psi})}{MT}+\frac{\mathbb{I}(D_{m};\theta_{m},\tilde{\theta}_{m}|\psi)}{T}$
$\displaystyle=\frac{\mathbb{I}(\psi;\tilde{\psi})}{MT}+\frac{\mathbb{I}(H_{M,T};\psi|\tilde{\psi})}{MT}+\frac{\mathbb{I}(D_{m};\tilde{\theta}_{m}|\psi)}{T}+\frac{\mathbb{I}(D_{m};\theta_{m}|\tilde{\theta}_{m},\psi)}{T}$
$\displaystyle\overset{(b)}{\leq}\frac{\mathbb{I}(\psi;\tilde{\psi})}{MT}+\frac{\mathbb{I}(H_{M,T};\psi|\tilde{\psi})}{MT}+\frac{\mathbb{I}(\theta_{m};\tilde{\theta}_{m}|\psi)}{T}+\frac{\mathbb{I}(D_{m};\theta_{m}|\tilde{\theta}_{m},\psi)}{T}$
$\displaystyle\overset{(c)}{\leq}\frac{\mathbb{H}_{\epsilon,M,T}(\psi)}{MT}+\epsilon+\frac{\mathbb{H}_{\epsilon^{\prime},M,T}(\tilde{\theta}_{m}|\psi)}{T}+\epsilon^{\prime},$

where $(a)$ and $(b)$ follow from the data processing inequality and $(c)$
follows from the definition of the rate-distortion functions. The upper bound
follows from the fact that inequality $(c)$ holds for all $\epsilon\geq 0$.

We now prove the lower bound. Suppose that
$\mathbb{I}(H_{M,T};\psi)<\mathbb{H}_{\epsilon,M,T}(\psi)$ Let
$\tilde{\psi}=\tilde{H}_{M,T}\notin\tilde{\Psi}_{\epsilon,M,T}$ where
$\tilde{H}_{M,T}$ is another history sampled in the same manner as $H_{M,T}$.

$\displaystyle\mathbb{I}(H_{M,T};\psi)$
$\displaystyle=\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{I}(X^{(m)}_{t+1};\psi|H_{m,t})$
$\displaystyle\overset{(a)}{\geq}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{I}(X^{(m)}_{t+1};\psi|\tilde{H}_{M,T},H_{m,t})$
$\displaystyle=\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{I}(X^{(m)}_{t+1};\psi|\tilde{\psi},X^{(m)}_{1},\ldots,X^{(m)}_{t})$
$\displaystyle\overset{(b)}{\geq}\epsilon MT,$

where $(a)$ follows from the fact that conditioning reduces entropy and that
$X^{(m)}_{t+1}\perp\tilde{H}_{M,T}|(\psi,H_{m,t})$ and $(b)$ follows from the
fact that $\tilde{\psi}\notin\tilde{\Psi}_{\epsilon,M,T}$. Therefore, for all
$\epsilon\geq 0$,
$\mathbb{I}(H_{M,T};\psi)\geq\min\\{H_{\epsilon,M,T}(\psi),\epsilon MT\\}$.

Suppose that
$\mathbb{I}(H_{T}^{(m)};\theta_{m}|\psi)<\mathbb{H}_{\epsilon,T}(\theta_{m}|\psi)$.
Let $\tilde{\theta}_{m}=\tilde{D}_{m}\notin\tilde{\Theta}_{\epsilon,T}$ where
$\tilde{D}_{m}$ is another history sampled in the same manner as $D_{m}$.

$\displaystyle\mathbb{I}(D_{m};\theta_{m}|\psi)$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{I}(X^{(m)}_{t+1};\theta_{m}|X^{(m)}_{1},\ldots,X^{(m)}_{t},\psi)$
$\displaystyle\overset{(a)}{\geq}\sum_{t=0}^{T-1}\mathbb{I}(X^{(m)}_{t+1};\theta_{m}|\tilde{D}_{m},X^{(m)}_{1},\ldots,X^{(m)}_{t},\psi)$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{I}(X^{(m)}_{t+1};\theta_{m}|\tilde{\theta}_{m},H_{m,t},\psi)$
$\displaystyle\overset{(b)}{\geq}\epsilon T,$

where $(a)$ follows from the fact that conditioning reduces entropy and that
$X^{(m)}_{t+1}\perp\tilde{D}_{m}|(\psi,X^{(m)}_{1},\ldots,X^{(m)}_{t})$ and
$(b)$ follows from the fact that
$\tilde{\theta}_{m}\notin\tilde{\Theta}_{\epsilon,T}$. Therefore, for all
$\epsilon\geq 0$,
$\mathbb{I}(D_{m};\theta_{m}|\psi)\geq\min\\{H_{\epsilon,M,T}(\theta_{m}),\epsilon
T\\}$. The lower bound follows as a result. ∎

###  B.1 Linear Representation Learning Example

We introduce a simple linear representation learning problem as a concrete
example of meta-learning to demonstrate our method of analysis. Just as in the
logistic regression example, the documents in this example consist of iid data
but we begin with such an example for simplicity and to demonstrate this as a
special case of meta-learning from sequences under our framework.

For all $d,r\in\mathbb{Z}_{++}$, we let $\psi:\Omega\mapsto\Re^{d\times r}$ be
distributed uniformly over the set of $d\times r$ matrices with orthonormal
columns. We assume that $d\gg r$. For all $i$, let
$\xi_{i}:\Omega\mapsto\Re^{r}$ be distributed iid $\mathcal{N}(0,I_{r}/r)$. We
let $\theta_{i}=\psi\xi_{i}$ and hence $\psi$ induces a distribution on
$\theta_{i}$. As for the observable data, for each $(i,j)$, let
$X_{j}^{(i)}=\emptyset$ and $Y_{j+1}^{(i)}$ be drawn as according to the
following probability law:

$Y^{(i)}_{j+1}=\begin{cases}1&\text{w.p. }\sigma(\theta_{i})_{1}\\\
2&\text{w.p. }\sigma(\theta_{i})_{2}\\\ \ldots&\\\ d&\text{w.p.
}\sigma(\theta_{i})_{d}\\\ \end{cases},$

where $\sigma(\theta_{i})_{j}=e^{\theta_{i,j}}/\sum_{k=1}^{d}e^{\theta_{i,k}}$
denotes softmax. Note that in this problem, the input $X$ does not influence
the output $Y$. For each task $i$, the algorithm is tasked with estimating a
vector $\theta_{i}$ from noisy observations
$(Y_{1}^{(i)},\ldots,Y_{n}^{(i)})$. By reasoning about data from previous
tasks, the algorithm can estimate $\psi$ which reduces the burden of
estimating $\theta_{i}$ to just estimating $\xi_{i}$ for each task. This is
significant given the assumption that $d\gg r$. We now present the theoretical
result.

######  Theorem B.1.

(linear representation learning Bayesian error bound) For all
$d,r,M,T\in\mathbb{Z}_{++}$,

$\displaystyle\mathcal{L}_{M,T}$
$\displaystyle\leq\frac{dr\left(1+\log\left(1+\frac{M}{r}\right)\right)}{2MT}+\frac{r\left(1+\log(1+\frac{2n}{r})\right)}{2T}.$

The first term indicates the standard irreducible error. The second term
indicates the statistical error incurred in the process of estimating $\psi$.
Since $\psi\in\Re^{d\times r}$ and there are $m\times n$ data points in total
which contain information about $\psi$. The final term represents statistical
error incurred in the process of estimating $\xi_{1},\ldots,\xi_{m}$. Since
each $\xi_{i}\in\Re^{r}$ and there are $n$ data points which contain
information about each $\xi_{i}$ the $\tilde{O}(r/n)$ follows standard
statistical intuition.

We note that this tightens a result shown in (Tripuraneni et al., 2021) which
studies an almost identical problem. Their proposed upper bound is
$\tilde{\mathcal{O}}(\frac{dr^{2}}{MT}+\frac{r}{T})$ which contains an extra
factor of $r$ in the meta-estimation error.

In the following, we will provide a result which requires a change of measure.
For all random variables
$X:\Omega\mapsto\mathcal{X},Y:\Omega\mapsto\mathcal{Y}$ and realizations
$y\in\mathcal{Y}$, one may consider the distribution
$\mathbb{P}(X\in\cdot|Y=y)$. Let function $f(y)=\mathbb{P}(X\in\cdot|Y=y)$.
Then, for any random variable $Z:\Omega\mapsto\mathcal{Z}$ for which
$\mathcal{Z}\subseteq\mathcal{Y}$, we use $\mathbb{P}(X\in\cdot|Y\leftarrow
Z)$ to denote $f(Z)$.

######  Lemma B.2.

(sq error upper bounds softmax KL-divergence) For all $d\in\mathbb{Z}_{++}$
and random vectors $\theta,\tilde{\theta}\in\Re^{d}$,

$\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\ln\frac{\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}}{\frac{e^{\tilde{\theta}_{l}}}{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}}\right]\
\leq\ \mathbb{E}\left[\|\tilde{\theta}-\theta\|^{2}_{2}\right].$

###### Proof.

$\displaystyle\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(Y\in\cdot|\theta)\|\mathbf{d}_{\mathrm{KL}}(Y\in\cdot|\theta\leftarrow\tilde{\theta}))\right]$
$\displaystyle=\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\ln\frac{\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}}{\frac{e^{\tilde{\theta}_{l}}}{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\left(\ln\frac{e^{\theta_{l}}}{e^{\tilde{\theta}_{l}}}+\ln\frac{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\right)\right]$
$\displaystyle=\mathbb{E}\left[\ln\frac{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\right]+\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\ln\frac{e^{\theta_{l}}}{e^{\tilde{\theta}_{l}}}\right]$
$\displaystyle=\mathbb{E}\left[\ln\frac{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\right]+\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\left(\theta_{l}-\tilde{\theta}_{l}\right)\right]$
$\displaystyle=\mathbb{E}\left[\ln\frac{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\right]+\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\left(\theta_{l}-\tilde{\theta}_{l}\right)\right]$
$\displaystyle=\mathbb{E}\left[\ln\frac{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\right]+\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\left(\theta_{l}-\tilde{\theta}_{l}\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\tilde{\theta}_{l}}}{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}\ln\frac{e^{\tilde{\theta}_{l}}}{e^{\theta_{l}}}\right]+\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\left(\theta_{l}-\tilde{\theta}_{l}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\tilde{\theta}_{l}}}{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}\left(\tilde{\theta}_{l}-\theta_{l}\right)\right]+\mathbb{E}\left[\sum_{l=1}^{d}\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\left(\theta_{l}-\tilde{\theta}_{l}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{l=1}^{d}\left(\frac{e^{\tilde{\theta}_{l}}}{\sum_{k=1}^{d}e^{\tilde{\theta}_{k}}}-\frac{e^{\theta_{l}}}{\sum_{k=1}^{d}e^{\theta_{k}}}\right)\left(\tilde{\theta}_{l}-\theta_{l}\right)\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[\sum_{l=1}^{d}\left(\tilde{\theta}_{l}-\theta_{l}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\tilde{\theta}-\theta\|^{2}_{2}\right],$

where $(a)$ follows from the log-sum inequality and $(b)$ follows from the
fact that the softmax function is $1$-Lipschitz. ∎

######  Lemma B.3.

(rate upper bound) For all $d,r,m,n\in\mathbb{Z}_{++}$,

$\frac{\mathbb{I}(H_{m,n};\psi)}{mn}\ \leq\ \inf_{\epsilon\geq 0}\
\frac{dr\log\left(1+\frac{1}{r\epsilon}\right)}{2mn}+\frac{r\log(1+d\epsilon)}{2n}.$

###### Proof.

Let $\tilde{\psi}=\psi+Z$ where $Z\in\Re^{d\times k}$ is $Z\perp\psi$ and
consists of elements which are distributed iid $\mathcal{N}(0,\epsilon)$.

$\displaystyle\frac{\mathbb{I}(H_{m,n};\psi)}{mn}$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{I}(H_{m,n};\psi,\tilde{\psi})}{mn}$
$\displaystyle\overset{(b)}{=}\frac{\mathbb{I}(H_{m,n};\tilde{\psi})}{mn}+\frac{\mathbb{I}(H_{m,n};\psi|\tilde{\psi})}{mn}$
$\displaystyle=\frac{\mathbb{I}(H_{m,n};\tilde{\psi})}{mn}+\frac{\mathbb{H}(H_{m,n}|\tilde{\psi})-\mathbb{H}(H_{m,n}|\psi)}{mn}$
$\displaystyle\overset{(c)}{=}\frac{\mathbb{I}(H_{m,n};\tilde{\psi})}{mn}+\frac{\sum_{i=1}^{m}\mathbb{H}(H_{n}^{(i)}|\tilde{\psi},H_{i-1,n})-m\cdot\mathbb{H}(H_{n}^{(1)}|\psi)}{mn}$
$\displaystyle\overset{(d)}{\leq}\frac{\mathbb{I}(H_{m,n};\tilde{\psi})}{mn}+\frac{m\cdot\mathbf{h}(H_{n}^{(1)}|\tilde{\psi})-m\cdot\mathbf{h}(H_{n}^{(1)}|\psi)}{mn}$
$\displaystyle\overset{(e)}{\leq}\frac{\mathbb{I}(\psi;\tilde{\psi})}{mn}+\frac{\mathbb{I}(H^{(1)}_{n};\psi|\tilde{\psi})}{n}$
$\displaystyle\overset{(f)}{\leq}\frac{\mathbb{I}(\psi;\tilde{\psi})}{mn}+\frac{\mathbb{I}(\theta_{1};\psi|\tilde{\psi})}{n},$

where $(a)$ follows from the fact that $H_{m,n}\perp\tilde{\psi}|\psi$, $(b)$
follows from the chain rule of mutual information, $(c)$ follows from the
chain rule of mutual information and the fact that $H_{n}^{(i)}$ are iid
$|\psi$, $(d)$ follows from the fact that conditioning reduces differential
entropy, and $(e)/(f)$ both follow from the data processing inequality applied
to the markov chains $\tilde{\psi}\perp H_{m,n}|\psi$ and $\psi\perp
H_{n}^{(1)}|\theta_{1},\tilde{\psi}$.

We now bound the two above terms.

$\displaystyle\frac{\mathbb{I}(\psi;\tilde{\psi})}{mn}$
$\displaystyle=\frac{\mathbf{h}(\tilde{\psi})-\mathbf{h}(\tilde{\psi}|\psi)}{mn}$
$\displaystyle\leq\frac{\frac{dr}{2}\log\left(2\pi
e\left(\epsilon+\frac{1}{r}\right)\right)-\frac{dr}{2}\log\left(2\pi
e\epsilon\right)}{mn}$
$\displaystyle=\frac{dr\log\left(1+\frac{1}{r\epsilon}\right)}{2mn},$

where $(a)$ follows from the maximum differential entropy of a random variable
of fixed variance being upper bounded by a Gaussian random variable.

Let $\theta_{\delta}=\theta_{1}+\delta Z$ where $Z\sim\mathcal{N}(0,I_{d})$
and $Z\perp\theta_{1}$.

$\displaystyle\frac{\mathbb{I}(\theta_{1};\psi|\tilde{\psi})}{n}$
$\displaystyle=\frac{\mathbb{I}(\theta_{1};\psi|\tilde{\psi})}{n}$
$\displaystyle=\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(\theta_{1}\in\cdot|\psi)\|\mathbb{P}(\theta_{1}\in\cdot|\tilde{\psi}))\right]}{n}$
$\displaystyle\overset{(a)}{\leq}\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(\theta_{1}\in\cdot|\psi)\|\mathbb{P}(\theta_{\in}\cdot|\psi\leftarrow\tilde{\psi}))\right]}{n}$
$\displaystyle\leq\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\lim_{\delta\to
0}\mathbb{P}(\theta_{\delta}\in\cdot|\psi)\|\lim_{\delta\to
0}\mathbb{P}(\theta_{\delta}|\psi\leftarrow\tilde{\psi}))\right]}{n}$
$\displaystyle\overset{(b)}{=}\frac{1}{n}\mathbb{E}\left[\lim_{\delta\to
0}\frac{1}{2}\log\left(\frac{\left|\delta
I_{d}+\frac{\tilde{\psi}\tilde{\psi}^{\top}}{k}\right|}{\left|\delta
I_{d}+\frac{\psi\psi^{\top}}{k}\right|}\right)-d+{\rm Tr}\left(\left(\delta
I_{d}+\frac{\tilde{\psi}\tilde{\psi}^{\top}}{k}\right)^{-1}\left(\delta
I_{d}+\frac{\psi\psi^{\top}}{k}\right)\right)\right]$
$\displaystyle\overset{(c)}{\leq}\frac{1}{n}\mathbb{E}\left[\lim_{\delta\to
0}\frac{1}{2}\log\left(\frac{\left|\delta
I_{d}+\frac{\tilde{\pi}\tilde{\psi}^{\top}}{k}\right|}{\left|\delta
I_{d}+\frac{\psi\psi^{\top}}{k}\right|}\right)\right]$
$\displaystyle\overset{(d)}{=}\frac{1}{n}\mathbb{E}\left[\lim_{\delta\to
0}\frac{1}{2}\log\left(\frac{\left|\delta
I_{d}\right|\cdot\left|I_{k}+\frac{\tilde{\psi}^{\top}\tilde{\psi}}{k\delta}\right|}{\left|\delta
I_{d}\right|\cdot\left|I_{k}+\frac{\psi^{\top}\psi}{k\delta}\right|}\right)\right]$
$\displaystyle=\frac{1}{n}\mathbb{E}\left[\lim_{\delta\to
0}\frac{1}{2}\log\left(\frac{\left|I_{k}+\frac{\tilde{\psi}^{\top}\tilde{\psi}}{k\delta}\right|}{\left|I_{k}+\frac{I_{k}}{k\delta}\right|}\right)\right]$
$\displaystyle\overset{(e)}{\leq}\lim_{\delta\to
0}\frac{1}{2n}\log\left(\frac{\left|I_{k}+\frac{\mathbb{E}\left[\tilde{\psi}^{\top}\tilde{\psi}\right]}{k\delta}\right|}{\left|I_{k}+\frac{I_{k}}{k\delta}\right|}\right)$
$\displaystyle=\lim_{\delta\to
0}\frac{1}{2n}\log\left(\frac{\left|I_{k}+\frac{\mathbb{E}\left[I_{k}+d\epsilon
I_{k}\right]}{k\delta}\right|}{\left|I_{k}+\frac{I_{k}}{k\delta}\right|}\right)$
$\displaystyle=\lim_{\delta\to
0}\frac{k}{2n}\log\left(\frac{1+\frac{1+d\epsilon}{k\delta}}{1+\frac{1}{k\delta}}\right)$
$\displaystyle=\frac{k}{2n}\log\left(1+d\epsilon\right),$

where $(a)$, $(b)$ follows from continuity of the KL-divergence between two
multivariate normal distributions w.r.t the covariance matrix, $(c)$ follows
from the fact that the trace term is upper bounded by $d$, $(d)$ follows from
the matrix determinant lemma, $\epsilon=\frac{1}{m}$, and $(e)$ follows from
Jensen’s inequality. ∎

######  Lemma B.4.

(distortion upper bound) For all $n,r\in\mathbb{Z}_{++}$,

$\frac{\mathbb{I}(H_{1,n};\theta_{1}|\psi)}{n}\ \leq\ \inf_{\epsilon\geq 0}\
\frac{r\log\left(1+\frac{1}{r\epsilon}\right)}{2n}+r\epsilon$

###### Proof.

Let $\tilde{\xi}=\xi+Z$ where $Z\perp\xi$ and $Z\sim\mathcal{N}(0,\epsilon
I_{r})$.

$\displaystyle\frac{\mathbb{I}(H_{1,n};\theta_{1}|\psi)}{n}$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{I}(H_{1,n};\theta_{1},\tilde{\xi}|\psi)}{n}$
$\displaystyle=\frac{\mathbb{I}(H_{1,n};\tilde{\xi}|\psi)+\mathbb{I}(H_{1,n};\theta_{1}|\tilde{\xi},\psi)}{n}$
$\displaystyle\overset{(b)}{=}\frac{\mathbb{I}(H_{1,n};\tilde{\xi}|\psi)+\sum_{j=1}^{n}\mathbb{I}(Y_{j}^{(1)};\theta_{1}|\tilde{\xi},\psi,H_{1,j-1},X_{j}^{(1)})}{n}$
$\displaystyle=\frac{\mathbb{I}(H_{1,n};\tilde{\xi}|\psi)+\sum_{j=1}^{n}\mathbb{H}(Y_{j}^{(1)}|\tilde{\xi},\psi,H_{1,j-1},X_{j}^{(1)})-\mathbb{H}(Y_{j}^{(1)}|\theta_{1},\psi,\tilde{\xi},H_{1,j-1},X_{j}^{(1)})}{n}$
$\displaystyle\overset{(c)}{=}\frac{\mathbb{I}(H_{1,n};\tilde{\xi}|\psi)+\sum_{j=1}^{n}\mathbb{H}(Y_{j}^{(1)}|\tilde{\xi},\psi,H_{1,j-1},X_{j}^{(1)})-\mathbb{H}(Y_{j}^{(1)}|\theta_{1},\psi,\tilde{\xi},X_{j}^{(1)})}{n}$
$\displaystyle\overset{(d)}{\leq}\frac{\mathbb{I}(H_{1,n};\tilde{\xi}|\psi)+\sum_{j=1}^{n}\mathbb{H}(Y_{j}^{(1)}|\tilde{\xi},\psi,X_{j}^{(1)})-\mathbb{H}(Y_{j}^{(1)}|\theta_{1},\psi,\tilde{\xi},X_{j}^{(1)})}{n}$
$\displaystyle=\frac{\mathbb{I}(H_{1,n};\tilde{\xi}|\psi)}{n}+\mathbb{I}(Y_{j}^{(1)};\theta_{1}|\tilde{\xi},\psi,X_{1}^{(1)})$
$\displaystyle\leq\frac{\mathbb{I}(\xi;\tilde{\xi}|\psi)}{n}+\mathbb{I}(Y_{j}^{(1)};\theta_{1}|\tilde{\xi},\psi),$

where $(a)$ follows from the fact that
$H_{1,n}\perp\tilde{\xi}|\psi,\theta_{1}$, $(b)$ follows from the chain rule
of mutual information, $(c)$ follows from the fact that
$(X_{j}^{(1)},Y_{j}^{(1)})$ is iid $|\theta_{1}$, $(d)$ follows from the fact
that conditioning reduces differential entropy, and $(e)$ follows from the
data processing inequality applied to the markov chain
$H_{1,n}\perp\tilde{\xi}|(\xi,\psi)$.

We now upper bound the two above terms.

$\displaystyle\frac{\mathbb{I}(\xi;\tilde{\xi}|\psi)}{n}$
$\displaystyle=\frac{\mathbf{h}(\tilde{\xi}|\psi)-\mathbf{h}(\tilde{\xi}|\psi,\xi)}{n}$
$\displaystyle=\frac{\mathbf{h}(\tilde{\xi})-\mathbf{h}(\tilde{\xi}|\xi)}{n}$
$\displaystyle=\frac{\mathbf{h}(\tilde{\xi})-\mathbf{h}(Z)}{n}$
$\displaystyle=\frac{\frac{r}{2}\log\left(2\pi
e(\epsilon+\frac{1}{r})\right)-\frac{r}{2}\log\left(2\pi e\epsilon\right)}{n}$
$\displaystyle=\frac{r\log\left(1+\frac{1}{r\epsilon}\right)}{2n}.$

Let $\tilde{\theta}=\psi\tilde{\xi}$. Then,

$\displaystyle\mathbb{I}(Y_{j}^{(1)};\theta_{1}|\tilde{\xi},\psi)$
$\displaystyle\leq\mathbb{I}(Y_{j}^{(1)};\theta_{1}|\tilde{\theta})$
$\displaystyle=\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}\left(Y^{(1)}_{j}\in\cdot|\theta_{1}\right)\|\mathbb{P}\left(Y^{(1)}_{j}\in\cdot|\tilde{\theta}\right)\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}\left(Y^{(1)}_{j}\in\cdot|\theta_{1}\right)\|\mathbb{P}\left(Y^{(1)}_{j}\in\cdot|\theta_{1}\leftarrow\tilde{\theta}\right)\right)\right]$
$\displaystyle\overset{(b}{\leq}\mathbb{E}\left[\|\tilde{\theta}-\theta_{1}\|^{2}_{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\xi-\tilde{\xi}\right)^{\top}\psi^{\top}\psi\left(\xi-\tilde{\xi}\right)\right]$
$\displaystyle=\mathbb{E}\left[\left(\xi-\tilde{\xi}\right)^{\top}\left(\xi-\tilde{\xi}\right)\right]$
$\displaystyle=\mathbb{E}\left[Z^{\top}Z\right]$ $\displaystyle=r\epsilon$

where $(a)$ follows from Lemma 3.1, and $(b)$ follows from Lemma B.2. ∎

See B.1

###### Proof.

$\displaystyle\mathcal{L}_{m,n}$
$\displaystyle\overset{(a)}{\leq}\inf_{\epsilon\geq 0}\
\frac{dr\log\left(1+\frac{1}{r\epsilon}\right)}{2mn}+\frac{r\log(1+d\epsilon)}{2n}+\inf_{\epsilon^{\prime}\geq
0}\frac{r\log\left(1+\frac{1}{r\epsilon^{\prime}}\right)}{2n}+r\epsilon^{\prime}$
$\displaystyle\overset{(b)}{\leq}\frac{dr\log\left(1+\frac{m}{r}\right)}{2mn}+\frac{r\log\left(1+\frac{d}{m}\right)}{2n}+\frac{r\log(1+\frac{2n}{r})}{2n}+\frac{r}{2n}$
$\displaystyle\leq\frac{dr\log\left(1+\frac{m}{r}\right)}{2mn}+\frac{dr}{2mn}+\frac{r\log(1+\frac{2n}{r})}{2n}+\frac{r}{2n},$

where $(a)$ follows directly from Lemmas B.3 and B.4, and $(b)$ follows from
setting $\epsilon=\frac{1}{m}$ and $\epsilon^{\prime}=\frac{1}{2n}$. We choose
these values because they are analytically simpler than the optimal values of
$\epsilon,\epsilon^{\prime}$ but are asymptotically identical to these optimal
values. ∎

###  B.2 Mixture of Transformer

######  Lemma B.5.

(sparse mixture meta-estimation error) For all $R,M,T\in\mathbb{Z}_{++}$,

$\mathbb{I}(H_{M,T};\psi)\leq R\log\left(1+\frac{M}{R}\right)\log(MN).$

###### Proof.

Recall that $\theta_{1:M}$ is distributed $\text{Dirichlet-
Multinomial}(M,[R/N,\ldots,R/N])$. Consider the following prefix-free coding
scheme for $\theta_{1:M}$: For every nonzero category, allocate $\log(M)$ bits
to designate the number of times that category was selected in $\theta_{1:M}$
with and an additional $\log(N)$ bits to designate the category
$(1,\ldots,N)$. We concatenate the bit strings for each such nonzero category.
As a result:

$\displaystyle\mathbb{I}(H_{M,T};\psi)$
$\displaystyle\overset{(a)}{\leq}\mathbb{I}(\theta_{1:M};\psi)$
$\displaystyle\leq\mathbb{H}(\theta_{1:M})$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[\sum_{i=1}^{N}\mathbbm{1}_{[i\in\theta_{1:M}]}\left(\log(M)+\log(N)\right)\right]$
$\displaystyle\overset{(c)}{\leq}R\log\left(1+\frac{M}{R}\right)\log(MN),$

where $(a)$ follows from the data processing inequality, $(b)$ follows from
the fact that entropy is the minimum average prefix-free code length, and
$(c)$ follows from the fact that the average number of non-zero outomes for a
$\text{Dirichlet-Multinomial}(M,[R/N,\ldots,R/N])$ random variable is upper
bounded by $R\log(1+M/R)$. ∎

See 4.5

###### Proof.

Let $\tilde{\Theta}_{N}=\\{\theta+Z_{\theta}:\theta\in\Theta\\}$. $\Theta$ is
the set of $N$ transformer model weights for each of the $N$ models in the
mixture and $Z_{\theta}\perp\theta$ is random noise of the following
characteristic:
$\theta=(A_{1:L},V_{1:L}),\tilde{\theta}=(\tilde{A}_{1:L},\tilde{V}_{1:L})$,
$Z_{\theta}=(Z^{\theta,A}_{1:L},Z^{\theta,V}_{1:L})$, for all $i$,
$\tilde{A}_{i}=A_{i}+Z^{\theta,A}_{i},\tilde{V}_{i}=V_{i}+Z^{\theta,V}_{i}$
where $Z^{\theta,A}_{i}$ consists of elements drawn iid
$\mathcal{N}(0,\frac{2\epsilon T}{r(d^{2}+r^{2})L^{2}\log(4K^{2})})$ and
$Z^{\theta,A}_{i}$ consists of elements drawn iid
$\mathcal{N}(0,\frac{2\epsilon T}{d^{2}(d^{2}+r^{2})L^{2}\log(4K^{2})})$.
$\tilde{\Theta}_{N}$ hence is a collection of lossy compressions of the models
in the mixture.

Let $\tilde{B}\in\\{1,\ldots,N\\}^{M}$ be the collection containing the
outcomes which model from the mixture was ascribed to
$\theta_{1},\ldots,\theta_{M}$. Since there are $N$ different transformers in
the mixture, $\tilde{B}$ takes values in the set $\\{1,\ldots,N\\}^{M}$.

$\displaystyle\mathbb{I}(H_{M,T};\psi,\theta_{1:M})$
$\displaystyle=\mathbb{I}(H_{M,T};\psi,\theta_{1:M},\tilde{\Theta}_{N},\tilde{\beta})$
$\displaystyle=\mathbb{I}(H_{M,T};\psi)+\mathbb{I}(H_{M,T};\tilde{\Theta}_{N},\tilde{\beta}|\psi)+\mathbb{I}(H_{M,T};\theta_{1:M}|\psi,\tilde{\Theta}_{N},\tilde{\beta})$
$\displaystyle\overset{(a)}{\leq}\mathbb{I}(H_{M,T};\psi)+\mathbb{I}(\theta_{1:M};\tilde{\Theta}_{N},\tilde{\beta}|\psi)+\mathbb{I}(H_{M,T};\theta_{1:M}|\psi,\tilde{\Theta}_{N},\tilde{\beta})$
$\displaystyle\overset{(b)}{=}\mathbb{I}(H_{M,T};\psi)+\mathbb{I}(\theta_{1:M};\tilde{\beta}|\psi)+\mathbb{I}(\theta_{1:M};\tilde{\Theta}_{N}|\tilde{\beta},\psi)+\mathbb{I}(H_{M,T};\theta_{1:M}|\psi,\tilde{\Theta}_{N},\tilde{\beta})$
$\displaystyle\leq\mathbb{I}(H_{M,T};\psi)+M\log(N)+\mathbb{E}\left[\mathbb{E}\left[\sum_{i=1}^{N}\mathbbm{1}_{[i\in\tilde{\beta}]}\cdot\mathbb{I}(\Theta[i];\tilde{\Theta}[i])\Big{|}\tilde{\beta}\right]\right]+\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{I}(X_{t+1}^{(m)};\theta_{1:M}|\tilde{\Theta}_{N},\tilde{\beta},H_{m,t})$
$\displaystyle\overset{(c)}{\leq}\mathbb{I}(H_{M,T};\psi)+R\log\left(1+\frac{M}{R}\right)\left[\frac{(d^{2}+r^{2})L^{2}\log\left(4K^{2}\right)}{2}+\frac{(d^{2}+r^{2})L\log\left(\frac{2\max\\{d,r\\}dKLT}{\epsilon}\right)}{2}\right]$
$\displaystyle\quad+MT\epsilon+M\log(N)$
$\displaystyle\overset{(d)}{\leq}\mathbb{I}(H_{M,T};\psi)+R\log\left(1+\frac{M}{R}\right)\left[(d^{2}+r^{2})L^{2}\log\left(4K^{2}\right)+\frac{(d^{2}+r^{2})L\log\left(\frac{4KMT^{2}}{L}\right)}{2}\right]+M\log(N)$
$\displaystyle\leq
R\log\left(1+\frac{M}{R}\right)\left[\log(MN)+(d^{2}+r^{2})L^{2}\log\left(4K^{2}\right)+\frac{(d^{2}+r^{2})L\log\left(\frac{4KMT^{2}}{L}\right)}{2}\right]+M\log(N)$

where $(a)$ follows from the data processing inequality, $(b)$ follows from
the chain rule of mutual information, $(c)$ follows from Theorem 3.5, $(d)$
follows by setting $\epsilon=(d^{2}+r^{2})L^{2}\log(4K^{2})/2MT$, and $(e)$
follows from Lemma B.5. ∎

###  B.3 In-context Learning

See 4.7

###### Proof.

$\displaystyle\mathbb{L}_{M,T,\tau}$
$\displaystyle=\frac{1}{\tau}\sum_{t=0}^{\tau-1}\mathbb{E}\left[-\log\mathbb{P}(X^{(M+1)}_{t+1}|H_{M+1,t})\right]$
$\displaystyle=\frac{1}{\tau}\sum_{t=0}^{\tau-1}\mathbb{E}\left[\log\frac{1}{\mathbb{P}(X^{(M+1)}_{t+1}|\theta_{M+1},H_{M+1,t})}+\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(X^{(M+1)}_{t+1}\in\cdot|\theta_{M+1},H_{M+1,t})\|\mathbb{P}(X^{(M+1)}_{t+1}\in\cdot|H_{M+1,t}))\right]$
$\displaystyle=\frac{1}{\tau}\sum_{t=0}^{\tau-1}\mathbb{H}(X_{t+1}^{(M+1)}|\theta_{M+1},H_{M+1,t})+\mathbb{I}(X_{t+1}^{(M+1)};\theta_{M+1}|H_{M+1,t})$
$\displaystyle=\frac{1}{\tau}\sum_{t=0}^{\tau-1}\mathbb{H}(X_{t+1}^{(M+1)}|\theta_{M+1},X^{(M+1)}_{1},\ldots,X^{(M+1)}_{t})+\mathbb{I}(X_{t+1}^{(M+1)};\theta_{M+1},\psi|H_{M+1,t})$
$\displaystyle\overset{(a)}{=}\frac{\mathbb{H}(D_{M+1}|\theta_{M+1})}{\tau}+\frac{\mathbb{I}(H_{M+1,\tau};\theta_{M+1},\psi|H_{M+1,0})}{\tau}$
$\displaystyle\overset{(b)}{=}\frac{\mathbb{H}(D_{M+1}|\theta_{M+1})}{\tau}+\frac{\mathbb{I}(H_{M+1,\tau};\psi|H_{M+1,0})}{\tau}+\frac{\mathbb{I}(H_{M+1,\tau};\theta_{M+1}|\psi,H_{M+1,0})}{\tau}$
$\displaystyle\overset{(c)}{\leq}\frac{\mathbb{H}(D_{M+1}|\theta_{M+1})}{\tau}+\frac{\mathbb{I}(H_{M+1,T};\psi|H_{M+1,0})}{\tau}+\frac{\mathbb{I}(D_{M+1};\theta_{M+1}|\psi)}{\tau}$
$\displaystyle\overset{(d)}{\leq}\frac{\mathbb{H}(D_{M+1}|\theta_{M+1})}{\tau}+\frac{\mathbb{I}(H_{M+1,T};\psi)}{(M+1)\tau}+\frac{\mathbb{I}(D_{M+1};\theta_{M+1}|\psi)}{\tau},$

where $(a)$ and $(b)$ follow from the chain rule of mutual information, $(c)$
follows from the fact that $\psi\perp H_{M+1,\tau}|H_{M+1,T}$ for $\tau\leq T$
and the data processing inequality, and $(d)$ follows from the fact that for
all $m$,
$\mathbb{I}(H_{m+1,T};\psi|H_{m,T})\leq\mathbb{I}(H_{m,T};\psi|H_{m-1,T})$ and
the chain rule of mutual information. ∎

##  Appendix C Analysis of Suboptimal Meta-Learning Algorithms

All of the prior results bound the error incurred by the optimal algorithm
which produces a prediction of the next token conditioned on the entire past
sequence. In this section, we will derive some simple results which pertain to
_suboptimal_ algorithms.

The following result quantifies the shortfall incurred by an algorithm which
produces an arbitrary prediction $\tilde{P}_{m,t}$ which may depend on the
history $H_{m,t}$.

######  Lemma C.1.

(loss of an arbitrary predictor) For all $M,T\in\mathbb{Z}_{++}$, if for all
$(m,t)\in[M]\times[T]$, $\tilde{P}_{m,t}$ is a predictive distribution which
may depend on the previous data $H_{m,t}$ and $\tilde{\mathcal{L}}_{M,T}$
denotes its cumulative average log-loss, then

$\tilde{\mathbb{L}}_{M,T}=\mathbb{L}_{m,n}+\underbrace{\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\hat{P}_{m,t}\
\big{\|}\ \tilde{P}_{m,t}\right)\right]}_{\rm misspecification\ error},$

Note that because KL divergence is always non-negative and $\mathcal{L}_{m,n}$
is the loss of the Bayesian posterior estimator $\hat{P}$, any prediction
other than $\hat{P}$ will incur nonzero misspecification error.

For a particular class of predictors $\tilde{P}$, we can retrieve the
following upper bound on the _misspecification error_. We consider predictors
which perform Bayesian inference with respect to an incorrectly specified
prior distribution $\tilde{P}_{0}$.

######  Theorem C.2.

(misspecified prior error bound) For all $M,T\in\mathbb{Z}_{++}$ and
$m,t\in[M]\times[T]$, if $\tilde{P}_{m,t}$ is the Bayesian posterior under the
prior $\tilde{P}_{0}(\psi)$, then

$\displaystyle\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\hat{P}_{m,t}\
\big{\|}\
\tilde{P}_{m,t}\right)\right]\leq\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(\psi\in\cdot)\|\tilde{P}_{0}(\psi\in\cdot)\right)\right]}{MT}.$

###### Proof.

$\displaystyle\frac{1}{MT}\sum_{m=1}^{M}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\hat{P}_{m,t}\
\big{\|}\ \tilde{P}_{m,t}\right)\right]$
$\displaystyle\overset{(a)}{=}\frac{1}{MT}\sum_{m=1}^{M}\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(H_{T}^{(m)}\in\cdot)\
\big{\|}\ \tilde{P}_{m}\left(H_{T}^{(m)}\in\cdot\right)\right)\right]$
$\displaystyle\overset{(b)}{=}\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}(\mathbb{P}(H_{M,T}\in\cdot)\
\|\ \tilde{P}(H_{M,T}\in\cdot))\right]}{MT}$
$\displaystyle\overset{(c)}{\leq}\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}(\psi\in\cdot)\
\|\ \tilde{P}_{0}(\psi\in\cdot)\right)\right]}{MT},$

where $(a)$ and $(b)$ follow from the chain rule of KL divergence and $(c)$
follows from the data processing inequality of KL Divergence. ∎

Theorem C.2 suggests that so long as the KL divergence between prior
distributions is finite, the misspecification error should decrease to $0$ as
$M$ and $T$ $\to\infty$. This can be ensured so long as the algorithm’s prior
$\tilde{P}_{0}(\psi)$ does not assign $0$ probability mass to any set for
which the environment prior $\mathbb{P}(\psi)$ assigns non-zero probability.

With these results in place, we provide the following Corollary which exactly
characterizes the loss of a predictor $\tilde{P}$ which produces predictions
via Bayesian inference with respect to a arbitrary prior distribution
$\tilde{P}_{0}(\psi\in\cdot)$.

######  Corollary C.3.

For all $M,T\in\mathbb{Z}_{++}$ and $m,t\in[M]\times[T]$, if $\tilde{P}_{m,t}$
computes probabilities under an arbitrary prior distribution
$\tilde{P}_{0}(\psi\in\cdot)$ and $\tilde{\mathcal{L}}_{M,T}$ denotes its
cumulative average log-loss,, then

$\displaystyle\tilde{\mathbb{L}}_{M,T}$
$\displaystyle=\frac{\mathbb{H}(H_{M,T}|\theta_{1:M})}{MT}+\frac{\mathbb{I}\left(H_{M,T};\psi\right)}{MT}+\frac{\mathbb{I}\left(D_{m};\theta_{m}|\psi\right)}{T}$
$\displaystyle+\frac{\mathbb{E}\left[\mathbf{d}_{\mathrm{KL}}\left(\mathbb{P}\left(H_{M,T}\in\cdot\right)\|\tilde{P}\left(H_{M,T}\in\cdot\right)\right)\right]}{MT}.$