Transformers are Minimax Optimal Nonparametric In-Context Learners

Authors: juno  kim
tai  nakamaki
taiji  suzuki
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:55:41

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.

Main paper: 
 introduction: 
 Large language models (LLMs) have demonstrated remarkable capabilities in understanding and generating natural language data. In particular, the phenomenon of in-context learning (ICL) has recently garnered widespread attention. ICL refers to the ability of pretrained LLMs to perform a 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 fewshot prompting is especially effective in large-scale models (Brown et al., 2020) and requires only a couple of examples to consistently achieve high performance (García et al., 2023) . In contrast, Raventos et al. (2023) demonstrate that sufficient pretraining task diversity is required for the emergence of ICL. However, we still lack a comprehensive understanding of the statistical foundations of ICL and few-shot prompting.A 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 L2 pretraining loss implements one step of GD 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 to the context length (Zhang et al., 2023) and number of tasks (Wu et al., 2024) have been obtained.Other works have examined ICL of more complex multilayer transformers. Bai et al. (2023); von Oswald et al. (2023) give specific transformer constructions which simulate GD in context, however it is unclear how such metaalgorithms 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 a separation where lower layers transform the input and upper layers perform linear ICL. Recently, Kim & Suzuki (2024) analyzed a model consisting of a shallow neural network followed by a 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 a transformer consisting of a deep neural network with N -dimensional output followed by one linear attention layer. The model is pretrained on n input-output samples from T 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. The bound consists of an approximation and in-context generalization gap, dependent on n, N , and a pretraining generalization gap, dependent on T, N . We also derive an information-theoretic lower bound for the minimax risk.• In the Besov space setting which includes the Hölder and Sobolev spaces, we show that ICL with deep ReLU networks achieve nearly minimax optimal risk n -2α 2α+d 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 of ICL at large scales.• We show that ICL can improve upon the a 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. At the same time, we identify a weakness of meta-learning schemes in certain smoothness regimes.• We extend the optimality guarantees to nearly dimensionindependent rates in the anisotropic Besov space and also to learning sequential data with transformers in the piecewise γ-smooth function class, further justifying the efficacy of ICL in extremely high-dimensional settings.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 γ-smooth class settings and show that transformers can achieve or exceed the minimax optimal rate in context. In Section 5, we derive minimax lower bounds. All proofs are deferred to the appendix.Meta-learning. The theoretical setting of ICL is closely related to meta-learning, where the goal is to infer a shared representation ψ • with samples from a set of transformed tasks β ⊤ i ψ • . When ψ • is linear, fast rates have been established by Tripuraneni et al. (2020) ; Du et al. (2021) , while the nonlinear case has been studied by Meunier et al. (2023) where ψ • is a 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 a 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 in the Besov space and thus achieve the minimax optimal rate. This has been extended to the anisotropic Besov space (Suzuki & Nitanda, 2021) , convolutional neural networks for infinitedimensional input (Okumoto & Suzuki, 2022) , and transformers for sequence-to-sequence functions (Takakura & Suzuki, 2023) .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 & Suzuki (2024) considered a compound transformer equivalent to ours with a 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. 
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 ⊆ R d be the input space (d is allowed to be infinite), P X a probability distribution on X , and(ψ • j ) ∞ j=1 a fixed countable subset of L 2 (P X ). A regression function F • β : X → R is randomly generated for each task by sampling the sequence of coefficients β ∈ R ∞ from a distribution P β on B(R ∞ ); the class of tasks F • is defined as F • = F • β = ∞ j=1 β j ψ • j β ∈ supp P β ,endowed with the induced distribution. Each task prompt contains n example input-response pairs {(x k , y k )} n k=1 . The covariates x k are i.i.d. drawn from P X and the responses are generated asEQUATIONwhere the noise ξ k is assumed to be i.i.d. with mean zero and |ξ k | ≤ σ almost surely. 1 In addition, we independently generate a query token x and corresponding output ỹ in the same manner.We proceed to state our assumptions for the regression model. Informally, we suppose a relaxed version of sparsity and orthonormality of ψ • j 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 integersEQUATION)Denoting the N -basis approximation ofF • β as F • β, N := N j=1 β j ψ • j , by Assumption 1 there exist 'aggregated' co- efficients βN , • • • , β N uniquely determined by β such that F • β, N = N j= N βj ψ • j .We define two types of coefficient covariance matricesEQUATIONuniformly over β ∈ supp P β . Furthermore, Tr(Σ β,N ) is bounded for all N andEQUATIONRemark 2.1. In the simple case where (ψ • j ) ∞ j=1 is a basis for L2 (P X ), we may set N = 1, N = N so that the dependency condition of Assumption 1 is trivially satisfied, moreover, Σ β,N = Σ β,N and boundedness of Tr(Σ β,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 |β j | 2 ≲ j -2s-1 (log j) -2 along with Assumption 1 implies (3). The (log j) -2 term can be replaced with any g(j) such that ∞ j=1 j -1 g(j) is convergent.We now describe our transformer model, which takesn context pairs X = (x 1 , • • • , x n ) ∈ R d×n , y = (y 1 , • • • , y n ) ⊤ ∈ R nand a query token x as input and returns a prediction for the corresponding output. The covariates are first passed through a nonlinear representation or feature mapping ϕ : X → R N , which we assume belongs to a sufficiently powerful class of estimators F N . Specifically:Assumption 3 (expressivity of F N ). ∥ϕ(x)∥ 2 ≤ B ′ N for some B ′ N > 0 for all x ∈ X , ϕ ∈ F N . Moreover for some δ N > 0, there exists ϕ * N : N = (ϕ * N , • • • , ϕ * N ) ⊤ ∈ F N satisfying max N ≤j≤ N ∥ψ • j -ϕ * j ∥ L ∞ (P X ) ≤ δ N .By choosing F N and δ N to satisfy the above assumption, we will be able to utilize established approximation and generalization guarantees for DNN classes in Section 4.The extracted representations ϕ(X)= (ϕ(x 1 ), • • • , ϕ(x n ))are then mapped to a scalar output via a linear attention layer parametrized by a matrixΓ ∈ S N for S N ⊂ R N ×N , fΘ (X, y, x) := 1 n n k=1 y k ϕ(x k ) ⊤ Γ ⊤ ϕ(x) = Γϕ(X)y n , ϕ(x) , where Θ = (Γ, ϕ) ∈ S N × F N .Finally, the output is constrained to lie on [-B, B] by applying clip B (u) := max{min{u, B}, -B}, yielding f Θ (X, y, x) := clip B ( fΘ (X, y, x)).We setS N = {Γ ∈ R N ×N | 0 ⪯ Γ ⪯ C 3 I N } for some C 3 > 0 and fix B = B for simplicity.The above setup is a 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 are consolidated into one matrix Γ. The form is equivalent to one step 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 on top of which upper layers perform ICL (Guo et al., 2023) .During pretraining, the model is presented with T prompts {(X (t) , y (t) , x(t) )} T t=1 where the tasks F •β (t) ∈ F • , β (t) ∼ P β and tokens X (t) = (x (t) 1 , • • • , x (t) n ), y (t) = (y (t) 1 , • • • , y (t) n ) ⊤ , x(t)and ỹ(t) are independently generated as described in Section 2.1, and is trained to minimize the empirical riskΘ = arg min Θ∈S N ×F N R(Θ) = 1 T T t=1 ỹ(t) -f Θ (X (t) , y (t) , x(t) ) 2 .Our goal is to verify the efficiency of ICL as a learning algorithm and show that learning the optimal Θ allows the transformer to solve new random regression problems y = F• β (x) + ξ for F • β ∈ F • in context.To this end, we evaluate the convergence of the mean-squared riskR( Θ) := E (X (t) ,y (t) ,x (t) ,ỹ (t) ) T t=1 [R( Θ)], R(Θ) := E X,y,x,β (F • β (x) -f Θ (X, y, x)) 2 .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 in Section 1.1. 
risk bounds for in-context learning: 
 In this section, we outline our framework for upper bounding the in-context estimation error R( Θ). Some additional definitions are in order. The ϵ-covering number N (C, ρ, ϵ) of a metric space C equipped with a metric ρ for ϵ > 0 is defined as the minimal number of balls in ρ with radius ϵ needed to cover C (van der Vaart & Wellner, 1996) . The ϵ-covering entropy or metric entropy is given as V(F, ρ, ϵ) := log N (F, ρ, ϵ). The ϵ-packing number M(ϵ, C, ρ) is given as the maximal cardinality of a ϵ-separated set {c 1 , . . . , c M } ⊆ C such that ρ(c i , c j ) ≥ δ for all i ̸ = j. The transformer model class is defined asT N := {f Θ | Θ = S N × F N }.To bound the overall risk, we first decompose into the approximation and generalization gaps.Theorem 3.1 (Schmidt-Hieber (2020), Lemma 4, adapted).There exists a universal constant C such that for any ϵ > 0such that V(T N , ∥•∥ L ∞ , ϵ) ≥ 1, R( Θ) ≤ 2 inf Θ∈S N ×F N R(Θ) + C B 2 + σ 2 T V(T N , ∥•∥ L ∞ , ϵ) + (B + σ)ϵ .Proof. The convergence rate of the empirical risk minimizer is established for a fixed regression problem y = f • (z) + ξ in Schmidt-Hieber (2020) when ξ is Gaussian; we modify the proof to incorporate bounded noise in Appendix B.1.The ICL setup can be reduced to the ordinary case as follows. We consider the entire batch (β, X, ξ 1:n , x) including the hidden coefficient β as a single datum z with output ỹ. The true function is given as f• (z) = F • β (x)and the model class is taken to be T N implicitly concatenated with the generative process (β, X, ξ 1:n , x) → (X, y, x). Then R(Θ), V(T N , ∥•∥ L ∞ , ϵ) and T agree with the ordinary L 2 risk, model class entropy and sample size.Here, the second term is the pretraining generalization error dependent on the number of tasks T ; the in-context generalization error dependent on the prompt length n 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, we analyze the risk of the choiceΘ * = (Γ * , ϕ * ) := Σ Ψ,N + n -1 Σ -1 β,N -1 , ϕ * N : Nwhere ϕ * is given as in Assumption 3 for a suitable δ N to be determined. The definition of Γ * approximately generalizes the global optimum Γ = (1+ 1 n )Λ + 1 n tr(Λ)I d -1for the Gaussian linear regression setup where x ∼ N (0, Λ) (Zhang et al., 2023) . Since Σ Ψ,N ⪰ C 1 I N we have Γ * ⪯ C -1 1 I N and hence we may assume Γ * ∈ S N by replacingC 3 with C 3 ∨ C -1 1 if necessary. Proposition 3.2. Under Assumptions 1-3, it holds that inf Θ∈S N ×F N R(Θ) ≤ R(Θ * ) ≲ N 2r n log N + N 4r n 2 log 2 N + N n + N -2s + N 2 δ 4 N + N 2r+1 δ 2 N .The proof is presented throughout Appendix A. The overall scheme is to approximate Bounding generalization error. To estimate the metric entropy of T N , we first reduce to the metric entropy of the representation class F N . Here, ∥•∥ L ∞ refers to the essential supremum over the support of P X and also over all N components for F N . The proof is given in Appendix B.2. Lemma 3.3. Under Assumptions 1-3, there exists D > 0 such that for all ϵ sufficiently small,EQUATIONV(T N , ∥•∥ L ∞ , ϵ) ≲ N 2 log B ′2 N ϵ + V F N , ∥•∥ L ∞ , ϵ DB ′ N √ N . 
besov space and dnns: 
 In this section, we apply our theory to study the sample complexity of ICL when F N consists of (clipped, see ( 6)) deep neural networks. These can be also seen as simplified transformers with attention layers and skip connections removed. To be precise, we define the set of DNNs with depth L, width W , sparsity S, norm bound M and ReLU activation η(x) = x ∨ 0 (applied element-wise) asF DNN (L, W, S, M ) = (W (L) η + b (L) ) • • • • • (W (1) x + b (1) ) W (1) ∈ R W ×d , W (ℓ) ∈ R W ×W , W (L) ∈ R W , b (ℓ) ∈ R W , b (L) ∈ R, L ℓ=1 ∥W (ℓ) ∥ 0 + ∥b (ℓ) ∥ 0 ≤ S, ∥W (ℓ) ∥ ∞ ∨ ∥b (ℓ) ∥ ∞ ≤ M .The Besov space is a very general class of functions including the Hölder and Sobolev spaces which captures spatial inhomogeneity in smoothness, and provides a natural setting in which to study the expressive power of deep neural networks (Suzuki, 2019) . Here, we fix X = [0, 1] d for simplicity. Definition 4.1 (Besov space). For 2 ≤ p ≤ ∞, 0 < q ≤ ∞, fractional smoothness α > 0 and r = ⌊α⌋ + 1, the rth modulus of f ∈ L p (X ) is defined using the difference operator∆ r h , h ∈ R d as w r,p (f, t) := sup ∥h∥2≤t ∥∆ r h (f )∥ p , ∆ r h (f )(x) = 1 {x,x+rh∈X } r j=0 r j (-1) r-j f (x + jh).Also, the Besov (quasi-)norm is given as∥•∥ B α p,q = ∥•∥ L p + | • | B α p,q where |f | B α p,q := ∞ 0 t -qα w r,p (f, t) q dt t 1/q q < ∞ sup t>0 t -α w r,p (f, t) q = ∞and the Besov space is defined as B α p,q (X ) = {f ∈ L p (X ) | ∥f ∥ B α p,q < ∞}. We write U(B α p,q (X )) for the unit ball in (B α p,q (X ), ∥•∥ B α p,q ). We have that the Hölder space C α (X ) = B α ∞,∞ (X ) for order α > 0, α / ∈ N and the Sobolev space W m 2 (X ) = B m 2,2 (X ) for m ∈ N as well as the embeddingsEQUATIONX ) compactly embeds into the space of continuous functions on X . See Triebel (1983) ; Giné & Nickl (2015) for more details. The difficulty of learning a nonparametric regression function is quantified by the minimax risk; the following rate is classical. Proposition 4.2 (Donoho & Johnstone (1998) ). The minimax risk for an estimator f n with n i.i.d. samplesD n = {(x i , y i ) n i=1 } over U(B α p,q (X )) satisfies inf fn:Dn→R sup f • ∈U(B α p,q (X )) E Dn [∥f • -f n ∥ 2 L 2 (X ) ] ≍ n -2α 2α+d .A natural basis system for B α p,q (X ) is formed by the Bsplines, which can be seen as a type of wavelet decomposition or multiresolution analysis (DeVore & 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 m ∈ N satisfying m > α + 1 -1/p, at resolution k ∈ Z d ≥0 and location ℓ ∈ I d k = d i=1 [-m : 2 ki ] is ω d k,ℓ (x) = d i=1 ι m (2 ki x i -ℓ i ),whereι m (x) = (ι * ι * • • • * ι m+1 )(x), ι(x) = 1 {x∈[0,1]} . When k 1 = • • • = k d , we abuse notation and write ω d k,ℓ for k ∈ Z ≥0 in place of ω d (k,••• ,k),ℓ .To apply our framework, we set the task class as the unit ball F • = U(B α p,q (X )) and take as basis {ψ• j | j ∈ N} = {2 kd/2 ω d k,ℓ | k ∈ Z ≥0 , ℓ ∈ I d k }the set of all B-spline wavelets ordered primarily by increasing k and scaled to counteract the dilation in x. Abusing notation, we also write β k,ℓ to denote the coefficient in β corresponding to 2 kd/2 ω d k,ℓ . 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, s = α/d under:Assumption 4. F • = U(B αp,q (X )), α > d/p and P X has positive Lebesgue density ρ X bounded above and below on X . Also, all coefficients β k,ℓ are independent andE β [β k,ℓ ] = 0, 0 < E β [β 2 k,ℓ ] ≲ 2 -k(2α+d) k -2 (5)for all k ≥ 0 and ℓ ∈ I d k .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 -2 ) in the sense that any f ∈ U(B α p,q (X )) can indeed be expanded into a sum of wavelets with the same coefficient decay when averaged over ℓ ∈ I d k . See Lemma C.1 and the following discussion. We obtain the following in-context approximation and entropy bounds in Appendix C.1.2. Lemma 4.4. For any δ N > 0, Assumption 3 is satisfied by takingF N = {Π B ′ N • (ϕ j ) N j=1 | ϕ j ∈ F DNN (L, W, S, M )} (6)whereΠ B ′ N is the projection in R N to the centered ball of radius B ′ N = O( √ N ) and each ϕ j is a ReLU network such that L = O(log N + log δ -1 N ) and W, S, M = O(1). Also, the metric entropy of F N is bounded asV(F N , ∥•∥ L ∞ , ϵ) ≲ N log N δ N ϵ .Combining the results thus far, we conclude in Appendix C.1.3:Theorem 4.5 (minimax optimality of ICL in Besov space). Under Assumption 4, if n ≳ N log N , R( Θ) ≲ N -2α d DNN approximation error + N log N n in-context generalization error + N 2 log N T pretraining generalization error . Hence if T ≳ n 2α+2d 2α+d and N ≍ n d 2α+d, in-context learning achieves the minimax optimal rate n -2α 2α+d 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, 2011a) . The second and third term each correspond to the in-context and pretraining generalization gap. With regard to N , we see that n = Ω(N ) is enough to learn the basis expansion in context, while T = Ω(N 2 ) is necessary to learn the attention layer. However if T /N = o(n), the third term dominates and the overall complexity scales suboptimally as T -α α+d , illustrating the importance of sufficient pretraining. This also aligns with the task diversity threshold observed by Raventos et 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.A limitation of ICL. In the regime 1 ≤ p < 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 at 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 p < 2. Indeed, for any N -dimensional subspace L N ⊂ B α p,q (X ) it holds that (Vybíral, 2008) infL N sup f • ∈U(B α p,q (X )) inf ℓn∈L N ∥f • -ℓ n ∥ L 2 (X ) ≳ N -α d +( 1 p -1 2 )+ .Remark 4.6. The N 2 log N term in the pretraining generalization gap is due to the covering bound of the attention matrix Γ, while the entropy of the DNN class is only N log N .Hence the required task diversity may be lessened by considering low-rank structure or approximation of attention heads (Bhojanapalli et al., 2020; Chen et al., 2021) .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(α 1 , • • • , α d ) in each coordinate.Then the optimal rate is nearly dimension-free in the sense that the rate only depends on d through the quantity α := ( i α -1 i ) -1 , and becomes independent of dimension if only a few directions are important i.e. have small α i . Rigorous definitions, statements and proofs are provided in Appendix C.2. Extending Theorem 4.5, we 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 highdimensional settings. Theorem 4.7 (informal version of Theorem C.7). For the anisotropic Besov space of smoothness (α 1 , • • • , α d ), assume variance decay (4) with s = α > 1/p. If T ≳ nN and N ≍ n 1 2 α+1 , in-context learning achieves the minimax optimal rate n -2 α 2 α+1 up to a log factor.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 (ψ • j ) ∞ j=1 is no longer the B-spline basis of B α p,q (X ) but instead is chosen from some wider function space, say the unit ball of B τ p,q (X ) for a smaller smoothness τ < α. Without knowledge of the basis, the sample complexity of learning any regression function F • β is a priori lower bounded by the minimax rate n -2τ 2τ +d by Proposition 4.2. For ICL, this difficulty manifests as an increase in the metric entropy of the class F N which must be powerful enough to approximate ψ • 1:N (Corollary C.12), giving rise to the modified risk bound:Corollary 4.8 (ICL for coarser basis). Suppose α > τ > d/p, the basis(ψ • j ) ∞ j=1 ⊂ U(B τ p,q (X )) and Assumptions 1, 2 hold with r = 1/2, s = α/d. Then if n ≳ N log N , it holds that R( Θ) ≲ N -2α d + N log N n + N 1+ α τ + d τ log 3 N T . Hence if T ≳ n 1+ d 2α+d α+d τand N ≍ n d 2α+d , the risk converges as n -2α 2α+d log n.The pretraining generalization gap is now dominated by the higher complexity N 1+ α τ + d τ log3 N of the DNN class and strictly worse compared to N 2 log N for Theorem 4.5. The required number of tasks also suffers and the exponent is no longer 2α+2d 2α+d ∈ (1, 2) but scales as O(d). Nevertheless, observe that the burden of complexity is entirely carried by T ; with sufficient pretraining, the third term can be made arbitrarily small and the ICL risk again attains n -2α 2α+d . Hence ICL improves upon the a priori lower bound n -2τ 2τ +d 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.We now consider a more complex setting where the inputs x ∈ [0, 1] d×∞ are bidirectional sequences of tokens (e.g. entire documents) and ϕ is itself a transformer network. 2 In this infinite-dimensional setting, transformers can still circumvent the curse of dimensionality and in fact achieve near-optimal sample complexity due to their parameter sharing and feature extraction capabilities (Takakura & Suzuki, 2023) . Our goal in this section is to extend this guarantee to ICL of trained transformers.For sequential data, it is natural to 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 γ-smooth function class introduced by Takakura & Suzuki (2023), which allows for arbitrary bounded permutations among input tokens; see Appendix D.1 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 (h) , Q (h) ∈ 2 We clarify that this is not equivalent to a multi-layer transformer setting where ϕ is the rest of the transformer. Instead, ϕ operates on tokens xi separately, which may now themselves be sequences of unbounded dimension. The extracted per-token features are cross-referenced only at the final attention layer fΘ. R D×d , V (h) ∈ R d×d and norm bound M defined as 3F Attn (U, D, H, M ) = g : R d×∞ → R d×∞ ∥K (h) ∥ ∞ ∨ ∥Q (h) ∥ ∞ ∨ ∥V (h) ∥ ∞ ≤ M, g(x) i = x i + H h=1 V (h) x i-U :i+U Softmax (K (h) x i-U :i+U ) ⊤ Q (h) x i .We also consider a linear embedding layer Enc(x) = Ex + P , E ∈ R D×d with absolute positional encoding P ∈ R D of bounded norm. Then the class of depth J transformers isF TF (J, U, D, H, L, W, S, M ) = f J • g J • • • • • f 1 • g 1 • Enc | ∥E∥ ≤ M, f i ∈ F DNN (L, W, S, M ), g i ∈ F Attn (U, D, H, M ) .Our result, proved in Appendix D.2, reads: Theorem 4.9 (informal version of Theorem D.1). Suppose F • consists of functions on [0, 1] d×∞ of bounded piecewise γ-smooth and L ∞ -norm with smoothness α ∈ R d×∞ >0 , and let γ be mixed or anisotropic smoothness with α † = max i,j α ij or ( i,j α -1 ij ) -1 , respectively. Under suitable regularity and decay assumptions, by taking F N to be a class of clipped transformers it holds thatR( Θ) ≲ N -2α † + N log N n + N 2∨(1+1/α † ) polylog(N ) T . Hence if T ≳ nN 1∨1/α † and N ≍ n 1 2α † +1 , ICL achieves the rate n -2α † 2α † +1 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 F TF class is essential in dealing with input-dependent smoothness, further justifying the efficiacy of ICL of sequential data. 
