When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective
Authors: Alireza Mousavi-Hosseini
Clayton Sanford
Denny Wu
Murat A Erdogdu
Venue: NeurIPS 2025 poster ()
Keywords: Transformer
RNN
Generalization Bounds
Sample Complexity
Primary area: theory
TL;DR: We prove a purely statistical separation between Transformers and other architectures such as feedforward and recurrent networks, where Transformers are more sample-efficient at learning sparse sequence models.

Abstract: Theoretical efforts to prove advantages of Transformers in comparison with classical architectures such as feedforward and recurrent neural networks have mostly focused on representational power. In this work, we take an alternative perspective and prove that even with infinite compute, feedforward and recurrent networks may suffer from larger sample complexity compared to Transformers, as the latter can adapt to a form of dynamic sparsity. Specifically, we consider a sequence-to-sequence data generating model on sequences of length $N$, where the output at each position only depends on $q \ll N$ relevant tokens, and the positions of these tokens are described in the input prompt. We prove that a single-layer Transformer can learn this model if and only if its number of attention heads is at least $q$, in which case it achieves a sample complexity almost independent of $N$, while recurrent networks require $N^{\Omega(1)}$ samples on the same problem. If we simplify this model, recurrent networks may achieve a complexity almost independent of $N$, while feedforward networks still require $N$ samples. Our proposed sparse retrieval model illustrates a natural hierarchy in sample complexity across these architectures.

When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective
Alireza Mousavi-Hossein'' Clayton Sanford', Denny Wu', Murat A. Erdogdu'
Universitt of Toronto and Vector Institute, ?Google Research,
New York University and Flatiron Institute
(mousavi, erdogdu) toronto. edu, chsanford@google.com com, dennyvu@nyu. edu
Abstract
Theoretical efforts prove advantages of Transformers in comparison with classi- cal architectures such as feedforward and recurrent neural networks have mostly focused on representational power. In this work, we take an alternative perspective and prove that even with infinite compute, feedforward and recurrent networks may suffer from larger sample complexity compared to Transformers, the latter can adapt to a form of dynamic sparsity. Specifically, we consider a sequence-to- sequence data generating model sequences of length N, where the output at each position only depends on < relevant tokens, and the positions of these tokens are described in the input prompt. We prove that single-layer Transformer learn this model if and only its number of attention heads is at least q. in which case it achieves sample complexity almost independent of N, while recurrent networks require R(1) samples the same problem. If simplify this model, recurrent networks may achieve a complexity almost independent of N, while feedforward networks still require N samples. Our proposed sparse retrieval model illustrates a natural hierarchy sample complexity across these architectures.
Introduction
The Transformer [VSP+ 17], neural network architecture that combines attention and feedforward blocks, forms the backbone of large language models and machine learning approaches across many domains [RNSS18, DBK 20. BMR+20], The theoretical efforts surrounding the success of Transformers have so far demonstrated various capabilities like in-context learning [ASA+2] VONR 23, BCW 23, ZFB24, KNS24, and others] and chain-of-thought prompting along with its benefits [FZG* 23, MS24, LLZM24, KS24, and others] in various settings. There are fewer works that provide specific benefits Transformers in comparison with feedforward and recurrent architectures. On the approximation side, there are tasks that Transformers can solve with size logarithmic in the input, while alternative architectures require polynomial size [SHT23, SHT24]. Based on these results, [WWHL24] showed a separation between Transformers and feedforward networks by providing further optimization guarantees for gradient-based training of Transformers on sparse token selection task.
While most prior works focused on the approximation separation between Transformers and feedfor- ward networks (FFNs), in this work we focus on a purely statistical separation, and ask:
What function class can Transformers learn with fewer samples compared feedforward and recurrent networks, even with infinite computational resources?
[FGBM23) approached the above problem with random features, where the query-key matrix for the attention and the first layer weights for the two-layer feedforward network were fixed random
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Statistical Model
Feedforward
RNN
Transformer
Simple-gSTR
X (Theorem 9)
(Theorem 5)
(Theorem 3)
gSTR
x (Theorem 9) X
(Theorem 7)
(Theorem 3)
Table 1:
Summary of main contributions (see Theorem 1). / indicates a sample complexity upper bound that is almost sequence length-frre free (up to polylogarithiic factors). indicates a lower bound of order NQ0))
initialization. However, this only presents a partial picture, as neural networks can learn significantly larger class of functions once "feature learning" is allowed, i.e., parameters are trained to adapt the structure of the underlying task [Bac 17, BES+22, 22, DLS22, BBSS22, O AAM23, MHWE24)..
We evaluate the statistical efficiency of Transformers and alternative architectures by characterizing how the sample complexity depends on the imput sequence length. A benign length dependence (e.g., sublinear) signifies the ability to achieve low test error in longer sequences, which intuitively connects the length generalization capability [AWA 22]. While Transformers have demonstrated this ability in certain structured logical tasks, they fail in other simple settings [ZBL_ 23, LAG 23]. Our generalization bounds for bounded-ne norm Transformers - along with our contrasts to RNNs and feedforward neural networks provide theoretical insights into the statistical advantages of Transformers and lay the foundation for future rigorous investigations of length generalization.
1.1 Our Contributions
We study the q-Sparse Token Regression (gSTR) data generating model, a sequence-to-sequenee model where the output every position depends on a sparse subset of the input tokens. Importantly, this dependence is dynamic, i.e., changes from prompt to prompt, and is described in the input itself. We prove that by employing the attention layer to retrieve relevant tokens at each position, single- layer Transformers can adapt to this dynamic sparsity, and learn 4STR with a sample complexity almost independent of the length of input sequence N, as long as the number of attention heads is at least g. On the other hand, we develop a new netric-entropy--asee argument to derive norm and parameter-coumt lower bounds for RNNs approximating the 4STR model. Thanks to lower bounds on weight norm, we also obtain sample complexity lower bound of order NT(11) for RNNs. Further, we show that RNNs can learn subset of gSTR where the output is constant sequence, which we call simple-gSTR, with sample complexity polylogarithmic lower bound technique for feedforward networks (FFNs) that takes advantage of the fully connected projection of the first layer to obtain a sample complexity lower bound linear in N, even when learning simple-gSTR models. The following theorem and Table summarize our main contributions.
N. Finally, we develop a
Theorem (Informal). We have the following hierarchy of statistical efficiency for learning gSTR.
A single-layer Transformer with H 2 9 heads learn qSTR with sample complexity almost independent of N, and cannot learn 9STR when H < q even with infinitely many samples.
RNNs can learn simple-qSTR with sample size almost independent of N, but require at least S2(Ne) samples for some constant c. to learn a generic qSTR model, regardless of their size.
Feedforward neural networks, regardless of their size, require ((Nd) samples to learn even simple-gSTR models, where d is input token dimension.
We empirically validate the intuitions from Theorem 1 in Figure 1. Observe that on a 1STR task, both FFNs and RNNs suffer from a large sample complexity for larger N. However, for a 1mmll--STTR model, RNNs perform closer to Transformers with much milder dependence on N than FFNs.
1.2 Related Work
While generalization is fundamental area of study in machine learning theory, theoretical work on the generalization capabilities of Transformers remains relatively sparse. Some works analyze the inductive biases of self-attention through connections to max- max-margin SVM classifiers [VDT24]. Others quantify complexity in terms of the simplest programs in a formal language (such as the RASP model of [YCA23]) that solve the task and relate that to Transformer generalization + CS24]. The most relevant works to our own are [EGK7222, TT23, Tru24], which employ covering numbers to bound the sample complexity of deep Transformers with bounded weights. They demonstrate a logarithmic scaling in the sequence length, depth, and width and apply their bounds
2

---

