# Asymptotic theory of in-context learning by
linear attention

Yue M. Lu To whom correspondence should be addressed. E-mail: (Y.M.L.)
<EMAIL_ADDRESS>and (C.P<EMAIL_ADDRESS>The John A.
Paulson School of Engineering and Applied Sciences, Harvard University  Mary
I. Letey  The John A. Paulson School of Engineering and Applied Sciences,
Harvard University  Jacob A. Zavatone-Veth J.A.Z-V.(Author Three) contributed
equally to this work with A.M. (Author Four) The John A. Paulson School of
Engineering and Applied Sciences, Harvard University  Department of Physics,
Harvard University  Center for Brain Science, Harvard University  Anindita
Maiti
Cengiz Pehlevan  Center for Brain Science, Harvard University  The Kempner
Institute for the Study of Natural and Artificial Intelligence, Harvard
University

(May 19, 2024)

###### Abstract

Transformers have a remarkable ability to learn and execute tasks based on
examples provided within the input itself, without explicit prior training. It
has been argued that this capability, known as in-context learning (ICL), is a
cornerstone of Transformers’ success, yet questions about the necessary sample
complexity, pretraining task diversity, and context length for successful ICL
remain unresolved. Here, we provide a precise answer to these questions in an
exactly solvable model of ICL of a linear regression task by linear attention.
We derive sharp asymptotics for the learning curve in a phenomenologically-
rich scaling regime where the token dimension is taken to infinity; the
context length and pretraining task diversity scale proportionally with the
token dimension; and the number of pretraining examples scales quadratically.
We demonstrate a double-descent learning curve with increasing pretraining
examples, and uncover a phase transition in the model’s behavior between low
and high task diversity regimes: In the low diversity regime, the model tends
toward memorization of training tasks, whereas in the high diversity regime,
it achieves genuine in-context learning and generalization beyond the scope of
pretrained tasks. These theoretical insights are empirically validated through
experiments with both linear attention and full nonlinear Transformer
architectures.

##  1 Introduction

Since their introduction by Vaswani et al. in 2017 [1], Transformers have
become a cornerstone of modern artificial intelligence (AI). Originally
designed for sequence modeling tasks, such as language modeling and machine
translation, Transformers achieve state-of-the art performance across many
domains, even those that are not inherently sequential [2]. Most strikingly,
they underpin the breakthroughs achieved by large language models such as BERT
[3], LLaMA [4], and the GPT series [5, 6, 7, 8].

The technological advancements enabled by Transformers have inspired a
substantial body of research aimed at understanding their working principles.
One key observation is that language models gain new behaviors and skills as
their number of parameters and the size of their training datasets grow [7, 9,
10, 11]. A particularly important emergent skill is in-context learning (ICL),
which describes the model’s ability to learn and execute tasks based on the
context provided within the input itself, without the need for explicit prior
training on those specific tasks. To give an example from natural language
processing, a pretrained large language model might be able to successfully
translate English to Italian after being prompted with a few example
translations, even if it has not been specifically pretrained on that
translation task [7]. ICL enables language models to perform new, specialized
tasks without retraining, which is arguably a key reason for their general-
purpose abilities.

Despite many recent studies on understanding ICL, important questions about
how and when ICL emerges in large language models are still mostly open. Large
language models are trained (or pretrained) with a next token prediction
objective. How do the different algorithmic and hyperparameter choices that go
into the pretraining procedure affect ICL performance? What algorithms do
Transformers implement for ICL? How many pretraining examples are required for
ICL to emerge? How many examples should be provided within the input for the
model to be able to solve an in-context task? How diverse should the tasks in
the training dataset be for in-context learning of truly new tasks not
observed in the training dataset?

In this paper, we address these questions by investigating the ICL
capabilities of a linear attention module for linear regression tasks. This
model setting allows us to derive an asymptotically precise theory of the
learning curve. In the remainder of this section, we first provide a
comprehensive overview of related works on ICL. Following this, we summarize
our main contributions.

###  1.1 Related Works

#### ICL in Transformer architectures.

The striking ICL abilities of Transformers were thrust to the fore by Brown et
al. [7]’s work on GPT-3. Focusing on natural language processing (NLP) tasks,
they showed that ICL performance dramatically improves with an increase in the
number of model parameters, with an increase in the number of examples in the
model’s context, and with the addition of a natural language task description.
In subsequent work, Wei et al. [11] proposed that the emergence of ICL with
increasing scale is an abrupt, unpredictable transition. This perspective has
substantially influenced proposed accounts for the emergence of ICL [12].
However, Schaeffer et al. [13] have disputed the idea that the emergence of
ICL is unpredictable; they suggest that appropriately-chosen measures of
otherwise hidden progress [14] reveal that ICL gradually develops with scale.

#### Empirical studies of synthetic ICL tasks.

Though ICL in NLP is both impressive and useful, these natural data do not
allow precise experimental control. Towards a fine-grained understanding of
the conditions required for ICL, many recent works have explored ICL of
parametrically-controllable synthetic tasks, notably linear regression and
classification. These works have identified various features of pretraining
data distributions that contribute to the emergence of ICL [15, 16, 17, 18,
19]. Closely related to our work is a study of ICL of linear regression by
Raventós et al. [18]. Their work identified a task diversity threshold for the
emergence of ICL, below which a pretrained Transformer behaves as a Bayesian
estimator with prior determined by the limited set of pretraining tasks. Above
this threshold, the model’s performance matches that of within-context ridge
regression, corresponding to a Gaussian prior over all tasks, including those
not seen during pretraining. This work underscores the roles of task
diversity, regularization, model capacity, and data structure in the emergence
of ICL; a motivating objective of our work is to provide a theoretical account
of their results.

#### Theoretical studies of ICL.

Many theoretical studies of ICL have centered on the idea that Transformers
learn a particular algorithm during pretraining, which is then flexibly
deployed to solve in-context tasks. In broad strokes, papers from this program
of research often consider a particular algorithm for solving an in-context
task, prove that Transformers can approximately implement this algorithm, and
then empirically compare the ICL performance of a pre-trained Transformer to
the performance of that algorithm [20, 21, 22, 23, 24, 25, 26, 27]. A clear
consensus on which algorithm underlies ICL of linear regression in full
transformers has yet to emerge [20, 21, 22, 23, 24, 25, 26, 27]. Within this
line of research, closest to our work are a series of papers that consider ICL
of linear regression by simplified Transformers using linear, rather than
softmax, attention modules [27, 26, 23, 28, 25, 29, 30]. Zhang et al. [27]
study these models in the limit of infinite pretraining dataset size (_i.e._ ,
the population risk limit), and show that their performance on in-context
linear regression nearly matches that of the Bayes-optimal estimator for the
ICL task. However, they found that linear Transformers are not robust to
shifts in the within-context covariate distribution. Zhang et al. [26] then
showed that any optimizer of the within-context risk for a linear Transformer
solves the ICL task with an approximation to one step of gradient descent from
a learnable initialization, and that the resulting estimator can saturate the
Bayes error for tasks with a Gaussian prior and non-zero mean. As we will
discuss in Section 2, our reduction of the linear attention module is inspired
in part by these works. In very recent work, Duraisamy [30] has studied the
fine-sample risk of in-context linear regression with a single step of
gradient descent, without directly analyzing Transformers. Ahn et al. [23] and
Wu et al. [28] investigated how linear Transformers adapt to limited
pretraining data and context length, again showing that in certain cases
nearly-optimal error is achievable. Like these studies, our work considers
linear attention, but our analysis, with its asymptotically sharp predictions
of the ICL performance, allows us to pinpoint when and how the transition from
memorization to ICL of linear regression occurs. We thus in closing highlight
work by Reddy [19] on in-context classification, who analyzed the transition
to ICL using a phenomenological model.

###  1.2 Summary of contributions

We now summarize the primary contributions of our paper, relative to the prior
art reviewed above. Following the recent literature, we focus on a simplified
model of a Transformer that captures its key architectural motif: the linear
self-attention module [25, 26, 29, 28, 27, 23]. Linear attention includes the
quadratic interaction between inputs that lies at the heart of softmax
attention, but does not include the normalization steps or fully-connected
layers. This simplification makes the model more amenable for theoretical
analysis. Our main result is a sharp asymptotic analysis of ICL of linear
regression by linear attention, resulting in a more precisely predictive
theory than previous population risk analyses or finite-sample bounds [27,
26]. The main contributions of our paper are structured as follows:

  1. 1.

We begin in §2 by developing a simplified parameterization of linear self-
attention that allows pretraining on the ICL linear regression task to be
performed using ridge regression.

  2. 2.

Within this simplified model, it is easy to identify the non-trivial scaling
limit in which performance should be analyzed (§3): as the token dimension
tends to infinity, the number of pretraining examples should scale
quadratically (with the token dimension), while the context length and
pretraining task diversity should scale linearly. In this joint limit, we can
compute sharp asymptotics for ICL performance using random matrix theory.

  3. 3.

Our theoretical results reveal several interesting phenomena (§3). First, we
observe double-descent in the model’s ICL generalization performance as a
function of pretraining dataset size, reflecting our assumption that it is
pretrained to interpolation. Second, we uncover a transition to in-context
learning as the pretraining task diversity increases. Concretely, there is a
threshold task diversity above which linear attention saturates the Bayes
error for the ICL regression task. Below that threshold, the model tends to
memorize the limited set of pretraining tasks, and its excess risk is
substantial. This transition recapitulates the empirical findings of Raventós
et al. [18] in full Transformer models.

  4. 4.

In §4, we show through numerical experiments that the insights from our theory
derived on a simplified model transfer to full Transformer models with softmax
self-attention. In particular, the scaling of pretraining sample complexity
and task diversity with token dimension required for successful ICL is
consistent.

More broadly, the study of solvable models is crucial for enhancing our grasp
of how machine learning algorithms learn and generalize across various tasks.
Understanding the mechanistic underpinnings of ICL of well-controlled
synthetic tasks is an important prerequisite to understanding how it emerges
from pretraining on natural data [19].

##  2 Problem formulation

We start by describing the setting of our study.

###  2.1 ICL of linear regression

In an ICL task, the model takes as input a sequence of tokens
$\\{x_{1},y_{1},x_{2},y_{2},\ldots,x_{\ell},y_{\ell},x_{\ell+1}\\}$, and
outputs a prediction of $y_{\ell+1}$. We will often refer to an input sequence
as a “context.” The pairs $\\{x_{i},y_{i}\\}_{i=1}^{\ell+1}$ are i.i.d.
samples from a _context-dependent_ joint distribution $P(x,y)$. Hence, the
model needs to gather information about $P(x,y)$ from the first $\ell$
examples and use this information to predict $y_{\ell+1}$ from $x_{\ell+1}$.
We will refer to $\ell$ as the “context length”.

In this work, we focus on an approximately linear mapping between
$x_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\mathbb{R}$:

$y_{i}=\langle x_{i},w\rangle+\epsilon_{i},$ (1)

where $\epsilon_{i}$ is a Gaussian noise with mean zero and variance $\rho$,
and $w\in\mathbb{R}^{d}$ is referred to as a task vector. We note that the
task vector $w$ is fixed within a context, but can change between different
contexts. The model has to learn $w$ from the $\ell$ pairs presented within
the context, and use it to predict $y_{\ell+1}$ from $x_{\ell+1}$.

###  2.2 Linear self-attention

The model that we will analytically study is the linear self-attention block
[31]. Linear self-attention takes as input an embedding matrix $Z$, whose
columns hold the sequence tokens. The mapping of sequences to matrices is not
unique. Here, following the convention in [27, 28, 31], we will embed the
input sequence
$\\{x_{1},y_{1},x_{2},y_{2},\ldots,x_{\ell},y_{\ell},x_{\ell+1}\\}$ as:

$\displaystyle
Z=\left[\begin{array}[]{ccccc}x_{1}&x_{2}&\ldots&x_{\ell}&x_{\ell+1}\\\
y_{1}&y_{2}&\ldots&y_{\ell}&0\end{array}\right]\in\mathbb{R}^{(d+1)\times(\ell+1)},$
(4)

where $0$ in the lower-right corner is a token that prompts the missing value
$y_{\ell+1}$ to be predicted.

For appropriately sized key, query, and value matrices $K,Q,V$, the output of
a linear-attention block [32, 33, 31] is given by

$\displaystyle A\coloneqq Z+\frac{1}{\ell}VZ(KZ)^{\top}(QZ).$ (5)

The output $A$ is a matrix while our goal is to predict a scalar,
$y_{\ell+1}$. Following the choice of positional encoding in eq. 4, we will
take $A_{d+1,\ell+1}$, the element of $A$ corresponding to the $0$ prompt, as
the prediction for $y_{\ell+1}$:

$\displaystyle\hat{y}\coloneqq A_{d+1,\ell+1}.$ (6)

###  2.3 Pretraining data

The model is pretrained on $n$ sample sequences, where the $\mu$th sample is a
collection of $\ell+1$ vector-scalar pairs
$\\{x_{i}^{\mu}\in\mathbb{R}^{d},y_{i}^{\mu}\in\mathbb{R}\\}_{i=1}^{\ell+1}$
related by the approximate linear mapping in eq. 1: $y_{i}^{\mu}=\langle
x_{i}^{\mu},w^{\mu}\rangle+\epsilon_{i}^{\mu}$. Here, $w^{\mu}$ denotes the
task vector associated with the $\mu$th sample.

We make the following statistical assumptions:

  1. 1.

$x_{i}^{\mu}$ are $d$-dimensional random vectors, sampled i.i.d. over both $i$
and $\mu$ from a Gaussian distribution $\mathcal{N}(0,I_{d}/d)$.

  2. 2.

For $1\leq\mu\leq n$, the task vector $w^{\mu}$ associated with the $\mu$th
sample context is uniformly sampled from a finite set with $k$ elements,
denoted by $\\{w_{1},\ldots,w_{k}\\}$. The elements of this set are
independently drawn once at the beginning of training from

$w_{i}\sim_{\text{i.i.d.}}\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d})),$ (7)

where $\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d}))$ denotes the uniform
distribution on the sphere $\mathcal{S}^{d-1}(\sqrt{d})$ of radius $\sqrt{d}$.
The variable $k$ controls the task diversity in the pretraining data set.
Importantly, $k$ can be less than $n$, in which case the same task vector may
be repeated multiple times.

  3. 3.

The noise terms $\epsilon_{i}^{\mu}$ are i.i.d. over both $i$ and $\mu$, and
drawn from a normal distribution $\mathcal{N}(0,\rho)$.

We denote a sample from this distribution by
$(Z,y_{\ell+1})\sim\mathcal{P}_{\mathrm{train}}$.

###  2.4 Parameter reduction

Before specifying a training procedure, it is insightful to examine the
prediction mechanism of the linear attention module for the ICL task. This
turns out to be a fruitful exercise, shedding light on critical questions: Can
linear self-attention learn linear regression in-context? If so, what
information do model parameters learn from data in solving this ICL problem?
By closely examining these aspects, we can also formulate a simplified problem
that lends itself to analytical study.

We start by rewriting the output of the linear attention module, eq. 6, in an
alternative form. Following Zhang et al. [27], we define

$\displaystyle V=\left[\begin{array}[]{cc}V_{11}&v_{12}\\\
v_{21}^{\top}&v_{22}\end{array}\right],\quad
M=\left[\begin{array}[]{cc}M_{11}&m_{12}\\\
m_{21}^{\top}&m_{22}\end{array}\right]\coloneqq K^{\top}Q,$ (12)

where $V_{11}\in\mathbb{R}^{d\times d}$, $v_{12},v_{21}\in\mathbb{R}^{d\times
1}$, $v_{22}\in\mathbb{R}$, $M_{11}\in\mathbb{R}^{d\times d}$,
$m_{12},m_{21}\in\mathbb{R}^{d\times 1}$, and $m_{22}\in\mathbb{R}$. The
expression we desire is

$\displaystyle\hat{y}$
$\displaystyle=\frac{1}{\ell}\left\langle{x_{\ell+1},v_{22}M_{11}^{\top}\sum_{i=1}^{\ell}y_{i}x_{i}+v_{22}m_{21}\sum_{i=1}^{\ell}y_{i}^{2}+M_{11}^{\top}\sum_{i=1}^{\ell+1}x_{i}x_{i}^{\top}v_{21}+m_{21}\sum_{i=1}^{\ell}y_{i}x_{i}^{\top}v_{21}}\right\rangle,$
(13)

where $\langle\cdot,\cdot\rangle$ stands for the inner product.

This expression reveals several interesting points. First, not all parameters
in (12) contribute to the output: We can ignore all the parameters except the
last row of $V$ and the first $d$ columns of $M$. Second, the first term

$\frac{1}{\ell}v_{22}M_{11}^{\top}\sum_{i=1}^{\ell}y_{i}x_{i}$ (14)

offers a hint about how the linear attention module might be solving the task.
The sum $\frac{1}{\ell}\sum_{i\leq\ell}y_{i}x_{i}$ is a noisy estimate of
$\mathbb{E}[xx^{\top}]w$ for that context. Hence, if the parameters of the
model are such that $v_{22}M_{11}^{\top}$ is approximately
$\mathbb{E}[xx^{\top}]^{-1}$, this term alone makes a good prediction for the
output. Third, the third term does not depend on outputs $y$, and thus does
not directly contribute to the ICL task that relies on the relationship
between $x$ and $y$. Fourth, the last term only considers a one dimensional
projection of $x$ onto $v_{21}$. Because the task vectors $w$ and $x$ are
isotropic in the statistical models that we consider, there are no special
directions in the problem. Consequently, we expect the optimal $v_{21}$ to be
approximately zero by symmetry considerations.

Motivated by these observations, and for analytical tractability, we study the
linear attention module with the constraint $v_{21}=0$. In this case,
collecting the remaining parameters in a matrix

$\displaystyle\Gamma\coloneqq
v_{22}\begin{bmatrix}M_{11}^{\top}/d&m_{21}\end{bmatrix}\in\mathbb{R}^{d\times(d+1)}$
(15)

and the input sequence in another matrix $H_{Z}$, defined as

