Approximation Rate of the Transformer Architecture for Sequence Modeling

Authors: haotian  jiang
qianxiao  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 01:51:24

Abstract: The Transformer architecture is widely applied in sequence modeling applications, yet the theoretical understanding of its working principles remains limited. In this work, we investigate the approximation rate for single-layer Transformers with one head. We consider general non-linear relationships and identify a novel notion of complexity measures to establish an explicit Jackson-type approximation rate estimate for the Transformer. This rate reveals the structural properties of the Transformer and suggests the types of sequential relationships it is best suited for approximating. In particular, the results on approximation rates enable us to concretely analyze the differences between the Transformer and classical sequence modeling methods, such as recurrent neural networks.

Main paper: 
 introduction: 
 The Transformer architecture, as introduced by Vaswani et al. [30] has become immensely popular in the field of sequence modeling. Variants such as BERT [8] and GPT [6] have achieved excellent performance, becoming the default choices for natural language processing (NLP) problems. Concurrently, Dosovitskiy et al. [11] successfully applied the Transformer to image classification problems by flattening the image into a sequence of patches. Despite its success across various fields of practical application, many theoretical questions remain unanswered. Among these, we focus on two essential questions in this work: firstly, the approximation rate of the Transformer on sequence modeling; secondly, the comparative advantages and disadvantages of the Transformer with recurrent neural networks (RNNs) on different temporal structures.The concept of Jackson-type approximation rates is derived from the Jackson Theorem for polynomials [15] , and is further elaborated in the work of DeVore [9] for addressing general forward approximation problems. To illustrate this, consider classic polynomial approximation. It involves defining an appropriate approximation space, accompanied by specific complexity measures, precisely the Sobolev space. According to the Jackson theorem, a function with a small Sobolev norm can be efficiently approximated by a polynomial. We aim to establish similar approximation rate results for the Transformer. This identifies the type of targets that the Transformer can efficiently learn. We examine general non-linear sequence-to-sequence target relationships, extending the linear target form explored in previous studies of the approximation results for linear RNNs and linear temporal convolution networks [24, 16] . We introduce a novel notion of complexity, establishing a concrete target space from which approximation rates can be deduced. This enables us to identify the types of sequential relationships that Transformer can approximate efficiently. Based on our theoretical analysis, we identify concrete classes of temporal structures where the Transformer outperforms the RNNs and vice versa. Our main contributions are summarized as follows: 1. We develop Jackson-type approximation rate results for single-layer Transformer networks with one attention head. Our analysis reveals that the approximation capacity is governed by a low-rank structure within the pairwise coupling of the target's temporal features. Empirical validation confirms that the findings observed under theoretical settings also hold true in practical applications. 2. We conduct a comparative analysis between the Transformer and RNNs, aiming to identify specific types of temporal structures where one model excels or underperforms compared to the other.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract and introduction accurately reflect the paper's contributions and scope.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 We first review the approximation results of Transformer networks. The universal approximation property (UAP) of the Transformer architecture is first proved in Yun et al. [33] , which is further extended to Transformers with sparse attention matrices [34] . The above universal results are developed for a deep Transformer structure. In contrast, Kajitsuka & Sato [17] applying a similar technique to prove one layer Transformers can achieve UAP by increasing the width. Additionally, Kratsios et al. [19] , Edelman et al. [12] , Luo et al. [25] considers the UAP of the Transformer in various different settings. Giannou et al. [13] considers a special setting regarding expressiveness, demonstrating that Transformers can represent any computer program. Beyond the UAP results, there have been developments in specific approximation rate results. Gurevych et al. [14] demonstrated the rate of the misclassification probability by considering the approximation of hierarchical composition functions, which are composed of sparse functions. This rate takes into account both the level of composition and the smoothness of the component functions. Bai et al. [1] and Wang & E [31] explore target relationships with certain special structures. Additionally, Takakura & Suzuki [29] developed approximation rates for a function space consisting of infinite-length sequence-to-sequence functions, which is characterized by the smoothness of the functions. Our approximation rate result steps further by considering temporal structures, shedding light on how the Transformer model handles temporal relationships. Apart from the approximation results, numerous intrinsic properties of the Transformer have been investigated. Dong et al. [10] and Bhojanapalli et al. [4] considers the rank structure of the attention matrices. Levine et al. [20] examine the correlation between the dependency of input variables and the depth of the model. The Transformer is a very flexible architecture, such that a special configuration of parameters can emulate other architectures. For example, Cordonnier et al. [7] , Li et al. [21] showed that attention layers under certain assumptions can perform convolution operations. However, not all emulations are valid explanations of the working principles of the Transformer. In this context, definitions of complexity measures and the resulting Jackson-type approximation rate estimates provide more insight into the inner workings of the architecture. This is the focus of the current work.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We made simplification and assumptions for theoretical analysis. However, we performed empirical experiments to demonstrate the implication of the theoretical results also holds true in general settings. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
sequence modeling as an approximation problem: 
 We first motivate the theoretical settings of Jackson-type approximation rate results by considering classic polynomial approximation. Then, we formulate the Transformer as an instance of such an approximation problem.Motivation of Jackson-type Approximation Rates Consider two normed vector spaces, X and Y, designated as the input and output spaces, respectively. We define the target space C ⊂ Y X as a set of mappings from X to Y that we aim to approximate with simpler functions. The hypothesis space is denoted by H = m H (m) , where H (m) represents a sequence of hypothesis spaces. Here, m denotes the complexity or the approximation budget of these spaces. Hypothesis space H encompasses the candidate functions used to approximate targets in C. Let α be a constant, we introduce a complexity measure, denoted as C (α) : C → R, based on the structure of H. The complexity measure is used to construct an approximation space C (α) := {H ∈ C : C (α) (H) < ∞}, which is usually dense in C. Then for any H ∈ C (α) , the Jackson-type approximation rate is expressed as follows:infEQUATIONHere, the error bound E(•, m) decreases to zero as m approaches infinity, and the rate of decay is usually called the approximation rate. In this context, C (α) (H) quantifies the complexity of a target H when approximated using H. A smaller value indicates that the target H can be more efficiently approximated with candidates from H. Consequently, the complexity measure discerns the types of targets that can be efficiently approximated within the given hypothesis space. Notably, different hypothesis spaces typically give rise to different complexity measures and approximation spaces. These variations characterize the approximation capabilities of the hypothesis spaces themselves.Defining an appropriate approximation space C (α) is essential. Without specific structures, the general target space C does not provide any rate results. Opting for an approximation space with defined structures allows for the derivation of approximation rates. Moreover, the property that C (α) is dense in C ensures that the restriction to C (α) is not overly limiting, preserving the necessary expressiveness of the space. To illustrate these concepts, we consider polynomial approximation over the interval [0, 1]. In this case we set X = [0, 1] and Y = R. The target space C = C([0, 1]) is the set of continuous functions defined on [0, 1]. The hypothesis space comprises all polynomials, expressed as follows:H = m∈N H (m) = m∈N Ĥ(x) = m-1 k=0 a k x k : a k ∈ R .According to the Jackson theorem for [15] , the Sobolev norm serves as an appropriate complexity measure, defined as α) be the approximation space containing targets with finite complexity measures. Consequently, for H ∈ C (α) , we have the following approximate rate: infC (α) (H) = max r=1...α ∥H (r) ∥ ∞ . Let C (EQUATIONHere, c α is a constant depending only on α. This theorem implies that smooth functions with small Sobolev norms can be efficiently approximated by polynomials. Developing Jackson-type approximation rates for various sequence modeling hypothesis spaces is crucial for understanding their differences. Jackson-type results for RNNs, CNNs, and encoder-decoder hypothesis spaces have been established in Li et al. [24] , Jiang et al. [16] , Li et al. [23] , where complexity measures such as decaying memory and sparsity were found to influence the approximation rates. In Section 4.1, we identify appropriate complexity measures regarding the Transformer and develop corresponding approximation rates. This enables us to discern the essential structures that facilitate efficient approximation using the Transformer. Furthermore, it allows us to understand how and when the Transformer architecture differs from traditional sequence modeling architecture RNNs, which we will discuss in Section 6.In sequence modeling, we seek to learn relationships between two sequences x and y. Mathematically, we consider an input sequence spaceEQUATIONHere, [τ ] := {1, . . . , τ } and τ denotes the maximum length of the input, and we focus on the finite setting, where τ < ∞. Corresponding to each input x ∈ X is an output sequence y belonging toEQUATIONWe use H := {H t } τ t=1 to denote the mapping between x and y, such that y(t) = H t (x) for each t ∈ [τ ]. Define C(X , Y) to denote the space of continuous mappings between the input and output space. We may regard each H t : [0, 1] d×τ → R as a τ -variable function, where each variable is a vector in [0, 1] d . Next, we define the Transformer hypothesis space.The Transformer Hypothesis Space. We consider the following Transformer block retaining most of the important components.EQUATIONwhere ĥ = f • x and F : R mv → R, f : R d → R n are two feed-forward networks. The parameter matrices have dimensionW Q , W K ∈ R m h ×n , W V ∈ R mv×n . The softmax function is denoted as σ, such that σ[ρ(t, •)](s) = exp(ρ(t,s)) s ′ exp(ρ(t,s ′ )). We focus on a simplified architecture: a single-layerTransformer with one head. In this work, layer normalization and residual connections are not taken into account. While this constitutes a simplified setting intended for theoretical analysis, it's worth noting that the phenomena observed under the theoretical settings also hold true in practical applications, as we have demonstrated in Section 5. The approximation budget of the Transformer depends on several components. We use F(mFF) to denote the class of feed-forward networks used in the Transformer with budget m FF , which is usually determined by the number of neurons and layers. Let m = (n, m h , m v , m FF ) denote the overall approximation budget. We use H (m) to denote the Transformer with complexity m. Then, we define the Transformer hypothesis space byEQUATIONQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: We conducted numerical experiments, with settings clearly presented in the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
approximation results: 
 Following the motivation of approximation problems for sequence modeling as discussed in Section 3, this section discusses the approximation rate results for the Transformer. Firstly, we introduce the notion of the permutation equivariance property of the Transformer and discuss the role of position encodings in eliminating it. Next, we define the target space and present the corresponding representation theorem. We then establish the complexity measures necessary to form the approximation space. Our main result Theorem 4.2 presents the approximation rate results.Permutation Equivariance and Position Encodings Our objective is to approximate a target relationship H where each H belongs to C(X , Y). It is important to note that without specific modifications, the Transformer inherently cannot approximate such targets due to its permutation equivariance properties. This property implies that permuting the temporal indices of the input sequence results in a corresponding permutation of the output sequence. More precisely, if p denotes a bijection on [τ ] representing a permutation of τ objects, a sequence of functions H is considered permutation equivariant if for all bijections p and inputs x ∈ X , the condition H(x • p) = H(x) • p holds. The Transformer Ĥ within the hypothesis space H is indeed permutation equivariant (refer to Appendix A for details). Directly applying the Transformer, therefore, yields permutation equivariant hypotheses, which are inadequate for approximating general sequential relationships that lack this symmetry. In practical applications, incorporating position encodings is a widely adopted approach to counteract permutation equivariance [30] . Various methods exist for embedding positional information. The simplest approach is fixed encoding, which involves mapping x(t) to a higher-dimensional space and then offsetting each x(t) by distinct distances. Formally, with A ∈ R d ′ ×d where d ′ ≥ d and a constant or trainable e(t) ∈ R d ′ , position encodings can be expressed as x(t) → A x(t) + e(t). For general purposes, it's sufficient for the encoded input space X (E) to satisfy the following condition:EQUATIONThis ensures that for each input x = (x(1), . . . , x(τ )), all tokens x(i) and x(j) are distinct, meaning no two input sequences are temporal permutations of each other. Define the set I = I s to be the range of the inputs. Moving forward, we assume that position encoding has been applied, allowing us to consider X (E) as the input space. Consequently, we define the target space to be C = C(X (E) , Y), which denotes the space of continuous mappings between X (E) and Y.To derive the Jackson-type approximation rate, it is necessary first to define the complexity measures to form an approximation space so that approximation rates can be obtained. We begin with the following representation theorem for the target space.Representation of the target space C Given that the Transformer inherently captures both pairwise and pointwise relations among input tokens through attention and feed-forward components, respectively, we are motivated to establish the following representation theorem for the target space C. This theorem demonstrates that every target can be exactly expressed in terms of pairwise and pointwise relations.Theorem 4.1 (Representation of the target space). Consider d-dimensional, length τ input space X (E) with position encoding added. Then, for any H ∈ C(X (E) , Y), there exists continuous functionsF ∈ C([0, 1] n , R), f ∈ C(I, [0, 1] n ) and ρ ∈ C(I × I, R) such that for all t ∈ [τ ]we haveEQUATIONwhere n = 2τ d + 1 and σ is the softmax function. The proof is presented in Appendix A.2.We refer to ρ as the temporal coupling component and F and f as the element-wise components. It's important to note that the functions F , f , and ρ may not be uniquely determined. In Appendix B.1, we explore certain invariant properties associated with Equation 8. Additionally, we provide illustrative examples in Appendix B.1 where the target explicitly conforms to Equation 8. Leveraging this representation theorem, we define the following complexity measures for targets H ∈ C.Temporal Coupling Component Now, we discuss the complexity measures associated with the temporal coupling term ρ(u, v) that is central to understanding the attention mechanism in the Transformer. We employ the proper orthogonal decomposition (POD) [3] to decompose the temporal coupling of ρ. This approach can be viewed as an extension of matrix singular value decomposition (SVD) to functions of two variables. We have the following decomposition:ρ(u, v) = ∞ k=1 σ k ϕ k (u)ψ k (v), where ϕ k , ψ k are orthonormal bases for L 2 (I), and the singular values σ k ≥ 0 are arranged in descending order. The bases ϕ k and ψ k are of optimal choices, ensuring that ρ(u, v) satisfies:EQUATIONanalogous to the Eckart-Young theorem for matrices, with the rank defined as the number of terms in the POD decomposition. This implies that the approximation quality of ρ(u, v) can be measured by the decay rate of its singular values. This motivates our following definition of complexity measure regarding ρ. Let α > 1/2 be a constant, and {σi } be singular values of ρ under POD. We define the complexity measure of H byEQUATIONwhere the first infimum is taken over all F, f, ρ such that Equation (8) holds. In particular, C1 (H) < ∞ if it has a representation in the form (8) with ρ having fast decaying singular values.Element-wise Component Now, we introduce the complexity measure for approximating the element-wise components F and f . Let F (mFF) be a hypothesis space comprising feed-forward neural networks with a budget of m FF , representing parameters such as width or depth. We assume the existence of β > 0 such that:EQUATIONHere, C FF represents a complexity measure of f corresponding to its approximation by F (mFF) . It is essential to emphasize that we are assuming the existence of pre-existing approximation rate results for the feed-forward component. For instance, in Barron [2] , F (mFF) is considered to be one-layer neural networks with sigmoidal activation, where m F F corresponds to the width of the network. By adopting this result, we have β = 1/2 and C (β) FF (f ) is a moment of the Fourier transform of f . For shallow ReLU networks commonly used in Transformers, Klusowski & Barron [18] demonstrate β = 1/2 + 1/n, where n is the input dimension of the neural network. We maintain the generality of Equation (11) . This enables us to substitute any other relevant estimates from the mentioned references. This flexibility allows for a broader application of the complexity measure in different scenarios and settings. Next, we proceed to define the complexity measure for H ∈ H. This measure considers all the components that need to be approximated using the feed-forward network.EQUATIONwhereC (β) FF (ρ, k) = k i=1 (C (β) FF (ϕ i ) + C (β)FF (ψ i )) considers the approximation of the approximation of the POD bases ϕ i and ψ i for the target function ρ . Notably, this complexity measure is dependent on a parameter k, which determines the number of bases we want to consider in the approximation of ρ. Finally, we define a complexity measure considering the norm of the target.EQUATIONwhere K F is the Lipschitz constant of F and ϕ i , ψ i are POD bases of ρ.Approximation Rates Combining the complexity measures Equations ( 10) and ( 13) and Equation (12) discussed above, we define the approximation spaces, which consists of targets that have finite complexity measures:EQUATIONOne can understand this as an analog of the classical Sobolev spaces for polynomial approximation but adapted to the Transformer hypothesis space. Note that C (α,β) is also dense in general continuous target space C(X (E) , Y) when n sufficiently large (See Appendix A.2). We are now ready to present the main result of this paper. Theorem 4.2 (Jackson-type approximation rates for the Transformer). Consider sequences with a fixed length τ . Suppose the target H ∈ C (α,β) has a representation in the form Equation (8) withEQUATIONare complexity measures of H defined in (13), ( 10) and (12), respectively. The proof is presented in Appendix A.3.Here, m h denotes the hidden dimension of the attention mechanism, essentially the size of the query and key vectors, while m FF represents the complexity measure of the pointwise feed-forward network employed in the Transformer. We first consider how the attention mechanism ρ(x(t), x(s)) approximates the temporal coupling term ρ. By setting[W Q ] k = e k and [W K ] k = e k+m h +1 , we can write ρ into ρ(x(t), x(s)) = (W Q f (x(t))) ⊤ W K f (x(s)) = m h k=1 φk (x(t)) ψk (x(s)), where φk , ψk : I → R for k ∈ [m h ]are components of f and are represented by the feed-forward network. This suggests that the approximation of ρ by ρ is a low-rank approximation as discussed in Equation ( 9). When we increase m h , the first term in the error rate that considers the POD decomposition decreases since there are more basis functions included. However, in scenarios where m FF remains unchanged, the second term in the error bound will increase. It is important to highlight that this error increment pertains only to the error bound, not to the best approximation error, which does not necessarily become worse when increasing the approximation budget. When m h increases, there are more basis functions that need to be approximated by the feed-forward components; thus, the error bound converges when both m h → ∞ and m β FF /m β+1 h → ∞. In Appendix B.2, we provide a synthetic example to illustrate the above discussion.The complexity measure C 2 (•) accounts for the quality of approximation using feed-forward networks. On the other hand, C 1 (•) is the most interesting part, which concerns the internal structure of the attention mechanism. It tells us that if a target can be written in form (8) with ρ(u, v), then it can be efficiently approximated with small m h if ρ(u, v) has fast decaying singular values. This decay condition can be understood as effectively a low-rank condition on (u, v) → ρ(u, v), analogous to the familiar concept for low-rank approximations of matrices. These observations provide important insights into the structure, bias, and limitations of the Transformer. 
numerical demonstrations: 
 In this section, we present numerical examples to demonstrate our approximation rate results. We begin with synthetic examples, where we can specify the singular value decay patterns, thus validating the Jackson-type approximation rates in Theorem 4.2. Then, we turn to a practical example involving a Vision Transformer (ViT) model applied to the CIFAR10 dataset, where we do not have direct access to the singular values. We will discuss methods to estimate the singular value decaying pattern.We next analyze a practical example, focusing on the Vision Transformer (ViT) model with the CIFAR10 dataset. In this scenario, we do have direct access to the temporal coupling term ρ of the target relationship. However, we demonstrate that as we train a sequence of models with increasing attention dimension m h , the singular values of ρ converges, implying the decaying pattern of ρ. Our first step is to estimate the rank of ρ from sampled data. Subsequently, we examine the singular value decay pattern, and the error changes when altering the attention head size m h . Estimate the Rank of ρ Given a trained model, it is hard to directly compute the rank of ρ(u, v). Instead, we examine the attention matrix ρ(x) ∈ R τ ×τ where [ ρ(x)] t,s = ρ(x(t), x(s)). This is essentially a sample from ρ. By analyzing the rank of these sampled matrices, we can estimate the rank of ρ. According to Braun [5] , the singular values of the matrix ρ(x) exhibit the same decay pattern as those of ρ(u, v). Consequently, we can approximate the singular values of ρ(u, v) by averaging the singular values of ρ(x) across various inputs. In Figure 1 (a), we numerically estimate the singular values of ρ in the ViT-B 16 model [11] . We observe that the singular values tend to be more concentrated, suggesting that we can effectively estimate the rank of ρ(u, v) by evaluating it at sampled inputs.We next estimate the singular value decaying pattern of the temporal coupling term ρ in the target.In Figure 1 (b), we analyze the singular values of the ρ for ViT models with varying values of m h . We estimate the singular values by averaging over a set of inputs. We observe that as m h increases and reaches a sufficiently large value, the decaying pattern of the singular values starts to converge.As an example, Figure 1 (b) plots the estimated singular values for the first head of the last layer for models with different m h . This convergence suggests that the rank of the attention matrix becomes representative of the actual rank of ρ in the target. Consequently, it suggests the presence of a low-rank structure in real-world datasets. In Figure 1 (c), we plot the training error as an estimation of the approximation error. The plot reveals that the error decreases as m h increases, following a power law decaying pattern O 1/m 0.27 h . This indicates that the target indeed exhibits a low-rank structure, and the pattern of error decay aligns with our approximation rate presented in Theorem 4.2. This illustrates that while our theorem is formulated based on a simplified scenario, the phenomenon of low rank is also observable in real-world datasets and models. 
comparison with rnn: 
 Based on the approximation results in Theorem 4.2, this section presents a comparison between the Transformer and RNN. Our comparison centers on how each model is affected by the alterations in the temporal structures of sequential relationships. We primarily investigate two distinct temporal structures: temporal ordering and temporal mixing, as they have varying impacts on the performance of each architecture. Our approach involves manipulating the temporal structures within the sequential relationships and evaluating how each architecture is affected by these changes. Proof are presented in Appendix D.2 and Appendix D.3.We first analyze how the Transformer and RNN handle the change in temporal ordering of the sequential relationship. Empirically, it is observed that in certain contexts, the ordering of inputs does not significantly impact the relationships. For instance, in NLP applications, altering the word order in a sentence often does not drastically change its meaning. Similarly, in the ViT model, the arrangement of image patches typically does not substantially affect the outcome. However, in specific applications such as time series analysis, temporal ordering plays a crucial role, as the target relationships are governed by the ordering of the sequence. To alter the temporal order of target H, we apply a fixed permutation p and define the new target as Ht (x • p) = H t (x). This permutes the input but keeps the output unchanged, resulting in a change to the temporal ordering.We start by considering the RNN, which is affected by the change in temporal ordering. As demonstrated in Li et al. [22] , a linear RNN is represented by the form Ĥt (x) = s c ⊤ e W s U x(t -s). When we employ it to approximate linear targets represented by H t (x) = s ρ(s)x(t -s), the complexity measures of the RNN C RNN (H) is determined by both decay speed and magnitude of ρ(s). We use C RNN to denote the approximation space for the RNN. (See Appendix D.1). We next show that the RNN is affected by the change in temporal ordering. Proposition 6.1. Let H ∈ C RNN and p be a fixed permutation, such that there exists t ′ with p(t′ ) > t ′ . Suppose H is defined by Ht (x • p) = H t (x). Then H / ∈ C RNN .This proposition shows that the altered target H no longer belongs to the approximation space for RNN. This lies in the fact that RNN can only handle causal targets, where y(t) does not depend on future inputs. However, the permuted target x is no longer causal, making the RNN incapable of learning such relationships. We next show that the Transformer, in contrast, remains unaffected by changes in temporal ordering.Proposition 6.2. Let H ∈ C (α,β) and p be a fixed permutation. Suppose H is defined by Ht (x•p) = H t (x). Then H have same complexity measures with H for the complexity measures C 0 , C 1 , C 2 defined in Equation ( 13), (10) and (12) .This proposition shows that the altered target H maintains the same complexity measures as the original target. This observation implies that the Transformer's approximation capability is not affected by alterations in temporal ordering. This point is further substantiated by our testing of the Transformer on real-world datasets, as illustrated in Table 1 . We consider the ViT model on the CIFAR10 dataset and the base Transformer structure [30] on the WMT2014 English-German dataset.To alter the temporal ordering of the target relationship, we fix a permutation of indices denoted as p and apply it to all inputs while keeping the output unchanged. 1 : Numerical results of the Transformer on original and altered targets. The altered target is constructed by permuting the entire input dataset while keeping the output unchanged.In this section, we explore how mixing elements from different time indices can affect the performance of the Transformer and RNN. Temporal mixing refers to the idea of blending information from various time indices, often through operations like convolution, which can alter the temporal structure. To illustrate, consider a linear relationship represented as H t (x) = s ρ(s)x(t -s). Now, imagine we apply a weighted sum of the input sequence x using a filter θ to get an altered input. We denote this operation as x = θ * x, where (θ * x)[t] = l-1 s=0 θ(s)x(t + s). This mixes the information in the sequence from different time indices. In this case, we define the altered target as Ht (x) = H t (θ * x) = s ρ(s)x(t -s), where ρ = θ * ρ is the altered kernel (See Appendix D.3). This scenario often arises in signal processing and data analysis. For example, when dealing with a noisy input signal x, one capproach is to apply a moving average filter to smooth it out. This filtering process involves mixing information from different time indices, which can significantly affect the behavior of target relationships. In the following sections, we will explore how such temporal mixing affects the temporal structures in sequential relationships. We begin by examining the linear RNN. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Detailed experiment settings are presented in the appendices.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this paper, we have developed Jackson-type approximation rates for the Transformer in a simplified setting. An important outcome of our work is the identification of complexity measures and approximation space defined in Equation ( 14). This, in turn, enables us to derive explicit Jackson-type approximation rate results in Theorem 4.2. Our rate results suggest that the Transformer performs well when the temporal coupling of the target exhibits a low-rank pattern. The experiments presented in Section 5 showcase the existence of low-rank patterns in real-world applications. Furthermore, the comparisons with RNNs underscore the specific temporal structures that each model handles efficiently. Future research directions involve extending the analysis to multi-headed attention and deeper Transformers. Additionally, we aim to investigate the potential benefits of removing temporal mixing in the input to enhance the performance of the Transformer.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: Our numeric demonstrations does not require error bars.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative rates). Justification: The Code of Ethics is followed. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our results are theoretical, and there is no societal impact. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper have no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A.1 Permutation Equivariance of the Hypothesis Space H Let p : [τ ] → [τ ] be a permutation. Let's consider an Ĥ ∈ H with permuted inputs:EQUATIONSince the permutation of index s does not affect the sum, we haveEQUATION= Ĥp(t) (x).This shows that the Transformer hypothesis H is permutation equivariant.A.2 Density of the Target Space CIn this section, we show that the target space C defined in Equation ( 8) is dense in the general continuous target space C(X (E) , Y). This ensures that the space defined is general enough to approximate arbitrary continuous targets.To begin with, we first introduce the following representation theorem for multivariate functions.Theorem A.1 (Kolmogorov Representation Theorem). [26] Let I 1 , . . . , I τ be compact d dimensional metric spaces. Then there are continuous functions ψ qs : I s → [0, 1] and continuous function g q : [0, τ ] → R, such that any continuous function f : I i → R can be represented asf (x 1 , . . . , x τ ) = 2τ d q=0 g q τ s=1ψ qs (x s ) .This theorem states that any τ variable functions can be decomposed into superpositions of one variable function. Now, we discuss how the pointwise functions on a sequence can apply different mappings on different time indices.Proposition A.2. Suppose we have τ variables in disjoint domains, where x 1 ∈ I 1 , •, x τ ∈ I τ and I 1 , . . . , I τ are all disjoint. We consider the following vector-valued functionEQUATIONwhere f s :I s → R for s ∈ [τ ].We can indeed define a pointwise function g : I s → R to represent f . Since all I s are disjoint, we can define a piecewise function g, where g(x s ) = f s (x s ) holds for all s ∈ [τ ].This proposition demonstrates that for a sequence input x with appropriate positional encodings, where x(i) and x(j) belong to disjoint sets, a pointwise function can represent distinct mappings for these elements. We are now ready to present the following theorem.Theorem A.3. Consider d-dimensional, length τ input space X (E) with position encoding added. Then, for any H ∈ C(X (E) , Y), there exists continuous functionsF ∈ C([0, 1] n , R), f ∈ C(I, [0, 1] n ) and ρ ∈ C(I × I, R) such that for all t ∈ [τ ]we haveEQUATIONwhere n = 2τ d + 1 and σ is the softmax function.Proof. Based on the representation for continuous function Theorem A.1, we can decompose H intoEQUATIONwhere ψ(τ )q,s : I s → [0, 1] and g (t)q : [0, τ ] → R are continuous functions. We next construct F, f and ρ to make H satisfy this form. Firstly, since I s are disjoint we can define proper piecewise functionρ such that σ[ρ(x(t), •)](x(s)) = 2 τ +1 t = s 1 τ +1 t ̸ = s, which simplifies Equation ( 8) toEQUATIONNext, based on Proposition A.2, we let the pointwise function f : I → [0, 1] n to apply different mappings for each x(s), such thatEQUATIONwhere b s ∈ [0, 1] are different constants. We then have thatEQUATIONHere, b t performs as a shifting to make the range of Equation ( 24) disjoint for different t. Again, based on Proposition A.2, we can define F to have individual mappings for different t. We first defineEQUATIONwhere u i denotes the i-th dimension of u. Next, define F 2 : [0, τ ] n → R to beEQUATIONFinally, let F (u) = F 2 • F 1 ((τ + 1)u). Substitute into Equation (22) we get thatEQUATIONThis theorem shows that the target space C is, in fact, a representation of the general continuous target space C(X (E) , Y). In particular, since I is a compact metric space, the complexity measures of each component g(s)q and ψ q,s used in the construction of H have finite complexity measures C 0 , C 1 and C 2 . This implies that the approximation space C (α,β) is also dense.Now, we present the proof of the Jackson-type approximation rates. Lemma A.4. The following inequality will be used to prove the theorem.EQUATIONEQUATIONProof. Proof of Theorem 4.2 Since there are various components in the model, we will consider each of them separately. Firstly let's consider the approximation of F .LetEQUATIONandEQUATIONwe haveEQUATION≤ K F h -ĥ + F ( ĥ) -F ( ĥ) .Let's consider F ( ĥ) -F ( ĥ) first. Since I is a compact domain and ĥ is continuous, its range ĥ(I) is a compact set. For all x ∈ ĥ(I) we have F ( ĥ(x)) -F ( ĥ(x)) ≤ ∥F -F ∥ L ∞ ( ĥ(I)) . This implies thatEQUATIONEQUATIONwhere |I| denotes the volume of I. Recall that ĥt (x) = τ s σ(ρ(x(t), x(s)))ρ(x(s)), we may assume the parameters of f is bounded such that f (x(s)) ⊂ [0, 1]. By the property of Softmax we have ĥ(I) ⊂ [0, 1], thus,EQUATIONNext, let's consider the first term of (32),EQUATIONEQUATIONSince Softmax is Lipschitz continuous and bounded by 1, we have thatEQUATION)The second term is an approximation with neural networksEQUATION)Now we remain to derive a bound for |ρ -ρ|. Let ρ be a m h term truncation of POD expansion of ρ, thenEQUATION)The first term is the error estimates using POD, which says thatEQUATIONThe second term is again approximation with neural works, which we haveEQUATIONThus, combining all the inequalities above, we have thatEQUATIONEQUATIONBy substituting the complexity measure of H to R.H.S., we have thatEQUATIONThis completes the proof.In this section, we provide numerical examples that follow the target form Equation ( 8):H t (x) = F τ s=1 σ[ρ(x(t), x(•))](s)f (x(s)) .This form, in fact, is not a unique representation; in other words, for H 1 = H 2 we may not haveF 1 = F 2 , f 1 = f 2 and ρ 1 = ρ 2 .However, we have the following propositions that characterize the invariant properties of the target form. Proposition B.1. Suppose H 1 and H 2 are in the form of Equation (8), then the following properties hold.1. If H 1 (x) = H 2 (x) holds for all x, then F 1 • f 1 = F 2 • f 2 . 2. Suppose σ is hard-max function. For non constant H 1 , H 2 ∈ C, if H 1 (x) = H 2 (x) holds for all x, then arg max x(s) [ρ 1 (x(t), x(s))] = arg max x(s) [ρ 2 (x(t), x(s))] if the argmax is unique and F 1 • f 1 , F 2 • f 2 are injections.3. Suppose σ is softmax function. For non constant H 1 , H 2 , if H 1 (x) = H 2 (x) holds for all x and ρ 1 , ρ 2 are unbounded, then arg maxx(s) [ρ 1 (x(t), x(s))] = arg max x(s) [ρ 2 (x(t), x(s))]if the argmax is unique andF 1 • f 1 , F 2 • f 2 are injections.Proof. By considering a constant input sequence x = (x, . . . , x), we getF 1 • f 1 (x) = F 2 • f 2 (x) for all x. Suppose arg max[ρ 1 (x(t), x(s))] = c 1 and arg max[ρ 2 (x(t), x(s))] = c 2 , then H 1 (x) = H 2 (x) implies F 1 • ρ 1 (c 1 ) = F 2 • ρ 2 (c 2 ). By the injection assumption, we have c 1 = c 2 , which implies the argmax are equal.When the normalization is softmax, since ρ is unbounded, we consider a sequence of inputs {x (i) } such that the ρ(x (i) (t), x (i) (s)) goes to infinity, which became the same as the previous hard-max case.Although these properties need to satisfy certain conditions to be theoretically correct, we empirically found they generally hold true in real applications.Next, we demonstrate these concepts through numerical examples by utilizing the Transformer model to learn different targets. We consider the following simplified version of a single layer TransformerEQUATIONHere, x ∈ R d×τ is the input, F , f are two nonlinear mappings applied column-wise, and σ is the softmax function applied column-wise to the matrix.Nearest point to a set In this example, we consider two sets of points U ⊂ R d and V ⊂ R d as inputs. For each point u t ∈ U , we aim to determine the nearest point from set V . More specifically, we define an input sequence x ∈ X ⊂ R 2d×τ in the form x(t) = (u t , v t ) ∈ R 2d , where u t and v t are two d-dimensional points belonging to point set U and V , respectively. The output is defined asEQUATIONThis can be rewritten as In Figure 2 (a), we plot the attention matrix A of a particular instance of the input x. For Figure 2 (b), we visualize the point set U, V based on their coordinates and establish connections according to the values in A. Specifically, two points u i and v j are connected based on the value of A ij . This visualization reveals exactly that each green point in set U is linked to the nearest point in V , demonstrating the model's ability to recover the target relationship accurately. Furthermore, for the target form Equation (52), F • f in this case is an identity function. As shown in Figure 2 (c), F • f is also found to learn an identity function. This observation is in accordance with Proposition B.1, despite the theoretical assumptions that may not fully apply.EQUATIONWeighted average by weight In this scenario, we are given sequences of point masses as inputs. Our objective is to compute the center of gravity for each sequence. These point masses are in R d space, each with a mass m ∈ R.Consider a sequence containing τ points. extend this to a sequence of τ + 1 points by adding an extra point x pred / ∈ X at the beginning of the sequence, serving as a prediction token. Consequently, the input sequence is represented as:EQUATIONThe corresponding output sequence is formulated as:EQUATIONwhere x pred is mapped to x, and the other points remain unchanged. | • | denotes the Euclidean norm. The center of gravity x is defined by the equation:EQUATION)We may consider several sequence segments of point masses, denoted as x 1 to x n , which may vary in length. These sequences are concatenated to form an input sequence x. Correspondingly, the output y concatenates y 1 to y n .As an example, consider the following input-output pair:x = (x pred , x 1 m 1 , x 2 m 2 , x 3 m 3 , x pred , x 4 m 4 , x 5 m 5).(57)EQUATION)In this example, the output sequence y includes the norm of the computed centers of gravity for each concatenated segment of the input sequence x, where each segment is separated by the prediction token x pred . This can be formulated as target form Equation ( 8) such thatEQUATION)where I x denotes the index of the sequence segment corresponding to x pred . The weighted output here depends on the prediction token, such that it only takes the weighted average within the corresponding sequence. For numerical illustration, we consider input x of length 10, containing sequence segments of length at least 2. We apply the single-layer Transformer model to learn this target.In Figure 3 , we analyze an input x comprising two sequence segment, x 1 and x 2 , with lengths of 3 and 5, respectively. In this scenario, x(0) and x( 5) are prediction tokens. The attention matrix behaves as expected: the outputs y(0) and y( 5) are influenced predominantly by the points within their respective sequences, and the values are approximately the normalized weight. Furthermore, since the remaining outputs are the same as the inputs, the attention matrix values for these elements are confined to the diagonal, which means that the output at that point is only determined by itself.Furthermore, in Figure 3 (c) we observe that F • f can successfully recover F • f in the target which is a norm of the R 2 vector. Weighted average by selection The previous calculated the weighted average by specifying the weight of each point. Now, we consider another way to calculate weighted average where we specify a subset of points we are going to take the average. Suppose we have a length τ sequence of R d vectors v ∈ R d×τ . We also have a sequence of vectors s ∈ [τ ] k×τ consisting of sequences of indices. We stack v and s to form the input sequence x ∈ R (d+k)×τ . This extends the qSA task proposed in Sanford et al. [27] .The output y(t) is defined asEQUATIONThis can be written in the target form Equation ( 8) such that F • f is identity. Depending on the frequency of s appears in the index vector s(t), we have thatEQUATIONAs an example, we have the following input-output pairs.EQUATION.EQUATIONIn our numerical experiments, we set τ = 8, d = 2, and k = 3. This configuration implies that both the input and output sequences have a length of 8, and the output y(t) is computed as the average of three inputs, as indices designated by s(t). For this particular setting we have ρ ∈ {0, 1 2 , 2 3 , 1}. Again, we use a single-layer transformer model to learn this target.In Figure 4 we examine a particular input, where (63)In Figure 4 (a), we observe that the attention matrix accurately reconstructs ρ, as demonstrated in Equation (61). In summary, these examples demonstrate tasks that follow the form presented in Equation ( 8). Moreover, the numerical experiments validates Proposition B.1, where F • f is always the same, and the attention matrix recovers the desired weights.(a) + constant, provided m FF is sufficiently large. We numerically verify the prediction by constructing a set of targets using Equation (8). In this specific example, we set both F and f as the identity function. The temporal coupling term ρ(u, v) is formulated using an orthonormal bases where ϕ i , ψ i ∈ { √ 2 sin 2iπx : i ≥ 1}, accompanied by singular values with various decaying patterns. Subsequently, we trained the Transformer as defined in Equation ( 5) to learn these targets. Figure 5 plots the training error against m h , where (a) and (b) correspond to targets with different singular value decay patterns. We also consider different rank r of the targets as plotted using lines with different colors. The error decay rates of (a) and (b) are different, which follows the decay rate determined by that of the singular values. Furthermore, for a fixed m h , the error increases with the target's rank. The experiment results are consistent with our estimates in Theorem 4.2.σ k = k -0.55 k ≤ r 0 k > r (b) σ k = k -1 k ≤ r 0 k > rIn this section, we summarize the settings for the numerical experiments.Experiments in Appendix B.2 These experiments consider the synthetic targets with simplified Transformer models as defined in Equation ( 5). The target relationship is constructed using Equation ( 8):EQUATIONWe consider scalar inputs where d = 1 and F (x) = f (x) = x are identity functions. ρ(u, v) is constructed using the POD decomposition:EQUATIONWe consider orthonormal bases ϕ i , ψ i ∈ { √ 2 sin 2iπx : i ≥ 1}. By doing this, we can specify σ i , which are then exactly the singular values. The input sequence of length 16 is generated using a uniform distribution on [0, 1]. We use Transformers as defined in Equation ( 5) to learn these targets. The feed-forward part is constructed using a dense network with a width of 128 and a depth of 3 to ensure it has enough expressiveness. Moreover, we have n = d v = 32 and m h , which range from 1 to 16, to construct a model with different ranks. We use PyTorch default initialization and use normal training procedures with Adam Optimizer. We train enough epochs to ensure the loss does not decrease so that we can use the training error to estimate the approximation error.Experiments in Section 5.1 In this example, we tested the ViT model on the CIFAR10 dataset. We consider the baseline model ViT B16 [11] . This model configuration utilizes 12 heads, and each head is of dimension 64. In Figure 1 (a), we plot the singular values distribution of the attention matrix (before Softmax normalization) from the first attention head. We then vary the size of each attention head from 1 to 64 while keeping other configurations unchanged. We follow the training procedure as described in [11] to train the modified models.Comparison of the Transformer and RNNs We consider the following linear target relationship:EQUATIONwith kernel ρ(s) = exp (-s). The input sequence of length 32 is generated using a uniform distribution on [0, 1]. For the RNN, we utilize a one-layer vanilla RNN architecture with 128 hidden units, employing a linear activation function. For the Transformer, we use the simplified structure as presented in Equation ( 8) with position encoding added. For parameter settings, we haven = d v = m h = 32.The feed-forward part is constructed using a dense network with a width 128 and a depth 3.To change the temporal ordering, we permute the input while keeping the output unchanged, this leads to a change in the temporal ordering of the target relationship. For all the input sequences, we exchange the first 10 values with the last 10 values, resulting in a change in the underlying temporal structure. For the temporal mixing operation, we use a randomly generated length 5 filter and the operation * described in Section 6.2.In Table 2 , it is also interesting to note that for this target, the RNN performs better than the Transformer. This is potentially because temporal ordering is inherently important in this target, and the Transformer is not good at capturing such relationships. Some variants of the Transformer, such as Informer [36] and Autoformer [32] , have been proposed specifically to address temporal relationships, particularly in sequence forecasting tasks. However, empirical results presented in Zeng et al. [35] indicate that these variants still cannot effectively capture temporal relationships.As a comparison, we consider a different type of linear relationship where the temporal ordering is unimportant. We randomly generate the filter such that ρ(s) ∼ U [0,1] . This does not have temporal ordering since if we permute ρ, the distribution of it does not change. The results are shown in Table 3 . We can observe that it is hard for RNN to learn this target. But the Transformer can learn this target, and a permutation of the input does not affect its performance.Trans.Original 5.58 5.43e-4 Permuted 5.24 5.36e-4 Table 3 : The table presents the MSE values for both RNN and the Transformer datasets without temporal ordering.Real-world datasets for the Transformer In Table 1 , we test the performance of the Transformer on a permuted dataset considering real-world examples. For the ViT experiment, we use the ViT B16 model. For the WMT2014 English-German dataset, we use the original Transformer model as proposed in [30] . For both experiments, when testing on the permuted dataset, we initialize the model with parameters that are trained on the original dataset. To generate the permuted dataset, we fix a permutation such that the first 10 elements are shifted to the end of the sequence. This operation is applied to all the input sequences. Note that the permutation of the ViT dataset is before the addition of position encoding and after the convolution embedding.In this section, we provide additional discussions related to Section 6. We first review the approximation results for the RNN, the we provide proofs for the propositions presented in Section 6.We here review the results of approximation results of RNN presented in Li et al. [23] . Here, we consider input and output space defined byEQUATIONandEQUATIONThere are infinite sequences with time indices starting from zero.We consider the following dynamics for the linear RNN:EQUATIONEQUATIONwhere h ∈ R n with h(0) = 0 is the hidden state of the RNN. W ∈ R n×n , U ∈ R d×n and c ⊤ ∈ R n×1 are parameters. The approximation budget of the model is n, which is the size of its hidden state. We can explicitly solve this dynamic where we getEQUATIONHere, we assume the eigenvalue of W has a negative real part to ensure it is stable when s increases.For the target, we consider a linear relationship represented byEQUATIONwhere ∥ρ(s)∥ ≤ ∞ is a unique representation of H. Thus, the approximation capability of the RNN is characterized by the properties of ρ.Note that ρ(s) = c ⊤ W s U in the RNN exhibits an exponential decaying pattern. Thus, the target must also have a similar decay pattern to achieve a good approximation. We have precisely defined the following complexity measures for the RNN.EQUATIONThis measures the decaying speed of the RNN, we assume ρ exhibits an exponential decay, with decaying speed measured by C 1 . The next complexity considers the norm of ρ:EQUATIONCombined together, we define the complexity measure for RNN asEQUATIONThis considers the magnitude of ρ, C 2 is small if ρ does not have a large value far from the origin. We define the RNN approximation space to be targets that have finite complexity measuresEQUATION)The approximation rate of the RNN followsd • C RNN m .D.2 Discussion of Section 6.1Proof of Proposition 6.1 We now present the proof for Proposition 6.1Proof. Let p : N ≥0 → N ≥0 be a permutation on the time indices. We consider an altered targetEQUATIONWe then haveEQUATIONLet's consider the most simple case where p only permute two time indices such that p(t 1 ) = t 2 and t 2 > t 1 . We consider the output at t 1EQUATIONHowever, for Ht1 (x) we haveEQUATIONNote the in this case the output at t 1 depends on a future value of input x(t 2 ), this means that H is no longer causal. Consequently, H cannot be written in the form of Equation (72), thus not belong to the RNN approximation space.Proof of Proposition 6.2 We next consider the Proposition 6.2Proof. For a fixed permutation p : τ → τ , we consider Ht (x • p) = H t (x). Suppose the altered target has the following form:EQUATIONwe next show that F , f and ρ has same complexity measures as F, f and ρ. Firstly, we note that we can remove the permutation on index s because the ordering of a summation does not affect the result.EQUATION)We now consider the POD expansion of ρ whereEQUATIONRecall that our input space is defined as Equation ( 7). Where x s ∈ I s such that I i and I j are closed disjoint sets. Thus, for a pointwise function ϕ, we can write it into the following piecewise formEQUATIONLet φi (x) = ϕ i (p(t)) (x) for x ∈ I t . This is essentially the permutation of the disjoint pieces of φi . Thus we haveEQUATIONConsequently, we have ρ(x(p(t)), x(s)) = ρ(x(t), x(s)). Finally let F = F and f = f we achieved Ht (x • p) = H t (x). Since F and f remain unchanged, we only need to consider the complexity measure for ρ. We note that the rank of the POD is unaffected. We remain with C FF ( φi ). The function φi is a permutation of pieces of the piecewise function ϕ i . We next discuss the kind of approximation schemes that C FF ( φi ) is unchanged under this operation.Since the set I is disconnect, we apply Tietze extension theorem to extend ϕ i to its convex hull, denoted as Φ i , such that Φ i (x) = ϕ i (x) for x ∈ I and sup{|Φ i (x)|} = sup{|ϕ i (x)|}.We first consider the polynomial approximation as we introduced in Section 3. In this case, we have C FF (ϕ i ) = max r=1...α ∥ϕ i ∥ ∞ . We next show that C FF ( φi ) = C FF (ϕ i ). Since I is closed and φ is continuous, we apply Tietze extension theorem to extend φi to R d denoted as Φi , such that Φi (x) = φi (x) for x ∈ I and sup{| Φi (x)|} = sup{| φi (x)|}. This implies that C FF ( φi ) = C FF (ϕ i ). Thus, in the case of polynomial approximation, the complexity measures remain unchanged.Next, we consider the approximation using the ReLu network. We assume ϕ i to be Hölder continuous such thatEQUATION)The Tietze extension theorem states we can extend it to Φ i with the same C and α.As shown in Shen et al. [28] , the approximation capability of a ReLU network on a Hölder function depends on C and α. Where functions with small C, α can be approximated more effectively. Since φi is a permutation of disconnected pieces of ϕ i , its Hölder constant remains unchanged. Thus, its Φi has same Hölder constant as Φ i , which implies the complexity measure is the same.In the above proof, we considered two different approximation schemes where the complexity measures of H remain unchanged.D.3 Discussion for Section 6.2Proof of Proposition 6.3 We first discuss Proposition 6.3. Consider a filter θ which is a length l filter with ∥θ∥ 1 ≤ 1. The altered target is defined byEQUATIONRearrange the summation, and we getEQUATIONEQUATIONThus, we have the altered kernel denoted as ρ = θ * ρ. By assumption we have ρ exhibits exponential decay such that |ρ(s)| ≤ e -βs for some β. We then haveEQUATIONwhich shows that ρ[t] is also bounded by e -βs . This implies that C 1 ( H) ≤ β and C 2 ( H) ≤ 1.Transformer Affected by Temporal Mixing Finally, we present an example where a temporal mixing in the input will affect the target's rank. For simplicity we consider the case where d = 1 and τ = 2, and x 1 , x 2 ∈ [0, 1]. Note that here, we do not assume x 1 and x 2 belong to disjoint intervals for simplicity. For target in the form of Equation ( 8), we consider a temporal coupling term ρ defined asρ(x 1 , x 2 ) = 1 + √ 2 sin(2πx 1 ) • √ 2 sin(2πx 2 ).(97) In this case, ρ(u, v) is of rank 2 with both singular values equal to 1. Consider a new input x = (x 1 , x 2 + x 1 ) with temporal mixing. We then haveρ(x 1 , x 2 + x 1 ) = 1 + √ 2 sin(2πx 1 ) • √ 2 sin(2π(x 1 , x)).(98) We numerically estimate the singular values of ρ to get σ 1 = 1.265, σ 2 = 0.5 and σ 3 = 0.4. The rank of ρ increases, and there are also extra bases included. Here, we only consider the rank ρ from the same representation, while we do not exclude the possibility that there exist other representations that may have another rank pattern. Indeed, analyzing the temporal mixing in the Transformer is nontrivial; we only provided an example where the rank increases. Conversely, a suitable deconvolution process can also decrease the complexity measure of the target. We leave it as a future direction for analysis. 


Decision: The paper received favorable reviews. Reviewers acknowledge the novelty of the Jackson-type approximation rate for the Transformer and agree on the merits of this paper being presented at NeurIPS.

Reviews: review: paper_summary: paper_summary: The study explores the theoretical aspects of Transformer architectures in sequence modeling, particularly focusing on approximation rates for sequence-to-sequence relationships. A representation theorem is established, introducing novel complexity measures that analyze interactions among input tokens, culminating in a Jackson-type approximation rate estimate for Transformers.
strength_weakness: strength_weakness: The paper deviates from the standard Transformer architecture by requiring a neural network layer before the attention mechanism to implement the Kolmogorov Representation Theorem, potentially inheriting the theorem's limitations.
questions: questions: Q1. In the context of POD, it is my understanding that having rho with fast decaying singular values allows for the complexity measure of H to be constant. However, this paper employs a specific construction to derive equation (22) for sigma(rho) as mentioned in line 492.
Could we still say that rho has fast decaying singular values in this case? Please provide a specific explanation.

Q2. It's unclear how to construct the F1 function that realizes equation (25). Could you explain in detail?

Q3. I cannot  understand the flow from equation (22) to (25). 
Eequation (24) (f(x_t)+sum_s f(x_s)) is constructed using equation (22), which is realized by using a specific attention, and then f(x_t) is removed in equation (25). 
Why not just construct an attention, average pooling, that constitutes sum_s f(x_s) in Eq. (22)?

Q4. Theorem A.3 states that n=tau * (2 * tau * d+1)+1.
However, looking at equation (23), it appears that the output of f is only (2 * tau * d+1)-dimensional.
Where does n=tau * (2 * tau * d+1)+1 need to be?

Q.5 Considering the theoretical framework presented here which inherits limitations from the Kolmogorov representation theorem, could you specify what limitations might arise in the class of functions approximated by the model?
It is worth noting that identifying these limitations does not detract from the contributions of this paper.
limitations: limitations: The paper deviates from the standard Transformer architecture by requiring a neural network layer before the attention mechanism to implement the Kolmogorov Representation Theorem, potentially inheriting the theorem's limitations.
paper_summary: paper_summary: This paper introduces a novel concept of complexity measures to construct approximation spaces for single-layer Transformers with one attention head, providing Jackson-type approximation rate results for target spaces that possess a representation theorem.
strength_weakness: strength_weakness: The results presented are limited to 2-layer single-head Transformers, which restricts their applicability and insights into more common models such as multi-layer multi-head Transformers.
questions: questions: - How can the results be generalized to analyze multi-layer multi-head Transformers? Will such generalization provide new insights or understanding?

- Although the discussion on the parameters' dependence on rank is provided, the factor $\tau^2$ in the RHS of the inequality in Theorem 4.2 appears suboptimal for approximating long sequences.

- It seems that much of the relevant literature on the approximation power of Transformers has been omitted. For example, [1][2][3].

[1] Giannou et al (2023). Looped Transformers as Programmable Computers.

[2] Bai et al (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection.

[3] Wang \& E (2024). Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling.
limitations: limitations: See Weaknesses.
paper_summary: paper_summary: This study investigates a Jackson-type approximation rate for single-layer Transformers with one head, and compares their ability with RNNs, another nonlinear sequence-to-sequence map.
strength_weakness: strength_weakness: The main theorem (Theorem 4.2) sounds trivial because the bound is a combination of the definitions of complexities $C^\alpha$ (Sobolev smoothness) and $C^\beta$ (Barron bound). The universality of Eq.8 (Theorem A.3) may sound non-trivial, but it is obtained by rewriting the Kolmogorov representation of continuous function (from Theorem A.1), which is much a stronger (but only existential) result.

It could be non-trivial if the authors could provide a similar bound in a constructive manner without using the magic argument of Kolmogorov.
questions: questions: - Can the author provide a similar bound in a constructive manner without using the Kolmogorov theorem?
- Given a dataset, how to estimate $\alpha$ and $\beta$?
limitations: limitations: n/a

Comments: comment: Thank you for the response. 
I will raise my score.
Thanks for your response. We would like to clarify again that the purpose of Theorem 4.1 is to ensure that the target space considered in form (8) is large enough to represent any continuous sequence-to-sequence functions. We want to confirm that this target space is not restrictive. Then, in Theorem 4.2, we consider target functions of the form in (8) with regularities to develop the approximation rates. The Kolmogorov method is a proof technique for Theorem 4.1, there may also be other methods to prove the theorem, but this should not affect the results and logic flow of the paper.
Thank you for your clarifications. I will maintain my score.
Thank you for your clarifications. I will keep my score as is.

> The approximation bound in Theorem 4.2 is independent of the Kolmogorov theorem.

If so, it's misleading that Theorem 4.1 is put inside the Section 4.2, and it's even better if the paper is written completely without Kolmogorov.