Pith. sign in

REVIEW 2 major objections 7 minor 1 cited by

Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective

T0 review · 2 major / 7 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single self-attention layer can approximate any Hölder map to accuracy ε at polynomial cost

desk verdict The construction is genuinely novel and likely repairable, but the paper proves less than its title promises: the result holds for a generalized Transformer with token-dependent biases, not the standard token-wise feedforward architecture. read the letter →

arxiv 2504.13558 v1 pith:JRTLC55N submitted 2025-04-18 cs.LG cs.AI

Yuling Jiao , Yanming Lai , Yang Wang , Bokai Yan This is my paper · ORCID
classification cs.LGcs.AI MSC 41A2541A3068T07
keywords TransformerapproximationcurseofdimensionalityKolmogorov-ArnoldrepresentationtheoremHöldercontinuousfunctionsself-attentionfeedforwardnetworksmemorizationrates
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that Transformers can approximate the full class of Hölder-continuous maps from $[0,1]^{d\times n}$ to $\mathbb{R}^{d\times n}$ without paying the exponential-in-dimension cost known as the curse of dimensionality. It constructs explicit networks made of one softmax self-attention layer and small feedforward blocks that achieve uniform error $\epsilon$ for any $\epsilon>0$; with ReLU and floor activations the feedforward depth is $O(\log 1/\epsilon)$ and width $O(\epsilon^{-2/\beta}\log 1/\epsilon)$, and with additional exotic activations the width becomes constant. Earlier universal-approximation results for Transformers all had approximation costs that grew exponentially with the token dimension, so this is a different and stronger statement about the architecture's expressive capacity. The proof routes the problem through the Kolmogorov-Arnold Representation Theorem and a feedforward memorization step, bypassing the contextual-mapping technique of previous work.

What carries the argument

Two pieces carry the argument. First, Proposition 2, a space-filling-curve form of the Kolmogorov-Arnold Representation Theorem, writes every Hölder component $f_{rs}$ as $g_{rs}(3\sum_{p,q} a_{pq}\varphi(x_{pq}))$ with univariate outer functions $g_{rs}$ on the Cantor set and a digit-extracting inner function $\varphi$; this transfers smoothness to the outer function and reduces high-dimensional approximation to one-dimensional operations. Second, the translation technique lets a single shared-weight feedforward block implement different column functions by adding different integer offsets to each token column, so that the inner $\varphi_K$ computation can be done once for all columns; the self-attention layer then performs the summation over token columns. The memorization lemmas for feedforward networks, covering binary memorization with ReLU-floor, sine/cosine variants, and constant-size memorization with superexpressive activations, finish the construction by fitting the finitely many values of the outer functions.

What would settle it

Take $d=1,n=2$ and enforce the standard constraint $B^l = b^l \mathbf{1}_{1\times 2}$ in every feedforward block of the constructed Transformer. If, for the simple target $f(x)=(x_1,x_2)$ and some small $\epsilon$, no weights of the depth and width stated in Theorem 1 produce the required inner matrix $Z$ for all $X\in[0,1]^{1\times 2}$, then the uniform-approximation claim fails for standard Transformers.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1, is that for any $f \in \mathcal{H}_Q^\beta([0,1]^{d\times n},\mathbb{R}^{d\times n})$ and any $\epsilon>0$, there is a Transformer $T = \widetilde{F}_{FF}^{(mmr)} \circ F_{SA} \circ F_{FF}^{(sr)}$ with one one-headed softmax self-attention layer such that $d_\infty(T,f)\le \epsilon$. The first feedforward block approximates the inner functions of a Kolmogorov-Arnold representation, the attention layer sums across token columns, and the final feedforward block memorizes the values of the outer functions on a finite set of integers. Depending on the activation inventory, the final block has depth $7dn-2$ and width $O(\epsilon^{-2/\beta}\log 1/\epsilon)$ with ReLU and floor, or depth $6$ and width $O(\log 1/\epsilon)$ with an added $2^x$ activation, or depth $3$ and constant width when a nonpolynomial analytic or reciprocal activation is allowed. Theorem 2 extends the statement to $L^p$ distance for all $p\in[1,\infty)$, using ReLU for the inner block and sine/cosine or periodic-plus-nonpolynomial activations for memorization.

Load-bearing premise

The construction depends on feedforward blocks accepting bias matrices whose columns may differ between tokens; a standard Transformer applies the same bias vector to every token, and the paper does not show how to simulate that difference at the same cost.

Editorial extensions

