Sequence Length Independent Norm-Based Generalization Bounds for Transformers

• URL: http://arxiv.org/abs/2310.13088v1
• Date: Thu, 19 Oct 2023 18:31:09 GMT
• Title: Sequence Length Independent Norm-Based Generalization Bounds for Transformers
• Abstract summary: 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.
• Score: 21.2523248114561
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper provides norm-based generalization bounds for the Transformer architecture that do not depend on the input sequence length. We employ a covering number based approach to prove our bounds. We use three novel covering number bounds for the function class of bounded linear transformations to upper bound the Rademacher complexity of the Transformer. Furthermore, we show this generalization bound applies to the common Transformer training technique of masking and then predicting the masked word. We also run a simulated study on a sparse majority data set that empirically validates our theoretical findings.

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)
• Sharper Generalization Bounds for Transformer [24.982988565358692]
  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.
  arXiv  Detail & Related papers  (2026-03-23T03:54:52Z)
• 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)
• 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)
• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  We study the problem of length generalization (LG) in transformers.<n>LG occurs when the internal behavior of the transformer on longer sequences can be "simulated" by its behavior on shorter sequences.
  arXiv  Detail & Related papers  (2025-10-30T21:31:36Z)
• The calculus of variations of the Transformer on the hyperspherical tangent bundle [0.0]
  We offer a theoretical mathematical background to Transformers through Lagrangian optimization across the token space.<n>The Transformer, as a flow map, exists in the tangent fiber for each token along the high-dimensional unit sphere.<n>We derive the Euler-Lagrange equation for the Transformer.
  arXiv  Detail & Related papers  (2025-07-21T09:43:33Z)
• Theoretical Analysis of Positional Encodings in Transformer Models: Impact on Expressiveness and Generalization [10.034655199520168]
  Positional encodings are a core part of transformer-based models.<n>This paper analyzes how various positional encoding methods impact a transformer's expressiveness, generalization ability, and extrapolation to longer sequences.
  arXiv  Detail & Related papers  (2025-06-05T23:02:18Z)
• The Role of Sparsity for Length Generalization in Transformers [58.65997625433689]
  We propose a new theoretical framework to study length generalization for the next-token prediction task. We show that length generalization occurs as long as each predicted token depends on a small (fixed) number of previous tokens. We introduce Predictive Position Coupling, which trains the transformer to predict the position IDs used in a positional coupling approach.
  arXiv  Detail & Related papers  (2025-02-24T03:01:03Z)
• On Rank-Dependent Generalisation Error Bounds for Transformers [18.601449856300984]
  We introduce various covering number bounds for linear function classes, each subject to different constraints on input and matrix norms. We then apply these bounds to derive generalization errors for single layer transformers.
  arXiv  Detail & Related papers  (2024-10-15T11:14: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. 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. 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)
• Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
  We show that the success of length generalization is intricately linked to the data format and the type of position encoding. We show for the first time that standard Transformers can extrapolate to a sequence length that is 2.5x the input length.
  arXiv  Detail & Related papers  (2024-02-14T18:18:29Z)
• 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)
• Sumformer: Universal Approximation for Efficient Transformers [2.4832703558223725]
  We introduce Sumformer, a novel and simple architecture capable of universally approxingimating sequence-to-sequence functions. We derive a new proof for Transformers, showing that just one attention layer is sufficient for universal approximation.
  arXiv  Detail & Related papers  (2023-07-05T13:59:35Z)
• Universality and Limitations of Prompt Tuning [65.8354898840308]
  We take one of the first steps to understand the role of soft-prompt tuning for transformer-based architectures. We analyze prompt tuning from the lens of universality and limitations with finite-depth pretrained transformers for continuous-valued functions. Our result guarantees the existence of a strong transformer with a prompt to approximate any sequence-to-sequence function in the set of Lipschitz functions.
  arXiv  Detail & Related papers  (2023-05-30T06:47:07Z)
• Approximation Rate of the Transformer Architecture for Sequence Modeling [18.166959969957315]
  We consider a class of non-linear relationships and identify a novel notion of complexity measures to establish an explicit Jackson-type approximation rate estimate for the Transformer. This rate reveals the structural properties of the Transformer and suggests the types of sequential relationships it is best suited for approximating.
  arXiv  Detail & Related papers  (2023-05-29T10:56:36Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  We mathematically analyze the power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-sequence functions. We present a negative result by showing there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. We develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions.
  arXiv  Detail & Related papers  (2022-05-26T14:51:30Z)
• Iterative Decoding for Compositional Generalization in Transformers [5.269770493488338]
  In sequence-to-sequence learning, transformers are often unable to predict correct outputs for even marginally longer examples. This paper introduces iterative decoding, an alternative to seq2seq learning. We show that transfomers trained via iterative decoding outperform their seq2seq counterparts on the PCFG dataset.
  arXiv  Detail & Related papers  (2021-10-08T14:52:25Z)
• I-BERT: Inductive Generalization of Transformer to Arbitrary Context Lengths [2.604653544948958]
  Self-attention has emerged as a vital component of state-of-the-art sequence-to-sequence models for natural language processing. We propose I-BERT, a bi-directional Transformer that replaces positional encodings with a recurrent layer.
  arXiv  Detail & Related papers  (2020-06-18T00:56:12Z)
• Applying the Transformer to Character-level Transduction [68.91664610425114]
  The transformer has been shown to outperform recurrent neural network-based sequence-to-sequence models in various word-level NLP tasks. We show that with a large enough batch size, the transformer does indeed outperform recurrent models for character-level tasks.
  arXiv  Detail & Related papers  (2020-05-20T17:25:43Z)

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.