$\displaystyle H_{Z}\coloneqq
x_{\ell+1}\begin{bmatrix}\frac{d}{\ell}\sum_{i\leq\ell}y_{i}x_{i}^{\top}&\frac{1}{\ell}\sum_{i\leq\ell}y_{i}^{2}\end{bmatrix}\in\mathbb{R}^{d\times(d+1)},$
(16)

we can rewrite the predicted label as

$\hat{y}=\langle\Gamma,H_{Z}\rangle.$ (17)

The $1/d$ scaling of $M_{11}$ in $\Gamma$ is chosen so that the columns of
$H_{Z}$ scale similarly; it does not affect the final predictor $\hat{y}$.

We note that Zhang et al. [27] provide an analysis of population risk (whereas
we focus on empirical risk) for a related reduced model in which they set
$v_{21}=0$ and $m_{21}=0$. Consequently, the predictors they study differ from
ours (17) by an additive term. They justify this choice through an
optimization argument: if these parameters are initialized to zero, they
remain zero under gradient descent optimization of the population risk, given
certain conditions.

In the remainder of this paper, we will examine the ICL performance of the
reduced model given in (16) and (17), except when making comparisons to a
full, nonlinear Transformer architecture. Henceforth, unless explicitly stated
otherwise, we will refer to this reduced model as the linear attention module.

###  2.5 Model pretraining

The parameters of the linear attention module are learned from $n$ samples of
input sequences,

$\displaystyle\\{x_{1}^{\mu},y_{1}^{\mu},\ldots,x_{\ell+1}^{\mu},y_{\ell+1}^{\mu}\\},\qquad\mu=1,\ldots,n.$
(18)

We estimate model parameters using ridge regression, giving

$\displaystyle\Gamma^{\ast}$
$\displaystyle=\underset{\Gamma}{\arg\,\min}\,\sum_{\mu=1}^{n}\left(y_{\ell+1}^{\mu}-\langle\Gamma,H_{Z^{\mu}}\rangle\right)^{2}+\frac{n}{d}\lambda\mathinner{\\!\left\lVert\Gamma\right\rVert}_{\mathrm{F}}^{2},$
(19)

where $\lambda>0$ is a regularization parameter, and $H_{Z^{\mu}}$ refers to
the input matrix (16) populated with the $\mu$th sample sequence. The factor
$n/d$ in front of $\lambda$ makes sure that, when we take the $d\to\infty$ or
$n\to\infty$ limits later, there is still a meaningful ridge regularization.
The solution to the optimization problem in (19) can be expressed explicitly
as

$\displaystyle\text{vec}(\Gamma^{\ast})=\left[\frac{n}{d}\lambda
I+\sum_{\mu=1}^{n}\text{vec}(H_{Z^{\mu}})\text{vec}(H_{Z^{\mu}})^{\top}\right]^{-1}\sum_{\mu=1}^{n}y_{\ell+1}^{\mu}\text{vec}(H_{Z^{\mu}}),$
(20)

where $\operatorname{vec}(\cdot)$ denotes the vectorization operation.
Throughout this paper, we adopt the _row-major_ convention. Thus, for a
$d_{1}\times d_{2}$ matrix $A$, $\operatorname{vec}(A)$ is a vector in
$\mathbb{R}^{d_{1}d_{2}}$, formed by stacking the rows of $A$ together.

###  2.6 Evaluation

For a given set of parameters $\Gamma$, the model’s generalization error is
defined as

$e(\Gamma)=\mathbb{E}_{\mathcal{P}_{\mathrm{test}}}\left[\left(y_{\ell+1}-\langle\Gamma,H_{Z}\rangle\right)^{2}\right],$
(21)

where $(Z,y_{\ell+1})\sim\mathcal{P}_{\mathrm{test}}$ is a new sample drawn
from the distribution of the test data set. We consider two different test
data distributions $\mathcal{P}_{\mathrm{test}}$:

  1. 1.

_ICL task:_ $x_{i}$ and $\epsilon_{i}$ are i.i.d. Gaussians as in the
pretraining case. However, for each $1\leq\mu\leq n$, the task vector
$w^{\mu}$ associated with the $\mu$th input sequence is drawn independently
from $\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d}))$. We will denote the test
error under this setting by $e^{\mathrm{ICL}}(\Gamma)$.

  2. 2.

_In-distribution generalization (IDG) task:_ The test data are generated in
exactly the same manner as the training data, _i.e._ ,
$\mathcal{P}_{\mathrm{test}}=\mathcal{P}_{\mathrm{train}}$, hence the term in-
distribution generalization. In particular, the set of unique task vectors
$\\{w_{1},\ldots,w_{k}\\}$ is identical to that used in the pretraining data.
We will denote the test error under this setting by $e^{\text{IDG}}(\Gamma)$.

The ICL task evaluates the true in-context learning performance of the linear
attention module. The task vectors in the test set differ from those seen in
training, requiring the model to infer them from context. The IDG task
assesses the model’s performance on task vectors encountered during
pretraining. High performance on the IDG task but low performance on the ICL
task indicates that the model memorizes the training task vectors. Conversely,
high performance on the ICL task indicates that the model can learn task
vectors from the provided context.

To understand the performance of our model on both ICL and IDG tasks, we will
need to evaluate these expressions for the pretrained attention matrix
$\Gamma^{\ast}.$ An asymptotically precise prediction of
$e^{\mathrm{ICL}}(\Gamma^{\ast})$ and $e^{\mathrm{IDG}}(\Gamma^{\ast})$ will
be a main result of this work.

###  2.7 Bayes optimal estimators

Following Raventós et al. [18], it is useful to compare the predictions made
by the trained linear attention to optimal estimators that use only the
current context information. These estimators do not rely on data outside of
the given context for their predictions. Under the mean square loss, the
optimal Bayesian estimator
$\hat{y}_{\text{Bayes}}=\mathbb{E}_{\mathcal{P}_{\mathrm{test}}}[y_{\ell+1}|x_{1},y_{1},x_{2},y_{2},\ldots,x_{\ell},y_{\ell},x_{\ell+1}]$
in our setting has the form

$\displaystyle\hat{y}_{\text{Bayes}}=(w^{\text{Bayes}})^{\top}x_{\ell+1},$
(22)

where $w^{\text{Bayes}}$ is the Bayes estimator of the task vector $w$.

For the ICL task, the Bayes-optimal ridge regression estimator is given by

$\displaystyle
w^{\text{Bayes}}_{\text{ridge}}\coloneqq\left(\sum_{i=1}^{\ell}x_{i}x_{i}^{\top}+\rho
I_{d}\right)^{-1}\left(\sum_{i=1}^{\ell}y_{i}x_{i}\right),$ (23)

where the ridge is set to the noise variance $\rho$. We will refer to it as
the _ridge estimator_. For the IDG task, the Bayes-optimal estimator is given
by

$\displaystyle
w^{\text{Bayes}}_{\text{dMMSE}}\coloneqq\frac{\sum_{j=1}^{k}w_{j}e^{-\frac{1}{2\rho}\sum_{i=1}^{\ell}\left(y_{i}-w_{j}^{\top}x_{i}\right)^{2}}}{\sum_{j=1}^{k}e^{-\frac{1}{2\rho}\sum_{i=1}^{\ell}\left(y_{i}-w_{j}^{\top}x_{i}\right)^{2}}}.$
(24)

Here, we assume that the training task vectors $\\{w_{1},\ldots,w_{k}\\}$ are
known to the estimator. Following [18], we will refer to this estimator as the
_discrete minimum mean squared error (dMMSE) estimator_.

The test performance of these estimators are calculated by

$e^{\text{Bayes}}=\mathbb{E}_{\mathcal{P}_{\mathrm{test}}}\left[\left(y_{\ell+1}-(w^{\text{Bayes}})^{\top}x_{\ell+1}\right)^{2}\right],$
(25)

where $\mathcal{P}_{\mathrm{test}}$ can be the ICL or IDG task, and
$w^{\text{Bayes}}$ can be the ridge or the dMMSE estimator. To avoid possible
confusion, we emphasize that we will sometimes plot the performance of an
estimator on a task for which it is not optimal. For example, we will test the
dMMSE estimator, which is Bayes-optimal for the pretraining distribution, on
the ICL task, where it is not optimal. This will be done for benchmarking
purposes.

##  3 Theoretical results

To answer the questions raised in the introduction, we provide a precise
asymptotic analysis of the learning curves of the linear attention module for
ICL of linear regression. We then verify through simulations that the primary
insights gained from our theoretical analysis extend to more realistic
nonlinear Transformers.

###  3.1 Joint asymptotic limit

We have now defined both the structure of the training data as well as the
parameters to be optimized. For our theoretical analysis, we consider a joint
asymptotic limit in which the input dimension $d$, the pretraining dataset
size $n$, the context length $\ell$, and number of task vectors in the
training set $k$, go to infinity together such that

$\displaystyle\frac{\ell}{d}\coloneqq\alpha=\Theta(1),\quad\frac{k}{d}\coloneqq\kappa=\Theta(1),\quad\frac{n}{d^{2}}\coloneqq\tau=\Theta(1).$
(26)

Identification of these scalings constitutes one of the main results of our
paper. As we will see, the linear attention module exhibits rich learning
phenomena in this limit.

The intuition for these scaling parameters can be seen as follows. Standard
results in linear regression [34, 35, 36] show that to estimate a
$d$-dimensional task vector $w$ from the $\ell$ samples within a context, one
needs at least $\ell=\Theta(d)$. The number of unique task vectors that must
be seen to estimate the true $d$-dimensional Gaussian task distribution should
also scale with $d$, _i.e._ $k=\Theta(d)$. Finally, we see from (15) that the
number of linear attention parameters to be learned is $\Theta(d^{2})$. This
suggests that the number of individual contexts the model sees during
pretraining should scale similarly, _i.e._ , $n=\Theta(d^{2})$.

###  3.2 Learning curves for ICL of linear regression by a linear attention
module

Our theoretical analysis, explained in detail in the Supplementary
Information, leads to asymptotically precise expressions for the
generalization error under the two test distributions under study.
Specifically, our theory predicts that, as $d,n,\ell,k\to\infty$ in the joint
limit given in (26),

$e^{\mathrm{ICL}}(\Gamma^{\ast})\longrightarrow
e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda)\qquad\text{almost surely},$
(27)

and

$e^{\mathrm{IDG}}(\Gamma^{\ast})\longrightarrow
e^{\mathrm{IDG}}(\tau,\alpha,\kappa,\rho,\lambda)\qquad\text{almost surely},$
(28)

where $e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda)$ and
$e^{\mathrm{IDG}}(\tau,\alpha,\kappa,\rho,\lambda)$ are two deterministic
functions of the parameters $\tau$, $\alpha$, $\kappa$, $\rho$ and $\lambda$.
The exact expressions of these two functions can be found in SI.5.2 and
SI.5.3, respectively. For simplicity, we only present in what follows the
ridgeless limit (_i.e._ , $\lambda\to 0^{+}$) of the asymptotic generalization
errors.

######  Result 1 (ICL generalization error in the ridgeless limit).

Let

$q^{\ast}\coloneqq\frac{1+\rho}{\alpha},\qquad
m^{\ast}\coloneqq\mathcal{M}_{\kappa}\left({q^{\ast}}\right),\qquad\text{and}\qquad\mu^{\ast}\coloneqq
q^{\ast}\mathcal{M}_{\kappa/\tau}(q^{\ast}),$ (29)

where $\mathcal{M}_{\kappa}(\cdot)$, defined in (B.3), is a function related
to the Stieltjes transform of the Marchenko-Pastur law. Then

$\displaystyle e^{\mathrm{ICL}}_{\mathrm{ridgeless}}\coloneqq\lim_{\lambda\to
0^{+}}e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda)$ (30)
$\displaystyle=\begin{cases}{\frac{\tau(1+q^{\ast})}{1-\tau}\left[1-\tau(1-\mu^{\ast})^{2}+\mu^{\ast}(\rho/q^{\ast}-1)\right]}{-2\tau(1-\mu^{\ast})+(1+\rho)}&\quad\tau<1\\\
\left(q^{\ast}+1\right)\left(1-2q^{\ast}m^{\ast}-(q^{\ast})^{2}\mathcal{M}^{\prime}_{\kappa}(q^{\ast})+\frac{(\rho+q^{\ast}-(q^{\ast})^{2}m^{\ast})m^{\ast}}{\tau-1}\right)-2(1-q^{\ast}m^{\ast})+(1+\rho)&\quad\tau>1\end{cases},$

where $\mathcal{M}^{\prime}_{\kappa}(\cdot)$ denotes the derivative of
$\mathcal{M}_{\kappa}(q)$ with respect to $q$.

######  Result 2 (IDG generalization error in the ridgeless limit).

Let $q^{\ast}$, $m^{\ast}$, and $\mu^{\ast}$ be the scalars defined in (29).
We have

$\displaystyle e^{\mathrm{IDG}}_{\mathrm{ridgeless}}$
$\displaystyle\coloneqq\lim_{\lambda\to
0^{+}}e^{\mathrm{IDG}}(\tau,\alpha,\kappa,\rho,\lambda)$ (31)
$\displaystyle=\begin{cases}\frac{\tau}{1-\tau}\left(\frac{\rho+q^{\ast}-2q^{\ast}(1-\tau)({q^{\ast}}/{\xi^{\ast}}+1)}{1-p^{\ast}(1-\tau)}+\frac{\tau\mu^{\ast}(q^{\ast}+\xi^{\ast})^{2}}{q^{\ast}}\right)&\qquad\tau<1\\\
\frac{\tau}{\tau-1}[\rho+q^{\ast}(1-q^{\ast}m^{\ast})]&\qquad\tau>1\end{cases},$
(32)

where $\xi^{\ast}=\frac{(1-\tau)q^{\ast}}{\tau\mu^{\ast}}$ and
$p^{\ast}=\big{(}1-{\kappa}\big{(}\frac{\kappa\xi^{\ast}}{1-\tau}+1\big{)}^{-2}\big{)}^{-1}$.

We derive these results using techniques from random matrix theory. The full
setup and technical details are presented in the Supplementary Information in
SI.1 through SI.5. A key technical component of our analysis involves
characterizing the spectral properties of the sample covariance matrix of
$n=\Theta(d^{2})$ i.i.d. random vectors in dimension $\Theta(d^{2})$. Each of
these vectors is constructed as the vectorized version of the matrix in (16).
Related but simpler versions of this type of random matrices involving the
tensor product of i.i.d. random vectors have been studied in recent work [37].
Some of our derivations are based on non-rigorous yet technically plausible
heuristics. We support these predictions with numerical simulations and
discuss in the Supplementary Information the steps required to achieve a fully
rigorous proof.

Before discussing the implications of our theoretical results, we first note
that if we take the limit of $\kappa\to\infty$ and $\alpha\to\infty$ in Result
1 (in either order), the ICL generalization error reduces to the
generalization error of simple ridgeless interpolation with isotropic Gaussian
covariates in $d^{2}$ dimensions [36, 38]:

$\displaystyle\lim_{\alpha\to\infty}\lim_{\kappa\to\infty}e^{\mathrm{ICL}}_{\mathrm{ridgeless}}=\lim_{\kappa\to\infty}\lim_{\alpha\to\infty}e^{\mathrm{ICL}}_{\mathrm{ridgeless}}=\begin{dcases}1-\tau+\frac{\rho}{1-\tau}&\tau<1,\\\
\frac{\rho\tau}{\tau-1}&\tau>1.\end{dcases}$ (33)

This limiting result makes sense, given that in this limit the ICL
generalization problem reduces to the generalization error of ridge regression
in $d^{2}$ dimensions with covariates formed as the tensor product of i.i.d.
Gaussian vectors, which by universality results in [37] should in turn be
asymptotically equal to that for isotropic Gaussian covariates [36].

###  3.3 Sample-wise double-descent

(a) Ridgeless ICL error against $\tau$

(b) Ridgeless IDG error against $\tau$

(c) Finite ridge IDG error against $\tau$

Figure 1: ICL performance as a function of $\tau$: theory (solid lines) vs
simulations (dots). Plots of (a), (c) ICL error
$e^{\text{ICL}}(\Gamma^{\ast})$ and (b) IDG error
$e^{\text{IDG}}(\Gamma^{\ast})$ vs $\tau$ at optimal $\Gamma^{\ast}$.
Parameters: $d=80,\kappa=0.5$, and $\rho=0.01$. Averages and standard
deviations are computed over 10 runs.

How large should $n$, the pretraining dataset size, be for the linear
attention to succesfully learn the ICL and IDG tasks? In Figure 1, we plot our
theoretical predictions for the ICL and IDG generalization error as a function
of $\tau=n/d^{2}$ and verify them with numerical simulations. Our results
demonstrate that the quadratic scaling of sample size with input dimensions is
indeed the appropriate regime for nontrivial learning phenomena to occur.

As apparent in Figure 1, we find that the generalization error for both ICL
and IDG tasks are not monotonic in the number of samples. In the ridgeless
limit, both ICL and IDG errors diverge at $\tau=1$, with the leading order
behavior in the $\tau\uparrow 1$ (respectively $\tau\downarrow 1$) limit given
by $\frac{c_{1}}{1-\tau}$ (respectively $\frac{c_{2}}{\tau-1}$), where $c_{1}$
(respectively $c_{2}$) is a $\tau$-independent constant. This leads to a
“double-descent” behavior [39, 36] in the number of samples. As in other
models exhibiting double-descent [39, 36, 38], the location of the divergence
is at the interpolation threshold: the number of parameters of the model
(elements of $\Gamma$) is, to leading order in $d$, equal to $d^{2}$, which
matches the number of pretraining samples at $\tau=1$. Further, we can
investigate the effect of ridge regularisation on the steepness of the double
descent, as illustrated in Figure 1(c) for the ICL task. As we would expect
from other models exhibiting double-descent [39, 36, 38], increasing the
regularization strength suppresses the peak in error around the interpolation
threshold.

###  3.4 The ICL error can have non-monotonic dependence on context length

(a) ICL error against $\alpha$

(b) IDG error against $\alpha$

