Transformers are Minimax Optimal Nonparametric In-Context Learners
Authors: Juno Kim
Tai Nakamaki
Taiji Suzuki
Venue: NeurIPS 2024 poster (2024)
Keywords: in-context learning
transformers
nonparametric regression
minimax optimality
meta-learning
Primary area: learning_theory

Abstract: In-context learning (ICL) of large language models has proven to be a surprisingly effective method of learning a new task from only a few demonstrative examples. In this paper, we shed light on the efficacy of ICL from the viewpoint of statistical learning theory. We develop approximation and generalization error analyses for a transformer model composed of a deep neural network and one linear attention layer, pretrained on nonparametric regression tasks sampled from general function spaces including the Besov space and piecewise $\gamma$-smooth class. In particular, we show that sufficiently trained transformers can achieve -- and even improve upon -- the minimax optimal estimation risk in context by encoding the most relevant basis representations during pretraining. Our analysis extends to high-dimensional or sequential data and distinguishes the \emph{pretraining} and \emph{in-context} generalization gaps, establishing upper and lower bounds w.r.t. both the number of tasks and in-context examples. These findings shed light on the effectiveness of few-shot prompting and the roles of task diversity and representation learning for ICL.

Transformers are Minimax Optimal Nonparametric In-Context Learners
Juno Kim 1.2 Tai Nakamaki' Taiji Suzuki
Uniiversity of Tokyo Center for Advanced Intelligence Project, RIKEN "junokingg.ee ecc. succ.u-tee u-tokyo.ac. jp.
Abstract
In-context learning (ICL) large language models has proven to be surprisingly effective method of learning a new task from only a few demonstrative exam- ples. this paper, we study the efficacy of ICL from the viewpoint of statistical learning theory. We develop approximation and generalization error bounds for a transformer composed of a deep neural network and one linear attention layer, pretrained on nonparametric regression tasks sampled from general function spaces including the Besov space and piecewise y-smooth class. We show that sufficiently trained transformers can achieve and even improve upon the minimax optimal estimation risk in context by encoding the most relevant basis representations during pretraining. Our analysis extends to high- -igh-dimensional or sequential data and distinguishes the pretraining and in-context generalization gaps. Furthermore, establish information-the -hheoretic lower bounds for meta-learners w.r.t. both the number of tasks and in-context examples. These findings shed light on the roles task diversity and representation learning for ICL.
Introduction
Large language models (LLMs) have demonstrated remarkable capabilities in understanding and generating natural language data. In particular, the phenomenon in-context learning (ICL) has recently garnered widespread attention. ICL refers to the ability of pretrained LLMs perform new task by being provided with a few examples within the context of a prompt, without any parameter updates or fine-tuning. It has been empirically observed that few-shot prompting especially effective in large-scale models (Brown et al., 2020) and requires only a couple of examples to consistently achieve high performance (Gareía al., 2023). In contrast, Raventos al. (2023) demonstrate that sufficient pretraining task diversity is required for the emergence of ICL. However, we still lack comprehensive understanding of the statistical foundations of ICL and few-shot prompting.
vigorous line of research has been directed towards understanding ICL of single-layer linear attention models pretrained on the query prediction loss of linear regression tasks (Garg et al., 2022; Akyürek et al., 2023; Zhang et al., 2023; Ahn et al., 2023; Mahankali et al., 2023; Wu et al., 2024). It has been shown that the global minimizer of the L pretraining loss implements on a least-squares linear regression objective (Mahankali et al., 2023) and is nearly Bayes optimal (Wu et al., 2024). Moreover, risk bounds with respect the context length (Zhang al., 2023) and number of tasks (Wu et al., 2024) have been obtained.
step of GD
Other works have examined ICL of more complex multi-layer transformers. Bai et al. (2023); von Oswald et al. (2023) give specific transformer constructions which simulate GD in context, however is unclear how such meta-algorithms may be learned. Another approach is to study learning with representations, where tasks consist of a fixed nonlinear feature map composed with a varying linear function. Guo et al. (2023) empirically found that trained transformers exhibit separation where lower layers transform the input and upper layers perform linear ICL. Recently, Kim and Suzuki
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(2024) analyzed model consisting of a shallow neural network followed by linear attention layer and proved that the MLP component learns to encode the true features during pretraining. However, they assumed the infinite task and sample size limit and did not study generalization capabilities.
Our contributions. In this paper, we analyze the optimality of ICL from the perspective of statistical learning theory. Our object of study is transformer consisting of a deep neural network with N- dimensional output followed by one linear attention layer. The model pretrained on n input-output samples from I nonparametric regression tasks, generated from a suitably decaying distribution on a general function space. Compared to previous works, we take a crucial step towards understanding practical multi-layer transformers by incorporating the representation learning capabilities of the DNN module. From a more abstract perspective, this work can also be situated as a nonlinear extension of meta-learning. Our contributions are highlighted below.
We develop a general framework for upper bounding the in-context estimation error of the empirical risk minimizer in terms of the approximation error of the neural network and separate in-context and pretraining generalization gaps depending on n, 7', respectively.
In the Besov space setting, we show that ICL achieves nearly minimax optimal risk n 22 when T' is sufficiently large. Since LLMs are pretrained on vast amounts of data in practice, T can be taken to be nearly infinite, justifying the emergence ICL. at large scales. We extend the optimality guarantees to nearly dimension-free rates in the anisotropic Besov space and also to learning sequential data with deep transformers in the piecewise y-smooth function class.
We show that ICL can improve upon the priori optimal rate when the task class basis resides in a coarser Besov space by learning to encode informative basis representations, emphasizing the importance of pretraining on diverse tasks.
We also derive information-theoredt confirming that ICL is jointly optimal when T' is large (Besov space setting), while any meta- learning method is jointly suboptimal when T is small (coarser space setting). This separation aligns with empirical observations of task diversity threshold (Raventos et al., 2023).
lower bounds for the minimax risk in both n, T, rigorously
The paper is structured as follows. In Section 2, the regression tasks and transformer model are defined in an abstract setting. In Section 3, we present the general framework for estimating the ICL approximation and generalization error. In Section 4, we specialize to the Besov-type and piecewise -mmoohh class settings and show that transformers can achieve or exceed the minimax optimal rate in context. Section 5, we derive minimax lower bounds. All proofs are deferred to the appendix; moreover, we provide numerical experiments validating our results in Appendix E.
1.1 Other Related Works
Meta-learning, The theoretical setting of ICL is closely related meta-learning, where the goal is to infer a shared representation 3 with samples from set of transformed tasks 3, vo. When di is linear, fast rates have been established by Tripuraneni al. (2020); Du al. (2021), while the nonlinear case has been studied by Meunier et al. (2023) where 1o is feature projection into a reproducing kernel Hilbert space. Our results can be viewed as extending this body of work to function spaces of generalized smoothness with specific deep transformer architecture.
Optimal rates for DNNs. Our analysis extends established optimality results for classes of DNNs in ordinary supervised regression settings to ICL. Suzuki (2019) has shown that deep feedforward networks with the ReLU activation can efficiently approximate functions the Besov space and thus achieve the minimax optimal rate. This has been extended to the anisotropic Besov space (Suzuki and Nitanda, 2021), convolutional neural networks for infmnitediimensional input (Okumoto and Suzuki, 2022), and transformers for sequence-to-seqquecee functions (Takakura and Suzuki, 2023). We remark that a work in progress (Imaizumi, 2024) also studies the sample complexity of ICL of transformers in Sobolev space setting.
Pretraining dynamics for ICL. While how ICL arises from optimization is not fully understood, there are encouraging developments in this direction. Zhang et al. (2023) has shown for one layer of linear attention that running GD on the population risk always converges to the global optimum. This was extended to incorporate a linear output layer by Zhang et al. (2024), and to softmax attention

---

