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

arXiv: https://arxiv.org/abs/2504.13558 · HTML: https://mlsanity.com/paper/2504.13558/

## 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 (most cited first, 30 of 59)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Is Space-Time Attention All You Need for Video Understanding?](https://mlsanity.com/paper/2102.05095/) (2021)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [VATT: Transformers for Multimodal Self-Supervised Learning from Raw Video, Audio and Text](https://mlsanity.com/paper/2104.11178/) (2021)
- [Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth](https://mlsanity.com/paper/2103.03404/) (2021)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Stabilizing Transformers for Reinforcement Learning](https://mlsanity.com/paper/1910.06764/) (2019)
- [The Lipschitz Constant of Self-Attention](https://mlsanity.com/paper/2006.04710/) (2020)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Deep Network Approximation Characterized by Number of Neurons](https://mlsanity.com/paper/1906.05497/) (2019)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Error bounds for approximations with deep ReLU neural networks in Ws,p norms](https://mlsanity.com/paper/1902.07896/) (2019)
- [Low-Rank Bottleneck in Multi-head Attention Models](https://mlsanity.com/paper/2002.07028/) (2020)
- [The Kolmogorov-Arnold representation theorem revisited](https://mlsanity.com/paper/2007.15884/) (2020)
- [The phase diagram of approximation rates for deep neural networks](https://mlsanity.com/paper/1906.09477/) (2019)

## Built on by (most cited first, 5 of 5)

- [Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity](https://mlsanity.com/paper/2605.08811/) (2026)
- [On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions](https://mlsanity.com/paper/2603.03084/) (2026)
- [On the Universality of Transformer Architectures; How Much Attention Is Enough?](https://mlsanity.com/paper/2512.18445/) (2025)
- [Approximation Error Upper and Lower Bounds for H"older Class with Transformers](https://mlsanity.com/paper/2605.07463/) (2026)
- [The Stability of Singular Distribution: A Spectral Perspective on the Two-Phase Dynamics of Language Model Pre-training](https://mlsanity.com/paper/2605.26489/) (2026)

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