minimax lower bounds: 
 In this section, we provide a lower bound for the minimax rate in the ICL setup by extending the theory of Yang & Barron (1999) . The result is purely information-theoretic and hence applies to not just ICL but any meta-learning scheme for the regression problem of Section 2.1 depending on the data D n,T = {(X (t) , y (t) , x(t) )} T +1 t=1 , where the index T + 1 corresponds to the test task.For this section we assume that the noise (1) is i.i.d. Gaussian, ξ k ∼ N (0, σ 2 ), instead of bounded. We also suppose the support of P β is included inB := {β ∈ R ∞ | |β j | ≲ j -2s-1 (log j) -2 , j ∈ N} and that the aggregated coeffi- cients βj for N ≤ j ≤ N satisfy E β [ β2 j ] ≤ σ 2β for some σ β dependent on N . The proof of the following statement is given in Appendix E.1.Proposition 5.1. For ε n,1 , ε n,2 , δ n > 0, let Q 1 and Q 2 be the ε n,1 -and ε n,2 -covering numbers of F N and B respectively, and M be the δ n -packing number of F • . Suppose that the following conditions are satisfied:EQUATION)Then the minimax rate is lower bounded asinf f :D n,T →R sup f • ∈F • E Dn [∥ f -f • ∥ 2 L 2 (P X ) ] ≥ 1 4 δ 2 n .Finally, Proposition 5.1 is applied to obtain concrete lower bounds for the settings studied in Section 4 throughout Appendices E.2-E.4. We prove the following rates: n -2α 2α+d for the Besov space, n -2α 2α+d +(nT ) -2τ 2τ +d for the coarser basis setting, and n-2α † 2α † +1for the piecewise γ-smooth class. In particular, we can check that insufficient pretraining indeed leads to a worse complexity for the second setting, while large T retrieves the faster rate n -2α 2α+d . These results verify the optimality of our previous results from the perspective of the sample complexity of meta-learning. 
