Attention Enables Zero Approximation Error
Authors: Zhiying Fang
Yidong Ouyang
Ding-Xuan Zhou
Guang Cheng
Venue: Submitted to ICLR 2023 (2023)

Abstract: Attention-based architectures become the core backbone of many state-of-the-art models for various tasks, including language translation and image classification. However, theoretical properties of attention-based models are seldom considered. In this work, we show that with suitable adaptations, the single-head self-attention transformer with a fixed number of transformer encoder blocks and free parameters is able to generate any desired polynomial of the input with no error. The number of transformer encoder blocks is the same as the degree of the target polynomial. Even more exciting, we find that these transformer encoder blocks in this model do not need to be trained. As a direct consequence, we show that the single-head self-attention transformer with increasing numbers of free parameters is universal. Also, we show that our proposed model can avoid the classical trade-off between approximation error and sample error in the mean squared error analysis for the regression task if the target function is a polynomial. We conduct various experiments and ablation studies to verify our theoretical results.

Under review as a conference paper at ICLR 2023
ATTENTION ENABLES ZERO APPROXIMATION ERROR
Anonymous authors
Paper under double-blind review
ABSTRACT
Attention-base architectures become the core backbone of many state-of-the-art models for various tasks, including language translation and image classification. However, theoretical properties of attention-based models are seldom considered. In this work, we show that with suitable adaptations, the single-head self-attention transformer with fixed number of transformer encoder blocks and free parameters is able generate any desired polynomial of the input with no error. The number of transformer encoder blocks is the same as the degree of the target polynomial. Even more exciting, we find that these transformer encoder blocks in this model do not need to be trained. As direct consequence, we show that the single- head self-attention transformer with increasing numbers of free parameters universal. Also, we show that proposed model can avoid the classical trade-off between approximation error and sample error in the mean squared error analysis for the regression task if the target function is polynomial. We conduct various experiments and ablation studies to verify our theoretical results.
INTRODUCTION
By imitating the structure of brain neurons, deep learning models have replaced traditional statistical models in almost every aspect of applications, becoming the most widely used machine learning tools LeCun al. 2015 ; Goodfellow et (2016). Structures of deep learning are also constantly evolving from fully connected networks to many variants such as convolutional networks Krizhevsky al. (2012). recurrent networks Mikolov
Metkoov et al. (2010) and the attention basedd transformer model Dosovitskiy et al. (2020). Attention-bant based architectures were first introduced in the areas of natural language processing, and neural machine translation [Bahdanau et al. (2014); Vaswani et al.) (2017): Ott et al. (2018), and now an inrention-basce transformer model has also become state-of-the-arr in image classification Dosovitskiy et al. (2020). However, compared with significant achievements and developments in practical applications, the theoretical properties of aitention-bbsse transformer models are not well understood.
Let describe some current theoretical progress of attention-basee based architectures briefly. The universality of a After that, sparse attention mechanism, BIGBIRD, is proposed by /aheer al.) (2020) and the authors further show that the proposed transformer model is universal if its attention structure contains the star graph. Later, Yun al. (2020) provides a unified framework analyze sparse transformer models. Recently, Shi et al. (2021) studies the significance of different positions in the attention matrix during pre-training and shows that diagonal elements in the attention map are the least important compared with other attention positions. From statistical machine learning point of view, the authors in ych et al. (202T) propose classifier based on a transformer model and show that this classifier can circumvent the curse of dimensionality.
transformer model is first established in Yun et al. (201)).
The models considered in the above works all contain attention-based transformer encoder blocks. It is worth noting that the biggest difference between transformer encoder block and traditional neural network layer is that it introduces an inner product operation, which not only makes its actual performance better but also provides more room for theoretical derivations.
In this paper, we consider the theoretical properties of the single- head self-attention transformer with suitable adaptations. Different from segmenting into small pieces Dosovitskiy et al. (2020) and capturing local information, we consider global pre-processing of x and propose a new vector structure of the inputs of transformer encoder blocks. In this structure, in addition to the global

---

Under review as a conference paper at ICLR 2023
Linear
Add
Feed
Forward
MatMul
times
Add
One-hot maximum
function
Singe-Heed Self-Attention
MatMul
With foeed weights, no need for training.
w w
Data Pre processing
R
Figure I: The Architecture of the single-head self-attention transformer. Wº, W.K w stand for the query matrix, the key matrix, and the value matrix respectively. MatMul stands for the matrix multiplication.
information we obtain from data pre-processing we place a one-hot vector to represent different features through the idea of positional encoding and place zero vector store the output values after each transformer encoder block. With such a special design, we can fix all transformer encoder blocks such that training is needed for them. And is able realize the multiplication operation and store values in zero positions. By applying a well-known result in approximation theory Zhou (2018) stating that any polynomial Q Py (R*) of degree most q can be represented by linear combination of different powers of ridge forms & x of E Iid, we prove that the proposed model can generate any polynomial of degree with transformer encoder blocks and a fixed number of free parameters. As a direct consequence, we show that the proposed model is universal we let the the number of freee parameters and transformer encoder blocks go to infinity. Our theoretical results are also verified by experiments on synthetic data. In summary, the contributions of our work are as follows:
We propose a new pre-processing method that captures global information and a new structure of imput vectors of transformer encoder blocks.
With the special structure of input of transformer encoder blocks, we can artificially design all the transformer encoder blocks a spare way and prove that the single-head self-attention transformer with y transformer encoder blocks and fixed number of free parameters is able to generate any desired polynomial degree y the input with no error.
As direct consequence, we show that the single-head self-attention transformer with increasing numbers of free parameters and transformer encoder block universal.
We conduct mean squared error analysis for the regression task with our proposed model. We show that if the target function is a polynomial, our proposed model can avoid the classical trade-off between approximation error and sample error. And the convergence rate is only controlled by the number of samples if we treat d and q as constants.
We apply our model to noisy regression tasks with synthetic data and real-world data-set. Our experiments show that the proposed model performs much better than traditional fully connected neural networks with comparable number of free parameters.
We apply our model to the image classification task and achieve better performance than Vision Transformer the CIFAR- 10 data set with suitable adaptations.
2 TRANSFORMER STRUCTURES
In this section, we formally introduce the single-head self-attention transformer considered in this paper. The overall architecture is shown in Figure
2

---

Under review as a conference paper at ICLR 2023
2.1 DATA PRE- PROCESSING
For an input E I which can be a vector or the concatenation of an image, the usual pre-processing method is to segment it into small pieces and then conduct linear transforms, which be thought of as extracting local features. However, we propose to directly apply a full matrix F E Rax to get global features Fz = R", where F Ii..... .n]' with & E I2 and ||E/|| S The matrix F is obtained through the training process. Then we have n global features t; = (Er, of the input Now we introduce the structure of inputs for transformer encoder blocks as follows,
2 = [t. 0,
0,
0,0,
0,
(x+1)
entry
for = 1, 1................ Each one of them is sparse vector in R and all the n vectors are inputs for the transformer encoder blocks. As we have covered before, we put a one-hot vector of dimension inside representing different features t; of the input x, which is similar to the idea of positional encoding. And we also place a q dimensional zero vector to store outputs from each transformer encoder block. At the last position, we place a constant 1 for the ease of computation in transformer encoder blocks. We use F(x): Ed (x(+++2)x(x)) to denote the above transformation such that F(x)
[21,-
Zn).
2.2 SINGLE-DERS DEAD DELF-ATTENTION TRANSFORMER ENCODER BLOCKS
One transformer encoder block contains self-attentin layer and fully connected layer with linear transformation. In the self-attention layer, we have one query matrix W E ((+++)x((+++3))) one key matrix W R (n++1)x(x++++)) and one value matrix W. E (=(++++))((==++2))
For every input 2; we calculate the query vector qi W 2; E R=++ the key vector K; W 24 Ra+1, and the value vector = WV 2; Rn+--2 With all these values, we have n attention vectors
query
06; = 1 ((g;())); ki), (yi, k.),.... (a,,,)) )T E ER..
In proposed model, the soft-max function in the self-attention layer is replaced by one hot maximum function m)(a;) R" + R= which keeps the largest value unchanged and sets the other values to We use the notation Awe,w* wv [((+g+2)xn + ((n+ to denote the mapping of the self-attention layer. Then the output of the self-attention layer is given by Awa, w wv (21, ,.,) [21, ... 2n), where & 2 + WV WV Zm(a;;) with Z [2,,-.. 2x).
The fully connected layer with linear transformation contains two matrices W1 R2x(n+++2) and W2 E (2(==+2)x22 and two bias vectors b E R2, b2 E 1R=+ We use the notation denote the mapping of the fully connected layer Bw, W2.b1.b2 RR(+++2jxn -> ((a+++2)xn
with a linear transformation. Then we have ,w,,W,,b, (21,... .,,) = [ ".,,.,,,,,, 2/),, where 2 + W20 (W141 61) b2, and is the ReLU activation function acting component-wiss
Now we define our single-head self-attention transformer model with l transformer encoder blocks as
('xx= B o A' o ..... B² o A' o F(x).
where A, B' are the mappings defined above. We further concatenate the output matrix into one vector and apply a linear transformation with a bias term to get our final output, that is,
C² (x) concat (T (x)) + b,
with 3 E ( and b R. We require the vector to possess sparse structure which will be shown in the proof. The values in and are obtained through the training process. The layer normalization is not considered in our model.
MAIN RESULTS
3.1 ZERO APPROXIMATION ERROR
In this section, first present main result from approximation theory point of view, showing that the single-head self-attention transformer model can generate any desired polynomial with fixed number of transformer encoder blocks and free parameters. Before stating our main theorem,
3

---

Under review as a conference paper at ICLR 2023
first present two important lemmas. For the following lemma, construct sparse single-head self-attention block with a fixed design that is able to realize the multiplication operation and store different products in the output vectors simultancously. Lemma 3.1. For all n imput vectors in the the form of
2, [t Ci, Vi. 0,. 0, 0.1]T& Rln+g+2)x1,
= 1,... ,n, there with t4, Tt. Vs E R. and absolute values bounded by some known constant M = exists a sparse single-head self-attention transformer encoder block with fixed fixed matrices WO, WK WV, W1, W2 and vectors by, b2 that can produce output vectors as
2/ - L2. Cz. Z4. I:y:, 0, ... ,0,1) E R(n+9+2)x1
where e, denotes the one-hot vector of dimension with value 1 in the i-th position et. The softmax function is replaced by one hot maximum contnnnufunniio function. The number of non-zer entries is 2n + 8.
Remark 3.2. The above lemma shows that fixed single-head self-attention transformer encoder block is able to simultaneously calculate the product of two elements in all n input vectors within the same two entries and store the negative value in the same O positions. Since the construction is fixed, these transformer encoder blocks in the whole model do not need to be trained.
Now we introduce a well-known result in approximation theory showing that any polynomial function Q E P. (R*) of degree at most can be represented by linear combination of different powers of ridge forms & x of æ E Rd. The following lemma is first presented and proved in Zhou (2018) and also plays an important role in the analysis of deep convolutional neural networks Zhou 2020) Mao et al. (202I).
Lemma 3.3. Let E N and q E N. Then there exists a set {Ex C {E E RR |K = 1}
of vectors with 2a-norm such that for any Q E Py (RE) we can find set of coefficients
{3 k ===1=11.. Ag. 1, ,,.-,,9) .9} C R such that
9
Q(0))
BR, (Ex 2)", x ZER
where ng = ((=-1t0) is the dimension P1 (Rd), the space of homogeneous polynomials on Id of degree q.
Remark 3.4. The above lemma shows that any polynomial Q E Py (Id) can be uniquely determined
by (0)), BK. and Êx. So by applying the above lemma, can perfectly reproduce any polynomial with proper construction.
Now are ready to state our main result the single-head self-attention transform model.
Theorem 3.5. Let B and E N. For any polynomial function Q E Py (IR") of degree at most there exist single-head self-attention transformer model with q transformer encoder blocks such that the output function C9 equals Q on {I E Rdd
||>||| < B}
Q(x)) A || S B. The number of free parameters is less then d + qd'd + 1 which comes from F, 3 and b. The number of non-zero entries in this model is less than da+1 3qd" 8q 11
Remark 3.6. The above theorem shows a very strong property of the self-attention transformer model that can generate any desired polynomial with a finite number of free parameters. As we can see, the degree of the polynomial is reflected in the number of transformer encoder blocks, showing that the more blocks the transformer have, the more complex polynomial can represent. Clearly, this result outperforms that of the other classical deep learning models without attention-based structure in at least two aspects. First, since the linear combination of the output units of traditional ReLU neural networks is only a piece-wise linear function of the input, matter how many finite layers and free parameters, it can never produce a polynomial of the input with no error. Second, the transformer encoder blocks in our construction only serve the realization of the multiplication operation. The non-zero values are all pre- pre-designed constants, so no training is needed for these blocks. We only need train free parameters in F, B, and b.
4

---

Under review as a conference paper at ICLR 2023
As direct consequence of the above result, the proposed single-head self-attention transform model universal.
Corollary 3.7. Let and q N. For any bounded continuous function f on 1],, there exists single-head self-attention transformer with increasing numbers of free parameters and transformer encoder blocks such that
lim | -Ilcc(a.111) 20000
The above result is simple application of the denseness of the polynomial set, which shows that the transformer model discussed in our paper is universal if we let the number of free parameters and transformer encoder blocks go to infinity.
3.2 MEAN SQUARED ERROR ANALYSIS
In this subsection, we consider the regression problem with mean squared error in the setting of statistical learning theory with our single-head self-attention transformer model. Let X == {a: : ||:1||| B, { and Y R. We observe N i.id. vectors 2; X with unknown probability distribution px and N responses Yi E R from the model
y/ fo (2.) + C2s 1= N,
where the noise variables e, are assumed to satisfy E (c((2)) O. Usually the noise variables satisfy standard normal distribution. We denote the joint distribution of (æ4, yt) by p and D {(x,, yt) > is drawn from the probability measure p. Our goal is to recover the regression function fo from the sample D. For any measurable function, we can define the population risk E(f) (f - dd, and the empirical risk as (f) == + E (f(z)) - y1)² We use fD. = arg min {f),), to approximate fo where H is the hypothesis space generated by our proposed model given by
H. : He,B = (c) ||&/l S 181 S B. B).
(2)
Let (Lxx-11-lpx) be the space of px square-integrable functions X such that |I Sx. (x))dpxx The target of mean squared error analysis is derive convergence rate of E(fD.u) - E(fp) IlfD.. - fell Now we are ready to state our main result of mean squared emror analysis.
Theorem 3.8. Let B, B > O. Lerd E N+, E N. H. be defined as 2 and fo be polynomial of degree at most q on X such that lfpl BB'. Then for N E N such that N ' ny we have
[ Sollox SC n log N
where C, is constant depending q, d, B, B and and - is the dimension of Ph (BR).
Remark 3.9. For classical mean squared error analysis the regression task, there is trade-off between approximation error and sample error and the convergence rate is controlled by the maximum value of these two errors. Since our model can achieve zero approximation ervor for polynomial target functions, our main result shows that this trade-off can be avoided. As direct consequence, the convergence rate O (oggN) is only controlled by the number of samples if we treat d and g as
N
constants. The above result also verified in experiment 5.2
COMPARISON AND DISCUSSION
In this section, compare work with some existing theoretical results the transformer model Yun et al. 2019 2020 Zaheer et al. (2020); Shi et al. (021). Since these works use similar methods to those in Yun et al. 2019), focus the theoretical contributions of this paper.
In Yun et al. (2019) the authors show that transformer models are universal approximators of continuous sequence-to-sequeeee to-sequence functions with compact support with trainable positional encoding.
5

---

Under review as a conference paper at ICLR 2023
(a) ATTENTION with MSE 0.02. (b) NNdepth with MSE 134.23. (c) NNwidth with MSE 10237.27.
Figure 2: For the target polynomial fp.1, the above 3-D surface plots output functions of three different models after the training process. ATTENTION stands for our single-head self-attention transformer model, while dedepth and NN stand for fully connected neural networks illustrated in experimental setting 5.1 MSE stands for the Mean Squared Error evaluated at testing data.
The notion of contextual mappings is also formalized, and it is shown that the attention layers can compute contextual mappings, where each unique context is mapped to a unique vector.
The universality result is achieved in three key steps: Step 1. Approximate continuous permutation equivariant functions with piece-wine wise constant functions FPE Step 2. Approximate (PE with modified Transformers T. Step 3. Approximate modified Transformers T with original Transformers T.
In order express the above steps more clearly, show the idea of proof as follows. For an input X E Raxn, the authors first use a series of feed-forward layers that can quantize X to an element T. on the extended grid G3 == {-5-nd 0, .............................. 5} dxn Activation functions that applied to these layers are piece-wise linear functions with at most three pieces, and at least one piece is constant. Then, the authors use a series of self-attention layers in the modified transformer network to implement a contextual mapping (L). After that, series of feed-forward layers in the modified transformer network can map elements the contextual embedding (L) to create a desired approximator I of the piece-wise constant function ff e (P)(5) which is the approximator of the target function.
We would like to address major differences between our work and theirs. First, the output functions are different. the above work, the goal to approximate a continuous function defined from Raxd to IRx which focuses on woweencee----eueenee functions. In our setting, we use the linear combination of the units in the last layer as our output, which focuses on regression and classification tasks. Second, the two structures we consider are slightly different. The self-attention layers and feed-forward layers their transformer model are set in an alternate manner. Although this may explain the different functions of different types of layers, it changes the structure of the transformer model in real applications. In our setting, we guarantee the integrity of transformer encoder blocks and analyze each transformer encoder block whole. Last but not least, the ultimate goals and core ideas of the theoretical analysis of our two papers are different, Because the inner product operation is the biggest difference between the attention layer and the traditional network layer, we focus on this special structure for analysis. We find that if we can make good use of this inner product structure, then from the perspective of theoretical analysis, we do not have think about approximation but can directly generate the function we want. And the exact construction only requires a finite number of free parameters with fixed transformer encoder blocks. This shows the different thinking in our theory and distinguishes our method from using piece-wiss functions to approximate target functions.
EXPERIMENTS
In this section, first verify main results of our single-head self-attention transformer model by experiments on two groups of synthetic data. Then, we conduct several ablation studies to demonstrate the superiority of the self-attention transformer.

---

Under review as a conference paper at ICLR 2023
5.1 EXPERIMENTS ON POLYNOMIAL FUNCTIONS AND WEALDWORLD DATA-SET
Target functions
For these two experiments, we consider the noisy regression task
y = [x(x) + 6,
where /o is the target polynomial and is the standard normal noise.
For the first experiment, in order to visualize the advantages of our proposed model, we consider a simple polynomial.
(x) = =xf +22
which satisfies d = 2 and = 2.
For the second experiment, to show the strong expressiveness of our model, we consider complicated polynomial
(x) 2 3.2 2 + 2x 52gg24 3x 20g2TI4 + 2rg, which satisfies d= 10 and q 5.
Experimental setting To demonstrate the power of attention-based structures, we compare our proposed model with two types of ReLU fully connected neural networks with comparable number of free parameters. Since for a polynomial
of degree q, our proposed model has one linear transformation with matrix F E IR" and transformer encoder blocks, we use NN depth to denote the fully connected network with y + layers, and we use NN witthh denote the shallow net with n, units in the hidden layer. For these two fully connected networks, ATTENTION model to generate output value, which is the linear combination of units in the last layer with bias term. The detailed descriptions of the experiments, i.e., data generating process, training pperrpparaeter, and model architectures, can be found in B
the same way
ATTENTION MEE
ATTENTION UsSLMSE Mr. desth trann MSSE
Mr. deeth test, MSE
1500
Mr. wicth train, MSE
Mr wicth best MSE
1000
503
2.5
500
750
1000
1250
1500
1750
2003
Figure 3: comparison of the convergence speed and generalization gap between our single-head self-attention model and two types of fully connected neural networks.
Table 1: comparison of three models learning f..2. MSET, and MSEr stand for the mean-squared
етror of the training data and the testing data after 2000 epochs training, respectively. We say that model achieves convergence if the absolute difference of MSEr, of two consecutive epochs less than 0.01. # EPOCHS stands for the number of epochs the model used before achieving convergence, and RUN TIME represents the corresponding running time the training process.
МSErr
MSEre
# EPOCHS
RUN TIME
ATTENTION
0.938
0.109
212
1.9
NN depch
5.884
103.916
956
7.6
NN
50.282
35.662
329
2.4
Experimental results For the target polynomial fo.1, Figure 2 demonstrates the strong power of learning polynomials of our proposed model. With only 19 free parameters, our single-head perfectly capture the target function by using noisy data. Due to
self-attention transformer the nature of piece-wise linear output function, both two types of fully connected neural networks obviously can achieve comparable results with very few parameters.
'GPU* * min NVIDIA A100 Tensor Core GPU.

---

Under review as a conference paper at ICLR 2023
For the target function fp.2, Table and Figure also also demonstrate the superior ability of our model to learn a complicated polynomial. Our single-head self-attention transformer the only one that can fit the ground truth function exactly with good convergence speed. Moreover, model has a much better generalization power than both two types of fully connected neural networks with a comparable number of free parameters.
5.2 THE SIGNIFICANCE OF THE SELE-ATTENTION TRANSFORMER
In this part, conduct several experiments to address the following question:
Given that neural networks can approximate any continuous function with enough width, what is the significance of zero approximation error achieved by the self-attention trans- former?
Can zero approximation error be achieved by using the quadratic activation function instead of the Relu Sigmoid activation functions?
Can our ATTENTION model avoid the trade-off between approximation error and sample eтror practically?
Can our ATTENTION model achieve good performance on real-world data-set?
Table The comparison Mean Squared Error for learning fp.1. Column ATTENTION demon- strates the MSE achieved by our architecture with 13 free parameters, while Column WIDTH=10+ to Column WIDTH=10' demonstrates the MSE achieved by the fully connected neural networks with one hidden layer and corresponding width.
ATTENTION
WIDTH=10'
wIDTH=10'
WIDTH=10*
WIDTH=10'
WIDTH=10"
MS ETRAN
1.11
7796. 18
285.03
21.34 49.44
141.81
1048.91
MS MSEyss
0.02
6713.48
333.21
73.21
1099.98
demonstrates the huge gap between universal approximation and zero approximation error. Even in the simple two-dimensional setting for learning fp.1 = x² + xz a traditional neural network can not perfectly approximate fp.1 given large numbers of width through training. The performance the ultra-wide vanilla neural network with width=10 even drops dramatically.
The significance of zero approximation error Table 2
Table 3: The comparison of Mean Squared Error for learning fa. (x) + I2 + I3 24 x3)5 Column ATTENTION demonstrates the MSE achieved by our architecture, while Column NN depth and Wiwtd demonstrates the MSE achieved by the fully connected neural networks with comparable amount of parameters.
ATTENTION
NNdepth
NN
MSE TRAIN
1.67
177282.67
2440869.38
MSETEST
0.81
196548.68
2246920.0
Moreover, the gap between zero approximation error and universal approximation error can be large enough in the sense that the former can perfectly fit the target function while the latter can even diverge. This phenomenon can happen even for the = and case, which is demonstrated in the Table
Table 4: The comparison of Mean squared eтrоr for learning fo. = x² 2 Column ATTEN- TION demonstrates the MSE achieved by our architecture with 21 free parameters, while Column WIDTH=10² to Column WIDTH=10" demonstrates the MSE achieved by the fully connected neural networks with one hidden layer and corresponding width.
ATTENTION
WIDTH==10
WIDTI1=10
WIDTH==10
MSETRAIN
0.99
13.29
12.97
12.41
MSE
0.0002
11.57
11.56
11.29
8

---

Under review as a conference paper at ICLR 2023
Zero approximation cannot be achieved by the quadratic activation function Table shows the performance of different kinds of fully connected networks with the quadratic activation function. It is clear that Fully Connected networks with the quadratic activation function not achieve approximation error, which demonstrates the superiority of the self-attention transformer.
The self-attention transformer can avoid the trade-off between the approximation error and the sample error shows the mean squared error of our single-head self-attention model under different number of samples. The test mean squared error monotone decreases as the number of samples increases. Also, the training error monotone increases from 0. 1349 to 0.9660, which indicates our model prevents over-fitting the noise.
train,
test
50-
40-
30-
20-
300
5.5
3:50
3.75
4.00
<23
4.50
4.55
3.00
Nammerr
Figure 4: demonstration of the test error of our single-head self-attention model under different
number of samples. The x-axis is the base 10 logarithm of the number of training samples.
Performance on real-world data-set and beyond regression task Theorem 3.5 and Theorem 3.8 show that our proposed model can fit any desired polynomial function with no error. The aforementioned experiments verify our theorems on fitting polynomial functions. Two questions then arise naturally. 1) Whether our proposed ATTENTION model works well on real-world data-set? 2) Whether our proposed ATTENTION model works well beyond regression task, for example, on image classification task? We first conduct experiments Household Electric Power Consumption Data-set on Appendix B.3 and achieve better performance than fully connected neural networks with comparable number of free parameters. Moreover, apply our model to the image classification task and achieve better performance than Vision Transformer on the CIFAR-10 data set with suitable adaptations. The detailed description can be found on Appendix B.4
6 CONCLUSION
In this paper, introduced single-head self-attention transformer model and showed that any polynomial could be generated exactly by an output function of such a model with the number of transformer encoder blocks equal the degree of the polynomial. The transformer encoder blocks in this model do not need to be trained. We also show that the target a polynomial function, our proposed model can avoid the classical trade-off between approximation error and sample error for the regression task.
In the future, many research directions will be very attractive. First of all, our core idea is different from the traditional one of approximation, and through the appropriate adjustment of the transformer model, completely new theoretical result is presented. Also, in our structure, the transformer encoder blocks are completely fixed. It is of great interest to check our results in real applications see whether these adaptations can indeed bring benefits. Second, we have obtained such exciting theoretical results by considering only the single-head self-attention structure. We can consider whether the multi-head structure can lead to more surprising conclusions. Last but not least, it is of great interest to consider this model under the setting of statistical machine learning. As we can see in our experiments, as long as the number of free parameters meets the theoretical requirement, model not only learn the objective function well but also has much stronger generalization ability than other models. And as far as we are concerned, this the first deep learning model which capable of reaching zero approximation error for certain function classes.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Houschold electric power consumption - kaggle. https:/
http://wwwwwwggg....c ctmp uc (iimm/
set (Accessed on 05/20/2022).
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv preprint 1.XXv:1409.0472. 2014.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11991 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. ArXiv, abs/2010.1 19999, 2021.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Iryna Gurevych, Michael Kohler, and Gözde Gül Sahin. On the rate of convergence of a classifier based transformer encoder. arXiv preprint arX15:2111.14574, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436-444 2015.
Tong Mao, Zhongjie Shi, and Ding-Xuan Zhou. Theory of deep convolutional neural networks ii:: Approximating radial functions. Neural Networks, 144:778-790, 2021.
Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Interspeech, volume 2, pp. 1045-1048. Makuhari, 2010.
Kenta Oono and Taiji Suzuki. Approximation and non-parametric estimation of resnet-type convolu- tional neural networks. In International Conference on Machine Learning, pp. -922-4931. PMLR, 2019.
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. arXiv preprint arXiv:1806.00166 2018.
Johannes Schmidt- Schmidt-Hieber activation function. Annals of Statistics, 1875):887-1189)) 2020.
Nonparametrie regression using deep neural networks with relu
Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James T Kwok. Sparsebert: Rethinking the importance analysis in self-attention. arXiv preprint arXiv:2102.12871, 2021.
Leslie N. Smith and Nicholay Topin. Super-convergence: very fast training of neural networks using large learning rates. Defense + Commercial Sensing. 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequenee functions? arXiv preprint arXiv: 1911.9121.00770 2019.
10