193008
Tranffrmer
000000
Tranformee
N. (Trainnnng Samples)
(Training Samples)
100000
500000
+00000
00000
000000
00000
20030
193300
N (loput Longth)
N (Input Length)
(a) Sample complexity (ISTR)
(b) Sample complexity (Simple-1SH) ISTR)
Figure 1: Number of samples required to reach certain test MSE loss threshold while training with online A. We consider (a) the 1STR model with loss threshold 0.7 and (b) the simple- ISTT model with loss threshold 0.02, averaged over experiments.
use a linear link function, standard Gaussian input, d 10 and d. = [5 log (N) Positional encodings are sampled uniformly from the unit hypercube. Experimental details and additional results on the effect of q are provided in Appendix E.
to the learnability of sparse Boolean functions. We refine these covering number bounds to better characterize generalization sequence-to-sequemee learning with dynamic sparsity [SHT23]. Our problems formalize long-context reasoning tasks, extending beyond simple retrieval to include challenges like multi-round coreference resolution [VOT+24].
Expressivity of Transformers. The expressive power of Transformers has been extensively studied in prior works. Universality results establish that Transformers can approximate the output of any continuous function Turing machine [YBR 19, WCM21], as well meeasrre-to-massiee maps [GRRB24), and their memorization capacity is well-understood [MLT24].. However, complexity limitations remain for bounded-size models. Transformers with fixed model sizes unable to solve even regular languages, such as Dyck and Parity [BAG20, Hah20J. Further work [e.g. MS23] relates Transformers boolean circuits to establish the hardness of solving tasks like graph connectivity with even polynomial-width Transformers. Additionally, work on self-attention complexity explores how the embedding dimension and number of heads affects the ability of attention layers approximate sparse matrices [LCW21], recover searest-neighbor associations [AYB24], and compute sparse averages [SHT23]. The final task closely resembles our cSTR model and has been applied to relate the capabilities of deep Transformers to parallel algorithms [SHT24]. Several works [c.g. JBKM24, BHBK24, WDL24] introduce sequential tasks where Transformers outperform RNNs or other state space models in parameter-efficien expressivity. We establish similar architectural separations with an added focus on generalization capabilities.
Statistical Separation. Our work is conceptually related to studies on feature learning and adaptiv- ity in feedforward networks, particularly learning models with sparsity and now-dimensional structures. Prior work has analyzed how neural networks and gradient-base optimization in- troduce inductive biases that facilitates the learning of low-rank and low-dimensional functions [LMZ18, WILLM19, CB20, MHPG+22 23, OSSW24). These studies often demonstrate favorable gen- eralization properties based on certain structures of the solution such as large margin low norm [BFT17, NLB 18, OWSS19, WLLM191. Our goal is to extend efficient learning of low-dimensional concepts to sequential architectures, ensuring sample complexity remains efficient both input dimension d and context length N. Our approach, motivated by [SHT23, WWHL24), suggests that 4STR is a sequential model whose sparsity serves as low-dimensional structure, making the primary determinant of generalization complexity for Transformers.
Notation. For a natural number n, define [n]] == (1,...,m) n). We use I1-1|, to denote the lp norm of vectors. For matrix A E Rmxn lp.g = [] (I,
A 1,)1 and |A||ap denotes the operator norm of A. We use a S and < (b) interchangeably. which means a S Cb for some absolute constant C. We similarly define 2 and Ω. Ô and Ω hide multiplicative constants that depend polylogarithmically problem parameters. denotes the ReLU activation.
3

---

2 Problem Setup
Statistical Model. In this paper, we will focus on the ability of different architectures for learning the following data generating model. Definition 2 (g-Sparse Token Regression). Suppose p. y ~ P where
11
p =
t E [N] and 2; E I for [N]. In the q-sparse token regression (qSTR) data generating model, the output is given by y = (y),-.. yN) E R.N, where
y g Tr..):
for some 12dd + IR. We call this model simple-qSTR if the data distribution is such that t; = t for all i [N] and some drawn from [N]
The above defines a class of sequence-to to -equuenece functions, where the label at position in the output sequence depends only on subsequence of size q of the input data, determined by the set of indices t,. in the above definition denotes the prompt or context. Given the large context length of modern architectures, we are interested a setting where q < N. In this setting, the answer at each position only depends Therefore, we seek architectures that are adaptive to this form of dynamic sparsity in the true data generating process, with computational and sample complexity independent of N. As special case, choosing g as the tokens' mean recovers the sparse averaging model proposed in [SHT23], where the authors separate the representational capacity of Transformers and other architectures.
few tokens, however the tokens it depends on change based on the context.
While our main motivation for using the qSTR model is the role of this model as a theoretical benchmark (cf. [SHT23, WWHL24]), we now present an example of how tasks similar to 9STR can arise in natural language modeling. Consider the prompt "For my vacation this summer, I'm considering either Paris or Tokyo. If' go to Puris, I want to visit their art museums, and if end up in Tokyo, I want to try their cuisine. Can you tell me how much would my first and second option cost respectively?" ?" In this case, f is the token first and refers to the tokens Paris and art museumes, while &2 is the token second and refers to the tokens Tokyo and cuisine. Note that for either tı or tz. the answer to the prompt only depends demonstrates the case of = 2. We refer the interested readers to the multi-round conference resolution task of [VOT+24) 24] for more realistic examples in evaluating large models.
two tokens out of the entire context, thus this example
To obtain statistical guarantees, we will impose mild moment assumptions on the data.
Assumption 1. Suppose B|||a,11"]' < dr and Blyya M S /Cgr for all 2 1, [N]. and some absolute constants $ 2 and Cz, Cy > 0.
We only require the above assumption establish standard concentration bounds, and it is satisfied as soon as || | is subGaussian and is sub-Weibull (c.g. grows at most like polynomial of degree s). Learning the 4STR model requires two steps: (i) extracting the relevant tokens each position, (ii) learning the link function g. We are interested in settings where the difficulty of learning is dominated by the first step. hence we assume g can be approximated by a two-layer feedforward network.
Assumption 2. There exist my N, ag. by E mm and W R xad such that ||a ll2 S ral Mag. and [[( g. b,) || I migr for some constants Ta, Tw > 0. and
|9(0),.... ..la....... m.)) ag (W ...,,,,,,.. x.. "T)TT + by)) < E2nx.
sup
where C= 3C2e and 6zm is some absolute constant.
Ideally, E2ex above is a small constant denoting the approximation error. This assumption can be verified using various universal approximation results for ReLU networks. For example, when is an additive model of P Lipschitz functions, where each function depends only on a k-dimensional projection of the input, the above holds for every 2 > 0 and my = (((P/ /emm)"))))))))) ra = ((P) Vezm)) (k+1)/2) and rw (we can always have Tw = 1 by homogeneity) [Bac17].

---

Empirical Risk Minimization. While Empirical Risk Minimization (ERM) is a standard abstract learning algorithm use for generalization analysis, its standard formalizations use risk functions for scalar-valued predictions. Before introducing the notions of FRM that we employ, we first state several sequential risk formulations to evaluate a predictor Mare )) E Jare on i.i.d. training samples (p(), ( 1==1 where are denotes a general architecture. We define the population risk, averaged empirical risk, and point-wise empirical risk respectively as
N
(+) = N
E
Ware (p: 0) - -1;)² = N
E B (p: )) - v12
(2.1)
(P,,(()) = nN
Zi=1 Z=== (Jarc (p(1); 0); Ug (8) )
(2.2)
(e (0)
(Jarc(p!); 2 )) -V(c)) )
(2.3)
where (5 Ji=1 are i...d position indices drawn from Uni[([N]]..T The goal is to minimize the popula- tion risk ( by minimizing some empirical risk, potentially with weight regularization. We use three formalizations of learning algorithms to prove our results.
1. Constrained ERM minimizes an empirical risk Ra subject to the model parameters belonging on some (e.g., norm-constrainedd set O Concretely, let
E arg mingge R (+).
Theorem 3 considers constrained ERM algorithms for bounded-wedt weight transformers with point- wise risk ( and Theorem 5 uses PAAN for RNNs. Note that upper bounds for training with pisnt-wise empirical risk Røre readily transfer training with averaged empirical risk R,N-
Min-norm E-ERM minimizes the norm of the parameters, subject to sufficiently small loss:
arg min (O: ( fereSe) Se}
mig
vec (r)22
(2.4)
Theorem uses min-norm &EERM to place a sample complexity lower bound سm (e).
3. Beyond ERM, Theorem also considers stationary points of the averaged or point-wise loss, with l2 regularization. This learning algorithm is presented in greater detail in Definition 8.
If T is defined by norm constraint, then min-norm e-ERM with proper can be seen instance of constrained ERM. All three formulations are motivated by practical optimization algorithms that either minimize an explicitly regularized loss, have an implicit bias towards min-norm solutions.
3 Transformers
A single-layer Transformer is composed of an attention and parallel feedforward layer. Given sequence {z.) of input embeddings where 2, R. with embedding dimension De. a single head of attention outputs another sequence of length N in R DD given by
N
(W
W fAcea(p: Wo. WK. Wv) = Σ
M
W Wo..
SEIN]
Where WR W Q, Wy y are the key, query, and value projection matrices respectively. The output of И units of attention can be concatenated to form multi-head attention with output h e I A two-layer neural network acts on to generate the final output sequence via
fax Baw(h: (h; azm, W 2mn, baxx) a W 20ch ba
W 2xx
R BDD a2mx bzm E I
Our architectural choices are standard in theoretical studies of Transformers. We provide full details, including how to obtain input embeddings by positional encoding, in Appendix A.I.
5

---

3.1 Learning Guarantees for Multi-Head Transformers
We consider the following parameter class OR (Ilvo(())] I R) and provide learning guaran- tee for empirical risk minimizers over Qa. with its proof deferred to Appendix A.2.
Theorem 3. Let Ô arg men (
(O) and mra./g + maru + /ddd.. Under Assumptions 2 and 3, we have
mg. Suppose
H q and R
R (Q.) S Ezmu + + +0( ((a/ mag(d + q) + qp + qdz
n
where C₁ = R22 qd, with probability at least 1 - - - for some absolute constant e >>> O.
We make the following remarks.
First, the sample complexity above depends on N only up to log factors. Second, we can remove the C₁ factor by performing a clipping operation with a large constant on the Transformer output. Note that the first and second terms in the RHS above denote the approximation and estimation errors respectively. Extending the above guarantee to cover m 2 my and H 2 q is straightforward.
This bound provides guidance on the relative merits of scaling the parameter complexity of the feedforward versus the attention layer (which is an active research area related to Transformer scaling laws [HSSL24, 24). by highlighting the trade-off between the two to achieve minimal generalization error. Concretely, my > d q represents regime where the complexity is dominated by the feedforward layer learning the downstream task g. while mg < d + signifies dominance of the attention layer learning to retrieve the relevant tokens.
Finally, by incorporating additional structure in the FRM solution, it is possible to obtain improved sample complex- ities. close study of the optimization dynamics may reveal such additional structure in the solution reached by gradient- based methods, pushing the sample complexity closer to the inffrrmttion-theorett limit of (gdd. Figure 2 demonstrates that the attention weights achieved through standard optimiza- tion of Transformer match theoretical constructions see Equation (A.2) even while maintaining separate Wq and W к during training (we use the 1STR setup of Figure with N = 100). We leave the study of optimization dynamics and the resulting sample complexity for future work.
Attention Weights
Weught Magnitude
Trained attention weights match our theoretical construction (A.2).
Figure 2:
3.2 Limitations of Transformers with Few Heads
We establish the necessity the linear dependence of H on q. contrast to [AYB24], we do not put any assumptions the rank of the kuy-query projections, i.c. our lower bound applies even when the key-query projection matrix is full-rank.
Proposition 4. Consider a qSTR model where y; Vqd Ei=1 (1 112 E[ [12]) x, (0, Σg) such that E; = La i < N/2 and E, = f i N/2. Then, there exists a distribution over (t.)setn) such that for any choice of Ora (including arbitrary {w/l) (hem)) we have
(g + d)H
N E 1ly DTa (p: 1TR) 2
qd
We highlight the importance of the nonlinear dependence of y on for the above lower bound. In particular, for the sparse token averaging task introduced in [SHT23], a single-head attention layer with a carefully constructed embedding suffices for approximation.
Remark.
The above proposition implies that given sufficiently large dimensionality d >>>>> q, approximation alone necessitates at least H H heads. In Appendix A.3, we present the proof of Proposition 4, along with Proposition 21 which establishes an exact lower bound 2 g for all 1, at the expense of additional restrictions the query-key projection matrix.

---

Recurrent Neural Networks
In this section, first provide positive results for RNNS by proving that they can learn simple-gSTTR with sample complexity only polylogarithmic in N, thus establishing separation in their learning capability from feedforward networks. Next, we turn to general gSTR, where provide negative result on RNNs, proving that to learn such models their sample complexity must scale with N9(1) regardless model size, making them less statistically efficient than Transformers. Throughout this section, focus bidirectional RNNs, since the gSTR model is not necessarily causal and the output at position may depend on future tokens.
4.1 RNNs can learn simple-gSTR
A bidirectional RNN maintains, for each position in the sequence, forward and reverse hidden state, denoted by ( and ) where h h E Rds, These hidden states are obtained by initializing h hy Od,, and recursively applying
h = r,,, (h,-1 + f 24
(2, N)
Z441; b = 1k, (h + fh 0+11 E (l...,,, N-1,
where II,, Rdh + Rd is the projection II,, = (1 A An/ / and fn and fr are implemented by feedforward networks, parameterized by O and @ respectively. Recall 2, (x:², enc(i, T)) is the encoding of æ;. We remark that while add 1I, for techni- cal reasons, it resembles layer normalization which ensures stability of the state transitions on very long inputs; more involved analysis can replace II,, with standard formulations of layer normal- ization. Additionally, directly adding h and h to the output transition functions represents residual or skip connections. The output position i is generated by
Y/ fu( h 21: Oy),
which is an Ly -lyer feedforward network. Specifically, we consider an RNN with deep transitions [PGCB13] and let f% (-; ,,,") ) be L, -layer feedforward network (see Appendix B.1 for complete definitions). We denote the complete output of the RNN via
Rnw (p: 6 RxR) (hy hT: 21; Og), ey),...,, fy hw nN: O,)) R.
We have the following guarantee for RNNs learning simple-g -ST models.
Theorem 5. Let Ô = arg min RANN ()) (with Orm defined in Equation (B.2)). Suppose As-
sumptions 1, 2 and 3 hold with the SMmple-gSTRRR model, i.e. t, = for all i E [N] and some t drawn from [N]9. Then, with Ln, Tyy (1), Th @(vgd), and proper hyperparameters in Oex (see Appendix B. I), we obtain
poly(d, q, mgg Pas Two Eznk: log(n.))
RAMX ( S Ezsu
n
with probability at least 1 - = for some absolute constant 0.
As desired, the above sample complexity depends N only up to polylogarithmic factors. The dimension and norm of RNN weights, implicit in the formulation above, must have a similar polynomial scaling evident by the proof of the above theorem in Appendix B.
4.2 RNNs cannot learn general 4STR
For our lower bound, we will consider a broad class of recurrent networks, without restricting to specific form of parametrization. Specifically, we consider bidirectional RNNs chracterized by
h projr, (J (h Di, t)) Vi (1,...,N' -
h = proj.. (fr 2.,
Vie (2....,N)
y4 SU -U-h;; h² U- t.,
Vi [N]
where Sy. Rd Rdd x I& [N] + R. JR Rd x Rd x [N]0+1 - Rdd, U- E dd xd. d2 is the width of the model, and rı > 0 is some constant. Moreover, proj., 1Rd d
7

---

is any mapping that guarantees |proo,,, (+) S rye As mentioned before, this operation mirrors the layer normalization to ensure that h: remains stable. Further, we assume (y x., t) is 2/ri- -Lipschitz for all z E Id and & E [N] This formulation covers different variants of (bidirectional) RNNS used in practice such as LSTM and GRU, and includes the RNN formulation of Section 4.1 as a special case. Define U = (U", U²) Rd x2dh for conciseness. Note that in practice fy. Jh JK are determined by additional parameters. However, the only weight that we explicitly denote this formulation is U, since our lower bound will directly involve this projection, and we keep the rest of the parameters implicit for our representational lower bound.
Our technique for proving the RNN lower bound differs significantly from that of FFNs. In particular, we will control the representation cost of the gSTR model, i.e., lower bound on the norm of O REKK
We will now present the RNN lower bound, with its proof deferred to Appendix B.5. Proposition 6. Consider the 1STR model where
(O, INa) with a linear link function, i.e. y (u, σz2) for some Sd-1. 1. Fuurther, t; is drawn independently from the rest of the prompt and uniformly from [N] for all i E [N]. Then, there exists an absolute constant >> 0, such that
1 E lly 2m (p)l² Sc.
implies
( dn 2 log(1 + -
N
and | 2 log(1 + dr.)
N
Remark. Note that the unboundedness of Gaussian random variables is not issue for approxi- mation here, since (g(x)) ..... ((xx)) is highly concentrated around (N-IVN), In fact, one can directly assume (g(x1), ..... ........(22)))) x)) Unif(S-V-1(/)) (vNN) and derive a similar lower bound. The choice of Gaussian above is only made to simplify the presentation of the proof.
The above proposition has two implications. First, it has computational consequence, implying that any RNN representing the şSTR models requires a width that grows at least linearly with the context-length N. A similar lower bound in terms of bit complexity was derived in [SHT23] using different tools. More importantly, the norm lower bound ||U|| ((vN) has generalization consequence, which we discuss below.
To translate the above representational cost result to a sample complexity lower bound, we now introduce the parametrization of the output function fy. The exact parametrization of the transition functions will be unimportant, and we will use the notation fr." (h, t; Ox,) to denote a general parameterized function (similarly with f*) We will assume fy given by a feedforward network,
h- x,t; Q2) W W., (...o(...ooo (W2o + W = + b,,) + b2)...),
where h ,h" hh) E Rdd,, encoding function with arbitrary dimension dz. Then O, = (U.W,,
(x; fr(t,, i)) E Rd+dE, Here, fE(ti, i) is arbitrary W y, by, W2, b2...., I,,). and RrR4 OU O O Note that thanks to the homogeneity of ReLU, we can always reparameterize the network by taking h h h/Tr. W,, = W /r/ by by/rn. and W₂ = W2/Te Tr without changing the prediction function. Thus, in the following, we take TA = 1 without losing the expressive power of the network. We then have the following sample complexity lower bound.
Theorem 7. Consider the 1STR model of Proposition 6. Suppose the size of the hidden state, the depth of the prediction function, and the weight norm respectively satisfy d, S e 2 S Ly S C. and || ( @wxx))] 2 S No for some absolute constants e < 1 and C 2 2, and recall we set Th = due to homogeneity of the network. Let O be the min-norm E-ERM of RAXX defined in (2.4). Then, there exist absolute constants C1, C2, C3 > such that if n S O for any E 2 O. with probability at least C2 over the training set,
E
VRAu (p: θn.e)
y/ 0112] 2 C3.
Remark. is possible to remove the subexponential bound on (rec(Om)))] by allowing the learner to search over families of RNNs with arbitrary d, S e rather than fixing a single d,, Additionally, one would avoid solutions that violate this norm constraint in practice due to numerical instability.
8

---

To prove the above theorem, we use the fact that an RNN that generalizes on the entire data distribution (hence approximates the 1STR model) requires a weight norm that scales with vN, while overfitting on the n samples in the training set with zero empirical risk possible with a poly(n) weight norm. As result, as long n Σ No for some small constant > O. min-norm & c-ERM will choose models that overfit rather than generalize. A similar approach was taken [POW*24 24] to prove sample complexity separations between two and three-layer feedforward networks. The complete proof is presented Appendix B.6.
Feedforward Neural Networks (FFNs)
In this section, we consider general formulation of feedforward network. Our only requirement will be that the first layer performs fully-connected projection. The subsequent layers of the network can be arbitrarily implemented, c.g. using attention blocks or convolution filters. Specifically, the FFN implements the mapping p + fT, W x) where W " x. is the weight matrix in the first layer, æ = (x) ..... N E R and f [N]ON x T - IR implements the rest of the network. Unlike the Transformer architecture, here we give the network full information of T = (4,,..., (N), and in particular the network can implement arbitrary encodings of the position variables tı ......, LN- This formulation covers usual approaches where encodings of t are added to or concatenated with æ.
For our negative result on feedforward networks, we can further restrict the class of qSTR models, and only look at simple-gSTR where R, of (2.3) and RN of (2.2) will be equivalent. Additionally, the lower bound of this section holds regardless of the loss function used for training, for some arbitrary loss & R R - I. we define the empirical risk of the FFN
CFFR W)
Au O Wa))),)
nN
where ( covers a broad set of algorithms, characterized by the following definition.
(1(1)
We still use 1E (J, W) for expected squared loss. Our lower bound
Definition 8. Let Asp denote the set of algorithms that return a stationary point of the regularized empirical risk. Specifically, for every A E Asp, A(S,) returns JA(S.). W A(S)), such that
W 2 (JA(Su)) LWFFEK(AAASSS W WA(S.)) XW A(S.) =0,
for some X > O depending A. S. above denotes the training set. Let AERM denote the set of algorithms that return the min-norm approximate ERM. Specifically, every AERM returns
A(S.)
arg min (WW
for some E 2 O. Define A = Asp U AERM-
In particular, A goes beyond constrained ERM in that also includes the (ideal) output of first-order optimization algorithms with weight decay, or ERM with additional Eg penalty on the weights. The following minimax lower bound shows that all algorithms in class fail to learn even the subset of simple-gSTR models with sample complexity sublinear in N.
(0, INa), and consider the simple- 1STR model with tu = t1 for all E [N]. where is drawn independently and uniformly in [N), and linear link function, i.e. y (u, x.,) )) for some u E sd-11 Let A be the class of algorithms in Definition 8. Then,
Theorem 9. Suppose
inf sup AEA uegd-1
RFF W A(S.)) 21 Nd'
with probability over the training set S..
The above lower bound implies that learning the simple 1STR model with FFNs requires at least Nd samples. Note that here we do not have any assumption mi, i.e. the network can have infinite width. This a crucial difference with the lower bounds in [SHT23, WWHI124] which are computational, i.c., similar model cannot be learned unless my Nd.
Remark.

---

The main intuition is that from the stationarity property of Definition 8, the rows of the trained W will always be in the span of the training data (+)) for E [n]. This is an n-dimensional subspace, and the best predictor that only depends on this subspace still has loss determined by the variance of y conditioned on this subspace. By randomizing the target direction u. the label can depend on all N d target directions. As result, as long as n < Nd, this variance will be bounded away from zero, leading to the failure of FFNs, even with infinite compute/width. See Appendix D for detailed proof.
6 Conclusion
In this paper, we established a sample complexity separation between Transformers and baseline architectures, namely feedforward and recurrent networks, for learning Soquence-t--sqqueee models where the output at each position depends on sparse subset of input tokens described in the input itself, coined the gSTR model. We proved that Transformers complexity almost independent of the length of the input sequence N, while feedforward and recurrent networks have sample complexity lower bounds N and N2((), respectively. Further, we established separation between FFNs and RNNs by proving that recurrent networks can learn the subset of simple-gSTR models where the output at all positions is identical, whereas feedforward networks require least N samples. An important direction for future work is develop understanding of the optimization dynamics of Transformers to learn 4SRR models, and to study sample complexity separations that highlight the role of depth in Transformers.
learn such model with sample
Acknowledgments and Disclosure of Funding
The authors thank Alberto Bietti and Song Mei for useful discussions. MAE was partially supported by the NSERC Grant [2019-06167], the CIFAR AI Chairs program, the CIFAR Catalyst grant, and the Ontario Early Researcher Award.
References
[AAM23] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz, Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics, The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 2552-2623.
[ACDS23] Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra, Transformers learn to implement preconditioned gradient descent for in-context learning, Advances in Neural Information Processing Systems 37 (2023), 45614-45650.
[ASA+23) Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou, What learning algorithum is in-context learning? investigations with linear models, The Eleventh International Conference on Learning Representations, 2023.
[AWA+22) +22] Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur, Explor- ing length generalization in large language models, Advances in Neural Information Processing Systems 35 (2022), 38546-38556.
[AYB24] Noah Amsel, Gilad Ychudai, and Joan Bruna, On the benefits of rank in attention layers, arXiv preprint urXiv:2407.16155 (2024).
[Bac 17] Francis Bach, Breaking the curse of dimensionality with convex neural networks, Journal Machine Learning Research 18 (2017). no. 19, 1-53.
[BAG20] S. Bhattamishra, Kabir Ahuja, and Navin Goyal, On the ability and limitations of transformers to recognize formal languages, Conference Empirical Methods in Natural Language Processing, 2020.
[BBSS22] Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song, Learning single-index models with shallow neural networks, Advances in Neural Information Processing Systems, 2022.
10

