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

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}}/{\alpha}})$ blocks can approximate any bounded Hölder function with $d_{0}$-dimensional input and smoothness $\alpha\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 $\Omega(\varepsilon^{-{d_{0}}/({4\alpha})})$ 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.

Why is the Transformer — the core architecture of modern AI models — so powerful? And what scale must a Transformer reach to control errors within a specific range when processing complex tasks? To answer these questions, we analytically evaluated the expressivity of Transformers through specific function approximation tasks, and aimed to establish a rigorous mathematical explanation for their success. In this paper, we derived the minimum and maximum model scale required for a standard yet mathematically simplified Transformer to achieve a given target accuracy. From another perspective, for any given model size, our results reveal the absolute best- and worst-case theoretical accuracy limits that a Transformer can reach. These theoretical guarantees provide solid mathematical backing for Transformers' remarkable performance. Furthermore, by extending our findings to general regression tasks, we offer a theoretical explanation for why Transformers perform so well in real-world applications.