Approximation ability of Transformer networks for functions with various smoothness of Besov spaces: error analysis and token extraction
Authors: Yuki Wada
Shokichi Takakura
Taiji Suzuki
Venue: Submitted to ICLR 2023 (2023)
Keywords: Transformer
approximation error
estimation error
minimax optimal rate
besov spaces
B-Splines
adaptive sampling recovery
token extraction

Abstract: Although Transformer networks outperform various natural language processing tasks, many aspects of their theoretical nature are still unclear. On the other hand, fully connected neural networks have been extensively studied in terms of their approximation and estimation capability where the target function is included in such function classes as H\"older class and Besov class. In this paper, we study the approximation and estimation error of Transformer networks in a setting where the target function takes a fixed-length sentence as an input and belongs to two variants of Besov spaces known as anisotropic Besov and mixed smooth Besov spaces, in which it is shown that Transformer networks can avoid curse of dimensionality. By overcoming the difficulties in limited interactions among tokens, we prove that Transformer networks can accomplish minimax optimal rate. Our result also shows that token-wise parameter sharing in Transformer networks decreases dependence of the network width on the input length. Moreover, we prove that, under suitable situations, Transformer networks dynamically select tokens to pay careful attention to. This phenomenon matches attention mechanism, on which Transformer networks are based. Our analyses strongly support the reason why Transformer networks have outperformed various natural language processing tasks from a theoretical perspective.

Under review as a conference paper at ICLR 2023
APPROXIMATION ABILITY OF TRANSFORMER NET- WORKS FOR FUNCTIONS WITH VARIOUS SMOOTHNESS OF BESOV SPACES: ERROR ANALYSIS AND TOKEN EX- TRACTION
Anonymous authors Paper under double-blind review
ABSTRACT
Although Transformer networks outperform various natural language processing tasks, many aspects of their theoretical nature still unclear. On the other hand, fully connected neural networks have been extensively studied in terms of their approximation and estimation capability where the target function is included in such function classes as Hölder class and Besov class. Besov spaces play an im- portant role in several fields such as wavelet analysis, nonparametrie statistical inference and approximation theory. In this paper, we study the approximation and estimation error of Transformer networks in a setting where the target fune- tion takes fixed-length sentence an input and belongs to two variants of Besov spaces known as anisotropic Besov and mixed smooth Besov spaces, in which it is shown that Transformer networks can avoid curse of dimensionality. By over- coming the difficulties in limited interactions among tokens, we prove that Trans- former networks accomplish minimax optimal rate. Our result also shows that token-wise parameter sharing in Transformer networks decreases dependence the network width the input length. Moreover, prove that, under suitable situations, Transformer networks dynamically select tokens to pay careful atten- tion to. This phenomenon matches attention mechanism, on which Transformer networks are based. Our analyses strongly support the reason why Transformer networks have outperformed various natural language processing tasks from the- oretical perspective.
INTRODUCTION
Transformer networks, which were proposed in Vaswani et al. (2017), have outperformed various natural language processing (NLP) tasks, including text classifications (Shaheen et al.) 2020), ma- chine translation (Vaswani et al. (0117), language modeling (Radford et al.) Devlin et al. 2018)). and question answering (Devlin et al.] 2018 Yang et al.,, 2019). Transformer networks make it feasible to approximate functions which can take sequence of tokens (i.e., text) as input due to their specific architecture which stack of blocks of self-attention layers and token-wise feed-forward layers. However, despite of these great successes in various NLP tasks, many aspects of their theoretical nature still unclear.
On the other hand, fully connected neural networks have been extensively studied in terms of their function approximation and estimation capability. A remarkable property of neural network is its universal approximation capability. which means that any continuous function with compact sup- port can be approximated with arbitrary accuracy with two fully connected layers (Cybenko) 1989). However, Cybenko (1989) did not state anything about an upper bound of the network size. There- fore, a relation between properties of the target function and the network size a next question. By imposing certain properties such smoothness ral network can be studied more precisely. Barron (1993) developed an approximation theory for functions with limited capacity that is measured by integrability of their Fourier transform. Deep neural networks with ReLU activation (Narr & Hinton 2010; Glorot et al.) (0IT) has also been ex- tensively studied from the viewpoint of the approximation and the estimation ability. For example,
target functions, the representabiliy of neu-

---