If this is right

  • If Theorem 1 is correct, Hölder-continuous sequence-to-sequence maps are approximable by Transformers whose width grows only polynomially in $1/\epsilon$ for fixed $d,n$, so the exponential dimensional barrier in earlier approximation bounds is not intrinsic to the architecture.
  • The $L^p$ version in Theorem 2 shows the same escape from the curse of dimensionality holds under the weaker metric used in statistical learning, at least for inputs outside a small measure-zero failure set in the ReLU construction.
  • The ReLU-floor and exotic-activation cases imply that the activation inventory matters for the bound: adding one nonstandard activation can reduce width from polynomial in $1/\epsilon$ to constant.
  • The construction template turns feedforward approximation and memorization results into Transformer results, so any future improvement in feedforward memorization size should transfer directly to this class of Transformers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof uses feedforward blocks whose bias matrices may have different columns for different tokens, while a standard Transformer feedforward layer applies one bias vector to every token; the paper does not show how to simulate the per-column bias at the same size, so the headline claim should be read for the generalized architecture unless such a simulation is supplied.
  • If the per-column-bias assumption turns out to be simulable with only a modest width increase, the proof strategy would extend to the vanilla Transformer; if not, the result identifies a representational advantage of an architectural variant, not of the standard model.
  • The construction suggests a testable empirical direction: a Transformer with token-dependent bias terms should represent high-dimensional Hölder functions with far fewer parameters than a standard Transformer of the same depth, and measuring that gap would separate representational benefit from optimization behavior.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. The paper studies the approximation of Hölder-continuous functions mapping [0,1]^{d×n} to R^{d×n} by a Transformer architecture consisting of one softmax self-attention layer and feedforward blocks. Using the Kolmogorov–Arnold representation theorem, the authors construct feedforward blocks that compute an approximate inner feature (a finite-bit approximation of the KST coordinate sum), a self-attention layer that sums across tokens, and a second feedforward block that memorizes the outer KST functions on a finite grid. They claim that for any ε>0 the resulting network approximates any f in the Hölder class to accuracy ε in L∞ (Theorem 1) or Lp (Theorem 2), with widths and depths that are polynomial in 1/ε rather than exponential in the input dimension, thereby 'overcoming the curse of dimensionality.' The proof relies on a 'translation technique' in which the feedforward blocks are allowed to use bias matrices whose columns differ across tokens, on known FNN memorization results, and on superexpressive activations for constant-size memorization.

Significance. If the central claim were established for the standard Transformer architecture, it would be a notable advance: previous Transformer universal-approximation results scale exponentially in the sequence length or dimension, and this paper would give the first construction with polynomial-in-1/ε complexity for a smoothness class. The paper's organization around KST is conceptually clean and avoids the contextual-mapping machinery of earlier work; the explicit reduction of Transformer approximation to FNN approximation and memorization is a useful methodological idea. The paper also ships concrete rates for several activation-function combinations, including fixed-width memorization networks using superexpressive activations. However, the advertised claim is currently tied to a nonstandard definition of the feedforward block, and the correctness of the stated error bounds is undermined by a false tail estimate. Both issues are repairable, but the architectural gap in particular affects the scope of the results as presented.

major comments (2)
  1. [Section 2.1; Section 3.2; Appendix A] The construction uses feedforward blocks with bias matrices B^l whose columns may differ across tokens, which is explicitly introduced as a generalization of the standard definition. A standard Transformer feedforward layer applies the same affine map, including the same bias vector, to every token, and the paper does not include positional encoding. Under these standard restrictions every feedforward block and every softmax self-attention layer is permutation-equivariant in the token index, so the whole network satisfies T(XP)=T(X)P for every permutation P of the n columns. The target class H^β_Q([0,1]^{d×n}, R^{d×n}) is not restricted to permutation-equivariant functions: for example, f(X)_{1,1}=x_{1,1} and f_{rs}(X)=0 otherwise is 1-Hölder but not equivariant under swaps of the first two tokens. For X=[[1,0],[0,0]] and XP=[[0,1],[0,0]], any permutation-equivariant T must have d∞(T,f)≥1/2, so no standard Transformer without positional encoding can approximate all functions in the class. Theorems 1 and 2 therefore hold only for the paper's more expressive variant with column-dependent biases; the manuscript does not show that this variant can be simulated by a standard Transformer of the same size, nor does it restrict the target class to permutation-equivariant functions. This is the load-bearing gap between the title/abstract and the actual construction.
  2. [Appendix B and Appendix C; Lemmas 2 and 3] The displayed tail estimate |φ_K(x)-φ(x)| = 2 Σ_{j=K+1}^∞ a_j^x 3^{-dn(j-1)-1} ≤ 2/(3^{2dn+1}-3^{dn+1}) · 3^{-dnK} is not correct. The worst-case tail (e.g., all a_j^x=1) equals (2/3)·3^{-dnK}/(1-3^{-dn}), which is Θ(3^{-dnK}), whereas the paper's bound is Θ(3^{-dn(K+2)}), a factor Θ(3^{2dn}) smaller in the linear tail. After applying Hölder continuity with exponent γ ∝ β/(dn), this discrepancy becomes a constant factor of order 2^{2β} in the second error term of Lemmas 2 and 3 and in the Lp estimate in Section 3.3.2. The qualitative conclusions survive because the extra constant can be absorbed by increasing K by an O(1) amount, but as written the lemmas overstate the accuracy of the construction. The authors should correct the tail bound and restate the parameter choices in Theorems 1 and 2 accordingly.
