Spectrum-Adaptive Generalization Bounds for Trained Deep Transformers

Technical Summary: Spectrum-Adaptive Generalization Bounds for Trained Deep Transformers

Problem Statement
Understanding why heavily overparameterized Transformers generalize well remains a fundamental challenge in modern machine learning theory. While existing norm-based generalization bounds (e.g., Edelman et al., 2022; Trauger and Tewari, 2024) have successfully removed explicit polynomial dependence on hidden dimensions and token lengths, they suffer from two primary limitations when applied to deep, trained models:

1. Depth Accumulation: They often exhibit unfavorable exponential or high-polynomial dependence on network depth ($L$) due to layerwise propagation factors (scaling as $C^L$ or $L^{3/2}$).
2. Fixed Norm Constraints: They rely on fixed norm radii (e.g., mixed $(2,1)$ or $(1,1)$ norms) specified a priori. These radii typically grow with the hidden dimension ($N$) and fail to adapt to the heterogeneous spectral profiles observed in trained weights, where attention matrices often exhibit low-rank structures distinct from feedforward matrices.

Methodology
The authors derive spectrum-adaptive post hoc generalization bounds for multi-layer Transformers. The core methodological innovations include:

• Post Hoc Adaptivity: Unlike traditional bounds where complexity parameters are fixed before training, this approach allows the Schatten indices ($p$) to be selected after observing the trained weights. These indices can be chosen separately for each matrix type (Query-Key, Value, Feedforward) and each layer.
• Parametric Interpolation: The paper extends parametric interpolation techniques (Ledent et al., 2025) to matrix-valued function classes. By decomposing weight matrices into a low-rank leading part and a Frobenius-controlled tail, the authors derive covering number bounds that interpolate between rank-based ($p=0$) and norm-based ($p=2$) regimes.
• Spectral Complexity Measures: The bounds are expressed in terms of layerwise Schatten $p$-quantities ($\|W\|_{s,p}$) and spectral norms ($\|W\|_2$). The complexity measure is defined as an infimum over all admissible Schatten indices $p \in [0, 2]^{3L}$.
• Covering Number Analysis: The proof constructs covering numbers for the Transformer architecture under the $\|\cdot\|_{2\to\infty}$ metric. It utilizes a dyadic peeling argument over realized Schatten-quantity radii to ensure the high-probability event holds uniformly over all choices of $p$, enabling the post hoc selection.

Key Contributions

1. Theorem 3.1 (Spectrum-Adaptive Bounds): The primary result provides a generalization gap bound where the complexity term involves an infimum over Schatten indices. This allows the bound to automatically select the most favorable trade-off between spectral complexity, hidden dimension, and depth for each specific learned matrix.
2. Theorem 4.1 (Matrix-Valued Parametric Interpolation): A technical extension providing covering number bounds for linear matrix-valued functions under simultaneous spectral norm and Schatten-quantity constraints. This serves as the building block for the Transformer analysis.
3. Theoretical Comparison: The paper demonstrates that in representative regimes (Frobenius, Rank, and Spectral norm constraints), the proposed bounds improve the dependence on depth compared to existing norm-based baselines. Specifically, the depth dependence improves from $L^{3/2}$ (in Edelman et al., 2022) to $\sqrt{L}$ or better, depending on the spectral structure.
4. Empirical Validation: Using BERT Miniatures checkpoints, the authors construct "BERT-adapted proxies" for the leading complexity factors. They observe that the proxies derived from their spectrum-adaptive bounds grow significantly more slowly with increasing depth ($L$) and hidden dimension ($N$) compared to the proxies derived from Edelman et al. (2022).

Results

• Depth and Dimension Scaling: Theoretical analysis shows that by selecting smaller $p$ (closer to rank), the layerwise propagation factor and polynomial depth factors are reduced. Empirical results on BERT checkpoints confirm that the leading complexity factors of the proposed bounds scale more favorably than norm-based counterparts as $L$ and $N$ increase.
• Heterogeneity of Weights: The empirical analysis reveals that while attention-related matrices (Query-Key, Value) are exactly low-rank (due to head dimension constraints), feedforward matrices exhibit slower spectral decay. However, even for these matrices, the post hoc selection of $p=0$ (rank-based) often yields the tightest bound because the reduction in the spectral term outweighs the penalty from architectural scaling factors.
• Token Length Dependence: The bounds retain a logarithmic dependence on token length ($T$), consistent with recent advances, though the paper notes this arises from the $\ell_2$-type covering argument used for the spectral approach, contrasting with the $\ell_1$-type arguments used to remove token dependence in other works.

Significance and Claims
The paper claims to provide a complexity-based perspective on how the spectral structure of trained Transformers is reflected in generalization analyses. Its significance lies in:

• Adaptivity: Moving beyond fixed, global norm constraints to allow complexity measures that adapt to the specific singular-value profiles of trained weights.
• Interpolation: Offering a theoretical bridge between rank-based and norm-based regimes, demonstrating that the optimal complexity measure is data-dependent and can be selected post hoc.
• Tighter Bounds for Deep Models: Providing a mechanism to mitigate the loose bounds often associated with deep networks by exploiting the low-rank or compressible nature of learned representations.

The authors modestly note that their analysis is training-agnostic, relying only on post hoc spectral quantities rather than the optimization trajectory or implicit regularization. They suggest that future work could integrate data-dependent activation structures and optimization dynamics for even sharper bounds.