Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically analyzed the reason why transformers could outperform fully-connected NNs in NLP tasks.
This 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.
strength_and_weaknesses: Strength:
The 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.

Weakness:
All claims are not supported by experiments, see details below.
clarity,_quality,_novelty_and_reproducibility: In lines 5-9 of the abstract and the second paragraph of the introduction, the author claimed the transformer could avoid the curse of dimensionality in the setting of fixed-length input and Besov space. This conclusion is mainly from Suzuki (2019) and Suzuki & Nitanda (2021). However, as far as I know, those two papers are not related to the transformer. So in order to claim and convince others that the transformer could also avoid the curse of dimensionality, experiments are necessary. This claim could also be found in the last sentence of page 6, but Suzuki (2019) and Suzuki & Nitanda (2021) never mentioned the transformer in their paper, as far as I know.

In the third paragraph, the author claimed that it is hard to study the representation (approximation) ability of the transformer as tokens interaction is only learned by pairwise dot-products. I agree with this claim. However, many related works in this branch are missed. e.g. Yun et al. (2019), Zaheer et al. (2020), Shi et al. (2021). Indeed, most of them proved that the transformer is the universal approximator of sequence-to-sequence functions with the limited pairwise dot-products, or even in the sparse attention setting. The author should compare this branch of work when analyzing the approximation ability, especially on the proof strategy.



Reference:
Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James T Kwok. Sparsebert: Rethinking the importance analysis in self-attention. In International Conference on Machine Learning, pp. 9547-9557. PMLR, 2021.

Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In ICLR, 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.




summary_of_the_review: The claim is not well-supported due to the lack of experiments and related works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Transformer networks are not well understood theoretically. This paper provides some interesting results to verify the efficiency of transformer networks. 
Besov 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. 
clarity,_quality,_novelty_and_reproducibility: The paper is well written. The role of transformers is not well explained in the paper. Based on a few papers published by the group of T. Suzuki, this one does not present much originality. 
summary_of_the_review: Transformer networks are not well understood theoretically. The topic deserves extensive study. 
Besov 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.
review_title: null

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

1. The paper addresses an important issue in the study of transformers, which is the approximation and estimation error of transformers.

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

3. The theoretical results in the paper explain the phenomenon that the transformer models dynamically select tokens to pay attention to. 

**Weak points:**

1. Experimental results are needed to corroborate the theoretical results in the paper.

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

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

**Minor Comments that did not Impact the Score:**

1. Can the results in the paper be extended to a variable length setting and to linear transformers?

**References:**

[1] Kratsios, Anastasis, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić. "Universal approximation under constraints is possible with transformers." arXiv preprint arXiv:2110.03303 (2021).

[2] Vuckovic, James, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of attention. ArXiv preprint arXiv:2007.02876, 2020.

[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).


clarity,_quality,_novelty_and_reproducibility: The clarity of the paper can be improved. The quality and novelty of the paper are high. There is no experimental result in the paper.
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. 

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

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies how fixed-length Transformer networks can approximate anisotropic Besov and mixed smooth Besov
spaces. 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
parameter 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. 
strength_and_weaknesses: Strengths:
- The paper studies the approximation error of Transformer networks which is a timely and important problem. 
- 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. 
- The 'Token extraction property of Transformer networks' in Section 5 highlights some interesting properties which resembles/alludes to attention mechanism in transformers.

Weaknesses:
- The main Theorems are not easy to understand. A corollary where the approximation error is directly linked with the 
- 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.
- 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.
- The importance of Besov spaces in approximation theory, and its comparison with other concepts, like universal approximation, should be discussed.
- Definition 4 seems to be a restatement of Definition 1. 
- Definition 10 is $\pi$ missing from the definition of $VU$?
- "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? 
clarity,_quality,_novelty_and_reproducibility: The paper is hard to follow, and the implication of the theorems are not clear as the expressions are indirect and hard to parse.

The paper provides new results relating approximation error of Besov spaces using finite-length Transformers, which is timely and possibly important. However, lacks in the discussion of related works, clarity in expressing the final results, and highlighting the novelty w.r.t. Suzuki & Nitanda 2020. These omissions make judging the quality of this work difficult.

The paper seems to be novel as it studies the approximability of Transformers with respect to Anisotropic and Mixed Smooth Besov spaces. However, the technical difficulty in analyzing Transformers with respect to Suzuki & Nitanda 2020 is not discussed clearly. 

The paper is reproducible. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper attempts to understand expressive power of popular transformer networks. In particular, the paper studies how fixed-length Transformer networks can approximate anisotropic Besov and mixed smooth Besov spaces. Compared to prior work on expressivity of transformer, this paper provides error rates rather than just stating that transformers are universal approximator (Emphasizing this point in the paper would be beneficial). This problem is of wide interest and the paper could have been timely, but unfortunately the results in the paper are not presented in very accessible manner. Most reviewers found the paper hard to follow and comprehend. The implications of the theorems can be made elaborate by adding a few corollaries of very simple special cases where the expressions are direct and clear to see the benefits. We thank the author and reviewer for engaging in discussion towards making the paper better. It would be useful to add a small discussion on key difficulties in moving from fully connected to transformer network in Suzuki & Nitanda 2021 framework (mostly as described in author response). Incorporating all the reviewer feedback would require a fair amount of rewriting and thus warrant another round of reviewing.
justification_for_why_not_higher_score: - Main reason: Hard to parse results and implications
- Limited development over Suzuki & Nitanda 2021 work
Decision: Reject