Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity

• URL: http://arxiv.org/abs/2605.08811v1
• Date: Sat, 09 May 2026 09:02:37 GMT
• Title: Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity
• Abstract summary: 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.
• Score: 5.37133760455631
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the learning theory of Transformer networks for regression tasks on the compact Euclidean domain $[0,1]^d$ and $d$-dimensional compact Riemannian manifolds. We propose a novel constructive approximation framework for Transformers that builds local approximations of the target function and aggregates them into a global approximation via softmax partition of unity. This approach leverages the attention mechanism to achieve spatial localization through affine transformations of the input. The softmax activation plays a crucial role in aggregating local approximations to a global output. From an approximation perspective, 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 $α$-Hölder continuous functions with $α\in (0,1]$ using $\mathcal{O}(\varepsilon^{-d/α})$ total parameters. Building upon this approximation guarantee, we establish a near minimax-optimal generalization error bound of order $\mathcal{O}\big(n^{-\frac{2α}{2α+d}} \log n\big)$ for the empirical risk minimizer, where $n$ is the training data size. The Transformer architecture studied in this paper is dense, shallow and wide, and employs softmax activation and sinusoidal positional encodings, closely reflecting practical implementations.

Related papers

• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
  arXiv  Detail & Related papers  (2026-06-04T16:04:31Z)
• FlatVPR: Plug-and-play Geo-linear Residual Adapter for Geometric Rectification of Foundation Model Feature Manifolds [0.7734726150561086]
  FlatVPR'' bridges the trade-off between map lightweightness and localization accuracy in visual place recognition.<n>Our method explicitly suppresses manifold curvature using a mathematically grounded Pullback Flatness Loss.<n>Experiments on the NCLT dataset demonstrate that the application of our adapter leads to significant performance improvements.
  arXiv  Detail & Related papers  (2026-06-01T05:56:59Z)
• Metric--Phase Fields: Decoupling Distance and Sign for Thin-Structure Reconstruction from Unoriented Point Clouds [67.30236447078187]
  We introduce Metric-Phase Fields (MPFs), a decoupled implicit representation that separates metric proximity from topological phase.<n>Experiments on both synthetic and scanned thin-shell and thin-plate shapes demonstrate that MPFs preserve thin and layered structures more faithfully than recent SDF-based methods.
  arXiv  Detail & Related papers  (2026-05-25T07:08:57Z)
• InfoFlow: A Framework for Multi-Layer Transformer Analysis [28.731784494689276]
  Multi-layer Transformers possess fundamentally different approximation capabilities from single-layer ones.<n>We propose InfoFlow, a framework for multi-layer Transformers.
  arXiv  Detail & Related papers  (2026-05-18T06:38:39Z)
• Fermion lattices can be simulated by same-size qubit lattices with $\mathcal{O}(1)$ interaction overhead [0.0]
  Local interactions among electrons underlie many complex properties of correlated materials.<n>We show how to simulate all geometrically local interactions on an $N$-site two-dimensional fermion lattice with no overhead in the number of interactions and no space overhead.
  arXiv  Detail & Related papers  (2026-05-12T18:00:04Z)
• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local L is a new projection-free type for constrained optimization.<n>Local LMO is perhaps best viewed as an oracle of Gradient Descent (GD)
  arXiv  Detail & Related papers  (2026-05-09T10:03:24Z)
• Approximation Error Upper and Lower Bounds for Hölder Class with Transformers [22.477358103223036]
  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)
  arXiv  Detail & Related papers  (2026-05-08T09:10:31Z)
• Ghosts of Softmax: Complex Singularities That Limit Safe Step Sizes in Cross-Entropy [0.0]
  Cross-entropy training analyses rely on local Taylor models of the loss to predict whether a proposed step will decrease the objective.<n>We derive closed-form expressions under logit linearization along the proposed update direction.<n>Temperature scaling confirms the mechanism: normalizing by $_a$ shrinks the onset-threshold spread from standard deviation $0.992$ to $0.164$.
  arXiv  Detail & Related papers  (2026-03-13T19:42:12Z)
• 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)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
  arXiv  Detail & Related papers  (2025-11-11T15:38:57Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients [0.196629787330046]
  We show that incorporating partial second-order information of the objective function can dramatically improve robustness to mini-batch size of variance-reduced gradient methods. We demonstrate this phenomenon on a prototypical Newton ($textttMb-SVRN$) algorithm.
  arXiv  Detail & Related papers  (2024-04-23T05:45:52Z)
• 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.