mlsanityData to 14 Oct 2026

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

arXiv 2504.13558 ↗First posted 18 Apr 2025cs.LG cs.AIcited by 5

Not on the map. Why?

Abstract (arXiv)

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 HQβleft([0,1]d× n,ℝd× nright) 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 ε, if the activation functions of the feedforward layers in the Transformer are ReLU and floor, only Oleft(logfrac1εright) layers of feedforward layers are needed, with widths of these layers not exceeding Oleft(frac1ε2/βlogfrac1ε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.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 59 of its 80 references that are in the map. First posted on arXiv 18 Apr 2025.

Builds on

59 of 80 references.

References · 59

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  5. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,372
  6. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,073
  7. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  8. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  9. 2021Is Space-Time Attention All You Need for Video Understanding?cited by 1,620
  10. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,546
  11. 2016Error bounds for approximations with deep ReLU networkscited by 574
  12. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
38 more
  1. 2021VATT: Transformers for Multimodal Self-Supervised Learning from Raw Video, Audio and Textcited by 429
  2. 2021Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depthcited by 419
  3. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  4. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  5. 2019Stabilizing Transformers for Reinforcement Learningcited by 270
  6. 2020The Lipschitz Constant of Self-Attentioncited by 174
  7. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 166
  8. 2020Deep Network Approximation for Smooth Functionscited by 164
  9. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
  10. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  11. 2023Representational Strengths and Limitations of Transformerscited by 133
  12. 2019Deep Network Approximation Characterized by Number of Neuronscited by 122
  13. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  14. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 96
  15. 2019Error bounds for approximations with deep ReLU neural networks in Ws,p normscited by 95
  16. 2020Low-Rank Bottleneck in Multi-head Attention Modelscited by 89
  17. 2020The Kolmogorov-Arnold representation theorem revisitedcited by 89
  18. 2019The phase diagram of approximation rates for deep neural networkscited by 88
  19. 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
  20. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 83
  21. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  22. 2020Neural Network Approximation: Three Hidden Layers Are Enoughcited by 63
  23. 2022Your Transformer May Not be as Powerful as You Expectcited by 55
  24. 2022Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spacescited by 51
  25. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  26. 2020A Mathematical Theory of Attentioncited by 46
  27. 2021Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neuronscited by 41
  28. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 40
  29. 2021Elementary superexpressive activationscited by 36
  30. 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
  31. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  32. 2024Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Datacited by 30
  33. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 29
  34. 2023Approximation Rate of the Transformer Architecture for Sequence Modelingcited by 28
  35. 2024Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modelingcited by 25
  36. 2024Prompting a Pretrained Transformer Can Be a Universal Approximatorcited by 25
  37. 2023Nonparametric regression using over-parameterized shallow ReLU neural networkscited by 24
  38. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 22

50 most cited of 59 All 59 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 4.

5 papers.

  1. 2026Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unitycited by 2
  2. 2026On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functionscited by 1
  3. 2025On the Universality of Transformer Architectures; How Much Attention Is Enough?cited by 0
  4. 2026Approximation Error Upper and Lower Bounds for H"older Class with Transformerscited by 0
  5. 2026The Stability of Singular Distribution: A Spectral Perspective on the Two-Phase Dynamics of Language Model Pre-trainingcited by 0