# Approximation Bounds for Transformer Networks with Application to Regression

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 70 references that are in the map.
- First posted on arXiv 16 Apr 2025.

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [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)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [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)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Deep Network Approximation Characterized by Number of Neurons](https://mlsanity.com/paper/1906.05497/) (2019)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [The Kolmogorov-Arnold representation theorem revisited](https://mlsanity.com/paper/2007.15884/) (2020)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recovery](https://mlsanity.com/paper/1908.01842/) (2019)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons](https://mlsanity.com/paper/2107.02397/) (2021)
- [On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding](https://mlsanity.com/paper/2410.01405/) (2024)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input](https://mlsanity.com/paper/2305.18699/) (2023)
- [Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Data](https://mlsanity.com/paper/2411.06646/) (2024)
- [Approximation Rate of the Transformer Architecture for Sequence Modeling](https://mlsanity.com/paper/2305.18475/) (2023)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling](https://mlsanity.com/paper/2402.00522/) (2024)
- [Prompting a Pretrained Transformer Can Be a Universal Approximator](https://mlsanity.com/paper/2402.14753/) (2024)
- [Nonparametric regression using over-parameterized shallow ReLU neural networks](https://mlsanity.com/paper/2306.08321/) (2023)

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

- [Posterior Contraction for Sparse Neural Networks in Besov Spaces with Intrinsic Dimensionality](https://mlsanity.com/paper/2506.19144/) (2025)
- [Universal Approximation of Measure-to-Measure Operators by Pushforwards](https://mlsanity.com/paper/2609.35483/) (2026)
- [Learning Guarantee of Reward Modeling Using Deep Neural Networks](https://mlsanity.com/paper/2505.06601/) (2025)
- [Approximation Error Upper and Lower Bounds for H"older Class with Transformers](https://mlsanity.com/paper/2605.07463/) (2026)

## Abstract (arXiv)

We explore the approximation capabilities of Transformer networks for H"older and Sobolev functions, and apply these results to address nonparametric regression estimation with dependent observations. First, we establish novel upper bounds for standard Transformer networks approximating sequence-to-sequence mappings whose component functions are H"older continuous with smoothness index γ ∈ (0,1]. To achieve an approximation error varepsilon under the Lp-norm for p ∈ [1, ∞], it suffices to use a fixed-depth Transformer network whose total number of parameters scales as varepsilon-dx n / γ. This result not only extends existing findings to include the case p = ∞, but also matches the best known upper bounds on number of parameters previously obtained for fixed-depth FNNs and RNNs. Similar bounds are also derived for Sobolev functions. Second, we derive explicit convergence rates for the nonparametric regression problem under various β-mixing data assumptions, which allow the dependence between observations to weaken over time. Our bounds on the sample complexity impose no constraints on weight magnitudes. Lastly, we propose a novel proof strategy to establish approximation bounds, inspired by the Kolmogorov-Arnold representation theorem. We show that if the self-attention layer in a Transformer can perform column averaging, the network can approximate sequence-to-sequence H"older functions, offering new insights into the interpretability of self-attention mechanisms.