Figure 2: ICL performance as a function of $\alpha$: theory (solid lines) vs
simulations (dots). Plots of (a) ICL error $e_{g}^{\text{ICL}}(\Gamma^{\ast})$
and (b) IDG error $e_{g}^{\text{IDG}}(\Gamma^{\ast})$ vs $\alpha$ at optimal
$\Gamma^{\ast}$. We highlight that, while the IDG error is monotonic in
$\alpha$, the ICL error for $\kappa=0.5$ and $\kappa=0.75$ is non-monotonic.
Parameters: $d=70,\tau=20,\rho=0.01$, ridgeless. Averages and standard
deviations are computed over 10 runs.

How large should the context length be? In Figure 2, we plot our theoretical
results verified with experiments. We observe that we have correctly
identified the regime where ICL appears: context length scales linearly with
input dimensions. An interesting observation is that the ICL error does not
always monotonically decrease with context length. There are parameter
configurations with $\kappa<1$ (blue curve in Figure 2(a)) for which the ICL
error is minimal at some finite $\alpha$.

###  3.5 Memorization to ICL transition with increasing pretraining task
diversity

Recall that the parameter $\kappa=k/d$ controls the diversity of the training
task vectors. How large should it be for ICL to emerge? Our theory
corroborates a phenomenon that was empirically observed in a recent study
[18]. Figure 3 shows a transition in the nature of the predictions that the
linear attention module makes. For low $\kappa$, the model’s performance is
close to that of the dMMSE estimator. This indicates that the model inherently
assumes the task vector is one of the $k$ vectors encountered in its
pretraining dataset, effectively memorizing these task vectors. As $\kappa$
increases beyond 1, the model’s performance approaches that of the ridge
estimator. In this regime, the model generalizes to task vectors beyond its
pretraining dataset, behaving as if it has learned the true prior on the task
vectors despite having only seen a finite subset in the pretraining dataset.

Figure 3: Comparison of linear Transformer generalization error with the dMMSE
estimator given by eq. 24: theory (solid lines) vs simulations (dots,
triangles). Each value plotted is the excess value of generalisation error
over the noise level $\rho$. Parameters: $\tau=0.2\alpha,\rho=0.01$,
ridgeless. Averages and standard deviations for linear model are computed over
10 runs.

To further understand the role of $\kappa$ in the solution learned by the
linear attention mechanism, consider the regime where $\tau,\alpha\to\infty$
with $\tau/\alpha=c^{\ast}$ kept fixed. Under this setting, we have

$\lim_{\begin{subarray}{c}\tau\to\infty\\\
\alpha\to\infty\end{subarray}}e^{\mathrm{ICL}}_{\mathrm{ridgeless}}=\begin{cases}\rho+(1-\kappa)\left(1+\frac{\rho}{1+\rho}c^{\ast}\right)\qquad&\kappa<1\\\
\rho&\kappa>1\end{cases}.$ (34)

This change in analytical behavior indicates a phase transition at $\kappa=1$.
Further, the $\kappa>1$ branch approaches $\rho$, the error of the Bayes-
optimal ridge estimator in this limit. The smooth memorization-ICL transition
observed in Figure 3 for the finite $\alpha,\tau$ case stems from this phase
transition.

##  4 Experiments with full, nonlinear Transformers

As our theoretical results are derived in a simplified setting, we aim to test
if these insights are applicable to a full, nonlinear Transformer model.
Specifically, we will investigate: (1) whether we have identified the correct
scaling regime for non-trivial learning in an ICL task; (2) if the full
Transformer exhibits a sample-wise double descent, and whether the location of
the peak error scales quadratically with input dimensions as predicted by our
theory; and (3) if the transition from memorization to generalization occurs,
with the transition point being around $\kappa=1$.

(a) Nonlinear model exhibits double descent of test ICL error in scaling
parameter $\tau$.

(b) Interpolation threshold follows predicted $n\propto d^{2}$ scaling.

Figure 4: Experimental verification of both scaling definitions and double
descent behaviour in $n$. Figure 4(a): Increasing $n$ will increase error
until an interpolation threshold is reached.
Figure 4(b) which occurs for $n$ proportional to $d^{2}$, as predicted by the
linear theory. Best fit lines (∗) correspond to fitting $\log(n)=a\log(d)+b$
giving $a_{2}=1.82,b_{2}=3.55$ for 2-layer model and $a_{3}=2.22,b_{3}=2.81$
for 3-layer model. Interpolation threshold was computed empirically by
searching for location in $\tau$ of sharp increase in value and variance of
training error at a fixed number of gradient steps. Parameters:
$d=10,\alpha=5,\kappa=\infty,\rho=0.25^{2}$. For fig. 4(a): 2-layer
architecture; variance shown comes from model trained over different samples
of pretraining data; lines show averages over 10 runs and shaded region shows
standard deviation.

Our experiments111Code to reproduce all experiments is available at
https://github.com/Pehlevan-Group/icl-asymptotic. are done with a standard
Transformer architecture consisting of blocks with: (1) a single-head softmax
self-attention with $K,Q,V\in\mathbb{R}^{hd\times\ell(d+1)}$
matrices222Provided that the hidden layer dimension $hd$ is greater than $d$,
it does not affect the expressivity of the attention mechanism. In our
experiments, we use $h=10$., followed by (2) a two-layer dense MLP with GELU
activation and hidden layer of size $10d$ [1]. Residual connections are used
between the input vector, the pre-MLP output, and the MLP output. Each sample
takes the form given by eq. 4. We use either two or three Transformer blocks
before returning the final logit corresponding to the $(d+1,\ell+1)$th element
in the embedding. The loss function is the mean squared error (MSE) between
the predicted label (the output of the model for a given sample $Z$) and the
true $\hat{y}_{\ell+1}$ value. We train the model in an offline setting with
$n$ samples $Z_{1},\cdots,Z_{n}$, using the Adam optimizer [40] with a
learning rate $10^{-4}$ until the training error converges, typically
requiring 300000-500000 gradient steps. The structure of the pretraining and
test distributions exactly follows the setup described in Section 2.

In Figure 4a, we plot the generalization error and observe the double descent
behavior of a full, nonlinear Transformer for the ICL task as the number of
pretraining samples varies (plotted as a function of $\tau$). We find that the
peak of this curve occurs at the interpolation threshold, identified by
tracking when the training loss is non-zero (see figure caption). Our theory
predicts that the number of samples $n$ at the peak of the curve, as well as
the interpolation threshold, should scale with $d^{2}$. This scaling is indeed
observed in Figure 4b for the full, nonlinear Transformers. These observations
suggest that the nonlinear Transformer operates within the scaling regime we
have identified.

Figure 5: Experiment in 2-layer nonlinear network demonstrates a sharp
transition between dMMSE estimator and ridge estimator, familiar from the
linear theory. Parameters: $d=20,\tau=50,\alpha=5,\rho=0.01$. Variance shown
comes from model trained over different samples of pretraining data; lines
show averages over 10 runs and shaded region shows standard deviation.

Further, as observed before in Raventós et al. [18], we recover the
memorization-to-ICL transition as a function of pretraining task diversity,
shown in Figure 3. We note that this transition happens near $\kappa=1$ in the
nonlinear model, consistent with our theoretical predictions on the linear
model.

##  5 Discussion

In this paper, we computed sharp asymptotics for the in-context learning (ICL)
performance in a simplified model of ICL for linear regression using linear
attention. This exactly solvable model demonstrates a transition from
memorizing pretraining task vectors to generalizing beyond them as the
diversity of pretraining tasks increases, echoing empirical findings in full
Transformers [18]. Additionally, we observe a sample-wise double descent as
the amount of pretraining data increases. Our numerical experiments show that
full, nonlinear Transformers exhibit similar behavior in the scaling regime
relevant to our solvable model. Our work represents a first step towards a
detailed theoretical understanding of the conditions required for ICL to
emerge [19].

Our paper falls within a broader program of research that seeks sharp
asymptotic characterizations of the performance of machine learning
algorithms. This program has a long history in statistical physics [41, 42,
38], and has in recent years attracted substantial attention in machine
learning [36, 43, 44, 45, 46, 47, 48, 38, 49]. For simplicity, we have assumed
that the covariates in the in-context regression problem are drawn from an
isotropic Gaussian. However, our technical approach could be extended to
anisotropic covariates, and, perhaps more interestingly, to featurized linear
attention models in which the inputs are passed through some feature map
before linear attention is applied [33, 32]. This extension would be possible
thanks to an appropriate form of _Gaussian universality_ : for certain classes
of regression problems, the asymptotic error coincides with that of a model
where the true features are replaced with Gaussian features of matched mean
and covariance [36, 43, 44, 45, 46, 47, 48, 37, 50]. This would allow for a
theoretical characterization of ICL for realistic data structure in a close
approximation of full softmax attention, yielding more precise predictions of
how performance scales in real Transformers.

In our analysis, we have assumed that the model is trained to interpolation on
a fixed dataset. This allows us to cast our simplified form of linear
attention pretraining as a ridge regression problem, which in turn enables our
random matrix analysis. In contrast, Transformer-based large language models
are usually trained in a nearly-online setting, where each gradient update is
estimated using fresh examples with no repeating data [51]. Some of our
findings, such as double-descent in the learning curve as a function of the
number of pretraining examples, are unlikely to generalize to the fully-online
setting. It will be interesting to probe these potential differences in future
work.

Finally, our results have some bearing on the broad question of what
architectural features are required for ICL [7, 11, 19]. Our work shows that a
full Transformer—or indeed even full linear attention—is not required for ICL
of linear regression. However, our simplified model retains the structured
quadratic interaction between inputs that is at the heart of the attention
mechanism. It is this quadratic interaction that allows the model to solve the
ICL regression task, which it does essentially by reversing the data
correlation. One would therefore hypothesize that our model is minimal in the
sense that further simplifications within this model class would impair its
ability to solve this ICL task. In the specific context of regression with
isotropic data, a simple point of comparison would be to fix $\Gamma=I_{d}$,
which gives a pretraining-free model that should perform well when the context
length is very long. However, this further-reduced model would perform poorly
if the covariates of the in-context task are anisotropic. More generally, it
would be interesting to investigate when models lacking this precisely-
engineered quadratic interaction can learn linear regression in-context, and
if they are less sample-efficient than the attention-based models considered
here.

## Acknowledgements

YML was supported by NSF Award CCF-1910410, and by the Harvard FAS Dean’s Fund
for Promising Scholarship. JAZV and CP were supported by NSF Award DMS-2134157
and NSF CAREER Award IIS-2239780. CP is further supported by a Sloan Research
Fellowship. AM acknowledges support from Perimeter Institute, which is
supported in part by the Government of Canada through the Department of
Innovation, Science and Economic Development and by the Province of Ontario
through the Ministry of Colleges and Universities. This work has been made
possible in part by a gift from the Chan Zuckerberg Initiative Foundation to
establish the Kempner Institute for the Study of Natural and Artificial
Intelligence. This research was supported in part by grants NSF PHY-1748958
and PHY-2309135 to the Kavli Institute for Theoretical Physics (KITP), through
the authors’ participation in the Fall 2023 program “Deep Learning from the
Perspective of Physics and Neuroscience.”

## References

  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv_ , 2021.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Touvron et al. [2023] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Radford et al. [2018] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.  Improving language understanding by generative pre-training, 2018.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Achiam et al. [2023] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023.
  * Ganguli et al. [2022] Deep Ganguli, Danny Hernandez, Liane Lovitt, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova Dassarma, Dawn Drain, Nelson Elhage, et al.  Predictability and surprise in large generative models.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , pages 1747–1764, 2022.
  * Srivastava et al. [2022] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_ , 2022.
  * Wei et al. [2022] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus.  Emergent abilities of large language models.  _Transactions on Machine Learning Research_ , 2022.  ISSN 2835-8856.  URL https://openreview.net/forum?id=yzkSU5zdwD.
  * Olsson et al. [2022] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah.  In-context learning and induction heads.  _Transformer Circuits Thread_ , 2022.  URL https://transformer-circuits.pub/2022/in-context-learning-and-induction-heads/index.html.
  * Schaeffer et al. [2023] Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo.  Are emergent abilities of large language models a mirage?  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=ITw9edRDlD.
  * Barak et al. [2022] Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang.  Hidden progress in deep learning: Sgd learns parities near the computational limit.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 21750–21764. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/884baf65392170763b27c914087bde01-Paper-Conference.pdf.
  * Chan et al. [2022] Stephanie C. Y. Chan, Adam Santoro, Andrew K. Lampinen, Jane X. Wang, Aaditya Singh, Pierre H. Richemond, Jay McClelland, and Felix Hill.  Data distributional properties drive emergent in-context learning in transformers, 2022.
  * Singh et al. [2023] Aaditya K. Singh, Stephanie C. Y. Chan, Ted Moskovitz, Erin Grant, Andrew M. Saxe, and Felix Hill.  The transient nature of emergent in-context learning in transformers, 2023\.
  * Bietti et al. [2023] Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou.  Birth of a transformer: A memory viewpoint.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 1560–1588. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/0561738a239a995c8cd2ef0e50cfa4fd-Paper-Conference.pdf.
  * Raventós et al. [2023] Allan Raventós, Mansheej Paul, Feng Chen, and Surya Ganguli.  Pretraining task diversity and the emergence of non-bayesian in-context learning for regression.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 14228–14246. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/2e10b2c2e1aa4f8083c37dfe269873f8-Paper-Conference.pdf.
  * Reddy [2024] Gautam Reddy.  The mechanistic basis of data dependence and abrupt learning in an in-context classification task.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=aN4Jf6Cx69.
  * Bai et al. [2023] Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei.  Transformers as statisticians: Provable in-context learning with in-context algorithm selection.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, _Advances in Neural Information Processing Systems_ , volume 36, pages 57125–57211. Curran Associates, Inc., 2023.  URL https://proceedings.neurips.cc/paper_files/paper/2023/file/b2e63e36c57e153b9015fece2352a9f9-Paper-Conference.pdf.
  * Li et al. [2023] Yingcong Li, M. Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak.  Transformers as algorithms: Generalization and stability in in-context learning, 2023.
  * Akyürek et al. [2023] Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou.  What learning algorithm is in-context learning? investigations with linear models.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=0g0X4H8yN4I.
  * Ahn et al. [2023] Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra.  Transformers learn to implement preconditioned gradient descent for in-context learning, 2023.
  * Fu et al. [2023] Deqing Fu, Tian-Qi Chen, Robin Jia, and Vatsal Sharan.  Transformers learn higher-order optimization methods for in-context learning: A study with linear models, 2023.
  * Von Oswald et al. [2023] Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov.  Transformers learn in-context by gradient descent.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 35151–35174. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/von-oswald23a.html.
  * Zhang et al. [2024a] Ruiqi Zhang, Jingfeng Wu, and Peter L. Bartlett.  In-context learning of a linear transformer block: Benefits of the mlp component and one-step gd initialization, 2024a.
  * Zhang et al. [2024b] Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett.  Trained transformers learn linear models in-context.  _Journal of Machine Learning Research_ , 25(49):1–55, 2024b.  URL http://jmlr.org/papers/v25/23-1042.html.
  * Wu et al. [2024] Jingfeng Wu, Difan Zou, Zixiang Chen, Vladimir Braverman, Quanquan Gu, and Peter Bartlett.  How many pretraining tasks are needed for in-context learning of linear regression?  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=vSh5ePa0ph.
  * Chandra et al. [2024] Pritam Chandra, Tanmay Kumar Sinha, Kabir Ahuja, Ankit Garg, and Navin Goyal.  Towards analyzing self-attention via linear neural network, 2024.  URL https://openreview.net/forum?id=4fVuBf5HE9.
  * Duraisamy [2024] Karthik Duraisamy.  Finite sample analysis and bounds of generalization error of gradient descent in in-context linear regression.  _arXiv preprint arXiv:2405.02462_ , 2024.
  * Wang et al. [2020] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma.  Linformer: Self-attention with linear complexity, 2020.
  * Shen et al. [2021] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li.  Efficient attention: Attention with linear complexities.  In _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , pages 3531–3539, 2021.
  * Katharopoulos et al. [2020] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret.  Transformers are RNNs: Fast autoregressive transformers with linear attention.  In _International conference on machine learning_ , pages 5156–5165. PMLR, 2020.
  * Marchenko and Pastur [1967] Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur.  Distribution of eigenvalues for some sets of random matrices.  _Matematicheskii Sbornik_ , 114(4):507–536, 1967\.
  * Bai and Silverstein [2010] Zhidong Bai and Jack W Silverstein.  _Spectral analysis of large dimensional random matrices_ , volume 20.  Springer, 2010.
  * Hastie et al. [2022] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  _The Annals of Statistics_ , 50(2):949 – 986, 2022.  doi: 10.1214/21-AOS2133.  URL https://doi.org/10.1214/21-AOS2133.
  * Dubova et al. [2023] Sofiia Dubova, Yue M. Lu, Benjamin McKenna, and Horng-Tzer Yau.  Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime.  _arXiv_ , 2023.
  * Atanasov et al. [2024] Alexander B. Atanasov, Jacob A. Zavatone-Veth, and Cengiz Pehlevan.  Scaling and renormalization in high-dimensional regression.  _arXiv_ , 2024.
  * Belkin et al. [2019] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  _Proceedings of the National Academy of Sciences_ , 116(32):15849–15854, 2019.
  * Kingma and Ba [2015] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_ , San Diega, CA, USA, 2015.
  * Watkin et al. [1993] Timothy L. H. Watkin, Albrecht Rau, and Michael Biehl.  The statistical mechanics of learning a rule.  _Rev. Mod. Phys._ , 65:499–556, Apr 1993.  doi: 10.1103/RevModPhys.65.499.  URL https://link.aps.org/doi/10.1103/RevModPhys.65.499.
  * Engel and van den Broeck [2001] Andreas Engel and Christian van den Broeck.  _Statistical Mechanics of Learning_.  Cambridge University Press, 2001.  doi: https://doi.org/10.1017/CBO9781139164542.
  * Gerace et al. [2020] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová.  Generalisation error in learning with random features and the hidden manifold model.  In _International Conference on Machine Learning_ , pages 3452–3462. PMLR, 2020.
  * Loureiro et al. [2021] Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová.  Learning curves of generic features maps for realistic datasets with a teacher-student model.  _Advances in Neural Information Processing Systems_ , 34:18137–18151, 2021.
  * Mei and Montanari [2022] Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  _Communications on Pure and Applied Mathematics_ , 75(4):667–766, 2022.
  * Hu and Lu [2022] Hong Hu and Yue M Lu.  Universality laws for high-dimensional learning with random features.  _IEEE Transactions on Information Theory_ , 69(3):1932–1964, 2022.
  * Hu et al. [2024] Hong Hu, Yue M. Lu, and Theodor Misiakiewicz.  Asymptotics of random feature regression beyond the linear scaling regime.  _arXiv:2403.08160_ , 2024.
  * Dhifallah and Lu [2020] Oussama Dhifallah and Yue M Lu.  A precise performance analysis of learning with random features.  _arXiv preprint arXiv:2008.11904_ , 2020.
  * Cui et al. [2024] Hugo Cui, Freya Behrens, Florent Krzakala, and Lenka Zdeborová.  A phase transition between positional and semantic learning in a solvable model of dot-product attention.  _arXiv_ , 2024.
  * Montanari and Saeed [2022] Andrea Montanari and Basil N. Saeed.  Universality of empirical risk minimization.  In Po-Ling Loh and Maxim Raginsky, editors, _Proceedings of Thirty Fifth Conference on Learning Theory_ , volume 178 of _Proceedings of Machine Learning Research_ , pages 4310–4312. PMLR, 02–05 Jul 2022.  URL https://proceedings.mlr.press/v178/montanari22a.html.
  * Muennighoff et al. [2023] Niklas Muennighoff, Alexander M Rush, Boaz Barak, Teven Le Scao, Nouamane Tazi, Aleksandra Piktus, Sampo Pyysalo, Thomas Wolf, and Colin Raffel.  Scaling data-constrained language models.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=j5BuTrEj35.
  * Erdős et al. [2013] László Erdős, Antti Knowles, Horng-Tzer Yau, and Jun Yin.  The local semicircle law for a general class of random matrices.  _Electronic Journal of Probability_ , 18(none):1 – 58, 2013.  doi: 10.1214/EJP.v18-2473.  URL https://doi.org/10.1214/EJP.v18-2473.
  * Erdős and Yau [2017] László Erdős and Horng-Tzer Yau.  _A dynamical approach to random matrix theory_ , volume 28.  American Mathematical Soc., 2017.
  * Householder [1958] Alston S. Householder.  Unitary triangularization of a nonsymmetric matrix.  _J. ACM_ , 5(4):339–342, oct 1958.  ISSN 0004-5411.  doi: 10.1145/320941.320947.  URL https://doi.org/10.1145/320941.320947.
  * Lu [2021] Yue M. Lu.  Householder dice: A matrix-free algorithm for simulating dynamics on Gaussian and random orthogonal ensembles.  _IEEE Transactions on Information Theory_ , 67(12):8264–8272, 2021.  doi: 10.1109/TIT.2021.3114351.
  * Trefethen and Bau [1997] Lloyd N. Trefethen and David Bau, III.  _Numerical Linear Algebra_.  Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997\.  doi: 10.1137/1.9780898719574.  URL https://epubs.siam.org/doi/abs/10.1137/1.9780898719574.