conclusion: 
 In this paper, we performed a learning-theoretic analysis of ICL of a 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 in terms of both the number of tasks and samples, and proved that ICL can achieve nearly minimax optimal rates in the Besov space, anisotropic Besov space and γ-smooth class. We also showed that ICL can improve upon the a priori optimal rate by learning informative representations during pretraining. Our analyses open up interesting approaches of adapting classical learning theory to study emergent behavior of transformers and meta-learning phenomena.Limitations. We do not study the optimization aspect of pretraining for ICL, and the derived upper bounds may not be tight with respect to the number of tasks T . In addition, our transformer model is limited to a single layer of selfattention and does not consider more complex ICL behavior which may arise in transformers with multiple attention layers. These issues may be addressed in a future work.  
 
 Appendix: Θ * = (Γ * , ϕ * ) = Σ Ψ,N + 1 n Σ -1 β,N -1 , ϕ * N : N .We introduce some additional notation in the following fashion. For brevity, we write N : ∞ instead of ( N + 1) : ∞ as an exception.Φ * = (ϕ * N : N (x 1 ), • • • , ϕ * N : N (x n )) ∈ R N ×n , ξ = (ξ 1 , . . . , ξ n ) ⊤ ∈ R n , Ψ • = (ψ • (x 1 ), . . . , ψ • (x n )) ∈ R ∞×n , Ψ • N : N = (ψ • N : N (x 1 ), • • • , ψ • N : N (x n )) ∈ R N ×n , Ψ • N :∞ = (ψ • N :∞ (x 1 ), • • • , ψ • N :∞ (x n )) ∈ R ∞×n . Since clipping fΘ does not make its difference with F • β ∈ [-B, B] larger, it holds that R(Θ * ) = E F • β (x) -f Θ * (X, y, x) 2 ≤ E F • β (x) -fΘ * (X, y, x) 2 ≤ 2E F • β (x) -F • β, N (x) 2 + 2E F • β, N (x) -fΘ * (X, y, x) 2 ≲ N -2s + E F • β, N (x) -ϕ * (x) ⊤ Γ * Φ * y n 2due to Assumption 2 and N ≍ N . Expanding the attention output asϕ * (x) ⊤ Γ * Φ * y n = (ϕ * (x) -ψ • N : N (x) + ψ • N : N (x)) ⊤ Γ * (Φ * -Ψ • N : N + Ψ • N : N )y n = (ϕ * (x) -ψ • N : N (x)) ⊤ Γ * (Φ * -Ψ • N : N )y n + (ϕ * (x) -ψ • N : N (x)) ⊤ Γ * Ψ • N : N y n + ψ • N : N (x) ⊤ Γ * (Φ * -Ψ • N : N )y n + ψ • N : N (x) ⊤ Γ * Ψ • N : N y n ,and the final term further asψ • N : N (x) ⊤ Γ * Ψ • N : N y n = ψ • N : N (x) ⊤ Γ * Ψ • N : N (Ψ •⊤ β + ξ) n = ψ • N : N (x) ⊤ Γ * Ψ • N : N Ψ •⊤ N : N βN : N n + ψ • 1:N (x) ⊤ Γ * Ψ • N : N (Ψ •⊤ N :∞ β N :∞ + ξ) n ,we obtain thatEQUATION)We proceed to control each term separately, from which the statement of Proposition 3.2 will follow.A.2. Bounding Term (8)EQUATION)Denote the operator norm (with respect to L 2 norm of vectors) by ∥•∥ op . For (13), noting that Σ Ψ,N is positive definite,E   ψ • N : N (x) ⊤ Γ * Ψ • N : N Ψ •⊤ N : N n -Σ Ψ,N βN : N 2   = E   ψ • N : N (x) ⊤ Γ * Σ 1/2 Ψ,N Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N Σ 1/2 Ψ,N βN : N 2   = E X,β β⊤ N : N Σ 1/2 Ψ,N Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N Σ 1/2 Ψ,N Γ * E x ψ • N : N (x)ψ • N : N (x) ⊤ × Γ * Σ 1/2 Ψ,N Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N Σ 1/2 Ψ,N βN : N = E X Tr Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N Σ 1/2 Ψ,N E β βN : N β⊤ N : N Σ 1/2 Ψ,N × Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N Σ 1/2 Ψ,N Γ * Σ Ψ,N Γ * Σ 1/2 Ψ,N ≲ E X   Tr Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N 2 Σ 1/2 Ψ,N Σ β,N Σ 1/2 Ψ,N  due to the independence of X, x and β. For the last inequality, we have used the fact that both the Σ1/2 Ψ,N Γ * Σ Ψ,N Γ * Σ 1/2 Ψ,Nterm and the matrix multiplied to it are positive semi-definite, and the former is bounded above as ≾ I N by Assumption 1.Furthermore, we utilize the following result proved in Appendix A.5:Lemma A.1. E X   Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N 2 op   ≲ N 2r n log N + N 4r n 2 log 2 N .It follows that ( 13) is bounded asE   ψ • N : N (x) ⊤ Γ * Ψ • N : N Ψ •⊤ N : N n -Σ Ψ,N βN : N 2   ≲ E X   Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N 2 op   Tr Σ 1/2 Ψ,N Σ β,N Σ 1/2 Ψ,N ≲ N 2r n log N + N 4r n 2 log 2 N ∥Σ Ψ,N ∥ op Tr(Σ β,N ) ≲ N 2r n log N + N 4r n 2 log 2 N since Tr(Σ β,N ) is bounded by Assumption 2.Moreover for ( 14), we computeE ψ • N : N (x) ⊤ Γ * Σ -1 β,N n βN : N 2 = E β⊤ N : N Σ -1 β,N n Γ * ψ • N : N (x)ψ • N : N (x) ⊤ Γ * Σ -1 β,N n βN : N = E Tr Σ -1 β,N n Γ * ψ • N : N (x)ψ • N : N (x) ⊤ Γ * Σ -1 β,N n βN : N β⊤ N : N = Tr Σ -1 β,N n Γ * E x ψ • N : N (x)ψ • N : N (x) ⊤ Γ * Σ -1 β,N n E β βN : N β⊤ N : N = Tr Σ -1 β,N n Γ * Σ Ψ,N Γ * positive definite Σ -1 β,N n Σ β,N ≤ 1 n Tr Σ Ψ,N + 1 n Σ -1 β,N Γ * Σ Ψ,N Γ * = 1 n Tr Σ Ψ,N Σ Ψ,N + 1 n Σ -1 β,N -1 ≤ N n .A.3. Bounding Term (9)Since the sequence of covariatesEQUATIONfor independent samples x, x ′ , x ∼ P X . We now bound the three terms separately below.For (15), we have that 2) and the diagonal of1 n E ψ • N : N (x) ⊤ Γ * ψ • N : N (x)β ⊤ N :∞ ψ • N :∞ (x) 2 = 1 n E ψ • N : N (x) ⊤ Γ * ψ • N : N (x)ψ • N : N (x) ⊤ Γ * ψ • N : N (x)ψ • N :∞ (x) ⊤ β N :∞ β ⊤ N :∞ ψ • N :∞ (x) = 1 n E x ψ • N : N (x) ⊤ Γ * Σ Ψ,N Γ * ψ • N : N (x)ψ • N :∞ (x) ⊤ E β β N :∞ β ⊤ N :∞ ψ • N :∞ (x) ≲ 1 n E x ∥ψ • N : N (x)∥ 2 ψ • N :∞ (x) ⊤ E β β N :∞ β ⊤ N :∞ ψ • N :∞ (x) ≲ 1 n sup x∈supp P X ∥ψ • N : N (x)∥ 2 • lim M →∞ Tr E β β N :M β ⊤ N :M E x ψ • N :M (x)ψ • N :M (x) ⊤ ≲ 1 n sup x∈supp P X ∥ψ • N : N (x)∥ 2 • lim M →∞ Tr E β β N :M β ⊤ N :M since Σ Ψ,M ⪯ C 2 I N as M → ∞ by Assumption 2. As sup x ∥ψ • N : N (x)∥ 2 ≲ N -2r by (E β [β N :M β ⊤ N :M ] decays faster than N -2s M -1 (log M ) -2 when M > N due to (4), it follows that 1 n sup x∈supp P X ∥ψ • N : N (x)∥ 2 • lim M →∞ Tr E β β N :M β ⊤ N :M ≲ 1 n N 2r N -2s .Similarly, for ( 16), we have thatn -1 n E ψ • N : N (x) ⊤ Γ * ψ • N : N (x)β ⊤ N :∞ ψ • N :∞ (x)ψ • N : N (x) ⊤ Γ * ψ • N : N (x ′ )β ⊤ N :∞ ψ • N :∞ (x ′ ) ≤ E ψ • N : N (x) ⊤ Γ * ψ • N : N (x)β ⊤ N :∞ ψ • N :∞ (x) ⊤ ψ • N : N (x) ⊤ Γ * ψ • N : N (x ′ )β ⊤ N :∞ ψ • N :∞ (x ′ ) = E x,x ′ ,β ψ • N :∞ (x) ⊤ β N :∞ ψ • N : N (x) ⊤ Γ * Σ Ψ,N Γ * ψ • N : N (x ′ )β ⊤ N :∞ ψ • N :∞ (x ′ ) = E β E x ψ • N : N (x)β ⊤ N :∞ ψ • N :∞ (x) ⊤ Γ * Σ Ψ,N Γ * E x ψ • N : N (x)β ⊤ N :∞ ψ • N :∞ (x) ≲ E β E x ψ • N : N (x)β ⊤ N :∞ ψ • N :∞ (x) 2 ≲ E β ψ • N :∞ (x) ⊤ β N :∞ β ⊤ N :∞ ψ • N :∞ (x) ≲ N -2s .And for (17), we have thatσ 2 n E ψ • N : N (x) ⊤ Γ * ψ • N : N (x) = σ 2 n Tr Γ * E x ψ • N : N (x)ψ • N : N (x) ⊤ Γ * E x ψ • N : N (x)ψ • N : N (x) ⊤ = σ 2 n Tr Γ * Σ Ψ,N Γ * positive definite Σ Ψ,N ≤ σ 2 n Tr Γ * Σ Ψ,N Γ * Σ Ψ,N + 1 n Σ -1 β,N = σ 2 n Tr [Γ * Σ Ψ,N ] ≤ σ 2 N n .Therefore, we obtain the following bound:E   ψ • N : N (x) ⊤ Γ * Ψ • N : N (Ψ •⊤ N :∞ β N :∞ + ξ) n 2   ≲ N 2r N -2s n + N -2s + σ 2 N n .A.4. Bounding Terms (10)-( 12)For ( 10), we use the Cauchy-Schwarz inequality and Assumption 3 to boundE   (ϕ * (x) -ψ • N : N (x)) ⊤ Γ * (Φ * -Ψ • N : N )y n 2   ≤ 1 n n i=1 E (ϕ * (x) -ψ • N : N (x)) ⊤ Γ * (ϕ * (x i ) -ψ • N : N (x i ))y i 2 ≤ 1 n n i=1 E ∥ϕ * (x) -ψ • N : N (x)∥ 2 ∥Γ * (ϕ * (x i ) -ψ • N : N (x i ))∥ 2 y 2 i ≤ ∥Γ * ∥ 2 op sup x∈supp P X ∥ϕ * (x) -ψ • N : N (x)∥ 2 2 E y 2 ≤ ∥Γ * ∥ 2 op N max N ≤j≤ N ∥ϕ * j -ψ • j ∥ 2 L ∞ (P X ) 2 E y 2 ≲ N 2 δ 4 N (B 2 + σ 2 ).Similarly for ( 11) and ( 12), we haveE   (ϕ * (x) -ψ • N : N (x)) ⊤ Γ * Ψ • N : N y n 2   ≤ 1 n n i=1 E (ϕ * (x) -ψ • N : N (x)) ⊤ Γ * ψ • N : N (x i )y i 2 ≤ 1 n n i=1 E ∥ϕ * (x) -ψ • N : N (x)∥ 2 ∥Γ * ψ • N : N (x i )∥ 2 y 2 i ≤ sup x∈supp P X ∥ϕ * (x) -ψ • N : N (x)∥ 2 ∥Γ * ∥ 2 op sup x∈supp P X ∥ψ • N : N (x)∥ 2 E y 2 ≲ N δ 2 N • N 2r (B 2 + σ 2 ) = N 2r+1 δ 2 N (B 2 + σ 2 ) and E   ψ • N : N (x) ⊤ Γ * (Φ * -Ψ • N : N )y n 2   ≤ 1 n n i=1 E ψ • N : N (x) ⊤ Γ * (ϕ * (x i ) -ψ • N : N (x i ))y i 2 ≤ 1 n n i=1 E ∥ψ • N : N (x)∥ 2 ∥Γ * (ϕ * (x i ) -ψ • N : N (x i ))∥ 2 y 2 i ≤ sup x∈supp P X ∥ψ • N : N (x)∥ 2 ∥Γ * ∥ 2 op sup x∈supp P X ∥(ϕ * (x) -ψ • N : N (x))∥ 2 E y 2 ≲ N 2r+1 δ 2 N (B 2 + σ 2 ).This concludes the proof of Proposition 3.2.A.5. Proof of Lemma A.1We will make use of the following concentration bound and its corollary, proved at the end of this subsection. v(Z) = max ∥E[ZZ ⊤ ]∥ op , ∥E[Z ⊤ Z]∥ op = max n i=1 E[S i S ⊤ i ] op , n i=1 E[S ⊤ i S i ] op .Then it holds for all t > 0 thatPr (∥Z∥ op ≥ t) ≤ 2N exp - t 2 2v(Z) + 2 3 Lt .Proof. See Tropp (2015) , Theorem 6.1.1.Corollary A.3. For matrices S 1 , • • • , S n satisfying the conditions of Theorem A.2, it holds that E 1 n 2 ∥Z∥ 2 op ≤ 4v(Z) n 2 (1 + log 2N ) + 16L 2 9n 2 (2 + 2 log 2N + (log 2N ) 2 ).We will apply Corollary A.3 to the matricesS i := Σ -1/2 Ψ,N ψ • N : N (x i )ψ • N : N (x i ) ⊤ Σ -1/2 Ψ,N -I N .It is straightforward to verify thatE[S i ] = Σ -1/2 Ψ,N Σ Ψ,N Σ -1/2 Ψ,N -I N = 0 and ∥S i ∥ op ≲ ∥ψ • N : N (x i )ψ • N : N (x i ) ⊤ ∥ op + 1 = N j= N ψ • j (x i ) 2 + 1 ≲ N 2ralmost surely by Assumption 1.Next, we evaluate the matrix variance statistic. Since each S i is symmetric,v(Z) = n i=1 E[S i S ⊤ i ] op = n i=1 E X Σ -1/2 Ψ,N ψ • N : N (x i )ψ • N : N (x i ) ⊤ Σ -1 Ψ,N ψ • N : N (x i )ψ • N : N (x i ) ⊤ Σ -1/2 Ψ,N -2E X Σ -1/2 Ψ,N ψ • N : N (x i )ψ • N : N (x i ) ⊤ Σ -1/2 Ψ,N + I N op = n i=1 E X Σ -1/2 Ψ,N ψ • N : N (x i )ψ • N : N (x i ) ⊤ Σ -1 Ψ,N ψ • N : N (x i )ψ • N : N (x i ) ⊤ Σ -1/2 Ψ,N -nI N op ≤ n + n E x Σ -1/2 Ψ,N ψ • N : N (x)ψ • N : N (x) ⊤ Σ -1 Ψ,N ψ • N : N (x)ψ • N : N (x) ⊤ Σ -1/2 Ψ,N opfor a single sample x ∼ P X . The second term is further bounded asE x Σ -1/2 Ψ,N ψ • N : N (x)ψ • N : N (x) ⊤ Σ -1 Ψ,N ψ • N : N (x)ψ • N : N (x) ⊤ Σ -1/2 Ψ,N op ≤ E x Σ -1/2 Ψ,N ψ • N : N (x)ψ • N : N (x) ⊤ Σ -1/2 Ψ,N op • ψ •⊤ N : N Σ -1 Ψ,N ψ • N : N L ∞ (P X ) ≲ ∥I N ∥ op • N j= N (ψ • j ) 2 L ∞ (P X ) ≲ N 2r ,again by Assumption 1.Hence we may apply Corollary A.3 with v(Z) ≲ nN 2r , L ≲ N 2r to conclude:E X   Σ -1/2 Ψ,N Ψ • N : N Ψ •⊤ N : N n Σ -1/2 Ψ,N -I N 2 op   = E 1 n n i=1 S i 2 op ≲ N 2r n log N + N 4r n 2 log 2 N.Proof of Corollary A.3. From Theorem A.2 and with the change of variables λ = t 2 /n 2 , we havePr 1 n 2 ∥Z∥ 2 op ≥ λ ≤ 2N exp - n 2 λ 2v(Z) + 2 3 Ln √ λ .Since the probability is also bounded above by 1, it follows thatPr 1 n 2 ∥Z∥ 2 op ≥ λ ≤ 1 ∧ 2N exp - n 2 λ 2(2v(Z) ∨ 2 3 Ln √ λ) ≤ 1 ∧ 2N exp - n 2 λ 4v(Z) + 1 ∧ 2N exp - 3n √ λ 4L ,and the expectation can be controlled asE 1 n 2 ∥Z∥ 2 op = ∞ 0 Pr 1 n 2 ∥Z∥ 2 op ≥ λ dλ ≤ ∞ 0 1 ∧ 2N exp - n 2 λ 4v(Z) dλ + ∞ 0 1 ∧ 2N exp - 3n √ λ 4L dλ.For the first integral, we truncate atλ 1 := 4v(Z) n 2 log 2N so that ∞ 0 1 ∧ 2N exp - n 2 λ 4v(Z) dλ = λ 1 + ∞ λ1 2N exp - n 2 λ 4v(Z) dλ = 4v(Z) n 2 log 2N + 4v(Z) n 2 .For the second integral, we truncate atλ 2 := 4L 3n log 2N 2 so that ∞ 0 1 ∧ 2N exp - 3n √ λ 4L dλ = λ 2 + ∞ λ2 2N exp - 3n √ λ 4L dλ = λ 2 - 16LN 3n √ λ + 4L 3n exp - 3n √ λ 4L ∞ λ=λ2 = 4L 3n log 2N 2 + 8L 3n 4L 3n log 2N + 4L 3n .Adding up, we conclude thatE 1 n 2 ∥Z∥ 2 op ≤ 4v(Z) n 2 (1 + log 2N ) + 16L 2 9n 2 (2 + 2 log 2N + (log 2N ) 2 )as was to be shown.B.1. Modified Proof of Theorem 3.1For a full proof of the original statement, we refer the reader to Section B.1 of Hayakawa & 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 an ϵ-cover of the model space by f 1 , • • • , f M . The only step which relies on the normality of noise ξ 1:n is a concentration result for the random variablesε j := n i=1 ξ i (f j (x i ) -f • (x i )) ( n i=1 (f j (x i ) -f • (x i )) 2 1/2 , 1 ≤ j ≤ M,where it is shown via the normality of ε j thatE max 1≤j≤M ε 2 j ≤ 4σ 2 (log M + 1).We will instead rely on Hoeffding's inequality. By writing ε j = w ⊤ j ξ 1:n = n i=1 w j,i ξ i wherew j,i = f j (x i ) -f • (x i ) ( n i=1 (f j (x i ) -f • (x i )) 2 1/2 , since |w j,i ξ i | ≤ σ|w j,i | a.s. it follows that Pr (|ε j | ≥ u) ≤ 2 exp - 2u 2 n i=1 (2σ|w j,i |) 2 = 2 exp - u 2 2σ 2 .for all u > 0. Then the squared-exponential moment of each ε j is bounded asE exp(tε 2 j ) = 1 + ∞ 1 Pr exp(tε 2 j ) ≥ λ dλ ≤ 1 + ∞ 1 2 exp - log λ 2σ 2 t dλ ≤ 1 + 2 ∞ 1 λ -1 2σ 2 t dλ ≤ 3 by setting t = 1 4σ 2 .Hence via Jensen's inequality we obtainexp tE max 1≤j≤M ε 2 j ≤ E max 1≤j≤M exp(tε 2 j ) ≤ M j=1 E exp(tε 2 j ) ≤ 3Mand thusE max 1≤j≤M ε 2 j ≤ 4σ 2 log 3M,retrieving the original result up to a constant.it follows that∥Γ 1 -Γ 2 ∥ op = ∥U 1 Λ 1 U ⊤ 1 -U 1 Λ 1 U ⊤ 2 + U 1 Λ 1 U ⊤ 2 -U 2 Λ 1 U ⊤ 2 + U 2 Λ 1 U ⊤ 2 -U 2 Λ 2 U ⊤ 2 ∥ op ≤ 2∥Λ 1 ∥ L ∞ ∥U 1 -U 2 ∥ op + ∥Λ 1 -Λ 2 ∥ L ∞ ≤ 2C 3 • δ 4C 3 + δ 2 = δ.Moreover, the covering number of O N in operator norm is given by the following result.Theorem B.2 (Szarek (1981) , Proposition 6). There exist universal constants c 1 , c 2 > 0 such that for all N ∈ N and δ ∈ (0, 2], c 1 δEQUATION.Hence we obtain thatV(S N , ∥•∥ op , δ) ≤ V O N , ∥•∥ op , δ 4C 3 + V [0, C 3 ] N , ∥•∥ L ∞ , δ 2 ≤ N (N -1) 2 log c 2 δ + N log 2C 3 δ ≲ N 2 log 1 δ .Finally, we remark that if elements of the domain S N are not constrained to be symmetric, we can alternatively consider the singular value decomposition and separately bound entropy of the two rotation components, giving the same result up to constants.C.1. Besov SpaceWe first give some background on wavelet decomposition. The decay rate s = α/d is intrinsic to the Besov space as shown by the following result, which allows us to translate between functions f ∈ B α p,q (X ) and their B-spline coefficient sequences.Lemma C.1 (DeVore & Popov (1988), Corollary 5.3). If α > d/p and m > α + 1 -1/p, a function f ∈ L p (X ) is in B α p,q (X ) if and only if f can be represented as f = ∞ k=0 ℓ∈I d k βk,ℓ ω d k,ℓsuch that the coefficients satisfy∥ β∥ b α p,q := ∞ k=0 2 k(α-d/p) ℓ∈I d k | βk,ℓ | p 1/p q 1/q < ∞,with appropriate modifications if p = ∞ or q = ∞. Moreover, the two norms ∥ β∥ b α p,q and ∥f ∥ B α p,q are equivalent.In particular, this implies that for any f ∈ U(B α p,q (X )) the p-norm average of βk,ℓ for ℓ ∈ I d k at resolution k is bounded as1 |I d k | ℓ∈I d k | βk,ℓ | p 1/p ≲ (2 -kd ) 1/p • 2 k(d/p-α) ∥f ∥ B α p,q ≤ 2 -kα ,and the coefficients β k,ℓ = 2 -kd/2 βk,ℓ w.r.t. the scaled basisEQUATION)Thus it is natural in a probabilistic sense to assume E[β p k,ℓ ] 1/p ≲ (2 kd ) -α/d-1/2 . This will be the case if for instance we sample (β k,ℓ ) ℓ∈I d k 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) .Assumption 1. We take m to be even for simplicity. The wavelet system (ω d K,ℓ ) ℓ∈I d K at each resolution K is linearly independent; for any g ∈ L 2 (X ) that can be expressed asg = ℓ∈I d K β K,ℓ 2 Kd/2 ω d K,ℓwe have the quasi-norm equivalence (Dũng, 2011b, 2.15 )∥g∥ 2 ≍ 2 -Kd/2 ℓ∈I d K 2 Kd β 2 K,ℓ 1/2 = ∥(β K,ℓ ) ℓ∈I d K ∥ 2 which implies that the covariance matrix E x∼Unif([0,1] d ) [ψ • N : N (x)ψ • N : N (x) ⊤ ]is bounded above and below. Since we assume P X has Lebesgue density bounded above and below, it follows that Σ Ψ,N is uniformly bounded above and below for all K ≥ 0.In contrast, any B-spline at a lower resolution k < K can be exactly expressed as a linear combination of elements of (ω d K,ℓ ) ℓ∈I d K by repeatedly applying the following relation. Lemma C.2 (refinement equation). For even m and r = (rEQUATIONProof. The relation for one-dimensional wavelets is given in equation (2.21) of Dũng (2011b) ,ι m (x) = 2 -m+1 m r=0 m r ι m 2x -r + m 2 ,from which it follows thatω d k,ℓ (x) = d i=1 ι m (2 k x i -ℓ i ) = m r1,••• ,r d =0 2 (-m+1)d d i=1 m r i ι m 2 k+1 x i -2ℓ i -r i + m 2 = m r1,••• ,r d =0 2 (-m+1)d d i=1 m r i • ω d k+1,2ℓ+r-m 2 1 (x)as was to be shown.Therefore we select all B-splines at a fixed resolution K to approximate the target tasks,N = I d K = (m + 1 + 2 K ) d ≍ 2 Kd and N = K-1 k=0 I d k + 1 ≍ N, N = K k=0 I d k ≍ N.It is straightforward to see that 0 ≤ ω d k,ℓ (x) ≤ 1 for all x ∈ X and moreover the B-splines (extended to all ℓ ∈ Z d ) form a partition of unity of R d at all resolutions:ℓ∈Z d ω d k,ℓ (x) ≡ 1, ∀x ∈ R d , ∀k ≥ 0.Then for all x ∈ X we have the boundN j= N ψ • j (x) 2 = ℓ∈I d K 2 Kd ω d K,ℓ (x) 2 ≤ 2 Kd ℓ∈Z d ω d K,ℓ (x) = 2 Kd ≲ N,and hence (2) holds with r = 1/2.Assumption 2. For any β ∈ supp P β we have that∥F • β ∥ L ∞ (P X ) ≤ ∞ k=0 ℓ∈I d k β k,ℓ • 2 kd/2 ω d k,ℓ L ∞ (P X ) ≤ ∞ k=0 2 kd/2 max ℓ∈I d k |β k,ℓ | • ℓ∈I d k ω d k,ℓ L ∞ (X ) ≤ ∞ k=0 2 kd(1/2+1/p) 1 |I d k | ℓ∈I d k |β k,ℓ | p 1/p ℓ∈I d k ω d k,ℓ L ∞ (X ) ≲ ∞ k=0 2 kd(1/2+1/p) • (2 kd ) -α/d-1/2 ∥F • β ∥ B α p,q ≲ (1 -2 d/p-α ) -1 =: B.Furthermore, the convergence rate of the truncated approximation F • β,N is determined by the decay rate of β in Lemma C.1 as follows (it does not matter whether we bound F• β, N or F • β,N since N ≍ N ).We consider a truncation of all resolutions lower than K so that N, N ≍ 2 Kd . Then it holds that∥F • β -F • β, N ∥ 2 L 2 (P X ) = X ∞ j= N +1 β j ψ • j (x) 2 P X (dx) = ∞ j,k= N +1 β j β k E x [ψ • j (x)ψ • k (x)] ≤ lim M →∞ C 2 ∥β N :M ∥ 2 = C 2 ∞ k=K ℓ∈I d k β 2 k,ℓ ≲ ∞ k=K |I d k | 1-2/p ℓ∈I d k |β k,ℓ | p 2/p ≲ ∞ k=K 2 kd • (2 kd ) -2α/d-1 = 2 -2αK 1 -2 -2α ≍ N -2α/d ,where for the last two inequalities we have used the inequality ∥z∥ 2 ≤ D 1/2-1/p ∥z∥ p for z ∈ R D and p ≥ 2 in conjunction with (18). Thus our choice of s = α/d is justified. Under this choice, (5) directly implies (4) asE β [β 2 K,ℓ ] ≲ 2 -Kd(2s+1) K -2 ≍ N -2s-1 (log N ) -2holds for the basis elements at each resolution K, that is for those numbered between N and N . Remark C.3. When 1 ≤ p < 2, the truncation up to N does not suffice to achieve the N -2α/d approximation rate, and basis elements must be judiciously selected from a wider resolution range. More concretely, a size N subset of all wavelets up to resolution K ′ = ⌈K(1 + ν -1 )⌉ where ν = pα/2d -1/2 > 0 must be used (Suzuki & Nitanda, 2021, Lemma 2) .Hence the exponent is a factor of 1 + ν -1 worse w.r.t. N ′ ≍ 2 K ′ d , leading to the inevitable suboptimal rate.To show boundedness of Tr(Σ β,N ), we analyze the composition of the aggregated coefficients β using the following result.Corollary C.4. For any 0 ≤ k < k ′ there exists constantsγ k,k ′ ,ℓ,ℓ ′ ≥ 0 for ℓ ∈ I d k , ℓ ′ ∈ I d k ′ such that ℓ∈I d k β k,ℓ 2 kd/2 ω d k,ℓ = ℓ ′ ∈I d k ′ βk ′ ,ℓ ′ 2 k ′ d/2 ω d k ′ ,ℓ ′ , βk ′ ,ℓ ′ = ℓ∈I d k γ k,k ′ ,ℓ,ℓ ′ β k,ℓholds for all (β k,ℓ ) ℓ∈I d k . Moreover, it holds thatℓ∈I d k γ k,k ′ ,ℓ,ℓ ′ ≤ 2 (k-k ′ )d/2 , ℓ ′ ∈I d k ′ γ k,k ′ ,ℓ,ℓ ′ ≤ 2 (k ′ -k)d/2 .The statement follows directly from the more general Proposition C.10, stated and proved in Appendix C.3 below, by restricting to wavelets with uniform resolution across dimensions. Using Corollary C.4, we can refine each lower resolution component of F • β to resolution K:F • β, N = N j=1 β j ψ • j = K k=0 ℓ∈I d k β k,ℓ 2 kd/2 ω d k,ℓ = K k=0 ℓ ′ ∈I d K ℓ∈I d k γ k,K,ℓ,ℓ ′ β k,ℓ 2 Kd/2 ω d K,ℓ ′ .Thus each aggregated coefficient, indexed here by ℓ ∈ I d K , can be expressed asβK,ℓ = K k=0 ℓ∈I d k γ k,K,ℓ,ℓ ′ β k,ℓ .Hence it follows that E β [ β2 K,ℓ ] = K k=0 ℓ∈I d k γ 2 k,K,ℓ,ℓ ′ E β [β 2 k,ℓ ] ≲ K k=0 ℓ∈I d k γ k,K,ℓ,ℓ ′ 2 2 -k(2α+d) k -2 ≤ K k=0 2 (k-K)d • 2 -k(2α+d) k -2 ≲ 2 -Kd • K k=0 2 -2kα k -2 ≍ N -1 , from which we conclude that Tr(Σ β,N ) = ℓ∈I d K E β [ β2 K,ℓ ] ≲ N • N -1 ≤ p, q ≤ ∞, directional smoothness α = (α 1 , • • • , α d ) ∈ R d >0 and r = max i≤d ⌊α i ⌋ + 1, we define ∥•∥ B α p,q = ∥•∥ L p + | • | B α p,q where |f | B α p,q := ∞ k=0 2 k w r,p (f, (2 -k/α1 , • • • , 2 -k/α d )) q 1/q q < ∞ sup k≥0 2 k w r,p (f, (2 -k/α1 , • • • , 2 -k/α d )) q = ∞.The anisotropic Besov space is defined asB α p,q (X ) = {f ∈ L p (X ) | ∥f ∥ B α p,q < ∞}.The definition reduces to the usual Besov space if Vybíral (2006) ; Triebel (2011) for details. We also write α = max i α i , α = min i α i and the harmonic mean smoothness asα 1 = • • • = α d ; seeα := d i=1 α -1 i -1.For the anisotropic Besov space, we need to redefine the wavelet basis so that the sensitivity to resolution k ∈ Z ≥0 differs for each component depending on α. Define the quantities∥k∥ α/α := d i=1 ⌊kα/α i ⌋, I d,α k := d i=1 {-m, -m + 1, • • • , 2 ⌊kα/αi⌋ } ⊂ Z d .We then set for each k ≥ 0 and ℓ∈ I d,α k ω d,α k,ℓ (x) := ω d (⌊kα/α1⌋,••• ,⌊kα/α d ⌋),ℓ (x) = d i=1 ι m (2 ⌊kα/αi⌋ x i -ℓ i ),and take the scaled basis {ψ• j | j ∈ N} = {2 ∥k∥ α/α /2 ω d,α k,ℓ | k ∈ Z ≥0 , ℓ ∈ I d,αk } with the natural hierarchy induced by k.The minimax optimal rate for the anisotropic Besov space is equal to n -2 α 2 α+1 (Suzuki & Nitanda, 2021, Theorem 4) . Our result for in-context learning is as follows.Theorem C.7 (minimax optimality of ICL in anisotropic Besov space). Let α ∈ R d >0 with α > 1/p and F • = U(B α p,q (X )). Suppose that P X has positive Lebesgue density ρ X bounded above and below on X . Also suppose that all coefficients are independent andEQUATION)Then for n ≳ N log N we haveR( Θ) ≲ N -2 α + N log N n + N 2 log N T .Hence if T ≳ nN and N ≍ n 1 2 α+1 , in-context learning achieves the rate n -2 α 2 α+1 log n which is minimax optimal up to a polylog factor.The overall approach is similar to Appendix C.1. The decay rate of functions in the anisotropic Besov space is characterized by the following result which extends Lemma C.1.Transformers are Minimax Optimal Nonparametric In-Context Learners Lemma C.8 (Suzuki & Nitanda (2021) , Lemma 2). If α > 1/p and m > α + 1 -1/p, a function f ∈ L p (X ) is in MB α p,q (X ) if and only if f can be represented asf = k∈Z d ≥0 ℓ∈I d,α k βk,ℓ ω d,α k,ℓ (x)such that the coefficients satisfy∥ β∥ b α p,q := ∞ k=0 2 kα-∥k∥ α/α /p ℓ∈I d,α k | βk,ℓ | p 1/p q 1/q ≲ ∥f ∥ B α p,q .Moreover, the two norms ∥ β∥ b α p,q and ∥f ∥ B α p,q are equivalent.We again select all B-splines (ω d,α K,ℓ ) ℓ∈I d K at each resolution K to approximate the target functions. By repeatedly applying the refinement equation for one-dimensional wavelets as many times as needed to each dimension separately, we may express any B-spline at a lower resolution k < K as a linear combination of (ω d,α K,ℓ ) ℓ∈I d K similarly to Lemma C.2. See Proposition C.10 for details. We thus haveN = |I d,α K | = d i=1 (m + 1 + 2 ⌊Kα/αi⌋ ) ≍ 2 ∥K∥ α/α .Since ∥k∥ α/α = kα/ α + O k (1) always holds, it also follows thatN = K k=0 |I d,α k | + 1 ≍ K k=0 2 ∥k∥ α/α ≍ K k=0 (2 α/ α ) k ≍ 2 Kα/ α ≍ N and similarly N ≍ N . Therefore, N j= N ψ • j (x) 2 ≤ 2 ∥K∥ α/α ℓ∈I d,α k ω d,α K,ℓ (x) 2 ≤ 2 ∥K∥ α/α ≍ Nand the scaled coefficients decay in average as1 |I d,α k | ℓ∈I d,α k |β k,ℓ | p 1/p ≲ d i=1 2 ⌊kα/αi⌋ -1/p 2 -∥k∥ α/α /2 ℓ∈I d,α k | βk,ℓ | p 1/p ≲ 2 -∥k∥ α/α /2-kα ∥f ∥ B α p,q ≍ N -( α+1/2) ∥f ∥ B α p,q . For Assumption 2, we can check that ∥F • β ∥ L ∞ (P X ) ≤ ∞ k=0 ℓ∈I d,α k β k,ℓ • 2 ∥k∥ α/α /2 ω d,α k,ℓ L ∞ (P X ) ≤ ∞ k=0 2 (1/2+1/p)∥k∥ α/α 1 |I d,α k | ℓ∈I d,α k |β k,ℓ | p 1/p ≲ ∞ k=0 2 (1/2+1/p)∥k∥ α/α • 2 -∥k∥ α/α /2-kα ≲ 1 -2 α/ α(1/p-α) -1 =: Band for a resolution cutoff K > 0, N ≍ 2 ∥K∥ α/α the truncation error satisfies∥F • β -F • β, N ∥ 2 L 2 (P X ) ≲ ∞ k=K+1 ℓ∈I d,α k β 2 k,ℓ ≲ ∞ k=K+1 |I d,α k | 1-2/p ℓ∈I d,α k |β k,ℓ | p 2/p ≲ ∞ k=K+1 2 ∥k∥ α/α • 2 -∥k∥ α/α -2kα ≍ 2 -2Kα ≍ N -2 α .Thus we may set r = 1/2, s = α and take the variance decay rate (20) asE β [β 2 k,ℓ ] ≲ 2 -∥k∥ α/α (2 α+1) k -2 ≍ 2 -kα(2+1/ α)) k -2 .For boundedness of Tr(Σ β,N ), we use the following result which is also obtained from Proposition C.10 by considering resolution vectors(⌊kα/α 1 ⌋, • • • , ⌊kα/α d ⌋) and (⌊k ′ α/α 1 ⌋, • • • , ⌊k ′ α/α d ⌋).Corollary C.9. For any 0≤ k < k ′ there exists constants γ k,k ′ ,ℓ,ℓ ′ ≥ 0 for ℓ ∈ I d,α k , ℓ ′ ∈ I d,α k ′ such that ℓ∈I d,α k β k,ℓ 2 ∥k∥ α/α /2 ω d,α k,ℓ = ℓ ′ ∈I d,α k ′ βk ′ ,ℓ ′ 2 ∥k ′ ∥ α/α /2 ω d,α k ′ ,ℓ ′ , βk ′ ,ℓ ′ = ℓ∈I d,α k γ k,k ′ ,ℓ,ℓ ′ β k,ℓ holds for all (β k,ℓ ) ℓ∈I d,α k . Moreover, it holds that ℓ∈I d,α k γ k,k ′ ,ℓ,ℓ ′ ≤ 2 (∥k∥ α/α -∥k ′ ∥ α/α )/2 , ℓ ′ ∈I d,α k ′ γ k,k ′ ,ℓ,ℓ ′ ≤ 2 (∥k ′ ∥ α/α -∥k∥ α/α )/2 .We apply Corollary C.9 to refine all components of F • β,N to resolution K:F • β, N = K k=0 ℓ∈I d,α k β k,ℓ 2 ∥k∥ α/α /2 ω d,α k,ℓ = K k=0 ℓ ′ ∈I d,α K ℓ∈I d,α k γ k,K,ℓ,ℓ ′ β k,ℓ 2 ∥K∥ α/α /2 ω d,α K,ℓ ′ .Hence it follows thatE β [ β2 K,ℓ ] = K k=0 ℓ∈I d,α k γ 2 k,K,ℓ,ℓ ′ E β [β 2 k,ℓ ] ≲ K k=0 ℓ∈I d,α k γ k,K,ℓ,ℓ ′ 2 2 -kα(2+1/ α) k -2 ≤ K k=0 2 ∥k∥ α/α -∥K∥ α/α • 2 -kα(2+1/ α) k -2 ≲ 2 -∥K∥ α/α • K k=0 2 -2kα k -2 ≍ N -1 ,and we again conclude that Tr(Σ β,N ) is uniformly bounded.The rest of the proof proceeds similarly to the ordinary Besov space.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, kEQUATIONholds for all (β k,ℓ ) ℓ∈I d k . Moreover, it holds thatℓ∈I d k γ k,k ′ ,ℓ,ℓ ′ ≤ 2 -∥k ′ -k∥1/2 , ℓ ′ ∈I d k ′ γ k,k ′ ,ℓ,ℓ ′ ≤ 2 ∥k ′ -k∥1/2 .Proof. We proceed by induction on ∥k ′ -k∥ 1 . When k ′ = k + e j for some 1 ≤ j ≤ d, we can refine each ω d k,ℓ using equation (2.21) of Dũng (2011b) asω d k,ℓ (x) = d i=1 ι m (2 ki x i -ℓ i ) = 2 -m+1 i̸ =j ι m (2 ki x i -ℓ i ) m r=0 m r ι m 2 kj +1 x j -2ℓ j -r + m 2 = 2 -m+1 m r=0 m r ω d k+ej ,ℓ+(ℓj +r-m 2 )ej (x).Since ℓ + (ℓ j + r -m 2 )e j matches a given location vector ℓ ′ ∈ I d k+ej if and only ifℓ i = ℓ ′ i (i ̸ = j) and ℓ ′ j = 2ℓ j + r -m 2 , comparing coefficients in (21) yields γ k,k+ej ,ℓ,ℓ ′ = 2 -m+1/2 1 {ℓi=ℓ ′ i (i̸ =j)} m ℓ ′ j -2ℓ j + m 2 .Here, 1 A denotes the indicator function for condition A. It follows that γ k,k+ej ,ℓ,ℓ ′ ≥ 0 andℓ∈I d k γ k,k+ej ,ℓ,ℓ ′ ≤ ℓj ∈Z 2 -m+1/2 m ℓ ′ j -2ℓ j + m 2 ≤ 2 -1/2 , ℓ ′ ∈I d k+e j γ k,k+ej ,ℓ,ℓ ′ ≤ ℓ ′ j ∈Z 2 -m+1/2 m ℓ ′ j -2ℓ j + m 2 ≤ 2 1/2 ,by considering parities. Now suppose the claim holds for a fixed difference ∥k ′ -k∥ 1 . Applying the above derivation to further refine resolution k ′ to k ′′ = k ′ + e j for arbitrary j givesℓ∈I d k β k,ℓ 2 ∥k∥1/2 ω d k,ℓ = ℓ ′ ∈I d k ′ βk ′ ,ℓ ′ 2 ∥k ′ ∥1/2 ω d k ′ ,ℓ ′ = ℓ ′′ ∈I d k ′ +1 βk ′ +1,ℓ ′′ 2 (∥k ′ ∥1+1)/2 ω d k ′ +ej ,ℓ ′′ where βk ′ +ej ,ℓ ′′ = ℓ ′ ∈I d k ′ 2 -m+1/2 1 {ℓ ′ i =ℓ ′′ i (i̸ =j)} m ℓ ′′ j -2ℓ ′ j + m 2 βk ′ ,ℓ ′ = ℓ∈I d k ℓ ′ ∈I d k ′ 2 -m+1/2 1 {ℓ ′ i =ℓ ′′ i (i̸ =j)} m ℓ ′′ j -2ℓ ′ j + m 2 γ k,k ′ ,ℓ,ℓ ′ β k,ℓ .Then the piecewise γ-smooth function class is defined asP γ p,q (P X ) := g = f • Π | f ∈ F γ p,q (P X ), ∥g∥ P γ p,q (P X ) < ∞ ,where∥g∥ P γ p,q (P X ) := s∈ Nd×[-V :V ] 0 2 qγ(s) ∥δ s (f ) • Π∥ q p,P X 1/q .Next, we state the set of assumptions inherited from Takakura & Suzuki (2023) . In particular, the importance function makes precise a notion of relative importance between tokens which is preserved by permutations.Assumption 5 (smoothness and importance function). 1 < q ≤ 2 and:1. The smoothness parameter α satisfies ∥α∥ wl η ≤ 1 and α ij = Ω(|i| η ) for some η > 1. For mixed smoothness, we also require α1 < α2 .2. There exists a shift-equivariant map µ : suppP X → R ∞ such that µ 0 ∈ U(F γ ∞,q ), ∥µ 0 ∥ ≤ 1 and Ω λ = {x ∈ supp P X | µ(x) π λ (1) > • • • > µ(x) π λ (2V +1) } for all λ ∈ Λ. µ is moreover well-separated, that is µ(x) π λ (v) - µ(x) π λ (v+1) ≥ C µ v -ϱ for C µ , ϱ > 0.We focus on parameter ranges 1 < q ≤ 2 and η > 1 strictly for simplicity of presentation, but the cases q = 1, q > 2 and η > 0 can be handled with some more analysis. Note that η > 1 ensures α † > 0 for anisotropic smoothness.Additionally, the assumption pertaining to our ICL setup is stated as follows.Assumption 6. For r ∈ Z d×∞ 0 the coefficients β r corresponding to ψ r are independent and satisfy for s ∈ Nd×∞ 0 such that the frequency component δ s (f ) contains the element ψ r ,EQUATION)Also Σ Ψ,N ≍ I N holds, for example P X is bounded above and below with respect to the product measure λ d×∞ on B([0, 1] d×∞ ) of the uniform measure λ on 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 • = {f ∈ U(P γ p,q (P X )) | ∥f ∥ L ∞ (P X ) ≤ B} for some B > 0 where γ corresponds to mixed or anisotropic smoothness. Suppose Assumptions 5 and 6 hold. Then for n ≳ N log N we haveR( Θ) ≲ N -2α † + N log N n + N 2∨(1+1/α † ) polylog(N ) T .Hence if T ≳ nN 1∨1/α † and N ≍ n Since the system (ψ r ) r is orthonormal, we may take N = 1, N = N following Remark 2.1. We mainly utilize the following approximation and covering number bounds.Theorem D.2 (Takakura & Suzuki (2023) , Theorem 4.5). For a function F • ∈ U(P γ p,q (P X )), ∥F • ∥ L ∞ (P X ) ≤ B and any K > 0, there exists a transformer F ∈ F TF (J, U, D, H, L, W, S, M ) such that∥ F 0 -F • ∥ L 2 (P X ) ≲ 2 -K , where J ≲ K 1/η , log U ≲ log K ∨ log V, D ≲ K 2(1+ϱ)/η log V, H ≲ (log K) 1/η , L ≲ K 2 , W ≲ 2 K/α † K 1/η , S ≲ 2 K/α † K 2+2/η , log M ≲ K ∨ log log V.E.1. Proof of Proposition 5.1In this section, we develop our framework for obtaining minimax lower bounds in the ICL setup by adapting the informationtheoretic approach of Yang & Barron (1999) .Let {(ψ (j) , βT +1 )} M j=1 be a δ n -packing of the class F • with respect to the L 2 (X )-norm such that ∥β (j)⊤ T +1 ψ (j) -β(j ′ )⊤ T +1 ψ (j ′ ) ∥ 2 L 2 (X ) ≥ δ 2 n , 1 ≤ j < j ′ ≤ M,where M is the corresponding packing number. Then we have the following proposition as an application of Fano's inequality (Yang & Barron, 1999) .Proposition E.1. Let Θ be a random variable uniformly distributed over {(ψ (j) , βT +1 )} M j=1 . Then, it holds thatinf fn:D n,T →R sup f • ∈F • E Dn [∥ f -f • ∥ 2 L 2 (P X ) ] ≥ δ 2 n 2 1 - E X [I X (1:T +1) (Θ, y (1:T +1) )] + log 2 log M ,where I X (1:T +1) (Θ, y (1:T +1) ) is the mutual information between Θ, y (1:T +1) for given X (1:T +1) .The mutual information I X (1:T +1) (Θ, y (1:T +1) ) is formulated more concretely as θ∈supp Θ w(θ) p(y (1:T +1) |θ, X (1:T +1) ) log p(y (1:T +1) |θ, X (1:T +1) ) p w (y (1:T +1) |X (1:T +1) ) dy (1:T +1) , where p(y|θ, X) is the probability density of y conditioned on θ, X and p w is the marginal distribution of y (1:T +1) where w(•) ≡ 1 M is the probability mass function of Θ. We let P y (t) |θ (and P y (1:t) |θ ) be the distribution of y (t) conditioned on θ, X (t) (and X (1:t) ) respectively, and let Py (1:T +1) = 1 M M j=1 P y (1:t) |θ (j)be the marginal distribution of y (1:T +1) conditioned on X (1:T +1) .Next, we define the set { ψ(j) } Q1 j=1 to be a ε n,1 -covering of F N w.r.t. the norm d(ψ, ψ ′ ) := E x [∥ψ(x) -ψ ′ (x)∥ 2 ] with ε n,1 -covering number Q 1 , and { β(j) } Q2 j=1 to be a ε n,2 -covering of B w.r.t. the L 2 norm with ε n,2 -covering number Q 2 . By taking all combinations of ( ψ(j) , β(j ′ ) ) for 1 ≤ j ≤ Q 1 and 1 ≤ j ′ ≤ Q 2 , we obtain the covering { θ(j) } Q j=1 with respect to the quantity ε 2 n = σ 2 β ε 2 n,1 + C 2 ε 2 n,2 where Q = Q 1 Q 2 and each θ(j) is given by θ(j) = ( ψ(j1) , β(j2) ) for some indices j 1 and j 2 .Then as in the discussion of Yang & Barron (1999) , the mutual information is bounded by Moreover, for θ = (ψ, β (T +1) ) it holds that p(y (1:T +1) |θ, X (1:T +1) ) = T t=1 p(y (t) |ψ, X (t) ) • p(y (T +1) |ψ, β (T +1) , X (T +1) ) = T t=1 p(y (t) |ψ, β (t) , X (t) )p β (β (t) )dβ (t) • p(y (T +1) |ψ, β (T +1) , X (T +1) ).Then the KL-divergence can be bounded as ∥P y (T +1) | ψκ(j) , β(κ(j))T +1, where the joint convexity of KL-divergence was used for the last inequality. Since the observation noise is assumed to be normally distributed, the integrand KL-divergence can be bounded asD P y (t) |ψ (j) ,β ∥P y (t) | ψκ(j) ,β = n i=1 1 2σ 2 β ⊤ ψ (j) (x (t) i ) -β ⊤ ψ(κ(j)) (x (t) i ) 2 .Hence, its expectation with respect to β, X (t) becomes E X (t) ,β D P y ψ(κ(j)) (x(t) i ) 2 ≤ n i=1 1 2σ 2 β (j)T +1 -β(κ(j))T +1⊤ ψ(κ(j)) (x(t) i ) 2 + n i=1 1 2σ 2 β (j)⊤ T +1 (ψ (j) (x (t) i ) -ψ(κ(j)) (x (t) i )) 2 .The expectation of the right-hand side with respect to X (T +1) , βT +1 is bounded asEQUATIONT +1D P y (T +1) |ψ (j) ,β (j)T +1∥P y (t) | ψκ(j) , β(κ(j))T +1 ≤ C 2 n 2σ 2 ∥β (j) T +1 - β(κ(j)) T +1 ∥ 2 + n 2σ 2 σ 2 β ∥ψ (j) -ψ(κ(j)) ∥ 2 L 2 (P X ) ≤ C 2 n 2σ 2 ε 2 n,2 + n 2σ 2 σ 2 β ε 2 n,1 = n 2σ 2 ε 2 n .Therefore, the expected mutual information can be bounded asE X [I X (1:T +1) (Θ, y (1:T +1) )] ≤ log Q 1 + log Q 2 + nT 2σ 2 σ 2 β ε 2 n,1 + n 2σ 2 ε 2 n .Applying Proposition E.1 together with (7) concludes the proof.University of Tokyo, Tokyo, JapanCenter for Advanced Intelligence Project, RIKEN, Tokyo, Japan. Correspondence to: Juno Kim <junokim@g.ecc.u-tokyo.ac.jp>. Proceedings of the 1 st Workshop on In-Context Learning at the 41 st International Conference on Machine Learning, Vienna, Austria. 2024. Copyright 2024 by the author(s).This implies Var ξ k ≤ σ. We require boundedness since the values y k form part of the prompt input, and we wish to utilize sup-norm covering number estimates for the attention map; this technicality can be removed with more careful analysis. However, for the information-theoretic lower bound we assume Gaussian noise.Here the ith column and (j, i)th component of x ∈ R d×∞ for i ∈ Z, j ∈ [d] are denoted by xi and xij, respectively. These are not to be confused with sample indexes (1) as those will not be used in this section. 