minor comments (7)
  1. [Section 2.2, Proposition 2] The Hölder space H^{β log 2/(d log 3)}_{2βQ}(C) is typeset in a garbled way in the statement of Proposition 2; please make the exponent and the constant explicit.
  2. [Section 2.2, Definition 1] Definition 1 restricts to β ≤ 1, but the main theorems use H^β_Q for general β ∈ (0,1]; the paper should state this parameter range consistently.
  3. [Abstract and Theorem 1] The abstract says the ReLU-floor construction needs only O(log(1/ε)) feedforward layers, but the depth of ~F^{(mmr)}_{FF} in Theorem 1(1) is 7dn−2, which depends on the sequence length n; the O(log(1/ε)) statement is only with respect to ε for fixed d,n. This should be qualified in the abstract.
  4. [Section 3.2] In the six-step diagram, the transition from the second matrix to the third matrix repeats the same row twice; the accompanying text attributes this to a feedforward block, but with shared weights this row duplication requires the two rows to be constructed separately. Please clarify how the row dimension is expanded.
  5. [Appendix D, Lemma 4] In the proof of Lemma 4, the measure condition '2^{-kβp}' should read '2^{-Kβp}'.
  6. [Appendix E, Lemma 6] The proof of Lemma 6(2) contains a rendering artifact '/BD x≥0' in the definition of σ3; please fix the notation.
  7. [Table 2] Table 2 has several blank or misaligned entries in the width/depth columns for the compared works; a cleaner table would help readers verify the comparison.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the proof reduces Transformer approximation to external KST and FNN memorization results, with no fitted input renamed as a prediction.

full rationale

The derivation chain is not circular. The central representation step is Proposition 2, Schmidt-Hieber's KST variant, which is quoted as an external theorem and is used only to decompose the target Holder function into inner functions on the Cantor set and an outer function on the Cantor set. The paper's own contribution is then to realize this decomposition in a Transformer: the translation trick in Section 3.2 converts per-column tasks into one shared column function, the self-attention layer performs the required summation, and the outer function is approximated by FNN memorization lemmas. The memorization lemmas are cited from published sources with explicit constructions, including independent references [49], [50], [66], and [72], alongside one self-cited ReLU-sine variant from [25]; the self-cited variant is not load-bearing because the same memorization task is also achieved by the independent lemmas, and it does not assume the Transformer approximation conclusion. The parameters K and H are chosen only to control approximation-error terms and are not fitted to any data, so there is no fitted-input-called-prediction pattern. The main caveat is architectural rather than circular: Section 2.1 explicitly generalizes standard feedforward bias matrices to allow different columns per token, and without that generalization a standard transformer without positional encoding is permutation-equivariant and could not approximate all non-equivariant Holder maps in the stated class. That is a correctness or scope concern about matching the advertised architecture, not a circularity of the proof. Because no displayed equation or cited result reduces the theorem to itself or to the theorem's conclusion, the appropriate finding is no circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No data fitting or invented physical entities appear. The construction parameters H, K, and L are set explicitly from ε and the function class; the main nonstandard input is the architectural license for column-dependent biases and exotic activations.

