Sharper Generalization Bounds for Transformer

• URL: http://arxiv.org/abs/2603.21541v1
• Date: Mon, 23 Mar 2026 03:54:52 GMT
• Title: Sharper Generalization Bounds for Transformer
• Abstract summary: We first express the excess risk of Transformers in terms of the offset Rademacher complexity.<n>We then derive refined excess risk bounds by upper bounding the covering numbers of Transformer hypothesis spaces.<n>We relax the boundedness assumption on feature mappings and extend our theoretical results to settings with unbounded (sub-Gaussian) features and heavy-tailed distributions.
• Score: 24.982988565358692
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies generalization error bounds for Transformer models. Based on the offset Rademacher complexity, we derive sharper generalization bounds for different Transformer architectures, including single-layer single-head, single-layer multi-head, and multi-layer Transformers. We first express the excess risk of Transformers in terms of the offset Rademacher complexity. By exploiting its connection with the empirical covering numbers of the corresponding hypothesis spaces, we obtain excess risk bounds that achieve optimal convergence rates up to constant factors. We then derive refined excess risk bounds by upper bounding the covering numbers of Transformer hypothesis spaces using matrix ranks and matrix norms, leading to precise, architecture-dependent generalization bounds. Finally, we relax the boundedness assumption on feature mappings and extend our theoretical results to settings with unbounded (sub-Gaussian) features and heavy-tailed distributions.

Related papers

• Spectrum-Adaptive Generalization Bounds for Trained Deep Transformers [6.2000582635449994]
  We derive spectrum-adaptive post hoc bounds for multi-layer Transformers.<n>Our results provide a complexity-based perspective on how the spectral structure of trained Transformers is reflected in analyses.
  arXiv  Detail & Related papers  (2026-05-08T06:08:25Z)
• Ordinary Least Squares is a Special Case of Transformer [13.28797305532504]
  We show that Transformer's basic nature: Ordinary Least Squares (OLS) is a special case of the single-layer Linear Transformer.<n>We also uncover a decoupled slow and fast memory mechanism within Transformers.<n>This progression facilitates the transition of the Hopfield energy function from linear to exponential memory capacity.
  arXiv  Detail & Related papers  (2026-04-15T09:21:01Z)
• On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions [8.192218166714422]
  Transformer networks have achieved remarkable empirical success across a wide range of applications, yet their theoretical expressive power remains insufficiently understood.<n>We first establish an explicit approximation of maxout networks by Transformer networks while preserving comparable model complexity.<n>As a consequence, Transformers inherit the universal approximation capability of ReLU networks under similar complexity constraints.
  arXiv  Detail & Related papers  (2026-03-03T15:27:15Z)
• Length Generalization Bounds for Transformers [9.186207021992535]
  Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length.<n>To provide such a guarantee, one needs to be able to compute a length generalization bound, beyond which the model is guaranteed to generalize.<n>This paper concerns the open problem of the computability of such generalization bounds for CRASP, a class of languages which is closely linked to transformers.
  arXiv  Detail & Related papers  (2026-02-13T14:49:27Z)
• Linear combination of unitaries with exponential convergence [0.0]
  We present a general method for decomposing non-unitary operators into a linear combination of unitary operators.<n>When implemented in a quantum circuit, the subnormalisation of the resulting block encoding scales with the double logarithm of the inverse error.
  arXiv  Detail & Related papers  (2026-01-25T22:47:21Z)
• A Constrained Optimization Perspective of Unrolled Transformers [77.12297732942095]
  We introduce a constrained optimization framework for training transformers that behave like optimization descent algorithms.<n>We observe constrained transformers achieve stronger to perturbations robustness and maintain higher out-of-distribution generalization.
  arXiv  Detail & Related papers  (2026-01-24T02:12:39Z)
• Generalization Bounds for Transformer Channel Decoders [61.55280736553095]
  This paper studies the generalization performance of ECCT from a learning-theoretic perspective.<n>To the best of our knowledge, this work provides the first theoretical generalization guarantees for this class of decoders.
  arXiv  Detail & Related papers  (2026-01-11T15:56:37Z)
• WUSH: Near-Optimal Adaptive Transforms for LLM Quantization [52.77441224845925]
  Quantization to low bitwidth is a standard approach for deploying large language models.<n>A few extreme weights and activations stretch the dynamic range and reduce the effective resolution of the quantizer.<n>We derive, for the first time, closed-form optimal linear blockwise transforms for joint weight-activation quantization.
  arXiv  Detail & Related papers  (2025-11-30T16:17:34Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• 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)
• MoEUT: Mixture-of-Experts Universal Transformers [75.96744719516813]
  Universal Transformers (UTs) have advantages over standard Transformers in learning compositional generalizations. Layer-sharing drastically reduces the parameter count compared to the non-shared model with the same dimensionality. No previous work has succeeded in proposing a shared-layer Transformer design that is competitive in parameter count-dominated tasks such as language modeling.
  arXiv  Detail & Related papers  (2024-05-25T03:24:32Z)
• On the Convergence of Encoder-only Shallow Transformers [62.639819460956176]
  We build the global convergence theory of encoder-only shallow Transformers under a realistic setting. Our results can pave the way for a better understanding of modern Transformers, particularly on training dynamics.
  arXiv  Detail & Related papers  (2023-11-02T20:03:05Z)
• Sequence Length Independent Norm-Based Generalization Bounds for Transformers [21.2523248114561]
  This paper provides norm-based generalization bounds for the Transformer architecture that do not depend on the input sequence length. We use three novel covering number bounds for the function class of bounded linear transformations to upper bound the Rademacher complexity of the Transformer.
  arXiv  Detail & Related papers  (2023-10-19T18:31:09Z)

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.