---

[BCW+23] Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei, Transformers as statis- ticians: Provable in-context learning with in-context algorithm selection, Advances in neural information processing systems 36 (2023).
[BES+22] Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Reprexentation, arXiv preprint wrXiv:2205.014:: (2022).
[FT17]] Peter L Bartlett, Dylan Foster, and Matus J Telgarsky, Spectrilly-oormalizedd margin bounds for neural networks, Advances in neural information processing systems 30 (2017).
[BHBK24] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade, Separations in the representational capabilittes of transformers and recurrent architectures, 2024.
[BRR + 20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al., Language models are few-shol learners, Advances in neural information processing systems 33 (2020), 1877-1901.
[CB20] Lenaic Chizat and Francis Bach, Implicit bias of grudient descent for wide two-layer neural networks trained with the logistic loss, 2020.
[CLZ20] Minshuo Chen, Xingguo Li, and Tuo Zhao, On generalization bounds of a family of recurrent neural networks, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 108, PMLR, 2020, pp. 1233-1243.
[CS24] Sourav Chatterjee and Timothy Sudijono, Neural networks generalize low complex- ity data, ArXiv abs/2409.12444 (2024).
[DBK+20] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold. Syl- vain Gelly, et al., An image is worth 16x16 words: Transformers for image recognition at scale, arXiv preprint arXiv:2010.1 1999 (2020).
[DKL*23] Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan, Learning two-layer neural networks, one (giant) step at a time, arXiv preprint arXiv:2305.18270 (2023).
[DLS22] Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi, Neural Networks can Learn Representations with Gradient Descent, Conference on Learning Theory, 2022.
[EGKZ22] Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang, Inductive bi- ases and variable creation in self-attention mechanisms, International Conference on Machine Learning, PMLR, 2022, pp. 5793-5831.
[FGBM23] Hengyu Fu, Tianyu Guo, Yu Bai, and Song Mei, What can single attention layer learn? a study through the random features lens, Advances in Neural Information Processing Systems 36 (2023).
[FZG Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang, Towards revealing the mystery behind chain of thought: theoretical perspective, Advances in Neural Information Processing Systems 36 (2023).
[GRRB24] Borjan Geshkovski, Philippe Rigollet, and Domènec Ruiz-Balet, Measure-to-measure interpolation using transformers, arXiv preprint S0.iv:2411.00555 (2024).
[Hah20] Michael Hahn, Theoretical limitations of self-attention in neural sequence models, Transactions of the Association for Computational Linguistics 8 (2020), 156-171.
[HSSL224] Shwai He, Guoheng Sun, Zheyu Shen, and Ang Li, What matters transformers? not all attention is needed, 2024.
11

---

[JBKM24] Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach, Repeat after me: Transformers are better than state space models at copying. ArXiv abs/2402.010332 (2024).
[JMB+24] Samy Jelassi, Clara Mohri, David Brandfonbrener, Alex Gu, Nikhil Vyas, Nikhil Anand, David Alvarez-Melis, Yuanzhi Li, Sham M. Kakade, and Eran Malach, Mixture of parrots: Experts improve memorization more than reasoning. 2024.
[KS224] Juno Kim, Tai Nakamaki, and Taiji Suzuki, Transformers are minimax optimal non- parametric in-context learners, ICML 2024 Workshop In-Context Learning, 2024.
[KS24] Juno Kim and Taiji Suzuki, Transformers provably solve parity efficiently with chain of thought, arviv preprint arXiv:2410.08633 (2024).
[LAG+23] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang, Exposing attention glitches with flip language modeling, 2023.
[LCW21] Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller, On the expressive power of self-attention matrices, ArXiv abs/2106.03764 (2021).
[LIPO23] Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oy- mak, Transformers as algorithms: Generalization and stability in in-context learning, International Conference on Machine Learning, PMLR, 2023, pp. 19565-19594.
[LLZM24) Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma, Chain of thought empowers transformers to solve inherently serial problems, The Twelfth International Conference on Learning Representations, 2024.
[LMZI8] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang, Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic activations, Confer- ence On Learning Theory, PMLR, 2018, pp. 2-47.
[MHPG 23] Alireza Mousavi-Hosseini, Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu, Neural networks efficiently learn cow-dimensional representations with sgd, The Eleventh International Conference on Learning Representations, 2023.
[MHWE24] Alireza Hissei,, Denny Wu, and Murat A Erdogdu, Learning multi- index models with neural networks via mean-field langevin dynamics, arXiv preprint arXiv:2408. 007254 (2024).
[MLT24] Sadegh Mahdavi, Renjie Liao, and Christos Thrampoulidis, Memorization capacity of multi-head attention in transformers, The Twelfth International Conference on Learning Representations, 2024.
[MS23] William Merrill and Ashish Sabharwal, The expressive power of transformers with chain of thought, 2023.
[MS24]
The expressive power of transformers with chain of thought, The Twelfth International Conference on Learning Representations, 2024.
[NLB+ 18] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro, Towards understanding the role of over-parametrization in generalization of neural networks, arXiv preprint at arvi: 1005.880.1100 12076 (2018).
[OSSW24] Kazusato Oko, Yujin Song, Taiji Suzuki, and Denny Wu, Pretrained trans- former efficiently learns low-dimensional target functions in-context, arXiv preprint mrXiv:241..025. (2024).
[OWSS19] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro, A function space view of bounded norm infinite width relu nets: The multivariate case, 2019.
[PGCB13] Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio, How to construct deep recurrent neural networks, arXiv preprint arXiv: 1tt.::131..6000 12. (2013).
12

---

[POW [24 Suzanna Parkinson, Greg Ongie, Rebecca Willett, Ohad Shamir, and Nathan Srebro, Depth separation in norm-bounded infinite- width neural networks, The Thirty Seventh Annual Conference on Learning Theory, PMLR, 2024, pp. 4082-4114.
[RNSS18] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever, Improving language understanding by generative pre-training, OpenAl Blog (2018).
[SHT23] Clayton Sanford, Daniel Hsu, and Matus Telgarsky, Representational strengths and limitations of transformers, Advances in Neural Information Processing Systems 36 (2023).
[SHT24] Clayton Sanford, Daniel Hsu, and Matus Telgarsky, Transformers, parallel compu- tation, and logarithmic depth, Proceedings of the 41st International Conference on Machine Learning, 2024.
[Tru24] Lan Truong, On rank-dependent generalisation error bounds for transformers, arXiv preprint arXiv:2410. 11500 (2024).
[TT2]] Jacob Trauger and Ambuj Tewari, Sequence length independent norm-based general- ization bounds for transformers, 2023.
[VDT24] Bhavya Vasudeva, Puneesh Deora, and Christos Thrampoulidis, Implicit bias and fast convergence rates for self-attention, ArXiv abs/2402.05738 (202)))
[VONR + 23] Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexan- der Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov, Transformers learn in-context by gradient descent, International Conference on Machine Learning, PMLR, 2023, pp. 35151-35174.
[VOT+24] 24] Kiran Vodrahalli, Santiago Ontanon, Nilesh Tripurameni, Kelvin Xu, Sanil Jain, Rakesh Shivanna, Jeffrey Hui, Nishanth Dikkala, Mehran Kazemi, Bahare Fatemi, Rohan Anil, Ethan Dyer, Siamak Shakeri, Roopali Vij, Harsh Mehta, Vinay Ramasesh, Quoc Le, Ed Chi, Yifeng Lu, Orhan Firat, Angeliki Lazaridou, Jean-Baptiste Lespiau, Nithya Attaluri, and Kate Olszewska, Michelangelo: Long context evaluations beyond haystacks via latent structure queries, 2024.
[VSP+ 17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin, Attention all you need, Advances in Neural Information Processing Systems, vol. 30, 2017.
[WCM21] Colin Wei, Yining Chen, and Tengyu Ma, Statistically meaningful approximation: case study on approximating turing machines with transformers, 2021.
[WDL24] Kaiyue Wen, Xingyu Dang, and Kaifeng Lyu, Rnns are not transformers (yet): The key bottleneck on in-context retrieval, 2024.
[WLLM19] Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma, Regularization malters: General- ization and optimization of neural nets vs their induced kernel, Advances in Neural Information Processing Systems 32 (2019).
[WWHL24] Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason D. Lee, Transformers provably learn sparse token selection while fully-connected nets cannot, Proceedings the 41st International Conference on Machine Learning, 2024.
[YBR+19] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar, Are transformers universal approximators of sequence-to to-peeeee-----sueceeeeee functions? 2019.
[YCA23] Andy Yang, David Chiang, and Dana Angluin, Masked hard-attention transformers recognize exactly the star-free languages, 2023.
[ZBL+23] Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran, What algorithms can transformers learn? sludy in length generalization, ArXiv abs/2310.16600 (2023).
[FFB24] Ruiqi Zhang, Spencer Frei, and Peter I. Bartlett, Trained transformers learn linear models in-context, Journal of Machine Learning Research 25 (2024), no. 49, 1-55.
13

---

A Details of Section
Here present the omitted details and proofs of Section 3. We begin by presenting the architectural details before proving sample complexity upper bounds for Transformers.
A.1 Transformer Architectural Definition
We formally introduce the single-layer H-headed Transformer that appears in all Section proofs.
Positional encoding. To break the permutation equivaraince of Transformers, we append positional information the input tokens. Given prompt p. we consider an encoding given by
I1 (p) = enc(1,tt)
NN enc(N,
E R.D.
where enc [N] [N] + Rd provides the encoding of the position and of 6, and Dr == d denc- We use 2; to refer to the ith column above. We remark that allowing enc to take L, as input allows specific encodings of the indices 1 that take advantage the 4STR structure; examples of this have been considered in prior works [WWHL24]. In practice, we expect such useful encodings to be learned automatically by previous layers in the Transformer. We remark that for a fair comparison, in our lower bounds for other architectures we allow arbitrary processing of t; in their encoding procedure. To specify enc, we use a set vectors {w
N in RR that satisfy the following property.
Assumption 3. We have (w,,, اامس S 1/2 for all i + j. and || = ffr all i, with de = (log N).
Such set of vectors can be obtained e.g., by sampling random Rademacher vectors from the unit cube (+1/Vd.) which will satisfy the assumption with high probability. We define
enc(i, f4) v d/g(ww:, Wt....., Wt.g) (R(+1)dd
hence denc (q + 1)de and D. = d + (q 1)dg. The dd/q prefactor ensures that æ; and enc f.) will roughly have the same l norm, resulting in a balanced input to the attention layer.
Multi-head attention. Given a sequence { where 2, E R: with D2 as the embedding dimension, a single head of attention outputs another sequence of length N in RP,,, given by
e WWoz. Wxx,)
facta (p: W Q WK. Wv)=
Σ W Wzzz
SE[N]
Where W K. Wo. Wv the key, query, and value projection matrices respectively. We can sim- plify the presentation by replacing W @ Wxx к with a single parameterizing matrix for query-key pro- jections denoted by W QK E D. and absorbing Wv into the weights of the feedforward layer. This provides with a simplified parameterization of attention, which we denote by fausa (p: W QK). This simplification is standard in theoretical works (see e.g. [LIPO23, ACDS23, ZFB24, WWHL24J). Our main separation results still apply when maintaining separate trainable projections.
We can concatenate the output of H attention heads with separate key-query projection matrices to obtain a multi-head attention layer with H heads. We denote the output of head h E [H] with fatta (p: w QK)- The output of the multi-heat attention at position is then given by
(H) JAtta (p; ((I)
QK QK...... W w(()) (frera(p: w(lk)........)..))))) faura(p: (p: W OK )T) R.D.
We will denote by OQK (W (1)
QK Q...... w((h)) the parameters of the multi- head attention.
Finally, a two-layer neural network acts on the output of the attention to generate labels. Given input h E R.D., the output of the network is given by
fam (h; azmx, W 2xx, b2ι)) o W 2 + bamb
where W 2n E pm are the first layer weights, dREN. a2ex E R are the second layer weights and biases, and m the width. We also use the summarized notation O (azun W 2un baxx) to refer to the feedforward layer weights. The prediction of the transformer at position is given by
(p: TR); = fzmm( (f( (p; θok),; 2zm),
where 1 (OQK: 22m) denotes the overall trainable parameters of the Transformer. We use the notation VTa @Ta) (9ta (p: @I))....., (p: TT))) N to denote the vectorized output.
14

---

A.2 Proof of Theorem 3
To prove Theorem 3, we will prove the more general theorem below.
Theorem 10. Ler = arg men RTR ()), where
Tm = |1a2mxl1 I ra/ vm, ( 28n: banx) | S Tw Tw
w QK
S a vh E [m]]
Suppose H = 9. = My. and ((1) (given in Lemma 11). Then, under Assumptions 1, 2 and 3, with probability at least 1 for some absolute constant
we have
()) 0(5NN) + + + +0(cv/ (mog(d + 9) + r2rar A q(p2 + dd)))
(A.1)
where C .
begin with lemma establishing the capability of Transformerrs approximating gSTR models.
Lemma 11. Suppose Assumption 2 holds. Let Ya V3C,edlog(NV), Assume and mg m. Then, there exists Tm such that
sup (Ie:ll,
ga Dt..) Dpa(p: Ora)il S 2
and
||a2uel|2 <
Ta Vm
(I( 200, bamn) )lp S Vmnw
(1k QK
S
2de
log
d
for all h E [H).
Proof. In our construction, the goal of attention head h at position will be to output St... Namely, we want achieve
Sacta(p; wilkk; as Zt..-
Note that to do so, for each key token Zj. only need to compute (Wir wj)- Therefore, most entries in wr(h)) QK can be zero. We only require a block of de x de, which corresponds to comparing w and Wt,,. when comparing query 2; and key Zj. Thus, we let
Od4thd))xd Odex (g--b)de xd
(dthhd))xd ald. Mlg-
0 )xd Odexqde (g- xqd.
(h( QK
(A.2)
Then, have 2; with) 2x22)
alwia wijdd/ We then verify that
Af (p; w!!)) oK) Azua
add((2)) (1|A2]1 + ll2)),
jift
for every matrix A. We will specifically choose to the projection onto the first d coordinates in the following. Hence, will control the emror in the softmax attention approximating a "hard-max" attention that would exactly choose Zt,..
To construct the weights of the feedforward layer azam W 2mn bass, we let azms ag and baxx by from Assumption 2, and define W 2mn by extending W. with zero entries such that
Zta
Ftas
W
23H1
=
W
Zt.
Then [[ ||p Notice that + T (W(()) + b) is rarn Lipschitz. As a result, for any with ||e||| S Tx. we have
gg( Dt.,)) ON @Ta)s| < /Ezun + Cattn:
15

---

where we recall
[g( ................................ Dtia)
Sanx ((Zt ... Recg); agux W 200, D2nx)
and
faxml (Z Ztcn); (2xx - faNu (Fheta (p; OQk) 2xx))
Exten
Afucta (p; wolke Aztin
S TaTw w
< 2 Vqe-oa/12))
where we recall Azj = By. Thus, with
a = ( (2raT /2/ /E2x)//
we can guarantee the distance at most 2 /e2un
Before proceeding obtain statistical guarantees, will show that we can consider the encodings (+) to be bounded with high probability. This will be a useful event to consider throughout the proofs of various sections.
Lemma 12. Suppose {p are input prompts (not necessarily independent) drawn from the (1000))
input distribution, with tokens denoted by {(ac]) ))=))== Under Assumplion 1, for any Vs. > 0 we have
IP
max iEIN]JE[N]
a3 2 Txx
(6)
2Tx)
S CNNe-rr (2/(Cee/
In particular, for Tx (3Czedlog(nN)) have
max ie i
rr
nN
Proof. Via Markov's inequality, for any p > 0 and rz
>
0, we have
(6)
P
(1)
IP
E
max
E
Nn Nn(Capd)p/2
max 4,
2
2
Tx
12
r2
P
Let (C.... Then,
S (
max (
x
2 To
which proves the first statement, and the second statement follows by plugging in the specific value r..
We are now ready to move to the generalization analysis of Transformers. First, we have to formally define the prediction function class of Transformers with notation suitable for this section. We begin by defining the function class of attention. We have
FAtth {p.j (H) (p: OQk), Oqk Oqkt,
where we will later specify θдK. Additionally, we define Fexu by
Faux (h + faam O Q2mn) Ozxx E 0zmn); )
where 2mm (a224, W 2am, bax).. and we will later specify Ozm. Then the class FrD can be defined as
F. {p.j fax (xxx(fact(())) (p),) SActa FAven fanm F }.
16

---

Recall we use the Sn to denote the training set. To avoid extra indices, we will use the notation P.j E Sn to go over {p(o) ;(0 We can then define the following distances on the introduced function classes
(J: supls(p); ('())bb VS,J FTR PJ (f. = suplif(p); - (2))) Vf. FAtta p.j
pes (J,S)
I5() - -(() VS. E FaNx. sup
We choose the radius Hr2 for defining de since on the event of Lemma 12, this will be the norm bound on the output the attention layer at every position.
Recall that for distance do and a F, an e-covering f is set such that for every f E F, there exists f f such that doc (J: f) S e. The e-covering number of F. denoted by C(F, do,, <), the number of elements the smallest such F. The following lemma relates the covering number Fra to those of Fetta and F2Ex.
Lemma 13. Suppose faux is L, Lipschitz for every fauu E Fzm-- Then, for any < Ctten 0, on the event of Lemma 12 we have
log C(Fr, dae Ezun + (ECttt)) S log C( d Ezmn) log (( dasta Catta))
Proof. The proof simply follows from the triangle inequality, namely
sup fre(P: OnR) fra(p: 0ra)s pj
f2m ONN) f2an(tu @NNi
sup |
S (p: OQk), 1 Ook)s
+ Lg sup P.j
We have the following estimate for the covering number of Fzm..
Lemma 14. Suppose ||vc (n 2l S R and
|²
s foror all E [n] and j [N]. Then,
log (F deN é) S M. log(1 pol
This is special case Lemma 30, proved in Appendix B. For the next step, define the distance
K + QK. Okk sup p.j
O 0k - eT Qk2
on Ook, where we recall OQk ( Q....., w the covering number of the multi-head attention layer the matrix covering number of the class of attention parameters.
DD.xHD, The following lemma relates
Qk
Lemma 15. Suppose
|
< for all E [n] and j [N]. Then,
log C(FAtta Mata ,e) < log (ok, d OK 2n
17

---

Proof. We recall that Z R Nx D. denotes the encoded prompt, and softmax is applied row-wise.
For conciseness, Let A supp. / (p: @ak), -hhtt (p: @ok)) ||² Then we have
A
sup P.jESn kE|H)
Σ
Shcta (p: w ok)s fatta(pi W (8) ok))
sup p.jESm hE(m)
Σ
softmax (z)
Wllk (A)
QK
Z )
softmax (z) W QK Z ) 2
Σ
softmax(2]]
W (A) Qk
Z TT softmax(2)
wi(h) QK 2 T )T| I1
sup P.jESa
2,00
kE(M]
where we used Lemma for the last inequality. Moreover, by [EGKZ22, Corollary A.7].
softmax (z, W (b) QK Z -T=²=
(h) softmax (z,) W
QK 2
|| s Zw
(h)
QK zw (h)
QK
- 2 Z
(hh)
QKZj - 1
QK2j
2,00
Consequently,
2
A S 4r sup p.jSS
Σ
((()) QK
W
(N)
2j
QK
2j
NE(H
4r sup P.jES
1 @QkZ
2 T
Qk 2j
which completes the proof.
Further, we have the following covering number estimate for OoK.
Lemma 16. Suppose Ook (Kl02ll,,, S R2,1, ||Q I RF} and
x.00 2
S T2 for all
i [n] and j e [N]. Then.
R2 log(2HD?)
2Rrrz)
log C(OQ 22K e) S min
HDD log (1+
2
Proof. The first estimate comes from Maurey's 's sparsification lemma [BFT17, Lemma 3.2), while the second estimate is based on the inequality
Qkk
/|1 < rz 00 O F²
and covering Ook with the Frobenius norm, see e.g. Lemma 41.
Finally, we obtain the following covering number for Fra- Proposition 17. Suppose || ll I Tmma
[I( 2nx, baun) Ilr < Rm and |w
(h) Qk
S roK
for all E [H]. Further assume | 2 max(rm,,y T2). Then, log C(Fra, e) Smg HD, log(1 R/c)
< rz for all i E [n]] and j E [N]. Let R =
min 2 m. 12 log HD)
R2
HDd log (1 v HHrqrrs Fr
Proof. The proof follows from a number of observations. First, given the parameterization in the statement of the proposition, we have L, Fm..Rmm, in Lemma 13. Moreover, we have
18

---

R S. Hrok and R₂ I Hrok in Lemma 16. The rest follows from combining the statements of the previous lemmas.
Next, we will use the covering number bound to provide bound for Rademacher complexity. Recall that for a class loss functions L, the empirical and population Rademacher complexities are defined
Rh = E sup E
1
El(p!))
, 200))10))) (C( = (pp. Rn (c)
i=1
respectively, where (5:) are i.i.d. Rademacher random variables. Let the class of loss functions be defined by
C, = (p, (fra(p); y A fI E FIR),
(A.3)
for some constant > 0 to be fixed later. We then have the following bound on Rademacher complexity.
(0) Lemma 18. Suppose maX
S T.z For the loss class Cy given by (A.3), we have
Ci + (C2ACa)
(C,) 5
TV
n
where C1 = mi C2 = r m, Rm H2 and C3 HD?
Proof. Let C(t, E) denote the e-covering number of L, where ((p.y.)) (f(p); - wj)² AT and (p, (p)) v;)²
Then, for any a 2 by standard chaining argument,
Ri (c+) 2 a+ /-"
log C(C, d c)
de.
log C(F dIR d.. (2(T))
5at
Sat l/"
Ci (og((RV)))) de
TC (2) ne²
C3 log 1 C4 CIVF/E)
de
de
n
n
7C log( (og(o
TC log( D2)
7a + CaVT/a)
2 aa+1
log
n
n
where (c are given in the statement of the lemma and C4 = v Hrrorr2 Fm Rom,o- no Choosing 1/vn completes the proof.
Using standard symmetrization techniques, the above immediately yields high probability upper bound for the expected truncated loss of any estimator in OTa.
Corollary 19. Let Ô = arg min R ( where Ora is described in Proposition 17. Define T2 VT2 + d(1 + 1/4) where Ta is defined in Lemma 12. Let C1 Cz and C3 be defined in Lemma 18. Then, with probability least 1 (nN)- 1/2 11/2 over Sm, we have
PIB - < 3
(C C2
log(1/5)
(T)(() )
TV
+ +0
where RREN ④ = Ep (WTa(p) θ) v,) AT
Proof. The proof is standard consequence of Rademacher- generalization bounds, with the additional observation that
(1;
) AT S R. ())
n
19

---

The last step in the proof of the generalization bound is to bound (T)(O) with (,). This is achieved by the following lemma.
Lemma 20. Define 6² = Hr m, R R Then, under Assumption for T x x² log(x vn) 2.
log(k² vn)", we have
RT)(() - -,,(())) S V
Proof. For conciseness, define Ay
Upa(p: θ) yg
By the Cuachy-Schwarr inequality,
have
1 1[4 A v E [A > Vi]
S (
د (44 ス VT) 1/2
Moreover,
E [ 1/2 1 2 [ 1/2 +2 12p 1/2
By Assumption 1, we have E [v3]] 1/2 2 Additionally, note that
u(p θ), I ammml 112( (vHH) H W
max 21112 + ||6 (E(N]
H Hr mrmma u (1
max
[E[N]
To bound max]e[M]]l Specifically, for all
21122- we use the subGaussianity of ||ærlla characterized in Assumption 1.
1/r
E
max tE
2
E
max [E(N]
E
ara
l1
4r
1/r
N/ |021|1
11
3 N dd.
$ (odl)g(NN)3
where the last inequality follows from choosing log N. As a result,
M Up: [p: 6);}
S
Hr m.a
R² R, log(N)² = x² log(N)²
We now turn to bounding the probability. We have
VT) 2
VT ((D:
P(A, VF) < IP [151
+P
S sexp (52())))))))
Nexp (-5(
Hr ma, R2 2
where the second inequality follows from Weibull concentration bounds for y and Lemma 12. Choosing (x² log N /n) + log( x2 /n)²) completes the proof.
Proof of Theorem 10.
The theorem follows immediately from the approximation guarantee of Lemma 11, the generalization bound of Corollary 19, and the truncation control of Lemma 20. L]
A.3 Details on Limitations of Transformers with Few Heads
While Proposition 4 is only meaningful in the setting of d = R(g), the following proposition provides an exact lower bound 2 q on the number of heads for all d, the expense of additional restrictions on the attention matrix.
20

---

Proposition 21. Consider the qSTR data model. Suppose d = and yi 1
Vi - - 1| 1)
Assume V2 ~ -N(0, o??) independently. such that o; = for i < N/2 and d; = 0 for 2 2/2. Further, assume the atlention weights between the data and positional encoding parts the lokens
( 0(g-1)ddxd
w(()
are fixed zero, i.e.
Wok-
QK
(k)
Odxig+1)de W
where w gaxd and w
xlltt)d are the attention parameters, for i E [ Then, there exists distribution over (ti)e(N) such that for any choice of Ora. we have
H
y (P 1R) 2
Note that in our approximation constructions for learning gSTR, we always fixed the attention weights between data and positional components to be zero, which is why we assume the same in Proposition 21.
Proof of Proposition 21. We will simply choose t; = =1,.... 9) deterministically for i 2 and draw t; from arbitrary distribution for i < N/2. Note that have
N
N
R (m
Σ
B[(u (pa(p: m.))
2
B[(u - 0ma(p) Om)),)
N
N
N/2
Let Φ RHD. > I denote the mapping by the feedforward layer. Fix some i 2 N/2. Note that (H) @b(AAct (p: QQk);)
(na(p; Ora):
(1)
(H) 01j 2j)
Z
ajj Ijj (21)
(H)
Kj
j=1
j=1
for some real-valued function o, where
(2. Qk<))
dif
ΣN (wh) Qk ok2,)
are the attention scores. Let A (8)
E R be the matrix such that A aij
(b)
Let æi.q
(I1,..., [.) R7, Then,
R (TTR)
E
V1
Dig (2))
N
i=N/2
N
1
E
Var
|| 21? (v(2
(A.4)
Nq
N=N/2
where (i) R #xq is matrix whose rows form orthonormal basis of span(a)
(1)
(
where o; (a (h) ..... 0ig ) E Rs (note that (i) may have fewer than H rows, we consider the worst-case for the lower bound which is having rows). The second inequality follows from the fact that 2, is independent of æi:g for / + 1, and the fact that best predictor of y (in Lg error)
given A 1i.g is E y/ (() x1:4
Next, thanks to the structural property of W (-(h) QK in the assumption of the proposition and the fact that I; = for i 2 N/2, oi does not depend on (mi)ee for all h E [H] i 2 N/2, and j E [g]. As result, (() is independent of T1:-- Therefore,
F1.g 110 xigg ~V((()) 1 v(i) V(()).
21

---

By Lemma 40, we have Var(I 1|² V x1:g) 2(g H), which combined with (A.4) completes the proof.
We now present the similarly structured proof of Proposition 4.
Proof of Proposition 4. The choice of distribution over (4:) is similar to the one presented above, i.e. we let 4, (1..... deterministically for 2 N. However, for i < Nt draw such that they are independent from æ. Once again, we use the fact that
(O TR 2 N
Σ
B[(u VIa(P: 1a))))
N/2
Recall 2, e )) Fix some 2 N/2, and define
(h)
(
(n) (hie.*)) my > eno(iit.) t.), (hice))
QK
enc(iiti).
where we use the notation
w (h..x) W(he,,) wheea
W whikate) (h,
(( QK
QK
for the query-key matrix of each head. Recall that x; given by
0 for i < N/2, thus the attention weights are
(h)
(K)
21=1
Recall from the proof of Proposition 21 that we denote the feedforward layer by 6 R HD. + R. With this notation, we have
(p: θTR);
2j
(H) Oij 2j)
j=1
(1)
ij Fン (ā /=1,j= (21)
(H) (b) A=H.jjN
j=1
J=1
Therefore, using the fact that z, and ijj are independent of æi:g for j 2 + 1, we have
(b)
27
N
TTh (TT((TT))))))))))))))))(())
E
y1
aij Lÿj (ā カ=1ي= (z (z:)
(H)
k=
i=
N/2
j=1
N
Σ
Var
||0110||| || ((a. (h.r) x11: ,,10)))))110))))))
h=1,-= (ā (h) |
Nqd
k= N/22
N
|| ||2|| ((a.t1 (hir) x1:g)) W ((w??) )m:1))
H.u
Var
Nqd
im N/2
N
E var ||
N ggd
Km N/2
where a; (h.r)
E Rod such that
(a
aig
if --=
if l i
which yields (a)h mm
Ej=1
Oij Tijrs and w (B)
(M)
E aR such that
w (he,a)) encli, (:)
(1((1)) )as
QK
i j if +
0
22

---