Under review as a conference paper at ICLR 2023
Yarotsky (2016) proved the approximation error of fully connected layers with the ReLU activa- tion for functions in Sobolev spaces. Schmidt-Hieber (2017) derived an estimation error bound of regularized least squared estimator performed by deep ReLU network based on an approximation error analysis in a regression setting. [Suzuki (219)) derived approximation and estimation error rates of fully connected layers with ReLU activation for the Besov space, which were also shown to be almost minimax optimal. Although the derived rates of convergence are almost optimal, they suffer from the curse of dimensionality, which is one of the main issues of machine learning. A typical consequence of the curse of dimensionality is that, when the dimension of data increases, the approximation accuracy (and estimation accuracy) deteriorates exponentially against the dimen- sion. However, under some specific structure on the data and the target function, we may avoid this issue. Indeed, [Suzuki (219) Suzuki Nitanda (202T) showed that, by assuming that the target function has mixed smoothness or anisotropic smoothness, we can avoid curse of dimensionality. Okumoto & Suzuki (2022) derived approximation and estimation errors in a severe setting in which input data are ciiiittt-dimsionall
Although many researches on the representation ability of fully connected layers and convolution layers are developed, relatively few researches that of Transformer networks found. Kratsios jet al. (202l) proved that there exists a pair of an input sequence and output particles which mini- mize given proper loss functions under given constraint set. /uckkvic (2020) proved that, when regarding attention layers as functions from measures to measures, attention layers have the Lips- chitz continuity property from a viewpoint of Wasserstein distances. Both Kratsios et al. (202I) and Vuckovic (2020) regard an input sentence as a measure, that is, particles or a bag of words, which is an interesting viewpoint. However, these papers do not specify how approximate Transformer net- works are to a given function from an input sequence to an output. Therefore, these papers' results are different from this paper's main purpose to explain why Transformer networks can outperform various NLP tasks represented by target functions in various function spaces. Yun et al. (2000), (Za- heer et al. (020) SSi et al. (202T) proved that Transformer networks are universal approximators of sequence to sequence functions. However, since these papers did not assume smoothness of the target function, the results of these papers did not specify an upper bound of Transformer network depths, which corresponds the fact that universal approximation capability of neural networks did not state anything about an upper bound of the network width. Thus, this paper studies a question which naturally arises as to how properties of the target function are related to the network size and precision required.
In this paper, we study the approximation and estimation error of the Transformer architecture in setting where the target function takes a fixed-length sentence as an input and belongs to a mixed smooth Besov space and an anisotropic Besov space. We prove that Transformer networks accom- plish almost minimax optimal rate by analyzing the Transformer network architecture and approxi- mation ability of the two function spaces. Moreover, we prove that, under suitable situations, Trans- former networks can dynamically select tokens to pay careful attention to. The essence of the proof strategy as follows: First, for a given target function, we obtain a sum of piece-wise polynomial functions which is approximate to the target function in certain rate. Next, one constructs neural network approximate to piece-wise polynomial functions. Finally, one constructs a neural network approximate to the sum. The problem is the second phase in which one constructs neural network approximate to a cardinal B-spline function. The proof of the phase is based on fully connected layers approximate zy in Yarotsky| (2016). However, Transformer networks limited interactions among tokens. In this paper, we propose how to construct an attention layer which values exchanges between different tokens. By using attention layers constructed above, we can construct Transformer network approximate to cardinal B-spline function. This difficulty is common to previous papers (Yun al. 2020, Zaheer al., 2020 SShi al., (02T). though their strategies of obtaining a piece-wise constant approximation are different from ours in a viewpoint of exploitation of function smoothness.
permitted to do
Our contributions can be summarized as follows:
1. We consider a situation in which the target function takes fixed-length sentence as an input and belongs to a mixed smooth Besov space and an anisotropic Besov space, in which is shown that Transformer networks can avoid curse of dimentionality and accomplish almost minimax optimal rate. We also shows that token-wise parameter sharing in Transformer networks decreases dependence of the network width on the input length.
2

---

Under review as a conference paper at ICLR 2023
2. We prove that, under suitable situations, Transformer networks dynamically select tokens to pay careful attention to. Moreover, we show that the count of tokens to pay careful atten- tion to is decided by an NLP task, and the accuracy required. This phenomenon matches attention mechanism, on which Transformer networks are based.
2 NOTATIONS AND PROBLEM SETTINGS
In this section, we define the notations and introduce the problem setting. Throughout this paper, we use the following notations. Let X be finite set. Then we shall write :X for the cardinality of X. Write E for the ring of rational integers and I for the field of real numbers. Let A E {Z, R and a E A. Then we denote by A>a == {a' E A a' > a}, Aza = {a' E A a' 2 a). Let S S Rd
be a domain of the functions. For a function f Ω R. let I|I = || (F()) = (Jn 1/Idxx)
for 0 < p < oo and | lox = Il == sup.en [f()) for p = xc. For a E B p E R we
denote by ||α||p (Ein la:1") ||al| max a ||al|o = 2 S i d. a, + 0).
For a B500 we denote by ā == max(a), a == min(a), ā := (I
For a 2
الداا1 we denote by D= == Io J f()). We also define some utility functions as follows: Let E IR. Then we denote by x++ == max(r, 0), x V max(x, v). [x] == min E 2|n S x).
[x] = max(n E Z|n 2 2).
In the following subsections, the function classes for which we develop error bounds, and the set of Transformer networks with given paperrppramtters.
2.1 MIXED SMOOTH BESOV SPACE
In this section, we define the mixed smooth Besov space, one of the function classes which we discuss. To define the mixed smooth Besov space, we first introduce the modulus of smoothness.
Definition 1 (r-th modulus of smoothness). Let Ω be a measurable subset of RP, p Rso U {oo} and r E Z211 For a function f E (2( and t Ryg the r-th modu- lus of smoothness of is defined by wx,(ftt) (-())) jh) (x Ex Q2 rh E 2). (otherwise).
suppaise. (1A)(f)) where (f)()(x) =
Next, based on the modulus of smoothness, we introduce the notion of mixed modulus of smooth-
Definition 2 (Mixed modulus of smoothness). Let d Zz1. Ω be measurable subset of I2 BsoU r E zd h E IRd, and function E Lp))). Then define the coordinate difference
I4-1, operator as follows: (f)x) == -ii,,,,.,,,I,,,,' Fit1,-.... (xa) Accordingly, for
e fl...... we define the mixed difference operator (f) = M REE
(F)
(e 0)
{f
(c 0)
(note that, for any i # j. Ai A A A and the r-th mixed modulus of smoothness of w (f,() = sup || T. (fIlp
Finally, based on the mixed modulus of smoothness, the mixed smooth Besov space is defined as in the following definition.
Definition 3 (mixed smooth Besov space). Let E A21, Ω be measureable subset of TRd,, p. q E Ry0 (oo),a a RRS.." r = [o] + 1. S (1....,d) dd. Then, for S (1....,
.......d, d), we define the
seminorm lang.e as follows:
Ifl 1flMBSS == (Lo 1 juc (f,t)) Nl.c (i )
(q o0),
( " (Wwp)
(g oo).

---

Under review as a conference paper at ICLR 2023
Note that If Ma r The norm of the mixed smooth Besov space M p.g.g can be defined as the sum of the semi-norm over the choice of e by I1fll == Eeg(i.... M and we define
E M B, (9t) ( E LP(9) < <00), = {f M (0) (1) 13.
The mixed smooth Besov space originally introduced by Scchmeisser 1987; Sickel & Ullrich (2009). Various researches showed that an appropriate estimator for these models can avoid curse of
(uzuki (001/ al. 2016). The relation between mixed smooth Besov spaces and ordinary Besov spaces, the definition of which found in Gine & Nickl (2015); Suzuki (019). can be informally explained follows. mixed smooth Besov space consists of functions for which the "maximum" of the orders of the derivatives "bounded": maxa=n D f while an ordinary Besov space consists of functions for which the "sum" of the orders of the derivatives is "bounded" _]a]] D J. This difference directly affects the rate of convergence of approximation accuracy (Düng et al. (2016); /uzuui (2019)), but, for this reason, mixed smooth Besov spaces do not include ordinary Besov spaces in general.
dimensionality (Meier et al. [2099] Raskutti et al. 2012 Kanagawa et al.] 2016;
2.2 ANISOTORPIC BESOV SPACE
In this section, we define the anisotropic Besov space, the other of the function classes which discuss. Here we define the anisotropic Besov space as follows.
Definition 4 (Anisotropic Besov space). Let d E Zzz,, Q be a measureable subset of Tr P. q E Ry0 U foo), E Rd Ro r == max((a:) + Then we define the seminorm -laa,, as follows:
(2 ( 4 ....,
04 2
(g oo).
IfIABE p.
(2 w (J, (2 ai ,.....,?
= (g=
The norm of the anisotropic Besov space ABp (9t can be defined as || = |1 +
|S Mlaag and we define
AB%
(0)))(())== (S)) = {f (1)]IIIIIA < <oo), p.q (S2) = { AB (9) $1}.
The statistical analysis on an anisotropic Besov space can be dated back Ibragimov & Khas' minskii 1984). who considered an estimation of a density function which is assumed to be in- cluded in an anisotropic Sobolev space with p S 2. Afterwards, several studied have been conducted from the viewpoint of non-pann paraameett statistics, such as nonlinear kernel estimator (Kerkyacharian et al. 200T), and kernel ridge regression (Hang & Steinwart 2018).
Here, we present some relations with anisotropic Besov spaces and other function classes. First, if Q1 =.. Po then follows from the definition of anisotropic Besov spaces that anisotropic Besov spaces are equal to oridinary Besov spaces with smoothness parameter a. Hence, the defini- tion of anisotropic Besov spaces includes that of the ordinary Besov spaces as a special case, while the definition of mixed smooth Besov spaces do not include that of the ordinary Besov spaces in general. Moreover, anisotropic Besov spaces are closely related to Hölder spaces. We present the definition of Hölder spaces follows.
Definition 5 (Hölder space). Let E Rso such as a & N and we denote by m := [a]. For an m times differentiable function f Rdd R. let the norm of the Hölder space (9)) be lfllc.. = 18"d f(a)-8"4 f(w)l Then, (a-)Hölder space Ca is 1
max/jnall Sm _| f loo + maaxl/aall =m supx,en defined as Ca (R) {f1llflle, < <c)..
Let P E RSe E IR and dg E Rso such that ā > J. and we denote by a' :=
To)T. Then, Triehel 2011) shows that ABa' 20,00 = Co. AB + CO This result shows that, the average smoothness is sufficiently large (ā > 1), then the functions in AB are continuous. However, can be shown that, if it small à < p ), then they are no longer continuous. Actually, there exists functions in which spikes and jumps appear (see Donoho & Johnstone (1998) for this perspective, from the viewpoint of wavelet analysis).
p
4

---

Under review as a conference paper at ICLR 2023
2.3 TRANSFORMER NETWORKS
In this section, we define the set of Transformer networks with given hyper-parameters such as fully connected layer count, transformer block count, layer width, etc. Let us denote Mat(R", Rd)) by the set of linear transformations from R' to R for any f Rd + R the function IT)) (RRd) + (R by (z) = (f(zz)); for any k E (RR4), , the attention func- tion Attn (R4y (R x (R - (R") by Attn (ettnv,k,g)) k) = (E 2/ 2/ Ei expl (xp)( by DAttn(a;; MR. Mq, My, Mo) == Mo Attn([I(MM)) ) (x), II (z), (M) for any
exp((kk,..))
PE E (, the concatenation function Concat (oncat(Pe]: (R + (IR by Concat[PE](e :=
r
and the head function Head : (R-y + Rd by Head (z) := 21.
Pe
6 (Transformer networks). Define the transformer architecture TN T, E. W, H. B) with dense layer count L, transformer block count T, width W. head count H, sparsity constraint S and norm constraint B recursively as follows:
Definition
FL(W, S, B) = (f(x) == x (M (x4)+b)) b) E
||M|| + |bb||o S S. v |10ll S BB),
FN(L,W B) = ( o...o f()) p( FL(WW, Bi), Ei Si S maxisiieL Bi S B).
AL(W, H. B) =+ DAttn v; K M (M) ) M
(h) M//) (IMM) (1)
th) Mat(W, W). W))..E(K..VV.)) E (IIM, (l0) (10) S max ISHSH (E(K.Q.V.))
1100 S B}. (lx))
B TL W,,,H,,,,... B) (I[ o fls AL H, B,,,, EN W, S2, B2),
E. 8; S S, m, B].
STL(L,T, W, H, H, ( o f (() TL(,,, W, H, St, Bd),
EL L < L, Σ S: < S, max Bi S B}.
TN(L, F. W, H,S, B) = (Head f Concat Pæ] PE (R f e LL, T, W, H1, S1 + PP PPll B).
We incorporate the architecture proposed in Vaswani et al.) (2017) into our definition of Transformer networks. We denote FL by the set of a single fully connected layer, FN by the set of stack of fully connected layers, AL by the set of multi-head attention layer. TL by the of a Transformer block which composes of multi-heat attention layer and a stack of fully connected layers, STL by the set of a stack of transformer blocks, TN by the set of an overall Transformer network with positional encoding. Note that, in order to exaggerate a count of interactions among tokens, we define a Transformer block as concatenation of multi-head attention layer and stack of fully connected layers, not single fully connected layers.
3 APPROXIMATION ERROR ANALYSIS
In this section, we evaluate how well the functions in mixed smooth Besov and anisotropic Besov spaces can be approximated by Transformer networks. To evaluate the accuracy of the deep neural network model in approximating target functions, we first define the worst case approximation error. Definition 7 (Worst case approximation error). Let d E Z2,, E Ryo U {oo} and F, H be subsets of measurable functions on Q TR.)) Then we define the worst case approximation error as follows:
(F, H) == sup inf Ilf - ffll
feE
Note that F is the set of functions used for approximation, and H. is the set of target functions.
Here, we present the results on the approximation ability.
Theorem (Approximation ability for mixed smooth Besov spaces). Suppose that 9. E Ryn U
{oo}. E (Rdy,m m E Zz1. Let 6 = ( - (note that 5 > 0 is equivalent to < r) and assume that ă 0, ā < min(m,
)
5

---

Under review as a conference paper at ICLR 2023
Then, for K parameters
Ez1. there exist absolute constant C E Ry0, constants which define hyper-
(r S p);
1 d'' -1-11 (1 1+ d'
k
d'-1
min (1
Di.d' ==
17 ==
7
(p < r and r < 00):
k
(p < r and r 20);
9
8 8
K" = [[ + v 1) ,N N = (2 (1 (1-2 2ー21-1)2 ,
v:= 28
c: 2 [2+ (1+ ( -2) )x, TTo = [log 11, I1 C c|10g
log (?a1)
Adl
)
41 3avm
Lg = 3 log2
+5 (dV m)] Lg = C log
EC(d.m)
Wo == 6dm((m +2) + 2dl
and hyper-paramettes of the set of Transformer networks
T = To; E = 1, H = 1, L L1 L2 T(L
1,W = WoN E,
: C(NI+ + L1) + L2 W N + CTo((N + E)+ + L3) N, B, -
such that
(N, T, E, W. H.S, B), MUpp,((0 11 ) 2- D2
Theorem 2 (Approximation ability for anisotropic Besov spaces). Suppose that p. P.q.r E R2o {o0), a E (Ro), m Zz1- Let ā = (t + (note that ō > 0 is equivalent to p < r) and assume that < ā, ā < min(m, m - 1 + }
Then, for K E Ezi. there exist absolute constant C E Ry0, constants which define hyper- parameters
8 K* = [K(I+ 1)1 N = (2+ + (1 1 2 ")
v:= 28
E e: Ñ (a+(1+v 1)( -2)+) To == flog 17 L1 = =c
c[og log
4ell )
41. 3dvmm
[67g
L2 = 3 2
loga
+ [ogg (d V m)1 Lo = C log
(C((.m)
Wo == 6dm(m + 2) + 2d
and hyper-paramettrrs of the set of Transformer networks
T : T:TT, E= = 1, = L, L2 + T(L 2) + 1, = WoN + E,
S: = C(NI+ + + L2WNN + CTo((N + E) + I2) + N, B S )(+
)(( de va)
such that
R (,,NLL,,,,,,HH B), AUR p.o (10, 11 $ Ñ-
The proofs of these theorems provided in Appendix D Note that the upper bound in the inequal- ity of Theorem [ depends only on Dx.at at (Dx,a mildly depends on d and 7) and the upper bound in that of Theorem 2 does not depend d or I. This means that if the target function is included these function classes, we can ease the curse of dimensionality. Moreover, thanks to the token-wise parameter sharing property in Transformer networks, the width of the network architecture does not depend on the input length I, but only on the feature dimension d. Thus, our result also shows that the extent to which the network width and the approximation error upper bounds depend on the input length can be relaxed. Hence. Transformer networks are more efficient in a network size than fully-connected layers (See Suzuki (2019) and (uzuki & Nitanda (202T)).
We give the following approximation bound by using adaptive sampling recovery method developed by (Dūng [0] The key point of this technique is that, instead of the whole set of the basis functions, functions. If the target function belongs to mixed smooth or anisotropic Besov spaces, we can use this adaptive technique. Therefore, we deal with the variants of Besov spaces in this paper.
Remark 1.
adaptively select much smaller functions from the whole set approximate
6

---

Under review as a conference paper at ICLR 2023
4 ESTIMATION ERROR ANALYSIS
In this section, we connect the approximation theory to estimation error analysis. First, we define the settings in the non-parametric regression model: Definition 8 (Non-parametric regression model for statistical analysis). Let fo 1jqy R be a measurable function and
yi = fz
where 24 Px with densiry function 0 S p(a) < R on (I0, 17 and & N(0, o²). We denote the training data D,, == (Fi, 1= which are independently identically distributed. Here, we define a regularized learning estimator as follows:
argmax
( f(x)))
L.
where J is the clipping of defined by f == min manxmax F} F) for F > which realized by ReLU units.
In practice, it is hard to exactly compute in the definition above. Therefore, there are numerous researches which study how to approximately compute f by applying sparse regularization such as L regularization and optimal parameter search through Bayesian optimization. In this study, we assume that the optimal solution is computable. Thus, we can assume that f in the definition above is valid.
Here, we provide the estimation error rate of deep learning to estimate functions in Besov spaces by using the approximation error bound given in the previous sections.
Theorem 3. Suppose that p.g g 1200 U (20), (RSD). ff E MB n L (S2) and || S 1 and || S F, then letting (L,T, E, W, H, be in Theorem 7
obtain
ED, (1f--llaaae
In=aa -2 log(n)
2id 1at-1X9+4)+0
where 1) = Up.g. as the notation of Theorem) 7
Theorem 4. Suppose that P,9 E Rso U foot,a E (RS f E AB n ( and obtain
|I I and || S F, then letting (L,T,E,,,H, H, be as in Theorem we
22 ED.. (115- (Iea(p)))) -n 2641 log(n) 1-20
65
The proof' are given in Appendix D The condition || S F is used to fill gap between the empirical L2-norm and the population L²-norm. A key factor these results fact that complexity of Transformer networks is not so high as that of fully connected layers to some extent. By combining this fact and the approximation error analysis in Section 3 the above estimations follows. Note that the dimensional parameters d, do not appear in the exponent of in the upper bounds, but only in the exponent of log(n) term. Thus, the risk bound (Theorem 3 and Theorem 4h indicates that curse of dimensionality can be relaxed in the two variants of Besov spaces. We that there does not appear d, directly in the exponent of the convergence rate (although it appears in the poly-log
for the mixed smooth case). Instead, the rate is mainly characterized by a, a. This means that the curse of dimensionality is eased by utilizing the smoothness structure of the true function fo.
Remark
According 10
Suzuki
2019 2/5
and Suzuki & Nitanda 2021
(og(n)1-2 12 in the case of mixed smooth 3 anddF we show that Transformer networks accomplish almost minimax optimal rate up to a poly-log(?) (n) order, and, especially, under the conditions of p < and 1/2 - 1/q > O, accomplish almost minimax optimal
inf, sup ED. (115 -110-fflra(P)) Z
2011
Besov spaces and anisotropic Besov spaces holds. Thus, by combining Theorem
rate up log(n)3 order.
Thus, Transformer networks have the potential to best fit the target function in either mixed smooth Besov spaces anisotropic Besov spaces among all estimators. Note that it has been already shown
7

---

Under review as a conference paper at ICLR 2023
in Suzuki (0019 and Suzuki & Nitanda [202] that fully connected layers achieve almost minimax optimal rate. Therefore, by Definition 6 it is intuitively true that Transformer networks also achieve almost minimax optimal rate. The important thing is that we prove that Transformer networks are more efficient than fully connected layers in setting where this intuition is true. For an instance, the extent which the network width and the approximation error upper bounds depend the imput length can be relaxed, as we show in Section
5 TOKEN EXTRACTION
In this section, we discuss the token extraction property of Transformer networks. First, we introduce new function class which a variant of mixed smooth Besov spaces to express a situation which Transformer networks dynamically select important tokens for an input sequence.
Let 22, S2 C IRd and Ω = Ui=1 Qr and a; E 2 where Ω2 Q are written as II L when 1; == [a: by]. [as, b.). (ag, by]. or (at, b.). We denote partition of S π == (22,) and piecewise smoothness as a == (a:). Then, the norm of the variable mixed smooth Besov space V B (St) can be defined as follows:
Definition 9.
fl (
and we define
VB (9) = {f L' <0)), (Ug = (f E ( $
Intuitively, the target function in the variable mixed smooth Besov space changes direction to regard as important or as a noise, according to an input. For each region Ω4 a corresponding smoothness parameter a; decides whether direction is important or noise. By regarding each direction as a token, we can express that the target function decide which tokens to pay attention to, for input sequence (or of input sequences).
Next, we introduce input quantization masks. Input quantization masks are used to cut off informa- tion of masked tokens to specify that Transformer networks extract much more information from non-masked tokens and much less information from masked tokens.
Definition 10. Let t, u E Zz1. Then we denote as Qt,u the set of input quantization masks f as follows: there exist a partition π. (S4) and subsets Sk .1,2 such that &Sk S t,
Fig [
E.4, E Sx)
(xr E L4,i $ Sx) By using the definition of the set of input masks, we define the set of transformer networks with input mask as follows:
f(x) = -xx;)I(x) where I(x,j): =
M.N.:.L..TE.WWWH......
(fo TN(L,T, W. H,
21,a).
Intuitively, masked tokens have much less information than non-masked tokens because masked tokens are rounded up by multiples of u. For example, when u = 2, Tij E (0, 1/2] are rounded up that this round-up quantization cut
to 1/2, and æıj (1/2, 1] are rounded up 1. Hence, off much information of original tokens. Note that the higher the parameter u is, more roughly an input value is rounded up (or quantized). The parameter u. in the definition is needed for certain technical reason. The reason is why we use cardinal B-splines (which is not a constant function but piecewise polynomial) to approximate the target function in this paper.
By using the definitions above, we can present the main result in this section.
Theorem (Token extraction property of Transformer networks). Let s E R Rsivg, (2x)) a = (ak), = (ax) where ag (RR& and σ be a permutation on (1,2,...,4y Moreover, we assume that r 2 and (ak)iz 2 (0)(f)-1 Then, for K E Zz21, letting (I, T, F, W, H.S, B) be as in Theorem there exists constants = holds:
logt +K) and == =2 such that following estimation log
R2 (MTN an (L, F. H.W.H.S. H. B), VUR (10, 1) $ 2-k DTV1
8

---

Under review as a conference paper at ICLR 2023
The proof is given in Appendix E First, we explain the role of variable mixed smooth Besov spaces. Variable mixed smooth Besov spaces can be regarded as the set of target functions which, for an imput sequence (or set of input sequences) decide which tokens to pay attention to. Smoothness parameters oz E (IR have control over this token selection process. For example, let us consider text classification task. When classifying text "FRB is stepping up its battle inflation" to finance category, we will pay attention to the first word "FRB" and the eighth word "inflation", and, when classifying text "Moreover, borrowing costs are going sharply higher" a finance category, we will pay attention to the second word "borrowing" and the third word "inflation". Therefore, variable mixed smooth Besov spaces can grasp how a task decide which tokens to pay attention to. Under the settings of Theorem 5 the smoothness parameters (au))ij increases with respect to a(j) an exponential order. This means that the importunce of token j by token i exponentially decays under an appropriate permutation oR which can depend on the input z. Then, Theorem [ shows that the Transformer can detect the input-dependent importance between tokens and achieves the addaptive rate which cannot be obtained by imposing fixed smoothness over the entire input z.
Next, we explain the role input quantization masks. Note that the range of masked token fea- ture values is {0, 1 at uutu...... u...... 1 3. 1), while the range of mon-masked token features is [0, 1]. Thus, the cardinality of the range of masked token feature values is finite while the cardinality of the range of non-masked token feature values uncountably infinite. Hence, masked tokens have much less information than non-masked tokens. Thus, input masks expresses a situation in which Transformer networks extract much more information from non-masked tokens and much less in- formation from masked tokens. As mentioned above, the parameter u in the definition is needed for certain technical reason. In this paper, we use cardinal B-splines (which is not a constant func- tion but a piecewise polynomial) to approximate the target function, and, since piecewise constant functions are needed to approximate cardinal B-splines, input masks need quantization. Actually, since Okumoto & Suzuki 20222 considered a space of functions which are (possibly infinite) sums of finite products trigonometric functions, this technical problem did not occur Okumoto & Suzuki (022)..
Consequently, MTN, in Definition I0 can be regarded as the set of transformer networks which, for an input sequence (or set of input sequences), fully exploit at most t tokens" features of an input sequence.
Thus, Theorem 5 shows that, for general NLP task and accuracy required, Transformer networks can dynamically select f tokens to pay careful attention to (a value decided by the target function which represents the NLP task and the accuracy required). This token selection property matches attention mechanism, on which Transformer networks are based.
6 CONCLUSION
This paper investigated the learning ability of Transformer networks when the target function is in mixed smooth Besov spaces or anisotropic Besov spaces. By overcoming the difficulties in lim- ited interactions among tokens, we show that Transformer networks can adaptively avoid curse of dimensionality and accomplish minimax optimal rate. Our result also shows that dependence of the network width on the imput length and the approximation eттоr upper bounds can be relaxed, thanks to loken-wise parameter sharing in Transformer networks. Moreover, we prove that, when the smoothness parameters Osj increases in an exponential order of a permutation of the token location j. Transformer networks dynamically select tokens to pay careful attention to. This phenomenon matches attention mechanism, and the result suggests that this favorable property is derived to the architecture of Transformer networks. Our analyses strongly support the reason why Transformer networks have outperformed various natural language processing tasks from theoretical perspec- tive.
This paper did not discuss the optimization aspect of networks. In this paper, we assume that the op- timal solution of regularized least squares are computable. For future works, would be interesting to incorporate non-convex optimization techniques into our study.

---

Under review as a conference paper at ICLR 2023
REFERENCES
A. R Barron. Universal approximation bounds for superpositions of sigmoidal function. 1EEE Transactions on Information theory, 39(3):933-99)) 945, 1993.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems, 2(4):303-314, 1989.
D. Düng. Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34(1): 1-41, 2011a.
D. Düng. B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness, Journal of Complexity, 27(6):541-567, 201 1b.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: pre-training of deep bidirectional trans- formers for language understanding. arXiv preprint arXiv:1810.04500 2018.
R. A Vore and V. A Popov. Interpolation of besov spaces. Transactions of the American Mathe- matical Sociery, 305(1):397 414, 1988.
R. A Vore G. Kyriazis, D. Leviatan, and V Tikhomirov. Wavelet compression and nonlinearn- widths. Advances in Computational Mathematics, 1(2):197-214, 1993.
D. L. Donoho and Johnstone. Statistics, 26(3):879 1998.
Minimax estimation via wavelet shrinkage. The Annals of
D. Düng, V. N Temlyakov, and T. Ullrich. Hyperbolic cross approximation. arXiv preprini arXiv:1601.03978, 2016.
Dinh Düng. On recovery and one-sided approximation of periodic functions of several variables. In Dokl. Akad. SSSR, volume 313, pp. 787-790. 1990.
Dinh Düng. On optimal recovery of multivariate periodic functions. In Satoru Igari (ed.). ICM- 90 Satellite Conference Proceeding, pp. 96-105. Tokyo, 1991. Springer Japan, ISBN 978-4- 431681 1816677.
Dinh Düng. Optimal recovery of functions of a certain mixed smoothness. Vietnam Journal of Mathematics, 20(2): 1992.
E. Gine and R. Nickl. Mathematical Foundations of Infinite-Dimensionne Statistical Models, volume Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, 2015.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 315-323. 2011.
H. Hang and Steinwart. arXiv: 1810.0023, 2018.
Optimal learning with anisotropic gaussian svms.
arXiv preprint
I. lbragimov and R. Khas' minskii. More on the estimation of distribution densities. Journal of Soviet Mathematics, 25(3):1155-116) 1984.
H. Kanagawa, T. Suzuki, H. Kobayashi, N. Shimizu, and Tagami. Gaussian process nonpara- metric tensor estimator and its minimax optimality. In Proceedings of the 33rd International Conference on Machine Learning (ICML2016), pp. 1632-1641. 2016.
G. Kerkyacharian, O. Lepski, and D. Picard. Probability theory and related fields. arXiv preprint arXiv:1601.03978. 137-777137-170, October 2001.
A. Kratsios, B. Zamanlooy, T. Liu, and I. Dokmanić. Universal approximation under constraints is possible with transformers. arXiv preprint 10.v:2/10003330: 2021.
L. Meier, S. van de Geer, and Bühlmann. High-dimensional additive modeling. The Annals of Statisties, 37(63)3377-3381, 2009.
10

---

Under review as a conference paper at ICLR 2023
V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In In Proceedings of the 27th International Conference on Machine Learning, pp. 807-814. 2010.
S. Okumoto and T. Suzuki. Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness. In International Conference on Learning Represen- tations. 2022.
A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever. Improving language understanding by generative pre- -raitrni.
G. Raskutti, M. J Wainwright, and B. Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. The Journal of Machine Learning Research, 13(1): 389 427, 2012.
H-J Schmeisser. An unconditional basis in periodic spaces with dominating mixed smoothness properties. Analysis Mathematica, 13(2):153-168, 1987.
J. Schmidt- Hieber. Nonparametric regression using deep neural networks with relu activation func- tion. ArXiv e-prints arXiv:1708.088 06633, August 2017.
Z. Shaheen, Wohlgenannt, and Filtz. Large scale legal text classification using transformer models. ArXiv preprint, arXiv:2010.1220 128711 2020.
H. Shi, Gao, X. Ren, H. Xu, X. Liang. Z. Li, and J. T. Kwok. Sparsebert: Rethinking the impor- tance analysis in olffaateetion. in international conference on machine learning. In Proceedings of the 38th International Conference on Machine Learning, pp. 9547-9557. 2021.
W. Sickel and Ullrich. Tensor products of sobolev-besov spaces and applications to approxima- tion from the hyperbolic cross. Journal of Approximation Theory, 161 2009.
Smolyak. Quadrature and interpolation formulas for tensor products of certain classes of func- tions. In Soviet Math. Dokl, volume 4, pp. 240-243. 1963.
T. Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionalityy In International Conference on Learming Representa- tions. 2019.
Suzuki and A. Nitanda. Deep learning is adaptive intrinsic dimensionality of model smoothness in anisotropic besov space. In Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
T. Suzuki, H. Kanagawa, H. Kobayashi, N. Shimizu, and Y. Tagami. Minimax optimal alternat- ing minimization for kernel nonparametric tensor learning. In Advances In Neural Information Processing Systems, pp. 3783-3791. 2016.
V.N. Temlyakov. Approximation of periodic functions of several variables with bounded mixed difference. Math. USSR Sb. 41(1):53-66, 1982.
V.N. Temlyakov. Approximation of Periodic Functions. Nova Science Publishers, 1993a.
V.N. Temlyakov. On approximate recovery of functions with bounded mixed derivative. Journal of Complexity, 9:41-59, 1993b.
H. Triebel. Entropy numbers in function spaces with mixed integrability. Revista matematica com- plutense, 24(1):169-188 2011.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N Gomez, L. Kaiser, and Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998-6008. 2017.
Vuckovie, mathematical theory of attention. ArXiv preprint arXiv:2007.02870 2020.
Z. Yang, Z. Dai, Y. Yang, J. Carbonell, R. Salakhutdinov, and Q. V. Le. Xlnet: Generalized autore- gressive pretraining for language understanding. ArXiv preprint arXiv: /06.08800 2019.
11

---

Under review as a conference paper at ICLR 2023
D. Yarotsky. Error bounds for approximations with deep relu networks. CoRR, abs/1610.01145, 2016.
C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar. Are transformers universal approx- imators of sequence-to-sequenee functions? In Proceedings the International Conference Learning Representations. 2020.
M. Zaheer, G. Guruganesh, A. Dubey, Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q Wang, L. Yang, and A. Ahmed. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, pp. 17283-17297. 2020.
A DEFINITION AND VARIOUS RESULTS ON THE CARDINAL B-SPLINE
Here, define the cardinal B-spline and present auxiliary lemmas. If the target function belongs to various Besov spaces Vore & Popov 1988 De et al. 1993 Düng 201 we can obtain its B-spline interpolant representations. Thus,
that approximation of function in various Besov spaces can reduce to an approximation the cardinal B-spline.
Definition (Cardinal B-spline). We define the cardinal B-spline of order m as follows:
(1 (x E 0))
N(x) = 00
(x $ 0J)
f(x - t)g(t)dt is and No(x) == Nxx,, ( = Nm((x) * (xx) where (f * ()) = fax
convolution of and g.
Let E Z21,k, E 2
Then we define
(x) = II Nm((a))
i=1
ME, (2) = Mo,0 (2 x2 - je).
Jul (k) = (-m,- (mm 1)..... 2 - 1,2 x {-m, -(m 1),...,2t4. -,, 2ka4 Lemma (Property of B-splines). I 1 S and, if m 2 1, Nm are 1-Lipschitz || 5 1 and, im 2 1, Md, are d-Lipschitz.
Proof. If m 0, it clearly follows from the definition of N that Ml S 1. If 2 follows that
[Wmllz= = sup FER
/
Nm Nm 1)((()) s sup ZER R
/
(N(I)a)) =1,
and
(m(xi) - (22) = (Wm-1 -) - -Nm-11 1))
< |2| x2l 1 -V(ejct) = =121 -221-
Thus, clearly follows || | 1m $ and
|Mo (21) Mo, L0
Σ
II Nm((21))) )+) (m)(()))))) -N
II
Nm(((12):)
Isisa 15s5i-1
it1SiEd
Σ 15idd
(a1); (x2)d s -d11 x2lloo
12

---

Under review as a conference paper at ICLR 2023
Lemma 2 (L" norm of linear combination of B-splines), Let d Σz1. K. I'zo- and :=
Ej 9j My k.j linear combination of B-splines. Then we estimate the IP norm of the linear combination f as follows:
|| ~
118111
Σ
lsp
SEJm (k)
The proof is found Suzuki (2019)
B SUB-NETWORKS
Here, present auxiliary lemmas, which are used to sub-networks of which Transformer networks compose. A key step to show the approximation accuracy is to construct a ReLU neural network which approximate the cardinal B-spline with high accuracy. By using the technique developed by Yarotsky (2016), we can construct fully connected layers with ReLU activation functions to approximate the cardinal B-spline. By combining the result B-spline approximation results and the results in this section, we can obtain the optimal approximation error bound for Transformer networks.
Lemma (Approximation of x²), Let E Ryo. Then, there exist constants
W == 4, = =8 J083 (1) Bi == 1, L = logz (t)
and a neural network Mi 22 Wi, S1, Bi Bi).such that
sup =E(0.1]
2²2
Mi (z)) Sc
Moreover, if R R2g, then, there exist constants
Ra )
R
L2 = loga
+ + W2 = 4, S.
loga
+ BN = R.
and a neural network M2 22 (L, W.S, Buchh that
1 M2(x) Sc
sup
0,
Proof. If R 1, the proof is found in Proposition following network:
Yarotsky 2016) R >> obtain the
Mi
xR
xR
Lemma (Approximation of ry). Let e, R2 Then, there exist constants
(
6/2²2
L:= log
+,, W 12, 24
log
14, B R
c
and a neural network M E (2 W, S, B).scch that
sup
Izy
M(x,
#E
Proof. The proof strategy is found in Proposition 3, Yarotsky 2016)
13

---

Under review as a conference paper at ICLR 2023
Lemma 5 (Approximation of cardinal B-spline basis by the ReLU activation). Let d Zz1. Then, there exists a constant c(d, m) depending only on d and m such that, for all e > 0, there exist constants
3dvm
log2
+
logg(d V mm]. Wo == 6dm(m + 2) + 2d,
(C(d,
Su
Lo Lo Bu = 2(m + 1)mh
and a neural network M E L2 W, S, B..ccch that
|| (R Se
and (x) (Vz & [0. 11d).
Proof. The proof is found in Lemma 1. Suzuki (2119).
C PROOF OF THE STATEMENTS OF SECTION 3
Here, give technical details behind the approximation bound. We will use the so-called sparse grid technique which Smolyak (963)) introduced to the function approximation theory field. The key point of this technique that, instead of the whole set of the regular grid, put the basis on sparse grid which subset of the whole set and has much smaller cardinality than the whole set. The applications of approximation algorithm [1982] 1993a b). Afterwards, the sparse grid technique develops into an optimal adaptive sampling recovery method by (Düng (011b), and we adopt this method on the cardinal B-spline bases. We follow the proof strategy for Suzuki (2019) and Suzuki & Nitanda (202I).
developed by Düng (199)) 1991 1992); [Temlykkvv
Definition 12.
Let E E21. Pk for E E and CR.j E IR for Z E Jd. (k)). Then we define quasi-norm over set of functions by
(etton)llpalll lppallo ))
(Lo))
Σ KERS
(2/0m
and a quasi-norm over a set of coefficients by
1
(cck)) =
(2(a.)) Ikl
Σ
Ick
kEEd
(EJA(()
Theorem (Cardinal B-spline approximation for mixed smooth Besov spaces). Suppose that
P.q.r RSo U ( E Rd Let 8 = ( 4 (note that 8 > 0 is equivalent p < r)
and assume that m E E21, and a. < min m, m +
Then, for any MB and K Zz,,, there exist constants
1)+
(r S p),
min((.I]
1 +
(p < r and r < o0);
(p < and = o0),
8
K" = K (1 + 1-) ni = 2 [2
D:=
28
S(k) C jdl (k) such that #(S(k)) 78k
and
Rx(f)=
Σ Σ
Σ
Σ
cn (x)
kEZzo (E)
kEZZo K K<llAllisk*
(ES(K)
14

---

Under review as a conference paper at ICLR 2023
such that
|l - (x(f)ll 2- " [Ifl|M
1E(K) ((..)) E E E Ck. #0} - (2 (1 -) 2 DK-.d-
max k; S K" Cmax = max Ch.j S $2 2k (5-2)) || MBB., Isid kEEx
kmax
Isidd kEEx
Proof of Theorem 6
According to Suzuki (2019) (see also Düng (011a)), there exist a collection of functions (Px)xez from M Byg to . Bp.g such that
(( = (I(ck.))
where : P=((f)
( Ejerg, Caj Mk (z).
(1) the case of S Then, the assertion can be shown in the same manner Theorem 3.1 of Düng (2)
(2) the case of < We need use adaptive approximation method. In the following, assume < r. For a given K, by choosing K appropriately later, we set
Rx(f)= = Σ
Σ Gn(PH)
kEZZo |AAIISK
kEZ K<]IAIISK
where Gb(Pk) is given as
Gs(Pk) := Σ ch.. C... (x)
where (Ck... ) is the sorted coefficients in decreasing order of their absolute value: |cu.jil 2 IcRUs Ck. (60)-
:=(f)= Σ Σ
Σ
Σ
kEZgo (EJA(K) [[]] SK
kEZzo K<]|
Then, holds that
G S |pk
26 n2 |6|1
where 8 == (1/p-12 1/r) (see also the proof of Düng 201 and Düng 201 1b
Here we denote by
8
K"
K (1
2 (2K-111
28
Then, by Lemma 5.3 Dūng
(011a), it follows that
|l - Rx( &
Σ
22 m 21
(2(61.6) [|aallz))
kEZZo K<]JAIlis*
kEZzo K <*<l
15

---

Under review as a conference paper at ICLR 2023
(2-1) the case of < 00 and S
|1 WV-RK(O RK(O)
Σ kEZOO K Kellkllik
(2 (1lpllll)))
(2(61 l1plllL))
keZza
K <<<||R|l
Σ
(2 (2
Σ (2/01.))/pall>>) 9
(since 2 y
$)
kEZ20
kEZz0
K<| K<|AA||SK*
K' <||A]
<2 -2-660 -Ka2-((a8))K
E
2- (k) 11xl)1111
REZZO
K<IlbIlis
+2 42-90-6)K
Σ
(2laA))lesller)) )
kE
K <1<l
<2- 1f
(2-2) the case of r < 0o and g>r
Since + 1. then follows by applying Hölder's 's inequality that
|l - RR
Σ
(20lbbll n& "Ipaalle))
+ Σ
(201lill: || (Pxlle))
kE K<l
kEZza
52-eKr
Σ
kEZZO K<]|N||SK
Σ
(2-1--011K11-KK)2(aa ||xll//ll (px|ler) ))
kEZ Kº <||k||a
52-
Σ
(2(rn)) Ipalle)) )
Σ
(2la.h) lpu 1lll (2allzz)))
kEZsO K K<]|N|ISK
keZoo
K <|[bil
(2-(00011R11-K3)) #
(2-10-6--0)11111-1]]
KEZZD K< K<
kEZ>o
K*< <||B||>
r(! 1) D K.d <2- 1If [|fll'mng
(2-3) the case of oo
16

---

Under review as a conference paper at ICLR 2023
We can execute the same the analysis in the case of q > r. Since applying Hölder's inequality that
+ + q 2-1
1, then it follows by
Ilf - -Kx())ll=
Σ
Σ
(25)AAlla (|pxllee))
+
KE SK
20
K <1<1//
22 2k
(2-60--60))1141) x) (a.))) [pxlll))
kE
K< SM
Mil1 K (0.0k))) (10.A||1|((x)))) (1px|leo)))
kEZ
<"< <1|1/1
$2-2k
(2
Σ
(2 (2/0A)) (pallle)
kE
keZzo
K< IMIISK
K <||l|e
(2 62-(0-6-60
kEZZo K<]AA|IISK
kEZzo K" <<<|
$2-ak I1flMBB Dk.
Estimation of (E))), kmax and Cmax First, we estimate the cardinality of E(K). It follows from easy calculations that
K
((k))=E>' + 1
1E(K) = 2"
+
E
n
d-1
h=0
d-1 (K+
(K
(x+
<2k+1
Σ
2K-K(x-K)
dd-1
KERSK-
<2 MK++DDK.d DK.d + 22K(1 (1- 12-1"--1D DDs
$ (2 (1 2- 2 2DK DK-.d-
Next, it clearly follows that kmax S ||:111 < K Finally, we estimate Cmax- Since the inequality below holds
2 +) |Ck.s < 2ia.k) likl
ICH.l S 11 [lfllMBg
follows that
Cmax max Chij S 2(f [ffl $²n (b-o)+ |IfllM Isied KEEx
This completes the proof.
Theorem 7 (Cardinal B-spline approximation for anisotropic Besov spaces). Suppose that p. g. e Ry0 U {oo), a E (Rdy. Let = ( -- (note that > 0 is equivalent to p < r) and assume that E Σzo, and 8 ā, ā min(m, m 1 1 1))
Then, for any E AB and K E Zz,, there exist constants
v:= 5-5 N := [2] ny = 1 -| K= = [K ,K'
+
28
17

---

Under review as a conference paper at ICLR 2023
S(k) - Ja (k)
such that f(((k)) = 2x (/--u((bl=-x>>))
where ||k]la
E
ka cxi
and
Rx( Σ
Σ
CK. Mg
Σ
E
k=)jEJ((K)
K=
such that
|ls - Rx(f)l & N 91
EE(K) ((k: E 2:20 Ck. * 0) S (2+ (1 22--1-111 N,,
= max Ck.j 52 ( (#-0)+ -1f All.BB.. ISi KEEK
Kmax = max Ki S K" Cmax
ISiSA KEEK
Moreover, it follows that 2 < N.
Proof. For the existence of Rx(f): See the proof in Suzuki & Nitanda (2021)
Estimation {E(K), kmax and Cmax First, we estimate the cardinality of E(K). It follows from easy calculations that
ΙE(K)
2
Σ
k: k<<[IKllisK-
<2 k+1
Σ
2 2
KEnSKi
<2k+1 + +2 (1 - 2-
$ (2 + (1 - 21-27")-1) N.
Next, since it clearly follows that kinax S K* we estimate Cmax. Since the inequality below holds
E 4p
[
2
IcRal S |l
it follows that
Ed |iue
k
<²" (40-)), 2)+ || AB
Cmax max Ck.j ISidd KEEK
$2
[I. Ala
Finally, it clearly follows that 2 < 211k1lu/a S.
This completes the proof.
By using the results of Theorem 6 and Thcorem 7 we can prove Theorem D which shows the approximation ability of Transformer networks for the target function in mixed smooth Besov space or an anisotropic Besov space.
Proof of Theorem 7
Let
9
Cn Mill
Mungin (x).
and we define
kmax
max 15n5N
Kns Crax
max Cy-
ISASN
Fix E Ry Now, we construct approximate Transformer network T(g] of g-
18

---

Under review as a conference paper at ICLR 2023
It follows from Lemma 3 that, for any c, R Rzu, there exist constants
Le, = 1o82
W., == 3, S.. :- 5Le, Be, == 1,
and neural network M. E (e, We, W., R. such that Mc) S.
sup [0,0
my
Positional encoding and B-spline coefficients: Let
h1
J1
PE = I,K== =
J
AN
JN
11
M1.1=
0
K
M1,2
(00
(INd
7
I
Let Mi : M1, Me, 2
M MI.1, Mi (1(M,) II(M) Concat(PE), Then, it follows that, for any integer j(1 S j 1), For ji 2Z 20000 Rd. it follows that
2 - J1
: 2 5n
MM(a) (x)
4elc 4ddc
where
(2 52
2ºx x ==
2 ja
Token-wise B-splines: Let y1...., Vn Rdd 82 = Alcmax
follows from Lemma 5 that there exist constants
3dvm
L2 == 3 +
loga
+ 5 [log (d V m)],
(C(d,m)
W2, 6m + 2) + 2d, S2.e. = Lo Wo Br,s, == 2(m 1)mh
and neural network M2,1 E Φ2 (L2, W 2,22 S2,52 B2, such that
||M M2alle>(RDD) I E2.
Then we define
91
(2,1(11)
M2
VH
M2. M2
and Mr := II (M2) Mr Since holds from Lemma that, for any r E R, (2) is 1-Lipschitz
and [|, (x)ll I 1. it follows that
Md M (x1)
Md
Maninn (x1)
M2(xx
Md
bi Ihhh (x1)
Md Mannnian (mi)
[.o0((91]99)
< sup 1S
Mb.of (2 x - in) (M
(((0.1))))
Mi (Mr, Mr (MI,
sup S Alemax
(R((
5 21
4lcmax
19

---

Under review as a conference paper at ICLR 2023
Multiplication between tokens:
Let T3 := [log2 1.53 == 67yemax" 7 == log (
and 6 =
- Note that
e
126 8 =
2 1 1- Le 1
(1 1) + e
(1: 8)
(1 0 1
1
) M2,1(z) = + (a,)((=)+)
W3,1
If all the elements Jaj of xj 0 S zej
1, then it follows from easy calculations that
(00)
22
)) =
1 σ1
22
M3.1
0
0
I1 )
1 - I2
C1
C2
61
C2
21
22
)
x1
0
(M3.1 o Ma.1)
0
0
T2
E1
22
61
62
B
Let H == 1, M =
B
B
Ma
-0 1),
MD
( 0)
M =
where : 7/ (9
Since
0
B 0
HlM())))
x x2 :.)
0 B
(x) =
0
then, it follows that
+
+ 24
= 6
12
xi
IAA
+ R
0
0
where H- =
[
1-6
- 22) :
ト
(Σ>n
#
- FAA
0 ...
Thus, it holds
...
that
))
M3.2
0
C1
C2
F1
0
0
22
+ (ACM)
el
e2
r1
0
0
0
0
x2
+
x2
*
*
+ R
C1
C2
0
0
Ø3
622
8x
*
+
R
0
Let Ma.3 := Mes. and M3 : 11 (Ma3) M3.2 II(Ma,1 o Ma.1). We denote may by the i-th
element of (6 ju), M2,,, by the i-th element of M2(x)) and Ma by the i-th element
20

---

Under review as a conference paper at ICLR 2023
of [M M²) (z). Then, the following inequality holds:
sup
1 - 2
x (j.1
sup
|,, (0) 22,4,2i- (2)
1ghSH
sup
(6)
(1)
15h5H
+ sup
1
(2
IShSH
+ sup
1 - M1.4,21-1(z))
IShSH
(m),2-1(x)) - 12 + sup (m),2(()) (2)22(z) + (1-11111111 6) + (Es + (1 (1-6)) 5)) 1ShS
sup
1gh5H
2
1
20max
T3 2cmax
Next, as well as M3. we can sequentially construct M3.... M3 Ia (we can execute these construction
0
0
0
by replacing by
) and define Ms M Mg and Ms M3 M2
0 0
0
such that
[M - MMs(z)
II (x) Mz(z)
E
Cmax
1 (((0,]]])))
Linear combination of B-splines: Let M (c1 cv.) Finally, we define an approximate Transformer network [gg] of g.
[gg] Head I(M') My.
Then, it follows from the estimations above that
sup (g(x)) - [(9)( SE. = =|
MUA AU p.g
Estimation of the bounds of hyper-parameters: Let f E
p.a.
Then, it follows from
Theorem d and Theorem 7 that there exist constants
D DK.dl= D = { DK dd,
N =
12k
à
a2
1,
1,
N,
ā
1
p 0
N == (-11-222--2111 :
dla
1)+
(r $ p),
min(r.1)
7
)
(p < and < 00),
(p < r and r = 00),
q
and an approximation function
RK(f(x)) = Σ
Cn Mdl Kuni (x).
==1
such that
|| - Rx(011 N
21

---

Under review as a conference paper at ICLR 2023
N & N kmax
max 1SnEN
Kn S K" Cmax max On 5 ,,"
S N.
Let == N Then, from above estimations, it immediately follows that
- ( & llf Rx (f)ll + - NN N D
Second, it follows from that there exist absolute constant C Rz0- Third, define constants which define hyper-parameters as follows:
4dl )
== N (a- m) To [log2 11 L1 C log ({e)
3dvm
670
L2 3+2 +2 2 log2
+ [log2 (d V m)], L1 C log
(C(d,m)
Wo = 6dm + 2d,
a.
Note that Cmax
Finally, we estimate hyper-parameters of the Transformer network. Because of the above estima- tions, it immediately follows that
T = To
I
H = 1,
L1 + L2 + T(L3 +2) +1
W = WON" +
5 S C(N4+ + L2) + + + CC((NN + +E) La) N
B& ((VV)
This completes the proof.
D PROOF OF THE STATEMENTS OF SECTION 4
To prove Theorem we define a covering number with respect to a given metric space.
Definition 13 (Covering number and packing number). Let 6 E Rso (V. d) be a metric space, and F be subset of V. Then, we define a covering number (e,,,, (V,, (V.d) of F with respect (V, d)) as follows:
N(e.F. min { N = ((K, U (1 fiEK
Before proving Theorem networks TN(L, T, E, W, H, B) with respect to -
have to estimate the covering number of the of transformer
Lemma 6 (Covering number estimation of the set of Transformer networks). The covering number of TN W, H, S, B) can be bounded by
log 108.N(8, TN(L, T, E, W, H, S,B), 112x) <S (40 4 (L + 1)( + 21 (B 11)11)22 1)
Proof. First, we define
F(M == M (x) +
22

---

Under review as a conference paper at ICLR 2023
Then, the following estimations hold:
|F[M (2))
$ |2 + max |IM,; |00 + |9| = (WB |=] + B
3 <W 1) + [1 V1),
[F[, ( - J[M b)
| x2llx0 + = || M,, [1(x))+ (12)+ S 1|:01 x2llxx WB ||:0 x2lla
<(WB - 1) ||=1 - x2ll
and, if 5' = ||M - o v -lb Ull then it follows that
b)() F[M' (<)))>> SW |,0 +1)
Next, we define
A[M]]() x
((M)) JunyJJttaalTiiyooo00000000011100
Then, the following estimations holds
|
$ |111|100 + max (I(M)) max ((Mb),; ||=||0
SHW? B² + 1) |
||[ [ A[M (x2) AM
|| 02ll.0 + H max ((M)) max (|(AM)))=ll || x2lloo
$ $|< 02|loc + HW² B² | 2211
<(HW3 + 1) ||= x2lloo
and, if == max max. || (M') /1 then it follows that
[ - A((M') S 25HW2 B1/00
Next, we define
Fe(x) = (C+ ................................ ... (z), = (42 .... Lb) (z),
Bx(x) = (LL+T
Lb) (z), (Cit C.) (x)
where, for k = 0. (x)x = Concat (aanca(Pee(aa (x)(2) and (x) = Concat (oncat(PE](x)) and, for k 2 1, either one the following cases is true:
1. (xx = [TF bx)) and C1(x)) = [[F[, K)()).
2. (x(xx) == ([(M)))))() and (x(2) A[[M))))))))
Moreover, for k 2 1, we denote
f = +sk,,0) =
4 :==:\ie2]i {(())))())
b. = = A((M))()))
f
TN(L F, W, H,S, and
8 max 1SkST++
|P | - -Pella v VIM -M -Mll v |lb b/ lla
[[(M))) -(A)) }
max IShSH..EO..v.k.o)
23

---

Under review as a conference paper at ICLR 2023
then it follows that
If - ff-fllla -
L+T
|1/+1 F B/4 C Fx-
L+T (WB +
+ 1) |L Fk-1 Ca F
k=
S(WB+1) (HW
L+T
(WB+ (BB+))+T B 11) + (1) (1FR- V1)
SWB 1)a (HW +1)
L+T
(WB+ 1) 1 (HW 8 1)
(W +1) 11)*-1----- (B
+ 1) (1
Coll v1)
L+T
28' 2² (W + L+2 (B (B+1) - (BV1)
22 1)H (W 1) 2T (B + 1) 1+27
Thus, for fixed sparsity pattern (the locations of non-zero parameters), the covering number is bounded by
2 + 1)H (W + 1) 2 (B + 1)
2B.
5
Thus, the covering number of the whole space TN T, E, W, H, S, B) is bounded as
(W + 1)4 +1)
2B 2(L + 1111 (W +1) 24 (B + 1)2-21
S
((4 1 (L+T+ ()(W 2)2 (B + 1
This completes the proof.
Next, to prove Theorem 3 we need the following result which connects the approximation theory to generalization error analysis.
Proposition 1 Sihhiddt-Hieber 2017 Let F be set of functions, let f be any estimator in F. Define
A, = ED,
1
Σ (u. f(x,))2
inf JEF
1 -v. f(x.)))))
Assume that || < F and all E F satisfies
Il F For some F 2 1. If0 < 8 satisfies
N6,,F, Il. [100)) then there exists a universal constant C such that
ED. (115- -fles((px))
inf ||I -1'lLA(P + p2 yEF
p2log log Log,N(8,FF -11-11==)) - log + 5F + An
nE
for any e E (0,
Proof. See the proof in Sechscttt (2017) and Suzuki (2019).
Finally, based the definition and the results above, prove Theorem
24

---

Under review as a conference paper at ICLR 2023
Proof of Theorem Theorem 3 and Theorem 4
Note that the estimations below holds:
D log
1, ,,
ND, H s 1,8 ND N, B S N(to 9)(v5)
Lemma 6 gives an upper bound of the covering number as
N6, ( T, E, W, H,S, B), 1| <Slog (L+ 1)( + 1)2L+27 (B + 1)
DNDlog N (log N)² + log (6 (6-1)
Next, it follows from Theorem that
|lf - Rx 2 $Ñ-
where 77 = fp..gr-- Since Px has a density function 0 $ p(x) < R on 1J9), then it holds that
|| - R (x( & |l Rx(f)
for any f: (10, + R. and by applying Proposition
with å = A, it follows that
log N (log Ñ)² + log n
Ep, (11f- - f(lea(pss)))) & -N-a-p' +
+
The case of mixed smooth Besov spaces: Note that - D = DR.at- Since
DR.at (1 1 k
dl-1
$ Kdl-1
dl -
then we obtain the following upper bound estimation:
ED, (11f- - f1122(2))) 2 2-2k 22((d111) + Kdl2 (K2 2 + logn)
2aK
Then, the right hand side minimized by K log log n-order. Then obtain the following result:
1+2a log, n + (2n I) 11+++))+ 1)+33
log, logn n
up to
1+2g
204 1X
2m
(log n)
22
The case of anisotropic Besov spaces: Note that Ñ = Ñ, D = 1. The right hand side is minimized IT (log n:)
by Ñ
rizz up to log log(())orrr))) order. Then we obtain the following result:
S n (log 1-26 1-26.
This completes the proof.
E PROOF OF THE STATEMENTS OF SECTION 5
Proof of Theorem 5 In the proof of Theorem we can easily check that how to construct Rg (f)
is independent of the smoothness parameter a. And, since 8, as in the proof of Theorem 6 we obtain the following estimation
|| RR S -k
KK Davair Kid
|| ||flv
such that
RK(f)=
ck. k.j (z),
(kI))
1F(K) ((k.)) E Zd Zd (k.
(kk # 0} (2 (1 - --- 2 Dx-
25

---

Under review as a conference paper at ICLR 2023
From now on, consider the in which
{[2}. For general n, adapt the same
[
proof strategy. Let lo
8
2 2K) and
log
Rx(f):=
Σ
ck. Mg
(KJ)ER(K) (1,'70,00))<tt
k + 0,((") 2 to. since 8 2 1. the following inequality holds:
22K ckk & - lonss s 2(a))
1kl lcaal S IIfllarg,
Thus, since 1, it follows that
[xx(]) |
Σ (LK)
lekall| || SEE(K) 2K Ilflla
5 (1-2-11))) 2 DR. ,22
22 DE l1flllee 2K
| Ifll
From estimations above, it follows that
||s Rx Rx(0)|, $2
D IIfllvnp K,d
Let
2 (m++1)
Nm Σ 1==*((-))-===(=))M, K x2
(the expressions 2- K [2 x correspond to input quantization masks). Then, it follows from Lemma
1 that
[| (x) - (z) 2
v + 0i) 2 lo. we denote (x( as the expression which we can obtain by replacing N
Rx (f) by Nn- Then the following estimation follows:
| (f) - -Rx())l 2-
Consequently, as in the proof of Theorem
0 it follows that
R, (L, E,W, H, B), VU (10, 11 2- D K,at
For general (i' * 0, (i') 2 tu]. Since o; * or for i + i' in general, it also holds that A # Ay for i * in general. For each A,, we can construct (Rx(f)), and this expression (Rx (f)), corre- sponds each quantization mask.
execute the same proof strategy. For each Qz set A;
This completes the proof.
26


Reviews:
[{"review_id": "i35FHxYujI", "reviewer": "Reviewer_SPZu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the approximation and estimation error of transformers to the target functions of fixed-length in a mixed smooth Besov space and in an anisotropic Besov space. The authors also show that transformer models are capable of avoiding the curse of dimensionality and obtaining almost minimax optimal rate. Furthermore, it is pointed out in the paper that token-wise parameter sharing in transformers helps reduce the dependence of the network width on the input length. The authors also show that the transformer models dynamically select tokens to pay attention to. ", "summary_of_the_review": "Overall, this paper could be an interesting theoretical contribution. However, my main concern is the lack of experimental results to validate the theoretical findings in the paper. Also, there is not enough comparison to other approximation and estimation error of transformers from recent works. \n\nCurrently, I am leaning toward rejecting the paper. However, given additional clarifications on the two main concerns above in an author response, I would be willing to increase the score.\n", "strength_and_weaknesses": "**Strong points:**\n\n1. The paper addresses an important issue in the study of transformers, which is the approximation and estimation error of transformers.\n\n2. The paper provides an interesting finding that token-wise parameter sharing in transformers helps reduce the dependence of the network width on the input length. \n\n3. The theoretical results in the paper explain the phenomenon that the transformer models dynamically select tokens to pay attention to. \n\n**Weak points:**\n\n1. Experimental results are needed to corroborate the theoretical results in the paper.\n\n2. The authors do not compare their approximation and estimation error of transformers to the recent results, such as those in [1]. Comparisons to [2] and [3] are mentioned in the paper but need to be elaborated more.\n\n3. The theoretical results in the paper are presented in a confusing way. The impact of the paper and insights from theoretical findings can be clearer if the authors clean up the manuscript and present the results in a more concise way.\n\n**Minor Comments that did not Impact the Score:**\n\n1. Can the results in the paper be extended to a variable length setting and to linear transformers?\n\n**References:**\n\n[1] Kratsios, Anastasis, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić. \"Universal approximation under constraints is possible with transformers.\" arXiv preprint arXiv:2110.03303 (2021).\n\n[2] Vuckovic, James, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of attention. ArXiv preprint arXiv:2007.02876, 2020.\n\n[3] Yun, Chulhee, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. \"Are transformers universal approximators of sequence-to-sequence functions?.\" arXiv preprint arXiv:1912.10077 (2019).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GuzgWQpHX78", "reviewer": "Reviewer_y5B2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies how fixed-length Transformer networks can approximate anisotropic Besov and mixed smooth Besov\nspaces. They show that the expected approximation error of  fixed-length Transformer networks is mildly dependent on feature dimension $d$ and input length $l$, and is independent of $d$ and $l$ for anisotropic Besov spaces.  Due to the token-wise\nparameter sharing property in Transformer network width is independent of the length of the sequence $l$.  They claim superior approximability of Transformer network as compared to Fully connected networks. Moreover, they provide an approximation error bound where the error over $n$ samples decays polynomially with $n$. Finally, by the use of variable smooth Besov spaces the authors try to capture the sparse dependence on the input sequence (e.g. sentence understanding). They show Masked Transformer networks are good at approximating such spaces. ", "summary_of_the_review": "This paper has several shortcomings: placement in literature, clarity in exposition of the results, and clarity in highlighting technical novelties. These shortcomings leave a lot of room for improvement despite the important topic studied in the paper.   ", "strength_and_weaknesses": "Strengths:\n- The paper studies the approximation error of Transformer networks which is a timely and important problem. \n- This paper extends the approximability results of Deep Neural Networks w.r.t. the smooth and anisotropic Besov spaces (Suzuki & Nitanda 2020) to Transformers with finite-length sequences. \n- The 'Token extraction property of Transformer networks' in Section 5 highlights some interesting properties which resembles/alludes to attention mechanism in transformers.\n\nWeaknesses:\n- The main Theorems are not easy to understand. A corollary where the approximation error is directly linked with the \n- The technical novelties as compared to Suzuki & Nitanda 2020 is not discussed clearly. What are the key difficulties faced in extending the results therein to Transformer network? For example, Section 4 seems to follow very similarly as Section 4 of  Suzuki & Nitanda 2020.\n- The related work part seems to be lacking. The authors should comment on how the current result improves upon Yun et al. 2020. Furthermore, there has been some other studies after Yun et al. 2020, e.g. Kratsios et al.  \"Universal Approximation Under Constraints is Possible with Transformers\" ICLR 22. A better placement of this work in the literature is needed.\n- The importance of Besov spaces in approximation theory, and its comparison with other concepts, like universal approximation, should be discussed.\n- Definition 4 seems to be a restatement of Definition 1. \n- Definition 10 is $\\pi$ missing from the definition of $VU$?\n- \"Note that the cardinality of values of masked tokens is finite while the cardinality of values of non-masked tokens are uncountably infinite. Hence, masked tokens have much less information than non-masked tokens.\" -- I thought fixed finite length input sequences are considered in this paper. Am I missing something here? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BvCtbuzi1ah", "reviewer": "Reviewer_hE8B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper theoretically analyzed the reason why transformers could outperform fully-connected NNs in NLP tasks.\nThis paper claimed that the transformer could avoid the curse of dimensionality and accomplish a minimax optimal rate in a setting where the target function takes fixed-length input and belongs to Besov spaces.", "summary_of_the_review": "The claim is not well-supported due to the lack of experiments and related works.", "strength_and_weaknesses": "Strength:\nThe topic is interesting and the proof is detailed: to explain the representation power of the transformer by proving it could avoid the curse of dimensionality, accomplish minimax optimal, decrease the dependence of the network width on the input length, could dynamically select 'focused' tokens.\n\nWeakness:\nAll claims are not supported by experiments, see details below.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-gjfsV042B", "reviewer": "Reviewer_YpHD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors study approximation and learning of functions from Besov spaces by transformer networks. The results show that transformer networks can avoid curse of dimensionality. Almost minimax optimal rates are presented. ", "summary_of_the_review": "Transformer networks are not well understood theoretically. The topic deserves extensive study. \nBesov spaces are interpolation ones between Sobolev spaces. Though anisotropic Besov spaces and mixed smooth Besov spaces are considered in the paper, the analysis is not surprising, based on a few papers published by the group of T. Suzuki. ", "strength_and_weaknesses": "Transformer networks are not well understood theoretically. This paper provides some interesting results to verify the efficiency of transformer networks. \nBesov spaces are interpolation ones between Sobolev spaces. Once results for Sobolev spaces are established, those for Besov spaces are well expected. This paper considers anisotropic Besov spaces and mixed smooth Besov spaces which are different from the standard Besov spaces and can explain networks' ability of avoiding curse of dimensionality. But the analysis results are not surprising. There have been a few papers published by the group of T. Suzuki. Publishing another one at ICLR would not give too much new insight for transformer networks. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject