Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:
1. The number of required transformer blocks is relatively small.
2. The transformer encoder is not needed to be trained, with the cost of introducing free parameters F, \beta, and b.
3. The modification is relatively simple compared with the original scale single-head self-attention layer.

Weakness:
1. Only discussed the upper bound of free parameters, which is very large.
2. In my understanding, most of the analysis is based on the assumption that the target function is polynomial.
3. Limits its application to regression and classification.
clarity,_quality,_novelty_and_reproducibility: The author included many details in the supplementary material, which is convincing. And the author compared this work with Yun et al. (2019) heavily, which is very necessary. However, I am not convinced by the comparison result.

In Yun et al. (2019), they explored the representation power of the transformer by showing that it is a universal approximation of sequence-to-sequence functions with less number of required parameters compared with the residual network (Section 4.4 in Yun et al. (2019)). 

In addition, this paper limits the target function as polynomial and the task as regression and classification, but Yun et al. (2019) do not have such requirements. 

Further, it is true that Yun et al. (2019) is the approximation, but their 'error' between continuous functions and piece-wise functions, transformers and modified transformers, and piece-wise functions and modified transformers are infinitesimal. I could not find the advantage of using polynomials directly compared with the universal approximation theory Yun et al. (2019) adapted. 

Finally, yes Yun et al. (2019) is not focused on the dot product (or the attention matrix), but many following works covered this direction. Such as Yun et al. (2020), Zaheer et al. (2020), and Shi et al. (2021).
summary_of_the_review: As above, my main concern is:
1. This theory included two strong assumptions, which limits its application value.
2. Compared with Yun et al. (2019), the benefit is not obvious to me.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 

Weaknesses:
(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? 
(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.

clarity,_quality,_novelty_and_reproducibility: Clarity: Fair
Quality: Fair
Novelty: Fair 
Reproducibility: Fair
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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.

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

First, 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.

Second, 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.

I 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.
clarity,_quality,_novelty_and_reproducibility: **Clarity**: the mathematical results are well detailed. The overall language can be improved. A section on related work on theoretical analysis of transformers (with more papers than the 3 in section 4) should be added.

**Quality**: As I explained above, there is a problem with the core results of the paper. Their actual content and limited impact contrasts with what the authors claim they achieve.

**Novelty/Originality**: On the theoretical side, the overall approach of showing that fixed sets of weights in popular architectures turn them into classic functions seems novel and original. It would however be more convincing if the authors did not change the softmax layer (or changed it to a hard attention). On the experimental side the paper shows that standard machine learning models can outperform neural networks on some small datasets. This seems hardly novel to me.

**Reproducibility**: Experimental hyperparameters are well detailed in appendix, and the authors provide their code. One minor issue in section 5.1 is that sampling function of input $x$ should be mentioned. It's essential to understand the results, especially how shallow networks behave on that data, and should not be in appendix.
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.

I do not think that this paper in its current form should be accepted.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Pros:
- The construction is clear and interesting.
Cons:
-  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.
- 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.
clarity,_quality,_novelty_and_reproducibility: The paper is clear, while some of the statements are a little overclaimed. Overall, the results are interesting but natural because, with the inner product structure of attention, it is easy to construct the basic components to form 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:

- The presented theoretical analysis framework is novel.
- The conclusion that a Transformer can universally approximate a polynomial function is strong.

Weakness:

- 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.
- The preprocessing only uses matrix F to embed the x, not considering positional embedding, which is important for Transformer.
- The main experiment is only on synthetic data.

clarity,_quality,_novelty_and_reproducibility: 
Clarity: fair, in general it can be understood with some effort.

Quality: the theory analysis is good; the experiments are weak.

Novelty: very novel.

Reproducibility: good. It will be easy to implement such a network.

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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studied theoretical properties of attention-based models for representing polynomials. It does not study the exact popular form of (self-)attention but another construction, which limits the scope of applicability of the findings. The bound on free parameters is not convincingly useful. Albeit interesting, the current form of the paper is not suitable for ICLR.
Decision: Reject