which yields [
(withww) enc(i, t.), Bz) Finally, V is a matrix whose rows A=H form an orthonormal basis of span (a. ) /=1,-=1 H (d + q) rows. Recall that
11:9/
(w
(h) (1)) h= h=
Namely, V has at most
1,3 h=1,==1)
Bigg
N(V(1))
V mi Ind v(1) V(o).
Once again, by Lemma 40, we conclude that var (| [1g""" ((() 2 2(qd H(g + d)), which completes the proof.
B Details and Proofs of Section 4
Before presenting the proofs, we state the omitted setup and parameterization of the network in the next section.
B.1 Complete Setup of RNNs
When introducing RNNs in Section 4, we used layyr deep feedforward networks implement the transitions fn. (,)) and f (r, ). These transitions are given by
ST (= - W Z, ( L. -.-1 ...... o.....WWWr W.. with O (WT, .........
... bZ, (B.1)
..... W L b W and similar equation for (1; Recall that the output of the RNN is denoted by
DRZu (p: RMM) = (Jy(hT AT 21; ; ,,), ...,, (h AN, NN; 0,,) E R.
We now define the constraint set of this architecture. Let
ORNX = @ ||vec( ( - R. WiWlill llop
WiTh llop ON,
W Wiwllop
op S oN f
(B.2)
where W contains the first d, columns of Wi' and the conditions above are introduced to ensure fr² and fx are at most Ly-Lipschitz with respect the hidden state input. One way meet this requirement to multiply With by a factor of oNx II [W7'l, llup in the forward pass. Without this Lipschitzness constraint, current techniques for proving uniform RNN generalization bounds will suffer from sample complexity linear in N, see e.g. [CLZ220].
For Theorem 5 we only require aN S N In particular, we can choose aN = 0 and fix W i.h W
O, which would simplify the parameterization of the network. Namely, in our construction f and f do not need to depend on h and h respectively.
B.2 Overview of the Proof of Theorem
The following is the roadmap will take for the proof of Section 4.1. The goal here is to implement a bi-directional RNN in such a way that
h x (1t, 1 141 < i)...., Dt, 1/g +)),
and
h RJ (z,, l[t > 8] Lzg 1it, > il).
Throughout this section, we will use the notation
(a 1) (a: 1[t 1) ..... 1t T
We can obtain the hidden states above through the following updates
h h + (æ;; Wt: w:),
and
h = h + ( We: w:).
where
( We, We, w.), x: (wo( wa,) - 8) x; [t: 1). v [gl
23

---

and a is ReLU. As a result, our network must approximate where we recall We (Wi,, ....... ,..,,,,,,,... Wt,),,
Sh (h," Bi, Wt wi; ²₂ Sh (h Bi we O), ~ ( w,, wi). A core challenge in this approximation is that if we simply control
I1 (h 2;; 0,,²) - (a;, We: will|2 s, this error will propoagte through the forward pass, and we will have
(B.3)
(ay.:w,ww)) Ne.
As result, would like implementation that satisfies the following
{ 44 4
1 (h," z;;
,2; Or: - (x We, wi)ella
(B.4)
t =
Note that
h = Σ th z; 07²)
Since for each / E [g]. t = j is possible for at most one E [N], (B.4) implies
h Σ V(z,,wr,
S VqE,
for all i E [N], hence, we can avoid dependence on N.
We can implmenet fT to satisfy (B.3) with a depth three network, where the first two layers imple- ments (wi, wr,) (as sum of Lipschitz 2-dimensional functions, example of their approximation is given by [Bac17, Proposition 6)), and the third performs coordinate-wist product between æ; and a a((w, W 1/2) (which for each coordinate a Lipschitz two-dimensional function). To ensure fn satisfies (B.4) 4),4), we can pass the outputs to fourth layer which rectifies its input near zero to be exactly zero using ReLU activations.
To generate yi from h," and h we first calculate
h; = fna(h, h Bi Wi: we)
= h + h + v/ (xx We wi)
2 (..,...., z.,))
Finally, Vi be generated from h; by applying the two-layer neural network from Assumption that approximates y; = g (xz)).
Note that the construction above has a complexity poly(d, g, log(n.V)) (both in terms of number and weight parameters), only depending on up to log factors. As a result, by simple parameter- counting approach, the sample complexity of regularized ERM would also be (almost) independent of N. We also simply use the encoding
2, = (.: Wi W
for the RNN positive result. The scaling difference with the encoding for Transofrmers is only made to simplify the exposition,
longer keep explicit dependence on d and
B.3 Approximations
As explained above, implement f/² first construct a depth three neural network (with two layers of non-linearity) which approximately performs the following mapping
h x
(Wi)ee))
2x00 Wi, - 1/2)
Wi
Wt.
+
(eol((s,, 1/2)
(wi, w(,) )
Wt./

---

The first mapping will be provided by
X1 A 1oo + b1),
where Xo (h x 1h.xx" wi. Wh, .., w7,) E Rdh-dt(otlddd W1 E R (0n b1 E
Rm,, and A R( with my the width of the first layer. We will use the notation
X1 (xf (x)
refer for the first d coordinates and the rest the q coordinates of Xı respectively, thus ideally Xi = a and (I) = (wi, Wa,) The second mapping is provided by
X2 A20 Waw 2X1 + b2),
where W2 2 Rm b2 R and A₂ E Rddxms, We will similarly use the notation
X2 (x. X2)))), where our goal is to have x2(1) = 220 wa) - 1/2). To implement the first mapping, we rely on the following lemma.
Lemma 22. Let be the ReLU activation. For any 0 and positive integer de, there exists m = (lg((d////)))) a IR",, W E RRmx2d, and E R such that
(w) - Ta TaT(no wh w.
sup
wi w2
+ +b)
Se.
and
||a||2 S o (lo((d,/))/)) /
W
S1
|b01 S 1.
Proof. Consider the mapping Cıj. E2j c1jo2j- Note that when leyyl 1 and [ezj] 1, this mapping 22-Lipschitz, and the output is bounded between [-1, Then, by Lemma 42, for every Ey 0, there exists mj ((11/E log log(1/z,))) a Rm W E m x2d. and by E " such that
agio ((w5r. [w) wT)T) + by)) E
sup
C2
1=1
1, and || < Specifically, the only non- zero coordinates of wzt are the jth and de + +ith coordinates.
||ارل < ((loo((/e,)/e))) /0/2 /mz).
||by|l
Construct a. b R" and W gmx2d. by concatenating (a,). (bz). ) and (W,) respectively. The resulting network satisfies
Let Ej e/d, and m = E my = (lg(dd
(w),w2) a W
wi SE,
+b)
sup Wi,Wg88
W2
while ||all2 S (lg(d |bb| S 1, and | proof.
1, completing the
1,00
I
We can now specify A,, W1, and by in our construction.
Lemma 23. For any 0, my = (log(d (de//)/=))) and m, 2d + qm,, Then, there exist
A₁ E R (d++))x., W1 R mm x (d. (d.=+((())))) and bj Rm, given by Equations (B.5) to (B.9), such that
(x) (w), S x =
for all Rdd,, x Idd wi (w,, )5e(a] E 1d. and E (q]. Furthermore, we have the following guarantees
0()),,
bb s0()),
A
1,00
1,00
Proof. We define the decompositions
Win W
bi b12
A11
W. =
b
Ai
(B.5)
12
A12
25

---

where W E (Rdx(( W 12
Ra (dy
b11 E _R2d b12 E RM,, A11 E Rdxms
and A E R Let pI.... a denote the standard basis of R and notice that - Therefore, we can implement the identity part of the mapping by letting
1
Odn
g l)d.
(a+ D).
W I1
(B.6)
Od
d
g lid
Od
d
(a+ 1jde/
as well as
1
0
0
q
0
0
1
-1
grit
bj = O2d,
and A1
(B.7)
9m
2. To implement the inner product part of the mapping, we take the construction of weights, biases, and second layer weights from Lemma 22, and rename them as W1 E mm x2d, bj E R and ă E RR Let introduce the decomposition W ( 11 W12). where W 11, W E R xd. With this decomposition, we can separate the projections applied to the first and second vectors in Lemma 22. We can then define
Notice that [ T
1 and A
11 1.00
0 (d)+((
W
W 12
Dmly xd.
O xd.
0 +(d
W
Om xd.
W 12
0 xd.
W
(B.8)
0 xida(da+)
WH
O
xd
Omly x
W 12
as well
b
0, 2d
a
m1
0g
0
mi
b
and
A12
(B.9)
0
mm
From Lemma 22, we have
W T
$ 1, b1 <
and
1,00
A
= =-aill s (1g(4/((00(44
1,00
which completes the proof.
To introduce the construction of the next layer, we rely on the following lemma which establishes the desired approximation for single coordinate, the proof of which is similar that of Lemma 22.
Lemma 24. Let be the ReLU activation. Suppose [h| S r |z| S r and |2| 1. Let
R = 1 rxx 2 + ph For any E > 0. there exists m = Ol a E R", W Rmx? and R, such that
sup h + 2ro 1/2) aa aTo(W((,,2,)) +b) <
and
||a||2 O(R
[WT]]
5 SR
|bbla S.
1,00
Additionally, i O, we have the improved bounds
(log(R\=)/=)3)) ||a||2 s
26

---

Proof. Note that (h, 2) H h + -2 is 2R-Lipschitz, and + 2x - 1/2) - R. The proof follows from Lemma 42 with dimension 3 when r * and dimension otherwise.
With that, we can now construct the weights for the second mapping in the network.
Lemma 25, Suppose lxx llo S Tz and maxi maxiix"((0 (1) I Let R = v1+ Then, for every E > O and absolute constant å E (0, 1), there exists mh S (log( (/))))))))) m2 == qdmı.
and A E Rddxm2, W2 E (d=x)(++)) and ba E mm given by Equations (B.10) and (B.11) such that
xxx(1)) - 2x 2x 1/2)1l S, for all such Xi and E [q]. where we recall X2 = A2o W 22x
2X1 + b2). Moreover we have
|
w S RR', ||62110c $
1,00
Proof. Let W (w22 w22), b, and à be the weights obtained from Lemma 24, where W22 ú222 b, R To construct We and b2, we let
W 12,
(2(1,
d2(1,d)
b2(1,d)
W₂
b22
(B.10)
12
b2(1,1)
d))
by (2)
where W 2l(1,) E ( is given by
W 21, (0 (0max(j-1)
U21
0 (d=x))
0 m2 (1-1) W22 0
and b2(1,) = b2. Consequently,
W
and
|b2l S 1. Finally, we have
1,00
a
m2
m2
ag
A
12g
m2
(B.11)
a
122
m2
Consequently, we obtain
S (lg((R/))//)))) completing the proof.
1,00
We ready provide the four-layer feedforward construction of f (h, t, Proposition 26. Let (x, wi; wt....... W.,). Then, for every E >> 0, there exists feedforward network with T, = 4 layers given by
1 (h, W L. (... W W Wh TT + bi)
b2) b2)...
where W. 1 b, R.T for E (2...., La - 1}. W, Rm xdwdddtddttlllddee E m
and W L, RRda that satisfies the following:
1. 1f4 = i, then
||
Se
2. Else (h, 2; 2h, - 0.5
for all I (g). h E Rd and | S rz. Additionally [ Alle S poly(rz, - for all [Lu] and m., 1bl122 I (oly(Ta, e for all i [Ln 1}. where recall D. d + (q + l)de.
27

---

Proof. Let A E x W1 E R bj E m be given by Lemma 23 with enror parameter é1 and A Rd W2 E (mmxx(+t)) error parameter E2. Recall that
be m be given by Lemma 25 with
X1 A (WlooWii) 1Xo + b1),
X2 X2= A20 -2 2X1 b2).
By the triangle incquality,
(x, t, A20 (Wo 2x1 + by)
(2x t, - A2o (W22: + +b2)
+
A20
W 2X1
+ b2)
-A20 (W 2X1 + b2) b2)ll_
Eea +
A
W
||x: - X11100
1,00
1,00
SEa
A₂
[
E1:
1,00
1,00
where X1 = (x= (Ww,, wi, ...., (w,, Wt,) T. By letting = E/4, we obtain
m22
A₂
W
by
$ poly(r2, De. E)
FF
F
Similarly, we can E1 = e/(4
A2
W
which yields
m1.
A1
W
b2
S poly(r2: Et.
F
F
Let
W₂ W2A1;
W WI,
bi =b;;
b2 b2-
Then,
X2 A W 20 W (h T x TTT + b1) + b2).
satisfies l|x; - V(z, t, i) I / for all | Tz.
Recall that when t # i for some E lg). we would like to guarantee the output of the network to be equal to (ar, t, i)) Og- do so, we rely on the fact that -> a - b) - a(-z - is zero for |=| S b, and has an T distance of b from the identity, i.e. 1z a(= - b) + f= b)l S b.
This mapping needs to be applied element-wise to X2. Let Wa E R2d, xdn bg E R2ds, and Wa 4 E Rd x 2ds via
U1
-1
0 0
0
0
E 12dn.
W3= 3 =
b3
WA =
0
0
1
-1
v
0
As result, X3 W WooWWaxe + bb) satisfies
S 1(x2)}1 5/22
1(xa); - (xx)x S E/2 1xx2);1 > E/22'
Vj E [dr).
(B.
We thus make two observations. Ilxa (1) (w, z, i) < g for all / E (q). Second, when l 4 i, we have Va t) 0, and (x2(1), < 8/2 for all j E [d] since lix² (a i)ello e/2.. Consequently, by the first case in (2) we have (I); = 0 for all j E [d]. We can summarize these two observations as follows
First, - S e/2, and consequently
00 t ti
(Iaa (x, t,
4 =-
which completes the proof.
With the above implementation of (h, 2; Or),, ), we have the following guarantee on h for all i [N].
28

---

where Wid E R2d, xds, bia E 222d, and Aja E xdd. Let W bi A, W b2, A be given as the proof Proposition 26, for achieving an Toxe error of é, to be fixed later. Recall z; (x. w.. , .......,,,) w.,,,, In the following, we remove the zero columns of W corresponding to the h part of the input (see Lemma 23), which does not change the resulting function. Our Corollary 27. Let fh be given by the construction in Proposition 26, and suppose Th 2 vQ(ro= Vde).. Then, h satisfies the following guarantees all [N] and [q]:
1. t 2 i, then h (1) = Od
2. tf < i, then h (1) It, ll E.
Proof. We can prove the statement by induction. Note that it holds for = since h, =0g- For the induction step, suppose it holds up to some i, and recall
h h + fn (h
21: 0
If 2 i then h²(() Oa and fr² (hx 2 θ = 0g by Proposition 26.
If f < (h, =3; x = 0d-
+ 1, then ||,, (1) Ft, ol S & by induction hypothesis, and
Finally, if = <iiiii i then h (1) 0 and (h4 zii O 2 llc S..
Note that since h | S rı for all j E [N], the projection II,, will always be identity through the forward pass, concluding the proof.
By symmetry, the same construction for f would yield a similar guarantee on h
The last step is to design fy (h h ,y) such that
f 1 z5: ,,) = g( (h- + h + (a) [ = =i,, :)......., ... [ = T)
The following proposition provides the end-to-end RNN guarantee for approximating simple @STR models.
Proposition 28. Suppose 9 satisfies Assumption 2. Then there exist RNN weights Oax with vec Rm)) E R (i.e. with p parameters) and rh vgra + /e2uN/ (raTw), such that
sup kE[M]
Ii,)) , i(p: Owm))e I 46zm
(B.13)
for all t [N] and ||اا||2 S Ta for all j [N]. Additionally, we have
||vee (rm)(l I poly(ra, Des Two Ta: E
PS poly(r.. D., mgg Twry Tas E
(B.14)
and fT. Sh. do not depend on h and h namely the first d, columns of W and W that are multiplied by h and h" respectively are zero.
Proof. As the proof of this proposition mostly follows from the previous proofs in this section, we only state the procedure for obtaining the desired weights.
Let (1y) 5m denote the standard basis of Rdd, Since a(=) a = we can implement the identity mapping Rd via a two-layer feedforward network with the following weights
v1
-1
0
0
0
0
W
iia=
bia O2ds Aia
-1
0
0
0
0
-1
1
di.
construction can then be denoted by
Awor(War))
Aw.)
h
h
h
Amo)Wia)))
Au
a._ C.WWW b.)
h
h
h
h + h + X2
Danx (p: @
z;
X1
X2
29

---

Note that the addition above can be implemented exactly by using the fact that ( + + 23)
(-21 22 - 23)
21
+
22
+ 23- Specifically, the weights this layer are given by
0 V1 V1
V1
01
V1
W add
Dadd 02da:
Aadd Asd,
dd
dd
dd dy
11 dr
17 dp
where W add E 2d x3d, badd 2dn, Andd E Rdd x2dh
Let b% (and similarly )) be given by Proposition 26 with corresponding enror Ey. Using the
shorthand notation It = (Iit) ..... mr,)) E Rd and it = =h," +
h
+ X2. we have
H+
1,," + h + X2 2eel2 S h Σ v Vaay,t t.
+ h
Σ
y (a 5)
+ +1xx2 (x,,,,,)))
j= N
I gdd( + E),
which holds for all input prompts p with ||ردع|2 S rz for all j E [M]. Finally, we have
sup (ayll,Sr..Wjell
[g(x+)) - ag oW Et + bn)l s
sup
[g(xz)) a o (W ae
at + b,]
||o
+
sup
a o W (W
at + by) a, o gā + by)
| Srl.
S V + Ta (2En + +).
Choosing Eh = V homm/(44/ (Avqdrarw) and ē = /22m// (2vqdrarw.) we obtain RNN weights that
saitsfy |/eee ( l1 S poly(rz) De, Tas Two E2m)), completing the proof.
B.4
Generalization Upper Bounds for RNNs
Recall the state transitions
h h IT,, (hz² 5 (z; OT
hラ = 1l, (hj + f (z
Zzi θ-)
We will use the notation h (p: 0T²)) and h (p: θ
to highlight the dependence of the hidden We then define the prediction function as
states the prompt p and parameters 0,," and O h F(p: O where
F(p ,r, - 1,, (p: 0 h (p: θ 2, θ,)
We now define the function class
Frum {p.j + F(p: O ,,), + O O, E O
We can then define our distance function by going over (p.j E 5m).
doo (F, F) = sup
F(p:O), O , - F':: 6 6,, O,),
p.jES
We will further use the notation
(,) = W r., o (
o (W] 2, (-+ + by) + b1, E FkN,
and (3 = WZ, o Z (W
Pb E FNN.LY"
We similarly define FNN The covering number of Fax can be related to that of FNN.L, FNN.LA and FNN.,, through the following lemma.
30

---

Lemma 29. Suppose for every O₂ O O E Oaxx we have
[Wy L, wXy I Cw:
[ Ln op ... [ Wiih Tp S aN.
W La lop ... | i, op S SNN,
where ON S NN-1 Then,
C doat c) S LogCC e/2, + logc
:xN, doo
c
4eCW
+ log ( doo AeC
Proof.
Throughout the proof, we will use the shorthand notation h² (p: 07,) and h3
he (p: O,,) ), with similarly define h and h We begin by observing
[y(h h5 23; ,2) -5 h 2, 0,) S + E2
sup P.jS.
where
E = sup
fu(h 12j :z; ,2) (n h2j z; 0,))
P.jES,
E = sup
(k h2j zzi ,,,) ( h z3 6,)
p.jES,
Then, we observe that & = d. (fy (:; 2 (+ )) Thus, we can ensure & s c/2 with a covering (Qy) of size C(F%,, doa (/2). Hence, move to &2.
Using the Lipschitzness of fy. we obtain
&g < WY T. w
(sup 12.5 - nīj² 11 + sup p.j
hoj hīj l1
op
p.j
S.W
(upp buj
happl1ny' h2j"
hnj
|1
sup D.j
h hīj - 1,)
Further, by Lipschitzness of II,,, we have
sup p.j p.j
hT h, <supl h h h
sup
1
S 1h
p.j
=2
25-1 0,, +-
p.j
By the Lipschitzness fi², for the second term we have
Et < w 7 1. h - -h-hhh n s aN
h h
Moreover, we have E < doe f% (:; 0r,, (: O,,)) Consequently, we obtain
sup p.j
11 h,
< (1 + (1+aa)
sup
h h h 11, + ddo (1
pj
j-2
Σ
(
(1 11
< (N
31

---

We can similarly obtain an upper bound on supp.j hjj -hj Hence, we have + dx (5h (1:
& - e do (
Therefore, by constructing / h/ coverings 1 and ( which have sizes C(FNN, e/ (/cCC))))) and, C(FNN, c/(4cC),N)
respectively, we complete the covering of FaM..
The next step is to bound the covering number of the class feedforward networks, as performed by the following lemma.
Lemma 30. Let
br.-1) FNN.L {ar + W Lo 1--10(.... W2(a(W bb) ..).b..+bb......... ONN E ONNY.
where ON = I, WI. 1- br.-1, Wt, and (NN)) IRP. Further, define the distance function
dx (f.ff)) = sup
- f())) ff.f' e FNN.L. |
Suppose (Wiles |bbll12 for all Then, for any absolute constant depth L = (1),, we have log (FNN,,,, doa; 6) S p plog(1 + polpooyy0 (R)/e).
Proof. Let x. = x, x (W 1 + by) for I E [T. 1]. and æ L- Also let (œt) be the corresponding definitions under weights and biases (Wi) and (b.). First, we remark that for I E [L 1).
|2ll|| & | Willopl/=/ 11/ + |161l22
(B.15)
1-1
W 11lp |
+
> b ll2 W 1- 1lap + |lbell2
1=0
1=0
S {ooly(Ht,
(B.16)
where we used the fact that is absolute constant. Next, for 1 [L 1]. have
| 21ll2 -
W W W + b 6
W Willop |z] - 22-1 11 + || l1
W W
+
b:
b,
op
- poly (R) | - - + W, w
+
by
6. ||
Once again, using the fact that L is an absolute constant and by expnaind the above inequality, we obtain
W: w. + b. 6.11]
| - 21ll2 S (ol
Finally, we have the bound
| ir.112 < W r.1l 1101,11 2r.-1112 1|2 + || 112 Wr wr op
S poly(R) voc(ONN) voel @NN)
Consequently, we have
log C(FNN,( doo, t) < log((10 E RD ||0|/ < poly(d.g)) 11-1:: (o))( poll())))
p + (R)y(R)/c).
where the last inequality follows from Lemma 41.
Therefore, immediately obtain the following bound the covering number of Faxx
32

---

Corollary 31. Suppose Qun _ j E [M]. Then,
{ IPP ||vec())l2 S Rj and /
R for all E [n] and
log ((FRM doc, - log(1 poly (R))/)))//).....
We can now proceed with standard Rademacher complexity based arguments. Similar to the argument Appendix A.2, we define truncated version the loss by considering the loss class
CRNN y: - (JRxx y3)² SRNN E FRRN),
where the constant will be chosen later. We then have the following bound on the empirical Rademacher complexity of CT
Lemma 32. In the same setting as Corollary 31 and with T 2 1, we have
p plog (RN
Ri (
ROCK (
S 50
Proof. By a standard discretization bound for Rademacher complexity, for all é we have
2 log C(CenN doc. E)
Ri ( CRNM
S E T
n 2 log C(F do E/ (2 n
S sEtTV
2p 2plog(1 + poly poly(RR)NvF/e)
SetTV
where the second inequality follows from Lipschitzness of (.)² A T. We conclude the proof by choosing 1/ nn.
We can directly turn the above bound on the empirical Rademacher complexity into a bound on generalization gap.
Corollary 33. Let θ = arg min
PANM (e). Suppose θxn S
{ E RP ||vee (0) - R),
and additionally /3C log(n)) + I R. Then, for every 0, with probability at least
1 8 (nN)-1f2 over the training set, we have
R (Ô)
RRUN ) SSO S
p plog(RNNr))
log (1/))
7
1
Proof. We highlight that for the specified Rt Lemma 12 guarantees
|=
< R for all i E [n] and
j E [N] with probability at least 1//2 Standard Rademacher complexity generalization arguments applied to Lemma 32 complete the proof.
Note that RRAM ( < RRAM ( which is further controlled in the approximation section by Propo- sition 28. Therefore, the last step is to demonstrate that choosing poly(d, 9. logn) suffices to achieve a desirable bound on gam (è) through [ (Ô).
Lemma 34. Consider the setting of Corollary 33, and additionally assume R 2 The Then, for some poly (R, n)) we have
Ram
RMU
Proof. The proof of this lemma proceeds similarly the proof of Lemma 20. By defining
Ag
Jam (p; θ)
33

---

and following the same steps (where we recall ~ Unif([[V])) we obtain
R (
I v + + > VT]
パ RKN
+
B الاه
1/2 PA 2 vF) 1/2
where
[ 1/2 2
1/2
jAAx (p; |)3 1/2
2
and
P(Ay > VT)
S
V 2
+ IP
(I
[inam (p: 6)2
2
V 2
From Assumption 1, we have E [ S and P(ys 2 c For the prediction of RNN, we have the following bound (see (B.16) for the derivation)
Ly
Ly 1
Dunu (p: 0)2 s
W ap (1 h5 (2))112
by
WV L.
op
1=1
1=0
1=0
As result,
Drn p; 6)₂} S poly(R) + Fa + |
As result, by the fact that rh S R and Assumption 1, after taking an expectation, we immediately have
E jRxx (p; 6)3} 1/2
S poly(R).
On the other hand, from Lemma 12 (with N 1), obtain
(( | (p: ②)
2 VT
I e (0rr//oooo
Therefore, for some poly R, n)
obtain the bound stated in the lemma.
We can summarize the above facts into the proof of Theorem 5.
Proof of Theorem 5. From the approximation bound of Proposition 28, we know that for some R (oly(d, (d. q, Tay Tw:: Ezwar log(nN)) and the constraint set
Orw o ||vec()) R. WT. I.p ||
1. SaN,
W E, lop
wiiillyn lop S AN)
with any ON S N-1, we have f S 62m- The proof is then completed by letting th / y /E2ex/ (FaTw), invoking the generalization bound of Corollary 33, and the bound on truncation error given in Lemma 34, with It = poly(d, aa Two Ezmn log (og)).))).
B.5 Proof of Proposition 6
The crux of the proof of Proposition bound on the prediction error at any fixed position in the prompt.
show the following position, which provides lower
Proposition 35. Consider the same setting as in Proposition 6. There exists an absolute constant > O, such that for any fixed E [N], if
E (Dnou(p)) - -1,) sc
then
N
N
dn > Ω
log(1 + S
and |1 Ω
log(1 ( dr
We shortly remark that the statement of Proposition directly follows from that of Proposition 35.
34

---

Proof of Proposition 6.
Let be the constant given by Proposition 35. Suppose that
1
B
| (p)
2112 c.
Then,
N I8 [JaRx (p),- -b) S c.
1 N
min ((anx - -ys) jE[N]
As a result, there exists some E [N] such that (Uxxx()) - yj) S c. We can then invoke Proposition to obtain lower bounds on d,, and ||U op completing the proof of Proposition 0
We now present the proof of Proposition 35.
Proof of Proposition 35. Let h = hU E R2dh, and define
T
((h,) = (Su(h,, 2; :y(:),,,,.,,,,,,,, 2j, (i-1). Jy (h2, 2j (i+1):)), Sa (h Øj (N)..)
E RNN-1
In other words, Φ Reds RNN-1 captures all possible outcomes of (nm(()) depending on the value ty (excluding the case where t, = j). Ideally, we must have fu(h, Zy,, (k). j) se g(øx).
Let ((),, ......'. (P)) be an i.i.d. sequence of prompts, then modify them to share the jth input token, i.c. zj zj for all i E [P], with /' to be determined later. Note that by our assumption on prompt distribution, this operation does not change the marginal distribution of each (1), Similarly, define = (g(z)) (0) ) ((.))....99()))...... 1() (f1)
2( E N-1
for each prompt. We also let (0) (5 be the corresponding hidden states obtained from passing these prompts through the RNN, and define h using them. Note that g()) g ) is an i.i.d. sequence of vectors drawn from (0,0IN IN-1).
We now define two events Ej and E2, where
| - E = V
g / 2 2 2
and
P E2 Σ
NV N 5
1
- (((h))))))
S 282
where 8 E (0, 1) will be chosen later. In other words, En is the event which ())) are "packed" in the space, while Eg is the event where the RNN will be "wrong" at position j on at most 28 fraction of the prompts. We will now attempt to lower bound P(E Ez).
Note that g ( (())) (d)
2g where g -N-)).
~NOO.
1). By union bound we have
P(E
P
9
(a)
11 S S
ifk
< p2p
(V2lgg11 S SENNN- -
< p2p
||وو|2 - Elll9laal S 1/2
- (e-c,//2/((N-10)))
for all Eg S cv2, where c>> > 0 is absolute constant such that cVN - < Ellgg []. and the last inequality holds by subGaussianity of the norm of a standard Gaussian random vector. From here on, we will choose Eg = c/ /2 (and simply denote Eg 1), which implies PP P(E)) < (N
To lower bound IP( Fiz ), consider a random prompt-label pair p. y and the corresponding g. Note that in the prompt p, the index ty is drawn independently of the rest of p, and has a uniform distribution
35

---

in [M] Let plt, + k] denote a modification of where we set equal to k, and let yftt + k] be the labels corresponding to this modified prompt. We then have
(k₂))
g|12
(prmm(pt; + k)); =(xx)))
N kTj
Damm(pe + kl); - u(plt, + 1e)),)
N
RA,
[Gjen (p), -y3}²]
As result, via a Markov inequality, obtain
1 (1,) - -gli
=² IP Er, (Wrm (p); - 11) 2 2²
82
82
8² E (p))(()) - y3
0².
Going back to our lower bound on PP E2), define the Bernoulli random variable
EVN
( 1
900
Note that (2(1) are i..d. since n and (0)) do not depend on æ,, Then, by Hoeffding's inequality,
P
F(E
= P
(0) 2 252p
2P-2P8
j=1
We now have our desired lower bound on P(E 0 E2), given by
2 -2 - (2
Suppose 2 e- N for some absolute constant e' > 0. Then, choosing P |e N for some
absolute constant d" would ensure P[E] n Eg) > 0, and allows to look at this intersection.
Let I = (i: 20) = 0}. On Ei, and for i E I with f k we have
[ *(h) (10) > ||2 2 g (1) (
(h
(i) -g(0)
(() 1/2
1 |0(1)(t) g(ab)
2 Eg VN - 1 2
= NVNEn.
8
As a result, the set { [1 i E I) is an ThEN -acckin for (h: ||/|l2 S v2| ll Ilop" rn Using Lemma 41, the log packing number can bounded by
Note that from the Lipschitzness of fy, we have (00(h()) - (((((()) ||
5 LVN
h (8)
2 up
U
2| 1 ))
M
log < dn log
1+
1 log 1+
Eh
c
On E1 E2, have 2 (1 (1-282) P3 > (1 26 e for some absolute constant > 0. Therefore,
log(1 -282) cN
S dh.
log(1 + +2 +2
and
2% (log(1 282) + c.V)
$ ||1|
2 log(1 + e /2 122)
Choosing 8= 1/2 and recalling &g x 1, we obtain En 2 (1 Ce)/E for some absolute constant C> O, which concludes the proof.
D
36

---

B.6 Proof of Theorem 7
We first provide an estimate for the capacity of two-layer feedforward networks to interpolate samples.
Lemma 36. Suppose f i...d
~ (N Id) and let y = (u, æt,) for arbitrary t; E [N] and E gd-1, Then, there exists an absolute constant e > 0 such that for all m 2 n and with probubility least e, there exist data dependent weights a, b E R and W E IRmxd such that
a [To(Wa' + +b) - y Viel
and
a 2
W ト + |bb12 On7).
Proof. The proof of Lemma 36 is an immediate consequence of two lemmas.
1. Lemma 37 shows that the inputs x scalar values with unit vector v.
(n) can be projected to sufficiently separated
2. Lemma 38 perfectly fits univariate samples using two-layer ReLU neural network. When invoking this lemma, we use || = (V))) and e = 22(1n²²) as given by Lemma 37.
The only missing piece is to upper bound ||/l|2 appearing in the final bound of Lemma 38. To that end, we apply the following Markov inequality,
EE
1
P (I 6m)
6n
6
As the statement of Lemma 37 holds with probability at least 3. this suggests that the statement of Lemma 36 holds with probability least j. concluding the proof.
Lemma 37. Suppose (ar00 jm ii.d. -N(O,L)) Then, with probability at least 1/3, there exists some
gd-1 (dependent {x(11} such that for all i + j.
x (1) v (1) = 9
1
(B.17)
n²
and Σか (u 22 O(n).
Proof. The proof follows the probabilistic method. Sample Unif(Sd-1) independent of (x) For each i + j. let
ai,j = u (x -
and note that a;,j v ~ N 2). We apply basic Gaussian coteennnctntratoon to place a lower bound on the probability of any ai, being close to zero,
n 1
P(Ji,j lans 5e <
Ep(lauss 5e)= Σ B[P((ar,)) S Selw)] S
V n 3
where the last inequality follows by taking c= (3n") Furthermore,
E a: (1)
Σ
v T (0)2
3n
3n
3
by Markov's inequality. Combining the two events completes the proof.
E IR" and y (g (g("))...g())) (T) R", such that (20)) - - 2 for all # j. For simplicity, assume e < 1. Then, there exists two-layer ReLU neural network
Lemma 38. Consider some =
9(1) Σ (w
37

---

that satisfies g(z(0)) = y for all i E [n]. m = and
(Lulley V
||ull22
+ 1|
||a| + | + 11b1 o
(B.18)
Without loss of generality, we assume that z(1) ... ... S (n). Then, we define the neural network 9 follows:
Proof.
- -
((t) = Σ do - -1) - -- 2(1) + +1) 1)+
22(2) 2(1) -y Ja(t 2
( yli-1)
y y - 116-2)
-(1-1) - 2(1-2) olt - 2(6-11)..
3 2(1) z(1-1)
One can verify by induction that g=x(0) = y for every i by noting that the slope of is
(g()) (0) (ii 2(1-1))
between (2(1-1), ((-1)) and (,(0,)()) From the above, we have wi 1, |1 - || + 1, and
||a'll2 2 1/212//2. For (01==12 + m)e² / / 1/1 let au', w' /a, and b b' b//a. By homogeneity, the neural network with weights (u, w. b) has identical outputs to that of (u', w b' and satisfies (B.18), completing the proof.
We are now ready present the proof of the sample complexity lower bound for RNNs.
Proof of Theorem 7. First, consider the case where dn < n. Note that as a function of Uh
(U'h h U h h²),,,) fy is L-Lipschitz with
L
W W.w llpll
W Ly 1lpp W2llopp
Using the AM-GM inequality,
I/L,
-
1 (()oc(O)11 se No/h.
L2
Ly
As result, we have U /2, By invoking Proposition 26, to obtain population risk less than some absolute constant 03 O, need
N
dp 2 Ω
9(N--9).
log(1 + L )
This implies 2 da > 1(V--9). By taking in the theorem statement to be less than 1 obtain a contradiction. Therefore, we must have either a population risk at least 63 or d,, 2 n.
we
Suppose now that d, 2 We show that with constant probability, we can construct an RNN that interpolates the n training samples with norm independent of n. We simply let O, 0, θ U = 0, and describe the construction of W L......, W2, W y. and (br) in the following. Using the construction of Lemma 36, we can let
a
W
Onxda (m--))xde x
b (mmm)) W2 =
W,, "
b =
m (m=nnxxdd
m-n
0 (m)))
0 (m--2)x (m
where W E [and and a, b IR" are given by Lemma 36. Then,
w W W yal j(u + by) = (y)0), 5/ O)T.
For (Wi) 1=3 we let (Wi)n (Wi)22 = and choose the rest of the coordinates of Wi to be zero. Therefore, the output of the (th layer is given by
(1) (o (o l ( v..)) T.
38

---

For the final layer, we let L., = ................................ Using the fact that o(2) o(-2) we obtain
fo(U U hj jou m (X) y0o
We have found @ such that R (+) = 0 and [vec())) 2 - O(n2) (recall that Ly S {0()). As result, θg must also satisfy vee I O(n").
On the other hand, notice that as function of Uh (U U is E-Lipschitz with W L.,,lll Lw
W 1op W 221 2llop
From Proposition 6, using the fact that Il-Ilap 11-11p and the AM-GM inequality, obtain
1/44 vec 0)1 (2 (
( log dr.
N 1/T,y
to achieve population risk less than some absolute constant C3 >> 0. Recall that log da S N for some e 1. The proof completed by noticing that unless n 2 (N(N))) for some absolute constant
a 0. @ will always be less than the lower bound above, with some absolute constant probability 02 0 over the training set.
C Auxiliary Lemmas
Lemma 39. Suppose A E RRd xdixds and B Rdda Then, for all r, 2 1 and p. 2 1 such that 1/p+ + 1/q- = 1, we have
|AB r, || |||
9.8"
Proof. First, we note that for any vector E Rdda we have
| Abll,
A
S
b,ll| S ||A,,,,,,,,, 161p
where the last inequality holds for all conjugate indices p, and follows from Hölder's inequality. We now have
AB -
AB 1
<
A mp
B 11 ||A BII
The next lemma follows from standard Gaussian integration.
Lemma 40. Suppose & N(, E). Then Var([|=| ?) 2 2tr 1 Σ) + 44 Ey..
The following lemma combines two different techniques for establishing packing number the unit ball, the first construction uses volume comparison, whereas the second construction uses Maurey's ss sparsification lemma, both of which well-established in the literature.
Lemma 41. Let P denote the e-packing number of the unit ball in Rdd We have
log P dlog 1+ 2) }
{ (1+ log(1 + +2de?))
Finally, the lemma below allows us to approximate arbitrary Lipschitz functions with two-layer feedforward networks.
Lemma 42 ([Bac17, Propositions and 61). Suppose Rd + R satisfies f(x)) < LR and
[f(x) f(x') < L|[ x' æ'112 for all æ, x' e R2 with ||>|| S R and |æ'') S R and some
39

---

constants L, R. >> 0. Then, for every > 0. there exists a positive integer m and W E R b Ih" and a E Rh, such that
f((x) aool oWo + b) Se
sup |
Additionally, we have
t+
m Ca
LR(1 + log (o &
WT
S
1 R
|b s 1,
||a||2 S
CaLR vm
LR(1 log (og(Le)))
E
2,00
D Proof of Theorem 9
Let u be sampled uniformly from gd independently from p (t1, and note that we have
sup B[(u; (A( W x(s))))))) Z En- P (ي) fA(S.)((,, W ((S.))))))) wEBd-1
for all A A. From this point, will simply use f for fa(s.) and W for W A((S)) Next, we argue that the output weights of any algorithm in A satisfy
W
( og
Vk: E [mi];
for some coefficients (a& )i This is straightforward to verify for A E Asp,
(6)
Vw.
FPN (f. W) E span(x(")...,,
For A E AERM, note that f only depends we through its projection on span(a ,..., (())).
As result, any minimum-norm E-ERM would satisfy wy E sspanzz())...... (()),
Note that for n I Nd, the span of (11), ,(")),..,.!!" Sn. Let a(1), ,i.,..., ((n) denote an orthonormal basis of (".,,, and let V (1(1), ..... ( E RRxNNd, Recall that for the simple-1STR model considered here, Y/ = y = mi, for j [N]. Then,
(x()) n-dimensional with probability over
Euv.jp [1y f(1,, wx),)² 2 Eu,,, (Va(yy u, f1, Vz)] = Eu,,, V (aa([ x)) f1. Vx)].
where P., E Ndxd has the form Oo...., Ia. 0z) T The conditioning above comes from the
fact that via training, f and W can depend on u. but the prediction depends on æ only through Vx. Consequently, we replace the predicition of the FFN by the best predictor having access 41, and Va. Note that 41, u. and x are jointly independent, and the joint distribution ((Pt, u, x) x) is
given by N/1.
VPt, u. I,
thuss we have
Varl (ar((P,,u,)) u, h, Vx) 1- VP,, u||2.
In particular,
P (()))
En, (Varr((P,,,,0)) u,,, Vw)]= =
and
N
Ex, (ar((P,, u,,,, Vx)]= =
1
P vi))
Nd
1
Ad
Nd
40

---

E Experimental Details and Additional Results
In this section, we provide the details of our experimental setup, well as additional results on the effect of Figure 3.
250000
Trasfonner
(Training Samples)
200000
PPN
Architectures. We use Transformer com- posed of multihead attention layer with g heads, where each heads observes the entire d+ (gg++)dddimmnsion input token, followed by fully connected ReLU layer with width 100. For the RNN, we use simple bidirectional RNN with a hidden state size 500 x q, and a lin- ear readout layer. For the FFN, we use a depth-3 fully connected ReLU network, where the first layer has width dq and the second layer has width 1000. The output layer of the FFN has width N to match the input sequence.
150000
100000
50000
3
Figure 3: Number of samples required to get to test MSE loss 0.88 while training with online AdamW for the quadratic qSTR model explained in Appendix E with N 7. The gap increases with larger
closer theoretical analysis capturing the effect of large q can be an interesting direction for future work.
Optimization. For Figures 1 and 3 use online A with weight decay 0.1, where in Figure we use a learning rate of 10 10-3 and in Figure
learning rate of 10 Each optimization step uses independent batch size of 64 samples, and we track the test MSE loss using an independent set of 10,000 samples. For Figure 2 we AdamW W with weight decay 0.2 and learning 10-3 fixed training set of 50,000 samples.
Data Generating Model. In all experiments, we sample æ ~ (O, INa). For Figures and 2 we have 9 1 and define g(x,) (u, æi) for unit-norm uniformly sampled from the unit sphere. For Figure 3 let gar,,..... ;. V4 E.= Hez ((u, æ:)) where Hez(z) (=² - 1)/ is the normalized second Hermite polynomial. We use a non-linear as this is a more challenging setting where e.g. Transformers require g heads by Theorem 4.
The code reproduce all our experiments is provided at: https: htops://en0 /ttp://ggtttt.ttt/ee com/nousavin/
41

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We prove all the claims made in the abstract and introduction in this paper.
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 be expected to generalize other settings.
much the results
is fine to 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:
We discuss the limitations throughout the paper and mostly in Section
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 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 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, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of 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 faimess.
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 '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]
42

---

Justification:
Our Definition 2 of the qSTR model and our Assumptions 1, and 3 are clearly
stated.
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 or 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 be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be 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 affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA].
Justification: Our contributions are theoretical and our limited numerical simulations are for illustration purposes only. We will include a link to the GitHub repository of our code in the de-anonymized version.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a 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. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution 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 often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require 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 reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to 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., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
43

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our contributions are theoretical and our limited numerical simulations are for illustration purposes only. We will include a link to the GitHub repository of our code in the ic-anonymized version.
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/
wiw.issiiiiiiyyyylio 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:
gewcc//ggiee..eee CooeeSumiissseeeee wwweiisssioooooooooooo onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments 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).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: 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?
Answer: [NA]
Justification: Our contributions theoretical and our limited numerical simulations are for illustration purposes only. We will include a link to the GitHub repository our code the de-an de-anonymized version.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
Justification: Our contributions are theoretical and our limited numerical simulations are for illustration purposes only.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
44

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. 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 show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in 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 reproduce the experiments?
Question:
Answer: [NA]
Justification: Our contributions are theoretical and our limited numerical simulations are for illustration purposes only.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https / http:///eerisssseeeee httpps/ccc....ttttecccceeeeeeeee
Answer: [Yes]
Justification:
We have followed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.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:
Our contributions are theoretical and do not have immediate socictal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
45

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 out that 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 is 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 of 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 of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our contributions are theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
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 or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our contributions are theoretical and we do not use any such assets.
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, possible, include URI.
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.
46

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/c datasttss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information 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:
Our contributions are theoretical and we do not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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. Crowdsoureing 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:
Our contributions are theoretical and we do not perform this type of experiment.
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 in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or 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 to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our contributions are theoretical and not perform this type of experiment.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
47

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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 as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We did use LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //tprr//n.uu..peeeeeee ///CCooferencce/2225//L/. for what should or should be described.
48


Reviews:
[{"review_id": "5ZI7kpNmKK", "reviewer": "Reviewer_J2MZ", "summary": "This paper investigates the statistical advantages of Transformers over FFNs and RNNs from a sample complexity perspective. The authors introduce the qSTR model, where each output depends on a sparse, dynamically defined subset of the input tokens. They prove that Transformers, with enough attention heads, can learn such models with sample complexity nearly independent of the input length, unlike RNNs and FFNs. The work includes formal theorems and empirical validation, contributing to our theoretical understanding of Transformer advantages in sequence modeling.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths.**\n- The theoretical results establish a clear separation in sample complexity between transformers and RNNs/FFNs. The insights are conceptually intuitive.\n- The synthetic experiments match the theoretical predictions regarding how sample complexity scales with sequence length.\n\n**Weaknesses.**\n- While the qSTR model is theoretically insightful, it may be overly simplified compared to real-world language tasks, where dependency structures are often more intricate and adaptively sparse (e.g., token-dependent).\n- It remains unclear whether Transformers trained via standard optimization algorithms like Adam can effectively discover the constructive attention patterns in the theoretical analysis.\n- How sensitive are the conclusions to the embedding dimension? For instance, if we increase the embedding dimension, can we reduce the number of heads required to achieve comparable sample complexity?", "was_revised": true, "final_justification": "The response and detailed clarifications have addressed my concerns. I will maintain my positive score.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.\n\n---\n* **The qSTR model may be overly simplified compared to real-world language tasks.**\n\n    We agree with the reviewer that this model is a simplification of real-world dependencies. Our motivation to view this model was to use it as a theoretical benchmark following the works of [SHT23] and [WWHL24]. However, we will provide the following example to better demonstrate the relevance of qSTR in real-world language modeling:\n\n   > **Input string**: *For my vacation this summer, I’m considering either Rome, `Paris`, or **Tokyo**. If I go to Rome, I would like to see their historic sites, if I go to Paris, I want to visit their `art museums`, and if I end up in Tokyo, I want to try their **cuisine**. Can you tell me how much my `second` option would cost? Would it cost more than the **third** option?*\n\n    Here, the token `second` determines that the important tokens to process are `Paris` and `art museums`, and the token **third** determines that the important tokens are **Tokyo** and **cuisine**. Namely, the task involves both retrieving a few important tokens from all tokens, and processing them.\n\n    We hope this example clarifies the relevance of the qSTR model, and plan to include such an example in the final version of our paper.\n\n---\n* **It remains unclear whether Transformers trained via standard optimization algorithms can effectively discover the constructive attention patterns in the theoretical analysis**:\n\n    Indeed, this is an important problem. We would like to highlight that we *provide some empirical evidence in Figure 2 that our attention construction is indeed learned by AdamW*. Further, [WWHL24] have studied the optimization aspect and were able to theoretically prove that gradient-based optimization recovers the same construction. However, their analysis is in the population limit, and we leave the analysis of finite-sample gradient-based optimization to future work, which we believe should be within reach given the current theoretical tools.\n\n---\n* **How sensitive are the conclusions to the embedding dimension?**:\n\n    The lower bound on the number of heads holds for any embedding dimension, and is in fact an approximation lower bound, meaning that even with infinite embedding dimension and infinite number of samples, the Transformer still cannot learn the qSTR model unless $H \\geq \\Omega(q)$.\n\n    On the other hand, a larger embedding dimension may be detrimental to generalization and increase the number of training samples needed. However, depending on the way the embedding is defined, one might be able to find tailored generalization arguments that avoid a worse dependency. In particular, one should avoid using one-hot encoding for positions, as the embedding dimension would grow linearly with the sequence length which is not ideal for this setting.\n\n---\n\nWe would be happy to answer any follow-up questions.\n\nReferences:\n\n[SHT23] C. Sanford et al. “Representational strengths and limitations of transformers”. NeurIPS 2023.\n\n[WWHL24] Z. Wang et al. “Transformers provably learn sparse token selection while fully-connected nets cannot.” ICML 2024."}, {"review_id": "0OKk0wr5Sa", "reviewer": "Reviewer_iF3B", "summary": "This paper compares Transformers, feedforward, and recurrent networks in qSTR or simple-qSTR setups, where the ability of inferring dynamic sparsity is required.\nAs a result of comparison and statistical analysis, it is proven that the sample complexity of a single-layer Transformer is almost independent of the context length, while recurrent networks require the samples at least dependent to the context length.\nThe (simple-)qSTR model family assumes a sequence-to-sequence setup, where the input is composed of the sequence of (x_i, t_i) where x_i corresponds to the value to be retrieved and t_i corresponds to the index for retrieval. The simple variant indicates the case where t_i value is fixed for every i.\nIn analyses, Empirical Risk Minimization (ERM) is used for finding bounds.\nThe results indicate that, (1) the sample complexity of Transformers depends on the context length N up to log factors, (2) RNNs cannot learn general qSTR albeit it can learn simple-qSTR, (3) FFNs require at least N samples to learn simple-qSTR.", "questions": "* Do you expect RNNs with attention mechanism will address some of the issues noted in the paper?\n* Do you think the result of Figure 2, that the standard optimization of Transformer will match the theoretical construction, even for general multi-head cases?", "limitations": "Explicit mentioning of the limitation about the potential gap between theoretical analyses given by ERM and the empirical training done by gradient descent algorithm would be helpful for readers not knowledgeable to the field (like me).", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n* Sound statistical analyses\n* The organization and flow of the paper is smooth\n\nWeaknesses\n* Empirical experiments are mainly done on 1STR and simple-1STR setups\n* Some factors for logical flow requires readers to refer to appendices.", "was_revised": true, "final_justification": "I checked the authors’ response and other reviews, and want to keep my score.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.\n\n---\n* **Experiments are done on 1-STR**:\n\n    Indeed, we choose 1-STR as the simplest baseline and still observe the theoretical separation in practice. We believe that this separation would be even more pronounced for larger values of $q$, and plan to include such experiments in the final version of the manuscript.\n\n---\n* **Some factors for logical flow requires readers to refer to appendices**:\n\n    Thank you for this feedback. We will try to improve the readability of our manuscript before the final version.\n\n---\n* **Do you expect RNNs with attention mechanism will address some of the issues noted in the paper?**:\n\n    Yes, we believe an interesting future direction is to theoretically study the capabilities of hybrid architectures that can achieve some notion of optimal tradeoff by combining some global and local information.\n\n---\n* **Will the result of Figure 2, the standard optimization of Transformer, match the theoretical construction, even for general multi-head cases?**:\n\n    This is an interesting question and we will perform additional experiments before the final version of our manuscript to see if this phenomenon holds for $q \\geq 1$ where we need to use multiple heads.\n\n---\n* **Explicit mentioning of the limitation about the potential gap between theoretical analyses given by ERM and the empirical training done by gradient descent**:\n\n    We thank the reviewer for this suggestion which will help readers better understand the current state of theoretical results on Transformers and our contributions, we will clarify this gap in the final version.\n\n---\n* *Paper Formatting Concerns*:\n\n    Thank you for expressing your concern. We adopt the `amsalpha` citation style from `natbib` that is quite common among theoretical works in NeurIPS, specifically to be consistent with this literature.\n\n---\nWe would be happy to answer any follow-up questions."}, {"review_id": "sRuikqjqwj", "reviewer": "Reviewer_Sbp1", "summary": "This paper introduces a novel modeling task termed q-Sparse Token Regression (qSTR) and demonstrates that Transformers exhibit a sample complexity advantage over traditional architectures (RNN, FFN) when applied to this setting.\nKey Findings:\n1. A single-layer Transformer can effectively leverage its attention mechanism to retrieve relevant tokens at each position, thereby adapting to dynamic sparsity. As long as the number of attention heads satisfies H ≥ q, it can successfully learn the qSTR model with sample complexity nearly independent of the sequence length N.\n\n2. Recurrent Neural Networks (RNNs) exhibit a sample complexity lower bound of Ω(N^c) for learning general qSTR tasks, for some constant c > 0, regardless of model size.\n\n3. Feedforward Neural Networks (FFNs), even with unbounded model size, require at least Ω(Nd) samples to learn the qSTR task, where d is the input token dimension.", "questions": "Could you comment on whether your theoretical results (especially the sample complexity separation) might extend to deeper Transformer architectures? Are there specific technical barriers to doing so?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. A novel perspective based on statistical learning theory.\n2. Introduction of the qSTR task, which serves as a well-designed abstraction that captures dynamic sparsity and long-range dependencies.\n\nWeaknesses\n1. While theoretical clarity necessitates simplifications, the Transformer model studied is restricted to a single-layer architecture, which may limit the applicability of the results to practical multi-layer models.\n2. The empirical experiments, though illustrative, are limited in scope and conducted on synthetic tasks. They do not evaluate performance on real-world datasets or complex modeling scenarios, leaving open questions about practical relevance.", "was_revised": true, "final_justification": "After reading the rebuttal and other reviewers’ comments, my positive view remains unchanged. I believe the paper meets the bar for acceptance, and no issues raised alter my initial assessment.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.\n\n---\n* **The Transformer model studied is restricted to a single-layer architecture / How to extend to deeper Transformers**:\n\n    When considering the $q$STR model, it would be relatively straightforward to prove that a multi-layer Transformer can also learn sample-efficiently, where the subsequent layers simply learn an identity map. \n\n    We however agree that an interesting open problem is to find data models where there exists a depth separation, and one needs deep Transformers to learn sample-efficiently. There are certain tasks for which Transformer depth lower bounds are known [SHT24, CPW25]. However, these lower bound arguments are based on communication complexity and hold for finite-bit precision. It would be an interesting direction for future work to find representational lower bounds that eventually characterize sample complexity.\n\n---\n* **The empirical experiments, though illustrative, are limited in scope and conducted on synthetic tasks**:\n\n    Indeed, our main contributions are theoretical and we present the numerical experiments only to validate our theory, and to demonstrate that our theoretical constructions for Transformers match the result of optimization algorithms, thus our ERM upper bounds should extend to gradient-based optimization. \n\n    We agree that it is important to have real-world examples where one can empirically verify Transformers outperform RNNs/FFNs on similar recovery problems. We remark however that the empirical separation between Transformers and RNNs/FFNs on this type of information retrieval tasks has already been well-studied in the literature [JBKM24]. We will better highlight these empirical separations in the revised version of our manuscript.\n\n---\n* *Paper Formatting Concerns*:\n\n    Thank you for your suggestions. \n\n---\n\nWe would be happy to answer any follow-up questions.\n\nReferences:\n\n[SHT24] C. Sanford et al. “Transformers, parallel computation, and logarithmic depth.” ICML 2024.\n\n[CPW25] L. Chen et al. “Theoretical limitations of multi-layer Transformer.” FOCS 2025.\n\n[JBKM24] S. Jelassi et al. “Repeat After Me: Transformers are Better than State Space Models at Copying.” ICML 2024."}, {"review_id": "ON0FBiQz2Z", "reviewer": "Reviewer_Dqgk", "summary": "The paper tries to answer which function classes can Transformers learn with fewer samples compared to feedforward networks and recurrent neural networks. The dependence of sample complexity and input sequence length is shown to be critical, as sub linear dependence would imply lower error in longer sequences, and hence length generalisable solutions. The main task used to study the same is $q$-Sparse Token Regression where the output at every position depends on $q$ other input tokens, where $q<<n$. There are $2$ variants, normal where every position can have different $q$ elements which are causal to that position and a simpler variant, where every position has the same $q$ dependent tokens. With this task setup, the paper shows that a single layer Transformer with $\\ge q$ heads can learn this task with sample complexity independent of the length of the sequence. RNNs can learn the simple variant in a similar fashion, but for the standard variant it requires polynomial (in length of sequence) number of samples. Feedforward networks have linear dependence (in length of sequence) to learn even simple-qSTR. Thus together these results establishes a clear separation between Transformers vis a vis RNNs and vis a vis Feedforward networks.", "questions": "- I am asking the following 2 questions to understand better why this specific setup was chosen. I think the current draft of the paper does not quite make it clear why q-STR is an important problem.\n  - What would happen if the number of query positions that matter are also dynamic i.e. the task is not q-STR, but is $\\le q$STR ?\n  - q-STR is not causal, and the output at position $i$ can depend on future tokens as well. What’s the intuition on what will happen, if a causal setup is considered ? \n- Regarding Assumption 2, the paragraph above (lines 132 - 134) explained the intuition behind why the assumption was required. Can you consider adding a similar paragraph, some more lines for Assumption 1 as well ? The current draft makes it hard to understand the motivation behind adding Assumption 1.", "limitations": "The limitations from the authors perspective is not discussed properly. The authors mention in the checklist that they discuss them throughout the paper and in Section 6, but I don’t think it is quite obvious what the authors consider as what the limitations are from their point of view. So, it would be helpful if it can be mentioned in a consolidated section what are the limitations for this work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- Technically quite strong. I went through all the proofs and it looks correct, no unnecessary assumptions are made to establish the results. The assumptions that are made are explained at the start, and are all reasonable.\n- Quite comprehensive, establishing the results across Transformers, RNNs and FFNs, the negative results are also established for example are for a highly general class of RNNs that covers all architectures used in practise.\n- Adequate empirical validation made for all the points and they match with what the theory predicts.\n\n**Weaknesses**\n\n- One might argue, that one doesn’t learn something as new compared to what was known before with these results. While the results seem accurate, they aren’t surprising, the fact that Transformers are better than RNNs and RNNs are better than FFNs seems intuitive for the task at hand.\n- The paper is a bit difficult to read, and it took me multiple careful reads to ensure that I am not missing anything, and perhaps I still did. While the overall idea is quite clear, as mentioned in the earlier point, the overall idea was never in question, the exact specifics of how much better is one architecture better than the other which is the most interesting, and grasping that point from the paper is not that straightforward.\n- The relevance of why q-STR is important, where is the general form useful compared to the simpler variant ? A discussion section is needed for explaining such things, currently it seems it has no practical relevance.", "was_revised": true, "final_justification": "I read the authors responses, and understood some of the things I missed (before the clarifications given by the authors). Conditioned on the authors including some of the improvements in writing and including some of the discussions mentioned in the rebuttal, I think the paper can be quite solid and would constitute a good contribution to the field of theoretical analysis of modern neural architectures.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.\n\n---\n* **The fact that Transformers are better than RNNs and RNNs are better than FFNs seems intuitive for the task at hand**:\n\n    We would like to highlight that our contribution is exactly to mathematically formalize this separation in a quantifiable way. To our knowledge, *we are the first to theoretically prove a sample complexity separation between Transformers/RNNs/FFNs*, and we further believe that the proof techniques we develop to establish these separations can be useful in subsequent studies of other/combined architectures.\n\n---\n* **The paper is a bit difficult to read**:\n\n    Thank you for this feedback. Table 1 and Theorem 1 summarize exactly how much Transformers are better than RNNs (on all of qSTR) and RNNs are better than FFNs (on simple-qSTR). We will try to improve the readability of the paper before the final version, and would be happy to incorporate any further specific feedback on improving readability.\n\n---\n* **Why is qSTR relevant? Where is the general form useful compared to the simpler variant?**:\n\n    We believe this is an important question, also raised by Reviewer J2MZ, and plan to incorporate such an example to highlight the relevance of qSTR in practice.\n\n    > **Input string**: For my vacation this summer, I’m considering either Rome, `Paris`, or **Tokyo**. If I go to Rome, I would like to see their historic sites, if I go to Paris, I want to visit their `art museums`, and if I end up in Tokyo, I want to try their **cuisine**. Can you tell me how much my `second` option would cost? Would it cost more than the **third** option?\n\n    Here, the token `second` determines that the important tokens to process are `Paris` and `art museums`, and the token **third** determines that the important tokens are **Tokyo** and **cuisine**. Namely, the task involves both retrieving a few important tokens from all tokens, and processing them.\n\n    We remark that our qSTR model is of course a simplification of this setting, and it most importantly serves as a theoretical benchmark used by prior works, see e.g. [SHT23, WWHL24].\n\n    *The difference between qSTR and simple-qSTR* lies in the fact that the former is a sequence-to-sequence mapping, while the latter is a sequence-to-scalar mapping (i.e. all elements in the output sequence are identical). One way to illustrate this difference is to view qSTR as answering multiple questions about the prompt where the number of questions and thus the output of the model also grows with the input length, while viewing simple-qSTR as answering a single question, thus having an effectively constant-length output. We will better emphasize this difference in the final version.\n\n---\n* **What would happen if the number of queries is also dynamic?**:\n\n    This is an interesting question. In this case, one would need to encode a list of indices of different lengths, which is less straightforward. Further, one would need to define how a unique function $g$ can act on sequences of different lengths. However, once these technical aspects are resolved, one might be able to show that the fundamental learning mechanism of Transformers for this problem remains unchanged.\n\n---\n* **What happens if qSTR is made causal?**:\n\n    We note that qSTR not being causal is exactly why we use bidirectional RNNs. We expect that if one considers a causal restriction of qSTR, then Transformers with causal masks and single-directional RNNs can learn it.\n\n---\n* **What is the intuition behind Assumption 1?**:\n\n    Assumption 1 is needed for purely technical reasons (to establish concentration bounds), and is very mild compared to typical data assumptions in the literature. It essentially means that $\\Vert \\boldsymbol{x}\\Vert$ is subGaussian, and $y$ is sub-Weibull (even milder than sub-exponential). In practice these assumptions are usually satisfied as these quantities are typically bounded. We will further clarify this in the revised version.\n\n---\n* **Discussion of limitations**:\n\n    Thank you for pointing this out. We will better highlight the limitations of our work in the final version. Specifically, our main limitation is the dependence of the lower bounds to ERM instead of being algorithm-free, and it would be interesting to see techniques developed to obtain minimax lower bounds for RNNs/FFNs over larger classes of algorithms. While another limitation can be the lack of studying optimization dynamics for Transformers, we believe this part should be more doable as the optimization dynamics of similar problems have been analyzed in the literature [WWHL24].\n\n---\n\nWe would be happy to answer any follow-up questions.\n\nReferences:\n\n[SHT23] C. Sanford et al. “Representational strengths and limitations of transformers”. NeurIPS 2023.\n\n[WWHL24] Z. Wang et al. “Transformers provably learn sparse token selection while fully-connected nets cannot.” ICML 2024."}]

Author rebuttal:

Meta-review: The authors introduce a theoretical model task called q-Sparse Token Regression, 
and show that this task establishes a sample complexity separation between transformers and RNNs: a single layer Transformer with at least q heads can learn this task with sample complexity depending only logarithmically of the length of the sequence, whereas RNNs need polynomially many samples in the length of the sequence. A simplified version of the task leads to a separation between RNNs and MLPs, where MLPs always need linearly many samples in terms of the sequence length, whereas RNNs need only logarithmically many. Initial reviews of the paper were positive, and increased further after clarifications and additional results during the rebuttal and discussion phase. I concur with the reviewers and recommend acceptance. The authors should carefully incorporate feedback from the reviewers into the final revision.
Decision: Accept (poster)