---

Under review as a conference paper at ICLR 2023
Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. o(n) connections are expressive enough: Universal approximability of sparse transformers, arXiv preprint arXiv:2006.04550 04862, 2020.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. In NeurIPS, 2020.
Ding-Xuat Zhou. Deep distributed convolutional neural networks: Universality. Analysis and Applications, 16(06):855-119, 2018.
Ding- Ding-Xuan Harmonic Analysis, 4802):787-794,20000 2020.
Xuan Zhou. Universality of deep convolutional neural networks. Applied and Computational

---

Under review as a conference paper at ICLR 2023
A APPENDIX: PROOF OF MAIN RESULTS
Proof of Lemma 3.1 We present explicit constructions of matrices and biases in single-head self- attention transformer encoder block. We let W E ([++a) (2++++)) as follows,
0
0
0
0
2M
0 0
Wº
2M
0 0
0 0
2M
0
0
where the constant 1 in the first row is in the (n + 2) th column. And we set W t t= ., + 1 and all the other elements 0. Since the inputs are in the form of
2M for
(t.t)
2j U, E2, Ti. Di, O,
O, 1 R(ntg+2)x1
where e, denotes the one-hot vector of dimension n with value in the i-th position of 6G. Then know that qi (I-n)x1 is follows
6 1) enty
202
0,
0,
2M
0
We let W (2++))((++==)) as follows
0
0
0
0
0
0
WK
0 0
0
0
0
0
0
0 0
1 0
where the constant in the first row is in the (n + 3) th column. And we set WK = for t 2,...,, an + and other elements Then we have K R(1+a)x11 as
(f,t)
(++ 1)-th entry
k = W 2; = -,0.00,.. 0,
,,,,..0
We can easily find that for each i, if j = i, then (gi, ky) = aays + 2M2 And if j * i, then (4,, ky) = TzAli- By the condition |as| < M and lysl < M, clearly we have 2;y1 + 2B² > s:Yli- Then the attention vector a, is
a₁ = kggs k1), (q. kt). (g., kn)] E Rax1
Since we apply the one hot maximum function to a,, then by the construction we have
2 th entry
à = 00,..
2434 + 2B .0] g
For the matrix WV (m=+ we set
wy, 0,
i 4,j +
others.
Then we know that for i = 1....
(a++-4 1th entry
VV 10
12

---

Under review as a conference paper at ICLR 2023
By the equation
2 + WV Zûi we know that the outputs 2; E [(++)+))x of self-attentio layer are
2 [t,, eú T, Vi, 2,y, + 2M² ,0, 0,
where denotes the one-hot hot vector of dimension n with value in the i-th position of e;. Now we construct the fully connected layer in the transformer. For Wi E (2x we let
1, -1, i = others.
i = = n 4,
W W1,(1,)
0,
and bj = O], Then we have
oW + bi) = (o( + 2M2, ( -M 2M
For W2 E (2(++++)x22 we let
-2,
i=
W2,(k))
2,
i= =
0,
others.
And we let by E (R to be
2M22
n
b22(1)
0,
others.
Then by have
2, = 2 + W20 (W1 + b1) + b2.
x U1 es, Fi, -,y6 0, 0, 1j_ E [((+t++)x11
Since assume that M is known, we do not have any free parameter in this construction. It is easy to see that the number of non-zero entry is 2n + 8. This finishes the proof.
Now we are ready to prove Theorem 3.5
Proof of Theorem 3.5
To prove our main result polynomial generation, we first apply Lemma
3.3 Since the matrix E Ra, xd can be obtained by training, we set F === [S,,... ... -Sy] and &
to be those vectors we need in Lemma 3.3 for 1,.... Rgg Then we know that the inputs for the transformer encoder blocks are
[E 3r, 0,
O,
0, 0,0, TT
(++1) entry
for i = 1,... Mg. Then we only need to apply Lemma g times with suitable adjustments of the position of non-zero entries make sure that the product of two elements vectors are saved in right entry.
For the first transformer encoder block, we calculate the product of & and and place - x in the (ny + 2)-th -th entry. Since we know that |||||| 1, if we further assume that ||>||| < B, then we Lemma 3.1 and the output vectors are
have & x] < B. Then we only need to set M
24 L H, C,
E x. 0TT,
where e; denotes the one-hot vector dimension n with value in the i-th position e,. For the second transformer encoder block, we calculate the product of & x and -Ea x to get (&: x)² and place it in the (n, -t entry. We set M B in Lemma 3.1 and the output vectors
2: =(E F. Ci Ee vr (Ex x) ... ..... 0,1
13

---

Under review as a conference paper at ICLR 2023
Without loss of generality, to be odd. For the i-th block with i =3.... :9 we set M = B'- Then after q transformer encoder blocks, the outputs are
24 = [t,s Cii t2, E2
1J" (((+))))xx
where &2 E.- for 1, ng. Now we have different powers of & for 1,... ng. Then we only need to set elements of [3 as those Bk we need in Lemma 3.3 and = Q(0) to generate the polynomial Q we want.
Since we assume that B known, then there is no free parameter in transformer encoder blocks. The free parameters in our model all come from F, 3 and By ng = (d=1+)), it is easy to see that ny S d9 The number of free parameters in F is less then d Since for each 2;, only need non-zero entries in 3, the number of free parameters parameters less than d#+1 + qd"
is less then qd". So the total number free
The number of non zero entries in this model those in F, W Wº, W Wi, W2, b b2 in each block and in B, b. It can be calculated easily to know the number of non zero entries is less than d + 3qd + 8q + 1.
This finishes the proof.
We first present a bound for covering number of our hypothesis space H. (2) as stated in the lemma below. The covering number N (n, H.) of subset H of ((X)) defined for rj >> be the smallest integer 1 such that H is contained in the union of balls in C(X) of radius 17.
Lemma A.1. For q E N and H given in (2) with two constants C C, and C² B, depending on Sq, d, B, B, there holds
log {N (8:74) S (d + q 1)mg
+1mg log + C² a. log log
where C B. of and C" 9, (d q (log (Cqd.B.B) + +1).
Proof of Lemma A.7
For fixed q, (z(2) another function from the hypothesis space induced by B, E.,, satisfying the restrictions in and
|,, 3.11- S. & - E.11001 s 5.,11o b||50 8,
then we have
B concat (T"(x)) b- concat (fT(x)) - b1
$ B concat (T9())-
- (x)()) 11. + 11 - concat (T9 + +11--8)
Sqn sq Bdd + qm B3 +
<BB
Then, by taking 8-net for each of & 3 and b, we know that the covering number of the hypothesis space H with radius 8 (0, 1] can be bounded
2 dng 2B 91
N (8.HL I
dag + +
(2B) (2 +o
drg + +1
14

---

Under review as a conference paper at ICLR 2023
where C q, q² dBB Thus we have
log {N (8.7)) - (d + a 1)mg log
+ C²
a. log(ng):
where C q. (d+ (log (Co.,B.)) +1).
directly apply Lemma 4 in Schmidt-Hicher et al. (2020) or Lemma 5 in Oono & Suzuki (2019) to get
Proof of Theorem 3.8
With suitable scaling transformation,
inf - F22 log N H))
E Bl/. - fpll S (1 +e)
+ F28F
SEH
Ne
for all , > 0. Here F is the sup-norm of functions in H and we can take F = 2gm BBq, By
applying Lemma A.l 1. = d and N Tlg have
log N
BlIDD, - follxx & 144C" R.
6Aq
Rgg N
N
where C"
C²
q. 9² B2 Thus have
n² log N
|I Sollzx S &Oq....B
with C 9.8 1440" q.d.B.B + 64g This finishes the proof.
B EXPERIMENTAL DETAILS
In this section, we describe the additional details of experiments.
B. EXPERIMENTAL SETTING
Data generating process For the target function fp,1. we generate 10000 i.i.d. sample x from multivariate Gaussian distribution (0, )1) with E = diag 100). We randomly choose 9000 of them for training and 1000 data for testing.
For the target function f/.2, we generate 50000 i.i.d. sample x from a multivariate Gaussian distribu- tion (0, Σn) with Σ, diag(1, ,1) e R 10 We randomly choose 45000 of them for training and 5000 data for testing.
Training Hyper-parameter In all the experiments, we use SGD optimizer with one cycle learning rate Smith & Topin 2019). with initial learning rate 0.0001 and maximum learning rate 0.001. For the polynomial fp.1. we train three models 600 epochs with batch size 5000, and for the polynomial fa.2, we train three models 2000 epochs with batch size 25000. The gradient clipping is used for all three models to avoid gradients exploding at the beginning of training.
Model architectures Table 5 and 6 illlstrate the architecture of types of ReLU fully connected neural networks with comparable number of free parameters used in Section [5] The NNwidtth has the same kind of linear transformation from Rd - R.v as our single-head self-attention transformer, while the NN dedtpt has the same hidden layer q as our single-head self-attention transformer.
B.2 SENSITIVITY OF THE DEPTH OF OUR ATTENTION MODEL.
For real applications, we do not know the order of the oracle polynomial in advance. Therefore, give sensitive analysis of the depth of our ATTENTION model in this subsection. Table
15

---

Under review as a conference paper at ICLR 2023
Table 5: The architecture of NN width and Nedtpth for the target polynomial fi.
LAYER
NN.WIDTH
DETTE
LINEAK(N=22OUT=100)
LINEAR(N=220UUT44)
2
RELU
RELU
3
LINEAR(N==10,OUT--] LINEAR(N==4.OUT=4))
4
RELU
7
LINUAR(IN=4,OUT-L)
Table 6: The architecture of NNwidthh and NNdepth for the target polynomial fā.
LAYER
NN_WIDTH
NN_DEPTH
LLNEAR(IN=1,OUT-4455
LINEAK(N=10.0UT=1100)
RELU
RELU
x
RELU
13
LINEAR(N==10,0UTT=))
demonstrates that when the number of layers is smaller than the order of the polynomial, we cannot get the zero approximation error, while when the number of layers is larger than equal to the underlying order, our ATTENTION model consistently gives good approximation results. This experiment demonstrates our ATTENTION model is not sensitive to the choice of the depth. For real applications, we can increase the depth of our ATTENTION model when the training error is not small enough.
Table 7:
The comparison of Mean squared error for learning fp. = +2 by using our ATTENTION model with different number of layers.
ORACIE(DEPPHEE)
DEPTH=2
DEPTH=4
DEPTH=5
TRAIN 0.9906
13.20 11.42
0.9986 0.00037
0.9899 0.00036
MSE TEST
0.0002
B.3 EXPERIMENT RESULT ON THE REAL-WORLD DATA-SET
Table & demonstrates the effectiveness of our ATTENTION model on Houschold Electric Power Consumption data-set Hou| This data-set contains 2,075,260 samples gathered between 16/12/2006 and 26/1 1/2010. We use several properties (global reactive power, voltage, global intensity, and three substrings) to predict global active power and construct train/test sets with a ratio of after removing all the null data.
B.4 EXTENSION ON THE IMAGE CLASSIFICATION TASK
The architecture illustrated in Figure is designed for regression tasks. And experiments synthetic data and real-world data-set verify our theoretical results. In this subsection, we aim to demonstrate the potential of our proposed model the image classification task.
Model Architecture Since model is designed for the regression setting, try to modify model to the classification task. There are two major modifications for generalizing our model image classification task. First, borrow the idea of Vision Transformer (Dosvviskkiy al.
16

---

Under review as a conference paper at ICLR 2023
Table 8: The comparison of Mean Squared Error for real-world data-set, Household electric power consumption data-set. Column ATTENTION demonstrates the MSE achieved by our architecture, while Column depth and NN width demonstrates the MSE achieved by the fully connected neural networks with comparable amount of parameters.
ATTENTION
NNdepth
NNwidth
MSETRAIN
0.0044 0.0094
0.9038
0.0051
MSE TEST
0.9017
0.0097
(2021) to adjust our architecture. We split an image into several non-overlapped patches and adopt linear transformation to these patches. After the concatenation, we feed the resulting sequence of embedding to our ATTENTION model. Similar to Dosovitskiy et al. (2021). we also adopt the position encoding and extra learnable classification token. Second, like standard classification model, we use classification head to transform the representation to R where e denotes the class number.
Experiment setting demonstrate the advantage of our self-head ATTENTION model, we compare the classification results with the original Vision Transformer SeneffrmmrDDsooisskkiii Dosovitskiy et al. (202T) on CIFAR-10 data-set. CIFAR-I4 10 data-set Krizhevsvy (2009) contains 32x32 color training images in 10 classes. There are 50k training images and 10k testing images.
We try different model setting for a comprehensive comparison. For VIT, we set the layer as 12, the number of patch 4, 8, 16, and the number of attention head 12. For our single-head ATTENTION model, we set the layer as 2 and the number of patch as 4, 8, or 16. Moreover, we also try adopt the hybrid architecture proposed in Section 3.1 in Krizhevsky (2009), i.e., instead of using the raw image patches, we use the feature map encoded by the CNN model.
Training Hyper-parameter In all the experiments, we use SGD optimizer with one cycle learning rate Smith & Topin (201),, with an initial learning rate 0.001 and maximum learning rate 0.01. We train each model for 200 epochs with batch size 512.
Experimental results Table 9 demonstrates the effectiveness of our single-head ATTENTION model on CIFAR- 10 data-set. Our model consistently gives better results on different patch size even though the weights in our ATTENTION block do not need to train. These experimental results further confirms potential of our proposed ATTENTION model.
Table 9:
The comparison of testing accuracy CIFAR-10 data-set. VIT denotes the vision trans-
former and ATTENTION denotes our model.
TEST Acc(%)
VIT LAYER=8 PATCH=16
65.36
VIT LAYER=12 PATCH=8
74.92
VIT LAYER=12 PATCH=4
81.08
VIT HYBRID
81.26
ATTENTION PATCH=16
73.34
ATTENTION PATCH=8
73.02
ATTENTION PATCH=4
71.44
ATTENTION HYBRID
85.43
Further discussion model.
There are some interesting studies of our proposed single-head ATTENTION
1. Why the performance of the Vision Transformer is much lower than that reported in Krizhevsky (2009)?
17

---

Under review as a conference paper at ICLR 2023
2. Whether smaller patch size can improve the performance of the results of our ATTENTION model?
Whether the hybrid architecture can further improve performances of the model?
We give detailed discussion of the above questions.
1. The accuracy of VIT is different from the Table 2 in Krizhevsky (2099) because we train the model on CIFAR-10 from sketch, while the author Krizhevsky (2009) pretrain the VIT on huge vison data-sct, i.c., ImageNet, ImageNet-2 and JFT-300M, and finetune it on CIFAR- 10. The performance of VIT drops dramatically when the number of sample becomes smaller. Our ATTENTION model can achieve better results than VIT without training the attention weights and with much smaller attention heads might give some inspirations for further design of the Transformer model the small data regime.
2. The larger patch size gives better performance for ATTENTION model, which is different from the case of VIT. This phenomena matches the design of the data-preprocessinng process in our ATTENTION model well since it encourages on the full input data to capture some global information.
linear transformation
3. Using a hybrid architecture can improve the performance our ATTENTION model dramatically (+12.41%). This illustrates the superiority of the convolution architecture to capture local information of image data than linear transformation, which gives some insights to further improve the ATTENTION architecture.
18


Reviews:
[{"review_id": "R8xto3KbYH", "reviewer": "Reviewer_4Zo8", "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": "This paper shows the single-head self-attention transformer with a fixed number of transformer encoder blocks and free parameters could generate the desired polynomial of input directly without approximation. Further, the author shows that with the increasing number of free parameters and polynomial of degree q, the single-head self-attention transformer block is universal.", "summary_of_the_review": "As above, my main concern is:\n1. This theory included two strong assumptions, which limits its application value.\n2. Compared with Yun et al. (2019), the benefit is not obvious to me.", "strength_and_weaknesses": "Strength:\n1. The number of required transformer blocks is relatively small.\n2. The transformer encoder is not needed to be trained, with the cost of introducing free parameters F, \\beta, and b.\n3. The modification is relatively simple compared with the original scale single-head self-attention layer.\n\nWeakness:\n1. Only discussed the upper bound of free parameters, which is very large.\n2. In my understanding, most of the analysis is based on the assumption that the target function is polynomial.\n3. Limits its application to regression and classification.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "O0vQcWP5VHz", "reviewer": "Reviewer_HdBP", "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 presents a novel theoretical analysis of the Transformer networks, showing that with a special preprocessing, Transformer can universally approximate any polynomial function. The theoretical analysis is based on a simplified transformer which only has a single attention head and only handle fixed input size. The authors also show that the proposed method can avoid the approximation error and sample error trade-off. Finally, the authors provided experimental results to verify their analysis.", "summary_of_the_review": "Overall, it is a novel perspective to understand a Transformer and has a lot of potential. My main concern is about the fixed length of input, because (1) Transformer is a powerful network in sequence modeling; (2) previous works, e.g., Yun et al. (2019), already can analyze the sequential input.", "strength_and_weaknesses": "Strength:\n\n- The presented theoretical analysis framework is novel.\n- The conclusion that a Transformer can universally approximate a polynomial function is strong.\n\nWeakness:\n\n- The study assumes that the input has a fixed size, i.e., $x \\in R^d$ where d is a constant. This is not true when a Transformer is used for sequence modeling.\n- The preprocessing only uses matrix F to embed the x, not considering positional embedding, which is important for Transformer.\n- The main experiment is only on synthetic data.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JCNIMKoY3_", "reviewer": "Reviewer_H8Qq", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper introduces a single-head self-attention transformer model and shows that any polynomial function could be generated exactly by an output function of such a model with the number of transformer encoder blocks equal to the degree of the polynomial. Furthermore, these transformer encoder blocks in this model do not need to be trained. Various experiments and ablation studies to verify our theoretical results demonstrate the effectiveness of their theoretical results.", "summary_of_the_review": "This paper provides theoretical results for single-head Transformer and the results are interesting. They also perform various experiments to support their conclusions.", "strength_and_weaknesses": "Strength: This paper provides a theoretical view towards the Transformer block and the theoretical results are interesting. Even though the experiment data is synthetic, the experiments can back up their experiment results. \n\nWeaknesses:\n(i) In Section 4, the authors discuss the difference between their paper and the previous paper. One difference is that prior papers focus on seq-to-seq tasks and they focus on regression tasks. However, I think seq-to-seq tasks are more universal than the latter one. Thus, is the conclusion weaker than the previous one? \n(ii) The authors introduce the single-head Transformer but ignore the effectiveness of multi-head. Can you explain the effect of the number of heads in your theoretical results? As all we know, the multi-head mechanism can improve performance.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CLzqlxO1kH", "reviewer": "Reviewer_8KLD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 proves that transformers with single-head attention and a specific embedding scheme can express any polynomial by constructing the weights required for forming a polynomial.", "summary_of_the_review": "In summary, the paper shows a clear construction of how to express polynomials with transformers, but the significance is borderline.", "strength_and_weaknesses": "Pros:\n- The construction is clear and interesting.\nCons:\n-  Most of the claims in the paper are just simple consequences of the exact construction. For example, \"the encoder blocks do not need to be trained\" and \"avoiding the classical trade-off between approximation error and sample error\" are just because the construction gives exact polynomials. However, the authors intentionally highlighted these as new contributions, making the paper a little overclaimed.\n- The comparison of the transformer and fully connected network in this paper is not fair because it is obvious that the transformer can compute functions over different tokens, while the only way for the fully connected network considered in this paper to mix different tokens is by using the linear combination in the last layer. Given the discussion in the paper is limited to fixed-length input, a better baseline would be a fully connected network over different tokens.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7ebJ4FLv9mr", "reviewer": "Reviewer_sof3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper analyses the potential for attention-based networks to model polynomial functions. The approach consists in taking a variation of the single-head transformer, and show that with proper input preprocessing and a specific set of fixed weights it can be set to any polynomial. The authors back their claims with mathematical proofs, and confirm them with experimental results on synthetic data. They also show that such a model can perform better than a Visual Transformer on the CIFAR10 dataset.", "summary_of_the_review": "Although taking an interesting approach, the paper does not convey compelling results in a convincing manner. The vocabulary used (attention, transformer, etc) is misleading with respect to the actual results, which say very little about transformers and (standard) attention. I tend to consider this a correctness issue: even though the theorems and lemmas are correct, the conclusions drawn from them are not.\n\nI do not think that this paper in its current form should be accepted.", "strength_and_weaknesses": "**Strengths**: The paper's claims are well detailed. The authors provide a complete formalism, and despite technicality the results and proofs are relatively easy to follow. Theoretical results seem correct and I have no reason to doubt the empirical ones.\n\n**Weaknesses**: Although I don't technically doubt them, I think that the core findings of the paper are weaker and less novel than the authors claim them to be, and could be considered misleading. I have two major concerns.\n\nFirst, the authors mention that the softmax in the transformer encoder block is replaced with \"one hot maximization\". This is all but an innocuous change. Softmax outputs a probability distribution which at the limit becomes hard attention (the largest value becomes 1 and the others 0). But one hot maximization keeps the largest value in the attention scores. After multiplying those scores with the values, the output of the self-attention layer is quadratic. That makes it easy to use to model polynomials, but it hardly says anything about standard self-attention. Therefore the claim in section 4 that the authors \"guarantee the integrity of transformer encoder blocks\" is misleading.\n\nSecond, the authors fix the transformer weights in all experiments in order to model polynomials. The output is always of the form $t,t^2,...,t^n$ with $t$ the input. The only trained weights in an initial linear layer $F$, and most importantly weighting coefficients of the outputs. In other words, the model they train is just a linear model on the outputs of $F$ in a polynomial feature space. That such a model is good at modeling polynomials is obvious, and that it performs better than a large neural network on small datasets is not particularly surprising either.\n\nI would argue that the paper is not really about transformers or self attention. They show that a model which isn't really a transformer but contains inner products can with specific weights be set to a polynomial feature extractor - though not a very efficient one. There are certainly interesting aspects of that result but they are not the ones the paper focuses on.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject