Approximation Error Upper and Lower Bounds for Hölder Class with Transformers

• URL: http://arxiv.org/abs/2605.07463v1
• Date: Fri, 08 May 2026 09:10:31 GMT
• Title: Approximation Error Upper and Lower Bounds for Hölder Class with Transformers
• Abstract summary: A new approximation upper bound is derived for the standard Transformer architecture equipped with Softmax operators, ReLU activation functions, and residual connections.<n>We prove that a Transformer network composed of at most $mathcalO(varepsilon-d_0/)$ blocks can approximate any bounded Hlder function.<n>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 $(varepsilon-d_0/(4)
• Score: 22.477358103223036
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore the expressive power of Transformers by establishing precise approximation error upper and lower bounds for Hölder 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 $\mathcal{O}(\varepsilon^{-{d_{0}}/α})$ blocks can approximate any bounded Hölder function with $d_{0}$-dimensional input and smoothness $α\in(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 $Ω(\varepsilon^{-{d_{0}}/({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.

Related papers

• Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't [78.36679389968772]
  We find that padded $textL$ constantprecision transformers are surprisingly robust to expressivity.<n>$logd-looped constant-precision transformers reach $textFO-uniform TCd$, and growing-precision ones reach $textFO-uniform TCd$.
  arXiv  Detail & Related papers  (2026-05-28T19:58:43Z)
• Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity [5.37133760455631]
  This paper investigates the learning theory of Transformer networks for regression tasks on the compact Euclidean domain $[0,1]d$.<n>We propose a novel constructive approximation framework for Transformers that builds local approximations of the target function and aggregates them into a global approximation.<n>We prove that a dense Transformer equipped with only two encoder blocks and standard single-hidden-layer point-wise feed-forward networks can achieve a uniform $varepsilon$-approximation error for $$-Hlder continuous functions.
  arXiv  Detail & Related papers  (2026-05-09T09:02:37Z)
• Standard Transformers Achieve the Minimax Rate in Nonparametric Regression with $C^{s,λ}$ Targets [8.844802588836059]
  This paper is the first work proving that standard Transformers can approximate Hlder functions.<n>By introducing two metrics: the size and the dimension vector, we provide a fine-grained characterization of Transformer structures.
  arXiv  Detail & Related papers  (2026-02-24T05:14:01Z)
• Transformers as Measure-Theoretic Associative Memory: A Statistical Perspective and Minimax Optimality [52.424255020469595]
  Transformers excel through content-addressable retrieval and the ability to exploit contexts, in principle, length.<n>We recast associative memory at the level of probability measures, treating a context as a distribution over unbounded tokens.<n>We show that a shallow measure-theoretic Transformer learns the recall-and-predict map under a spectral assumption on the input densities.
  arXiv  Detail & Related papers  (2026-02-02T09:34:17Z)
• Scaling Diffusion Transformers Efficiently via $μ$P [61.13987622359833]
  Maximal Update Parametrization ($mu$P) was proposed for vanilla Transformers, which enables stable HP transfer from small to large language models.<n>We generalize standard $mu$P to diffusion Transformers and validate its effectiveness through large-scale experiments.
  arXiv  Detail & Related papers  (2025-05-21T08:49:03Z)
• Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective [7.069772598731282]
  The Transformer model is widely used in various application areas of machine learning, such as natural language processing.<n>This paper investigates the approximation of the H"older continuous function class $mathcalH_Qbetaleft([0,1]dtimes n,mathbbRdtimes nright)$ by Transformers and constructs several Transformers that can overcome the curse of dimensionality.
  arXiv  Detail & Related papers  (2025-04-18T08:56:53Z)
• Approximation Bounds for Transformer Networks with Application to Regression [9.549045683389085]
  We explore the approximation capabilities of Transformer networks for H"older and Sobolev functions.<n>We establish novel upper bounds for standard Transformer networks approxing sequence-to-sequence mappings.<n>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.
  arXiv  Detail & Related papers  (2025-04-16T15:25:58Z)
• Circuit Complexity Bounds for RoPE-based Transformer Architecture [25.2590541420499]
  Empirical evidence suggests that $mathsfRoPE$-based Transformer architectures demonstrate greater generalization capabilities than conventional Transformer models.<n>We show that unless $mathsfTC0 = mathsfNC1$, a $mathsfRoPE$-based Transformer with $mathrmpoly(n)$-precision, $O(1)$ layers, hidden dimension $d leq O(n)$ cannot solve the Arithmetic formula evaluation problem.
  arXiv  Detail & Related papers  (2024-11-12T07:24:41Z)
• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  We study in-context learning for linear regression with diverse tasks. We show that multilayer Transformers are not robust to even distributional shifts as small as $O(e-L)$ in Wasserstein distance.
  arXiv  Detail & Related papers  (2024-10-29T03:27:56Z)
• Higher-Order Transformer Derivative Estimates for Explicit Pathwise Learning Guarantees [9.305677878388664]
  This paper fills a gap in the literature by precisely estimating all the higher-order derivatives of all orders for the transformer model.<n>We obtain fully-explicit estimates of all constants in terms of the number of attention heads, the depth and width of each transformer block, and the number of normalization layers.<n>We conclude that real-world transformers can learn from $N$ samples of a single Markov process's trajectory at a rate of $O(operatornamepolylog(N/sqrtN)$.
  arXiv  Detail & Related papers  (2024-05-26T13:19:32Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.