assumptions (3)
  • standard math Kolmogorov-Arnold Representation Theorem in the Schmidt-Hieber form (Proposition 2): there exists a fixed monotone φ such that every Hölder f can be written as g(3 Σ 3^{-p} φ(x_p)) for some g on the Cantor set with Hölder smoothness.
    Invoked in Section 3.2 and used to reduce multivariate approximation to univariate memorization; proved in [47].
  • ad hoc to paper The constructed feedforward blocks are allowed to use column-dependent bias matrices B^l, so different tokens can receive different biases within the same weight-shared layer.
    Stated in Section 2.1; this is a nonstandard architectural assumption that makes the translation technique work. Standard Transformers use a shared bias vector for all tokens.
  • standard math Memorization lemmas for ReLU-floor and exotic-activation networks (Lemmas 6-10 from prior work): a small network can memorize arbitrary finite integer-to-label maps.
    Used in Lemmas 2 and 3 to memorize the outer functions g_rs on a finite grid; cited from [49,50,25,66,72].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective." pith.science (2026). https://pith.science/paper/JRTLC55N

@misc{pith2026250413558,
  author       = {Pith},
  title        = {Pith review of: Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JRTLC55N}},
  note         = {Machine review of arXiv:2504.13558}
}
abstract

The Transformer model is widely used in various application areas of machine learning, such as natural language processing. This paper investigates the approximation of the H\"older continuous function class $\mathcal{H}_{Q}^{\beta}\left([0,1]^{d\times n},\mathbb{R}^{d\times n}\right)$ by Transformers and constructs several Transformers that can overcome the curse of dimensionality. These Transformers consist of one self-attention layer with one head and the softmax function as the activation function, along with several feedforward layers. For example, to achieve an approximation accuracy of $\epsilon$, if the activation functions of the feedforward layers in the Transformer are ReLU and floor, only $\mathcal{O}\left(\log\frac{1}{\epsilon}\right)$ layers of feedforward layers are needed, with widths of these layers not exceeding $\mathcal{O}\left(\frac{1}{\epsilon^{2/\beta}}\log\frac{1}{\epsilon}\right)$. If other activation functions are allowed in the feedforward layers, the width of the feedforward layers can be further reduced to a constant. These results demonstrate that Transformers have a strong expressive capability. The construction in this paper is based on the Kolmogorov-Arnold Representation Theorem and does not require the concept of contextual mapping, hence our proof is more intuitively clear compared to previous Transformer approximation works. Additionally, the translation technique proposed in this paper helps to apply the previous approximation results of feedforward neural networks to Transformer research.

Figures

Figures reproduced from arXiv: 2504.13558 by the authors.

Figure 1
Figure 1. The flowchart for computing φK(x) when K = 4. Let f0 = x; fj =   σF (2K−jTj ) σF (Tj ) σF (Sj−1)   , j ∈ {1, 2, . . . , K}. By (3)(4) we conclude that f0 = x; fj = σF (Ajfj−1), j ∈ {1, 2, . . . , K}, (5) where A1 =   2 K 2 0   ; Aj =   1 −2 K−j+1 0 1 2K−j −2 0 0 2 · 3 dn(K−j+1) 1   , j ∈ {2, 3, . . . , K}. Define f (inner) F F = AK+1fK (6) with AK+1 = 1 3 dn(K−1)+1 [PITH_FULL_IMAGE:figures/full_fig_p027… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with $C^{s,\lambda}$ Targets

    stat.ML 2026-02 conditional novelty 5.0 of 10

    Standard Transformers attain the minimax optimal rate m^{-2γ/(2γ+dn)} (up to logs) for nonparametric regression of Hölder C^{s,λ} targets on [0,1]^{d×n}.

Reference graph

Works this paper leans on

73 extracted references · 61 canonical work pages · cited by 1 Pith paper

  1. [1]

    Vatt: Transformers for multimodal self-sup ervised learning from raw video, audio and text

    Hassan Akbari, Liangzhe Yuan, Rui Qian, Wei-Hong Chuang, Shih- Fu Chang, Yin Cui, and Boqing Gong. Vatt: Transformers for multimodal self-sup ervised learning from raw video, audio and text. In Advances in Neural Information Processing Systems, 2021. 14

    work page 2021

  2. [2]

    On the theory of dynamic programming

    Richard Bellman. On the theory of dynamic programming. Proceedings of the na- tional Academy of Sciences , 38(8):716–719, 1952

    work page 1952

  3. [3]

    Is space -time attention all you need for video understanding? In International Conference on Machine Learning

    Gedas Bertasius, Heng Wang, and Lorenzo Torresani. Is space -time attention all you need for video understanding? In International Conference on Machine Learning . PMLR

    work page

  4. [4]

    Simplicity bias in transformers and their ability to learn sparse boolean functio ns

    Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunso m. Simplicity bias in transformers and their ability to learn sparse boolean functio ns. In The 61st Annual Meeting Of The Association For Computational Lingui stics. Association for Computational Linguistics, 2023

    work page 2023

  5. [5]

    Low-rank bottleneck in multi-head attention models

    Srinadh Bhojanapalli, Chulhee Yun, Ankit Singh Rawat, Sashank Re ddi, and San- jiv Kumar. Low-rank bottleneck in multi-head attention models. In International Conference on Machine Mearning . PMLR, 2020

    work page 2020

  6. [6]

    Language models are few-shot learners

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D K aplan, Pra- fulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Am anda Askell, et al. Language models are few-shot learners. In Advances in neural information processing systems, 2020

    work page 2020

  7. [7]

    Decision trans former: Re- inforcement learning via sequence modeling

    Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover , Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision trans former: Re- inforcement learning via sequence modeling. In Advances in neural information processing systems, 2021

    work page 2021

  8. [8]

    What can transformer learn with vary ing depth? case studies on sequence learning tasks

    Xingwu Chen and Difan Zou. What can transformer learn with vary ing depth? case studies on sequence learning tasks. In International Conference on Machine Learning, 2024

    work page 2024

Show all 73 references
  1. [9]

    Approximation by superpositions of a sigmoidal function

    George Cybenko. Approximation by superpositions of a sigmoidal function. Mathe- matics of control, signals and systems , 2(4):303–314, 1989

    1989

  2. [10]

    BERT: pre- training of deep bidirectional transformers for language underst anding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutan ova. BERT: pre- training of deep bidirectional transformers for language underst anding. In Proceed- ings of the 2019 Conference of the North American Chapter of t he Association for Computational Linguistics: Human...

    2019

  3. [11]

    A ttention is not all you need: Pure attention loses rank doubly exponentially with depth

    Yihe Dong, Jean-Baptiste Cordonnier, and Andreas Loukas. A ttention is not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learning . PMLR, 2021

    2021

  4. [12]

    An image is worth 16x 16 words: Transformers for image recognition at scale

    Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk We issenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x 16 words: Transformers for image recognition ...

    2021

  5. [13]

    Inductive biases and variable creation in self-attention mechanisms

    Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang . Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning. PMLR, 2022. 15

    2022

  6. [14]

    Attention enables zero approximation error

    Zhiying Fang, Yidong Ouyang, Ding-Xuan Zhou, and Guang Cheng . Attention enables zero approximation error. arXiv preprint arXiv:2202.12166 , 2022

    2022 arXiv

  7. [15]

    Switch transfor mers: Scaling to trillion parameter models with simple and efficient sparsity

    William Fedus, Barret Zoph, and Noam Shazeer. Switch transfor mers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(120):1–39, 2022

    2022

  8. [16]

    On the approximate realization of continu ous mappings by neural networks

    Ken-Ichi Funahashi. On the approximate realization of continu ous mappings by neural networks. Neural networks , 2(3):183–192, 1989

    1989

  9. [17]

    Approximation rates for neur al networks with encodable weights in smoothness spaces

    Ingo G¨ uhring and Mones Raslan. Approximation rates for neur al networks with encodable weights in smoothness spaces. Neural Networks , 134:107–130, 2021

    2021

  10. [18]

    Error bou nds for approxima- tions with deep relu neural networks in w s, p norms

    Ingo G¨ uhring, Gitta Kutyniok, and Philipp Petersen. Error bou nds for approxima- tions with deep relu neural networks in w s, p norms. Analysis and Applications , 18 (05):803–859, 2020

    2020

  11. [19]

    On the rate of convergence of a classifier based on a transformer encoder

    Iryna Gurevych, Michael Kohler, and G¨ ozde G¨ ul S ¸ahin. On the rate of convergence of a classifier based on a transformer encoder. IEEE Transactions on Information Theory, 68(12):8139–8155, 2022

    2022

  12. [20]

    Understanding scaling laws with stat istical and ap- proximation theory for transformer neural networks on intrinsic ally low-dimensional data

    Alex Havrilla and Wenjing Liao. Understanding scaling laws with stat istical and ap- proximation theory for transformer neural networks on intrinsic ally low-dimensional data. arXiv preprint arXiv:2411.06646 , 2024

    2024 arXiv

  13. [21]

    Approximation capabilities of multilayer feedforwar d networks

    Kurt Hornik. Approximation capabilities of multilayer feedforwar d networks. Neural networks, 4(2):251–257, 1991

    1991

  14. [22]

    Fundamental limits of prompt tuning transformers: Univer sality, capacity and efficiency

    Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zha o Song, and Han Liu. Fundamental limits of prompt tuning transformers: Univer sality, capacity and efficiency. arXiv preprint arXiv:2411.16525 , 2024

    2024 arXiv

  15. [23]

    Offline reinforcem ent learning as one big sequence modeling problem

    Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcem ent learning as one big sequence modeling problem. In Advances in neural information processing systems, 2021

    2021

  16. [24]

    Approximation rate of the transfo rmer architecture for sequence modeling

    Haotian Jiang and Qianxiao Li. Approximation rate of the transfo rmer architecture for sequence modeling. arXiv preprint arXiv:2305.18475 , 2023

    2023 arXiv

  17. [25]

    Deep neural networks with relu-sine-exponentia l activations break curse of dimensionality in approximation on h¨ older class

    Yuling Jiao, Yanming Lai, Xiliang Lu, Fengru Wang, Jerry Zhijian Yan g, and Yuanyuan Yang. Deep neural networks with relu-sine-exponentia l activations break curse of dimensionality in approximation on h¨ older class. SIAM Journal on Mathe- matical Analysis, 55(4):3635–3649, 2023

    2023

  18. [26]

    Convergenc e analysis of flow matching in latent space with transformers

    Yuling Jiao, Yanming Lai, Yang Wang, and Bokai Yan. Convergenc e analysis of flow matching in latent space with transformers. arXiv preprint arXiv:2404.02538 , 2024

    2024 arXiv

  19. [27]

    Approximation bounds for transformed with application to regression

    Yuling Jiao, Yanming Lai, Defeng Sun, Yang Wang, and Bokai Yan. Approximation bounds for transformed with application to regression. preprint, 2025

    2025

  20. [28]

    Optimal memorization capacity of transformers

    Tokio Kajitsuka and Issei Sato. Optimal memorization capacity of transformers. arXiv preprint arXiv:2409.17677 , 2024. 16

    2024 arXiv

  21. [29]

    Are transformers with one lay er self-attention using low-rank weight matrices universal approximators? In International Conference on Learning Representations, 2024

    Tokio Kajitsuka and Issei Sato. Are transformers with one lay er self-attention using low-rank weight matrices universal approximators? In International Conference on Learning Representations, 2024

    2024

  22. [30]

    The lipschitz constant of self-attention

    Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning . PMLR, 2021

    2021

  23. [31]

    Provable memor ization ca- pacity of transformers

    Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memor ization ca- pacity of transformers. In International Conference on Learning Representations , 2023

    2023

  24. [32]

    On the representation of cont inuous functions of many variables by superposition of continuous functions of one var iable and addi- tion

    Andrei Nikolaevich Kolmogorov. On the representation of cont inuous functions of many variables by superposition of continuous functions of one var iable and addi- tion. In Doklady Akademii Nauk , volume 114, pages 953–956. Russian Academy of Sciences, 1957

    1957

  25. [33]

    Univer- sal approximation under constraints is possible with transformers

    Anastasis Kratsios, Behnoosh Zamanlooy, Tianlin Liu, and Ivan D okmanic. Univer- sal approximation under constraints is possible with transformers . In International Conference on Learning Representations , 2022

    2022

  26. [34]

    On the expressive flexibility of self-attention matrices

    Valerii Likhosherstov, Krzysztof Choromanski, and Adrian We ller. On the expressive flexibility of self-attention matrices. In Proceedings of the AAAI Conference on Artificial Intelligence , 2023

    2023

  27. [35]

    RoBERT a: A robustly optimized BERT pretraining approach

    Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Dan qi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERT a: A robustly optimized BERT pretraining approach. arXiv preprint arXiv:1907.11692 , 2019

    1907 arXiv

  28. [36]

    De ep network ap- proximation for smooth functions

    Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. De ep network ap- proximation for smooth functions. SIAM Journal on Mathematical Analysis , 53(5): 5465–5506, 2021

    2021

  29. [37]

    The ex- pressive power of neural networks: A view from the width

    Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wan g. The ex- pressive power of neural networks: A view from the width. In Advances in neural information processing systems , 2017

    2017

  30. [38]

    Your transformer may not be as powerful as you expect

    Shengjie Luo, Shanda Li, Shuxin Zheng, Tie-Yan Liu, Liwei Wang, and Di He. Your transformer may not be as powerful as you expect. In Advances in Neural Information Processing Systems, 2022

    2022

  31. [39]

    Upper and lower mem- ory capacity bounds of transformers for next-token prediction

    Liam Madden, Curtis Fox, and Christos Thrampoulidis. Upper and lower mem- ory capacity bounds of transformers for next-token prediction . arXiv preprint arXiv:2405.13718, 2024

    2024

  32. [40]

    Memor ization capacity of multi-head attention in transformers

    Sadegh Mahdavi, Renjie Liao, and Christos Thrampoulidis. Memor ization capacity of multi-head attention in transformers. In International Conference on Learning Representations, 2024

    2024

  33. [41]

    Stabilizing transformers for reinforcement learning

    Emilio Parisotto, Francis Song, Jack Rae, Razvan Pascanu, Cag lar Gulcehre, Sid- dhant Jayakumar, Max Jaderberg, Raphael Lopez Kaufman, Aida n Clark, Seb Noury, et al. Stabilizing transformers for reinforcement learning. In International Conference on Machine Learning . PMLR, 2020. 17

    2020

  34. [42]

    Scalable diffusion models with transfor mers

    William Peebles and Saining Xie. Scalable diffusion models with transfor mers. In IEEE International Conference on Computer Vision , 2023

    2023

  35. [43]

    Prompting a pre trained trans- former can be a universal approximator

    Aleksandar Petrov, Philip HS Torr, and Adel Bibi. Prompting a pre trained trans- former can be a universal approximator. In Proceedings of the 41st International Conference on Machine Learning , pages 40523–40550, 2024

    2024

  36. [44]

    Sutsk ever

    Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya. Sutsk ever. Improving language understanding by generative pre-training. 2018

    2018

  37. [45]

    Language models are unsupervised multitask learners

    Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners . OpenAI blog , 1 (8):9, 2019

    2019

  38. [46]

    Represe ntational strengths and limitations of transformers

    Clayton Sanford, Daniel J Hsu, and Matus Telgarsky. Represe ntational strengths and limitations of transformers. In Advances in Neural Information Processing Systems , 2024

    2024

  39. [47]

    The kolmogorov–arnold represent ation theorem revisited

    Johannes Schmidt-Hieber. The kolmogorov–arnold represent ation theorem revisited. Neural networks , 137:119–126, 2021

    2021

  40. [48]

    Deep network a pproximation char- acterized by number of neurons

    Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network a pproximation char- acterized by number of neurons. Communications in Computational Physics , 28(5): 1768–1811, 2020

    2020

  41. [49]

    Deep network w ith approximation error being reciprocal of width to power of square root of depth

    Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network w ith approximation error being reciprocal of width to power of square root of depth. Neural Computation, 33(4):1005–1036, 2021

    2021

  42. [50]

    Neural networ k approximation: Three hidden layers are enough

    Zuowei Shen, Haizhao Yang, and Shijun Zhang. Neural networ k approximation: Three hidden layers are enough. Neural Networks , 141:160–173, 2021

    2021

  43. [51]

    Optimal approx imation rate of relu networks in terms of width and depth

    Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approx imation rate of relu networks in terms of width and depth. Journal de Math´ ematiques Pures et Appliqu´ ees, 157:101–135, 2022

    2022

  44. [52]

    Sharp bounds on the approx imation rates, metric entropy, and n-widths of shallow neural networks

    Jonathan W Siegel and Jinchao Xu. Sharp bounds on the approx imation rates, metric entropy, and n-widths of shallow neural networks. Foundations of Computational Mathematics, 24(2):481–537, 2024

    2024

  45. [53]

    Adaptivity of deep relu network for learning in beso v and mixed smooth besov spaces: optimal rate and curse of dimensionality

    Taiji Suzuki. Adaptivity of deep relu network for learning in beso v and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations , 2019

    2019

  46. [54]

    Approximation and estimat ion ability of trans- formers for sequence-to-sequence functions with infinite dimens ional input

    Shokichi Takakura and Taiji Suzuki. Approximation and estimat ion ability of trans- formers for sequence-to-sequence functions with infinite dimens ional input. In Inter- national Conference on Machine Learning . PMLR, 2023

    2023

  47. [55]

    Sequence length independen t norm-based gener- alization bounds for transformers

    Jacob Trauger and Ambuj Tewari. Sequence length independen t norm-based gener- alization bounds for transformers. In International Conference on Artificial Intelli- gence and Statistics . PMLR, 2024. 18

    2024

  48. [56]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems , 2017

    2017

  49. [57]

    A mathematical theory of attention

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

    2007 arXiv

  50. [58]

    Understanding the expressive power and mechanisms of transformer for sequence modeling

    Mingze Wang and Weinan E. Understanding the expressive power and mechanisms of transformer for sequence modeling. arXiv preprint arXiv:2402.00522 , 2024

    2024 arXiv

  51. [59]

    Don’t fear peculiar activation functions: Eu af and beyond

    Qianchao Wang, Shijun Zhang, Dong Zeng, Zhaoheng Xie, Hengt ao Guo, Feng-Lei Fan, and Tieyong Zeng. Don’t fear peculiar activation functions: Eu af and beyond. arXiv preprint arXiv:2407.09580 , 2024

    2024

  52. [60]

    Transfo rmers prov- ably learn sparse token selection while fully-connected nets cannot

    Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason D Lee. Transfo rmers prov- ably learn sparse token selection while fully-connected nets cannot . arXiv preprint arXiv:2406.06893, 2024

    2024 arXiv

  53. [61]

    Statistically meaningful app roximation: a case study on approximating turing machines with transformers

    Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful app roximation: a case study on approximating turing machines with transformers. In Advances in Neural Information Processing Systems , 2022

    2022

  54. [62]

    Whic h transformer architecture fits my data? a vocabulary bottleneck in self-attent ion

    Noam Wies, Yoav Levine, Daniel Jannai, and Amnon Shashua. Whic h transformer architecture fits my data? a vocabulary bottleneck in self-attent ion. In International Conference on Machine Learning . PMLR, 2021

    2021

  55. [63]

    Carbonell, Ruslan Salak hutdinov, and Quoc V

    Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salak hutdinov, and Quoc V. Le. Xlnet: Generalized autoregressive pretraining for language under- standing. In Advances in Neural Information Processing Systems , 2019

    2019

  56. [64]

    Error bounds for approximations with deep r elu networks

    Dmitry Yarotsky. Error bounds for approximations with deep r elu networks. Neural networks, 94:103–114, 2017

    2017

  57. [65]

    Optimal approximation of continuous functio ns by very deep relu networks

    Dmitry Yarotsky. Optimal approximation of continuous functio ns by very deep relu networks. In Conference on Learning Theory . PMLR, 2018

    2018

  58. [66]

    Elementary superexpressive activations

    Dmitry Yarotsky. Elementary superexpressive activations. I n International Confer- ence on Machine Learning . PMLR, 2021

    2021

  59. [67]

    The phase diagram o f approximation rates for deep neural networks

    Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram o f approximation rates for deep neural networks. In Advances in Neural Information Processing Systems , 2020

    2020

  60. [68]

    Do transformers really perform badly fo r graph repre- sentation? In Advances in Neural Information Processing Systems , 2021

    Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke , Di He, Yan- ming Shen, and Tie-Yan Liu. Do transformers really perform badly fo r graph repre- sentation? In Advances in Neural Information Processing Systems , 2021

    2021

  61. [69]

    Reddi, and Sanjiv Kumar

    Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J . Reddi, and Sanjiv Kumar. Are transformers universal approximators of seq uence-to-sequence functions? In International Conference on Learning Representations , 2020. 19

    2020

  62. [70]

    O (n) connections are expressive enough : Universal ap- proximability of sparse transformers

    Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Ra wat, Sashank Reddi, and Sanjiv Kumar. O (n) connections are expressive enough : Universal ap- proximability of sparse transformers. In Advances in Neural Information Processing Systems, 2020

    2020

  63. [71]

    Big bird: Transformers for longer sequences

    Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Josh ua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, L i Yang, et al. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, 2020

    2020

  64. [72]

    Deep network a pproximation: Achieving arbitrary accuracy with fixed number of neurons

    Shijun Zhang, Zuowei Shen, and Haizhao Yang. Deep network a pproximation: Achieving arbitrary accuracy with fixed number of neurons. Journal of Machine Learning Research, 23(276):1–60, 2022. A Proof of Lemma 1 We only present a proof for the ReLU case. The proof for the floor -R...

    2022

  65. [73]

    The space Cm consists of all functions whose first m derivatives exist and are continuous, and C0 denotes the space of continuous functions

    Hβ denotes the space of β-H¨ older continuous functions with compact support and bounded norm. The space Cm consists of all functions whose first m derivatives exist and are continuous, and C0 denotes the space of continuous functions. Bγ(·;a) p,θ refers to the Besov space with...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.