Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Data
Authors: Alexander Havrilla
Wenjing Liao
Venue: NeurIPS 2024 poster (2024)
Keywords: scaling laws
LLMs
approximation theory
statistical theory
Primary area: learning_theory
TL;DR: We prove novel approximation and statistical theory for transformers and show this can be used to predict empirically observed scaling laws.

Abstract: When training deep neural networks, a model's generalization error is often observed to follow a power scaling law dependent both on the model size and the data size. Perhaps the best known example of such scaling laws are for transformer-based large language models (**LLMs**), where networks with billions of parameters are trained on trillions of tokens of text. Yet, despite sustained widespread interest, a rigorous understanding of why transformer scaling laws exist is still missing. To answer this question, we establish novel statistical estimation and mathematical approximation theories for transformers when the input data are concentrated on a low-dimensional manifold. Our theory predicts a power law between the generalization error and both the training data size and the network size for transformers, where the power depends on the intrinsic dimension $d$ of the training data. Notably, the constructed model architecture is shallow, requiring only logarithmic depth in $d$. By leveraging low-dimensional data structures under a manifold hypothesis, we are able to explain transformer scaling laws in a way which respects the data geometry.  Moreover, we test our theory with empirical observation by training LLMs on natural language datasets. We find the observed empirical scaling laws closely agree with our theoretical predictions. Taken together, these results rigorously show the intrinsic dimension of data to be a crucial quantity affecting transformer scaling laws in both theory and practice.

Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Data
Alex Havrilla
Wenjing Liao Department of Mathematics Georgia Institute of Technology Atlanta, GA, 30308 w1iao600gatech..o edu
Department of Mathematics Georgia Institute of Technology Atlanta, GA, 30308 ahavrilla3ggatech edu
Abstract
When training deep neural networks, model's generalization error often ob- served to follow a power scaling law dependent both the model size and the data size. Perhaps the best known example of such scaling laws are for transformer- based large language models (LLMs), where networks with billions of parameters are trained on trillions tokens of text. Yet, despite sustained widespread interest, rigorous understanding of why transformer scaling laws exist is still missing. To answer this question, we establish novel statistical estimation and mathematical approximation theories for transformers when the input data concentrated on low-dimensional manifold. Our theory predicts a power law between the general- ization error and both the training data size and the network size for transformers, where the power depends on the intrinsic dimension d of the training data. Notably, the constructed model architecture is shallow, requiring only logarithmic depth in d. By leveraging low-dimensional data structures under a manifold hypothesis, we are able explain transformer scaling laws way which respects the data geometry. Moreover, we test our theory with empirical observation by training LLMs on natural language datasets. We find the observed empirical scaling laws closely agree with our theoretical predictions. Taken together, these results rigorously show the intrinsic dimension of data be crucial quantity affecting transformer scaling laws in both theory and practice.
1
Introduction
Deep learning has made remarkable breakthroughs in various real-world applications, such natural language processing Graves et al.] 2013 Bahdanau et al. 2014 Liu et al. [023] Vaswani et al. [207]] computer vision Krizhevssky et al. 2012 Goodfellow et al. 2014 Song et al. 2020), healthcare [Miotto et al. 2018), and robotics [Gu et al. 2017]. A neural scaling law between the generalization error (or test loss) and several quantities, including the model size, training data size, and amount of compute, plays key role in the performance of neural networks. Perhaps the best known example of such scaling laws are for transformer based LLMs. Recent works in Hestnesss et al. [2017). Rosenfeld et al. [2019), Kaplan al. [2020), Bahri et al. [2021] demonstrated power law between the test loss and the network size, the training data size, and the amount of compute for transformer-based LLMss. Yet, despite sustained widespread interest, rigorous understanding of why transformer scaling laws exist still missing.
Understanding the theory behind neural scaling laws provides invaluable insights into practical applications deep learning. A mathematical principal of neural scaling laws enables researchers and practitioners to describe and analyze the performance of neural networks with precision and
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