Supplementary Information

Some of the derivations in this document are based on non-rigorous yet
technically sound heuristic arguments from random matrix theory. We support
these predictions with numerical simulations and discuss the steps required to
achieve a fully rigorous proof. All rigorously proven results will be clearly
stated as lemmas, propositions, and the like.

##  SI.1 Notation

_Sets, vectors and matrices:_ For each $n\in\mathbb{N}$,
$[n]\coloneqq\left\\{1,2,\ldots,n\right\\}$. The sphere in $\mathbb{R}^{d}$
with radius $\sqrt{d}$ is expressed as $\mathcal{S}^{d-1}(\sqrt{d})$. For a
vector $v\in\mathbb{R}^{d}$, its $\ell_{2}$ norm is denoted by
$\mathinner{\\!\left\lVert v\right\rVert}$. For a matrix
$A\in\mathbb{R}^{d\times d}$, $\mathinner{\\!\left\lVert
A\right\rVert}_{\mathsf{op}}$ and $\mathinner{\\!\left\lVert
A\right\rVert}_{\mathsf{F}}$ denote the operator (spectral) norm and the
Frobenius norm of $A$, respectively. Additionally, $\mathinner{\\!\left\lVert
A\right\rVert}_{\infty}\coloneqq\max_{i,j\in[n]}\mathinner{\\!\left\lvert
A(i,j)\right\rvert}$ denotes the entry-wise $\ell_{\infty}$ norm. We use
$e_{1}$ to denote the first natural basis vector $(1,0,\ldots,0)$, and $I$ is
an identity matrix. Their dimensions can be inferred from the context. The
trace of $A$ is written as $\operatorname{tr}(A)$.

Our derivations will frequently use the vectorization operation, denoted by
$\operatorname{vec}(\cdot)$. It maps a $d_{1}\times d_{2}$ matrix
$A\in\mathbb{R}^{d_{1}\times d_{2}}$ to a vector $v_{A}=\operatorname{vec}(A)$
in $\mathbb{R}^{d_{1}d_{2}}$. Note that we shall adopt the _row-major_
convention, and thus the rows of $A$ are stacked together to form $v_{A}$. We
also recall the standard identity:

$\operatorname{vec}(E_{1}E_{2}E_{3})=(E_{1}\otimes
E_{3}^{\top})\operatorname{vec}(E_{2}),$ (SI.1.1)

where $\otimes$ denotes the matrix Kronecker product, and $E_{1},E_{2},E_{3}$
are matrices whose dimensions are compatible for the multiplication operation.
For any square matrix $A\in\mathbb{R}^{(L+1)\times(L+1)}$, we introduce the
notation

$[M]_{\setminus 0}\in\mathbb{R}^{L\times L}$ (SI.1.2)

to denote the principal minor of $M$ after removing its first row and column.

_Stochastic order notation_ : In our analysis, we use a concept of high-
probability bounds known as _stochastic domination_. This notion, first
introduced in [52, 53], provides a convenient way to account for low-
probability exceptional events where some bounds may not hold. Consider two
families of nonnegative random variables:

$X=\big{(}X^{(d)}(u)\mathrel{\mathop{\mathchar 58\relax}}d\in\mathbb{N},u\in
U^{(d)}\big{)},\quad Y=\big{(}Y^{(d)}(u)\mathrel{\mathop{\mathchar
58\relax}}d\in\mathbb{N},u\in U^{(d)}\big{)},$

where $U^{(d)}$ is a possibly $d$-dependent parameter set. We say that $X$ is
_stochastically dominated_ by $Y$, uniformly in $u$, if for every (small)
$\varepsilon>0$ and (large) $D>0$ we have

$\sup_{u\in U^{(d)}}\mathbb{P}[X^{(d)}(u)>d^{\varepsilon}Y^{(d)}(u)]\leq
d^{-D}$

for sufficiently large $d\geq d_{0}(\varepsilon,D)$. If $X$ is stochastically
dominated by $Y$, uniformly in $u$, we use the notation $X\prec Y$. Moreover,
if for some family $X$ we have $\mathinner{\\!\left\lvert X\right\rvert}\prec
Y$, we also write $X=\mathcal{O}_{\prec}(Y)$.

We also use the notation $X\simeq Y$ to indicate that two families of random
variables $X,Y$ are asymptotically equivalent. Precisely, $X\simeq Y$, if
there exists $\varepsilon>0$ such that for every $D>0$ we have

$\mathbb{P}\left[\,\mathinner{\\!\left\lvert
X-Y\right\rvert}>d^{-\varepsilon}\right]\leq d^{-D}$ (SI.1.3)

for all sufficiently large $d>d_{0}(\varepsilon,D)$.

##  SI.2 Moment Calculations and Generalization Errors

For a given set of parameters $\Gamma$, its generalization error is defined as

$e(\Gamma)=\mathbb{E}_{\mathcal{P}_{\mathrm{test}}}\left[\left(y_{\ell+1}-\langle\Gamma,H_{Z}\rangle\right)^{2}\right],$
(SI.2.1)

where $(Z,y_{\ell+1})\sim\mathcal{P}_{\mathrm{test}}$ is a new sample drawn
from the distribution of the test data set. Recall that $Z$ is the input
embedding matrix defined in (4) in the main text, and $y_{\ell+1}$ denotes the
missing value to be predicted. The goal of this section is to derive an
expression for the generalization error $e(\Gamma)$.

Note that the test distribution $\mathcal{P}_{\mathrm{test}}$ crucially
depends on the probability distribution of the task vector $w$ used in the
linear model in (1). For the ICL task, we have
$w\sim\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d}))$, the uniform distribution on
the sphere $\mathcal{S}^{d-1}(\sqrt{d})$. For the IDG task, $w$ is sampled
uniformly from the set $\left\\{w_{1},w_{2},\ldots,w_{k}\right\\}$, where
these $k$ vectors are the same as those used in the training data [see (7)].
In what follows, we slightly abuse the notation by writing
$w\sim\mathcal{P}_{\mathrm{test}}$ to indicate that $w$ is sampled from the
task vector distribution associated with $\mathcal{P}_{\mathrm{test}}$.

Let $w$ be the task vector used in the input matrix $Z$. Throughout the paper,
we use $\mathbb{E}_{w}\left[\cdot\right]$ to denote the conditional
expectation with respect to the randomness in the data vectors
$\left\\{x_{i}\right\\}_{i\in[\ell+1]}$ and the noise
$\left\\{\epsilon_{i}\right\\}_{i\in[\ell+1]}$, with the task vector $w$ kept
fixed. We have the following expressions for the first two _conditional_
moments of $(H_{Z},y_{\ell+1})$.

######  Lemma 1 (Conditional moments).

Let the task vector $w\in\mathcal{S}^{d-1}(\sqrt{d})$ be fixed. We have

$\mathbb{E}_{w}\left[y_{\ell+1}\right]=0,\quad\text{and}\quad\mathbb{E}_{w}\left[H_{Z}\right]=0.$
(SI.2.2)

Moreover,

$\mathbb{E}_{w}\left[y_{\ell+1}H_{Z}\right]=\frac{1}{d}w\begin{bmatrix}w^{\top},&1+\rho\end{bmatrix}$
(SI.2.3)

and

$\mathbb{E}_{w}\left[\operatorname{vec}(H_{Z})\operatorname{vec}(H_{Z})^{\top}\right]=\frac{(1+\rho)}{d}I_{d}\otimes\begin{bmatrix}\frac{d}{\ell}I_{d}+(1+\ell^{-1})(1+\rho)^{-1}ww^{\top}&(1+2\ell^{-1})w\\\
(1+2\ell^{-1})w^{\top}&(1+2\ell^{-1})(1+\rho)\end{bmatrix}.$ (SI.2.4)

###### Proof.

Using the equivalent representations in (A.1) and (A.2), it is straightforward
to verify the estimates of the first (conditional) moments in (SI.2.2). To
show (SI.2.3), we note that

$H_{Z}=(d/\ell)z_{a}z_{b}^{\top},$ (SI.2.5)

where

$z_{a}=M_{w}\begin{bmatrix}s\\\ u\end{bmatrix}\qquad\text{and}\qquad
z_{b}=\begin{bmatrix}M_{w}h\\\
(\theta_{w}a/\sqrt{d}+\theta_{\epsilon})^{2}/\sqrt{d}+\theta_{q}^{2}/\sqrt{d}\end{bmatrix}.$
(SI.2.6)

Using the representation in (A.2), we have

$\mathbb{E}_{w}\left[y_{\ell+1}H_{Z}\right]=(d/\ell)\mathbb{E}_{w}\left[y_{\ell+1}z_{a}\right]\mathbb{E}_{w}\left[z_{b}^{\top}\right].$
(SI.2.7)

Computing the expectations $\mathbb{E}_{w}\left[y_{\ell+1}z_{a}\right]$ and
$\mathbb{E}_{w}\left[z_{b}^{\top}\right]$ then gives us (SI.2.3). Next, we
show (SI.2.4). Since $z_{a}$ and $z_{b}$ are _independent_ ,

$\mathbb{E}\left[\operatorname{vec}(H_{Z})\operatorname{vec}(H_{Z})^{\top}\right]=(d/\ell)^{2}\,\mathbb{E}\left[z_{a}z_{a}^{\top}\right]\otimes\mathbb{E}\left[z_{b}z_{b}^{\top}\right].$
(SI.2.8)

The first expectation on the right-hand side is easy to compute. Since $M_{w}$
is an orthonormal matrix,

$\mathbb{E}_{w}\left[z_{a}z_{a}^{\top}\right]=I_{d}$ (SI.2.9)

To obtain the second expectation on the right-hand side of the above
expression, we can first verify that

$\mathbb{E}_{w}\left[M_{w}hh^{\top}M_{w}\right]=\frac{\ell}{d^{2}}\left[(1+\rho)I_{d}+\frac{(\ell+1)}{d}ww^{\top}\right].$
(SI.2.10)

Moreover,

$\mathbb{E}_{w}\left[M_{w}h\left((a/\sqrt{d}+\theta_{\epsilon})^{2}/\sqrt{d}+\theta_{q}^{2}/\sqrt{d}\right)\right]=\frac{\ell(\ell+2)(1+\rho)}{d^{3}}w$
(SI.2.11)

and

$\mathbb{E}_{w}\left[\left((a/\sqrt{d}+\theta_{\epsilon})^{2}/\sqrt{d}+\theta_{q}^{2}/\sqrt{d}\right)^{2}\right]=\frac{\ell(\ell+2)(1+\rho)^{2}}{d^{3}}.$
(SI.2.12)

Combining (SI.2.10), (SI.2.11), and (SI.2.12), we have

$\mathbb{E}\left[z_{b}z_{b}^{\top}\right]=\frac{(\ell/d)^{2}(1+\rho)}{d}\begin{bmatrix}\frac{d}{\ell}I_{d}+(1+\ell^{-1})(1+\rho)^{-1}ww^{\top}&(1+2\ell^{-1})w\\\
(1+2\ell^{-1})w^{\top}&(1+2\ell^{-1})(1+\rho)\end{bmatrix}.$ (SI.2.13)

Substituting (SI.2.9) and (SI.2.13) into (SI.2.4), we reach the formula in
(SI.2.4). ∎

######  Proposition 1 (Generalization error).

For a given weight matrix $\Gamma$, the generalization error of the linear
transformer is

$\displaystyle e(\Gamma)$
$\displaystyle=\frac{1+\rho}{d}\operatorname{tr}\left(\Gamma\begin{bmatrix}\frac{d}{\ell}I_{d}+(1+\ell^{-1})(1+\rho)^{-1}R_{\mathrm{test}}&(1+2\ell^{-1})b_{\mathrm{test}}\\\
(1+2\ell^{-1})b_{\mathrm{test}}^{\top}&(1+2\ell^{-1})(1+\rho)\end{bmatrix}\Gamma^{\top}\right)$
(SI.2.14)
$\displaystyle\qquad\qquad-\frac{2}{d}\operatorname{tr}\left(\Gamma\begin{bmatrix}R_{\mathrm{test}}\\\
(1+\rho)b_{\mathrm{test}}^{\top}\end{bmatrix}\right)+1+\rho,$

where

$b_{\mathrm{test}}\coloneqq\mathbb{E}_{w\sim\mathcal{P}_{\mathrm{test}}}\left[w\right]\quad\text{and}\quad
R_{\mathrm{test}}\coloneqq\mathbb{E}_{w\sim\mathcal{P}_{\mathrm{test}}}\left[ww^{\top}\right].$
(SI.2.15)

######  Remark 1.

We use $w\sim\mathcal{P}_{\mathrm{test}}$ to indicate that $w$ is sampled from
the task vector distribution associated with $\mathcal{P}_{\mathrm{test}}$.
Recall our discussions in Section 2.6. For the ICL task,
$w\sim\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d}))$. It is straightforward to
check that, in this case,

$\textrm{(ICL)}\mathrel{\mathop{\mathchar 58\relax}}\qquad
b_{\mathrm{test}}=0\quad\text{and}\quad R_{\mathrm{test}}=I_{d}.$ (SI.2.16)

For the IDG task, we have

$\text{(IDG)}\mathrel{\mathop{\mathchar 58\relax}}\qquad
b_{\mathrm{test}}=\frac{1}{k}\sum_{i}w_{i}\quad\text{and}\quad
R_{\mathrm{test}}=\frac{1}{k}\sum_{i\in[k]}w_{i}w_{i}^{\top},$ (SI.2.17)

where $\left\\{w_{i}\right\\}_{i\in[k]}$ is the set of fixed task vectors used
in the training data.

###### Proof.

Recall the definition of the generalization error in (SI.2.1). We start by
writing

$\displaystyle
e(\Gamma)=\operatorname{vec}(\Gamma)^{\top}\mathbb{E}\left[\operatorname{vec}(H_{Z})\operatorname{vec}(H_{Z})^{\top}\right]\operatorname{vec}(\Gamma)-2\operatorname{vec}(\Gamma)^{\top}\operatorname{vec}(\mathbb{E}\left[y_{N+1}H_{Z}\right])+\mathbb{E}\left[y_{\ell+1}^{2}\right],$
(SI.2.18)

where $H_{Z}$ is a matrix in the form of (16) and $H_{Z}$ is independent of
$\Gamma$. Since $y_{\ell+1}=x_{\ell+1}^{\top}w+\epsilon$, with
$\epsilon\sim\mathcal{N}(0,\rho)$ denoting the noise, it is straightforward to
check that

$\mathbb{E}\left[y_{\ell+1}^{2}\right]=1+\rho.$ (SI.2.19)

Using the moment estimate (SI.2.4) in Lemma 1 and the identity (SI.1.1), we
have

$\displaystyle\operatorname{vec}(\Gamma)^{\top}\mathbb{E}\left[\operatorname{vec}(H_{Z})\operatorname{vec}(H_{Z})^{\top}\right]\operatorname{vec}(\Gamma)$
(SI.2.20)
$\displaystyle\qquad\qquad=\frac{1+\rho}{d}\operatorname{tr}\left(\Gamma\begin{bmatrix}\frac{d}{\ell}I_{d}+(1+\ell^{-1})(1+\rho)^{-1}R_{\mathrm{test}}&(1+2\ell^{-1})b_{\mathrm{test}}\\\
(1+2\ell^{-1})b_{\mathrm{test}}^{\top}&(1+2\ell^{-1})(1+\rho)\end{bmatrix}\Gamma^{\top}\right).$

