On Rank-Dependent Generalisation Error Bounds for Transformers
This work provides incremental theoretical improvements for researchers in machine learning theory, specifically in understanding transformer generalization.
The paper tackles the problem of deriving generalization error bounds for single-layer transformers by introducing covering number bounds for linear function classes based on matrix rank constraints, resulting in an improved bound of O(1/√n) that is independent of input sequence length and decays with rank.
In this paper, we introduce various covering number bounds for linear function classes, each subject to different constraints on input and matrix norms. These bounds are contingent on the rank of each class of matrices. We then apply these bounds to derive generalization errors for single layer transformers. Our results improve upon several existing generalization bounds in the literature and are independent of input sequence length, highlighting the advantages of employing low-rank matrices in transformer design. More specifically, our achieved generalisation error bound decays as $O(1/\sqrt{n})$ where $n$ is the sample length, which improves existing results in research literature of the order $O((\log n)/(\sqrt{n}))$. It also decays as $O(\log r_w)$ where $r_w$ is the rank of the combination of query and and key matrices.