rigor. The neural scaling law between the generalization error and the network size can be partially explained via neural network representation theory (Yarttsky] 2016]. Further, the neural scaling law between the generalization error and the training data size can be explained via statistical estimation theory. For feedforward neural networks Becmiidt-Hieber 2020] and convolutional residual networks [Oono and Suzuki 2019]. a generalization error bound has been established for regression. [Schmidt] Hieber [2020], Oono and Suzuki [2019) predicted Generalization Error ~ n n- where n. is the training data size, is the data dimension and e is a constant. This predicted rate of convergence is extremely slow for high dimensional data when D is large, while the rate of convergence observed in real-world applications is significantly faster, which reveals gap between theory and practice.
This gap can be bridged by exploiting low-dimensional structures of data. Real-world data sets often exhibit low-dimensional geometric structures due rich local regularities, global symmetries, or repetitive patterns [Tenenbaum et al. 22000, Roweis and Saul 2000]. According to Min et al. [2023] Figure 1J. the intrinsic dimension of CIFAR- 100, CelebA and ImageNet datasets are about 20, 20 and 40 respectively. When the tow-dimensional geometric structure of data is modeled by manifold, the predicted scaling for regression, classification and distribution estimation becomes Generalization Error n-=/d where is the training data size, d is the intrinsic dimension of the data manifold, and e is a constant [Chen et al.] 2022 Liu et al.) [021] Dahal et al. 2022 Nakada and Imaizumi| 2020]. In Sharmma and Kaplan 2022], the neural scaling law between the test loss and the network size predicted to be Test loss (size)=4/4 where d is the intrinsic dimension of data. While the theoretical studies focus on feedforward neural networks (Chen et al., [2022 Nakada and Imaizumi] 2020) and convolutional residual networks (Liu al., 2021], generalization to transformer- neural networks [Vaswani et al. 2017] is of great interest but widely open.
This paper establishes mathematical approximation and statistical estimation theories to predict and justify the scaling law between the generalization error and the model/data size for transformer neural networks. We consider regression of 3-Hölder continuous function f M - E where M is a d'dimensional compact Riemannian manifold isometrically embedded in IR After embedding the input x E M R to proper sequence, apply transformer network the embedded sequence to learn the function f. Our main results are on the statistical estimation and universal approximation theories of Hölder continuous functions M by transformer neural networks.
Statistical Theory: In Theorem | we consider the global empirical risk minimizer T,, from n i.i.d. training data ((rs, (x:))) given by
T,, arg minTer E. (T(xs) (xx))²
under properly chosen transformer network architecture T. We prove that, the generalization error of T, satisfies
BJJT, - fliia() f S Ö(Dd ズデイ2
23
where Q denotes the distribution of x, and Ô hides constants and log terms.
Approximation Theory: In Theorem 2 we construct a transformer network to universally approxi- mate ß-Hölder continuous functions on M with arbitrarily given accuracy e. Notably, the network is shallow, requiring only O log(d)) independent of the desired accuracy e to approximate f locally. This highlights& a major advantage of Transformers over feed-forward ReLU networks, which require O( (log(=)) (-)) layers to achieve the same accuracy.
In our proof, we embed the entries of x [x' "..",...,,""" PI E M into tokens such that the x''s appear in sequence. Our proof for the approximation theory explicitly constructs transformers to realize the interaction between different tokens efficiently via crucial Interaction Lemma 3 This lemma allows us to flexibly implement many common operations including addition, multipicction, and parallelization, and so may of independent interest. In our proof for the statistical theory, we calculate the covering number of our transformer network class, which is also of independent interest.
Neural Scaling Laws and the Intrinsic Dimension: Our generalization error bound in (2) predicts the following neural scaling law between the generalization error and the data size
2
Squared Generalization Error := T. flltt S n aaD, where ap = 2, + d'
(3)

---

with sufficient data. Our approximation theory in Theorem law between the approximation error and the network size N:
2 predicts the following neural scaling
Squared Approximation Error == infrer ||T f S NoaN, where aN 2
for a sufficiently large network class T.
Our prediction of the power scaling law is consistent with our own empirical observations, and those in Kaplan et al. [2020) and Biderman et al. [203). More importantly, our theory quantifies the power OD, in terms of the intrinsic dimension of data.
After establishing our theory we seek to validate it in practice by predicting empirical scaling laws for LLMs trained on natural language data. To test our predictions for the data scaling law, we pretrain a series of small (125 million parameter) LLMs on three
Experimental Validation on LLMs:
datasets [Gokaslan al. 2019 Eldan and Li 2023 Kocetkov et al. 2022]. We find close agreement (#0.02) between our predicted scaling exponent ap and the observed exponents åp. To evaluate our predictions for the model scaling exponent a,, we rely on publicly available scaling suites [Biderman ct al.] [023] Radford ct al., [219 whose intrinsic data dimensions we can estimate. We find our predictions are still close but less accurate for o.N. Finally, we carry out a series of ablations investigating factors impacting the estimated intrinsic data dimension d. For fixed dataset, we find the estimated is stable with respect to several factors including the model size, model embedding dimension, and context length[]
In summary, we make the following contributions:
A novel approximation theory for transformers approximating Hölder continuous functions d-dimensional manifold, requiring Ollog(d) depth independent of the accuracy
A novel computation of the covering number of our transformer network class. This is used to establish generalization bounds exponentially depending on the intrinsic dimension
Empirical experiments demonstrating our theory predicts data scaling laws for LLMs function of the estimated intrinsic data dimension d.
An empirical study several factors affecting the estimated intrinsic data dimension for transformers including model size, embedding dimension, layer depth, and context length.
We will present our main theory in Section numerical validation of our theory and the prediction
of neural scaling laws in Section 3 We will discuss related work in Section 4 and conclude our paper in Section 5] Our pre-training hyperparameters are given Appendix A The derivation of
neural scaling laws is presented in Appendix
B Our notation is given in Appendix and proofs
presented in Appendix and
Transformer Generalization and Approximation Theory
This paper establishes statistical estimation and mathematical approximation theory of transform- ers for the regression of Hölder functions on a low-dimensional manifold. We start by defining transformer neural networks.
2.1 Transformer Neural Networks
Definition (Transformer Neural Network), We define a transformer neural network as a compo- sition of functions of the form
T(x) Do D..B,,y o... o o (PE + E(x))
(5)
which is parameterized by
Lr: The number of transformer blocks B, in
m: The maximum number of attention heads per transformer block.
Levx: The max depth of the ford-forward layers per block.
WFen: The max width of the feed-forward layers per block.
'Code available at http://///..i.ccaaa/aa/////////e

---

dembdd The token embedding dimension.
D: The input dimension.
1: The number of hidden tokens.
A bound on the magnitude of network parameters.
We define each component of the composition as
x E R is the input.
linear embedding layer TR. Rdembaxl In this work we will always take E o where U E Rx and E' E [gdemsaal applied columnwise is fixed. We call embedded output B(x) the first embedding matrix whose columns are referred to as tokens.
PE e Relmbaxi is fixed matrix implementing the transformer positional encoding.
Transformer blocks B; Rdxt - Rdxi for E (1,..., LoT} which are residual compositions of multi-headed attention (MHA) layers MHA and feed (frwadfowward layers FFN acting token- wise.
A decoding layer D Rifemba + R which is fixed to outputting the first element of the last column.
We use the ReLU activation function (xx) max(0, x)) in the network.
For complete definition of the components of the transformer neural networks, we refer to Appendix D The transformer network may sometimes be written Ta which makes explicit the dependence on learnable weights 0. We can also define a class of transformer neural networks T of interest.
Definition 2 (Transformer Network Class). We define class of transformer networks
T(Lr, LuN, WYNN, 1 dembd, m. R, (oo To is in 5 with most attention heads in each block,
LEVN layer feed-forward networks with hidden width weeN. demod token dimension, hidden tokens
and have ||T (2> S R. |00| S
where [TolD><RR)) < R bounds the output T and ||0] bounds the weight magnitude To.
2.2 Assumptions
We consider a manifold M and the target function f M - R. with the following assumptions:
Assumption (Manifold). Let M be compact Riemannian manifold with intrinsic dimension isometrically embedded in RDD Because M is compact, there exists M > such that || S M for x E M. Additionally, we assume M has positive reach T >
Assumption 2 (Target function), The target function f :M - IR. is ß-Hölder continuous on M, for some 0 < 3 < 1 and Hölder constant H > 0, and in addition [|. [=M) < for some R > 0.
In Assumption T the reach [Federer 1959 Aamari et al. 2019
7 of M can be defined as
== (r > 0 : Ar # E M, E R such that
||x
w|
|y - u|| = inf || - w|]}-
Informally, reach is the smallest distance at which a projection onto the manifold is no longer unique. In practice this be used establish bound the number of charts covering the manifold.
2.3 Transformer Generalization Theory
Given training samples {(x;, fx:))) where {x are i.i.d. samples of a distribution Q supported on M, aim to learn approximation T, to f by minimizing the empirical risk (I) over

---

class of a transformer neural networks T T(LI, LEEN, WFEN, 1, dembd, m. R. K). The corresponding
generalization error given by
EITT f((2(0) = SM ((x))
(6)
If M and satisfy Assumptions aad we prove the following generalization error bound.
B S 1, d. E N. M and f satisfy Assump- tion and respectively. Given training samples {(r4, (x:))))== where {xr))==1 iid. samples of a distribution Q supported on M, if we use the transformer neural network class TLLT, LFFN, WPFN, L, dembds m, R, x) with parameters
Theorem 1. Let M, R. H 0,
LT O LEFN = ((lg((n)) WFFN = 0(),, 1= Odn 1 dembd = 01), m = 00(n (idn,, R k= Od n 25+2
24
in the empirical risk minimization ( where O hides terms in CM (the number of charts), D, H M, then the empirical risk minimizer Tn given by ① satisfies
f(x)) dQ s ÓDd 2344 E L (Ix())-f(s))
2344
where Ô hides logarithmic terms in n, and linear terms in CM-
Theorem 1 is proved in Appendix via bias- decomposition. The bias represents the approximation error of by transformer neural networks, and the variance represents the stochastic error in the parameter estimation of transformer neural networks. To quantify the bias, explicitly construct a transformer neural network to universally approximate 3-Hölder continuous functions on M, to be detailed in Section 2.4 The variance is bounded by novel calculation of the covering number of the transformer network class used in Theorem
2.4 Transformer Approximation Theory
Theorem 2. Let M, r, R, H 0.0 e N and M satisfy Assumption 7 For any e E (0,1), 1), there exists a transformer neural network class T(Lr, LANN, WPEN, I, dembd, m. R, x) with parameters
Lr = =(log(d)) LANN = 01 WFFN = 0(1, 1= Ode
demba = 01),, m = Ode )), =)) Od- 24
where O hides terms in CM. D, D.H such that for any target function f satisfying As- sumption if the network parameters @ are properly chosen, then the network yields a function Ty E T(
LeNN. WPFN. I, demba, m, R, k) with the approximation error
Tgg fl(.=(M) S
Theorem is proved Appendix E.2 In our proof, we decompose (x) as sum of terms over local neighborhoods U,,..., UCm M covering M. Approximations on overlapping neighborhoods containing will then be combined via partition of unity (PoU) J which subordinates (U.).M. This will give us the expression f(x) ICm fn( (I) with fn fpn M - RR On each local neighborhood Un. we project the input x E M C RR. the tangent coordinate in [0, 1jd. This will give us the following local decomposition of the target function:
-x)=II> Fn on (x)
where F, = f 10, + R and o, We then construct transformers to approximate the f.. on. 1u, components in (7). A diagram of the constructed transformer network approximating f M - is given in Figure L The following key lemma is used to efficiently approximate each low-dimensional function fn on d-dimensional coordinates.
[0, 1]d is projection onto the local tangent space.
5

---

H1
H2
Ha
Joy
Ti
1u
Mel) Laee
f(a))
Legand
A -ss
Chart
decerninet
f Kuy
TayLor
Approrieation
-Patring
Figure Diagram of the transformer architecture constructed in Theorem 2 computes approx- imations of f(x) on each local chart Un S .M by first projecting to the tangent coordinates in Rd via on(r) (x)) and then approximating f(x) with local Taylor polynomials. A shallow uut-network computes indicators 10, each local chart in parallel. The results of the two sub-networks are then multiplied together and summed to produce the final result. Here H; denotes the embedding matrix before the ith transformer block B;.
1. For any e (0,1), there exists a transformer neural network class TLLT, LEEN WFFN, L, dembd, m. R, K) with parameters
Lemma Let H O, and <351.
LT (lo((d)) LAEN 0(). WEEN = 0(),, 1 Ode
dembd = =0(1), m = o K == od=
where ((.) hides terms in Hj. such that, for any 3-Hölder continuous function f [0, 1]s with Hölder constant more than H and llf (ju,1)*) S R, if the network parameters 0 properly chosen, this transformer network yields a function To T(Lr, LYrN, WYENs demba, m, R, K) such
that
[Tg -f11 Se.
Lemma proved in Appendix E.1 We develop novel lemma Interaction Lemmn implementing highly-spane pairwise interaction between two arbitrary tokens h4, ht,, as crucial architectural building block allowing us easily implement more complex functions, architecture serialization, and parallelization 77) This result highlights a distinct advantage of transformer function approximation over ReLU function approximation (Yarotsky] 2016]: transformer network only needs constant O( (d))(d)) number of layers to approximate J [0, 1j + R independent of the desired accuracy In contrast, the depth of ReLU feed-forward networks is in the order of log(e-1) Yarotsky 2016 This is desirable from an empirical point view, where wider networks instead of deeper ones tend
to achieve superior performance [Kaplan et al. 2020 Lee al. 2020
3 Predicting Empirical Scaling Laws and Validation on LLMs
Our theory provides practical insights by predicting neural scaling laws for transformers, as given in (3) and (4), by explicitly quantifying the data scaling exponent ap and the model scaling exponent N' as a function of the intrinsic dimension (ID) If we assume the language modeling objective has Lipschitz regularity such that between the squared generalization error and the data size n, as given in (3). with ap 2ー7 and
in Assumption 2 then Theorem predicts the scaling law
the model scaling law with exponent given by a 3- For full derivation refer to Section We will observe how well our theory predicts these exponents both by pretraining small models from scratch and evaluating existing open-source model suites (Biderman et al. 2023
In the following, we denote ap and axx as the scaling exponents predicted by our theory, where we numerically estimate the intrinsic dimension of data, denoted by dp. The empirical exponents

---

Openidatiee (is) lan st Oagi number of trait cumple
Bgrade Sct dagn velizer vs lis number of tran sample
Try Storic (og) val et (agi number frsh camplex
0.2
Dropical 4,m0.222
Dropiical fl: 6ym0.226 228
Emprical 22m0
Theers do 000200000000000 15.1)
Therg: Rp 16.23)
Thenry Ra-2.32 (4.24)
0.5+
422
Org1 14 BOCK
Orgg VO 1000
040
-055
300
1073 1.2
6G2
820
8.C.
9:20
K32 K.0
3022
6.0
200 Mumn
Figure 2: Observed and predicted data scaling laws on OpenWebTex. The Stack-SQL, and Tiny Stories pretraining datasets. All estimates are close (=0.02) and appear to reflect varying levels of pretraining data complexity. Note: åD denotes the empirically observed data scaling exponent and ap denotes the theoretically estimated exponent.
denoted by á and ox. To obtain the data scaling exponent &p. plot the test loss (comparable to squared error) versus the data size n in log-log scale, fit the log-log curve with a line, and then obtain åD from the magnitude of the slope. The model scaling exponent dv is obtained similarly.
Estimating the ID of Text To predict scaling exponents, we must first estimate the intrinsic dimension of our pretraining dataset D. While we can do this directly for image datasets (Russakovsky et. 2014] Pope et al.] 2021], we cannot do this directly for textual datasets. Instead, we will estimate the intrinsic dimension of the input data by estimating the intrinsic dimension of token embeddings. Specifically, we will represent each input token with its corresponding final final-layer token embedding. Given pretraining test set Dust we embed random 1 1024 length subsequence from each document D& E Dust. We then randomly sub-sample 32 final-layer tokens from the embedded subsequence and shuffle together all the embeddings. To estimate the ID of the embeddings the Maximum Likelihood Estimation ID algorithm [Levina and Bickel| 2004] [Pedregoaa et al.] 2011] with K = 20 neighbors. We split the sampled embedding tokens into batches of 4096 and the MLE estimator on each batch, averaging together for the final result. Unless otherwise specified, we embed each document D& E Prest using a 125 million parameter model M with LT 12 layers and embedding dimension dembd 768. We first pretrain M on the full Drain for 200, 000 steps or until convergence.
Intrinsic dimension predicts the empirical data scaling exponent &D To validate our prediction of the dataset scaling exponent an pretrain a series of 125 million parameter GPT-style LLMs on three different datasets: Open WebText [Gokaslan et al. 2019), the SQL portion of The Stack We train across three orders of dataset size to fit scaling laws. Detailed hyperparameters can be found in the Appendix [A] We report the observed scaling laws in log scale in Figure [ In addition, we plot our predicted test loss whose where do is the our estimated intrinsic dimension.
[Kocetkov al. 2022]. and Tiny Stories [Eldan and Li 2023
slope is given by OD
2+dp
Empirically, we find all three datasets produce nearly log-linear laws whose exponents lie between 0.1 < âD < 0.15. Tiny Stories has the largest exponent, indicating the fastest rate of convergence, followed by the SQL dataset, followed by Open WebText. This matches our rough intuition, since Tiny Stories is synthetically generated dataset with less complexity than the other two datasets and thus easier to learn. The predicted exponents a generally over-estimate å but otherwise closely match up to +0.02 absolute error. Additionally, the predicted a' reflect the previouly mentioned differences in complexity of pretraining datasets. In particular, Tiny Stories has a smaller estimated ID than both Open WebText and SQL, resulting in a larger predicted an as desired.
Predicting empirical model scaling exponent ón with intrinsic dimension To validate our
predictions of the model scaling exponent o.y 2 we evaluate two model scaling suites: GPT2
Radford et al. 2019) and Pythia [Biderman et al. 2023). We refer to Kaplan et al. (2020) for GPT2's ăy and estimate n& using WebTett as a proxy for GPT2's pretraining data. We compute ON for Pythia by evaluating each model on The Pile's test set [Gao et al.) 2021]. We also estimate dp on the publicly available pretraining data to predict ax. The results are reported in Figure 3 Our predicted ax under-estimates the empirical âx. We conjecture this to be due to number of factors including possible under-training of the largest models and the intrinsic entropy of the data distribution.
7

---

9o42 model size va, vell loss
pyll model size va, val loss
0.34
0.55
0.32
0.50
[ Vall Vall
0.30
0.65
0.29
0.20
0.40
021
truth
Ground bruth
Empincal ht. dy 0.073
Empirical 1it: 6u 0.068
Theory: my =0 (ID 15.11
0.20
heory: -0.129 (ID 15.56)
55
6.0
2.5
8.1
0.6
88
60
9.
(log) Medel dize
lingt Madel sipe
Figure 3: Observed and predicted model scaling laws in model size GPT2 and Pythia scaling swites. aN denotes the empirically observed scaling exponent, and & denotes the theoretically predicted exponent. Note: we estimate a,v for GPT2 using WpenWebText.
Estimated DD Model Else
Extimated DD Enbedding dimession
17-
34
2.3
22.8
2.1
Layer
Openilleb lengsh
17
12.5
14.5
14.0
13
600
Layer
bege
Figure 4: Top left: Estimated ID vs. number of parameters. Top right: Estimated ID vs. the embedding dimension. Bottom left: Variation of estimated ID across model layers. Bottom right: Variation of estimated ID across context position.
Ablating the impact of model architecture on the estimated ID Practical application of our theory relies on a good estimate of the intrinsic dimension. However, there are many factors potentially biasing our estimate. Of particular interest is the embedding model's embedding dimension, depth, context length, and number parameters. We ablate these factors in Figure plotting estimated ID against each factor.
Overall, we find the estimated ID is fairly stable across each factor. As the number of parameters increases, the estimated ID of The Pile slightly increases from 15.56, via 410 million parameter model, 20.02 with a 12.8 billion parameter model. ID on OpenWebTest behaves similarly when increasing the embedding dimension, increasing from 15.56 when demba 768 to 18.68 when dembe 1536. When fixing a single model, we find the across intermediate embedding layers small initially but then increases and decreases again, stabilizing around the ID of the final layer. We observe that the ID appears to inversely correlate with sequence length, decreasing from 15.86 for very short sequences to 12.9 for sequences around 1024 tokens.

---

Predicting aN from ap (and vice versa) without estimating ID Above we estimated ap and O by first estimating the intrinsic dimension d for a model's pretraining dataset. However, estimating may not always be possible when pretraining data is not public. Alternatively, we can predict o in terms of o, (and vice versa) without ever needing to estimate d:
2
2/2
ON
0DD
1 1-ap 0D ON
2+d
2
+1
ON +1
See Table | for ID-free estimations of empirically observed exponents in the literature (Sharma and Kaplan 2022 Hoffmann et al. 2022
GPT-2
Chinchilla
ON 0.076
oD 0.070
óN = 0.34
= 00.25
åDD 0.095
ON 0.106
âD 0.28
oN = 0..3
Table I: ID-free estimation of scaling exponents for GPT-2 and Chincilla.
4 Related Work
The theoretical properties and advantages of transformers have been studied from many different
perspectives [Jelassi et al. [022] Zhang et al. 2022 Bai et al. 2023 Pérezz et al. [002] Sanford et al.
2024]. Most related us are Yun al. [2019] Edel man al. 2022 Wei et al. [2022] Takakura and
Suzuki [023 in which transformers were studied from an approximation viewpoint. The work in Yun
ct al. [2199] proved that transformer models are universal approximators of continuous permutation
functions with compact support, while the network size suffers from the curse of dimensionality (the number entries in the input sequence). Takakura and Suzuki [2023] studied the approximation and estimation ability of Transformers as seq-to-seq functions with infinite dimensional input, where anisotropic smoothness avoids the curse of dimensionality.
equivariant
In the applications of Large Language Models (LLMs), empirical findings have demonstrated some correlation between the performance of transformers and the low-dimensional data structures
|Razzhigaev et al.) 2023 Min et al.) 2023 Aghajanyan et al. 2020 Pandey] 2024). |azzhigaev et al.
2023] investigated the intrinsic dimension of embeddings transformer architectures, and suggested
an encoder and decoder embedding property. Most similar to our work is Sharma and Kaplan [2022
which demonstrates an empirical connection between neural scaling laws and the intrinsic dimension of data. While they briefly discuss predictions for LLMs, their theory works best for predicting student-teacher model setups and image classification tasks which seem to enjoy more regularity (and faster rate of convergence) than language modeling. Despite these empirical findings, we are not aware of any rigorous theoretical justification connecting the scaling laws of transformers with the intrinsic dimension of data. Our paper complements this line of research with statistical estimation and mathematical approximation theories which well-predict the behavior observed in practice.
Conclusion
Conclusion This paper establishes statistical and approximation theory results for transformers approximating Hölder continuous functions on low-dimensional data manifolds. The resulting bound on the generalization error suffers from exponential dependence only in the intrinsic dimension d. The constructed approximations of low-dimensional functions are shallow, requiring only O( (o)( layers independent of the desired accuracy. We demonstrate this theory is accurate in practice by predicting scaling laws in both model size and data size for LLMs trained on natural language datasets. We pay careful attention to the sensitivity of the estimated intrinsic data dimension, finding it is relatively stable with respect to several relevant hyperparameters.
Limitations and Broader Impact One important question unanswered by this work is how the intrinsic data dimension may affect the computational scaling exponent ac- Future work may investigate this direction. Additionally, our empirical experiments make the simplifying assumption that the underlying target function possesses Lipschitz regularity (3 1). Better estimates of the correct regularity would likely improve the accuracy of our predictions. More broadly, our work improves fundamental understanding of transformer-based L.LMs and improves our ability to theoretically and safely predict future capabilities.

---

References
Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasser- man. Estimating the reach of manifold, 2019.
Armen Aghajanyan, Luke Zettlemoyer, and Sonal Gupta. Intrinsic dimensionality explains the effectiveness of language model fine-tuning, ArXiv, abss2001.13355, 2020. /ttpttss://ppp
semanticscholar org/ Werg/CorpusSD.... 229371560
Jean-Yves Audibert and Alexandre Tsybakov. Fast learning rates for plug-in classifiers. 2007.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint urXiv:1409.0477 2014.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. ArXiv, abs/2102.06701, 2021. URL https://api www.nticccooolla..... httpps///ppl.seemniiiccc......
org/
CorpusID:231918700
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection, 2023.
Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O' O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. Pythia: A suite for analyzing large language models across training and scaling, 2023.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. Advances in neural information processing systems, 32, 2019.
Minshuo Chen, Haoming Jiang. Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep relu networks: Function approximation and statistical recovery. Information and Inference: A Journal of the IMA, 11(4): 2022.
John Conway and N. Sloane. Sphere Packings, Lattices and Groups, volume 290. 01 1988. ISBN 978-1-4757-2018-11 doi: 10. 11007/978-1-477--0111
Biraj Dahal, Alexander Havrilla, Minshuo Chen, Tuo Zhao, and Wenjing Liao. On deep generative models for approximation and estimation of distributions on manifolds. Advances in Neural Information Processing Systems, 35:10515-10628, 2022.
Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. International Conference on Machine Learning, pages 5793-5831. PMLR, 2022.
Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english?, 2023.
Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3): 418 491, 1959.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The pile: An 800gb dataset of diverse text for language modeling. CoRR, abs/2101.00027, 2021. URL https://arxiv.orge hbsp:/ab/2200 /
Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex Openwebtext corpus. http
2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances neural information processing systems, 27, 2014.
10

---

Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. 2013 IEEE international conference on acoustics, speech and signal processing. pages 6645-6649. leee, 2013.
Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international conference on robolics and automation (ICRA), pages 3389-3396. IEEE, 2017.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint urXiv:1712.0000
2017.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models, 2022.
Samy Jelassi, Michael Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. Advances in Neural Information Processing Systems, 35:37822-37836, 2022.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001 /08861, 2020.
Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification, 2019. URL https:t::///rr http:/axxvv...rrrrg../ www.aa/s....e... 03599
Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Carlos Muñoz Ferrandis, Yacine Jemnite, Margaret Mitchell, Sean Hughes, Thomas Wolf, Dzmitry Bahdanau, Leandro von Werra, and Harm de Vries. The stack: tb of permissively licensed source code. Preprint, 2022.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent * Journal of Statistical Mechanics: Theory and Experiment, 2020(12): doi: 11-11088/77225556//aaao60 11/11/422-54688 abc62b
124002, December 2020. ISSN 1742-5468. //dx.dor wog.dooo..oooooooo 10.
URL http
Elizaveta Levina and Peter Bickel. Maximum likelihood estimation of intrinsic dimension. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004. URL https::/ppocceedinii
neurips.coomm http//pppr.iilll/pp/e/////00////
Paper pdf
Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on cow-dimensional manifolds using convolutional residual networks. In International Conference on Machine Learning, pages 6770-6780. PMLR, 2021.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35, 2023.
Zeping Min, Qian Ge, and Zhong Li. An intrinsic dimension perspective of transformers for sequential modeling, 2023. URL httptts://pperreeiieeee htt.:///e//ppppooooeeeeeee///eea
Riccardo Miotto, Fei Wang, Shuang Wang, Xiaoqian Jiang, and Joel T Dudley. Deep learning for healthcare: review, opportunities and challenges. Briefings bioinformatics, 1966):236-11255 2018.
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(174): 2020.
11

---

Kenta Oono and Tajji Suzuki. Approximation and non- non-parametric estimation of resnet-type con- volutional neural networks. In International conference on machine learning, pages 4922-4931 PMLR, 2019.
Rohan Pandey. grip predicts data-dependent scaling laws, 2024. /tt.htttss://arvvv.orr/// 2405. 16684
Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Phillip E. Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact learning. ArXiv, abs/2104.08899 2021. URL https
Orgg/orpusID::: (D:.ppps1::23226655533033 233296562.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75): 1-35, 2021. http::/tt:////l http://rrrrgpppppeee/eaee
302 html
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019. URL BtRLhttps: /ttp///tppe///p....ee.mmmmm http://ppp..emmmmicccccol.oa.aaa org/
CorpusID:160025553:
Anton Razzhigaev, Matvey Mikhalchuk, Elizaveta Goncharova, Ivan Oseledets, Denis Dimitrov, and Andrey Kuznetsov. The shape of learning: Anisotropy and intrinsic dimensions in transformer- based models. ArXiv, 00//2311.05928 2023. URL httpp::/papl..emannicccccooo semanticschholllr org/
CorpusID:2651226033
Jonathan Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. arXiv preprint arXiv: 19f.:2/999..677, 2019.
Sam Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2333-2333 2000.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Li Fei- Fei. Imagenet large scale visual recognition challenge. CoRR, abs/14099055 2014. URL
hwtp://wwwrrrabb/////eaa/ 0575
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and log- arithmic depth. ArXiv, abs/2402.09268,, 2024. URL
org/
CorpusID:267657800
Johannes Shhmidt-Hieber Nomparametric regression using deep neural networks with ReLU activa- tion function. The Annals of Staristics, 48(4):1875 1897, 2020. doi: 11111/111--O11100 URL
https://doi. org/ 1214/19-A081875
Utkarsh Sharma and Jared Kaplan. Scaling laws from the data manifold dimension. J. Mach. Learn Res,, 23(1), jan 2022. ISSN 1532-4435.
Yang Song, Jascha Sohl-Dickste Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint U. 2020.
Shokichi Takakura and Taiji Suzuki. Approximation and estimation ability of transformers for sequence-to-sequenee functions with infinite dimensional input. In International Conference on Machine Learning, 2023. URL uttts:t::://ap semanticscholarr orgg/oorpusD::28957777
Joshua B Tenenbaum, Vin de Silva, and John C LLngffrd. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):219-23320 2000.
Loring W. Tu. An Introduction to Manifolds. 01 2011. ISBN 97--1-441--711111 1-44-993797
12