Moreover, by (SI.2.3),

$\operatorname{vec}(\Gamma)^{\top}\operatorname{vec}\left(\mathbb{E}\left[y_{\ell+1}H_{Z}\right]\right)=\frac{1}{d}\operatorname{tr}\left(\Gamma\begin{bmatrix}R_{\mathrm{test}}\\\
(1+\rho)b_{\mathrm{test}}^{\top}\end{bmatrix}\right).$ (SI.2.21)

∎

######  Corollary 1.

For a given set of parameters $\Gamma$, its generalization error can be
written as

$e(\Gamma)=\frac{1}{d}\operatorname{tr}\left(\Gamma
B_{\mathrm{test}}\Gamma^{\top}\right)-\frac{2}{d}\operatorname{tr}\left(\Gamma
A_{\mathrm{test}}^{\top}\right)+(1+\rho)+\mathcal{E},$ (SI.2.22)

where

$A_{\mathrm{test}}\coloneqq\begin{bmatrix}R_{\mathrm{test}}&(1+\rho)b_{\mathrm{test}}\end{bmatrix},$
(SI.2.23)
$B_{\mathrm{test}}\coloneqq\begin{bmatrix}\frac{1}{\alpha}(1+\rho)I_{d}+R_{\mathrm{test}}&(1+\rho)b_{\mathrm{test}}\\\
(1+\rho)b_{\mathrm{test}}^{\top}&(1+\rho)^{2}\end{bmatrix},$ (SI.2.24)

and $R_{\mathrm{test}},b_{\mathrm{test}}$ are as defined in (SI.2.15).
Moreover, $\mathcal{E}$ denotes an “error” term such that

$\mathinner{\\!\left\lvert\mathcal{E}\right\rvert}\leq\frac{C_{\alpha,\rho}\max\left\\{\mathinner{\\!\left\lVert
R_{\mathrm{test}}\right\rVert}_{\mathsf{op}},\mathinner{\\!\left\lVert
b_{\mathrm{test}}\right\rVert},1\right\\}\left(\mathinner{\\!\left\lVert\Gamma\right\rVert}_{\mathsf{F}}^{2}/d\right)}{d},$
(SI.2.25)

where $C_{\alpha,\rho}$ is some constant that only depends on $\alpha$ and
$\rho$.

###### Proof.

Let

$\Delta=\begin{bmatrix}\frac{d}{\ell}(1+\rho)I_{d}+(1+\ell^{-1})R_{\mathrm{test}}&(1+2\ell^{-1})(1+\rho)b_{\mathrm{test}}\\\
(1+2\ell^{-1})(1+\rho)b_{\mathrm{test}}^{\top}&(1+2\ell^{-1})(1+\rho)^{2}\end{bmatrix}-B_{\mathrm{test}}.$
(SI.2.26)

It is straightforward to check that

$\displaystyle\mathcal{E}$
$\displaystyle=\frac{1}{d}\operatorname{tr}\left(\Gamma\Delta\Gamma^{\top}\right)$
(SI.2.27)
$\displaystyle=\frac{1}{d}\operatorname{vec}(\Gamma)^{\top}(I_{d}\otimes\Delta)\operatorname{vec}(\Gamma)$
(SI.2.28)
$\displaystyle\leq\mathinner{\\!\left\lVert\Delta\right\rVert}_{\mathsf{op}}\frac{\mathinner{\\!\left\lVert\Gamma\right\rVert}_{\mathsf{F}}^{2}}{d}.$
(SI.2.29)

The bound in (SI.2.25) follows from the estimate that
$\mathinner{\\!\left\lVert\Delta\right\rVert}_{\mathsf{op}}\leq
C_{\alpha,\rho}\max\left\\{\mathinner{\\!\left\lVert
R_{\mathrm{test}}\right\rVert}_{\mathsf{op}},\mathinner{\\!\left\lVert
b_{\mathrm{test}}\right\rVert},1\right\\}/d$. ∎

######  Remark 2.

Consider the optimal weight matrix $\Gamma^{\ast}$ obtained by solving the
ridge regression problem in (19). Since $\Gamma^{\ast}$ is the optimal
solution of (19), we must have

$\frac{n}{d}\lambda\mathinner{\\!\left\lVert\Gamma^{\ast}\right\rVert}_{\mathsf{F}}^{2}\leq\sum_{\mu\in[n]}(y_{\ell+1}^{\mu})^{2},$
(SI.2.30)

where the right-hand side is the value of the objective function of (19) when
we choose $\Gamma$ to be the all-zero matrix. It follows that

$\frac{\mathinner{\\!\left\lVert\Gamma^{\ast}\right\rVert}_{\mathsf{F}}^{2}}{d}\leq\frac{\sum_{\mu\in[n]}(y_{\ell+1}^{\mu})^{2}}{\lambda\,n}.$
(SI.2.31)

By the law of large numbers, $\frac{\sum_{\mu\in[n]}y_{\mu}^{2}}{n}\to 1+\rho$
as $n\to\infty$. Thus,
$\mathinner{\\!\left\lVert\Gamma^{\ast}\right\rVert}_{\mathsf{F}}^{2}/{d}$ is
asymptotically bounded by the constant $(1+\rho)/\lambda$. Furthermore, it is
easy to check that $\mathinner{\\!\left\lVert
R_{\mathrm{test}}\right\rVert}_{\mathsf{op}}=\mathcal{O}(1)$ and
$\mathinner{\\!\left\lVert b_{\mathrm{test}}\right\rVert}=\mathcal{O}(1)$ for
both ICL [see (SI.2.16)] and IDG [see (SI.2.17)]. It then follows from
Corollary 1 that the generalization error associated with the optimal
parameers $\Gamma^{\ast}$ is asymptotically determined by the first three
terms on the right-hand side of (SI.2.22).

##  SI.3 Analysis of Ridge Regression: Extended Resolvent Matrices

We see from Corollary 1 and Remark 2 that the two key quantities in
determining the generalization error $e(\Gamma^{\ast})$ are

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}A_{\mathrm{test}}^{\top})\qquad\text{and}\qquad\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}B_{\mathrm{test}}(\Gamma^{\ast})^{\top}),$
(SI.3.1)

where $A_{\mathrm{test}}$ and $B_{\mathrm{test}}$ are the matrices defined in
(SI.2.23) and (SI.2.24), respectively. In this section, we show that the two
quantities in (SI.3.1) can be obtained by studying a parameterized family of
extended resolvent matrices.

To start, we observe that the ridge regression problem in (19) admits the
following closed-form solution:

$\operatorname{vec}(\Gamma^{\ast})=G\left(\textstyle\sum_{\mu\in[n]}y_{\mu}\operatorname{vec}({H_{\mu}})\right)/d,$
(SI.3.2)

where $G$ is a resolvent matrix defined as

$G=\left(\textstyle\sum_{\mu\in[n]}\operatorname{vec}({H_{\mu}})\operatorname{vec}({H_{\mu}})^{\top}/d+\tau\lambda
I\right)^{-1}.$ (SI.3.3)

For our later analysis of the generalization error, we need to consider a more
general, “parameterized” version of $G$, defined as

$G(\pi)=\left(\textstyle\sum_{\mu\in[n]}\operatorname{vec}({H_{\mu}})\operatorname{vec}({H_{\mu}})^{\top}/d+\pi\Omega+\tau\lambda
I\right)^{-1},$ (SI.3.4)

where $\Omega\in\mathbb{R}^{(d^{2}+d)\times(d^{2}+d)}$ is a symmetric
positive-semidefinite matrix and $\pi$ is a nonnegative scalar. The original
resolvent $G$ in (SI.3.3) is a special case, corresponding to $\pi=0$.

The objects in (SI.3.2) and (SI.3.4) are the submatrices of an _extended_
resolvent matrix, which we construct as follows. For each $\mu\in[n]$, let

$z_{\mu}=\begin{bmatrix}y_{\mu}/d\\\
\operatorname{vec}(H_{\mu})/\sqrt{d}\end{bmatrix}$ (SI.3.5)

be an $(d^{2}+d+1)$-dimensional vector. Let

$\Omega_{e}=\begin{bmatrix}0&\\\ &\Omega\end{bmatrix},$ (SI.3.6)

where $\Omega$ is the $(d^{2}+d)\times(d^{2}+d)$ matrix in (SI.3.4). Define an
extended resolvent matrix

$G_{e}(\pi)=\frac{1}{\sum_{\mu\in[n]}z_{\mu}z_{\mu}^{\top}+\pi\Omega_{e}+\tau\lambda
I}.$ (SI.3.7)

By block-matrix inversion, it is straightforward to check that

$G_{e}(\pi)=\begin{bmatrix}c(\pi)&-c(\pi)q^{\top}(\pi)\\\
-c(\pi)q(\pi)&G(\pi)+c(\pi)q(\pi)q^{\top}(\pi)\end{bmatrix},$ (SI.3.8)

where

$q(\pi)\coloneqq\frac{1}{d^{3/2}}G(\pi)\left(\textstyle\sum_{\mu\in[n]}y_{\mu}\operatorname{vec}({H_{\mu}})\right)$
(SI.3.9)

is a vector in $\mathbb{R}^{d(d+1)}$, and $c(\pi)$ is a scalar such that

$\frac{1}{c(\pi)}=\frac{1}{d^{2}}\sum_{\mu\in[n]}y_{\mu}^{2}+\tau\lambda-\frac{1}{d^{3}}\sum_{\mu,\nu\in[n]}y_{\mu}y_{\nu}\operatorname{vec}(H_{\mu})^{\top}G(\pi)\operatorname{vec}(H_{\nu}).$
(SI.3.10)

By comparing (SI.3.9) with (SI.3.2), we see that

$\operatorname{vec}(\Gamma^{\ast})=\sqrt{d}\,q(0).$ (SI.3.11)

Moreover, as shown in the following lemma, the two key quantities in (SI.3.1)
can also be obtained from the extended resolvent $G_{e}(\pi)$.

######  Lemma 2.

For any matrix $A\in\mathbb{R}^{d\times(d+1)}$,

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}A^{\top})=\frac{-1}{c(0)\sqrt{d}}\begin{bmatrix}0&\operatorname{vec}(A)^{T}\end{bmatrix}G_{e}(0)e_{1},$
(SI.3.12)

where $e_{1}$ denotes the first natural basis vector in
$\mathbb{R}^{d^{2}+d+1}$. Moreover, for any symmetric and positive
semidefinite matrix $B\in\mathbb{R}^{(d+1)\times(d+1)}$, if we set

$\Omega=I_{d}\otimes B$ (SI.3.13)

in (SI.3.6), then

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}B(\Gamma^{\ast})^{\top})=\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c(\pi)}\right)\biggr{|}_{\pi=0}.$
(SI.3.14)

###### Proof.

The identity (SI.3.12) follows immediately from the block form of $G_{e}(\pi)$
in (SI.3.8) and the observation in (SI.3.11). To show (SI.3.14), we take the
derivative of $1/c(\pi)$ with respect to $\pi$. From (SI.3.10), and using the
identity

$\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}G(\pi)=-G(\pi)\Omega
G(\pi),$ (SI.3.15)

we have

$\displaystyle\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c(\pi)}\right)$
$\displaystyle=\frac{1}{d^{3}}\sum_{\mu,\nu\in[n]}y_{\mu}y_{\nu}\operatorname{vec}(H_{\mu})^{\top}G(\pi)\Omega
G(\pi)\operatorname{vec}(H_{\nu})$ (SI.3.16)
$\displaystyle=q^{\top}(\pi)\Omega q(\pi).$ (SI.3.17)

Thus, by (SI.3.11),

$\displaystyle\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c(\pi)}\right)\biggr{|}_{\pi=0}$
$\displaystyle=\frac{1}{d}\left(\operatorname{vec}(\Gamma^{\ast})\right)^{\top}\Omega\operatorname{vec}(\Gamma^{\ast})$
(SI.3.18)
$\displaystyle=\frac{1}{d}\left(\operatorname{vec}(\Gamma^{\ast})\right)^{\top}\left(I_{d}\otimes
B\right)\operatorname{vec}(\Gamma^{\ast}).$ (SI.3.19)

Applying the identity in (SI.1.1) to the right-hand side of the above
equation, we reach (SI.3.14). ∎

######  Remark 3.

To lighten the notation, we will often write $G_{e}(\pi)$ [resp. $G(\pi)$] as
$G_{e}$ [resp. $G$], leaving their dependence on the parameter $\pi$ implicit.

######  Remark 4.

In light of (SI.3.13) and (SI.3.14), we will always choose

$\Omega=I_{d}\otimes B_{\mathrm{test}},$ (SI.3.20)

where $B_{\mathrm{test}}$ is the matrix defined in (SI.2.24).

##  SI.4 An Asymptotic Equivalent of the Extended Resolvent Matrix

In this section, we derive an asymptotic equivalent of the extended resolvent
$G_{e}$ defined in (SI.3.7). From this equivalent version, we can then obtain
the asymptotic limits of the right-hand sides of (SI.3.12) and (SI.3.14). Our
analysis relies on non-rigorous but technically sound heuristic arguments from
random matrix theory. Therefore, we refer to our theoretical predictions as
_results_ rather than propositions.

Recall that there are $k$ unique task vectors
$\left\\{w_{i}\right\\}_{i\in[k]}$ in the training set. Let

$b_{\mathrm{tr}}\coloneqq\frac{1}{k}\sum_{i\in[k]}w_{i}\quad\text{and}\quad
R_{\mathrm{tr}}\coloneqq\frac{1}{k}\sum_{i\in[k]}w_{i}w_{i}^{\top}$ (SI.4.1)

denote the empirical mean and correlation matrix of these $k$ regression
vectors, respectively. Define

$A_{\mathrm{tr}}\coloneqq\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}.$
(SI.4.2)

and

$E_{\mathrm{tr}}\coloneqq\begin{bmatrix}\frac{(1+\rho)}{\alpha}I_{d}+R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\\\
(1+\rho)b_{\mathrm{tr}}^{\top}&(1+\rho)^{2}\end{bmatrix}.$ (SI.4.3)

######  Definition 1.

Consider the extended resolvent $G_{e}(\pi)$ in (SI.3.7), with $\Omega_{e}$
chosen in the forms of (SI.3.6) and (SI.3.20). Let $\widetilde{G}_{e}$ be
another matrix of the same size as $G_{e}(\pi)$. We say that
$\widetilde{G}_{e}$ and $G_{e}(\pi)$ are asymptotically equivalent, if the
following conditions hold.

  1. (1)

For any two deterministic and unit-norm vectors
$u,v\in\mathbb{R}^{d^{2}+d+1}$,

$u^{\top}G_{e}(\pi)v\simeq u^{\top}\widetilde{G}_{e}v,$ (SI.4.4)

where $\simeq$ is the asymptotic equivalent notation defined in (SI.1.3).

  2. (2)

Let
$A_{\mathrm{tr}}=\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}$.
For any deterministic, unit-norm vector $v\in\mathbb{R}^{d^{2}+d+1}$,

$\frac{1}{\sqrt{d}}\begin{bmatrix}0&\operatorname{vec}(A_{\mathrm{tr}})^{\top}\end{bmatrix}G_{e}(\pi)v\simeq\frac{1}{\sqrt{d}}\begin{bmatrix}0&\operatorname{vec}(A_{\mathrm{tr}})^{\top}\end{bmatrix}\widetilde{G}_{e}v.$
(SI.4.5)

  3. (3)

Recall the notation introduced in (SI.1.2). We have

$\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}(\pi)\right]_{\setminus
0}\cdot\left[I\otimes
E_{\mathrm{tr}}\right]\right)=\frac{1}{d^{2}}\operatorname{tr}\left(\left[\widetilde{G}_{e}\right]_{\setminus
0}\cdot\left[I\otimes
E_{\mathrm{tr}}\right]\right)+\mathcal{O}_{\prec}(d^{-1/2}),$ (SI.4.6)

where $\left[G_{e}(\pi)\right]_{\setminus 0}$ and
$\left[\mathcal{G}_{e}(\pi)\right]_{\setminus 0}$ denote the principal minors
of $G_{e}(\pi)$ and $\mathcal{G}_{e}(\pi)$, respectively.

######  Result 3.

Let $\chi_{\pi}$ denote the unique positive solution to the equation

$\chi_{\pi}=\frac{1}{d}\operatorname{tr}\left[\Big{(}\frac{\tau}{1+\chi_{\pi}}E_{\mathrm{tr}}+\pi
B_{\mathrm{test}}+\lambda\tau I_{d}\Big{)}^{-1}E_{\mathrm{tr}}\right],$
(SI.4.7)

where $B_{\mathrm{test}}$ is the positive-semidefinite matrix in (SI.2.24),
with $b_{\mathrm{test}},R_{\mathrm{test}}$ chosen accroding to (SI.2.16) or
(SI.2.17). The extended resolvent $G_{e}(\pi)$ in (SI.3.7) is asymptotically
equivalent to

$\mathcal{G}_{e}(\pi)\coloneqq\left(\frac{\tau}{1+\chi_{\pi}}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)^{\top}\\\
\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)&I_{d}\otimes
E_{\mathrm{tr}}\end{bmatrix}+\pi\Omega_{e}+\tau\lambda I\right)^{-1},$
(SI.4.8)

in the sense of Definition 1. In the above expression, $\Omega_{e}$ is the
matrix in (SI.3.6) with $\Omega=I_{d}\otimes B_{\mathrm{test}}$.

In what follows, we present the steps in reaching the asymptotic equivalent
$\mathcal{G}_{e}(\pi)$ given in (SI.4.8). To start, let $G_{e}^{[\mu]}$ to
denote a “leave-one-out” version of $G_{e}$, defined as

$G_{e}^{[\mu]}=\frac{1}{\sum_{\nu\neq\mu}z_{\nu}z_{\nu}^{\top}+\pi\Omega_{e}+\tau\lambda
I}.$ (SI.4.9)

By (SI.3.7), we have

$G_{e}\left(\textstyle\sum_{\mu\in[n]}z_{\mu}z_{\mu}^{\top}+\pi\Omega_{e}+\tau\lambda
I\right)=I.$ (SI.4.10)

