Approximation Error Upper and Lower Bounds for H"older Class with Transformers
Not on the map. Why?
Abstract (arXiv)
We explore the expressive power of Transformers by establishing precise approximation error upper and lower bounds for H"older class. Specifically, a new approximation upper bound is derived for the standard Transformer architecture equipped with Softmax operators, ReLU activation functions, and residual connections. We prove that a Transformer network composed of at most O(varepsilon^-d0/α) blocks can approximate any bounded H"older function with d0-dimensional input and smoothness α∈(0,1] under any accuracy varepsilon>0. In the case of approximation lower bounds, leveraging the VC-dimension upper bound, we are the first to rigorously prove that Transformers demand for at least Omega(varepsilon^-d0/(4α)) blocks to achieve the varepsilon approximation accuracy. As a final step, we extend the derived results for standard Transformers to a general regression task and establish the corresponding excess risk rates demonstrating Transformers' empirical effectiveness in real-world settings.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 41 references that are in the map. First posted on arXiv 8 May 2026.
Builds on
29 of 41 references.
References · 29
- 2017Attention Is All You Needcited by 60,361
- 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
- 2023GPT-4 Technical Reportcited by 18,396
- 2016Error bounds for approximations with deep ReLU networkscited by 574
- 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
- 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
- 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
- 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
- 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 96
- 2019The phase diagram of approximation rates for deep neural networkscited by 88
- 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
- 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
17 more
- 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
- 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 40
- 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 40
- 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 36
- 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
- 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
- 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
- 2024Prompting a Pretrained Transformer Can Be a Universal Approximatorcited by 25
- 2024Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiencycited by 22
- 2024On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimalitycited by 22
- 2021On the rate of convergence of a classifier based on a Transformer encodercited by 16
- 2024Convergence Analysis of Flow Matching in Latent Space with Transformerscited by 16
- 2024On the rates of convergence for learning with convolutional neural networkscited by 10
- 2024On the Optimal Memorization Capacity of Transformerscited by 10
- 2025Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspectivecited by 5
- 2021Universal Regular Conditional Distributionscited by 4
- 2025Approximation Bounds for Transformer Networks with Application to Regressioncited by 4
Built on by
Not cited yet.