by Huang et al. (2023); Li et al. (2024); Chen et al. (2024). Kim and Suzuki (2024) considered a compound transformer equivalent to ours with shallow MLP component and proved that the loss landscape becomes benign in the mean-field limit, deriving convergence guarantees for the corresponding gradient dynamics. These analyses indicate that the attention mechanism, while highly nonconvex, may possess structures favorable for gradient-based optimization.
2 Problem Setup
2.1 Nonparametric Regression
In this paper, we analyze the ability of a transformer to solve nonparametric regression problems in context when pretrained on examples from a family of regression tasks, which we describe below. Let X' C R be the input space (d is allowed to be infinite), Px probability distribution X, and (1)) a fixed countable subset of (P A regression function F3 X' - IR is randomly generated for each task by sampling the sequence of coefficients 3 E IR" from a distribution Pa on (R 2 ); the class of tasks F is defined
j=1
F3 -ド= Pyvig] | E supp Ps).
endowed with the induced distribution. Each task prompt contains example input-response pairs {(2,, 1-- The covariates 2ạ are i.i.d. drawn from Px and the responses are generated as
yk F3 tk. 1sks n,
where the noise &x is assumed to be i.i.d. with mean zero and |&x| S almost surely. In addition. we independently generate a query token ã and corresponding output ÿ in the same manner.
We proceed to state assumptions for the regression model. Informally, we suppose relaxed version of sparsity and orthonormality of 2/द and suitable decay rates for the basis expansion. These will be subsequently verified for specific function spaces of interest with their natural decay rate. Assumption 1 (relaxed sparsity and orthonormality of basis functions). For N N, there exist inte- gers N < N & N with N N +1 = N such that N..... , are independent and ,f V are all contained in the linear span of " S- Moreover, there exist r. Ci, C2, Coo > 0 such
that Eg,N == (E (x) (x) JAN= satisfies C.IN = Ev.N I C2IN and
- (x9))
(Pxx) SC
1/2
Denoting the N-basis approximation of F3 as F A.N == Eド BBUs by Assumption 1 there exist
'aggregated' coefficients By,... .Bx uniquely determined by B such that F2.N E We define two types of coefficient covariance matrices
Σg, ;= (Epl3,8a)) E NxN and DJ.N (Eg13 N JA=N E NNN
Assumption (decay of (). For 8, B > it holds that |1881 S for all F3 E F and
F3 (1A(()) 2-2
(3)
uniformly over 3 E supp Pg. Furthermore, Tr(Eg,n) is bounded for all N and
0 < NN,N 3 diag [j (j-20-1(log) (log.) --
(4)
Remark 2.1. In the simple case where (1))²² is a basis for (2(Pxx), we may set N = 1, = N so that the dependency condition of Assumption is trivially satisfied, moreover, Σ3,N Σg,N and boundedness of Tr(Eg.N) automatically follows from (4). However, the assumptions in the stated form also allow for hierarchical bases with dependencies such as wavelet systems. We also note that (3) and (4) entail basically the same rate but are not equivalent: the uniform bound |3,12 S j--=0 2s 1---2-11- with any 9()) such that 1 (j) is convergent.
(log
along with Assumption implies (3). The (log.) term can be replaced
'This implies Var < o². We require boundedness since the values y form part of the prompt input, and we wish to utilize up-norm covering number estimates for the attention map: this technicality can be removed with more careful analysis. However, for the information wetooreticccereeieeeeoooe lower bound we assume Gaussian noise.

---

2.2 In-Context Learning
We now describe our transformer model, which takes n context pairs X = (x1 "'1,",,,,,)) ) E IRdxn
,,,)
= (yi,... ya) E R and a query token ă as input and returns a prediction for the corresponding first passed through a nonlinear representation or feature mapping é
output. The covariates X' --R* RN,, which we assume belongs to sufficiently powerful class of estimators FN. Specifically:
Assumption 3 (expressivity of FN). (lo(x))l2 S B'v for some B'v > foror all x E X, Φ FN. Moreover for some öN 0, there exist ON: 'N FN satisfying
max NSISN
33 (mx)) S 8N.
By choosing FN and åv to satisfy the above assumption, we will be able to utilize established approximation and generalization guarantees for families of deep neural networks in Section 4.
The extracted representations o(X) (Φ(x1), ... ((xx)) are then mapped to scalar output via linear attention layer parametrized by matrix I E SN for SN C CRNNN
Je(X, y, 3)
T (6T)
(()) where O (T, SNXFN.
n
Finally, the output is constrained lie on [B, by applying clip = maixmmnnuu B), B}. yielding fo (X, y, .) = clipg (fe (X, v.). We set SN = [T RNXN I = C3IN) } for some C3 > 0 and fix B = B for simplicity.
The above setup is restricted reparametrization of linear attention widely used in theoretical analyses (see e.g. Zhang et al., 2023; Wu et al., 2024, for more details), where the values only refer to y and the query and key matrices of GD with matrix step size and has been shown to be optimal for a single layer of linear attention for linear regression tasks (Ahn et al., 2023; Mahankali et al., 2023). The placement of the attention layer after the DNN module ò is justified by the observation that lower layers of trained transformers act as data representations top of which upper layers perform ICL (Guo al., 2023).
consolidated into matrix Г. The form is equivalent one step
During pretraining, the model is presented with T prompts {(X(), (y (()) where the tasks (v) (1) .... yn TT, T aa()) and g())
Fig E Fo, g00 Pa and tokens ( (a{²) : .... (x(2)) (0))
are independently generated as described Section 2.1, and is trained to minimize the empirical risk
T
+ arg min R(O)), R(O) = E - (0 ...0
BeSN xFx
Our goal is to verify the efficiency of ICL as learning algorithm and show that learning the optimal Ô allows the transformer to solve new random regression problems y F3 (z) + & for Fž E F in context. To this end, we evaluate the convergence of the mean-squared risk or estimation error,
@ px0 ( (o.,,.0.))).......
[R(O)] R(O)= Ex [( - fe y, =])
Note that we do not study whether the transformer always converges to θ the training dynamics of a DNN is already a very difficult problem. For the attention layer, see the discussion Section 1.1.
3 Risk Bounds for In-Context Learning
In this section, we outline our framework for analyzing the in-context estimation error R()). Some additional definitions are in order. The e-covering number (C,,, p, e) of a metric space C equipped with a metric for e > is defined as the minimal number of balls in p with radius c needed to cover C (van der Vaart and Wellner, 1996). The e-covering entropy ((F, p. == log N (F, c). The e-packing number M(e,C, C. is given as the maximal cardinality of e-separated set {e1,- ... CM C C such that p(c;, 0j) 2 8 for all i + j. The transformer model class is defined as TN == (Je θ E Sx x FN).
metric entropy is given as
To bound the overall risk, we first decompose into the approximation and generalization gaps.

---

Theorem 3.1 (Schmidt-Hieber Hieber (2020), Lemma 4, adapted), There exists universal constant C such that for any e such that V(TN N. 11 c) -
B² 1 T [)
R(()) S
inf GESNxFN
R(0)+O
(
Proof. The convergence rate of the empirical risk minimizer established for a fixed regression problem y (z) + Ç in Schmidt-Hieber (2020) when & is Gaussian; we modily the proof to incorporate bounded noise in Appendix B. The ICL setup can be reduced to the ordinary case as follows. We consider the entire batch (B, X, f1::: .) including the hidden coefficient 8 as a single datum 2 with output ÿ. The true function is given as (2) = (G) and the model class is taken to be TN implicitly concatenated with the generative process (3, X, Ei B) + (X, y: .). Then R(O), V(T N; ||-|| (==,)) and T agree with the ordinary 1 risk, model class entropy and sample size. L
Here, the second term is the pretraining generalization error dependent on the number of tasks T; the in-context generalization error dependent the prompt length manifests as part of the first term. This separation allows us to compare the relative difficulty of the two types of learning.
Bounding approximation error. In order to bound the first term, analyze the risk of the choice
- -T= (T*))"))= ((20..v + -2 (T"
N:N
where Ø² is given as Assumption for a suitable ōN to be determined. The definition approximately generalizes the global optimum I ((1 + ) + Li)(A)La) -1 for the Gaussian linear regression setup where x A), (Zhang et al., 2023). Since Eg.N M C1IN we have I' C IN and hence we may assume m E SN by replacing Css with C3 V CT if necessary.
Proposition 3.2. Under Assumptions 1-3, holds that
2 log N +
N4r
inf R(O)= I R(O*)= S 0E5
n log N + - + N + +
The proof is presented throughout Appendix A. The overall scheme is to approximate ( )) by its truncation 3 (z) and the finite basis N:N by &NNN. which incurs errors N-2s and the terms pertaining to 8N. respectively. The first three terms arise from the concentration of the n token representations v/e N:N (I&). All hidden constants are at most polynomial in problem parameters.
Bounding generalization error. To estimate the metric entropy of T N. first reduce to the metric entropy of the representation class FN. Here, I. refers to the essential supremum over the support of Px and also over all N components for FN. The proof is given in Appendix B.2.
Lemma 3.3. Under Assumptions 1-3, there exists D > O such that for all e sufficiently small,
B + + (FN.llllE,, ( N. I+ & 2 log
6
DB
4 Minimax Optimality of In-Context Learning
4.1 Besoy Space and DNNs
We now apply theory to study the sample complexity of ICL when FN consists of (clipped, (6)) deep neural networks. These can be also seen as simplified transformers with attention layers and skip connections removed. To be precise, define the set of DNNs with depth L, width W. sparsity S, norm bound M and ReLU activation 7)xx) = x V (applied element-wise) as
FUNN (L, W.S.M)
(Wil)) -B(L)) ...)....................... +
w
R Wxd
W
E IR WxW
1. (RL) E R. Σ
W E W 600 E R
| (1 S, max
M
13151
5

---

The Besov space is a very general class of functions including the Hölder and Sobolev spaces which captures spatial inhomogencity in smoothness, and provides natural setting in which to study the expressive power of deep neural networks (Suzuki, 2019). Here, we fix X = [0, 1] for simplicity. Definition 4.1 (Besov space). For 2 S p S 00,0 < q S oo, fractional smoothness > 0 and r= r= [La] + 1, the rth modulus of f E T.P(2)) is defined using the difference operator A h E I as Wr.p(f.t t) := Wldne و (f)pp, (T))(()) (z, Σj ()(-1)- jh).
Also, the Besov (quasi-)nont is given as |1-1la,, = 11-11lp + -1.B8,. where
(10 160 t (f. t)) 1/4
flB
9
(supiso to wr.(fttt
= 00
and the Besov space is defined as Bg. If L2()) |lffl for the unit ball in (bg.g(2)) 11-1l
oo}. We write U(Bg, (X))
We have that the Hölder space (*(X) = B (X) for order a > 0, N and the Sobolev space W (2)) 2 for E N well the embeddings Byy, (2) + W
(2) + po (X); if > d/p, Pp.g( (2') compactly embeds into the space of continuous functions on X. See Triebel (1983); Giné and Nickl (2015) for more details. The difficulty of learning a regression function in the Besov is quantified by the minimax risk; the following rate is classical.
Proposition 4.2 (Donoho and Johnstone (1998)). The minimax risk for an estimator Fn with i.i.d. samples D, = {(Ii, 31) == over U(B (X)) satisfies
inf P. R p (XI) Ep. Fa Falli
Zartd
natural basis system for (,,y())) is formed by the B-splines, which can be seen as a type of wavelet decomposition or multiresolution analysis (DeVore and Popov, 1988). As B-splines are piecewise polynomials, they can be efficiently approximated by DNNs with at most log depth (Suzuki, 2019). Definition 4.3 (B-spline wavelet basis). The tensor product B-spline of order e N satisfying m 1/p, at resolution l: E zá and location e E T - [ 2 is
d
dd (z) = II
4m (2hr 4;), where (m(()) = x x m+1
(x) = 111-1p (==(0.1]-
1=1
When 1 kd. we abuse notation and write whe for k E Zzo in place of w ((,..., ()).t"
4.2 Estimation Error Analysis
To apply our framework, we set the task class as the unit ball F = U(B (2)) and take as basis {15 j E N} [f, k Zzo. l E } the set of all B-spline wavelets ordered primarily by increasing k and scaled to counteract the dilation in Abusing notation, we also write 8x, to denote the coefficient in 3 corresponding 24d/2 The set of B-splines at each resolution are independent, while those of lower resolution can always be decomposed into a linear sum of B-splines of higher resolution satisfying certain decay rates, which we prove in Proposition C.10.
From this setup, in Appendix C.1.1, we verify Assumptions 1 and 2 with r = 1/2, = a/d under: d/p and Px has positive Lebesgue density px bounded above and below on X. Also, all coefficients 3x.s are independent and
Assumption 4. F U ((BB,,( (X)),
Es[Ba.e] 0,
Egl3.d S 1(20+d) k
Vk 00 2.0.E. E
(5)
We can check that we have not given ourselves an easier learning problem with (5): the assumed variance decay rate is tight (up to the logarithmic factor k: 22) in the sense that any ʃ E U(Bg,(()) can indeed be expanded into sum of wavelets with the same coefficient decay when averaged over l E Tg. See Lemma C.I and the following discussion. We also obtain the following in-context approximation and entropy bounds in Appendix 1.2.

---

Lemma 4.4. For any óN > 0, Assumption 3 is satisfied by taking
FN B o Φ I -00=(6;))) -6;]()))= LD,N(L, W, M,}
(6)
where Bg, is the projection in R& to the centered ball of radius B'y = O OVvN) and each Φ3 is ReLU network such that L (log N + log nN) and W, S, M O(1), Also, the metric entropy of FN is bounded V(FN, ||-||== e) z N log ENC
Hence Assumptions 1-3 all follow from Assumption 4, and conclude in Appendix C.1.3: Theorem 4.5 (minimax optimality of ICL in Besov space). Under Assumption 4, if 2
N log N,
DNN approximation emror
N Nlog. N
in-context generalization eiror
N2
1olog N
pretraining generalization error
R(O) S N
+
+
π
T
Besi- Ta and N
Hence if T
2
Fu in-context learning achieves the minimax optimal rate
n up to a log factor.
The first term arises from the N-term truncation and oracle approximation error of the DNN module, and is equal to the N-term optimal error (Düng, 201 la). The second and third term each correspond (((N)
to the in-context and pretraining generalization gap. With regard to N, we see that enough to learn the basis expansion in context, while T ((N2)) is necessary to learn the attention layer. However if T = o(n). the third term dominates and the overall complexity scales suboptimally as 7" - illustrating the importance of sufficient pretraining. This also aligns with the task diversity threshold observed by Raventos al. (2023). Since the amount of training data for LLMs is practically infinite in practice, our result justifies the effectiveness of ICL at large scales with only a small number of in-context samples.
2, the approximation error is strictly worse without an adaptive representation scheme and the resulting rate is suboptimal (see Remark C.3). While DNNs can adapt to task smoothness in supervised settings (Suzuki, 2019), ICL and any other meta- learning methods are fundamentally constrained to non-adaptive representations since they cannot update inference time, and hence are bounded below by the best linear approximation rate or Kolmogorov width, which is strictly worse than the minimax optimal rate when < 2. Indeed, for any N dimensiional subspace CN C BB.gg(')) holds that (Vybiral, 2008)
A limitation of ICL. In the regime
inf sup Bup (x)) ecx Ilf- (xlle3(Px) 2 a/d//t(1/p-1/1),
Remark 4.6. The N2 log N term in the pretraining generalization gap is due to the covering bound of the attention matrix I, while the entropy of the DNN class is only N log N. Hence the task diversity requirement may be lessened to the latter by considering low-rank structure or approximation of attention heads (Bhojanapalli et al., 2020; Chen et al., 2021).
4.3 Avoiding the Curse of Dimensionality
The above rate inevitably suffers from the curse of dimensionality as d appears in the exponent of the optimal rate. We also consider the anisotropic Besov space (Nikol'skii, 1975), a generalization allowing for different degrees of smoothness (0I,.... (aa) in each coordinate. Then the optimal rate nearly dimension-free in the sense that the rate only depends on d through the quantity == (E, o --- and becomes independent of dimension if only a few directions are important i.e.
have small a; Rigorous definitions, statements and proofs are provided in Appendix C.2.
Extending Theorem 4.5, show that ICL again attains near-optimal estimation error in the anisotropic Besov space, circumventing the curse of dimensionality and theoretically establishing the efficiacy of in-context learning in high-dimensional settings.
Theorem 4.7 (informal version of Theorem C.7). For the anisotropic Besov space of smoothness (ai,... ,a4), assume variance decay (4) with > 1/p. IfT Z nN and N x n3341, in-context learning achieves the minimax optimal rate
24 26+1 up factor.
7

---

4.4 Learning a Coarser Basis
Thus far, we have demonstrated the importance of sufficient pretraining to achieve optimal risk; as another application of our framework, we illustrate how pretraining can actively mitigate the complexity of in-context learning. Consider the case where (45) no longer the B-spline basis of B% (X) but instead is chosen from some wider function space, say the unit ball of ,,, for smaller smoothness < a. Without knowledge of the basis, the sample complexity of learning any regression function F3 is a priori lower bounded by the minimax rate n 2F4a by Proposition 4.2. For ICL, this difficulty manifests an increase in the metric entropy of the class FN which must be powerful enough to approximate Vi (Corollary C.12), giving rise to the modified risk bound:
(X)
Corollary 4.8 (ICL for coarser basis). Suppose > d/p. the basis (1)))= (( (x)) and Assumptions 1, 2 hold with 1/2, o./. Then if 2 N log N,
R( S N T Nlog N N log N
T
Hence if Z n² m0 and N n 2 the risk converges as nV"
log n2.
The pretraining generalization gap is now dominated by the higher complexity N log N of the DNN class and strictly worse compared to N2 log N for Theorem 4.5. The required number of tasks also suffers and the exponent is no longer 20--d 2a-t2d E (1,2) but scales as O(d). Nevertheless,
observe that the burden of complexity entirely carried by T:; with sufficient pretraining, the third 20
term can be made arbitrarily small and the ICL risk again attains n 20tt, Hence ICL improves upon the priori lower bound ж at inference time by encoding information on the coarser basis during pretraining. We remark that the result is also readily adapted to the anisotropic setting.
4.5 Sequential Input and Transformers
We now consider a more complex setting where the inputs x E [0, 1 are bidirectional sequences of tokens (e-g. entire documents) and & is itself a transformer network.? 2 In this anfnite-dimensional setting, transformers can still circumvent the curse of dimensionality and in fact achieve near-optimal sample complexity due their parameter sharing and feature extraction capabilities (Takakura and Suzuki, 2023). Our goal in this section is to extend this guarantee to ICL of trained transformers.
For sequential data, it is natural suppose the smoothness w.r.t. each coordinate can vary depending on the input. For example, the position of important tokens in a sentence will change if irrelevant strings are inserted. To this end, we adopt the piecewise 7-smooth function class introduced by Takakura and Suzuki (2023), which allows for arbitrary bounded permutations among input tokens; see Appendix D.I for definitions. Also borrowing from their setup, we consider multi-head sliding window self-attention layers with window size U, embedding dimension D, number of heads H with key, query, value matrices K k(h), Q(A) E IR Dxd ((()) E dddd and norm bound M defined as²
{
F Fau(UU D2 M)
g: : dx - d
| V 11Q V | S M, ISASH
max
g(x): vi +
((h) -4--0: U.:4 u (K (K(M Q())) (Q())))))))))))))
We also consider a linear embedding layer Enc(z) Ex + P. R Dxd with absolute positional encoding P IR" D of bounded norm. Then the class of depth J transformers is defined as
H,, W.S,
(SI ..... S1 gi Enc || S M,
f FoNN S, 9 F F DU,
Our result, proved in Appendix D.2, reads:
We clarify that this is not equivalent to a multi- layer transformer setting where ø is the rest of the transformer. Instead, & operates individual tokens z; separately, which may now themselves be sequences of unbounded dimension. The extracted per-token features are cross-referenced only the final attention layer fe. 'Here the ith column and (j, i)th component of E dx for E Z,j j E [d] are denoted by æ; and Z.y. respectively. These not to be confused with sample indexes (1) those will not be used in this section.
8

---

Theorem 4.9 (informal version of Theorem D.I). Suppose F² consists of functions on [0, 1 of bounded piecewise "-smooth and LL with smoothness or anisotropic smoothness with at max,,j aij or (Ei, وي ",y'""''' respectively. Under suitable regularity and decay assumptions, by taking F to be class of clipped transformers it holds that Nlog N N2v(1+1/a") polylog(N)
Rx and let y be mixed
R(Ō) - N- 20d
n
20
Hence if 2 nNIvi/a and N n ICL achieves the rate n 2n polylog(n).
This matches the optimal rate in finite dimensions independently of the (possibly infinite) length of the input or context window. The dynamical feature extraction ability of attention layers in the FIF class essential dealing with input-dependent smoothness, further justifying the efficiacy of ICL of sequential data.
Minimax Lower Bounds
In this section, provide lower bounds for the minimax rate in both n, T by extending the theory of Yang and Barron (1999), which can be leveraged to yield results stronger than optimality in merely n. The bound is purely scheme for the regression problem of Section 2.1 from the data D,, (x((), y ( the index T + corresponds to the test task.
and hence applies to not just ICL but any meta-learning + where
For this section we assume that the noise (1) is i.idd Gaussian, &a ~ NO, o²), instead of bounded; while the exact shape of the noise distribution not important, having restricted support may convey additional information and affect the minimax rate. We also suppose for simplicity that the support of Pa is included in B == {B3 Rº ||8,| 1 S j--2s-1 (logj) j NJ and that the aggregated coefficients Bj for N < j S Ñ satisfy E E313 I o for some dg dependent on N. The proof of the following statement is given in Appendix F.1.
Proposition 5.1. For ,,,1, > O, let Q1 and Q2 be the En,1- and en,2-coveiing numbers of FN and B respectively, and M be the 8n -acking number of Fo. Suppose that the following conditions are satisfied:
20 (n(T + 1)03e2,1 + C2nen,) < log Q1 + log Q2 S g log M, 4 2 S log M.
Then the minimax rate is lower bounded
inf P...TRR fo E III 1 (1()(()) 2 1
Finally, Proposition 5.1 is applied to obtain concrete lower bounds for the settings studied in Section 4 throughout Appendices F.2-F4.
Corollary 5.2 (minimax lower bound). The minimax rates in the previous regression settings are lower bounded as follows.
(i) Besov space (Section 4.2): ssups ED.,, 1-// 2
2042
(ii) Coarser basis (Section 4.4): inf oo ED, [llf f01 こ
Iuli + (nT))
(iii) Sequential input (Section 4.5): suf Ep., [II 1
ス n
261
These results match the upper bounds for (i), (iii) and show that ICL is provably jointly optimal in T in the 'large T" regime. Moreover, we can check for the coarser basis setting that insufficient pretraining T (1) indeed leads to the worse complexity - while the faster rate n =a44 is (o-r)d
retrieved when T Z (2a-0r This aligns with the discussion in Section 4.4, showing that ICL is provably suboptimal in the "small 7" regime.
Remark 5.3. The obtained upper and lower bounds in the coarser basis setting not tight as T varies, hence it remains to be shown whether there exists a meta-learning algorithm that attains the lower bound (ii). The task diversity threshold for optimal learning suggested by the bounds are also (a-x))
d (2) ); it would be interesting for future work to resolve this gap.
different (n 12

---

Conclusion
In this paper, we performed learning-theoretic theoretic analysis of ICL of transformer consisting of a DNN and a linear attention layer pretrained on nonparametric regression tasks. We developed a general framework for bounding the in-context estimation error of the empirical risk minimizer terms of both the number of tasks and samples, and proved that ICL can achieve nearly minimax optimal rates the Besov space, anisotropic Besov space and y-smooth class. We also demonstrated that ICL can improve upon the priori optimal rate by learning informative representations during pretraining. We supplemented our analyses with corresponding minimax lower bounds jointly in n, and also performed numerical experiments validating our findings. Our work opens up interesting approaches of adapting classical learning theory to study emergent phenomena of foundation models.
Limitations. Our transformer model is limited to single layer of linear self-attention and does not consider more complex in-context learning behavior which may arise in transformers with multiple attention layers. Moreover, the obtained upper and lower bounds are not tight in certain regimes, suggesting future research directions for meta-learning.
Acknowledgments
JK partially supported by JST CREST (JPMJCR2015). TS was partially supported by JSPS KAKENHI (24K02905, 20H00576) and JST CREST (JPMJCR2115). We would like to express our gratitude to Masaaki Imaizumi for valuable and insightful discussions the topic in relation to his work in progress (Imaizumi, 2024).
References
K. Ahn, X. Cheng, H. Daneshmand, and S. Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. arXiv preprint arXiv:2306.00297, 202.
E. Akyürek, D. Schuurmans, J. Andreas, T. Ma, and D. Zhou. What learning algorithm is in- context learning? Investigations with linear models. International Conference on Learning Representations, 2023.
Y. Bai, F. Chen, H. Wang, C. Xiong, and S. Mei. Transformers as statisticians: provable in- context learning with in-context algorithm selection. In ICML Workshop on Efficient Systems for Foundation Models, 2023.
S. Bhojanapalli, C. Yun, A. Rawat, S. Reddi, and S. Kumar. Low-rank bottleneck in multi-head attention models. In International Conference on Machine Learning, 2020.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark,
C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
B. Chen, T. Dao, E. Winsor, Z. Song, A. Rudra, and C. Ré. Scatterbrain: attention approximation. In Advances in Neural Information Processing Systems, 2021.
unifying sparse and low-rank
S. Chen, H. Sheen, Wang, and Z. Yang. Training dynamics of multi-heas softmax attention for in-context learning: emergence, convergence, and optimality. arXiv preprint 2402:24402.14422 2024.
R. A. DeVore and V. A. Popov. Interpolation of Besov spaces. Transactions of the American Mathematical Society, 305(1):397-414, 1988.
D. L. Donoho and I. M. Johnstone. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3):879992) 921, 1998.
S. Du, W. Hu, Kakade, J. Lee, and Q. Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2021.
10

---

D. Düng. Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34:1-41, 2011a.
D. Düng, B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness. Journal of Complexity, 27(6):541-567, 201
X. García, Y. Bansal, C. Cherry, G. F. Foster, M. Krikun, F. Feng, M. Johnson, and O. Firat. The unreasonable effectiveness of few-shot learning for machine translation. In International Conference on Machine Learning, 2023.
S. Garg, D. Tsipras, P. Liang, and G. Valiant. What can Transformers learn in-context? A case study of simple function classes. In Advances in Neural Information Processing Systems, 2022.
E. Giné and R. Nickl. Mathematical Series Statistical and Probabilistic Mathematics. Cambridge University Press, 2015.
of seffiitteedimensionnn statistical models. Cambridge
T. Guo, W. Hu, S. Mei, H. Wang, C. Xiong, S. Savarese, and Y. Bai. How do Transformers learn in-context beyond simple functions? A case study on learning with representations. arXiv preprint arXiv:2310. 10616, 2023.
S. Hayakawa and T. Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343-361, 2020.
Y. Huang, Y. Cheng, and Y. Liang. In-context convergence of Transformers. arXiv preprint arXiv:2310.05249, 2023.
M. Imaizumi. Statistical analysis in-context learning, 2024. Personal communication.
nonconvex mean-field dynamics on the attention landscape. In International Conference on Machine Learning, 2024.
Kim and T. Suzuki. Transformers learn nonlinear features in context:
H. M. Wang, Lu, X. Cui, and P.-Y. Chen. Training nonlinear Transformers for efficient in-context learning: theoretical learning and generalization analysis. arXiv preprint arXiv:2402.15607, 2024.
A. Mahankali, T. B. Hashimoto, and T. Ma. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arXiv preprint arXiv:2307.0355 03576, 2023.
D. Meunier, Z. Li, A. Gretton, and S. Kpotufe. Nonlinear meta-learning can guarantee faster rates. arXiv preprint arXiv:2307.10870, 2023.
M. Nikol' Skii. Approximation of functions of several variables and imbedding theorems, volume 205 of Grundlehren der mathematischen Wissenschaften. Springer Berlin, 1975.
Y. Nishimura and Suzuki. Minimax optimality of convolutional neural networks for infinite dimen- sional onput-output problems and separation from kernel methods. In The Twelfth International Conference on Learning Representations, 2024. URL https: http/////peeeeeeeeeeeeee/eeeeeee net/ ffrmmfrrrrmdd EW8ZExRZkJ.
S. Okumoto and T. Suzuki. Learnability of convolutional neural networks for infinite dimensional imput via mixed and anisotropic smoothness. In International Conference on Learning Representa- tions, 2022.
A. Raventos, M. Paul, F. Chen, and S. Ganguli. Pretraining task diversity and the emergence of Bay-Baaesi in-context learning for regression. In Advances in Neural Information Processing Systems, 2023.
J. Schmidt- Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4), 2020.
T. Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse dimensionality. In International Conference on Learning Representations, 2019.

---

T. Suzuki and A. Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. In Advances in Neural Information Processing Systems. 2021.
J. Szarek. Nets of Grassmann manifold and orthogonal group. Proceedings of Banach Space Workshop, pages 169-186, 1981.
S. Takakura and T. Suzuki. Approximation and estimation ability of Transformers for sequence- to-sequence functions with infinite dimensional input. In International Conference on Machine Learning, 2023.
H. Tricbel. Theory function spaces. Monographs in mathematics. Birkhäuser Verlag, 1983.
H. Triebel. Entropy numbers in function spaces with mixed integrability. Revista Matematica Complutense, 24:169-188, 2011.
N. Tripuraneni, C. Jin, and M. Jordan. Provable meta-learning of linear representations. In Interna- tional Conference on Machine Learning, 2020.
A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends Machine Learning, ((1-2):1-2 1-00, May 2015. ISSN 1935-8237.
A. W. der Vaart and A. Wellner. Weak convergence and empirical processes: with applications to statistics. Springer, New York, 1996.
J. von Oswald, E. Niklasson, E. Randazzo. J. Sacramento, A. Mordvintsev. A. Zhmoginov, and M. Vladymyrov. Transformers learn in-context by gradient descent. International Conference on Machine Learning, 2023.
J. Vybíral. Function spaces with dominating mixed smoothness, volume 30 of Lectures in Mathematics. European Mathematical Society, 2006.
J. Vybíral. Widths embeddings in function spaces. Journal of Complexity, 24(4):545-577 2008.
J. Wu, D. Zou, Z. Chen, V. Braverman, Q Gu, and P. L.. Bartlett. How many pretraining tasks are needed for in-context learning of linear regression? In International Conference on Learning Representations, 2024.
Y. Yang and A. Barron. Information-theoreti determination of minimax rates of convergence. The Annals of Statistics, 27(5): 1564 1599, 1999.
D. Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94: 103-114, 2016.
R. Zhang, S. Frei, and P. L. Bartlett. Trained Transformers learn linear models in-context. arXiv preprint arXiv:2306.0999
2023.
R. Zhang, J. Wu, and P. L. Bartlett. In-context learning of a linear Transformer block: benefits of the MLP component and one-step GD initialization. arXiv preprint 4rXiv:2402.14951, 2024.
12

---

Table of Contents
1
Introduction
1.1
Other Related Works
2
Problem Setup
2.1
Nonparametric Regression
2.2
In-Context Learning
3
Risk Bounds for In-Context Learning
Minimax Optimality of In-Context Learning
4.1
Besov Space and DNNs
4.2
Estimation Error Analysis
4.3
Avoiding the Curse of Dimensionality
4.4
Learning Coarser Basis
4.5
Sequential Input and Transformers
5
Minimax Lower Bounds
Conclusion
10
Proof of Proposition 3.2
15
A.I
Decomposing Approximation Error
15
A.2
Bounding Term (8)
16
A.3 Bounding Term (9)
17
A.4 Bounding Terms (10)-(12)
19
A.5 Proof of Lemma A.1
20
B Proofs on Metric Entropy
22
B.1 Modified Proof of Theorem 3.1
22
B.2 Proof of Lemma 3.3
22
B.3 Proof of Lemma B.1
23
C Details on Besov-type Spaces
24
C.1
Besov Space
24
C.1.1
Verification of Assumptions
24
C.1.2 Proof of Lemma 4.4
27
C.1.3
Proof of Theorem 4.5
28
C.2 Anisotropic Besov Space
28
C.2.1 Definitions and Results
28
C.2.2 Proof of Theorem C.7
29
C.3 Wavelet Refinement
31
C,4 Proof of Corollary 4.8
32
D Details on Sequential Input
33
D.I Definitions and Results
33
13

---

D.2
Proof of Theorem D.1
34
Numerical Experiments
36
F Proofs of Minimax Lower Bounds
37
F.1 Proof of Proposition 5.1
37
F.2 Lower Bound in Besov Space
39
F3 Lower Bound with Coarser Basis
39
F4
Lower Bound in Piecewise 7-smooth Class
39
14

---

Appendix
A Proof of Proposition 3.2
A.1 Decomposing Approximation Error
Recall that
1 ((INeN
@- = (T" ,0'"
- B.N
N.V
We introduce some additional notation the following fashion. For brevity, we write N oo instead of (N + 1): oo as exception.
Φ (oy.N (x1),
E ERN
(EI, ER",
T (v (21).... ................................ (xn)) E RRoox, V : (o) oo (zn)) E gexn
W NNN
& (x1)) ( E ERAx"
Since clipping fe does not make its difference with F3 E I--B, B] larger, it holds that
R(O*) E
(F) fe. (X, ))))
< (F)(()) for (X, y. 3))
s 2F (FF3(B) F2,x(()) + +2E
(F (F - (x-
$ 2s + + ( (G))
r 27
n
due to Assumption and N = N. Expanding the attention output as
r
(f) v N:N (z) + 60 (ō)) r
(Ø*
To
N.N
+ To
N.N)
n
n
vNN T (Ø* vr N.N
= (0)
1
T N:N V
(g) 10 N:N (2)) T
(++ 1o N:N y
2 N:N (T) T
To 1
N:NU
2 (T)
and the final term further as
To V
N
To
N: TTOT3 -
N
(7)
N:N
(7) T 1
n
n
wo
N B
T
Wr
T
Ni00 No + +
T
Vi (7) T
NiN
n
we obtain that
I' "" 27
E
no (.)(T) -x-
27
$
F (x) - 2y (7) T
N:N
N: NEN
(8)
15

---

wo (OOT
3 N:00 + +5) 27
B
1/
N:N (8) T
N:V
N:00
(9)
Vpr N )y 2
E
(x) WN:N (2)) T r
(10)
n
To
NN:N V
E3
(σ)
UN (2)) T
(11)
(4"
N:N )
+ E
d N:N
(i)
(12)
We proceed control each term separately, from which the statement of Proposition 3.2 will follow.
A.2
Bounding Term (8)
Since Fo. A.N (T) = vi ( :1.N= = v/
(ā) BYNN.
we can introduce a (T*)-1 factor to bound
To
NOT 3
N:N
N:N N:N
E
po (.) (E)
n
N:N MOT
27
E
F (xx()) 1o ( T
N.N
By:N
Vo N:N TOT N:N
27
E
w/o (IN T T
Ev.N
- B.N0
--
BN.NN
TOT N:N
27
< 2E
W/o (1: T
N:N
Ev.N
BNIN
(13)
- B.N
27
+ 2E
N:N (T)
r
B
NN.N
(14)
Denote the operator norm (with respect to 2 norm of vectors) by [|-llop- For (13), noting that Σ positive definite,
Vp NOT N.N
E
N:N
(2)
T
N:N
Ev.N
By:iN
n
T N:N N:N
TO
E
WyNN (x)
1'10//1
1112 2g.N
2 1/2
IN
1/2
n
Yo N:w N:N
NOT
Ex,9
BI E1/2 2
E
11/2
Ew,N
1/2
IN
Σ
(
n
1/2 1/2 To x 1 1//2
NEN NOT N
1--12 N.N
IN
N
1/22
n
1/2 M N.N T
Ex
N.N
5D 1/2
IN
E.
[Bv.R N.N
1//
W.N
72
T
TOT
x
1-12 1/2
N.N
N:N
--112 1/2
W.N
In
E
1'1
16

---

/ 2-1/2
Mr
NOT
x Ex
Tr
N:N
N:N
1/2 2N IN
E
1/2 B.N W.N
due the independence X, 2 and For the last inequality, we have used the fact that both the E Ey E "VNN term and the matrix multiplied to it are positive semi semi-definite, and the former I
is bounded above as 3 IN by Assumption 1.
Furthermore, we utilize the following result proved in Appendix A.5:
Wo NOT N.N
2r
Ntr log N +
Lemma A.1. Ex
1-
N.N
E-1/2
IN
2
log² N.
V.N
n2
op
It follows that (13) is bounded
Ve N:N N.N
yoT
27
E8
N.N
(i)
1
E.N.N
n
yo
MOT N:N
Fx
5-1/2 1/2 P
N:N
1122 M
IN
Tr
1122 11/2
B.N
n
op
2r
N4r
22 2A
log N
log² N
Evoplllop Tr(Eg,n)
11
n²
22r
2rr
log +
log² N
n
since Tr(2.,,) is bounded by Assumption 2.
Moreover for (14), we compute
Σ 1" B.N
27
E
N.N
(i)
BN=N)
E-1
R
AT
BNN
r
N.N (
N.N (7) T S.N 3 N.N
N.Ñ
Σ=1 1
E
Tr
to N:N B.N
(1)
N (x)
T r
B B N:N
Σ
Tr
J.N
E
do NIN (+)
N.N
r
3.N
Es 13
1N.NN TT N.N
72
n
-=1
A.N
J.N
Tr
E'
33,N
positive detinite
1 Ev.N
-1- n2 B,N
Tr
I'EN,NI"
11
1
Ev.N + -
N
Tr
EΦ,N
B.N
A.3 Bounding Term (9)
Since the sequence of covariates T1, .na and noise E,.... En are each i.i.d.
T N:N Nioo No0 + E) 27
uoo (NN (Z)
17

---

v/ NN
No (01) +.) 27
1/ N.N (8) r
Nico
N:00
n
E
w N:N N (N
20 N:00 (24)
Σ
2o Niw (8) r
n²
( (NNNN()) r N (z) UN (
E
(15)
E (B) (+) TT ( n
( (.))
Ni00 1 Noo
(a')
(16)
E (U) T Tr uo (. )
(17)
for independent samples x, x a x. We now bound the three terms separately below. For (15), we have that
T W (x) Noo v (x)) (1)
E
u ( (x)
(x)
n
E
T WN x (1) (x) BNio0 N:o0 Noo (x)
72
Exp wo MiNn(a
N (x) Bg [8Ni00 Nooo (0 (x))
24 2A 21
En [I M (z) (x) ES [3 Nood (8r (x))
1 (+))
lim Tr (E& [BNM En ( M
sup
rEsupp Px
sup 1100 N.N (x)]
lim Tr (E ( M
rEsupp Px
since Σv.M 3 C2IN as M + oo by Assumption 2. As sup, 11 N:N (x) S N by (2) and the
diagonal of Eg[3x. T k decays faster than - M) follows that
when M > N due to (4),
(x))2 lim Tr (Es ( S N 4-000
sup n #Esupp Px
n
Similarly, for (16), we have that
E N:N
(T)
I V (
N0 (x) 1 u (i (x')
n
<B
[
W W (8) T v (
1/ W ( &i (z') 2 (x)
E , 1 (x)
11 (x))
T
= Eg
Ex
V (x)
r'EENNT'. (3) vo (x)
$
Eg
Ex
(z)
(z)
2 Eg [1 Nooo (x) N 3 N (xx (4)
2 222
And for (17), we have that
(US). ( 7]
18

---

0²
Tr I EEE 2 (3) (T) N (T) T E (1
11
Tr L'Ev, wI Σv,Nl
positive definite
Tr
1 T'E,,N''
Ev.N + - n 2
OºN
Tr [ v| S
Therefore, we obtain the following bound:
E
(+)
Vo r
( N:W
N:0o
:N:00 + E)
+ S
)
27
N2rN-2
+
N
2s
+
22N
n
A.4 Bounding Terms (10)-(12)
For (10), we use the Cauchy-Schward inehuaallii inequality and Assumption 3 to bound
(Φ) - ( 1 (Φ*
yo N.N)y
)
27
E
n
1
n
(00( & (i ( - - ( (2:))11)
EE
E (T)
2 N (1))
S (x (3)
110(x)) - Us U
E [u2]
sup >esupppxx Px
2
| op
N max |0 vz
E [
NSISN
S N (B² + +
Similarly for (11) and (12), we have
N y 27
E
(6
S (F))
T
n
(10))))
w (. )
E
r (yvN(())
n
n
Σ E
(
N
S 12
1 (x) w 1 18
11 (x))) [u²]
sup #Esupp Px
sup
rEsupp Px
S No 2r (B² +02) = N 2rr+1 83 (02 +02)
and
(Øt Tho N:N ) 27
E
2o (+) TT
11
Vy (a:))s)) 27
3o (N (7) (x))))))
n
19

---

R (
& &NN (1:) )13))
sup ( rEsupp Px
up
[1(0(()) x [w-]]
sup zEsupp Px
2 22 8 (B* O2))
This concludes the proof of Proposition 3.2.
A.5 Proof of Lemma A.1
We will make use of the following concentration bound and its corollary, proved at the end this subsection.
Theorem A.2 (matrix Bernstein inequality). Let SI. Sn E R NxN be independent random matrices such that [[[s] = 0 and |S L almost surely for all i. Define - Di=1 Sn and the
matrix variance statistic v (Z)
u (Z) = max [|
olo |E Z [|oppp
= max [ E|S,S
E EIS S,
lo
Then holds for all > 0 that
f2 20((Z + L
Pr (l 2 2)) 5 2N exp
Proof. See Tropp (2015), Theorem 6.1.1.
Corollary A.3. For matrices S,, SS, satisfying the conditions of Theorem A.2, it holds that
(Z) n² (1+ log +
16T.2
E
1
I
(2 2 2oo 2N + (log 22)
2
9n2
We will apply Corollary A.3 to the matrices
--122 S = W.N wo N. (2.) N:N (xx) 24 IN-
It is straightforward to verify that
E|S.] = E 1/2 1/22/ Eg, 2-1/2
IN =0
and
N
|Sollo & 1 (z.)a Nxx llop + 1
Σ (z,) + 11, 2
almost surely by Assumption 1.
Next, we evaluate the matrix variance statistic. Since each S, is symmetric,
Z
E
lp
Ex
D 1/2 (1:
D (1s)) EE'!?
2Ex
Dv.N
1-1/2
40 (1:
N:N
TD
Dw,N
INN
Σ
Ex
E w/
E
T 1/2 E
-nIN
< +
Eg
E 2
(
(z) Eg 1/2
20

---

for single sample ~ Px. The second term is further bounded as
Ex Σ
1/2
u N:N
(2)
( E W N.W (2) N:N
T 1/2 E/! (x))
Bx
1/2
N.N (I)
N (x)
2 1-112
20.N
1 2i 1/ N.N0 (Pxx)
op
||nllop
Σ (1))2
(Pxx
2
again by Assumption 1.
Hence we may apply Corollary A.3 with u( S n2 I S 2 to conclude:
Ex
Σ
1/2
yo N:N
To
N:N
E
1/2
IN
E
1 1
Σs s
2r
log N log N.
2ar
n
n²
Proof of Corollary A.3.
From Theorem A.2 and with the change of variables A = 1²/n2, we have n²a A
2)
S 2N exp
n
op
20(Z) + LnV
Since the probability is also bounded above by follows that
1
n²
Pr
7
A
< 1A2N exp
2(2o(Z)) V LnVA)
n²d
3nvA
$1A20 SAAN
2N exp
+1 2N exp
40(Z)
4L
and the expectation can be controlled as
1
E
2 op
Pr
Z 1lop
A
dx
/
00
3nv
1A exp
dd + j
1 2N exp
YP
4u(Z)) (t)
4L
For the first integral, we truncate λ1
4v(2)
log 2NV that
n²) da
A 2N exp
dA
A1
2N exp
(z(Z)
4u(Z)
4u (Z)
4u(
1og2N +
n²
n²
For the second integral, truncate
X2 := (16 log 2N
2
so that
3nv A
1A 1A2N exp
dd
4L
3nv A
A +
2N exp
Yd
4L
16LN
4L
3nv À
Aa 3n
exp
3n
4T.
1==2
4L
8L.
4L
4I.
log 2N
+
log
2N +
3n
3n
3n
3n
Adding up, conclude that
4v Zz)
161.2
E
7
<
n² (1 + log
2N) +
(2 + 2 2og 2N + 2N)
2
op
9n?
as to be shown.
21

---

B Proofs on Metric Entropy
B.1 Modified Proof of Theorem 3.1
For a full proof of the original statement, we refer the reader to Section B.1 of Hayakawa and Suzuki (2020), which corrects some technical flaws in the original proof. Here we only outline the necessary modification to incorporate the bounded noise setting.
Denote c-cover of the model space by f1.... fM- The only step which relies the normality of noise fim is a concentration result for the random variables
Ej = Ei= ((l) 8 (x:))
ISiSM M,
I (1)())) - (x:)))) 1/2
where it is shown via the normality of E, that
o) S 40 (log M 1).
E
max ISISM
We will instead rely on Hoeffding's 's inequality. By writing Ej = w/ Ei: = Eiz W5,51 where
[y(x;) - 1 (xx)
Wy.s (15(z)) f (x:)) 1/21
since |wم,ررر| S o W/ a.s. it follows that
2u² (2o (ory, = 2 exp
u²
Pr Pr (ley) u) S exxp
(-
2
for all u >> 0. Then the squared-exponential moment of each is bounded as
[exx((1s3] = 1+
/
Pr (exp(1e))) 2 X) dA dA
$ + /
log A
2exp
2002 dd
$ 11+2
> 20 dd S
by setting 1 Hence via Jensen's inequality we obtain
M Σ j=1
exp
IE
max
< E
max exp(ls3) ISiSM
< E [exx(([3)]] 3M
1SSS M
and thus
E
max
< 40 log 3M,
ISSSM
retrieving the original result up to a constant.
B.2 Proof of Lemma 3.3
Let us take two functions fer fe, E NN for 9, = (T (1), = 1,2 separated as
||T T2llop S 81,
max |1 - 22. S 82.
15J5N
Then it holds that
[fe, (X, y. x) fe, X, y, ā]
< fe, (X, .) fe, X, y, ā
TiΦ1 (X)y Φ (
T202 (Xy Φ2 (ō)
n1
22

---

(1() T1 (X)y 02( T1 (X)y (2) 11 (X)y
-2(
[X) 62( T202(X)1)
(T) 02 (2)
-
11 - I'2 (X)
+ 1
(1(16())1 dz (X))all
C2 + B¹
C₂ n
Σ
(x))ll)
Σ - 22
n
n
< 2 + BB (B Co
BB +066 2B (B+o)c2VN6
Hence to construct an c-cover GT of T N. it suffices to exhibit cover Gs of SN and a cover Gy of FN for
e
61 = BB+ 82 4B + CNN
and set Gy = Gs x Gy. For the metric entropy, this implies
N(T,,II-lle [1-I,,)))
e) S V(Sx, I1- 61) +
We further bound the metric entropy of Sx with the following result, proved in Appendix B.3.
1
1
Lemma B.1. For 8 & it holds that V(SN. Il-llop 6) S N log 8'
2
Substituting into the above, we conclude that
B
V(TN: Il,l c) S N2 log
+ FN,II-le,, 4B CVV
e
The choice of 82 is not important as long as the metric entropy of FN is at most polynomial in 62. O
B.3 Proof of Lemma B.1
Let Pı, P2 E Sx and consider their diagonalizations
r U,A.U,
A, diag(>r.1,"" ...N), i= 0,
where U, On, the orthogonal group in dimension N, and S Ais S C3 for each S s N. Assuming
8
U - U2llop S 4Cs²
Ais - -esl Vj
it follows that
||T - T2llop
U U + U - U2A,U + U.A.U - U2ArU, 1lop
< 2| r.
U, U2llop + || - A2/1
8 8.
2C3 4C3
Moreover, the covering number of ON in operator norm is given by the following result.
Theorem B.2 (Szarek (1981), Proposition 6). There exist universal constants C1 > 0 such that for all E N and (0, 2).
NCN 13
N(N-1)
C1
S SN(OO NI, 8) I (
23

---

Hence we obtain that
- + V 0. Cal ,11-1la. 2
V(SN. Il. 6) S ON. lllp
4C3
N(N 1)
C2 log
2C3
+ log
2
8
8
25 2 log 8
Finally, we remark that if elements of the domain Sy not constrained to be symmetric, alternatively consider the singular value decomposition and separately bound entropy of the two rotation components, giving the same result up to constants.
C
Details on Besov-type Spaces
C.1
Besov Space
C.1.1
Verification of Assumptions
We first give some background on wavelet decomposition, The decay rate == a/d is intrinsic to the Besov space as shown by the following result, which allows us to translate between functions f E B (X) and their B-spline coefficient sequences.
Lemma C.1 (DeVore and Popov (1988), Corollary 5.3). If a d/p and + 1 - 1/p, function f E L?(X) Bpgg(2)
(X) ) if and only if f can be represented as
00
Σ
Σ
such that the coefficients satisfy
1/2 87 1/4
ber P.o
2kla d/p)
Σ
e
00,
k==
EEIS
with appropriate modifications i 00 or = Jc. Moreover, the two norms 11311 and [|fll
are equivalent.
In particular, this implies that for any f E U(B (x))) the p-norm average of Br, for l E Ig at resolution &s is bounded as
1/P
Σ
1
-
S
S 2-k
EES
and the coefficients Bn.E 2 kd/2 Bane w.r.t. the scaled basis (2kd/22 w satisfy
1/p
Σ BEI
(2kd)-a/d-11)
(18)
I
Thus it is natural in a probabilistic sense to assume E[SE 11/p S (2dd)-a/d-1/2, This will be k.
the case if for instance we sample (Bk,,)eerg uniformly from the p-norm ball (18). This matches Assumption 4 up to the logarithmic factor and hence the rate is nearly tight in variance, even though (18) only applies to the average over locations rather than each coefficient explicitly. See also the discussion in Lemma 2 of Suzuki (2019).
24

---

Assumption 1. We take m to be even for simplicity. The wavelet system (w at each resolution K is linearly independent; for any g (X) that can be expressed
Σ
3K 2 K.t
EE
we have the quasi-norm equivalence (Düng, 2011b, 2.15)
llgll2 = 2 Kd/2
2-Kd/2
Σ BESK
2d
a2 PK.
= =1((3x,)) ll2
which implies that the covariance matrix En~Unif([O, 114) N:N (z) N: (1) is bounded above and below. Since assume Pxx has Lebesgue density bounded above and below, it follows that Eg, N is uniformly bounded above and below for all 2 0.
In contrast, any B-spline at lower resolution k < K can be exactly expressed as linear combination of elements of (w* (w by repeatedly applying the following relation.
Lemma C.2 (refinement equation). For even m and (ri,'.,, .ra)r. -1, ,1) R holds that
m (m))
WE,
Σ
2(-m+1)d
II
w
11+1,2t---71 71
(19)
TLy
Proof. The relation for one-dimensional wavelets is given in equation (2.21) of Düng (2011b)
4m (xx = m1+1
m km
2x
+
p=0
from which it follows that
wh, (x)
II
6m (2 Ei)
i=1
Σ
m
2 1jd
m
4m
22+1 x4
26, 2
ri
i=1
d
2 --dd
m
d
1
ri
Pa=0
as was to shown.
Therefore select all B-splines at fixed resolution K to approximate the target tasks, and
N
1 = (m + 1 2* 2d
K 1-1
K
N =
-
Ñ
Σ
X.
k=
k=0
It is straightforward to see that 0 S wH,
< 1 for all x E X' and moreover the B-splines (extended
to all E gd) form partition of unity of RRd at all resolutions:
Σ Enta (x)= e Rd
V6
FEZ4
Then for all X have the bound
Σ (g)=²= Σ 2kd (x)) 22d Σ
we ( 2Kd < N,
LE14
EE24
and hence (2) holds with 1/2.
25

---

Assumption 2. For any 3 E supp Pe we have that
(Px))
Bk,e 2
k=0
BE
(Px(
2k1/2
max 18k,el tEIK
Σ
White
REIH
(x0)
1/P
2kd(1/2+1/p)
Σ
Wkst
k=0
FETS
KETg
(x)()
80
1kd(1/2+1//) (2
k=0
3 (1 2 2//0-a)1
=: B.
Furthermore, the convergence rate of the truncated approximation F is determined by the decay rate of B in Lemma C.I as follows (it does not matter whether we bound F.N or FUNN since N x N). We consider truncation of all resolutions lower than K so that N, N 2 Then it holds that
x
F - Pa (.NNI = 1/x Σ
B103(o)) j=N+1
Px(dx)= = Σ
f=k=
lim M+000
C2113N
C2
Sh
k=K EET
2/p
80
1-29
Σ
BR,ee
2 (2hd))22a/40)
EE
km
2-2K
N 2a/d
2-2a
where for the last two inequalities we have used the inequality |||||2 < 11/221//11=11/ for 2 E R and p 2 conjunction with (18). Thus our choice of s a/d / is justified. Under this choice, (5) directly implies (4) as
Es k. $ 2- Kd(2++1) K-2 =
20- 2- (log N)
holds for the basis elements at each resolution K, that is for those numbered between N and N.
Remark C.3. When 1 < < 2, the truncation to N does not suffice to achieve the N 2 approximation rate, and basis elements must be judiciously selected from wider resolution range. More concretely, a size N subset of all wavelets up to resolution K' = [K(1 + 1 where = pa/2ad 1/2 > 0 must be used (Suzuki and Nitanda, 2021, Lemma 2). Hence the exponent is factor of 1 + -ー worse w.r.t. N' 22'd, leading to the inevitable suboptimal rate.
To show boundedness of Tr analyze the composition of the aggregated coefficients B using the following result.
Corollary C.4. For any 0 S k < k' there exists constants "ke &,E 2 f E 1 E' E 1g such that
2hoc2 = Σ 2
4/2
we 8 8 B = Σ N...ee.a
FETS
FEES
EETE
holds for all (BK,))Erg
Moreover, it holds that
Σ 1,e S (///2
Σ
MK eee S 2(K-=R)/12
26

---

The statement follows directly from the more general Proposition C. stated and proved in Appendix C.3 below, by restricting to wavelets with uniform resolution across dimensions. Using Corollary we can refine each lower resolution component of / to resolution K:
C.4,
N
K Σ
F
Σ 3,0J
Be.e2kd/2uf
Σ
Tr.KEeP 2
j=1
k=0 2 terg
Thus each aggregated coefficient, indexed here by E T can be expressed as
K Σ
3KG
E
K-
Hence it follows that
Eg Eg
k
Σ Σ
K,K BB Bolpkel
Σ TKKKR. 2 k(2a+t))
0
RET
K
(k - K)d 2 kk(2atd)
<
k=0
K
< 2 Kd.
2 2ka k- NN-1
k=
from which we conclude that J,N) = EeErg Esl S N. N-N uniformly bounded.
Finally for the verification of Assumption 3, see Appendix C.1.2.
C.1.2 Proof of Lemma 4.4
We use the following result to approximate each wavelet wi.ee e at resolution K with the class (6). The proof, in turn, relics on the construction by Yarotsky (2016) of DNNs which efficiently approximates the multiplication operation.
Lemma C.5 (Suzuki (2019), Lemma 1). For all 8 > O, there exists a ReLU neural network w E FDNN L, S,S,M M) with
L = 3 +
loga (3dm (1 dm
5 [log (d m)],
W Wo 6mm + 2) + 2d,
S LW2
M 2(m + 1)"H
satisfying supp R C [0, m + _ and || (1lx 8.
Here, 8 is also dependent on N.
Now consider N identical copies of @s in parallel, where each module is preceded by the scaling (xx), + (2xxz x; - 4) for E I and whose output is sealed by 2K4/2, In particular, these operations be implemented by K log N consecutive additional layers with norm bounded by constant. Hence each module oy .6x approximates the basis 2 a// K, with kd/228 S VN8
accuracy, and substituting 8N v No gives that
1| Φ 110 EN, NEJSN,
with L S log 8-1 + log N x log o + log N. Note that the sparsity S is only multiplied by factor of since different modules do not share any connections. Moreover the target basis has 2-norm bounded
1/2
1/2
(x))lla
Σ 2kd wx,(())))
2Kd Σ wk,
x XVN,
FETS
JE2d
where we have again used the sparsity of w at each resolution. Hence we may clip the magnitude of the vector output á by B'y and the approximation guarantee remains unchanged.
To bound the covering number of Fx. directly apply the following result.
27

---

Lemma C.6 (Suzuki (2019), Lemma 3), The covering number of FDNN is bounded as
((F W,S, M), (HIle, ( & L(MVI) (W + 1)22 9
Since clipping the magnitude of the outputs does not increase the covering number, conclude:
V(FN, 111l,=,))) NN V(FDNN W, S,
S SN log I. + SLN log M + 2SLN log(W +1) 1) + SN log
N
2 log Nn
N log
C.1.3 Proof of Theorem 4.5
By Lemma 3.3 and Lemma 4.4, the metric entropy of N is bounded as
N + N Nogg dyc
N2
V(TN,lHll N2 log c
Combining with Theorem 3.1 and Proposition 3.2 with 1/2 and = a/d gives
N n²
N2 log N + N Nlog
.22
1(@) log N log N + N 2a/d + 22 + 7
+
ÔNe
Substituting ON N-1-a/d and N-2a/d yields the desired bound.
C.2 Anisotropic Besov Space
C.2.1 Definitions and Results
For S p.g S co, directional smoothness = (ai,""..,al) E RS, and r = maxigalas + 1, we define ||- Bp.. I1-I1 L. + +1-1pp, where
(En [2 Wn , (2 (..//...)//// sup 2h Wri (S, (2 k/a1 k/as,.... 2-a/d)))
| Bg.
q<
The anisotropic Besov space is defined
Bp.g (x) (S E LF(X) |/ < x.).
The definition reduces the usual Besov space if for details. We also write z = max; a;, a = min; a and the harmonic mean smoothness as
az; see Vybíral (2006); Triebel (2011)
ā = a )
For the anisotropic Besov space, we need redefine the wavelet basis so that the sensitivity to resolution & E Zzo differs for each component depending a. Define the quantities
||blaa/a
Σ ka/ai,,
II (-m, m. + 1, ko/odl c zd
We then set for each & 2 0 and l Ida
who (x) == wd
mm (2 ka/aal xi C.),
wilka/as Lka/aa
28

---

and take the scaled basis
{vg [JEN) = (2llklllo/a/ da Waz
Z20, l E Idaa
with the natural hierarchy induced by
The minimax optimal rate for the anisotropic Besov space is equal to n (Suzuki and Nitanda, 2021, Theorem 4). Our result for in-context learning is follows.
Theorem C.7 (minimax optimality ICL in anisotropic Besov space), Let a E IS with ā > 1/p and F ( (X)). Suppose that Px has positive Lebesgue density px bounded above and below on X. Also suppose that all coefficients are independent and
EslBu,r] =
EslSk, S ka(2+1/a0
Vk 2 0, LE Ibaa
(20)
Then for n 2 Nlog N we have
N log N
N log N
R(O) S N
T
Hence if Z nN and N x n ž,4,, in-context learning achieves the rate n minimax optimal up to polylog factor.
20 log n which is
C.2.2 Proof of Theorem C.7
The overall approach is similar to Appendix C.I. The decay rate of functions in the anisotropic Besov space characterized by the following result which extends Lemma C.I.
Lemma C.8 (Suzuki and Nitanda (2021), Lemma 2). if >
1/p and m > a + 1/p, a function E TP(X) is in MB. p.g (X) if and only if can be represented
Σ
Σ
B de (x)
kezd RET
such that the coefficients satisfy
1/2 87 1/4
1111bg.. hag
2ka
|| |1
Σ
$11l|| mg.
BE BETE
Moreover, the two norms
llg.. and ||] are equivalent.
4. We again select all B-splines (ee,)) at each resolution K to approximate the target functions. By repeatedly applying the refinement equation for onc-dimensional wavelets as many times as needed each dimension separately, we may express any B-spline a lower resolution K linear d.a. combination of (wk,))ergg similarly to Lemma C.2. See Proposition C.10 for details. thus have
N Idda
II (m + (a/add) x 2 1a/a [=1
Since ||klaaja kajā + O1(1) always holds, it also follows that
K Ñ
K
Σ
+1++1
|| l/
(22/aap 2ka/a N
k=0
k=
k=0
and similarly N x N. Therefore,
g
Σ
(x))) < 21l Σ
da < 221
j=
29

---

and the scaled coefficients decay in average
1/P 18aeel")
-1/1
1/8
(17/21
Σ RETE
x
2 2-11bll/aa2
Σ
1
BE RE
- 2 //// 122 [lfll
N (a+ 1/2+1/2)11111) |ffl
For Assumption 2, we can check that
|18llz0(Px) $
Σ
3u,e 21 da
k=
EEI
(px)
1/v
01/2+1/pillklp
13
EE
21//+1//Dllkll/a 2 2-1lkllu/a/22-o
k=
S [
22/a(1/p-0)) =
and for a resolution cutoff K 0, N 2 Kklaa/ the truncation error satisfies
2/0
[FF FE.NIIiP(PP) S
Σ Σ
1-/01-2/00
Σ
km K+ k
EER
2||M|e/a 2 |lAlla/a 2h x 2 2Ka x 25
k= K+1
Thus we may set 1/2, ã and take the variance decay rate (20) as
E S 2 [2+ 2 = 2 k
For boundedness of Tr(Eg,v), we use the following result which is also obtained from Proposition C.10 by considering resolution vectors [[ka/ai],-" [ka/aal) and ([k'a/a)), Lk'a/// a/aa))
Corollary C.9. For any 0 < k <, k! there exists constants K 0ffor le 1 that
I such
2 d,a Σ tEPO
Σ
2 Pule :e
Σ
Wk
BERT
EEI
holds for all (Br.))eerd... Moreover, it holds that
Σ TKKe < 2(1 -IKK -IK'I w//
Σ
K S -
FET
PErT
We apply Corollary C.9 to refine all components of Fo A,N
to resolution K:
FR.N Σ Σ
Br.c2lk
wio/
Wki
Σ Σ
Σ
m..K.e Be aall
wK.
da
k=0ter
ameeerta EEI..
Hence it follows that
K S
E k
Σ
Σ
R..
Σ
Σ
TrKKEN
2 k-
k=U sErd
k=0
30

---

2 2 -ellllaa-la -|/ l/tl////.2222ll11110 2-
K
- 2
Klla/a
2 2o-2kak-2
N
k=0
and we again conclude that Tr(2g,,) is uniformly bounded.
The rest of the proof proceeds similarly the ordinary Besov space.
C.3 Wavelet Refinement
In this subsection, we present and prove an auxiliary result concerning the refinement of B-spline wavelets and the recurrence relations satisfied by their coefficient sequences.
Proposition C.10. For any k. k' E Σ such that K' k E E there exists constants " 2 for & I. l' I such that
Σ
Σ
Bw e 112/2 21 wh.er
B =
(21)
RETS
VETS
EEI
holds for all (Br,e)eere.
Moreover, it holds that
Σ
KK 2 -1ll//2
Σ
WKee S 21ll/-111//2
FET
ME
Proof. We proceed by induction on || - 11/1.. When k'' = + for some i s d, we can refine each wh, using equation (2.21) of Düng (2011b) as
(x)
II E=1
mm
(2
xr Es)
2 m++1
(2 I3 - E4)
==0 rr) im (2 I. 22, - r
(m
m
4m
2
iiftj
m
2 m+1
d Cett,, D)s (I).
Since / (L, + 2 ye matches given location vector el E litee and only if = (i+
and E 26, + comparing coefficients in (21) yields
t,, = m 1/2 (f- (175)) Cy
m
26, + 2
Here, 1 denotes the indicator function for condition It follows that Neckees L. 2 0 and
S f.
Σ
2 2-m+1/2
1/2
m
S 2122
28 + m 2
EE
2,EZ
<
m-+11/2
m
21/2
C
20, +
E2
by considering parities.
Now suppose the claim holds for a fixed difference || - Al|1. Applying the above derivation to further refine resolution K kn =k' +ej ej for arbitrary gives
Σ E
3R 2 Ml1 M
Σ PETS
Bw /
Σ
B w te,
31

---

where
Be =
Σ 3- (8== 1 ((+1))
m
Bure
0 - 26 + 2
m
PEr
Σ
2 -+ 1 1/2 1 (e==1) (+#1)
m
Tr kr s. Bu,e.
14g 222 +
eer, mERS
Hence we obtain the recurrence relation
Σ
2 2-
(C== (1+1))
( 26' +
m 2
,
CELD
from which we verify that Nk,b',, ee" 2 and
Σ noWtes
Σ
2 m 1/2 --= (1/1))
m
Σ EE
WE
(
20'
RETg
FEE
2
2- 1/2 12/11/2
2 (11--A11+13/22
Ey 20
+
m 2
and furthermore
Σ
Σ
Σ
2 1-+1112
m
(0,= (i+5))
En - 28' +
m
PEIT E
2
< 2 m2 1/2
Σ
m
PELS Ef
S 21/2
Σ
TEN S 2(1K 2 -k|l+
PELS
This concludes the proof.
C.4 Proof of Corollary 4.8
In order to approximate arbitrary v/ E UB, p.0 (X)), we need the following construction instead of Lemma C.5. Note that N' corresponds to the number of B-splines used to approximate the target function and can be freely chosen to match the desired error, which however affects the covering number of Fx.
t + 1/p and v = (pT - d)/2d. Lemma C.11 (Suzuki (2019), Proposition 1). Set m E N, m > For all N' e N sufficiently large and e = N'-r/d(log -2 for any f E g there exists
ReLU network f FUNN (L, W, W.S.M. with
L = loge (3dvm (1 + dm dm/ DE DE-1) ) + 5 [loge (d v m)],
W = -NW..
S= ((I-((LWvv)) - 1) + +1N,,
M = (NV1////))
satisfying I )1 S N/-1/d
Setting N' x 5 d/d/T Also note that from Assumption follows that [l, S Coc C2N N1/2
and applying the covering number bound in Lemma C.6, after some algebra we obtain the following counterpart to Lemma 4.4. Corollary C.12.
For any 8 > 0, Assumption 3 is satisfied by taking
Fx = (I o ool I O = (0,) E (.S,(L
where B3 = N1/2 and
1/2
L 0loog W O()
$ 0 log)z'), log M = O(log dx).
32

---

Also, the metric entropy of FN is bounded as
NH x N
d/r
log
log
log"
1
ÖN
ÖN
Then by combining with Lemma 3.3 and Proposition
3.2 via Theorem 3.1, it follows that
N N2 log + N6
N
V(TN, NT,,Illlloo,
log NN
log + "logg"
NN
and
N
N
R(O) -
log N +
log" + N N-2a/dd /d + N2
n2
n²
22
N
N d/r log
log N
log +
+ log"
+
T
T
ÖN
NN
Substituting ON x N-1-a/d and x N-2a/d concludes the desired bound.
D Details Sequential Input
D.1 Definitions and Results
-mmooohh class. We first define the 7-smooth function class introduced by Okumoto and Suzuki (2022). Let E 2dx and E Nox where N = N NUO and the subscript 0 indicates restriction the subset of elements with finite number of nonzero components. Consider the orthonormal basis (xhrr of ([0, 1]dx00) given as
cos((
Túj <
(x) = IIII
Dny (1z)),
Uro (Iiz)
0.
f=
2 sin (in((nr
Tij
The frequency component 8.(f) of L2 ) is defined
8.(f)
(f. vr) Σ
[2"0-] [2t0-1 ssnull<<
For monotonically nondecreasing function and function class defined as
Fixxx - R and p 2 2, g 2 1, the 7-smooth norm :NN
|I [[bx); =
Σ
and
(f 1]xx00)) [1fl | < <0).
The 7-smooth class over inite-dimensional input space [0, 1]dxm is similarly defined.
In particular, consider two specific cases of for the component-wise smoothness parameter
Rdxx0 for which we also define the corresponding degrees of smoothness al E Ezo. Denote by (ā, )= all components of a sorted by ascending magnitude.
=
Mixed smoothness:
7(s) (a, s), at ā max,,j Aij.
Anisotropic smoothness: 7ss) max;, OsjSijj at -Et, 0.j 111-1
Furthermore, the weak no-norm of a is defined as ||a|lu == sup, j" for 17 0.
33

---

Piecewise 7-smooth class. The piecewise y--smooth class is an extension of the y-smooth class allowing for arbitrary bounded permutations of the tokens of an imput (Takakura and Suzuki, 2023). For threshold V E N and an index set A, let {Ωx [aa)xEe be a disjoint partition of supp and (aA a set of bijections from [2V + to [-V VJ. Further define the permutation operator II: supp xx + (2V++++1) as
[1(x) Tx (I), 3n (2V+1)))
if S2x
Then the piecewise y-ssmooth function class is defined as
p. = 1 1 - / / F (Px), (.(Px) < <0o),
where
1/9
1l0l) =
Σ
SENO V.V.
Next, state the set of assumptions inherited from Takakura and Suzuki (2023). In particular, the importance function makes precise a notion relative importance between tokens which is preserved by permutations.
Assumption 5 (smoothness and importance function). < 5 2 and:
The smoothness parameter a satisfies ||a: lott S and oxg = ) for some vj > For mixed smoothness, we also require i1 < 02.
2. There exists a shifteqquivariant map P supp + R such that Po E U(F g).g). |Pol| |l < 1 and Ω2 = {o E supp Px p(z)=x(1) > ... ((2)) for all E A. is moreover well-separated, that is (1()) ((x)xx(+11 Cyv for Cp. 0.
We focus on parameter ranges < S and rj > strictly for simplicity of presentation, but the cases q 1,g > 2 and > 0 can be handled with some more analysis. Note that > ensures at > 0 for anisotropic smoothness.
Additionally, the assumption pertaining to our ICL setup is stated as follows.
Assumption 6. For Zdxx the coefficients 3, corresponding to th are independent and satisfy for Nxx0 such that the frequency component 8z(f) contains the element thr.
Eg[3,]= = O, Eg[33] S 2 (2+1/a" (2+1/a")(()) (r(())()))+
(22)
Also E IN holds, for example Px is bounded above and below with respect to the product measure xdx on B(0,, 1] of the uniform measure on B B(0, 1)).
We then obtain the following result for ICL with transformers:
Theorem D.1 (minimax optimality of ICL for sequential input). Let F = = E U ((9g,())) [| S B} for some B > 0 where 7 corresponds mixed or anisotropic smoothness. Suppose Assumptions 5 and 6 hold. Then for Z N log N we have
(Px))
log N N2v(1+1/a") polylog(N)
R(θ) N 20
T
Hence if Z nnViv/a and N x naa 1, ICL achieves the rate n polylog(n).
D.2 Proof of Theorem D.1
Since the system (1b,), ) is orthonormal, we may take N = 1, = N following Remark 2.1. We mainly utilize the following approximation and covering number bounds.
Theorem D.2 (Takakura and Suzuki (2023), Theorem 4.5). For a function F E U(P (Px)),
|| [[==(xx) (Px) S. B and any K > 0, there exists transformer F E FTE(J,U, D, H. M. such that
|o - F $2
34

---

where
v logV, D S K2 log V, H S (log K) LSK2, W W 2k/ K2in, 5 2k/a K2t2/1 log M x K V log log V. Theorem D.3 (Takakura and Suzuki (2023), Theorem 5.3). For e > 0 and 2 1 it holds that
JSK' logU S V
(DLWWM M
Oog.(FirJJUuu) H, 1I 1)) & JRL(S + HD*) ) log
To analyze the decay rate in the y-smooth class, we approximate function f E L2 1]dxa) by the partial sum of its frequency components up to 'resolution' K, measured via the y function:
Rx())= = E 5.(5).
7()CK
The basis functions e are thus ordered primarily ordered by increasing 7()). Lemma D.4 (Okumoto and Suzuki (2022), Lemma 17). For 15 S. 2 holds that q
II - Rx (xILLL(() $ [1
Note that if (8)) < K then 8ij < K/aij S K/ |i]" for all i, for both types of smoothness and so ||s|lo S dk 1/9 In addition, the number of basis functions vr used in the sum for 6.()) is exactly 2||+11 = Ik, 2 Theorem D.3 of Takakura and Suzuki (2023) shows that the number of basis elements used in the sum Rx (f') satisfies
N
Σ 7()(K
21le11 $ 2k/a
for both mixed and anisotropic smoothness. Hence the N-term approximation error decays as N N so that the choice at leading to the assumed variance bound N-2n" x (2+1/a1)) in (22) justified. Moreover for large K,
Σ
Σ
1 1 I
Σ 211+11: (V2ll 2 {(s)<
<())< K 12"0- 120="Islru 1sln
since ||l|o = ||s|lo. so that (2) of Assumption satisfied with r = 1/2. The second part of Assumption holds since (1rr) orthonormal w.r.t. dxx Furthermore, the discussion thus far immediately extends to the piecewise 7-smooth class for any partition {Ax by composing with the permutation operator 11.
We proceed to use Theorem D.2 to approximate each basis function v o II up to resolution K. Moreover, we can see from the proof of Lemma 17 of Okumoto and Suzuki (2022) that do not need to account for the sup-norm scaling of vù, and thus it suffices to find the parameter K' E N such that the approximation error 2- K'' x 8x. Hence combining Theorems D.2 and D.3, we conclude that
(),,,) S KB2K 22 lat 2222/ K' log
K'log
1/a polylog
N,
log
5N
NN
sufficient to satisfy Assumption 3. Therefore, we can now apply our framework with By x to obtain the bound
N
N N
R(Ô)
log N log"
+ 2-
+N288
n²
N
N
1/a1 polylog (N, N, bx
log
+ oN
log
+e.
E
Substituting ON x NN11oa and x N 2a concludes the thcorem.
35

---

Query Prediction
Query
Guery Prediction
Saf-Attentin (Lineor)
S4mentttoo (Sftmaa))
Feed (FelLu
Encocer Stort
Se fdterntinn (So0mma))
CNN Soook
(Pot
ward (P
(RoLLu)
DAN
Fenettorwend (Pot L.)
Feedhrreant (fett
Sel Aitertioon (Sctlimss)
Soltmas
Transformer
Figure Architecture of the compared models. Each model contains two MLP components, all attention layers are single-head and LayerNorm is not included. (a). implement the simplified reparametrization for attention, while all layers in (c) utilize the full embeddings. The input dimension is 8 and all hidden layer and DNN output widths are 32. The query prediction is read off the last entry of the output at the query position.
train loss
test less
15
Incer 20P.
cfft
10
10
20
30
20
20
30
<p0075
<p0075
Figure 2: Training and test curves for the ICL pretraining objective. We use the Adam optimizer with learning rate of 0.02 for all layers. For the task class we take 1, p q = oc, n 512 and generate samples from random combinations of order wavelets.
E Numerical Experiments
In this section, connect theoretical contributions to practical transformers by conducting experiments verifying our results as well as justifying the simplified model setup and the empirical risk minimization assumption. We implement and compare the following toy models: (a) the simplified architecture studied in our paper; (b) the same model with linear attention replaced by softmax; and (c) full transformer with 2 stacked encoder layers. The number of feedforward layers, widths of hidden layers, learning rate, etc. are set to equal for a fair comparison, see Figure for details.
Figure shows training (solid) and test loss curves (dashed) during pretraining. All 3 architectures exhibit similar behavior and converge to near zero training loss, justifying the use of our simplified model and also supporting the assumption that the empirical risk is minimized. Moreover, Figure 3 shows the converged losses over a wide range of N, n, T values. We verify that increasing N, n
150
prompe longth
tort
10%
12-
30
Figure 3: Training and test losses of the three models after 50 epochs while varying (a) DNN width N: (b) number of in-context samples n; (c) number of tasks T., For (a), the widths of all hidden layers also vary with N. We take the median over runs for robustness.
36

---

leads to decreasing train and test error, corresponding to the approximation error of Theorem 3.1. We also observe that increasing T tends to improve the pretraining generalization gap up threshold. confirming our theoretical analysis of task diversity. Again, this behavior is consistent across the 3 architectures. We note that in the overparametrized regime when the number of total parameters Z nT,, the trained model is likely not the empirical risk minimizer, which may also contribute to the large error for large N or small n,
F Proofs of Minimax Lower Bounds
F.1 Proof of Proposition 5.1
In this section, we develop our framework for obtaining minimax lower bounds in the ICL setup by adapting the information-theorctie approach of Yang and Barron (1999).
904 20/ (f41)) be 6n -papkingng of the class F with respect to the -no) such that Let {(1bb)
| (0 3 (1'')) (120()) 2 82 1 < s M,
where M is the corresponding packing number. Then we have the following proposition as an application of Fano's is inequality (Yang and Barron, 1999).
Proposition F.1. Let θ be a random variable uniformly distributed over (() 3/41)) Then, it holds that
82
(1-Ex
Ex Exxxxxxxxt((0 (O, y ( (1T++1)] + log log M
inf sup ED.. T IlI - f (() Da. + F
2
where 1xor++1)( (O, y (1:T+1) is the mutual information between θ y (1:T+1) 1) for given X (1:++1),
The mutual information (xar+1) (0, y (1:41)) is formulated more concretely as
Σ w(0) / p(y(1:+1100 x(::++1))oo log
(gg x(:++1)
(1T+)
Pw (1:T++1)
X X(:++1)
@Esupp θ
where 00 X) is the probability density of y conditioned on 0, X and Pie is the marginal distri- bution of y (1:T+1) where w(-) N is the probability mass function of θ (i.e., --( Eocsupp e w (0)p(-100 x(IT++))). We let P Py0e (and P Py( be the distribution of (0) condi- tioned on 0, (t) (and (1:t)) respectively, and let
M
1 M
P Pynr++
Poor+1po00)
be the marginal distribution of y (1:+1) conditioned on (1:++1))
j=m Next, we define the set {
Q1 to be a cooverin of FN w.r.t the norm d(v. =
/ Ez [[x((x)> [ with en, number Q1. and {3 to be a cn,2-covering of B w.r.t the T,2 norm with cn.v-covning number Q2. By taking all combinations of (176), }00) for 1 S s Q1 and S j S Q2. we obtain the covering (06) )== with respect to the quantity et = 03 + C2 where Q Q2Q₂ and each g(i) is given by (()) (3)61, ((2)) for some indices and jz.
Then as in the discussion of Yang and Barron (1999), the mutual information bounded by
Ixar+nn g (1:++1))
1
D(P y ( (
M
j=1
1
(1:++11011)11 D(Perrr4noo111aaaa)))
D(P
D(P
M
37

---

where D(-II-) is the Kullback-Leibe Leibler divergence and Pa P = à [ P g114+118800 because
P Pyorr+ minimizes the right hand side. If we let
((j) == arg min D (PPyrr+appos))
|| [| P p)rr-)(())
ggk5
then each summand of the right-hand side is further bounded by
log D(P ((TPttt)))))))) y
Moreover, for 0 = ( (((+)) it holds that
ply (1:T+1) 0, x (1:T+1)
T
II plu 10b (1) p(y (bb B(T+1), x(T+1))
T
II
/ ply 1bb, 300 (p)( plyy B(T+1), x(T+1)).
Then the Ki-diiereence can be bounded as O(Poor+ty y
P Poooreeelleecco poppsso ) + D (P (Per+onpas poropaann (33
D PPooosos a p pooson) ) Pa (2())))d33())
D (PrrtHnooon,))) 2/2 IP
where the joint convexity of KL-divergence was used for the last incquality. Since the observation noise is assumed to be normally distributed, the integrand KL-divergence can be bounded as
D
( (Prro a PIl p50p)1)))
1
(T())
3
20
Hence, its expectation with respect B, (1) becomes
n
no? 20 2
Ex0o,8 (D (P (Prroeet,, .ll (ylParo = 20 In the same manner, we have that
|,50ا) - 18
22(xx)) S
D (P y(Tl (6)))) 2922 ||P y po
( (
Bloti0 (aN))) )²
TT41
20
(244), - 344511) (a
]²
+ Σ
1
( ( (v)) -3000)0))))
(x.))) (2)²))))
2
20
1=1
==1
The expectation of the right-hand side with respect to ((++1) (زاو
PT+1 is bounded as
[ (P, (Pacttooou
(0 .51(() )
E Ex.+0.00)
264 |P
Cen
20 P )lm(1)) 12 1
20 - 3(x600
C2n 2 +
202 0 = 20 n
n
n
20 2,
Therefore, the expected mutual information can be bounded as
nT
Ex (0, y (1:++1)) < log Q + log Q2 +
02 n
2
202
20 fn.
Applying Proposition F.1 together with (7) concludes the proof.
38

---

F.2 Lower Bound in Besov Space
Here, we derive the minimax lower bound when JF U(BB,)()) (2)). Recall that in this setting 8 = a/d. We fix a resolution K and then consider the set of B-splines w E Tik of cardinality
N" = 2 Considering the basis pairs (w (,K,1 - ( k.2....... ...., 1w, KKN'), we can determine which one is employed to construct the basis vb0), The Varshamov-Gilbert bound yields that for = {0. 13 N /2, we can construct a subset St' = fwi..... Wg C Ω such that [S2] = 2 /16 and w # w' 52' has Hamming distance not less than N /16 Using this S2, we set N = N2/2 and M 2 /16 and define (zb0)) as w. = 2 if , = 0 and w! = wk if W = 1.
We use the same B-spline bases with resolution more than for (5( (a 2 N) across all j. By the construction of (z)10),, if we set ((1) = (az..... og. 0,.00..... then
||B0)T g00 10' 11 2 o2N/8.
Hence, for 6
S L0.N/8 S 1, the 6np bh-packing number is not less than 2 Moreover, the logarithmic
6, -ackkig number of ab()) B E B} for a fixed j is O(min standard argument.
log((/6,,)) by the
Hence taking 8n = N we obtain log M ズ N and the upper bound of the covering numbers log Q + log Q2 S N for oōo2,1 1 S 6% and eñ, C6 where C is a constant. Then, by choosing C
appropriately and E,, & N 1-a (so that log Q1 2 N), as long as
n + no < log Q1 + log Q2 S N
is satisfied, the minimax rate lower bounded by 82 Taking N x n we obtain the lower bound
2 n Zo1..
(23)
F.3 Lower Bound with Coarser Basis We consider generalized setting where X' = Rd x Rd ... x Rd and take (66 E U(B p.g (R"))
(N +1+1) +iiins
and assume that 31 [-1,,] and B3 E [- where o3 =
Since the logarithmic Ê E--ooveiing and packing numbers of U(B (R²)) are ( O(TT4/T) 4/T), those for the basis functions on
No3 j 2....,, N become O(Ne,d/1) and those for B are O(N log(1 + = Therefore, by taking * NoT see that
d/f
No²
n + (3 + n= n S E
d/r
+N N
Ex.1
+N log
1+
VN
should be satisfied. Moreover, by taking (2r+0)/T we can balance both sides. In particular, we may set
x 1/nI and Eh x N + N 2522)22)))
mn.1
N
1 x (nT)
n.
2
Taking the balance with respect to to maximize 2. we have x n no and 2 x (nl)) offa. Therefore, the minimax rate is lower bounded
2a 22 ー (1 (1) + 2n ~ n 2042 + ( 2tt -
(24)
F.4 Lower Bound in Piecewise y-smooth Class
Suppose that utilize the basis functions up to resolution K. Then, by the argument by Nishimura and Suzuki (2024), the number of basis functions v,, in the K-th resolution is N' x 2k/a", Moreover, the 8, -aacking number of the smoohh class is also lower bounded by
log M 2 N' 'ol')
(25)
39

---

Here, by noticing the approximation error bound in Appendix D.2, we take N' = on 1/a1 where the basis functions are chosen from the K'th resolution. As in the case of the Besov space, we construct (15()) 1== where M' = 2 /16 and (:6) (a) E R for N = /2/2 and |bb "0'')1E 2 N/8 for * Following the same argument as in the Besov case, we need to take 5n, and En, as
n nE X on 1/a 8,/1/a²
up to logarithmic factors, This is satisfied by taking o = C8 x n
24 with a constant and
2
2a
balancing N so that 03 = (nT) (25) yields that the minimax lower bound given by
2a 2 0
TT n -="-1 Combining this evaluation and
2x1
n
2ul+1 11
(26)
40

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the Our Contributions paragraph for details.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See the Limitations paragraph.
41

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Assumptions 1, 3, 6. All proofs were provided the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
See Appendix E, Figure 1.
Guidelines:
The answer NA means that the paper does not include experiments.
42

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
All experiments are toy simulations and data is i.i.d. random.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //tips.cc/pppppeee wttpccccccpppcccccc.cceeeooceece
Cooeeubmiii wewbbbmsssiii ssissssonoo seiniiossiiiyiyyooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
43

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: See Appendix E, Figure 2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The median over 5 runs is reported in Figure 3.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
All experiments are toy simulations.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
44

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tp:///nnu......ee cc cc/public/ aethhicsCuieelneee
Answer: [Yes]
Justification: The research is thcoretical and raises ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The research is theoretical and raises concerns societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
45

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
46

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
47


Reviews:
[{"review_id": "3YmdnIpeNc", "reviewer": "Reviewer_KRWK", "summary": "This paper studies in-context nonparametric learning using transformers. In the setting used in the main result of the paper, the transformer is trained on a dataset consisting of multiple sequences/tasks. For each task, the target function $F_\\beta$ is drawn from the span of a certain countable set of functions - in the setting used for the main result of the paper, the target function is drawn from a Besov space spanned by a B-spline wavelet basis. The task then consists of multiple in-context pairs $(x_k, y_k)$, where $y_k$ is $F_\\beta(x_k) + \\xi$, where $\\xi$ is random noise. Certain technical assumptions are made on the basis functions $\\psi_j$ and the coefficients $\\beta_j$: the $\\psi_j$ are assumed to have a property that is similar to linear independence/orthonormality, while the $\\beta_j$ are assumed to decay at a certain rate.\n\nThe model in this paper's setting consists of a feature map $\\phi$ applied to all of the $x_k$, followed by a linear attention layer applied to the $\\phi(x_k)$ and the $y_k$. The feature map $\\phi$ is assumed to be expressive enough to approximate the $\\psi_j$. In the main result of this paper, $\\phi$ is chosen from the class of deep neural networks (DNNs) with a logarithmic number of layers (logarithmic in the size of the feature map), and $O(1)$ width and $O(1)$ entries per layer. The class of feature maps $\\phi$ is denoted as $\\mathcal{F}_N$, and the overall model class is denoted as $\\mathcal{T}_N$.\n\nThe main result of the paper, Theorem 4.5, is that with a sufficient number of tasks during pretraining, in-context learning with transformers will achieve the optimal minimax risk. This is shown as follows. Theorem 3.1 first gives a bound on the expected test loss in terms of the covering number of the model class $\\mathcal{T}_N$, and the minimum test loss achievable by some member of $\\mathcal{T}_N$. Next, the paper gives a particular construction for a set of parameters which achieves low test loss. The weight matrix for the linear attention layer is chosen similarly to the optimal weight matrix given in Zhang, et al. (2023) and nonlinear feature map outputs a subset of the basis functions.\n\nAdditional results are also given. This paper shows how the curse of dimensionality can be avoided when the target function is drawn from an anisotropic Besov space. Also, under certain assumptions, even if the target function is drawn from a Besov space with smoothness $\\tau < \\alpha$, it is possible to achieve the same minimax rate as in the case where the target function is drawn from a Besov space with smoothness $\\alpha$. Finally, the paper gives similar results in the setting where the tokens are themselves sequences of unbounded length, and gives minimax lower bounds that match the upper bounds.", "questions": "- In Lemma 4.4, how important is the assumption that the width/sparsity of the deep neural network is $O(1)$? Would the guarantee obtained in Theorem 4.5 change if the deep neural network is allowed to have more nonzero entries?\n- Could the setting in this paper be considered similar to the linear regression setting studied by previous works such as Zhang, et al. (2023), with the difference being that the linear regression weight vector is replaced by the vector $\\beta$ of coefficients for the basis functions?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- This work seems to be the first to study in-context learning using transformers in Besov spaces (prior work studied settings such as regression with DNNs).\n- The paper is very well-written.", "weaknesses": "I think the main weakness is that the techniques used to show Theorem 4.5 are somewhat standard. \n- Theorem 3.1, which shows that the empirical risk minimizer achieves good test loss, seems to be using relatively standard arguments from previous work, based on covering numbers.\n- The construction used to show that low approximation error can be achieved also seems somewhat straightforward. The weight matrix for the attention layer is chosen similarly to Zhang, et al. (2023), and the feature map outputs a subset of the basis vectors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your through review of our work! We hope our responses can help clarify some important points.\n\n**Weakness 1.**\n\nTheorem 3.1 is indeed a standard result, as we have indicated it is a straightforward adaptation of Lemma 4 of Schmidt-Hieber (2020). While it is only the first step of the proof of the main results, we included the statement to explicitly show how the in-context and pretraining generalization gaps arise from different elements of the risk: the former manifests when evaluating the approximation error w.r.t. $n$, while the latter is the usual entropy term.\n\n**Weakness 2.**\n\nThe attention matrix construction can be seen as an extension of Zhang (2023), however we urge the reviewer to take the following points into consideration.\n\n* The optimal construction is completely determined for a linear attention layer since the L2 linear regression loss is convex; even the construction in Zhang et al. (2023) is stated to be a generalization of Oswald et al. (2023). So while we agree the construction is not surprising, it is an important step allowing us to reduce to the analysis of the DNN module which facilitates the main risk analysis. Conversely, Zhang and Oswald do not consider the MLP at all and only study the attention matrix.\n* The given form (line 174) is only an example construction to upper bound the empirical loss. Unlike Zhang, we do **not** claim the ERM or optimization dynamics must result in such a simplified form, which may not be true in a deep Transformer setting.\n* The idea of approximating the target function with a well-chosen basis is of course fundamental to all functional analysis and is not unique to our approach. Indeed, our goal is to **establish a strong connection between ICL and ordinary supervised regression** by isolating the pretraining generalization gap. We dive deeper into this idea by pointing out a new limitation of ICL stemming from non-adaptive function approximation (Remark 4.6).\n* Moreover, a **unique technical difficulty** that we newly uncover and address is the necessity of the inverse covariance matrix $\\Psi_N^{-1}$ to approximate the attention matrix. Wavelet systems of Besov-type spaces are fundamentally co-dependent and form a multi-resolution scheme which makes $\\Psi_N$ singular and affects various decay rates. This was not a problem in Zhang's work ($\\Lambda$ was simply assumed to be positive definite) nor any existing minimax optimality works (which don't have a product structure). Nonetheless, we were still able to prove optimality by decomposing all splines to the finest resolution and performing the analysis strictly at that scale, hence the additional steps to account for the aggregated coefficients $\\bar{\\beta}$.\n* We have added experiments justifying the use of our simplified transformer model; please see Item 3 of the global response.\n\nWe also implore the reviewer to judge our result not based on the perceived difficulty level of the proof, but its implications towards understanding the effectiveness of in-context learning.\n\n**Question 1.**\n\nThe assumption can be substantially relaxed; the stated form is mostly to clarify the minimum number of essential parameters. Recall that a fully connected network has $S\\sim LW^2$. The dominating term from the DNN entropy (line 675) is $SLN\\log W$, so that letting $S=O(\\log N)$ (fully connected depth $L$ network) would only incur an additional log factor to yield $N(\\log N)^2$. Since the $N^2\\log N$ term from the attention matrix entropy dominates this, the overall bound remains unchanged. The same holds even if width is relaxed to $W=O(N)$, and furthermore even if $S=O(N)$ in this case.\n\nHowever if $W=O(N)$ *and* the network is fully connected, that is $S=O(N^2\\log N)$, the pretraining gap will worsen to around $N^3/T$. This reflects the fact that wavelets are 'easier' to approximate with DNNs than Besov functions are with wavelets.\n\n**Question 2.**\n\nThat is indeed the setup we were aiming for, however please consider our response to Weakness 2 as well as the following points.\n\n* Linear attention has been studied in many other papers including Zhang, Oswald, Mahankali, and Ahn's works (cited in the paper), all yielding similar 'optimal matrix' constructions. As mentioned before, we do not claim originality in this regard. However, our focus is on reduction to the **representational capability of the MLP layers**. Except constructive works such as Bai et al. (2023), The NN+attention setup had only been studied before very recently by Kim and Suzuki (2024), and they only considered a shallow MLP.\n* We also find it illuminating to consider our setup as a deep Transformer with all but the last attention layer removed. Since this simplified model is already in-context sample optimal, we can expect a full Transformer to be the same. Moreover, we indicate how to extend our results to nonlinear attention or multiple attention layers in Item 1 of the global response.\n\nWe have also obtained **improved lower bounds** which reinforce the message of our paper, and newly conducted **numerical experiments** justifying our assumptions and results. Please see Item 2 and Item 3 of the global response for details. We also humbly ask the reviewer to consider raising their score if some of their concerns were addressed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jAwjUlH0hc", "reviewer": "Reviewer_1n5m", "summary": "This work shows that ICL can perform non-parametric regression at an optimal rate.\n\nSection 3 gives an upper bound on ICL error in terms of a metric entropy of the representation class. Section 4 instantiates the bound for DNN representations and shows it to be optimal. Section 4.3 explores ways to reduce the dependence on dimension. Section 5 gives lower bounds for any ICL (not just transformers).\n\nThere is a sufficiently expressive representation class $\\mathcal{F}$ (here we take DNNs) from which we can draw a $\\phi^*$ such that linear attention on top of this solves regression well. In that sense, this paper generalizes the idea from linear attention for linear regression that the attention inverts the data-covariance.", "questions": "A matter of notation: in assumption 1, why aren’t the basis functions the first N functions, rather than the functions from $\\underline{N}$ to $\\overline{N}$? Also, are the functions past $\\overline{N}$ not spanned by the basis? Remark 2.1 offers some explanation. I think it would be helpful to write the main paper in the setting where $\\psi$'s span the space and leave the generalization for the appendix.\n\nWhat role does the sparsity $S$ play, why is it set to be $O(1)$? Isn't is unrealistic that $N$ should scale in $n$ for a real transformer (one of the key selling points about transformers are how the parameters dont scale in the context length)? Do the authors think this is due to the analysis or is it fundamental for attention?\n\nIt would be helpful to instantiate a target function class in the main paper, specify what $\\alpha$ is, etc.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper contains a general analysis of ICL error for regression problems. The comparison to non-parametric rates is interesting and possibly the right way to extend the so far mostly linear analysis in the literature to problems beyond linear regression.", "weaknesses": "This is general analysis of a very specific simplification of the transformer. The setting is that there are trainable layers before the attention layer, and then exactly one linear attention layer. Is there any hope to extend this analysis to more attention layers/ non-linear attention/ constant $N$? When $N$ is constant, the error is constant, which seems vacuous considering everything is bounded. Is that an artifact of analysis?\n\nIs it possible to have a setting where we removed the DNN and force the features themselves to satisfy Assumption 3? Would that reduce to the linear regression setting of prior work? If so, it seems very important to justify how we can find a $\\phi^*$ satisfying Assumption 3 for DNNs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and insightful questions! Our responses are as follows.\n\n* **It would be helpful to instantiate a target function class in the main paper, specify what $\\alpha$ is, etc.**\n\n(We answer this question first to help in understanding our paper.) **Throughout Section 4, we consider concrete task classes including the Besov space, anisotropic Besov space, and piecewise $\\gamma$-smooth function class.** Our main result for DNNs (Theorem 4.5) is stated when $\\mathcal{F}^\\circ$ is the unit ball in Besov space $B_{p,q}^\\alpha(\\mathcal{X})$, which is a very wide function class generalizing Holder and Sobolev spaces; please see Section 4.1 for details. Here $\\alpha$ is the smoothness and $p,q$ are additional parameters controlling spatial inhomogeneity. These relate to the decay rate $s$ of Assumption 2 by $s=\\alpha/d$; the high-level Assumptions 1-3 all follow from Assumption 4 in this setting.\n\nWe also show the curse of dimensionality can be avoided when $\\mathcal{F}^\\circ$ is extended to the *anisotropic* Besov space in Section 4.3. Furthermore, for the multilayer Transformer setting (Section 4.5) the inputs $x$ are sequences and $\\mathcal{F}^\\circ$ is the piecewise $\\gamma$-smooth class, which is a more realistic model for text by allowing the position of important tokens to depend on input.\n\n* **Is there any hope to extend this analysis to more attention layers/non-linear attention/constant $N$?**\n\nPlease see Item 1 of the global response where we address this question in depth.\n\n* **When $N$ is constant, the error is constant, which seems vacuous.**\n\nWhile our bounds (e.g. Theorem 4.5) hold for all $N$, the risk dependency is not an artifact but a natural result of how our task class is set up. After pretraining our transformer has learned $N$ feature maps $\\phi_1,\\cdots,\\phi_N$ and its output $f_\\Theta(\\mathbf{X},\\mathbf{y},\\cdot)$ is always contained in the span of these $N$ functions. However, the true test task $F_\\beta^\\circ$ is randomly chosen from an infinite-dimensional space, and so the $L^2$ regression error is fundamentally lower bounded by its **Kolmogorov width** -- the minimum approximation error by an $N$-dimensional linear subspace -- which scales as $N^{-\\alpha/d}$ for the Besov space. Hence this error is unavoidable for *any* fixed-basis approximation scheme; an implication of our analysis is that Transformers attain this optimal rate (the first term in Theorem 4.5).\n\nBesides the approximation error, the pretraining and in-context generalization errors decrease as $O(1/T)$ and $O(1/n)$, which is still a useful result if one is concerned with improving generalization.\n\n* **Is it possible to have a setting where we removed the DNN?**\n\nIndeed, if we completely remove the DNN and set both the features and basis to be simply the coordinate mappings $x_1,\\cdots,x_d$, this reduces to the class of linear maps in prior works. In a nutshell, our contribution is extending this to infinite-dimensional nonparametric task classes via learnable representations, enabling fine-grained sample complexity analysis and guaranteeing optimality of ICL with deep architectures.\n\n* **It seems very important to justify how we can find a $\\phi$ satisfying Assumption 3 for DNNs.**\n\nThat is exactly what Appendix C.1.1 (Verification of Assumptions) and Lemma 4.4 are for! We show that the abstract Assumptions 1,2,3 are all replaced by the single concrete Assumption 4 when the target class is set to the Besov space. For the multilayer Transformer setting (Section 4.5), Assumption 3 instead follows from Theorem D.2. We will make this point clearer in the paper.\n\n* **Why aren’t the basis functions the first N functions?**\n\nIn fact, this is to address a **unique technical difficulty** that we newly uncover: the necessity of the inverse covariance matrix $\\Psi_N^{-1}$ to approximate the attention matrix. Wavelet systems of Besov-type spaces are fundamentally co-dependent and form a multi-resolution scheme: there are $O(2^k)$ independent basis elements at each resolution $k\\in\\mathbb{N}$, which can always be refined as a linear combination of higher resolution wavelets. This makes $\\Psi_N$ singular and affects various decay rates, so we cannot simply take the first $N$ elements. This was not a problem in prior attention-only works ($\\text{Var}(x)$ was simply assumed to be positive definite) nor any existing minimax optimality works (which don't have a product structure). Nonetheless, we were still able to prove optimality by decomposing all wavelets to the finest resolution -- numbered from $\\underline{N}$ to $\\overline{N}$ -- via the refinement analysis in Appendix C.3, hence the additional steps to account for the aggregated coefficients $\\bar{\\beta}$. While this additional notation may cause confusion upon first reading, we have left it in since specializing to the wavelet system to obtain optimality is an important part of our work.\n\n* **What role does the sparsity $S$ play, why is it set to be $O(1)$?**\n\nThe sparsity bound $S=O(1)$ is merely to clarify the minimum number of essential parameters and can be completely removed. Recall that a fully connected network has $S\\sim LW^2$. The dominating term from the DNN class entropy (line 675) is $SLN\\log W$, so that letting $S=O(\\log N)$ (fully connected depth $L$ network) would only incur an additional log factor to yield $N(\\log N)^2$. Since the $N^2\\log N$ term from the attention matrix entropy dominates this, the overall bound remains unchanged.\n\n(continued in comment)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bohmdIBmr0", "reviewer": "Reviewer_YwVZ", "summary": "This paper explores the ICL capabilities of transformers from a statistical learning theory perspective. It focuses on transformers with a deep neural network and a linear attention layer, pretrained on nonparametric regression tasks from function spaces like the Besov space and piecewise gamma-smooth class. The authors demonstrate that sufficiently trained transformers can achieve or even surpass the minimax optimal estimation risk by encoding relevant basis representations during pretraining. The paper also establish result that explains the pretraining and in-context generalization gaps, which is essential for understanding ICL.", "questions": "While reading this paper, I feel it provides new insights into understanding ICLs. However, I cannot find concrete evidence of how this theoretical framework can offer supportive insights for practitioners using ICL. The simplified model without numerical experiments cannot indicate how real LLMs behave. \n\nCould the authors provide more detailed explanations on how this work connects to the mechanisms of ICL and LLMs in practice?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The topic of this work is both interesting and important, addressing key aspects of ICL in transformers.\n\n2. The results developed, especially Theorem 4.5, are very encouraging and could help the community better understand LLMs and their ICL capacity.\n\n3. The analysis provided is rigorous and sound, offering new tools and methodologies for theoretical analysis in the ICL literature.", "weaknesses": "1. The writing and presentation of the paper need improvement. For instance, in Section 4, the flow feels disjointed, with several results appearing to be stitched together without a clear, organized connection.\n\n2. Although the ICL capabilities of transformers are powerful and of great interest, the simplified transformer model presented in this paper is not very realistic. While it is common to use simplified models for analyzing LLMs, the paper would greatly benefit from numerical experiments demonstrating the claimed theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your through review and helpful suggestions, which have helped us greatly to improve our paper!\n\n**Response to Weakness 1.**\n\nUnfortunately, Section 5 was completed last minute which resulted in the flow of the paper being rather disjoint. Together with improved lower bounds, we restate our take-home message (besides in-context optimality in $n$) as follows. We believe this novel understanding will be helpful to both theoreticians and practitioners.\n\n* (In the Besov space setting) The obtained upper bound $n^{-\\frac{2\\alpha}{2\\alpha+d}}$ when $T\\gtrsim nN$ which is minimax optimal in $n$, has also been shown to be jointly optimal in $n,T$. Hence **ICL is provably optimal in the large $T$ regime.**\n* (In the coarser basis setting) We obtained an improved lower bound $n^{-\\frac{2\\alpha}{2\\alpha+d}} + (nT)^{-\\frac{2\\tau}{2\\tau+d}}$ using the method in Appendix E.3. If $T=O(1)$, this gives the slower $\\tau$ rate, while if $T$ is larger this gives the faster $\\alpha$ rate. This aligns with Corollary 4.9 (which only gave an upper bound), hence **ICL is provably suboptimal in the small $T$ regime.**\n\nWhen combined, these results are stronger than optimality in only $n$. (Since the Transformer requires $n$ in-context samples plus $n\\times T$ pretraining samples, one could argue that standard minimax rates do not apply. However, the above lower bounds do apply rigorously to any meta-learning algorithm in the $n\\times T$ samples.) They also align with experimental observations of task diversity threshold (Raventos 2023), rigorously supporting the importance of varied tasks over increasing prompt length.\n\n**Response to Weakness 2 & Question 1.**\n\nMotivated by your comments on practical relevance, we have conducted new numerical experiments justifying our simplified model setup and the assumption of empirical risk minimization. Figures can be found in the attached PDF of the global response. We implement and compare the following toy models:\n\n* Linear Transformer: the model studied in our paper, where a DNN (2 hidden layers) feeds into a simplified linear attention layer\n* Softmax Transformer: the same model as (a) but with softmax attention\n* Full Transformer: an ordinary transformer with 2 stacked encoder layers\n\nArchitectures are compared in Figure 1. The number of feedforward layers, width of hidden layers, learning rate etc. are set to equal for a fair comparison.\n\n* Figure 2 shows training (solid lines) and test loss curves (dashed lines) during pretraining. All 3 architectures exhibit similar behavior and converge to near zero training loss, justifying the use of our simplified model and also supporting the assumption that the empirical risk can be minimized.\n* Moreover, Figure 3 shows the converged losses over a wide range of $N,n,T$ values (median over 5 runs). We verify that increasing $N,n$ leads to decreasing train and test error, corresponding to the approximation error of Theorem 3.1. We also observe that increasing $T$ tends to improve the pretraining generalization gap up to a threshold, confirming our theoretical analyses. Again, this behavior is consistent across the 3 architectures.\n* Although the dimensions and architectures are relatively small due to limited time and compute, we plan to scale up our experiments and add them to the final version of the paper.\n\nPlease also see **Item 1** of the global response where we discuss how our theoretical results may be extended to more complex transformer architectures. We also humbly ask the reviewer to consider raising their score if their concerns were addressed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HbWrbpdS9o", "reviewer": "Reviewer_eg5H", "summary": "This paper analyzed in-context learning of a transformer consisting of a DNN and a linear attention layer pretrained on nonparametric regression tasks.  The authors derived a general bound on the generalization error consisting of the approximation error, in-context generalization error and pertaining generalization error. They also showed that the icl prediction given by the pretrained TF is minimax optimal when the nonparametric regression functions are from the Besov space or  piecewise  $\\gamma$-smooth class.", "questions": "1. The functions in the Besov space are well approximated by linear combinations of finite number of basis functions in the space. Suppose now the feature map $\\phi$ can well-approximate the basic functions (assumption 3) and is fixed to be $\\phi^*$, and only the linear weight in the attention layer is trainable. I wonder how much differences there are between this simplified setting and previous works on ICL for linear regression.\n\n2. I wonder if it is possible to theoretically analyze the training dynamics under the setting where the feature map is given and fixed and only the linear attention is trainable.", "limitations": "As the author already mentioned, this work only analyzed the generalization error of the ERM but not the training dynamics. The transformer model in this work is limited to a single layer of self-attention and does not include the softmax activation and the MLP layer.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and the theoretical results are solid. The authors made reasonable assumptions on the regression tasks and the TF function class that do not significantly simplify the problem. From a technical perspective, this work leverages the approximation ability of DNNs and the ICL ability of single-layer linear attention to derive the near-optimal generalization error bounds. A few generalizations are also considered, e.g., anisotropic Besov space and piecewise  $\\gamma$-smooth class.", "weaknesses": "The paper considered a model different from the standard TF models in practice, in the sense that a trainable DNN-based feature map is applied to the tokens before the attention layer. The proof in this works heavily rely on this feature map, as it is used to approximate the basis functions of the Besov space.\n\nLack of simulation results. The work showed that the empirical risk minimizer is minimax-optimal but didn't analyze the training dynamics. So it would be good to have empirical evidence showing that pretraining indeed finds an empirical risk minimizer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and positive assessment of our theoretical contributions! Here are our responses to the comments.\n\n**Weakness 1 & Limitations.**\n\nWhile the reviewer mentioned in the Limitations section that our model does not include the MLP layer, we find it illuminating to consider our setup as a deep Transformer with all attention layers (except the last one) and layernorm/output layers removed, so that the MLP layers have combined into a feedforward DNN. Since this simplified model already achieves optimal ICL, we can expect a full Transformer to achieve the same. Moreover, our techniques can be partially applied to settings with multiple attention layers or nonlinear (e.g. softmax) attention; please see **Item 1** of the global response where we address this in depth.\n\n**Weakness 2.**\n\nMotivated by the reviewers' comments, we have conducted new numerical experiments justifying our simplified model setup (Weakness 1) and the assumption of empirical risk minimization (Weakness 2). Please see **Item 3** of the global response for details.\n\n**Question 1.**\n\nIndeed, if we completely remove the DNN and set both the features and basis to be simply the coordinate mappings $x_1,\\cdots,x_d$, this reduces to the class of linear maps in prior works, e.g. Zhang et al. (2023). In a nutshell, our contribution is extending this to infinite-dimensional nonparametric task classes via learnable representations, enabling fine-grained sample complexity analysis and guaranteeing optimality of ICL with deep architectures.\n\n**Question 2.**\n\nIf the features are fixed, the dynamics are arguably less interesting. Since the attention layer output is linear in the attention matrix $\\Gamma$, the pretraining loss function is always convex (ignoring clipping). Hence gradient descent is easily shown to converge exponentially fast to a minimizer regardless of the number of samples, random initialization, etc. which can also be written down explicitly by computing the matrix derivative of line 145 to zero and solving for $\\Gamma$.\n\nThe linear regression setup of the previous work by Zhang is not quite as simple, in that they also include a scalar multiplier $\\sigma$ representing the value matrix and study the joint dynamics. In that paper, convergence is proved by showing a PL inequality under restrictive assumptions on initialization. Rough calculations show that a similar result can be obtained in the fixed feature setting as well, justifying the fixed value matrix assumption in our model. Some other works also indicate that the attention mechanism may possess structures favorable for optimization; see our discussion in Section 1.1. Nevertheless, the main novelty of our work comes from incorporating the representational capability of the MLP layers, for which a dynamical analysis is unfortunately still out of reach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## 1. Extending to Multiple/Nonlinear Attention

As reviewers have noted, our setup builds on previous works which establish ICL of a single attention layer as linear regression in order to extend to complexity analysis of nonparametric regression. ICL of multiple/nonlinear attention layers can be fundamentally different, possibly exhibiting complex behavior such as induction heads or data clustering which are not yet well understood. Nonetheless, our techniques may be partially applied to these settings as follows.

**Multiple attention layers:** We consider a setup with multiple attention layers in Section 4.5, where the preceding Transformer module performs dynamical feature extraction and the final attention layer performs regression based on the learned representations. This aligns with the empirical observation by Guo et al. (2024) that lower layers of Transformers learn representations of the input and upper layers perform linear ICL.

We also find it illuminating to consider our setup as a deep Transformer with all but the last attention layer removed, so that the feedforward layers combine into a deep MLP. Since this simplified model already achieves sample optimal ICL, we can expect a full Transformer to achieve the same.

**Nonlinear attention:** The simplest approach is to linearize the kernel, for example by taking a small rescaling factor $\gamma$ and approximating $e^{\gamma x^\top\Gamma x'}\approx 1+\gamma x^\top\Gamma x'$. Ignoring the normalizing factor, this shows that nonlinear attention has at least as much expressivity as linear attention. Moreover, linear attention has been empirically shown to capture many other prominent aspects of softmax attention (Ahn et al. 2024).

However ideally we want to characterize the full expressive capability of nonlinear attention. To this end, we can take the following kernel-based approach. By introducing an additional kernel transformation $K(x,x')$ such as the RBF kernel $e^{x^\top\Gamma x'}e^{-\lVert x\rVert_\Gamma^2/2}e^{-\lVert x'\rVert_\Gamma^2/2}$ for (rescaled) softmax attention, we can use Mercer's theorem to decompose $K(x,x') = \sum_{j=0}^\infty \lambda_j e_j(x)e_j(x')^\top$ and approximate $K$ using the top few eigenfunctions $e_j$. For example for the RBF kernel, $e_j$ is an appropriately scaled Gaussian density times the $j$th Hermite polynomial.

Then the main problem is to evaluate the approximation capability of the maps $e_j\circ\phi$ composed with the DNN module. This can be done assuming some compatibility conditions between the kernel eigenfunctions and target class basis functions. (This is particularly straightforward if e.g. the kernel is such that $\lambda_j$ is learnable, so that the terms can be considered separately in $j$.)

## 2. Take-home Message

Together with improved lower bounds, we restate our take-home message (besides in-context optimality in $n$) as follows. We believe this novel understanding will be helpful to both theoreticians and practitioners.

* (In the Besov space setting) The obtained upper bound $n^{-\frac{2\alpha}{2\alpha+d}}$ when $T\gtrsim nN$ which is minimax optimal in $n$, has also been shown to be jointly optimal in $n,T$. Hence **ICL is provably optimal in the large $T$ regime.**
* (In the coarser basis setting) We obtained an improved lower bound $n^{-\frac{2\alpha}{2\alpha+d}} + (nT)^{-\frac{2\tau}{2\tau+d}}$ using the method in Appendix E.3. If $T=O(1)$, this gives the slower $\tau$ rate, while if $T$ is larger this gives the faster $\alpha$ rate. This aligns with Corollary 4.9 (which only gave an upper bound), hence **ICL is provably suboptimal in the small $T$ regime.**

When combined, these results are stronger than optimality in only $n$. They also align with experimental observations of task diversity threshold (Raventos 2023), rigorously supporting the importance of varied tasks over increasing prompt length.

## 3. Numerical Experiments

Following comments by reviewers on the lack of experiments connecting our analysis to practical transformers, we have conducted new simulations justifying our simplified model setup and the assumption of empirical risk minimization. Figures can be found in the attached PDF. We implement and compare the following toy models:

* Linear transformer: the model studied in our paper, where a DNN (2 hidden layers) feeds into a simplified linear attention layer
* Softmax transformer: the same model as (a) but with softmax attention
* Full transformer: an ordinary transformer with 2 stacked encoder layers

Architectures are compared in Figure 1. The number of feedforward layers, width of hidden layers, learning rate etc. are set to equal for a fair comparison.

* Figure 2 shows training (solid lines) and test loss curves (dashed lines) during pretraining. All 3 architectures exhibit similar behavior and converge to near zero training loss, **justifying the use of our simplified model** and also supporting the assumption that the **empirical risk can be minimized**.
* Moreover, Figure 3 shows the converged losses over a wide range of $N,n,T$ values (median over 5 runs). We verify that increasing $N,n$ leads to decreasing train and test error, corresponding to the approximation error of Theorem 3.1. We also observe that increasing $T$ tends to improve the pretraining generalization gap up to a threshold, confirming our theoretical analyses. Again, this behavior is consistent across the 3 architectures.
* Although the dimensions and architectures are relatively small due to limited time and compute, we plan to scale up our experiments and add them to the final version of the paper.

Meta-review: This paper develops generalization bounds for 1-layer transformers for nonparametric regression tasks.  The authors show that one can achieve optimal rates through the forward pass of a simple 1-layer linear transformer provided the inputs are "tokenized" correctly via their feature maps.  I think this work provides a nice contribution to our understanding of the power of the forward pass of transformers to implement complex algorithms and the statistical complexity of a natural task.  I recommend acceptance.
Decision: Accept (poster)