Applying the Woodbury matrix identity then gives us

$\sum_{\mu\in[n]}\frac{1}{1+z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu}}G_{e}^{[\mu]}z_{\mu}z_{\mu}^{\top}+G_{e}(\pi\Omega_{e}+\tau\lambda
I)=I.$ (SI.4.11)

To proceed, we study the quadratic form $z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu}$.
Let $w_{\mu}$ denotes the task vector associated with $z_{\mu}$. Conditioned
on $w_{\mu}$ and $G_{e}^{\mu}$, the quadratic form
$z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu}$ concentrates around its _conditional
expectation_ with respect to the remaining randomness in $z_{\mu}$.
Specifically,

$z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu}=\chi^{\mu}(w_{\mu})+\mathcal{O}_{\prec}(d^{-1/2}),$
(SI.4.12)

where

$\chi^{\mu}(w_{\mu})\coloneqq\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}^{\mu}\right]_{\setminus
0}\cdot\left[I\otimes E(w_{\mu})\right]\right),$ (SI.4.13)

and

$E(w)\coloneqq\begin{bmatrix}\frac{1+\rho}{\alpha}I_{d}+ww^{\top}&(1+\rho)w\\\
(1+\rho)w^{\top}&(1+\rho)^{2}\end{bmatrix}.$ (SI.4.14)

Substituting $z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu}$ in (SI.4.11) by
$\chi^{\mu}(w_{\mu})$, we get

$\sum_{\mu\in[n]}\frac{1}{1+\chi^{\mu}(w_{\mu})}G_{e}^{[\mu]}z_{\mu}z_{\mu}^{\top}+G_{e}(\pi\Omega_{e}+\tau\lambda
I)=I+\Delta_{1},$ (SI.4.15)

where

$\Delta_{1}\coloneqq\sum_{\mu\in[n]}\frac{z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu}-\chi^{\mu}(w_{\mu})}{(1+\chi^{\mu}(w_{\mu}))(1+z_{\mu}^{\top}G_{e}^{[\mu]}z_{\mu})}G_{e}^{[\mu]}z_{\mu}z_{\mu}^{\top}$
(SI.4.16)

is a matrix that captures the approximation error of the above substitution.

Next, we replace $z_{\mu}z_{\mu}^{\top}$ on the left-hand side of (SI.4.15) by
its _conditional_ expectation
$\mathbb{E}_{w_{\mu}}\left[z_{\mu}z_{\mu}^{\top}\right]$, conditioned on the
task vector $w_{\mu}$. This allows us to rewrite (SI.4.15) as

$\sum_{\mu\in[n]}\frac{1}{1+\chi^{\mu}(w_{\mu})}G_{e}^{[\mu]}\mathbb{E}_{w_{\mu}}\left[z_{\mu}z_{\mu}^{\top}\right]+G_{e}(\pi\Omega_{e}+\tau\lambda
I)=I+\Delta_{1}+\Delta_{2},$ (SI.4.17)

where

$\Delta_{2}\coloneqq\sum_{\mu\in[n]}\frac{1}{1+\chi^{\mu}(w_{\mu})}G_{e}^{[\mu]}\left(\mathbb{E}_{w_{\mu}}\left[z_{\mu}z_{\mu}^{\top}\right]-z_{\mu}z_{\mu}^{\top}\right)$
(SI.4.18)

captures the corresponding approximation error. Recall the definition of
$z_{\mu}$ in (SI.3.5). Using the moment estimates in Lemma 1, we have

$\mathbb{E}_{w_{\mu}}\left[z_{\mu}z_{\mu}^{\top}\right]=\frac{1}{d^{2}}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}w_{\mu}^{\top}\otimes\begin{bmatrix}w_{\mu}^{\top}&1+\rho\end{bmatrix}\\\
\frac{1}{\sqrt{d}}w_{\mu}\otimes\begin{bmatrix}w_{\mu}\\\
1+\rho\end{bmatrix}&I_{d}\otimes
E(w_{\mu})\end{bmatrix}+\frac{1}{d^{2}}\begin{bmatrix}0&\\\
&I_{d}\otimes\mathcal{E}_{\mu}\end{bmatrix},$ (SI.4.19)

where $E(w_{\mu})$ is the matrix defined in (SI.4.14) and

$\mathcal{E}_{\mu}=\frac{1}{\ell}\begin{bmatrix}w_{\mu}w_{\mu}^{\top}&2(1+\rho)w_{\mu}\\\
2(1+\rho)w_{\mu}^{\top}&2(1+\rho)^{2}\end{bmatrix}.$ (SI.4.20)

Replacing the conditional expectation
$\mathbb{E}_{w_{\mu}}\left[z_{\mu}z_{\mu}^{\top}\right]$ in (SI.4.17) by the
main (i.e. the first) term on the right-hand side of (SI.4.19), we can
transform (SI.4.17) to

$\frac{\tau}{n}\sum_{\mu\in[n]}\frac{1}{1+\chi^{\mu}(w_{\mu})}G_{e}^{[\mu]}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}w_{\mu}^{\top}\otimes\begin{bmatrix}w_{\mu}^{\top}&1+\rho\end{bmatrix}\\\
\frac{1}{\sqrt{d}}w_{\mu}\otimes\begin{bmatrix}w_{\mu}\\\
1+\rho\end{bmatrix}&I_{d}\otimes
E(w_{\mu})\end{bmatrix}+G_{e}(\pi\Omega_{e}+\tau\lambda
I)=I+\Delta_{1}+\Delta_{2}+\Delta_{3},$ (SI.4.21)

where we recall $\tau=n/d^{2}$, and we use $\Delta_{3}$ to capture the
approximation error associated with $\mathcal{E}_{\mu}$.

Next, we replace the “leave-one-out” terms $G_{e}^{\mu}$ and
$\chi^{\mu}(w_{\mu})$ in (SI.4.21) by their “full” versions. Specifically, we
replace $G_{e}^{\mu}$ by $G_{e}$, and $\chi^{\mu}(w_{\mu})$ by

$\chi(w_{\mu})\coloneqq\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}\right]_{\setminus
0}\cdot\left[I\otimes E(w_{\mu})\right]\right).$ (SI.4.22)

It is important to note the difference between (SI.4.13) and (SI.4.22): the
former uses $G_{e}^{\mu}$ and the latter $G_{e}$. After these replacements and
using $\Delta_{4}$ to capture the approximation errors, we have

$G_{e}\left(\frac{\tau}{n}\sum_{\mu\in[n]}\frac{1}{1+\chi(w_{\mu})}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}w_{\mu}^{\top}\otimes\begin{bmatrix}w_{\mu}^{\top}&1+\rho\end{bmatrix}\\\
\frac{1}{\sqrt{d}}w_{\mu}\otimes\begin{bmatrix}w_{\mu}\\\
1+\rho\end{bmatrix}&I_{d}\otimes
E(w_{\mu})\end{bmatrix}+\pi\Omega_{e}+\tau\lambda I\right)=I+\sum_{j\leq
4}\Delta_{j}.$ (SI.4.23)

Recall that there are $k$ unique task vectors $\left\\{w_{i}\right\\}_{1\leq
i\leq k}$ in the training set consisting of $n$ input samples. Each sample is
associated with one of these task vectors, sampled uniformly from the set
$\left\\{w_{i}\right\\}_{1\leq i\leq k}$. In our analysis, we shall assume
that $k$ divides $n$ and that each unique task vector is associated with
exactly $n/k$ input samples. (We note that this assumption merely serves to
simplify the notation. The asymptotic characterization of the random matrix
$G_{e}$ remains the same even without this assumption.) Observe that there are
only $k$ unique terms in the sum on the left-hand side of (SI.4.23). Thus,

$G_{e}\left(\frac{\tau}{k}\sum_{i\in[k]}\frac{1}{1+\chi(w_{i})}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}w_{i}^{\top}\otimes\begin{bmatrix}w_{i}^{\top}&1+\rho\end{bmatrix}\\\
\frac{1}{\sqrt{d}}w_{i}\otimes\begin{bmatrix}w_{i}\\\
1+\rho\end{bmatrix}&I_{d}\otimes
E(w_{i})\end{bmatrix}+\pi\Omega_{e}+\tau\lambda I\right)=I+\sum_{j\leq
4}\Delta_{j}.$ (SI.4.24)

So far, we have been treating the $k$ task vectors
$\left\\{w_{i}\right\\}_{i\in[k]}$ as fixed vectors, only using the randomness
in the input samples that are associated with the data vectors
$\left\\{x_{i}^{\mu}\right\\}$. To further simplify our asymptotic
characterization, we take advantage of the fact that
$\left\\{w_{i}\right\\}_{i\in[k]}$ are independently sampled from
$\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d}))$. To that end, we can first show
that $\chi(w_{i})$ in (SI.4.22) concentrates around its expectation.
Specifically,

$\chi(w_{i})=\mathbb{E}\left[\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}\right]_{\setminus
0}\cdot\left[I\otimes
E(w_{i})\right]\right)\right]+\mathcal{O}_{\prec}(d^{-1/2}).$ (SI.4.25)

By symmetry, we must have

$\mathbb{E}\left[\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}\right]_{\setminus
0}\cdot\left[I\otimes
E(w_{i})\right]\right)\right]=\mathbb{E}\left[\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}\right]_{\setminus
0}\cdot\left[I\otimes E(w_{j})\right]\right)\right]$ (SI.4.26)

for any $1\leq i<j\leq k$. It follows that
$\mathinner{\\!\left\lvert\chi(w_{i})-\chi(w_{j})\right\rvert}=\mathcal{O}_{\prec}(d^{-1/2})$,
and thus, by a union bound,

$\max_{i\in[k]}\,\mathinner{\\!\left\lvert\chi(w_{k_{1}})-\widehat{\chi}_{\mathrm{ave}}\right\rvert}=\mathcal{O}_{\prec}(d^{-1/2}),$
(SI.4.27)

where

$\widehat{\chi}_{\mathrm{ave}}\coloneqq\frac{1}{k}\sum_{i\in[k]}\chi(w_{i}).$
(SI.4.28)

Upon substituting (SI.4.22) into (SI.4.28), it is straightforward to verify
the following characterization of $\widehat{\chi}_{\mathrm{ave}}$:

$\widehat{\chi}_{\mathrm{ave}}=\frac{1}{d^{2}}\operatorname{tr}\left(\left[G_{e}\right]_{\setminus
0}\cdot\left[I\otimes E_{\mathrm{tr}}\right]\right).$ (SI.4.29)

The estimate in (SI.4.27) prompts us to replace the terms $\chi(w_{i})$ in the
right-hand side of (SI.4.24) by the common value
$\widehat{\chi}_{\mathrm{ave}}$. As before, we introduce a matrix $\Delta_{5}$
to capture the approximation error associated with this step. Using the newly
introduced notation $E_{\mathrm{tr}},b_{\mathrm{tr}}$ and $R_{\mathrm{tr}}$ in
(SI.4.3) and (SI.4.1), we can then simplify (SI.4.24) as

$\displaystyle
G_{e}\left(\frac{\tau}{1+\widehat{\chi}_{\mathrm{ave}}}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)^{\top}\\\
\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)&I_{d}\otimes
E_{\mathrm{tr}}\end{bmatrix}+\pi\Omega_{e}+\tau\lambda I\right)$ (SI.4.30)
$\displaystyle=I+\sum_{1\leq j\leq 5}\Delta_{j}.$

Define

$\widehat{\mathcal{G}}_{e}(\pi)\coloneqq\left(\frac{\tau}{1+\widehat{\chi}_{\mathrm{ave}}}\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)^{\top}\\\
\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)&I_{d}\otimes
E_{\mathrm{tr}}\end{bmatrix}+\pi\Omega_{e}+\tau\lambda I\right)^{-1}.$
(SI.4.31)

Then

$G_{e}=\widehat{\mathcal{G}}_{e}(\pi)+\underbrace{\widehat{\mathcal{G}}_{e}(\pi)\left(\Delta_{1}+\Delta_{2}+\Delta_{3}+\Delta_{4}+\Delta_{5}\right)}_{\text{approximation
errors}}.$ (SI.4.32)

######  Remark 5.

We claim that $\widehat{\mathcal{G}}_{e}$ is asymptotically equivalent to
$G_{e}$, in the sense of Definition 1. Given (SI.4.32), proving this claim
requires showing that, for $j=1,2,\ldots,5$,

$u^{\top}\left(\widehat{\mathcal{G}}_{e}(\pi)\Delta_{j}\right)v\simeq 0,$
(SI.4.33a)
$\frac{1}{\sqrt{d}}\begin{bmatrix}0&\operatorname{vec}(A_{\mathrm{tr}})^{\top}\end{bmatrix}\left(\widehat{\mathcal{G}}_{e}(\pi)\Delta_{j}\right)v\simeq
0,$ (SI.4.33b) and
$\frac{1}{d^{2}}\operatorname{tr}\left(\left[\widehat{\mathcal{G}}_{e}(\pi)\Delta_{j}\right]_{\setminus
0}\cdot\left[I\otimes E_{\mathrm{tr}}\right]\right)\simeq 0,$ (SI.4.33c)

for any deterministic and unit-norm vectors $u,v$ and for
$A_{\mathrm{tr}}=\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}$.

We note the equivalent matrix $\widehat{\mathcal{G}}_{e}(\pi)$ still involves
one scalar $\widehat{\chi}_{\mathrm{ave}}$ that depends on the original
resolvent $G_{e}(\pi)$. Next, we show that $\widehat{\chi}_{\mathrm{ave}}$ can
be replaced by $\chi_{\pi}$, the unique positive solution to (SI.4.7). To that
end, we recall the characterization in (SI.4.29). Using the claim that
$G_{e}(\pi)$ and $\widehat{\mathcal{G}}_{e}(\pi)$ are asymptotically
equivalent (in particular, in the sense of (SI.4.6)), we have

$\widehat{\chi}_{\mathrm{ave}}\simeq\frac{1}{d^{2}}\operatorname{tr}\left(\left[\widehat{\mathcal{G}}_{e}(\pi)\right]_{\setminus
0}\cdot\left[I\otimes E_{\mathrm{tr}}\right]\right).$ (SI.4.34)

To compute the first term on the right-hand side of the above estimate, we
directly invert the block matrix $\widehat{\mathcal{G}}_{e}(\pi)$ in
(SI.4.31). Recall that $\Omega_{e}$ is chosen in the forms of (SI.3.6) and
(SI.3.13). It is then straightforward to verify that

$\widehat{\mathcal{G}}_{e}=\begin{bmatrix}\bar{c}&-\bar{c}\,{\bar{q}}^{\top}\\\
-\bar{c}\,\bar{q}&I\otimes
F_{E}(\widehat{\chi}_{\mathrm{ave}})+\bar{c}\,\bar{q}{\bar{q}}^{\top}\end{bmatrix},$
(SI.4.35)

where $F_{E}(\chi)$ is a matrix valued function such that

$F_{E}(\chi)=\Big{(}\frac{\tau}{1+\chi}E_{\mathrm{tr}}+\pi B+\lambda\tau
I_{d+1}\Big{)}^{-1},$ (SI.4.36)
$\bar{q}=\frac{\tau}{(1+\widehat{\chi}_{\mathrm{ave}})\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\widehat{\chi}_{\mathrm{ave}})\right),$
(SI.4.37)

and

${1/}\bar{c}=\frac{\tau(1+\rho)}{1+\widehat{\chi}_{\mathrm{ave}}}+\lambda\tau-\frac{\tau^{2}}{(1+\widehat{\chi}_{\mathrm{ave}})^{2}d}\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\widehat{\chi}_{\mathrm{ave}})\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}^{\top}\right).$
(SI.4.38)

Using (SI.4.35), we can now write the equation (SI.4.34) as

$\displaystyle\widehat{\chi}_{\mathrm{ave}}$
$\displaystyle\simeq\frac{1}{d}\operatorname{tr}\left(F_{E}(\widehat{\chi}_{\mathrm{ave}})E_{\mathrm{tr}}\right)$
(SI.4.39)
$\displaystyle\quad+\frac{\bar{c}\,\tau^{2}}{(1+\widehat{\chi}_{\mathrm{ave}})^{2}d^{3}}\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\widehat{\chi}_{\mathrm{ave}})E_{\mathrm{tr}}F_{E}(\widehat{\chi}_{\mathrm{ave}})\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}^{\top}\right).$

The second term on the right-hand side of (SI.4.39) is negligible. Indeed,

$\displaystyle\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\widehat{\chi}_{\mathrm{ave}})E_{\mathrm{tr}}F_{E}(\widehat{\chi}_{\mathrm{ave}})\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}^{\top}\right)$
(SI.4.40) $\displaystyle\qquad\qquad\qquad\leq\mathinner{\\!\left\lVert
F_{E}(\widehat{\chi}_{\mathrm{ave}})E_{\mathrm{tr}}F_{E}(\widehat{\chi}_{\mathrm{ave}})\right\rVert}_{\mathsf{op}}(\,\mathinner{\\!\left\lVert
R_{\mathrm{tr}}\right\rVert}_{\mathsf{F}}^{2}+(1+\rho)^{2}\mathinner{\\!\left\lVert
b_{\mathrm{tr}}\right\rVert}^{2}).$

By construction, $\mathinner{\\!\left\lVert
F_{E}(\widehat{\chi}_{\mathrm{ave}})\right\rVert}_{\mathsf{op}}\leq(\lambda\tau)^{-1}$.
Moreover, since the task vectors $\left\\{w_{i}\right\\}_{i\in[k]}$ are
independent vectors sampled from $\mathsf{Unif}(\mathcal{S}^{d-1}(\sqrt{d}))$,
it is easy to verify that

$\mathinner{\\!\left\lVert
E_{\mathrm{tr}}\right\rVert}_{\mathsf{op}}=\mathcal{O}_{\prec}(1),\qquad\mathinner{\\!\left\lVert
R_{\mathrm{tr}}\right\rVert}_{\mathsf{F}}=\mathcal{O}_{\prec}(\sqrt{d})\qquad\text{and}\qquad\mathinner{\\!\left\lVert
b_{\mathrm{tr}}\right\rVert}_{2}=\mathcal{O}_{\prec}(1).$ (SI.4.41)