Decision: 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.

Reviews: review: paper_summary: paper_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.

The 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$.

The 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.

Additional 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.
strength_weakness: strength_weakness: I think the main weakness is that the techniques used to show Theorem 4.5 are somewhat standard. 
- 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.
- 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.
questions: 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?
- 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: limitations: Yes.
paper_summary: paper_summary: This work shows that ICL can perform non-parametric regression at an optimal rate.

Section 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).

There 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.
strength_weakness: strength_weakness: 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?

Is 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.
questions: 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.

What 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?

It would be helpful to instantiate a target function class in the main paper, specify what $\alpha$ is, etc.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.
questions: 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. 

Could the authors provide more detailed explanations on how this work connects to the mechanisms of ICL and LLMs in practice?
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Lack 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.
questions: 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.

2. 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: 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.

Comments: comment: Thank you for your response. I will raise my score to a 5.
We are very grateful to the reviewer for re-evaluating our contributions and raising their score! Here are some further clarifications:

* Wavelet systems form a hierarchy ordered by resolution, and wavelets with lower resolution can always be written as a combination of those with higher resolution (forming the basis of *multiresolution analysis* theory). Hence the covariance matrix is indeed never invertible, necessitating our new 'aggregation' techniques.
* ICL can be viewed as a meta-learner which takes as input not just $n$ samples from the current task but also $(n+1)T$ samples from related tasks. Now also consider $T$ as a variable. It could be the case that a well-designed meta-estimator (possibly not constrained to be fixed at inference time) can achieve a rate faster than $n^{-\frac{2\alpha}{2\alpha+d}}$ by taking all these samples as input, as the ordinary minimax rate only applies to estimators which only learn from $n$ ground-truth samples. Our lower bound shows that this is impossible: *any* estimator that takes the $n$ ground-truth \& $(n+1)T$ related samples as input is still lower bounded by $n^{-\frac{2\alpha}{2\alpha+d}}$. Since our upper bound matches this when $T$ is sufficiently large, we conclude that ICL is **optimal in both** $n,T$. Conversely, the new lower bound $n^{-\frac{2\alpha}{2\alpha+d}} + (nT)^{-\frac{2\tau}{2\tau+d}}$ in the coarser basis setting allows us to conclude that ICL (or any other meta-learner) is **suboptimal in both** $n,T$ when $T<n^{\frac{(\alpha-\tau)d}{\tau(2\alpha+d)}}$, supplementing our upper bound in Corollary 4.9.
* The selection of $N$ is standard rate analysis, except that we also have to consider the effect of $T$ through the pretraining gap. Let's look at Theorem 4.5. First assume $T\gtrsim nN$ so that the 3rd term can be ignored compared to the 2nd term. Then we want to choose $N$ such that $N^{-2\alpha/d}+\frac{N\log N}{n}$ is minimized, which can be found by balancing $N^{-2\alpha/d}\asymp\frac{N}{n}$ and thus $N\asymp n^\frac{d}{2\alpha+d}$ (ignoring log terms). However if $T<nN$ then the 3rd term dominates and $N^{-2\alpha/d}+\frac{N^2\log N}{T}$ is minimized when $N\asymp T^\frac{d}{2\alpha+2d}$, so the overall risk is now bounded suboptimally as $T^{-\frac{\alpha}{\alpha+d}}$.
* Corollary 4.9 is similarly tuned and the bound cannot be optimized further as we also proved it is optimal in both $n,T$ when $T$ is large. Again there is some suboptimal scaling when $T$ is small, but -- as we indicate in our global response -- for this regime it is better to look at the information-theoretic lower bound which gives a rigorous proof of suboptimality.
Thank you for the detailed reply. I am not familiar with the literature on wavelet systems, but since the covariance matrix may not be invertible, this suggests that the analysis in this work is more than a direct extension of Zhang, et al. The lower bound in the coarser basis setting is also an interesting takeaway. I will increase my score to 6.