---

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, 30, 2017.
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: case study on approximating turing machines with transformers. In Koyejo, S. Mo- hamed. A. Agarwal, D. Belgrave, K. Cho, and A. Oh. editors, Advances in Neu- ral Information Processing Systems, volume 35, pages 12071 Curran Associates, Inc., 2022. URL https::/pproceedings neurips....pppp.... cc/paper fi ptt.e//pape//222/111122 4ebf http:4//S..eeeeaaaaaaaaaaaaaeeea www.appppparraaaaeeeeeeeeeeeeeep
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural networks the official journal of the International Neural Network Society, 94:103-1,4, 2016. URL
https://api. www.eticscooooseeeee.e ooooo////ooooooooooooooo Corpusup 4266133 426133
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are
transformers universal approximators sequence-to-seequene functions? ArXiv, abs/1912.10077,, 2019. https://:
20944444100
Yufeng Zhang, Boyi Liu, Qi Cai, Lingxiao Wang, and Zhaoran Wang. An analysis of attention via the lens of exchangeability and latent variable models. arXiv preprint 21X2::2212,,485,,, 2022.
13

---

A Pretraining Hyperparameters
Architecture hparams
num layers
12
num attention heads
embedding dimension
768
context length
1024
Optimization hparams
Optimizer max Ir min Ir Ir schedule warmup steps max steps global batch size
AdamW
6e-4
6c-5
linear warmup + cosine decay
2000
200,000
1920
Table 2: Default hyperparameters for all training jobs. All training was done on four RTX 6000s.
Table 2 lists the default hyper-parameters we use for pretraining. All training was done on four RTX 6000s.
B Deriving Lanugage Model Scaling Laws from Statistical and Approximation Theory
B.1 Squared Regression Error
First we extract bounds scaling laws in the case of regression squared error. We have the bound from the proof Theorem !
J. Tn)))
Ddft
Ö(6²
where e is the approximation error such that
[l. (()) <c TET
inf
Let the model size of a transformer E T be N Le (dP (demba (3m + LPEN)) = log(d)(25(3c log(e "))) ŌE $). Write the squared generalization error
Lag (N, / Mm (x))))
Then
Tag (N, ( Ddft = O
In the model scaling regime, when data is plentiful, we have N << N # which implies the behavior of (Ng n) is dominated by N This gives us the model scaling exponent as
23 d
ON
For the data scaling exponent a we will choose N to balance both error terms. The will predict how data size and model size should scale together to achieve a minimal generalization error. We should have
28
N
28+4
N
N n
14

---

where x denotes in the same order. Substituting this into the error bound gives
Lg n) 50
N Ö कमंं 4) Ö( ズデ42 )
20
n
which gives rise to
23
a 23 + d
B.2 From Regression to Classification
After establishing statistical and approximation theory for transformers for regression, we now seek to apply theory classification. In language models, the next-token prediction task is a multi-class classification problem, where transformers are trained to predict the probability of the next word out of large dictionary.
For simplicity, we consider binary classification here. Let (z, y) be a random couple taking values in M x {0, }} with joint distribution P. where M is manifold satisfying Assumption I Let Pa be the marginal distribution of æ. Here x stands for the input feature and y is the corresponding label. The classification goal is to predict the label y given the value of x. A decision rule is given by function : + {0, 1). The performance of a decision rule f is measured by the misclassification error
R(f) Ply # f())).
The Bayes decision rule has the form
fx)x = 1 [n(2) 2 1/2]
where 1 denotes the indicator function and
T7x)) = P 1/x)
(8)
the regression function of y æ. For binary classification, the goal is to estimate the probability function ()))) If is a 3-Hööldrr function satisfying Assumption [] our approximation theory in
Theorem gives rise transformer neural network njo such that
||m 7])..((M Se
(9)
for an arbitrary small > 0.
We next consider the plug-in estimate of n/ Audibert and Tsybakov 2007]: So(x) = {no 2 1/2]. The excess risk of the plug-in estimate so is
E(fo) = R(fe) R(f*)
P(y # fo(x)) - P(y fx)))
-P(y = fx)) 10--PP -P(y fe(z))
(1)) (1-v()) n(x))
-1(fo(z) = -1)n(r)-
(1-n(z))
E. [[2)(2)) +
We next discuss how the regression error in 9 impacts the excess risk E(fa). For classification problems, the classification error depends on how well the conditional probability nf is estimated, and how many points are close to the decision boundary. Following Audibert and Tsybakov 2007]; ) assume the following margin condition: There exist eM and 7 O, such that for any t 0,
(x < 17xx) - 1/2 < t) < catt".
(10)
smaller y means more samples cluster around the decision boundary with a higher likelihood of
falling into either class. This is not expected to be the case for natural data, where for most samples it
easy to tell to which class they belong [Kim et al. 2019 Figure 2]. As a result, we assume 7 2
Under the margin condition in TO we follow Audibert and Tsybakov 2007 to decompose the excess risk E(fe) such that for any 8 0:
{(fa) = E., [[2n(z) []](.f((z) + (())) -
< 8H
E. [12n(z) - [()))(()
87
< ())((()())) 1/2] < 0) 2E, (Im [ ((m)) - n(x) > 8)1
< 22 + 2E, [ln((x) - ((=) (1)0(2) - n(z) > 5)].
(11)
15

---

Plugging the regression error in 9 to the excess risk bound in 11 with å = e, we obtain
{(fo) S 20 1+7
When the margin assumption satisfies y 1, the excess risk bound becomes
{(fo 20
which demonstrates a connection between the classification risk bound and the squared regression error for the y function in (8). This argument partially justifies the connection between empirical neural scaling laws in large language models and the squared regression error. We will leave rigorous mathematical argument as future work.
B.3 Cross-Entropy Based Language Model
In practice, language models are trained and evaluated using cross-entropy loss. We consider the next- token prediction language models. Per-sample (token), language models are trained to minimize the multi-class cross-entropy loss over large number of classes/tokens:
V
La((n) -
Σ 1 y= In(P(y)x)))
(12)
where V the vocabulary size of the model (number of classes), yg the ground-truie truth label of z;, ly=y; is the indicator function for the event y y, and P(y[z) is the conditional probability of labels given æ. For the next-token prediction, transformers are trained to estimate the probability function Ply(æ), and the next token is predicted to the word with the highest probability. The test loss is evaluated using cross-entropy on test data. We will leave the error bound on the cross-entropy loss future work.
C Notation
H will represent the embedding matrix a transformer and h; will represent the ith token (column) of the embedding matrix. hy will denote the jth component of the vector hŞ- || Il P > 1, will denote the yth norm of vectors, and || Iln.g will denote the component-wise matrix norm. For matrix
A E mx*, || C (2 |Ag ())))) In particular, we denote ||A||s = ||] and ||l|| | 1 for matrices. || (|L-()) will denote the TPP norm of function U C RDD. Neural network blocks will always be bolded. Sometimes neural network blocks will also be sub-scripted with their corresponding vector of weights 0. We use |0]|oo to denote the largest magnitude of the weight parameters. However we will often omit and leave the dependence as implicit. In many places, we will also write ONN denote the weights for neural network NN. e; will denote the ith standard basis vector where the ith component is 1 and all other entries are 0. will always denote the ReLU activation. B(x, r) denotes the Euclidean ball of radius r centered at æ E R?,, For a vector he, h. E -i-i will denote the vector such that (h fij = h i.c. the contiguous components of he from j....
D Details about Transformer Neural Networks
We have defined transformer neural networks in Definition Some detailed definitions are given below.
Definition (Transformer Block). We define transformer block B as residual composition of the form
B(H) = FFN(MHA(H) + H) + MHA(H) + H
(13)
laking input embedding mairix H E Rederaai and MHA is multi-header attention layer and FFN is a feed-forward layer. To define the multi-headed atlention layer we first define the attention mechanism.
16

---

H
FFN
H1.5
MHA
H1
Figure 5: Diagram of transformer block.
Definition 4 (Attention).
(H, = (Ho(()))=V
(14)
where Q, K, V E RRdemra X demba are referred to as the query, key, and value matrices and o(x) max(0, x) is the ReLU activation function. Often we will omit the dependence of A on Q, K, V. We note it will be convenient to write the action of on the ith column h2 of H as
A(h,) Σ oh,
(15)
This allows interpret the ith column of the output of A as linear combination of the values weighted by the interaction of hith query and the hith key. Multi-headed attention can then be defined as
MHA(H) = (concat,, (V, (.KK
(16)
where the output of each of j E {1, (L...., M} attention heads is concatenated and Wo Remndd xmdembd Frequently we will simply take Wo to be sum that
m
MHA(H) Σ (H)
(17)
We also formally define the feed-forward layer FFN:
Definition 5 (Feed-forward Layer). A ford-rorwwrrd layer of depth LEEN and width WFFN is of the form
(F WLex ( (Wi
+ b1)... + bLON-1) + bLAN
where W2, ..., W Wons11 Bedemdd Xdenad, W1 E Wers W Xdembd WLnx Relembaxwaas bi,..., bLaws Redemdd and the activation is ReLU. Note, each feed-forward layer is applied tokenwise to an embed- ding matrix H.
We can also define class FFN of feed-forward networks:
17

---

Structured Token
Dynamic/Mutable
Data terms
Static/lmmutable
Interaction terms
Constant term
Figure 6: Diagram of a structured token. The first two rows contain mutable data used to compute the target function. The remaining rows never changed after initialization.
Definition 6 (Feed-forwart Network Class).
(FNN WFFN) {FFN, FFN, is feed-forward network with weights 0 with most LeFN layers with width wPex).
Sometimes we may omit the dependence of F WIrN- In these cases We similarly define multi-headed attention and transformer block classes:
WTTN dembd-
Definition (Multi-headed Attention and Transformer Block Classes).
MH.A(m) =
{MHAgl MHAg is a multi-headed attention network with weights 0
with at most attention heads.
B(m, LEPN, WFFN) = BBo | Bg is transformer block with weights a m-headed multi-headed attention layer, and LypN deep feed-forward layer with width WFFN).
As with F, we may sometimes omit the dependence of B on WyeN- In these cases we take WYFN = dembd- We parameterize the class of transformer neural networks T as Definition 2
Lastly, our constructions will rely heavily on a particular structuring the tokens/columns in transformer's hidden states. The first two rows will contain mutable data used to compute the target function. The remaining rows will be immutable, containing positional/interaciion vectors allowing us to uniquely identify each row and constant term serving kind of "scratchpad". See Figure for a diagram.
E Proof of Transformer Approximation Theory
We first prove the approximation theories in Section 2.4 We first prove Lemma 1 in Section E.1 and then prove Theorem 2 in Section E.2
E.1 Proof of Lemma 11
Proof of Lemmal 7 Fix f [0, 1]d R and e 0. We aim to approximate f efficiently with transformer T E T(Lz, LIIN, WFeN, I, dembe. m. R. k). We will proceed similarly to Yarotsky 2016) by approximating f locally with piecewise constant functions. First, we partition the domain uniformly into blocks indexed by n E (1,..., Nj for some N 2 1 with U, = fa [), Vi E n' {1.... d), Jx' N - S - In this proof, we use x' and n' denote the ith coordinate of a and respectively. Then we construct partition of unity (PoU) via
d
n²
(x) = II 1b 3N
(18)
N -
18

---

with the trapezoid function u RR -+ R as
1
| S
(xx)
-1-1a]
1 1 |t| S2.
x
We can now write our approximation for f as
f(x) = Σ (n(
where fa = f(x)) with zn being the center point of Un. This yields the following approximation error:
sup Il (0.1)=
f(() f(x))
xE(0,1]
sup
fx()
E
fndn(z)
=E|o,1j
RJ(
sup
Σ
(())
Σ fndn(z)
=c|o.1]
nE(In.,,N]
DE NJ(
= sup =c I]]
Σ
(f(x)-
- fnl
nE NJ.
sup =E|0,1]
Σ
15(z) fml
IS
Σ
Hy||æ In 12
sup xEJ0,1]
N- NS -
< sup =E oE(0,1]"
2d
max
Hy|1æ - 2nll2
|z' N
d
2dd Hs
2HH
sup xE|0,11
(N 1)5 (N-1)
Thus we can control this error simply by increasing N. suffices pick N d( #e) + to obtain an error bound.
We next construct an approximation f with transformer neural network T. In fact we can represent/ ff exactly transformer neural network.
At a high level, we will proceed by building up each on as an accumulated partial product p.. in parallel over transformer blocks. Each block will use at most dembad embd attention heads. Each head will be responsible for multiplying two partial products. Conveniently Ón can be exactly implemented with two-layer FFN and applied column-wise each term. The constant terms will then be multiplied in and summed at the final layer to compute the output.
Step 1: Embed the input Now fix input E I First augment the input, via concatenation, with sequence of Os: ON forming input x' R Nx (note this is linear operation). We can then construct linear embedding layer [1, 0, 0,0,0, E IBdemba resulting in the input
embedding matrix H E Rdeesa (d+ d) of the form
x rd
O On
Ndd
0 O Ova
ONe
0
O Ond
0
Ova
ONed
0
O
Ona
Oxda
19

---

where dembt 5. To this we add fixed positional encoding PE E Re x (d+ NN4 producing the first hidden embedding matrix
r
x
O Ndd
O and Onda Ia+dN+Ned
0
Nd
H1
I1
where I; E R² represents interaction term determining when each token embedding will interact with another the attention mechanism. can set 7, = (cos(? () (f where I is the number of hidden tokens. Note, this type of positional embedding commonly known the sinusoidal positional encoding and can be visualized as rotations of the unit vector éj around the first quadrant of the unit circle.
Step 2: Pre-compute (3N - -> Now we pre-compute the terms (3N (x* 2-1 from which
construct partition of unity. We define st 3 1)(x² x for 1 S i d, S j S N. We know (3 1)-) can be computed exactly with two-layer FFN. So all must do is prepare the input x² N-T- We will do this with transformer block B The results will be stored in token columns ha+1, .... ha=Nd-
Define B ((Nd, 7) i.e. B1 has a multi-headed attention layer with Nd attention heads and feed-forwe forwadd layer with depth 7. We will construct each of the ijth blocks using the Interaction Lemma 3 We may choose data kernels
dataa
0
0
0
1
E
R
2xdemad
Kdate
1
0
0
0
0
R
22xambd
0
0
0
0
0
0
0
N-1
1
so that for the token embedding hig hatiedtjs we have
Aig(hig)
o (Qighis Kight)
a (1 data hij. Kd hx) + (ofghes K7hh) O)e2
k=1
Σ ahh j-1
+1 1 (Q/yhiji K2,haa C)e2
N-1
1-1 N-1
j j-1
= oa
1)ez (x'
+ 1)e2
N-1
where we can choose token hy to only interact with token h4 Otherwise we have Ag (hr) = 0 for hy A hag. Further, the weights of OA., of Aij are bounded such that ||0A,, 1l (12) according to Lemma
The added output of the multi-headed attention layer is then HI. = MHA1 + H and is given by
x
zd
Nd
...
Dad Owed Io+Nd+N4d
0
0
x
+c
xd
1
H1.5
I
20

---

It remains to subtract the positive term = 1 and then apply vb for the tokens d 1,..., d + dN while leaving the other tokens untouched. Define
1
0
0
+
M
0
-1
0
0
M
W1
0
0
1
0
bj = 0
O
0
0
1
O
0
0
0
0
-M
0
1
0
0
-
M
W2
0
0
b2 = O.
0
0
0
Here Wi shifts values in the second component of each token to the first and subtracts The second component is negated to be subtracted from H1.5- I and the last component are preserved. A large positive number removes M after the activation is applied. We can construct a two-layer network FFN1 to apply ii to the first component each token h4. In tokens hds ..., ha+ Nd this produces the desired Siy terms.
2/ |ooo is added to prevent negative terms from getting crased by ReLU. W2
Now we simply must ensure we zero-out changes to tokens outside the range d + 1..... + Nd. Via Lemma we can construct a two-layer weeward gating network FFN, such that FFN; for i < d and FFN2(h+) ) is zero except for the last three rows when / >> + d.N. We can again invoke the same lemma to produce FFN,, E F2) such that FFN, (ht) = he when d and zero except for the last three rows otherwise. Applying FFN, and FFN; zeroes out tokens outside
h
+ 1,.... d + d.N while preserving the rest. Finally, we define the last layer
0
0
0
1
0
0
W
0
0
b7
0
0
0
0
which zeros out all except the first two components. This produces the next embedding matrix H2;
x
r
51.1
Sd,N
aad N Id 1
0
ONd
H2
I
Step 3: Building up partial products Now we can start construction of the partial products for each patch Φn. n E (1, NJ For fixed patch n, write Pr,k, to indicate the ith partial product of 2 terms. Formally, Pa,k, - 112:-1 Pr,A-1,21 with Pa,1,i -i,n' where St. <333 - (a' )) and n [1,... 1 < log, (d). i < ze. See Figure 7 for a diagram of how each partial product is assembled. Architecturally. this will be done in log(d) transformer blocks. The first block will copy the product terms into the last A'd tokens. The remaining log(d) blocks compute the recursively assembled partial products by multiplying
Pa,k-1,21-1 Pn,k 1,24- Storage and assembly will be done in the last d Nd 1,..., d+ Nd N'd tokens.
For the first transformer block we define B₂ B(N4d, 0). We index each attention head as An,i where n (1....,,Ny n² and 1 < < d. Fix patch n and the corresponding product I $i,= These terms have been pre-computed and stored tokens het1,..., hd+ Nd- We will then use each attention head A,, to copy 8t, into its corresponding token hn, = ha4 2 (n--1)ad--44
Concretely, for fixed attention head An, define the data kernels
daaaa
0
0
0
0
K
datta
0
0
D2
21

---

Pn,3,1
2n,2,1
Pn,2,2
Pn,1,1
Pn,1,2
Pn,1,3
Pn,1,4
11,
2nn
3n
8 4,
Figure 7: Recursive assembly of partial products from constituent terms. Formally, Pn.k. = 4
Pa.k-122-1 1,22 with Pa,1, Si,ni for E NJ, 1 S & S log2 S 26.
via the Interaction Lemma 3 we may pick An, so that
Angiing
((Qn Kn Kngha))
Σ al ohn Qi K2, C)
k=1
a[ Si,n )e1 St,nil
where the interaction terms zero-out all terms in the sum except when k = d + id + nz (which the index of the token containing $i,n)). Similarly in B₁ we have An, 0 when k # d .d Ep=(n (n² 1).dd> + i. Set the feed-forward layer FFN = O. Then the next token embedding matrix can be written as
51,1
SNN
P ONA Io+Na+N
0
Nd
Hl3
I
...
where P1 E R Nd is
Pi = P( P())22 POYAL P()x(1)-MM1) P(N)4..
[111
$2,1
$d
$1.2
SdNs
where recall 1,1 denotes the first term in the base level product for for the patch {1,.., 1}. Now define the next block B3 E B(Ndg, 2 1). Index the corresponding attention heads as An, for E (I,...,,N Njd, djd 1 <
is < d 2.
Define data kernels
data n.ó
data K
n.
0
0
where we choose the interaction terms so that the token containing Pa, 1.26-1 only interacts with the token containing Pa, that they multiply form Pa,2,i as shown in Figure 7 Note, in addition to computing the product, we must also subtract Pa,1,2í-1 from each corresponding token so that the output of the residual from Bg cancels with the existing terms in the embedding matrix H3. Write
Ap,
Σ Col(nnat (aa = o Jmn
o(p.2i)e2 Pn2.10.
22

---

Adding the result onto H3 gives the intermediate embedding matrix
xd
111
Sd
Pi
0
Nd
PL. Io+Nd+Nad
H3.5
I
where Pi.5
I. N is
Pa. P11422
2(1
*
P(N
Note: denotes a non non-essential entry which can take any value. We then design our FFN network as 1 where
1
0
0
0
0
W1
0
0
0
0
0
61
0
0
0
0
0
0
which when added to H3.5 swaps the first component for the second component of each token and zeros out the second component. Then the next embedding matrix H4 gives
P2 O
Na N I1
H4
Ne
1
where P3 = P1.s E Rd More generally define the kth block implementing the kth level of the parallel product Bx+2 B(Nd 2 d FF)(()) with attention heads A,, where n (I,..,, N]d.
d We can construct each attention head An, k. so that the token containing Pn,k- 1 i 2t. only interacts with the token containing k 1,21 to produce pn,
An Σ (lQmatin Vo, o opnnk-1,,2 1,20 12n. 12 = P2,
In the FFN set W1 as before, yielding
Ps Id+Na-N4d
Oa+Na4Ned
HR42
I1
where
Pk [PO)A
P(N)AR ...]
At k log(d) have
Poge(d)
Os+Nd4 I
Hing(d)22
I4+N4+N44
d+NN+ A4Nd+ (n = ln.log(d). = (x) as desired in (18). It simply now where component log(d)+2
remains to multiply each (z) by the corresponding local average fu and sum the result. This can be implemented with a single attention block Bing(d)+3 E B(Nd, 1). For n E (1...,,NT define A, with the data kernels
0
0
0
0
fn
Q.
K,
=
0
R
23

---

where (10.12=(00011)) S R and the token h (ne- = hn,1 only interacts with itself so that
Anhin
Σ - R++ +++ K2 C)e2
k=1
= + R)e2 (fn + R)e2
where the last equality comes from n (a))
- [
R. We implement FFN to subtract R via
0
0
0
0
0
0
R
W1
0
0
0
0
0
0
0
0
0
so that
Oa+Nd I
Plog(d)+1
Hog(d))+1
Io+No+Nod
where p=.1
log(d)+4 = Sn for n E (1,..., NJ and is O elsewhere. To sum up the resulting terms we
define the final transformer block +4 ((1, 0) containing single attention head Ai
0
0
0 0
0
0
0
0
0
0
1000
Q
K
0
V
0
0
0
0
0
0
0
0
0
0
0
R
0
0
which when applied to each token simply sums up the second components of all tokens. The result when applied to he where t gives
41h4
o ((Qhe, Khx))
k=1
(h R)e1
(IR+ +
Σ
fndn)es.
ne NJ.
We can subtract IR with the FFN as
1 0
-RR
0
Wi
0
0
0
yielding the final result 12 = Σn fnon. Applying the decoding head returns the desired result. This shows we can construct the approximation f exactly with an O(log(d)) layer transformer.
E.2 Proof of Theorem 2
With Lemma I we can now move on to the proof of Theorem 2
Proof of Theorem 2 Our goal is to approximate f M R in (M) with transformer neural network. Our construction proceeds similarly to the construction in Chen et al.) 2019 with feedforward neural networks.
24

---

First, we will decompose f() as sum of terms over local neighborhoods UI...., UCM S M covering M. Approximations on overlapping neighborhoods containing will then be combined via a partition of unity (PoU) {px le which subordinates (Un)mi) while contributions from neighborhoods not containing will be zeroed-out via an indicator 1u,- This will give us the expression
CM =(x)= - Mn 1=1
(19)
where fn .M- + R agrees with f on Un- Next, each local neighborhood we will project the input E M C R to [0. 1l This will give us the following local decomposition of the target function:
CM f(x) = Σ fa (x)
where fn : Rd + R and on - - projection. This step is critical: we now must only approximate low-dimensional function fn and simple projection on instead of the high- dimensional function fn. After this, we must simply approximate each fn. on. Iu, using transformer neural networks.
Step 1: Local Decomposition Denote the open Euclidean ball with center c and radius r in R by B(c, r). Given manifold M satisfying Assumption 1 the collection of open balls (B(c, r)) cE.M with some r S /4 is an open cover of M. Since M is compact, there are a finite number of points, denoted by Ca. for n I...., CM such that M C U r). We can then decompose M into CM charts (Un; @n)m where U,. .M n B(cn, and each 6n Un -> IRd is an orthogonal projection of the local neighborhood U, onto the local tangent space Te,, (M) Via Lemma 8 as long as r I r/44, each on, is diffeomorphism between Un and subset in To, (M). Here the number of charts CM is a constant depending on the complexity of the manifold M.. We can bound it as CMS SA(M), d log(d) where SA(M) is the surface area of M Conwwy and Sloane 1988
x2
For the open covering {Un) CM there exists smooth partition of unity (pm) such that f(x) JU= DCM Pn (z) for M [Tu 2011). Each P. is supported only its corresponding chart Un- We additionally include an indicator function ly, for each neighborhood U,., resulting the decomposition
CM
[(x) - Σ (1) (z)
(w)
We then aim to approximate each term in the sum on its corresponding local neighborhood U, and then sum the result. Because we are only locally approximating each Pa. the indicator is critical in the approximation as it will be used to suppress contributions from U, such that the input & Un.
Fix local neighborhood Un. We will now project the input x E M C RDD the local tangent space To, (M) C 1) We can write
fa(x) (fn on on (x) fr o (x)
where Fn Rd - IR and again on M M R + Rd is orthogonal projection. Then we can write f as
CM
f(x) = Σ in on (v),
(20)
Step 2: Local Approximation In (20). we have rewritten f as sum of functions which can be approximated locally on each Un and indicators 1 We will approximate each component with transformer neural networks. Specifically, let Tú, approximate fn. To., approximate On, and T Tig, approximate 1 1 < n < C.. Then we will have the overall approximation
CM
f(x) = (x(2)
Σ
j, To. (2)TTe, (x).
25

---

This yields the error decomposition
CM
Il - Tyllmw(m)
Σ
Il @nlu.- - -T Too Tiu, (
n=1
CM
Il Pn Tin. T, o TTo, Tio, ( + Ilfa ooluu, fn on Tw,, (M)
CM
II On -Tj. To. (1 + Fm,
CM
II on - - o Unlll @ollL=((W)) + J oΦn - -T o Toolle + En,3
nml
CM
En, + En, + En,3
7=1
where the error terms F,,1, F,,,, F,,3 denote
E = [l Φn i o @ullem(U,)
(21)
E,, [T on - -. Too, (1))
(22)
En, == Ilfn 0, - fn on Tıc, (M
(23)
respectively. remains construct transformer approximations for each term.
Step 2.1: Approximating Ín and Bounding E,,, We first handle the E in
21 Fix
1 S n < Cм- We can write
II on Tj @n (nllLm S -
so it suffices to approximate f. [0, 1Jd R. Now choose the desired accuracy 8n,1 0. Via Lemma we can construct an approximation such that
In T 10 8n,1-
This construction Tj has O(log(d) transformer block layers, O(1) feed-forward layers, O(db,,) tokens, (11) embedding dimension, (d6,,,)) attention heads per-layer, and weights with magnitude we can compute each approximation of fr.
most Odd5,, 2d Via the Parallelization Lemma
in parallel using transformer with dC attention heads and OCC)demba) FFN width, where we 81 = 61,1
S and O log(d)) layers.
Step 2.2: Approximating on Exactly Such That E,,2 = -0 Fix S n C.. We must now control the Fn, error in 22
En,2 = [Ty, o On -Tú, To (l
We will implement on using a transformer block B E B(dD, 5). We can identify the tangent space at the point ca
Te,, (M) = span In, Un.a)
where the vectors Un.; E R.,, i d, form an orthonormal basis of Te, (M). Then we can write the projection map on as
(n(x)) Sv c,) un)
where 8, E (0, 1] is scaling factor, un E Rd a translation, and V,, = [Un,1 Vn.a] Dxd
so that or (x) E [0, 1]d. Suppose we have an input hidden embedding matrix of the form
0g
0
0
E Remebaa xl
I
I
1
1
26

---

We will implement the operation o Define the data kernels
(xd cti) via an attention head Ar,. 1 liiidiidssss
Qa
0
1
K Kidato
0
0
0
2M
via the Interaction Lemma
define Aij that token hD+s interacts with token h3 so that
Aig(1utii - =0((Qua hD4i, kgata/)))
=o((h, G2 2M)
= =0(1,,1 ct,)) + 2M)
= (xh, ())) + 2M)ei
and is on other tokens h4 F hD+i, where M bounds x E M is such that (2) o2)) + 2M 2 0 for all n, j.j. Then the output of the multi- attention MHA on hp4s is
MHA(hD+1)
Σ ALShD+i Σ AighDti
Iskdd 1SI5D
5=1
-h che + 2Me 1 -
+ 2DMMr
This yields the intermediate embedding matrix
x
(Un,1 ca) + 2DM
(Un,d, x -C)) + 2DM
0
H MHA(H)
I
It
We can then design a five layer FFN layer to subtract 2DM and then add u, and multiply 8, only from the embedding tokens D + 1, 1,... D + d. The first layer will simply subsract 2DM and then add un and multiply 8n from each token. This can implemented by the matrix
0
0
-2DMs, s. + Un
0
0
0
0
Wi
0
0
0
1
0
0
0
Then, via the gating Lemma 4 we can construct a two-layer ferd-forward network FFN gating such that, for chosen except for the last three rows for k > tu- We can again invoke the lemma to construct another FFN layer so that for & 2 4 - FFN gotgngg (b+)) hy and k < 4 - FFN gaNggning(Hy
ta S we have FFNneting (hu) = ha when k: < ty and goNigg (hg) is zero
zero except for the last three rows. So, applying Lemma 4 twice, we can construct four-layer feed-forward network FFN FFN three rows gating such that FFN gatggtiigg(h (he) he for D + < D + d and is zero except for the last
This yields the desired output.
I1
Su((Un,1, Cn) + un)
Sn Sn xt Cx) + un)
0
H' = B(H)
=
I
I
1
Further, this approximation exact, so that E,, 0. We can then compute each Φ., in parallel via the Parallelization Lemma with a transformer having O (CCddD) attention heads and O OC dembba)) FEN width.
Step 2.3: Approximating 1 (x) and Bounding En,3 we can write
Again fix
CM- By construction
{
| Cn 12 < 2
Lu, (2)
| Ca b > 2
27

---

Suppose we are given an input embedding matrix of the form
Op
0
0
H1 =
E
I
It
1
We must start by computing ||
Via the Addition Lemma
5
we can construct a transformer
block B1 E ()) such that
x
x
x
0
H2 (H1))
I
IL
We now construct transfomer block B2 E B(D, 2) squares each term in the sum. For sii D define the data kernels
Quata
0 0
K:lata
0
0
0
Then via the Interaction Lemma 3 we can construct A; so that the token hp4i interacts with itself such that
A.(hD+s) = o((x' ),2 = (x² -
and O otherwise. The output of the resulting multi-headed attention gives
x
x
D D
0
(x
(x D2²
H
I
I
Via Lemmas 6 and
4 we can construct FFN E FFN((5 which replaces the first row with the second
row for hD-1 ... 12D. This gives the output
(x - c222
(x
20
0
H3 (22)
I
I
and it remains only to take the sum. This can be done with B3 E B(D - 1,0). For 1 Sis D-
define the data kernels
Quaata
Kdata
0
0
0
via the Interaction Lemma we construct A, so that hD+1 interacts only with hD+1+$ such that
11(++1) = ((Q hD41, K ddata hD4141))er = a(xtt1 oft1) = (x -
The output of the multi-headed attention is then
D-1
D-1
MHA = Σ
A((bD-1)
Σ
++1 c c(t1)ez
and 0 otherwise. This gives the intermediate output
x Eb (xt
-
(x. - c2
0
Hi
I
It
where in particular hb41 = |||--pah
c.. 1c-ccal1.
remains approximate the indicator
2
1,a(s) (
2 2
28

---

2.3a: Approximating (s) Recall our goal is to approximate the function f .M + R in L However. we cannot approximate 1, in * as is discontinuous function. To address this issue, recall the error term corresponding to the approximation of 1v, is En,3 = Il. o on b, fn on Ti,,, [M.-- We know on the boundary of Un that fn o @n = fn = fpn must be 0 as P.. is and further frn (-Hölder continuous f is (-Hööldr continuous and Pn. smooth. This suggests the following approach. Define the approximating indicator
I 2 A 1 <
(s)
< <<<9" <²
3
0
8 2 r2
for some A 0. Clearly for p² - A and 22 have 1, (s) (s)(s). So argue fn
is small for z E M in the range Kn, {or E M: - A || cn r².. This is handled by Lemma 8 in Chen et al. 2022] which gives us the following bound on E.,3:
Fn,3 S -
for some constant c. So suffices to make A small. then remains to implement 1,2, We will do so using a feed-forward layer FFN E (Fo( )))). Note that we can write the target exactly
(s),((8) (1 (1- (1
while is realized by a two-layer ReLU network. However, the weight 1 will scale unboundedly with the desired accuracy So we must deepen the FFN to utilize logarithmic number of layers Olog(()) as
Togt 5
Tngs
(s), = 1
(s 1r-(22 --)))....
o... oa
which prevents the weights (
from blowing up. We can then approximate each 1u, in parallel using transformer with D) and three layers.
Step 3: Bringing it all together Recall our goal is to approximate f on M by writing ʃ as
CM
f(x)
Σ R=1
In o On (z)
We argued we can successfully approximate
1. fm up Jn,1 accuracy in L via transformer neural network with O(d5,,)) width and (log(d)) depth. All approximations can be computed in parallel via transformer with 0 (C attention heads and O log(d)) layers.
2. Each on exactly via transformer neural network with O(dD) width and constant depth. All the on can be computed in parallel via transformer with (CMd)) heads and constant depth.
3. Each l up to 6n.3 accuracy in _ via transformer with O(D) width and feed-forward layer with O log( (og({)) })) depth. All lu, be approximated in parallel via transformer with DC attention heads and constant number of transformer blocks.
Via the Parallelization Lemma transformer with (d 1 dD)) attention heads, O (C FFN width, and O (log(dd)
7 we can compute the approximations of Iy, and fn oΦn in parallel via d
29

---

transformer blocks. As result will have the embedding matrix
Cfi
CfcM
CU
CUe
0 I1
0
H
It
where each cs. fn (x) and cU2 1u (z). We implement the final via two transformer
blocks B1, B2. First define B1 E B(CM: 1) with attention heads A,.
CM with data kernels
Qdata
0 M
Kdata
1 0
0
0
with interaction kernels chosen so that hn++ only interacts with hD+CMti under A, Then
A,(D)+t) = (cy c, + M)e1 = (e,,cv, C,, + M)
We can then design a two-layer FFN to subtract M from columns D + 1,.., D + CM yielding the output embedding matrix
D
CU
ClaM CUCM
* 0
0 I
H
I
We can sum up the result with another transformer block B₂ E B(CM, 2) and storing the desired result the first component of the last token = I. Applying the decoding layer D yields the desired result.
simply remains to control the errors. Recall we have the error bound
CM
|| - -Tyyll==(M))
Σ
En,1
+ En, En,3
n=l
CM
8,,1 8n,3 Cmôn, CMôn,3
Then for a target accuracy we choose 8n,1 20 and 8n,3 = c so that
20
TT-T S CMÔn,I CMrn3 CM2CmM +CM 2CM
E
This completes the proof of Theorem 2
The above result concludes our approximation theory results. To summarize, we first showed (sufficiently smooth) function ʃ [0, 1] + Ik can be approximated up to e accuracy in L with a transformer neural network with (de d) width and (log(d)) depth in Lemma used this construction to show function f: M + ER on compact manifold M with intrinsic dimension d can be approximated up to accuracy in L2 with a transformer neural network with width O (max(dD, de d)) and depth (log(dd))
We then
Proof of Transformer Generalization Theory
next prove Theorem in Appendix F. Much of this follows the same argument as in Chen et al. 2022) which focused on feedforward neural networks. The main novelty of this paper is a bound on covering number of T(LT,, TAEN WreN, 1, dembd, m, R, x) given in Lemma which proved in
Appendix R2
30

---

F1 Proof of Theorem 1
Proof of Theorem 4 Suppose we have 21, "1,...;a Q as ii.d. training samples drawn from Q on the manifold M and their evaluations f(, fzn). Set the approximating function class as T(I-r, LITN, WFEN, 1, dembd, R, k:). We define the transformer empirical risk minimizer T,, in (T) as the transformer network which minimizes the empirical I,² training loss. Our goal to bound the squared generalization error in 6
We first rewrite the squared generalization error by adding and subtracting (twice) the training objective where we note a factor of two is used to accelerate convergence of the statistical error.
E
-f=())
f(
M
f(z)) + / (()) 22
" Σ 7
2E n
- (24)
JM
The first (bias) term in 24 can be controlled via Theorem 2
(T,();)) - f(x:)) = inf TET n
(T(x;) - fxx)))
7
n
inf E
Σ (T(ws) s(xxa))
TET
inf / TET
(T(x)= [(x))2
JM
S inf
| - flli= 2²
TET
JM
where the last line follows from Theorem Jensen's inequality. Set (x) fxx)
2 Note, we can pass the expectation inside the infimum via
remains to control the last two (variance) terms in 24). We will do so by controlling the covering number of the approximating function class T(LT, LFEN, WPEN, L, dembd, m, R, k). Via Lemma from Chen et al. 2022] we have the bound
E /
n
J
-2 -
Σ (f.())) - {(x)))
n
104R2
8 4R. T, 1120) + (4+ 2R )
$ inf 8>0
log N
(25)
3n
where N (
loo)) denotes of the covering number of the network class T under the L norm.
Our goal is now to bound this covering number of ((LT, LEEN, WFEN, demba, m, R, k). We do so with the following lemma:
Lemma 2. Consider transformer neural network class T= T(LT, LIFN, WFFN, I dembds m, R, R) with input x E TRP satisfying 1| M.. Let >> Then
181. 1812, Tan 6LL Love Loxe 1 4demea D Lot (6 T. 1.0) 12 LEEN demba WTN
Lemma is proved in Appendix F2
With the covering number of T(LT, LEFN, WFFN, I dembd, m. R. 1)) in hand we may now apply 25 obtain
E / -
n Σ
-2E
(T. - f(x;))?
n
iml
104R²
8
1
< inf
log.N
11.11110))
+ 44
5
82-0
3n
4H'
2R
104R22
1
log
T.
|| 1lo0
4
3n
4Rn
2R
31

---

where we set 8 8= This yields
Mar 8 T, -lb0) < log (2 LEAN F 11822 18L3 Loen ,6/. Luon m 1. ( 1e ueeesu Dim+ Lovx)
N
WPEN
4Pm
eebe (m + LEEN) (5L7, log L (2Ar:2MMAdemaamm
20 (2g LrnedeeeaaaUUUynysssn De " mlmmm.... 1 I FFN-
can choose LT log(d), LFFN log(e +),, WFFN 4CM. dembd = 5, 1 S CMdE 3, m S CMde $ R S (MCMde 31 CMdE This simplifies the above to
Recall for target accuracy
8 NI. T. 11bo) z 900(11g(()))) log(d) log(60d -4 ())++n)))+e))) C)) Ddc s ÓDDe #) 4R'
where Ô hides log terms and constants. Then we can bound the variance term as
R (Ta(t)- ((=)) 2 (z.) -(x))) Ö Dule O
E
n
Putting together the bounds on the bias and variance yields a bound on the empirical risk:
E S -())))))(=)))0))) S 0(2 Dofe-á
72
and it simply remains to pick e to balance the error terms. We do this by choosing such that
22 - yiclding = n 20+0 This gives our final bound on the expected empirical risk:
S (fn(a) (()))) 2E Σ (f)) f(x))) < Ō(D 28+4 M
28
E
as desired.
F22 Proof of Lemma about the Transformer Covering Number
Proof of Lemma 2 The key bound the difference in || -l between two transformers T, T' T(Lr, LINN WFFN, I, dembd, m. R, k).. Set 0 and choose T, T' so that ||0 8'1 In other words, the weight parameters in T and T' differ at most by n. Fix x E [0, 1) Recall the decoder D Rdennext IR is fixed output the first element of the first row. We compute
T(x)= - Tx()) = Do BoBLO
B (PE + E(x)) D' B', o... o B' (PE+ E'())) BB o o B, (PE + B(x)) B' o... o By (PE + (x:)))
<
To handle this term, we write
|B2 o Bj (PE + E(x)) - B' .... B (PE E
< B o.. o o PE + E(x)) - By, o.. o Bj o (PE + E'())l))
+ B o... o B, (PE + E'())) By, o.... B (PE + ((x)))l
We will first bound the second term.
Consider two multi-headed attention layers MHA,, MHA2 MHA((m) with attention heads A3.
E [1,2), 1 و < m. For H [0, demomux we compute
m
7
|MHA| (H) MHA. (H))lo
Σ
A Σ
A3(H)lbo Σ [A) A3(H)) 1ls
j=1
1=1
m
<
Σ
[A) 13
32

---

Consider two attention heads A1, A2 with weight parameters Qi K, V,, E {1,2}. For H e [-M, M] demmaxx we compute
[|)) A2(H) &
max 1515!
[A1(h)) A2(h,)]lo
max 18
((QQhh,,Kib)))
((
max isis!
(o((Ohy, Kiha ( K2he))
max sis
Σ
(Q((
([Q2g, K2hx)) V o((2n3 K2ha) V2h (V
where the last inequality comes from adding and subtracting the term (Q2h3 K2hx) We bound the first term via
(0( Kyha)) (((eh) Kahe)
(Q1hg, K2ha) - K2hh,,K
< [KQ 1ej Kihx) (Q1hg K2hu)1 + +(Q K2h1) - (Q2hi, Kaha)
< [(Q2h,, K2hx - K2h4a) + IQQ Q2hg. [|
[11@ - K22h//2 1Q - Q211 [12 K K2hx [|a] ||Vihalloo
[11@:|11llbbll... |K, K21h //lll//ball + 11Q Q2 11, K2 h ball
< [2x² axx2deemaa M h/
52x 2 M
where we note ||rll22 < ||Ax|| < ||||||I=T for A E R Reemtaxdemod x E Reeend and ||A|]] S de demball-4 |Alloc This bounds the first term.
The second term can be bounded as
(oQ Kghh)) (1Q2h,, Keha)) |1 K haha)
Am (Q2h5, K2ha)/hull
Anl Q2hrl1122211llll (Kokblllal/Ka < t Ma
Thus we can bound the attention difference [|A((H) - A2(H))
- bo
KiRnh,,,hheVVi - (Q2h,, Khhlle 1515
max
11022hj, Kehn) (Q2hj, V2hulloo
max
3x
Memba M 3x² M ln... M
We can also now bound the multi-headed difference ||HA]((H) MHA2 ( llcc as
||MHA| (H) MHA2 (o) S Σ (1)(0)) A3( S 3x 33x3d M 3xx do demba M mLn.
A bound on the first residual layer in the transformer block immediately follows via
(H + MHA, (H)) - (H - MHA)(H)) = (MHHA(H)) - MMHA, (H)
33

---

To bound the difference in the output of the FFN layer in the transformer block we have for f1, f2 (LN() and input E [0, M dembb we have
( (2 S Leve(demba +
LeN-
which also bounds the second residual layer of the transformer block. Then bound the difference of two transformer blocks B1, B2 E [mm, LIEN) write, for H E [O, M]demsaxi
[B (H) (2 II(H + MHA (H) + FFN1(H MHA (H)))
(H + MHAg [)) + 2 (H + MHA2 (H))) 1l
||MHA| (H) ) + FFN, (H + MHAI(H) MHA2(H) + FFN2 MHA2 (MHAA(H) MHAz H)) loc
||FNN (H MHA, - F MHAg(H))
S 3x Ae mln + ( + MHAI FFN; + (H)
where we can bound the first term via analysis above. For the second term write
|FFN, (H + (HAI(H) HH + M
FIFN (H + MHA1 (H) FFN, (H + MHA2 + ||FFN2 + MHA2(H)) FFN: (H + MH))
To handle the first term we must bound he Lipschitz constant of FFN, Let H, H' RRdennaal Write
||FNN, (H)
FFN, (H²) lxx
max 1515!
|IFN (h₂) FFN, FFNI(K))lI (1))Ilo
L - bı)... + DLINN + bLVN LieN (( LW + b1)... + bLINN bLnN 1l00 h + +1)... + ÓLANN-1 W WLEN-1... (W2h's b2)... + 1oox
max 1SJS! [ Lii (W
I max ISJS! |W WeRN
< max 1515!
[[s] |/, 1/llo0 S WilNeN x Jvo | H'
1=1
where we again use that | - ||W] o1 and that o(-) I-Lipschitz. Applying this to the first term from above get
[FN,, (H + MHAI (H)) - FFN, (H + (H)) I
WHn 2LWx xs LEES 3d M mln
2LaN L |MHA, - (MHA(HH)le
WTFN
3+
WFFN
2T. d de M Mmljj.
We can bound |FFN (H + MH))(H) - FFN, (H + MHAg as [F + (H)a(H)) FFN, (H + MH)
< FFN + MHA2(H)) FFN, (H + MHAg (FEN + 2) (kUPFN)) LIN-11 where || ( S M'. Putting all the estimates together, we have
[H) - l10
<3 deeddemaa M + ||FFN/ (H + MHA, (H) FFN2(H + MHA2(H))lls
<3x² &emba 3 (m1mm + 3xd 3+ Lavs 2Tays
M "mly + LENN(UFEN M + (N(WFFN)) -
WPEN
<(4x3t LAeN 2Lax WTIN
ml 3 LFEN(WEEN + 22) (KWFFN) Iax ')n "
and it remains to control M' in terms of M. We know || + MHA(H)]] S M' and so we compute
|| + MH)(H))) < . ||MHA(H)]l>
m
M
max
Σ
KK Kyhh)Vyhulll
< M + mlds m M < 2d
2d mlM.
34

---

Thus, we can complete our estimate on [[B 1 By (2 oc
[B, (H) - (2 S (41. 3 FFN demba 2mmi md + TANN (WTEN (aeeuwrrr22eeeaaee (mdee mlM) + 2) Lmx
Now consider the multi-block difference
BBL o.. B1 (H) Bzz, ... (H)) - |B ... o (H) BLT 0 ... BH)
+ BLr (H) B'L,, o... BJ (H) oo.
To bound the second difference we must bound the output [[B( co. E Bim, LANN). Suppose |||| I M. Write
[B(H) = |F + MH)(H)) + MHA(H) + H
S || ~0 + [[MHA Dc + [[FFN( + MHA(H))
- 2dembak mlM + ||FEN(H + MHA(H)))
so we must bound the output of the FFN layer. We have for H' E Redemsai with || M, we have
|I S (Aeeemaa Law- M + K(Kidemba) Lers-
Since || + MH a( S 2d Aemmat we have
[B(H)) 0c I 2d m/MM + (NeW)EN) 1 2d 2demb mlM + x((N A
S 4d 4edemba 2ops bienstmmMM
lterating this gives
B ... Bi (1 S (Adem
2LaR xe be ml) ( M.
Then we can bound the above second term
B ... (H) B/ o... B' 1o)
S <(4r² (4x ber d 642Lmm (1 aaann p (.Lxstlml) por--lMM
+ LENN( (dembed 22 emba md
3 (4d taxt ml) 11))-(1-)) M)) + 2) (xdenba))
embd
<A3LT L Bler Lee + 121.7 104pN FL Low +
m L
embd
SLT LFFN G Lass LovN GL. Loss m fr n.. WHEN
To bound the first term [ ... B1 (H) B B' (H)l 1l must control the Lipschitz constant of of B E B(m, LeeN). Let H. H' Bddebaxi with | bo; || S M. Compute
[B(H) B(H |
||FFN(H + MHA(H)) FFN(H' + MHA(H') + MHA(H) - (HHA(H))
|FFN(H + MHA(H)) FFN(H' + MHA(H')) + [MHH((H)* MHA(H')
FFN(H + MHA(H)) FFN + MHA(H )|) + ||MH{(H) MHA(H')
2LnN reL [MHA(H) MHA(H') H H' +|MHA(H) - MHA(H))
FPN
2LEN Lovs |
H' + 2WE Aaas + 1) MHA(H) - MHA(H')
and it suffices to control the Lipschitz constant of MHA E MHL((m)). For the same H, H' compute
(HH(H)) - (HA(H S max IS
ΣΣ fi
10,h,, Kyha)V,he (Q,M, K K,M
We can bound K0,h,, (Q,M, K,MWSM
IKQ,h,
1Q,M, KAW,Vl (Q,M, K,M +
- K,MYV,H < (Qphi, Kyht) - -Q2144 KyMA)lIV + 1Q,,44 KyMa) - (0 KyMe) (V - Vyhulloo
< (Qyhi, K2hh) -Q2ph4, Kihhe) R.M + 1Q,44 Kyh()) (Q K, K2h&k) demsattil//x 1/ollo
< (Q Kyha) - -1Qgh4, Kyhle) d2 R + 2dt 2 M2 de dembatillh - 16/1l0
4ddmmaa 2211/0 A/.loo.
35

---

Applying this gives
|MHA((H) - MHA(H') S 4d 4demba embet M2 H 12
Then
[B(H) - B(H al
FFN
2THN n LAEN H H' + (WFFN KOLERN + 1) +1)[MMHA(H) - MHA(H')l
2LE LAs H H' 11/10- 00 + (WFFF
210EN LLN + 11) Mannnnn-- M 1l
" WFFN
< SWEEN K LII de dembar M ad22ml|| 1l
2ors
With this we can bound the first term of the multi-block difference
[B o... o (H) - B o (H) I sdenost K LoN dembaat |L 0... Bi (H)
* BL .... B1 - BB o.. (3 1000
Se LIN de Lembaa ((Ad L )m))+ ml) -r- M 2)²ml
B L .... (H) -1
BH)
< 2 eemtal
goLLoo 2 Lers de dembes K M Lr
* | .... BIH 1
o (H)
Putting together the estimates on both terms gives
BB (H) BBL,, (H) s 2 2dd deler LAeN 2L LIEN de cembd M2 mr
|
BH(H) BL, ... B' (2)
+ 43 LFNN M L18L & L m 1r 1 "
< 2 2Lr LT LFFN M 3 di LAN GL. LINN m LT (1r
| o (1(l) - B¹ o o.. o Bi (H)
which reduces the bound on the LT layer transformer class to the bound on the bound on the LT - 1 layer transformer class. Finally, via induction, we get
[BL, ... (II -B2, ... o ll s
LT LFFN M &d 18LT LavN GL mn br (br
FFN
n
22 TATN 3Lr 11812 2 "FFN
1 n. GL2, Lun Lum 1
simply remains to deal with the encoding layer H PE + B(x).. Both F. and PE are fixed among architectures and further |PE + B(x) = || + 1 M + 1. Thus
BB .... o Bi o (PE + ll I (4d fe go ml)) br M.
This allows to complete the total bound on the transformer difference of T,T E T(LT, LEFN, WPFN, I, demba, m, R. K) such that ||0 00'l < 17 as
[T(x)- - T')))l = ||D o BLT o Bi o (PE (E(x)) - D B'L,, .... Bi o (PE + E'())l
< 2 LIFN LAAN 3TTT a 1813, 1. 1 1.. Cr1.
Now, we may compute (V,, 5, || )lo)). We must cover T(LT, LEEN, WFEN, I demod: m, R, 1c) with d-net such that, for all T T(LT, LFEN, WFFN, L, demba, m. R, K),, we can find T in the net such that $ We construct the d-net by uniformly discretizing the set of weights
T'lloc 8. Set 1 Cz
corresponding to To E T with step size given by 1,. Then for any TET T, we can find a T" the grid such that | 0T ol < 7). Then we have T T' COn Cr Cr
S ó. We can compute the
number of parameters in
LT
[8] = 10 + 10pl +
0p.1 = dembd + demba D + L1 18pl
dembd + dembad + L (l@MuAl + 10rrs))
dembd + dembaD + LT
+ LFFNw)Ex)
S 4d 4d u D(m + LFEN)
36

---

2x, We can compute the number of steps per parameter as " T(Lr, LANN, WENN, 1 dembd, m. R. R.) is bounded by D(m Eep
Thus the covering number of
V(T,6,11-10 ()) 4d adeena fix
Cr 4ef ambe " D(m+ loy
21 L d 22017 1827 Lovs ,03 mm 17 " 46 4o6ems D(m Lavs Fo
W "FF
G Building Blocks of Transformer Neural Networks
Lemma 3 (Interaction Lemma). Set dembd 5 and let M > O. E 1 1,, S I, Rddemtatt be structured transformer embedding matrix such that he lifemdd 2:dembes Is and h hounnd 1. Further suppose || I M for some M be written in the
and I S dembd. Let
Let B Rddemba Rdemba - TR be kernel function tokens which of o kbKB))) for some h, h' E RRdemra, Q QB E Ridemaa- 3yxdemna with ||Q 1100,001 ||K 110,000 I K. Then we can construct an attention head A acting on H such that A(hy,) B(h hegle; and otherwise A(hy) = 0 for + l1 Further we have ||0Allo Odemmaak 22 Note: we call the matrices Q KB "data kernels".
form B(h,
Proof of Lemma
Define the query, key, and value matrices as
QB
KB
0
0
Q
K
KI
0
V
eje
0
0
0
0
0
-C
where we call Q7, KI E 2x2 the interaction kernels, QB, KB E Rdoome-- 3xxdmma the data kernels, and 0 simply a large positive number. We can choose Q K- so K Pi., is projection onto the unit interaction vector It (the interaction term for hr,)) and Q² is a dilation and rotation of It onto I, i.e. Q²I,, CIty. We must now compute A A(H). For arbitrary t S I we compute the action of A on h4 as
A(hx) Σ o (1Qh, Vh
k=1
Σ
(( h., K KBha) + (Q=I,, K²Ix) -C)e
h=1
Now we must case on whether the input token = tl.
Case 1: == t1
Write
A(ha,) Σ Eal10 K" + (Q= K²Ia) - CCes
1=1
To handle the same must again go by casework. this by casing whether k =2
Case la): l: = 12 When i la we have (Q=I,, K"Ing) = (CI,, It,) since by construction Q It, and KT is projection onto I, so that K K-In, = Izz- This further simplifies as (CI,,, Ina) = C' since Iz is unit length. Thus
o((2"ty,, hB) + (Q=I,, KFIx) I0-,,,,K=Iu C³ = =0(00 he, K Bhaa) + CC =a(1Q KK kBh)))
37

---

Now we must consider the other terms in the sum when ls + t2.
Case 1b): k + l2 When l # l2 we compute
(Q K²I,) S II
PI, Ixlla <C
where we use Cauchy-Schward at the first inequality and note that | Ixll2 < 1 since h o t2 for the second inequality. Then, for large enough C, we have
a(1Q hi, hx) + IQ ,T,, (( 0(1 he, kBhh)) + Cl Ixll2 - C) -0
so we simply must choose C' so that (Qthr, kBhb)) + Cl Ix 2/22 - C < 0. Compute
(Q B hit KB
(Q KBhbh + C - -C = C>
1 Pi., Inllz
We bound
Th@ he, K h2hhal
11Q hr, 1122|| "hx ll2
I|Qu 11.11//r, ol I 111,1 1h
11Q oo, Lemball lo Lembd M² S dembar" M²
so it remains to control
when + l2 by upper bounding || Ixll2. Compute
1- Pr.g Ixllz
PT.,, Is 122
max
|Pr,, Itall2
15
I PI l|2
(Io, In)
cos( 21
n²
S 2!. 2212
where we note the projection is maximized by any adjacent interaction terms I, I,+1. Then (Q 1rr, KBha)
d4 R M
O 2
I 1- PI.PIIINl
22
which gives bound on C. So for large enough C can conclude
A(ba,)==od ( hr K hx)))
It remains to consider the case t * t1.
Case 2: t + t Now consider A applied to tokens other than he, We have
A(ha) = Σ o((Q@), KBha) + IQII, K=Ix) C)e
so we must argue each term in the sum is 0 by showing (Q KB (Q"I,, -C We again split into two cases.
When k * to we have (Q" K hx) + argument as in case 1b.
Case 2a): k #
- C < 0 via the same
Case 2b): k = la When l: = la we must instead more carefully bound the inner product. We can simplify the interaction terms
IQ'I. KI,,, IIQ=I, 112 cos(O,, = C cos(fr,t2)
38

---

where 01,t, is the angle between Q'I, and K III. Crucially, because t + #1,, Q # CI₁ and so 0,,t > 0 and cos(t,,)2) Then we can say
1Q K h(g) ,L,)) -<0 = (Q kB))))) + C cos((tttt)) - <<0
(Q h,, KaBKBBB h22)
C> 1 cos(Or,t2)
We upper bound the numerator by 22(2). Note that the Q rotates by clockwise 27 a radians. So Q²I, C(cos( (++4 1 ) sin (1+1) f2)m ()) Thus we can upper bound cos (0t,tg) cos
21
as
cos(02,22)
(Iete--2: Tta)
1 (Io, IT)
cos(
π
$ 1
2 2! 2212
So in case 1b have C = Oddemia M21).. For sufficiently large C' we have A(ha) 0 as desired. This completes the proof of Lemma
Lemma 4 (Gating FFNs). Given an embedding matrix H E Rdembaxl which has all ones in the last row and whose tokens contain interaction terms and given a half-space of contiguous tokens his hy or his... hi, we can design FFN E FFN(() such that
h
E {1.
FFN(h))
I
otherwise
I?
where E
is zero except for the last three coordinates. We call this FFN gating feed-forward
network. We additionally have ||0 S (l)
Proof of Lemmal 4
Without loss of generality assume are given contiguous prefix of tokens
hi,... hg, S We can choose vector u St such that v I, for 1 E {I..., k) and v I, < for > k. We call such v the pivot vector. In particular we choose R To+T4 quarter-circle rotation clockwise. For a large C O, construct
where R ; is
T
C
0
Cvl
Cos
W1 = Idamba +
0
0
0
b =
0
0 0
T 0
-Cv1
-Cu2
Cv
CC2
W₂ = Iddemie
0 0
by = 0.
39

---

where Idemad is the identity matrix of size dembd X dembd- Then
( CC..00
(o + CI. u)
oh + C)
o + Cle v)
oWWih + bb)==
o (Me (heendd= o algpmmde (hhombuu
I
I
I 1
I
I -
which is
I. < 0. Applying the second layer to
yields
Otherwise assume
I
I, 0 Then (h CI. : u) hi CI v. Applying the second layer yields
W2 + b2 he
as desired. Further we can compute a bound on C > 0 as CC,, . o/ > | = compute
C
We
Is Ix+1
1/ (I, R
1 (Ik. R Ix] + [Ik, R Ix+1il
I + Ix+1ll2
(Ik. Rg Ixt 1||
= 2
(To, R Zi>
π 2
1
sin
2
where the last inequality holds for 2 2. Thus
H|| [e
2 H||
C.
Lemma 5 (Constant Addition). Let M > 0 and be vector in R such that ||c|lo 2. Let H be an embedding matrix of the form
xD
0p
H
E Rddemsaii
I
I
where 2D such that 100,00 <
M.
Then there exists a transformer block B(D,3) such
x
x
c
x
B(H)
Ii
I
with 10 = OIM)). In this case we say B implements the addition of to x.
Proof of Lemma We begin by defining the attention heads A,, 1 S i D. For each head A, we define the data kernels
data
0
0
0
0
1
data
1 0
0
0
0
-
M
Then, via the Interaction Lemma that
3
we can construct A; so that token hp+i interacts with h; such
At(hp+))= = = data hD4t, kdatah.) h1)
=o(r' - d + +Me1 = (xt - c² + M)
40

---

and (h,) = 0 when t + D +
Then the residual multi- attention yields
x
M
x
c +
M
0
MHA(H) +
...
I1
I
Via the gating lemma we can design a three layer FFN to subtract M from only hD+1:..,,hhp Thus
D
0
B(H)
IL
1
desired.
Lemma (Replacing FFN). Set dembd and N. Let Rdemmsxi be a structured intermediate embedding matrix. We can construct a forddforwwrdd network FFNrepioce E (F) with the following output:
11 +1
11 + +1
FeNrope (H)
0
In this case we say FeNreplace replaces the the first row of H with the second row.
Proof of Lemma 6 Set
1
07
0
W
Applying W token-wise gives the desired result.
Lemma (Transformer Parallelization). Let mı, m2, 1 l2, LFEN1, LFFN2, WFFN1, WFFN2, dembd E N. Fix transformer blocks B E B(m,, LIENI, WPFN1) with input H1 E Rdemea and B E B(m2, LFFn2, WFFN2) with imput H2 E IRdemsaxlz, Further suppose both inputs are structured such that each token ha, has an interaction term It and constant all attention heads in both B₁ and B2 are implemented using the Interaction Lemma and all FFN layers are either Gating FFN layers are independent of the interaction terms. Then there exists B3 E B(m, + m2, max LFEN1, LFFN2) + 2, WFEN1 + WPFN2) which takes as input Hi E [ddemaaX(1 (l)+ such that
1. Further suppose
(a( ( (H
Hb)) = (B, B₂(H2)]
E (deenaa(lsHt)
where Hi Rl is the same as H; except for the interaction terms where we have I2 (cos(, 1,+ 7 sin( 1 for forl < 1 < 112 IfB3 satisfies this relationship we say B3 parallelizes By and B2.
Proof of Lemma FEN, (MHA, (H2) + MHA, + H2. Let AI, < i < my denote the attention heads of MHA2 and A2,22 1 < & m2, denote the attention heads of MHA2. We construct B3 follows.
Let Bj (H,) FMHA, + MHA, Hi and Bz H2)
First we construct the new input embedding matrix Hg from H, and H2. For 1 S L h set h3, h1 except we define new interaction term Iz. (cos( 1, 2), sin 11
$ 1)). For
41

---

+ define hs.: = h3,-11, except where we again must change only the interaction term. The main difficulty in defining MHA; will then simply be updating the interaction kernels of the Interaction Lemma structured attention heads to respect the new interaction terms I, 1 < 1 S 1 + l2.
We now define the attention heads As,j in MHA3- When 1 S the same Qi except for new interaction kernel 2i-5- Let h h1, 85 E (1,..,,44 J1
my write Q3. Qi where Li the source token in 11 interacting with Q and Ai,s, 4 E {_,,.., J. be the target token of the old interaction kernel Yi (recall Q1.5 J is defined as the rotation of Li.s, onto IT,e,) ). Then define Ri's as rotation onto the new target interaction kernel Zz,t.- Similarly define K3.j Ki, where Ki K1.j up to a difference interaction kernels. Let KL, be the old interaction kernel which is projection on to the target interaction term Zi,,, Then define the new interaction kernel as projection onto the new target interaction term Is,t, Simply set V3.5 V1.j- Now check As.j (Hz) l.-d1 A1. (H1) up to the interaction terms. Compute
4
As.((13,s))
= Σ k=1
o (1Q3, VV3
= - ha.,) V3,
= c0(Q11,h1. K1, K Vi, = A1.5(11.s))
where the second equality comes from the sparse construction of As.j. the third equality comes from the construction of Q3.j. Ks.j. and the last equality comes from the definition of the sparsely for + 8j. Thus
interacting 11,j- Otherwise As, (Rs,e)
conclude (H,) A1,y (H,)
up to interaction terms. The case 4 + < j s 4, + +22 proceeds analogously. Thus we conclude
MHAs
[B (Hi) (2
up to the interaction terms. Now we must construct the parallelized feed-forward layer FFN; from FFN, and FFN2. Let W1, be the kth weight matrix of FFN1. By assumption know W1, either a gating layer or is independent of token interaction terms. If Wi.k is independent of interaction terms can simply set W WI, Otherwise if W .. is gating layer on some
half-space
Io.ptZappt Set 1 S 41, we must pick new pivot vector v' R (TZ,, to
Wi, accordingly to the new v/. We may similarly choose W2,,. as we did for Wi,s- Then we set the new layer 3,3
Wi,
bi.k
3.A
R (WINN wVINz) ( x ((UNN)) + by,
R WWIN +wres
W2,k]
b2,k
We must also construct an embedding network W3.0
Tdtembd [dembd]]
W3.0 =
E I x22eesaatdeems
which duplicates the input token h3,t E RRdembd for parallel processing. Finally, via lemma construct two-layer network ggatigg such that FFN, IFN1,goting (h3,e) ha, 1 < S and has
we may
zeroed out data rows otherwise. We similarly define FFN2.gating for 4 + 1 < < 4 + lg. Finally
we define the output layer W3 (anax((un,,Leaaall as
[Laemad Idembal Redemtd 2dd
Thus, for input token h3,r. 1 S 1, we have FFNg(ha.)) W3. W,,max(( LINNI,
FFN gggting FFN,
FFN, gatting FFN2) Wa,oha.
[hgtr] h3.t
W3 Foww
FFN FFNN 1.gating FFN,
FFN, gating FFN2]
FFN (h3,t)
=Wa.max(Lenn Lanax)(rww
0
= FFN (ha,))
42

---

as desired. The case 1 St 1 + l2 proceeds analagously.
H Other Lemmas
The following lemma [Chen et al. 2022 Lemma 2] is used for our construction of charts in the proof of Theorem 2
Lemma 8 (Local Diffeomorphism). Suppose Assumption [ holds for manifold M and S r/4. Then the local neighborhood Un (en,, r) NM is diffeomorphic subset of RA In particular, the orthogonal projection Pn onto the tangent space Te,, (M) is a diffeomorphism.
43

---

NeurIPS Paper Checklist
[Yes] [No] [NA]
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We develop approximation and statistical theory predicting transformer scaling laws by mathematically proving approximation and statistical theory which we validate on several pretraining datasets and scaling suites.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals 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 that our analysis does not extend analyzing benchmark capabili- ties of LLMs, which are of much interest, and identify this direction as promising future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 sell-specffication 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency 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, worse outcome might be that reviewers discover limitations that aren't acknowledged 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.
44

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We clearly state all assumptions in Section 2 and give complete proofs in the appendix.
Guidelines:
The answer NA means that the paper does 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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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 properly referenced.
4. Experimental Result Reproducibility
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)?
Question:
Answer: [Yes]
Justification: We share all our hyperparameterrs, code, data, and models publicly for 100% reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility 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.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
45

---

reproducible, they In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
We share all our hyperparameters, code, data, and models publicly for 100% reproducibility.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is 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
httc:///bbbb///ttieeee///eeuuaas Swtp///oodSSssss.eoooea wwtpsubmmmsssssnniii ssiiiioiccciiiiiiicc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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: [Yes]
Justification:
We specify all parametrs used in our experiments.
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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[No]
Justification:
We do not report error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
46

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We specificy the compute resources used to run our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary 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
Answer:
[Yes]
Justification:
We have reviewed the code of ethics and confirm we are consistent.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws 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: [Yes]
Justification:
We include discussion of broader impacts in our conclusion.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
47

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 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 to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: NA
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 is 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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, we give proper citation with urls and follow all licensing.
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 URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
48

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide full set of instructions in the released code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset 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: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According 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 or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "7Ilo9R9n4y", "reviewer": "Reviewer_TAmh", "summary": "This paper investigates the representational capabilities of transformers in regression tasks and their correlation with scaling laws. The authors present a novel analysis of the transformer's sample complexity on datasets with low intrinsic dimension $d$, or those residing on a $d$-dimensional manifold $\\mathcal{M}$. Their findings yield a bound reminiscent of standard non-parametric regression results, with the key distinction that it depends on the intrinsic dimension rather than the actual data dimension.\n\nThe analysis hinges on a specific transformer construction that performs approximation on subregions of $\\mathcal{M}$. Notably, when the model is sufficiently wide and deep, this construction can approximate the target function to $\\epsilon$ precision with a depth independent of $\\epsilon$. This characteristic contrasts favorably with feedforward models using ReLU activation, which typically require $O(\\epsilon^{-1})$ layers.\n\nFinally, the paper shows that if we estimate the intrinsic dimension of the data, the resulting estimate of the exponent can be informative of that predicted by the sample complexity from the theoretical result.", "questions": "1. Why is the intrinsic dimension dependent on the model since they are supposed to be intrinsic to the data? How do I know the approximation of it is reasonable? For example, why is \"sub-sample final-layer tokens from the embedded subsequence and shuffle together all the embedding\" a reasonable thing to do?\n\n2.  How does the computational complexity of the proposed transformer construction compare to that of the feedforward model? If the transformer requires significantly more parameters to achieve the $\\epsilon$-independent depth, does this truly represent an advantage, given that other parameters in the bound still depend on $\\epsilon$? Can you provide a more comprehensive comparison that takes into account total computational resources, including the number of parameters and operations required? Without such a comparison, it's challenging to conclude whether this result definitively demonstrates the benefit of transformers over MLPs.", "limitations": "Some limitations I discussed above are already in the paper but many are not.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "As far as I know, the theoretical result of the paper is novel and highly non-trivial. To a certain degree, it sheds light on the fundamental difference between a transformer and simpler models like the feed-forward model. I foresee these results to be useful for future research into the statistical properties of transformers.", "weaknesses": "The theoretical result is novel but I am not sure how insightful the bound of the construction is about what the model actually is doing and how the result is related to scaling law. There are several weaknesses in the paper which I will discuss below:\n\nDespite its novel theoretical contributions, this paper has several significant weaknesses that warrant discussion:\n\n1. **Limited applicability to real-world scenarios**: The theoretical model presented in the paper assumes a regression or supervised learning task, which diverges significantly from how transformer models are typically used in practice. The input representation ($x$ as a $D$-dimensional vector with the sequence being a linear transformation of $x$) also appears overly simplistic and may not adequately capture the complexity of real-world data and tasks. This disconnect raises questions about how well the theoretical results translate to practical applications.\n\n2. **Relevance of the proposed construction**: While the construction presented in the paper is mathematically interesting at a technical level, it's unclear whether it accurately represents the actual learning process of transformer models. The authors do not provide empirical evidence to support that their theoretical construction aligns with the internal representations or mechanisms developed by transformers during training. This lack of validation leaves a significant gap between theory and practice. I would be more than happy to be proven wrong with empirical evidence.\n\n3. **Tenuous connection to scaling laws**: The paper's attempt to link its theoretical results to empirical scaling laws appears weak. The predicted line for $\\alpha_D$ in Figure 2 shows a substantial divergence from actual scaling laws for most datasets, with OpenWebText being a notable exception. The claimed error margin of $\\pm 0.2$ is exceptionally large on a log-log scale, potentially overstating the accuracy of the predictions. Moreover, the fit for $\\alpha_N$ is even less convincing, further undermining the paper's claims about its relevance to scaling laws.\n\nThese weaknesses suggest that while the theoretical work presented is novel, its practical implications and connections to real-world transformer behavior may be limited. The paper would benefit from stronger empirical validation and a more thorough exploration of how its theoretical insights relate to the actual functioning of transformer models in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough response! We address some of your concerns below.\n\n**Strengths**:\n- As far as I know, the theoretical result of the paper is novel and highly non-trivial. To a certain degree, it sheds light on the fundamental difference between a transformer and simpler models like the feed-forward model\n\nWe appreciate the reviewer recognizes our theoretical result as novel and higly non-trivial and that it shed light on the fundamental difference between a transformer and simpler models like the feed-forward network. We would like to emphasize that the **main contribution of this paper is theoretical**. This includes our statistical estimation theory in Theorem 1 which  relies upon a novel and non-trivial covering number result for transformers (Lemma 2) and a novel approximation theory in Theorem 2 which is constructed from a number of key sub-lemmas (e.g. see Lemma 3 - Interaction Lemma) allowing for complex interaction of multiple tokens which is also of independent interest. We believe these results constitute a signficant step forward in the theoretical understanding of transformers\n\n**Weaknesses:**\n\n1a. Limited applicability to real-world scenarios: The theoretical model presented in the paper assumes a regression or supervised learning task, which diverges significantly from how transformer models are typically used in practice... This disconnect raises questions about how well the theoretical results translate to practical applications.\n\nDespite being proved for regression, our result also sheds light on applications using next-token prediction (classification). Theoretically it is known that results on regression problems can be used to estalish results for classification problems [2, Theorem 1.1] since classification essentially depends on estimation of the probability function for classification. This allows our results on regression for transformers to be applied to next-token prediction which translates to practical applictaions. Additionally, we remark the regression objective itself is commonly used in many real-world scenarios e.g. training a transformer diffusion backbone [1]\n\n1b. The input representation ($x$ as a - $D$ dimensional vector with the sequence being a linear transformation of $x$) also appears overly simplistic and may not adequately capture the complexity of real-world data and tasks\n\nWe note that most common real-world tasks including language modeling, which embeds an input $x \\in R^{vocab\\_size}$ via a linear token embedding matrix, and ViT, which takes an image $x \\in R^D$ and embeds it as token *patches* using a (linear) convolution, utilize this embedding strategy.\n\n2. Relevance of the proposed construction: While the construction presented in the paper is mathematically interesting at a technical level, it's unclear whether it accurately represents the actual learning process of transformer models. The authors do not provide empirical evidence to support that their theoretical construction aligns with the internal representations or mechanisms developed by transformers during training. This lack of validation leaves a significant gap between theory and practice. I would be more than happy to be proven wrong with empirical evidence... This disconnect raises questions about how well the theoretical results translate to practical applications.\n\n\nIn machine learning theory, to obtain an empirical minimizer $\\hat{T}_n$, we start with an empirical risk function (in our case mean squared error (mse) on training data) and a hypothesis function class $\\mathcal{T}$. The empirical risk minimizer (ERM) $\\hat{T}_n$ is then the candidate in $\\mathcal{T}$ which minimizes the empirical risk. Our goal is to understand how the generalization error of $\\hat{T}_n$ depends on the number of samples and the intrinsic dimesion of the data. Note that our statistical learning theory does not make any claim about how $\\hat{T}_n$ is achieved (i.e. the optimization process).\nThe generalization error can be decomposed into two parts: bias (approximation error) and variance (stochastic error). The approximation error represents the expressivity of the transformer architecture space $\\mathcal{T}$ e.g. how well can a function in $\\mathcal{T}$ approximate the target $T$. Our approximation theory results are significant because **they allow us to quantitatively and precisely control the approximation error $\\epsilon$ as a function of the transformer architecture size**. Importantly, this construction to control the approximation does not say anything about the learned parameters of the empirical risk minimizer or the parameters learned during the optimizaion process. Roughly speaking the discrepancy between the ERM and our construction is controlled by the stochastic error which we bound using the covering number of the transformer hypothesis space. We view this flexiblity as an advantage of our theory, as **we do not require the learned parametrs of the ERM to align with our construction in the approximation theory to control the ERM's generalization error**. We would further remark that this theory **does** translate to practical applications for understanding transformer scaling laws as evidenced by our experimental results on datasets similar to those used in [3].\n\n3. The predicted line in Figure 2 shows a substantial divergence from actual scaling laws for most datasets, with OpenWebText being a notable exception. The claimed error margin of $\\pm 0.2$ is exceptionally large on a log-log scale, potentially overstating the accuracy of the predictions. Moreover, the fit for $\\alpha_D$ is even less convincing.\n\nOur margin of error in Figure 2 when predicting $\\alpha_D$ is $\\pm 0.02$ (an order of magnitude lower than $\\pm 0.2$). We believe this is fairly accurate. The prediction of $\\alpha_N$ is similarly accurate (up to $\\pm 0.03$). Further this is an improvement over other empirically driven works [4] which estimate scaling laws using intrinsic dimension.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4I557QpFcA", "reviewer": "Reviewer_1VDq", "summary": "This paper makes a series of contributions:\n\n- Transformer Generalization Error: Loosely speaking, assuming a transformer is trained to approximate a Holder function in a regression setting, and assuming the data lives on the low dimensional manifold, then the generalization error of the transformer is upper bounded in a particular manner (Theorem 1)\n- New Covering Number for Transformers (although I believe this is not presented in the main text)\n- Predicting Transformer Empirical Scaling Laws\n- Some investigations into how transformer hyperparameters affect the estimated intrinsic dimensionality of text data\n\n \nI am not familiar with these more theoretical methods, and I have never taken a course on differential geometry. Consequently, my review will be quite limited. I focus more on the empirical methods since I am more familiar with these.", "questions": "- Looking at equation (3) and (4), the scaling exponents $\\alpha_D, \\alpha_N$ are partially determined by $\\beta$. Later, $\\beta$ is set to 1. How is this justified? Why would this be true empirically?\n- The paper critically concerns estimating the intrinsic dimensionality of the pretraining dataset D, but then claims this cannot be done directly for textual datasets. Why? No justification is given.\n- Following the above bullet, the paper then estimates the intrinsic dimension of the data by estimating the intrinsic dimension of the output token embedding matrix. Why is using this alternative quantity reasonable?\n- I’m not familiar with the “Maximum Likelihood Estimation ID algorithm”. What is this algorithm? Why was it chosen? How do the results depend on this choice? The ID estimation methods I'm more familiar with are quantities like participation ratio - how do other method \n- Line 71: Is the word “layers” missing? i.e. “requiring only O(log(d)) layers independent of the desired accuracy…”\n- Figure 3: Why are there 5 GPT2 model sizes? HuggingFace offers only 4. \n- Figure 3: Why are only 4 Pythia models used? I believe that there are 8.\n- What in this paper is a prediction? To me, the hallmark of a scientific prediction is a statement regarding what one should expect beyond already-existing data, followed by new experiments to confirm the new behavior. With the exception of Figure 2, I don't see much in the way of new predictions or new experiments to confirm predictions, and even Figure 2 is relatively weak in the sense of external verifiability.", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Note: I am not familiar with these more theoretical methods, and I have never taken a course on differential geometry. Consequently, my review will be quite limited. I focus more on the empirical methods since I am more familiar with these.\n\n- Having minor familiarity with Sharma and Kaplan, I think this work is a great extension towards language modeling.\n- The paper is clearly very well written and thorough\n- Figure 1 is visually nice (although I don’t have the background required to understand it)", "weaknesses": "Note: I am not familiar with these more theoretical methods, and I have never taken a course on differential geometry. Consequently, my review will be quite limited. I focus more on the empirical methods since I am more familiar with these.\n\n- “Overall, we find the estimated ID is fairly stable across each factor.” -> Looking at Figure 4, this feels very wrong to me. In 3 out of 4 subplots, the intrinsic dimensionality clearly seems to be changing with no asymptotic value in sight.\n- [nit] Figures 2 and 3: Please use a log scale. Don’t log transform the number of samples and then plot the log-transformed variable linearly.\n\nI have many questions (below) that may become weaknesses, but I don't wish to penalize the authors if I've misunderstood their work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Strengths:**\n\n- Having minor familiarity with Sharma and Kaplan, I think this work is a great extension towards language modeling.\n\nWe thank the reviewer for recognizing this work as a great extension towards lanugage modeling! However, we want to emphasize the main contribution of our work is **theoretical** (as oppsed to [1] which is empirical). Via our novel approximation and statistical theory, we are able to establish theoretical bounds on Transformer scaling laws. We then do experimentation, extending similar experiments in [1] to transformers, demonstrating this theory holds well in practice.\n\n**Weaknesses:**\n\n1. I am not familiar with these more theoretical methods, and I have never taken a course on differential geometry. Consequently, my review will be quite limited. I focus more on the empirical methods since I am more familiar with these.\n\nAgain, we would like to emphasize that the main contributions of this paper are **theoretical**. This includes our statistical estimation theory in Theorem 1 which crucially relies upon a novel and non-trivial covering number result for transformers (Lemma 2) and a novel approximation theory in Theorem 2 which is constructed from a number of key sub-lemmas (e.g. see Lemma 3 - Interaction Lemma) allowing for sophisticated interaction of multiple tokens which is also of independent interest. We believe these results constitute a signficant step forward in the theoretical understanding of transformers.\n\n\n2. “Overall, we find the estimated ID is fairly stable across each factor.” -> Looking at Figure 4, this feels very wrong to me. In 3 out of 4 subplots, the intrinsic dimensionality clearly seems to be changing with no asymptotic value in sight.\n\nSince the measurement of intrinsic dimension (**ID**) is essential to our theoretical predictions in practice, our ablations in Figure 4 are meant to demonstrate the stability of our measurements of intrinsic dimension under various **reaslistic** model hyperparameters - **not to suggest any asymptotic behavior**. In general the estimation of intrinsic dimension can be fairly noisy, depending variably even on the hyperparameters chosen in the ID estimation algorithm [1,2]. For example, [2] finds the ID of imagenet varies anywhere between 20-40 depending on the algorithmic hyperparameters used. Our estimates for the ID vary only by $\\pm 5$ units across all model parameters we considered, motivating our remark that the estimation is fairly stable.\n\n3. [nit] Figures 2 and 3: Please use a log scale. Don’t log transform the number of samples and then plot the log-transformed variable linearly.\n\nOur results show that the (squared) generalization error (**SGE**) can be bounded by power-laws in the number of samples $n$ as $SGE \\lesssim n^{-\\alpha_D}$. Then taking log of both sides yields $\\log(SGE) \\lesssim -\\alpha_D \\log(n)$ which exactly bounds the (log) SGE by the (log)-linear line in the number of samples with slope given by the scaling exponent $-\\alpha_D$. This should hopefully clarify why we plot in log-log scale.\n\n**Questions:**\n\n1. Looking at equation (3) and (4), the scaling exponents are partially determined by $\\beta$. Later, $\\beta$ is set to 1. How is this justified? Why would this be true empirically?\n\nRecall $\\beta$ represents the Holder regularity index of the target function $f$. In general we expect the target function to have some regularity as otherwise it would be impossible to estimate [3]. Assuming the output varies according to the variation of the input, Holder regularity is the proper and mostly widely considered assumption in nonparametric estimation. A Lipschitz assumption with $\\beta = 1$ implies the variation of the output for the target function is proportional to the variation of the input which is also widely used in literature. In general we are unaware of numerical methods for measuring the Holder index of the target function from samples.\n\n2. The paper critically concerns estimating the intrinsic dimensionality of the pretraining dataset D, but then claims this cannot be done directly for textual datasets. Why? No justification is given. \n3. The paper then estimates the intrinsic dimension of the data by estimating the intrinsic dimension of the output token embedding matrix. Why is using this alternative quantity reasonable?\n\nEstimating the intrinsic dimension via model embeddings is a relatively established practice [1]. Further, in the case of text we have no other choice as existing ID estimation algorithms are designed for continuous data. However this should not be taken to mean that textual data does not have low-dimensional structure. While using embeddins to measure this low-dimensional structure may introduce some noise, we expect a model (such as an LLM) to have learned good enough representations to preserve the majority of the low-dimensional structure. We do ablations at the end of the paper to examine how sensitive this estimation is to various hyperparameters and find it is relatively stable. While embeddings from any layer could be chosen, we choose the final layer to stay consistent with prior work.\n\n**Please refer to our comment for the remainder of our response**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QZDggba3bZ", "reviewer": "Reviewer_DzYy", "summary": "This document appears to be a research paper on predicting scaling laws for transformer neural networks, particularly when applied to data with low intrinsic dimensionality. Here are some key points:\n1. The paper aims to establish mathematical theories to explain and predict scaling laws observed in transformer models like large language models (LLMs).\n2. It presents both statistical estimation and approximation theories for transformers when the input data lies on a low-dimensional manifold.\n3. The main results predict power law relationships between generalization error and both training data size and network size, where the power depends on the intrinsic dimension d of the training data.\n4. A key finding is that the transformer architecture constructed in their theory only requires logarithmic depth in d, which is an advantage over feedforward networks.\n5. The authors test their theoretical predictions empirically by training LLMs on natural language datasets and find close agreement with observed scaling laws.\n6. The paper argues that the intrinsic dimension of data is crucial in determining transformer scaling laws both theoretically and empirically. It provides formal definitions and theorems around transformer networks, generalization bounds, and approximation capabilities. The work aims to bridge gaps between theory and practice in understanding neural network scaling, leveraging the low-dimensional structure often present in real-world data", "questions": "1. Can you state the process of estimating the intrinsic dimension of textual datasets which is important for your work? If the dimension depends on the pre-trained model, it seems the posterior estimate is not supering to be good and its practicability seems weak.\n2. In Theorem 1 and 2, the parameters of the network should satisfy a specific magnitude assumption, is this assumption significant and practical in applications?\n3. In figure2, only 5 points are presented in each subfigure and the x-axis’s scope is different, how does the empirical result appear in other regions?\n4. Why did you assume the Lipschitz regularity of language modeling objective equals 1? Is there any explanation for it? \n5. The results shown in figure3 seem not good so what’s the significant reason?\n6. The order of subscripts seems incorrect in Table 1.", "limitations": "1. The assumptions in the theorem seem not practical.\n2. The construction in the proof of estimation theory is hard and not practical in empirical inference.\n3. The estimation of the intrinsic dimension is not clear.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a rigorous mathematical framework for understanding transformer scaling laws, which has been a significant open question in the field.\n2. The work attempts to reconcile theoretical predictions with empirical observations, particularly in the context of large language models.\n3. By incorporating the intrinsic dimension of data, the theory provides a more nuanced understanding of scaling laws that aligns better with real-world observations.\n4. The authors test their theoretical predictions on actual language models, providing evidence for the practical relevance of their work.", "weaknesses": "1. Simplified assumptions: The theory relies on assumptions about data lying on a low-dimensional manifold, which may not always hold in practice, especially for complex, high-dimensional data like natural language.\n2. Limited scope: The paper focuses primarily on regression tasks, while many practical applications of transformers (like language modeling) involve more complex objectives.\n3. Generalizability: It's unclear how well the theory generalizes to other types of transformer architectures or variations that differ from the specific formulation used in the paper.\n4. Computational complexity: The paper doesn't deeply address the computational aspects of their proposed methods, which could be a practical limitation for very large models.\n5. Data dimension estimation: The reliability and stability of estimating the intrinsic dimension of complex datasets (like text) remains a challenge and could impact the practical application of the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Strengths:**\n\n1. The paper provides a rigorous mathematical framework for understanding transformer scaling laws, which has been a significant open question in the field. [...] The authors test their theoretical predictions on actual language models, providing evidence for the practical relevance of their work.\n\nWe are glad the reviewer recognizes our work as making progress on a significant open question in the field and that the reviewer recognizes the importance of our theory being validated with experiments on actual language models.\n\n**Weaknesses:**\n\n1. Simplified assumptions: The theory relies on assumptions about data lying on a low-dimensional manifold, which may not always hold in practice, especially for complex, high-dimensional data like natural language.\n\nThe widely supposed *manifold hypothesis* suggests that most natural data, such that images and text, lie on low-dimensional manifolds embedded in a high-dimensional ambient space. Many papers [2,3] find evidence suggesting this is true for image data and show this helps explain the success of deep-learning in learning high-dimensional data with low-dimensional structures. In particular, we and others [4,5] find evidence that low-dimensional structures exist in textual data once it is embedded by a model. (15 ID vs. 768 ambient dimension). \n\n2. Limited scope: The paper focuses primarily on regression tasks, while many practical applications of transformers (like language modeling) involve more complex objectives.\n\nDespite being proved for regression, our result also sheds light on real world applications using next-token prediction (classification). Theoretically it is known that results on regression problems can be used to estalish results for classification problems [1, Theorem 1.1] since classification essentially depends on estimation of the probability function for classification. This allows our results on regression for transformers to applied directly to next-token prediction which translates to practical applictaions. Additionally, we remark the regression objective itself is commonly used in many real-world scenarios e.g. training a transformer diffusion backbone.\n\n3. Generalizability: It's unclear how well the theory generalizes to other types of transformer architectures or variations that differ from the specific formulation used in the paper.\n\nOur theory crucially relies upon a number of key lemmas (e.g. the Interaction lemma facilitating pairwise interaction between tokens in the attention mechanism) to develop our novel approximation theory and a novel covering number result to develop the statistical theory. Both of these are general and can be extended to different transformer architectures. Further, our experimental results suggest that, despite the architectures being used in practice differing from our theory, we are still able to make good predictions about the scaling behavior of these models both in terms of the model size and the number of training samples.\n\n4. Computational complexity: The paper doesn't deeply address the computational aspects of their proposed methods, which could be a practical limitation for very large models.\n\n\nOur paper aims to predict scaling laws of transformer neural network which crucuially relies on the intrinsic dimension of training data. Typically, to estimate a scaling exponent empirically, one must pre-train a family of models across different data/model sizes. In contrast, with our theory, one only needs to pre-train a single model which can then be used to estimate intrinsic dimension from which all scaling can be theoretically predicted. In comparison with pre-training, which can take multiple weeks for the largest models, estimating the intrinsic dimension takes only a couple minutes. \n\n5. Data dimension estimation: The reliability and stability of estimating the intrinsic dimension of complex datasets (like text) remains a challenge and could impact the practical application of the theory.\n\nEstimating the intrinsic dimension via model embeddings is a relatively established practice [1,4,5]. Further, in the case of text we have no other choice as existing ID estimation algorithms are designed for continuous data. However this should not be taken to mean that textual data does not have low-dimensional structure. While using embeddins to measure this low-dimensional structure may introduce some noise, we expect a model (such as an LLM) to have learned good enough representations to preserve the majority of the low-dimensional structure. We do ablations at the end of the paper to examine how sensitive this estimation is to various hyperparameters and find it is relatively stable. While embeddings from any layer could be chosen, we choose the final layer to stay consistent with prior work.\n\n**Please refer to our comment for the remainder of our response**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gz0wnDgrBx", "reviewer": "Reviewer_e2w2", "summary": "This work derived a generalization error bound of using transformer architecture to estimate beta-Holder continuous functions. The bounds depend on the intrinsic dimension of the data. The generalization error can be decomposed into an approximation error and a variance error. They further showed that TFs with finite number of blocks can approximate arbitrary beta-Holder continuous functions up to any precision.  Both their generalization and error bound and approximation error bound exhibit power-law decay, with exponents depending on the smoothness and intrinsic dimension. Empirical results on real datasets also validated their theoretical findings.", "questions": "1. What is the number of hidden neurons in FFNs?\n2. Does the result in (3) matches the minimax lower bound for estimating beta-holder class? What is the gain of using TFs instead of simple nonparametric methods to estimate $f$?", "limitations": "1. As the author discussed, this work doesn't consider the training dynamics of the learning problem.\n2. The exponents in (3), (4) highly depend on  the smoothness of $f$ (i.e., $\\beta$) and the intrinsic dimension of the data. However, the exact value of $\\beta$ is hard to predict in practice. Is there any practical way to estimate $\\beta$?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper present novel approximation theory for transformers in terms of the intrinsic dimension.  Empirical observations are well-aligned with the theory.", "weaknesses": "1. The statement that TFs can approximate $f$ to any precision $\\epsilon$ with finite number of blocks is a bit inaccurate and misleading. Namely,  Theorem 2 assumes $L_{FFN}$ is of order $O(\\log(1/\\epsilon))$. This means in the standard TF architecture, we would have $O(\\log(1/\\epsilon))$ number of FFN-attention blocks instead of only a finite number.  It would be great if the author can clarify this point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough repsonse! We address some of your comments below.\n\n**Strengths:**\n\n1. The paper present novel approximation theory for transformers in terms of the intrinsic dimension. Empirical observations are well-aligned with the theory.\n\nWe are glad the reviewer found our approximation theory novel and our empirical findings well-aligned with our theory!\n\n**Weaknesses:**\n\n1. The statement that TFs can approximate to any precision with finite number of blocks is a bit inaccurate and misleading. Namely, Theorem 2 assumes is FFN depth is of order $O(\\log(\\epsilon^{-1}))$. This means in the standard TF architecture, we would have $O(\\log(\\epsilon^{-1}))$ number of FFN-attention blocks instead of only a finite number. It would be great if the author can clarify this point.\n\nThis is a good point, the number FFN layers per transformer block is $\\log(\\epsilon^{-1})$. However, we recall that the weight-matrices in each FFN are of constant size (5x5 since $d_{embd} = 5$) and thus the number of parameters in each FFN layers is negligible. The vast majority of parameters are used in highly-parallel attention layers of which we only need $\\log(d)$ layers. Note: a transformer *block* consists of an attention layer and then a FFN network.\n\n**Questions:**\n\n1. What is the number of hidden neurons in FFNs?\n\nThe number of parameters in each FFN is  $d_{embd}^2\\cdot \\log(\\epsilon^{-1}) = O(\\log(\\epsilon^{-1}))$. \n\nNote $d_{embd} = 5$.\n\n2. Does the result in (3) matches the minimax lower bound for estimating beta-holder class? What is the gain of using TFs instead of simple nonparametric methods to estimate $f$?\n\nYes, our bound matches the min-max rate up to logarithmic factors [1]. For Holder functions, both transformer and many nonparametric methods (kernel regression and piecewise polynomial regression) can achieve the min-max rate up to logarithmic factors. However, transformer has achived remarkable success in large language models, which makes a theoretical understanding of transformer significant and meaningful. It is well known that simple nonparametric methods can not achive the same performance as transformers in real-world applications with large scale complex data. \n\nWe believe (but have not proved) that transformer networks are more *adaptive* to the regularity of the target function at different areas of the domain. For simple nonparametric methods, such as kernel methods, often one must choose a kernel width, making adaptivity more difficult.\n\n\n\n**Limitations:**\n\n1. As the author discussed, this work doesn't consider the training dynamics of the learning problem.\n\nTo our best knowledge, the training dynamics of multi-layer transformers is an open-question. We agree studying transformer dynamics is of great interest, but this is not the goal of the current paper.\n\n2.. The exponents in (3), (4) highly depend on the smoothness of $f$ (i.e., $\\beta$) and the intrinsic dimension of the data. However, the exact value of $\\beta$ is hard to predict in practice. Is there any practical way to estimate $\\beta$.\n\nIn general we expect the target function to have some regularity as otherwise it would be impossible to estimate [1]. Assuming the output varies according to the variation of the input, Holder continuity is the proper and mostly widely considered assumption in nonparametric estimation. A Lipschitz assumption with $\\beta = 1$ implies the variation of the output for the target function is proportional to the variation of the input which is widely used in literature. In general we are unaware of any methods for measuring the Holder index of the target function from samples.\n\n\n**References:**\n\n[1] A Distribution-Free Theory of Nonparametric Regression, https://link.springer.com/book/10.1007/b97848", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper develops a theoretical analysis of scaling laws for transforms for intrinsically low-dimensional data and validates the theory via empirical observation of training LLMS on text data. The topic is salient and will be of interest to the community. The reviewers found the work novel and highly non-trivial, opening a window into the differences between transformers and simpler architectures. I recommend acceptance.
Decision: Accept (poster)