Finally, since $\bar{c}$ is an element of $\widehat{\mathcal{G}}_{e}$, we must
have
$\mathinner{\\!\left\lvert\bar{c}\right\rvert}\leq\mathinner{\\!\left\lVert\widehat{\mathcal{G}}_{e}\right\rVert}_{\mathsf{op}}\leq(\tau\lambda)^{-1}$.
Combining these estimates gives us

$\frac{\bar{c}\,\tau^{2}}{(1+\widehat{\chi}_{\mathrm{ave}})^{2}d^{3}}\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\widehat{\chi}_{\mathrm{ave}})E_{\mathrm{tr}}F_{E}(\widehat{\chi}_{\mathrm{ave}})\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}^{\top}\right)=\mathcal{O}_{\prec}(d^{-2}),$
(SI.4.42)

and thus we can simplify (SI.4.39) as

$\widehat{\chi}_{\mathrm{ave}}\simeq\frac{1}{d}\operatorname{tr}\left[\Big{(}\frac{\tau}{1+\widehat{\chi}_{\mathrm{ave}}}E_{\mathrm{tr}}+\pi
B+\lambda\tau I_{d}\Big{)}^{-1}E_{\mathrm{tr}}\right].$ (SI.4.43)

Observe that (SI.4.43) is a small perturbation of the self-consistent equation
in (SI.4.7). By the stability of the equation (SI.4.7), we then have

$\widehat{\chi}_{\mathrm{ave}}\simeq\chi_{\pi},$ (SI.4.44)

where $\chi_{\pi}$ is the unique positive solution to (SI.4.7).

Recall the definitions of $\mathcal{G}_{e}(\pi)$ and
$\widehat{\mathcal{G}}_{e}(\pi)$ in (SI.4.31) and (SI.4.8), respectively. By
the standard resolvent identity,

$\displaystyle\widehat{\mathcal{G}}_{e}(\pi)-\mathcal{G}_{e}(\pi)$ (SI.4.45)
$\displaystyle=\frac{\tau[\widehat{\chi}_{\mathrm{ave}}-\chi_{\pi}]}{[1+\chi_{\pi}][1+\widehat{\chi}_{\mathrm{ave}}]}\widehat{\mathcal{G}}_{e}(\pi)\begin{bmatrix}1+\rho&\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)^{\top}\\\
\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)&I_{d}\otimes
E_{\mathrm{tr}}\end{bmatrix}\mathcal{G}_{e}(\pi).$

By construction,
$\mathinner{\\!\left\lVert\widehat{\mathcal{G}}_{e}(\pi)\right\rVert}_{\mathsf{op}}\leq
1/(\tau\lambda)$ and
$\mathinner{\\!\left\lVert\mathcal{G}_{e}(\pi)\right\rVert}_{\mathsf{op}}\leq
1/(\tau\lambda)$. Moreover, $\mathinner{\\!\left\lVert
E_{\mathrm{tr}}\right\rVert}_{\mathsf{op}}\prec 1$ and

$\mathinner{\\!\left\lVert\frac{1}{\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}\right)\right\rVert}\prec
1.$ (SI.4.46)

It then follows from (SI.4.44) and (SI.4.45) that

$\mathinner{\\!\left\lVert\widehat{\mathcal{G}}_{e}(\pi)-\mathcal{G}_{e}(\pi)\right\rVert}_{\mathsf{op}}\simeq
0.$ (SI.4.47)

If $\widehat{\mathcal{G}}_{e}(\pi)$ satisfies the equivalent conditions
(SI.4.4), (SI.4.5) and (SI.4.6) (as claimed in our analysis above), then the
estimate in (SI.4.47) allows us to easily check that $\mathcal{G}_{e}(\pi)$
also satisfies (SI.4.4), (SI.4.5) and (SI.4.6). Thus, we claim that
$\mathcal{G}_{e}(\pi)$ is asymptotically equivalent to the extended resolvent
matrix $G_{e}(\pi)$ in the sense of Definition 1.

##  SI.5 Asymptotic Limits of the Generalization Errors

In this section, we use the characterization in Result 3 to derive the
asymptotic limits of the generalization errors of associated with the set of
parameters $\Gamma^{\ast}$ learned from ridge regression.

###  SI.5.1 Asymptotic Limits of the Linear and Quadratic Terms

From Corollary 1 and the discussions in Remark 2, characterizing the test
error $e(\Gamma^{\ast})$ boils down to computing the linear term
$\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}A_{\mathrm{test}}^{\top}\right)$
and the quadratic term
$\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}B_{\mathrm{test}}(\Gamma^{\ast})^{\top}\right)$,
where $A_{\mathrm{test}}$ and $B_{\mathrm{test}}$ are the matrices defined in
(SI.2.23) and (SI.2.24), respectively.

We consider two different types of test data distributions
$\mathcal{P}_{\mathrm{test}}$: ICL and IDG. [See Section 2.6 in the main text
for details.] From (SI.2.16) and (SI.2.17), these two settings correspond to
choosing

$\text{(ICL)}\mathrel{\mathop{\mathchar 58\relax}}\qquad
A_{\mathrm{test}}=\begin{bmatrix}I_{d}&0\end{bmatrix}\quad\text{and}\quad
B_{\mathrm{test}}=\begin{bmatrix}(\frac{1+\rho}{\alpha}+1)I_{d}&\\\
&(1+\rho)^{2}\end{bmatrix}.$ (SI.5.1)

and

$\text{(IDG)}\mathrel{\mathop{\mathchar 58\relax}}\qquad
A_{\mathrm{test}}=A_{\mathrm{tr}}\quad\text{and}\quad
B_{\mathrm{test}}=E_{\mathrm{tr}},$ (SI.5.2)

respectively. In (SI.5.2), $A_{\mathrm{tr}}$ and $E_{\mathrm{tr}}$ are the
matrices defined in (SI.4.2) and (SI.4.3).

######  Result 4.

Let $\Gamma^{\ast}$ be the set of parameters learned from the ridge regression
problem in (19). Let $A_{\mathrm{test}}\in\mathbb{R}^{d\times(d+1)}$ and
$B_{\mathrm{test}}\in\mathbb{R}^{(d+1)\times(d+1)}$ be two matrices
constructed as in (SI.5.1) or (SI.5.2). We have

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}A_{\mathrm{test}}^{\top})\simeq\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}_{\mathrm{eq}}A_{\mathrm{test}}^{\top}\right),$
(SI.5.3)

and

$\displaystyle\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}B_{\mathrm{test}}(\Gamma^{\ast})^{\top})\simeq\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}B_{\mathrm{test}}(\Gamma^{\ast}_{\mathrm{eq}})^{T})-\frac{c_{e}}{d}\operatorname{tr}\left(B_{\mathrm{test}}\left[(E_{\mathrm{tr}}+\xi
I)^{-1}-\xi(E_{\mathrm{tr}}+\xi I)^{-2}\right]\right).$ (SI.5.4)

In the above displays, $\Gamma^{\ast}_{\mathrm{eq}}$ is an asymptotic
equivalent of $\Gamma^{\ast}$, defined as

$\displaystyle\Gamma^{\ast}_{\mathrm{eq}}$
$\displaystyle\coloneqq\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}(E_{\mathrm{tr}}+\xi
I)^{-1},$ (SI.5.5)

where $\xi$ is the unique positive solution to the self-consistent equation

$\xi\mathcal{M}_{\kappa}\left(\frac{1+\rho}{\alpha}+\xi\right)-\frac{\tau\lambda}{\xi}=1-\tau,$
(SI.5.6)

and $\mathcal{M}_{\kappa}(\cdot)$ is the function defined in (B.3). Moreover,
the scalar $c_{e}$ in (SI.5.4) is defined as

$c_{e}=\frac{\rho+\nu-\nu^{2}\mathcal{M}_{\kappa}(\nu)-\xi\left[1-2\nu\mathcal{M}_{\kappa}(\nu)-\nu^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)\right]}{1-{2\xi}\mathcal{M}_{\kappa}(\nu)-\xi^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)-\tau},$
(SI.5.7)

where

$\nu\coloneqq\frac{1+\rho}{\alpha}+\xi.$ (SI.5.8)

To derive the asymptotic characterizations (SI.5.3) and (SI.5.4) in Result 4,
we first use block-matrix inversion to rewrite $\mathcal{G}_{e}(\pi)$ in
(SI.4.8) as

${\mathcal{G}}_{e}(\pi)=\begin{bmatrix}c^{\ast}(\pi)&-c^{\ast}(\pi)\,(q^{\ast}(\pi))^{\top}\\\
-c^{\ast}(\pi)\,q^{\ast}(\pi)&I\otimes
F_{E}(\chi_{\pi})+c^{\ast}(\pi)q^{\ast}(\pi)(q^{\ast}(\pi))^{\top}\end{bmatrix},$
(SI.5.9)

where $F_{E}(\cdot)$ is the matrix-valued function defined in (SI.4.36),
_i.e._ ,

$F_{E}(\chi_{\pi})=\Big{(}\frac{\tau}{1+\chi_{\pi}}E_{\mathrm{tr}}+\pi
B_{\mathrm{test}}+\lambda\tau I_{d+1}\Big{)}^{-1}.$ (SI.5.10)

Moreover,

$q^{\ast}(\pi)=\frac{\tau}{(1+\chi_{\pi})\sqrt{d}}\operatorname{vec}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\chi_{\pi})\right),$
(SI.5.11)

and

$\frac{1}{c^{\ast}(\pi)}=\frac{\tau(1+\rho)}{1+\chi_{\pi}}+\lambda\tau-\frac{\tau^{2}}{(1+\chi_{\pi})^{2}d}\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}F_{E}(\chi_{\pi})\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}^{\top}\right).$
(SI.5.12)

Observe that there is a one-to-one correspondence between the terms in
(SI.5.9) and those in (SI.3.8).

To derive the asymptotic characterization given in (SI.5.3), we note that

$\displaystyle\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}A_{\mathrm{test}}^{\top})$
$\displaystyle\simeq\frac{-1}{c(0)\sqrt{d}}\begin{bmatrix}0&\operatorname{vec}(A_{\mathrm{test}})^{T}\end{bmatrix}\mathcal{G}_{e}(0)e_{1}$
(SI.5.13)
$\displaystyle=\frac{c^{\ast}(0)}{c(0)}\cdot\frac{1}{d}\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}(E_{\mathrm{tr}}+\lambda(1+\chi_{0})I)^{-1}A_{\mathrm{test}}^{\top}\right)$
(SI.5.14)
$\displaystyle\simeq\frac{1}{d}\operatorname{tr}\left(\begin{bmatrix}R_{\mathrm{tr}}&(1+\rho)b_{\mathrm{tr}}\end{bmatrix}(E_{\mathrm{tr}}+\lambda(1+\chi_{0})I)^{-1}A_{\mathrm{test}}^{\top}\right).$
(SI.5.15)

In the above display, (SI.5.13) follows from (SI.3.12) and the asymptotic
equivalence between $G_{e}(0)$ and $\mathcal{G}_{e}(0)$. The equality in
(SI.5.14) is due to (SI.5.9) and (SI.5.11). To reach (SI.5.15), we note that
$c(0)=e_{1}^{\top}G_{e}(0)e_{1}$ and
$c^{\ast}(0)=e_{1}^{\top}\mathcal{G}_{e}(0)e_{1}$. Thus, $c(0)\simeq
c^{\ast}(0)$ due to the asymptotic equivalence between $G_{e}(0)$ and
$\mathcal{G}_{e}(0)$. In Appendix B, we show that

$\lambda(1+\chi_{0})\simeq\xi,$ (SI.5.16)

where $\xi$ is the scalar defined in (SI.5.6). The asymptotic characterization
given in (SI.5.3) then follows from (SI.5.15) and from the definition of
$\Gamma^{\ast}_{\mathrm{eq}}$ given in (SI.5.5).

Next, we use (SI.3.14) to derive the asymptotic characterization of the
quadratic term in (SI.5.4). Taking the derivative of (SI.5.12) gives us

$\displaystyle\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c^{\ast}(\pi)}\right)\biggr{|}_{\pi=0}=\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}B_{\mathrm{test}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top})$
$\displaystyle\qquad-\frac{\tau\chi^{\prime}_{0}}{(1+\chi_{0})^{2}}\left(1+\rho-\frac{2}{d}\operatorname{tr}(A_{\mathrm{tr}}(E_{\mathrm{tr}}+\xi
I)^{-1}A_{\mathrm{tr}}^{T})+\frac{1}{d}\operatorname{tr}(A_{\mathrm{tr}}(E_{\mathrm{tr}}+\xi
I)^{-1}E_{\mathrm{tr}}(E_{\mathrm{tr}}+\xi I)^{-1}A_{\mathrm{tr}}^{T})\right)$
(SI.5.17)
$\displaystyle=\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}B_{\mathrm{test}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top})-\frac{\tau\chi^{\prime}_{0}}{(1+\chi_{0})^{2}}\left(1+\rho-\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}A_{\mathrm{tr}}^{T})-\frac{\xi}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top})\right),$
(SI.5.18)

where $A_{\mathrm{tr}}$ is the matrix defined in (SI.4.2). In reaching the
above expression, we have also used the estimate in (SI.5.16).

To further simplify our formula, we note that

$A_{\mathrm{tr}}=S\left(E_{\mathrm{tr}}+\xi
I_{d+1}-\Big{(}\frac{1+\rho}{\alpha}+\xi\Big{)}I_{d+1}\right),$ (SI.5.19)

where $S$ is a $d\times(d+1)$ matrix obtained by removing the last row of
$I_{d+1}$. Using this identity, we can rewrite the matrix
$\Gamma^{\ast}_{\mathrm{eq}}$ in (SI.5.5) as

$\displaystyle\Gamma^{\ast}_{\mathrm{eq}}$
$\displaystyle=S\left(I-\Big{(}\frac{1+\rho}{\alpha}+\xi\Big{)}(E_{\mathrm{tr}}+\xi
I)^{-1}\right)$ (SI.5.20) $\displaystyle=\begin{bmatrix}I-\nu
F_{R}(\nu)-a^{\ast}(1+\rho)^{2}\nu
F_{R}(\nu)b_{\mathrm{tr}}b_{\mathrm{tr}}^{\top}F_{R}(\nu)&a^{\ast}(1+\rho)\nu
F_{R}(\nu)b_{\mathrm{tr}}\end{bmatrix},$ (SI.5.21)

where $F_{R}(\cdot)$ is the function defined in (B.1), and $\nu$ is the
parameter given in (SI.5.8). The second equality (SI.5.21) is obtained from
the explicit formula for $(E_{\mathrm{tr}}+\xi I)^{-1}$ in (B.7).

From (SI.5.19) and (SI.5.20), it is straightforward to check that

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}A_{\mathrm{tr}}^{T})=1-\nu+\nu^{2}\frac{1}{d}\operatorname{tr}(S(E_{\mathrm{tr}}+\xi
I)^{-1}S^{\top}),$ (SI.5.22)

and

$\frac{\xi}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top})=\xi\left[1-2\nu\frac{1}{d}\operatorname{tr}(S(E_{\mathrm{tr}}+\xi
I)^{-1}S^{\top})+\nu^{2}\frac{1}{d}\operatorname{tr}(S(E_{\mathrm{tr}}+\xi
I)^{-2}S^{\top}\right].$ (SI.5.23)

By using the asymptotic characterizations given in (B.19) and (B.20), we then
have

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}A_{\mathrm{tr}}^{T})\simeq
1-\nu+\nu^{2}\mathcal{M}_{\kappa}(\nu),$ (SI.5.24)

and

$\frac{\xi}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top})\simeq\xi\left[1-2\nu\mathcal{M}_{\kappa}(\nu)-\nu^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)\right].$
(SI.5.25)

Substituting (SI.5.24), (SI.5.25), and (B.21) into (SI.5.18) yields

$\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c^{\ast}(\pi)}\right)\biggr{|}_{\pi=0}\simeq\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}B_{\mathrm{test}}(\Gamma^{\ast}_{\mathrm{eq}})^{T})-\frac{c_{e}}{d}\operatorname{tr}\left(B_{\mathrm{test}}\left[(E_{\mathrm{tr}}+\xi
I)^{-1}-\xi(E_{\mathrm{tr}}+\xi I)^{-2}\right]\right),$ (SI.5.26)

where $c_{e}$ is the scalar defined in (SI.5.7). The asymptotic
characterization of the quadratic term in (SI.5.4) then follows from (SI.3.14)
and the claim that

$\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c(\pi)}\right)\biggr{|}_{\pi=0}\simeq\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\pi}\left(\frac{1}{c^{\ast}(\pi)}\right)\biggr{|}_{\pi=0}.$
(SI.5.27)

###  SI.5.2 The Generalization Error of In-Context Learning

######  Result 5.

Consider the test distribution $\mathcal{P}_{\mathrm{test}}$ associated with
the ICL task. We have

$e(\Gamma^{\ast})\simeq e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda),$
(SI.5.28)

where

$\displaystyle e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda)$
$\displaystyle\coloneqq\left(\frac{1+\rho}{\alpha}+1\right)\left(1-2\nu\mathcal{M}_{\kappa}(\nu)-\nu^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)-c_{e}\left[\mathcal{M}_{\kappa}(\nu)+\xi\mathcal{M}^{\prime}_{\kappa}(\nu)\right]\right)$
(SI.5.29)
$\displaystyle\qquad\qquad\qquad-2\left[1-\nu\mathcal{M}_{\kappa}(\nu)\right]+1+\rho,$

and $c_{e}$ is the constant given in (SI.5.7).

######  Remark 6.

Recall the definition of the asymptotic equivalence notation “$\simeq$”
introduced in Section SI.1. The characterization given in (SI.5.28) implies
that, as $d\to\infty$, the generalization error $e(\Gamma^{\ast})$ converges
almost surely to the deterministic quantity
$e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda)$.

To derive (SI.5.28), our starting point is the estimate

$e(\Gamma^{\ast})\simeq\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}B_{\mathrm{test}}(\Gamma^{\ast})^{\top}\right)-\frac{2}{d}\operatorname{tr}\left(\Gamma^{\ast}A_{\mathrm{test}}^{\top}\right)+1+\rho,$
(SI.5.30)