Could you please clarify the following:
- For your main setting, you mention in the global response that your upper bound is jointly optimal in $n, T$. In what sense is it optimal in $T$?
- How do you select $N$ in Theorem 4.5 and Corollary 4.9? Would it be possible to optimize the bound in Corollary 4.9 further by selecting a different $N$?
Thanks for the response. I will maintain my positive score.
Thank you again for your time and effort in reviewing our paper! As the discussion period is ending soon, we are following up to see if our response was satisfactory in addressing the reviewer's questions. If not, we would be happy to discuss any remaining concerns.
Thank you again for your time and effort in reviewing our paper! As the discussion period is ending soon, we are following up to see if our response addressed the reviewer's questions. If so, we hope that they would be willing to increase their score. If not, we would be happy to discuss any remaining concerns.
Thank you again for your time and effort in reviewing our paper! As the discussion period is ending soon, we are following up to see if our response addressed the reviewer's questions. If so, we hope that they would be willing to increase their score. If not, we would be happy to discuss any remaining concerns.
Thank you for taking the time to read our rebuttal! As your criticisms were generally on the lack of numerical experiments, if there are any other types of experiments which you believe will further benefit our paper, please inform us and we will strive to implement them to gain more insight into our analyses.
Thanks for the reply. My questions are partly addressed and I'll maintain my rating.
(continued from rebuttal)

* **Isn't is unrealistic that $N$ should scale in $n$ for a real transformer?**

In practice we agree that the architecture should not depend on $n$, especially if prompts of any length are allowed. However since we assume **all** prompts (during both pretraining and ICL) are of fixed length $n$, it is reasonable to choose a more powerful architecture for larger $n$.

Strictly speaking, $N$ does not need to scale in $n$ since our bounds hold for all $N,n,T$. But the bound itself is natural: as we mentioned, approximation error must decrease in $N$ due to the infinite dimensionality of the target class, and generalization error should of course decrease in $n,T$. For example if $N$ is considered fixed, the bound is interpreted as an excess risk of $O(1/n+1/T)$. However we want to obtain the *overall* sample complexity rate in $n$, which necessitates $N$ to scale in $n$. The rate itself is less important than the fact that it is the *best rate attainable by any estimator*, and the optimality result should be viewed more as guaranteeing tightness of the derived bounds (further justified by Section 5) than a prescription of how $N,T$ should scale.

We also mention that this approach is standard in minimax analyses. For example, rate-optimal scaling for ordinary supervised regression with DNNs (Suzuki, 2019) also requires the width to scale as $n^{\frac{1}{2s+1}}$ even though the smoothness of the target is unknown.

* **Rebuttal End**

Finally, we 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.