which follows from Corollary 1 and the discussions in Remark 2. We consider
the ICL task here, and thus $A_{\mathrm{test}}$ and $B_{\mathrm{test}}$ are
given in (SI.5.1). The asymptotic limits of the first two terms on the right-
hand side of the above equation can be obtained by the characterizations given
in Result 4.

Using (SI.5.3) and the expressions in (SI.5.21) and (SI.5.1), we have

$\displaystyle\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}A_{\mathrm{test}}^{\top})$
$\displaystyle\simeq\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}_{\mathrm{eq}}A_{\mathrm{test}}^{\top}\right)$
(SI.5.31)
$\displaystyle=1-\frac{\nu}{d}\operatorname{tr}F_{R}(\nu)-a^{\ast}(1+\rho)^{2}\nu\frac{\mathinner{\\!\left\lVert
F_{R}(\nu)b_{\mathrm{tr}}\right\rVert}^{2}}{d}$ (SI.5.32) $\displaystyle\simeq
1-\nu\mathcal{M}_{\kappa}(\nu),$ (SI.5.33)

where $\nu$ is the constant defined in (SI.5.8). To reach the last step, we
have used the estimate given in (B.19).

Next, we use (SI.5.4) to characterize the first term on the right-hand side of
(SI.5.30). From the formulas in (SI.5.21) and (SI.5.1), we can check that

$\displaystyle\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}_{\mathrm{eq}}B_{\mathrm{test}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top}\right)$
$\displaystyle\simeq\left(\frac{1+\rho}{\alpha}+1\right)\frac{1}{d}\operatorname{tr}\left(I-\nu
F(\nu)\right)^{2}$ (SI.5.34)
$\displaystyle\simeq\left(\frac{1+\rho}{\alpha}+1\right)\left(1-2\nu\mathcal{M}_{\kappa}(\nu)-\nu^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)\right),$
(SI.5.35)

where the second step follows from (B.19) and (B.20). From (B.7),

$\frac{1}{d}\operatorname{tr}(B_{\mathrm{test}}(E_{\mathrm{tr}}+\xi
I)^{-1})\simeq\left(\frac{1+\rho}{\alpha}+1\right)\frac{1}{d}\operatorname{tr}F_{R}(\nu)\simeq\left(\frac{1+\rho}{\alpha}+1\right)\mathcal{M}_{\kappa}(\nu).$
(SI.5.36)

Similarly, we can check that

$\frac{1}{d}\operatorname{tr}(B_{\mathrm{test}}(E_{\mathrm{tr}}+\xi
I)^{-2})\simeq\left(\frac{1+\rho}{\alpha}+1\right)\frac{1}{d}\operatorname{tr}F^{2}_{R}(\nu)\simeq-\left(\frac{1+\rho}{\alpha}+1\right)\mathcal{M}^{\prime}_{\kappa}(\nu).$
(SI.5.37)

Substituting (SI.5.35), (SI.5.36), and (SI.5.37) into (SI.5.4) gives us

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}B(\Gamma^{\ast})^{\top})\simeq\left(\frac{1+\rho}{\alpha}+1\right)\left(1-2\nu\mathcal{M}_{\kappa}(\nu)-\nu^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)-c_{e}\left[\mathcal{M}_{\kappa}(\nu)+\xi\mathcal{M}^{\prime}_{\kappa}(\nu)\right]\right),$
(SI.5.38)

where $c_{e}$ is the constant given in (SI.5.7). Combining (SI.5.33),
(SI.5.38), and (SI.5.30), we are done.

In what follows, we further simplify the characterizations in Result 5 by
considering the ridgeless limit, _i.e._ , when $\lambda\to 0^{+}$.

######  Result 6.

Let

$q^{\ast}\coloneqq\frac{1+\rho}{\alpha},\qquad
m^{\ast}\coloneqq\mathcal{M}_{\kappa}\left({q^{\ast}}\right),\qquad\text{and}\qquad\mu^{\ast}\coloneqq
q^{\ast}\mathcal{M}_{\kappa/\tau}(q^{\ast}),$ (SI.5.39)

where $\mathcal{M}_{\kappa}(x)$ is the function defined in (B.3). Then

$\displaystyle e^{\mathrm{ICL}}_{\mathrm{ridgeless}}\coloneqq\lim_{\lambda\to
0^{+}}e^{\mathrm{ICL}}(\tau,\alpha,\kappa,\rho,\lambda)$ (SI.5.40)
$\displaystyle=\begin{cases}{\frac{\tau(1+q^{\ast})}{1-\tau}\left[1-\tau(1-\mu^{\ast})^{2}+\mu^{\ast}(\rho/q^{\ast}-1)\right]}{-2\tau(1-\mu^{\ast})+(1+\rho)}&\quad\tau<1\\\
\left(q^{\ast}+1\right)\left(1-2q^{\ast}m^{\ast}-(q^{\ast})^{2}\mathcal{M}^{\prime}_{\kappa}(q^{\ast})+\frac{(\rho+q^{\ast}-(q^{\ast})^{2}m^{\ast})m^{\ast}}{\tau-1}\right)-2(1-q^{\ast}m^{\ast})+(1+\rho)&\quad\tau>1\end{cases},$

where $\mathcal{M}^{\prime}_{\kappa}(\cdot)$ denotes the derivative of
$\mathcal{M}_{\kappa}(x)$ with respect to $x$.

We start with the case of $\tau<1$. Examining the self-consistent equation in
(SI.5.6), we can see that the parameter $\xi$ tends to a nonzero constant,
denoted by $\xi^{\ast}$, as $\lambda\to 0^{+}$. It follows that the original
equation in (SI.5.6) reduces to

${\xi^{\ast}}\mathcal{M}_{\kappa}\left(\frac{1+\rho}{\alpha}+\xi^{\ast}\right)=1-\tau.$
(SI.5.41)

Introduce a change of variables

$\mu^{\ast}\coloneqq\frac{(1-\tau)(1+\rho)}{\alpha\tau\xi^{\ast}}.$ (SI.5.42)

By combining (SI.5.41) and the characterization in (B.4), we can directly
solve for $\mu$ and get
$\mu^{\ast}=q^{\ast}\mathcal{M}_{\kappa/\tau}(q^{\ast})$ as given in
(SI.5.39). The characterization in (SI.5.40) (for the case of $\tau<1$) then
directly follows from (SI.5.33), (SI.5.38), and (4) after some lengthy
calculations.

Next, we consider the case of $\tau>1$. It is straightforward to verify from
(SI.5.6) that

$\xi=\frac{\tau}{\tau-1}\lambda+\mathcal{O}(\lambda^{2}).$ (SI.5.43)

Thus, when $\tau>1$, $\xi\to 0$ as $\lambda\to 0^{+}$. It follows that

$\lim_{\lambda\to 0^{+}}\nu=\lim_{\lambda\to
0^{+}}\left(\frac{1+\rho}{\alpha}+\xi\right)=q^{\ast}\quad\text{and}\quad\lim_{\lambda\to
0^{+}}\mathcal{M}_{\kappa}(\nu)=m^{\ast}.$ (SI.5.44)

Substituting these estimates into (SI.5.33), (SI.5.38), and (4), we then reach
the characterizations in (SI.5.40) for the case of $\tau>1$.

###  SI.5.3 The Generalization Error of In-Distribution Generalization

In what follows, we derive the asymptotic limit of the generalization error
for the IDG task.

######  Result 7.

Consider the test distribution $\mathcal{P}_{\mathrm{test}}$ associated with
the IDG task. We have

$e(\Gamma^{\ast})\simeq
e^{\mathrm{IDG}}(\tau,\alpha,\kappa,\rho,\lambda)\coloneqq\tau\frac{\rho+\nu-\nu^{2}\mathcal{M}_{\kappa}(\nu)-\xi\left[1-{2\nu}\mathcal{M}_{\kappa}(\nu)-{\nu^{2}}\mathcal{M}^{\prime}_{\kappa}(\nu)\right]}{\tau-\left[1-{2\xi}\mathcal{M}_{\kappa}(\nu)-\xi^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)\right]},$
(SI.5.45)

where $\xi$ the unique positive solution to the self-consistent equation
(SI.5.6) and $\nu$ is the constant given in (SI.5.8).

Similar to our derivation of Result 5, we only need to use (SI.5.3) and
(SI.5.4) to characterize the asymptotic limits of the first and second terms
on the right-hand side of (SI.5.30). Note that, for the IDG task,
$A_{\mathrm{test}}=A_{\mathrm{tr}}$. It follows from (SI.5.3) and (SI.5.24)
that

$\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}A_{\mathrm{test}}^{\top})\simeq
1-\nu+\nu^{2}\mathcal{M}_{\kappa}(\nu).$ (SI.5.46)

Similarly, since $B_{\mathrm{test}}=E_{\mathrm{tr}}$, we can verify from
(SI.5.5) that

$\displaystyle\frac{1}{d}\operatorname{tr}\left(\Gamma^{\ast}_{\mathrm{eq}}B_{\mathrm{test}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top}\right)$
$\displaystyle=\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}A_{\mathrm{tr}}^{\top})-\frac{\xi}{d}\operatorname{tr}(\Gamma^{\ast}_{\mathrm{eq}}(\Gamma^{\ast}_{\mathrm{eq}})^{\top})$
(SI.5.47) $\displaystyle\simeq
1-\nu+\nu^{2}\mathcal{M}_{\kappa}(\nu)-\xi\left[1-2\nu\mathcal{M}_{\kappa}(\nu)-\nu^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)\right],$
(SI.5.48)

where the second step follows from (SI.5.24) and (SI.5.25). Moreover,

$\frac{1}{d}\operatorname{tr}\left(B_{\mathrm{test}}\left[(E_{\mathrm{tr}}+\xi
I)^{-1}-\xi(E_{\mathrm{tr}}+\xi
I)^{-2}\right]\right)=1-2\xi\mathcal{M}_{\kappa}(\nu)-\xi^{2}\mathcal{M}^{\prime}_{\kappa}(\nu).$
(SI.5.49)

Substituting (SI.5.47) and (SI.5.49) into (SI.5.4), we have

$\displaystyle\frac{1}{d}\operatorname{tr}(\Gamma^{\ast}B(\Gamma^{\ast})^{\top})$
(SI.5.50) $\displaystyle\
\simeq\tau\frac{\rho+\nu-\nu^{2}\mathcal{M}_{\kappa}(\nu)-\xi\left[1-{2\nu}\mathcal{M}_{\kappa}(\nu)-{\nu^{2}}\mathcal{M}^{\prime}_{\kappa}(\nu)\right]}{\tau-\left[1-{2\xi}\mathcal{M}_{\kappa}(\nu)-\xi^{2}\mathcal{M}^{\prime}_{\kappa}(\nu)\right]}+2(1-\nu+\nu^{2}\mathcal{M}_{\kappa}(\nu))-(1+\rho).$

The final result in (SI.5.45) then follows from combining the above expression
with (SI.5.46) and (SI.5.30).

Finally, we derive the ridgeless limit of the characterization given in Result
7.

######  Result 8.

Let $q^{\ast}$, $m^{\ast}$, and $\mu^{\ast}$ be the scalars defined in
(SI.5.39). We have

$\displaystyle e^{\mathrm{IDG}}_{\mathrm{ridgeless}}$
$\displaystyle\coloneqq\lim_{\lambda\to
0^{+}}e^{\mathrm{IDG}}(\tau,\alpha,\kappa,\rho,\lambda)$ (SI.5.51)
$\displaystyle=\begin{cases}\frac{\tau}{1-\tau}\left(\frac{\rho+q^{\ast}-2q^{\ast}(1-\tau)({q^{\ast}}/{\xi^{\ast}}+1)}{1-p^{\ast}(1-\tau)}+\frac{\tau\mu^{\ast}(q^{\ast}+\xi^{\ast})^{2}}{q^{\ast}}\right)&\qquad\tau<1\\\
\frac{\tau}{\tau-1}[\rho+q^{\ast}(1-q^{\ast}m^{\ast})]&\qquad\tau>1\end{cases},$
(SI.5.52)

where $\xi^{\ast}=\frac{(1-\tau)q^{\ast}}{\tau\mu^{\ast}}$ and
$p^{\ast}=\big{(}1-{\kappa}\big{(}\frac{\kappa\xi^{\ast}}{1-\tau}+1\big{)}^{-2}\big{)}^{-1}$.

The derivation of this result closely follows that of Result 6. We analyze the
cases of $\tau<1$ and $\tau>1$ separately. For $\tau<1$, the equation in
(SI.5.6) simplifies to (SI.5.41) as $\lambda\to 0^{+}$. For $\tau>1$, $\xi$
approaches zero as $\lambda\to 0^{+}$. Substituting these estimates into
(SI.5.45) then yields (SI.5.52) after some detailed calculations.

##  Appendix A Equivalent Statistical Representations

In this appendix, we present an equivalent (but simplified) statistical model
for the regression vector $H_{Z}$ defined in (16). This statistically-
equivalent model will simplify the moment calculations in Section SI.2 and the
random matrix analysis in Section SI.4.

######  Lemma 3.

Let $w$ be a given task vector with $\mathinner{\\!\left\lVert
w\right\rVert}=\sqrt{d}$. Meanwhile, let $a\sim\mathcal{N}(0,1)$,
$s\sim\mathcal{N}(0,1)$, $\epsilon\sim\mathcal{N}(0,\rho)$ be three scalar
normal random variables, and $q\sim\mathcal{N}(0,I_{\ell-1})$,
$g\sim\mathcal{N}(0,I_{d-1})$, $u\sim\mathcal{N}(0,I_{d-1})$, and
$v_{\epsilon}\sim\mathcal{N}(0,\rho I_{\ell})$ be isotropic normal random
vectors. Moreover, $w$ and all of the above random variables are mutually
independent. We have the following equivalent statistical representation of
the pair $(H_{Z},y_{\ell+1})$:

$H_{Z}\overset{(d)}{=}(d/\ell)M_{w}\begin{bmatrix}s\\\
u\end{bmatrix}\begin{bmatrix}h^{\top}M_{w},&(a/\sqrt{d}+\theta_{\epsilon})^{2}/\sqrt{d}+\theta_{q}^{2}/\sqrt{d}\end{bmatrix},$
(A.1)

and

$y_{\ell+1}\overset{(d)}{=}s+\epsilon.$ (A.2)

In the above displays, $M_{w}$ denotes a _symmetric_ and _orthonormal_ matrix
such that

$(M_{w})e_{1}=\frac{w}{\mathinner{\\!\left\lVert w\right\rVert}},$ (A.3)

where $e_{1}$ denotes the first natural basis vector in $\mathbb{R}^{d}$;
$h\in\mathbb{R}^{d}$ is a vector defined as

$h\coloneqq\begin{bmatrix}\frac{{\theta_{\epsilon}}a}{\sqrt{d}}+\frac{a^{2}}{d}+\theta_{q}^{2}\\\
\big{[}(\theta_{\epsilon}+a/\sqrt{d})^{2}+\theta_{q}^{2}\big{]}^{1/2}{g}/{\sqrt{d}}\end{bmatrix};$
(A.4)

and $\theta_{\epsilon}$, $\theta_{q}$ are scalars such that

$\theta_{\epsilon}={\mathinner{\\!\left\lVert
v_{\epsilon}\right\rVert}}/{\sqrt{d}}\qquad\text{and}\qquad\theta_{q}=\mathinner{\\!\left\lVert
q\right\rVert}/\sqrt{d}.$ (A.5)

######  Remark 7.

For two random variables $A$ and $B$, the notation $A\overset{(d)}{=}B$
indicates that $A$ and $B$ have identical probability distributions. Note that
$A$ and $B$ can be either scalars [as in the case of (A.2)], or matrices of
matching dimensions [as in the case of (A.1)].

######  Remark 8.

A concrete construction of the symmetric and orthonormal matrix $M_{w}$
satisfying (A.3) can be based on the Householder transformation [54, 55, 56].

###### Proof.

Recall that the data vector $x_{\ell+1}$ is independent of the task vector
$w$. Then, by the rotational symmetry of the isotropic normal distribution, we
can rewrite

$x_{\ell+1}\overset{(d)}{=}\frac{1}{\sqrt{d}}M_{w}\begin{bmatrix}s\\\
u\end{bmatrix},$ (A.6)

where $s\sim\mathcal{N}(0,1)$ and $u\sim\mathcal{N}(0,I_{d-1})$ are two
independent normal random variables (vectors), and $M_{w}$ is the symmetric
orthonormal matrix specified in (A.3). Note that
$y_{\ell+1}=x_{\ell+1}^{\top}w+\epsilon$, with
$\epsilon\sim\mathcal{N}(0,\rho)$ denoting the noise. The representation in
(A.2) then follows immediately from (A.6) and the identity in (A.3).

To show (A.1), we first reparameterize the $d\times\ell$ Gaussian data matrix
$X$ as

$X=M_{w}\begin{bmatrix}a&q^{\top}\\\
p&U\end{bmatrix}M_{v_{\epsilon}}/\sqrt{d}.$ (A.7)

In the above display, $a\sim\mathcal{N}(0,1)$, $p\sim\mathcal{N}(0,I_{d-1})$,
$q\sim\mathcal{N}(0,I_{\ell-1})$; $U\in\mathbb{R}^{(d-1)\times(\ell-1)}$ is a
matrix with iid standard normal entries; and $M_{v_{\epsilon}}$ is a symmetric
orthonormal matrix such that

$M_{v_{\epsilon}}e_{1}=\frac{v_{\epsilon}}{\mathinner{\\!\left\lVert
v_{\epsilon}\right\rVert}},$ (A.8)

where $e_{1}$ denotes the first natural basis vector in $\mathbb{R}^{\ell}$.
Since the data matrix $X$, the task vector $w$, and the noise vector
$v_{\epsilon}$ are mutually independent, it is straightforward to verify via
the rotational symmetry of the isotropic normal distribution that both sides
of (A.7) have identical probability distributions. Using this new
representation, we have

$Xv_{\epsilon}=\theta_{\epsilon}M_{w}\begin{bmatrix}a\\\ p\end{bmatrix}.$
(A.9)

Meanwhile,

$X^{\top}w=M_{v_{\epsilon}}\begin{bmatrix}a\\\ q\end{bmatrix},$ (A.10)