# Sequence Length Independent Norm-Based Generalization Bounds for
Transformers

Jacob Trauger
Department of Statistics
University of Michigan
<EMAIL_ADDRESS>&Ambuj Tewari
Department of Statistics
University of Michigan
<EMAIL_ADDRESS>
###### 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.

##  1 INTRODUCTION

Since Vaswani et al., (2017) debuted the Transformer, it has become one of the
most preeminent architectures of its time. It has achieved state of the art
prediction capabilities in various fields (Dosovitskiy et al.,, 2020; Wu et
al.,, 2022; Vaswani et al.,, 2017; Pettersson and Falkman,, 2023) and an
implementation of it has even passed the BAR exam (Katz et al.,, 2023). With
such widespread use, the theoretical underpinnings of this architecture are of
great interest.

Specifically, this paper is concerned with bounding the generalization error
when using the Transformer in supervised learning. Upper bounding this can be
used to help understand how sample size needs to scale with different
architecture parameters and is a very common theoretical tool to understand
machine learning algorithms (Kakade et al.,, 2008; Garg et al.,, 2020;
Truong,, 2022; Lin and Zhang,, 2019).

The main contribution of this paper is providing norm-based generalization
bounds for the Transformer architecture that have no explicit dependence on
input sequence length. Previously, the best known norm-based generalization
bound scaled with the logarithm of the sequence length (Edelman et al.,,
2022). Removing the dependence on sequence length leads to more intuitively
appealing bounds since the total number of parameters in the Transformer is
independent of input sequence length. Since our bounds are norm-based they
have potential to provide meaningful guarantees even in overparameterized
regimes where parameter counting bounds might be less meaningful.

We are able to show this by going through the Rademacher complexity of the
Transformer and then using three novel linear covering number bounds to bound
the Rademacher complexity. Therefore, Section 1 goes over the necessary
background needed. Section 2 shows the novel covering number bounds for a
linear transformation function class with bounded matrices and inputs. In
Section 3 we start dealing specifically with Transformers. Here we show a new
Rademacher complexity bound for a single layer Transformer. Section 4 provides
details on how our covering number bounds can be used in the multi-layer
analysis of Edelman et al., (2022) to get a sequence length independent norm-
based generalization bound. Section 5 shows how a method of training used in
BERT (Devlin et al.,, 2018) can be reduced to what is studied in this paper.
Finally, in Section 7 we show an experiment on a simulated sparse majority
data set to empirically validate our theoretical findings.

###  1.1 Related works

This paper is most closely related to the work of Edelman et al., (2022) who
prove a norm-based generalization bound that grows logarithmically with
sequence length. Due to this, they state Transformers have an inductive bias
to represent a sparse function of the inputs. We bolster this claim further by
removing the dependence on sequence length altogether.

Another result similar to our is given by Zhang et al., (2022). They are able
to remove the dependence on sequence length. However, the bound they get,
which we shall call a parameter counting-based bound, has several drawbacks
which we discuss in Section 2.5. Wei et al., (2022) also show generalization
bounds for Transformers, but specifically study binary classification setting
with $0$-$1$ loss and use a margin approach. Fu et al., (2023) freeze some of
the weight matrices at initialization and bound the excess risk in this
setting as a function of the amount of heads in the attention layer. This
paper’s bound also do not depend on sequence length.

Outside of Transformers, using Rademacher complexity in deep learning to bound
the generalization gap has a rich history. Golowich et al., (2018) was able to
use Rademacher complexities to get a generalization bound independent of the
depth and width of a neural network. Truong, (2022) is able to use Rademacher
complexity to get nearly tight bounds on neural networks under some
assumptions on the data. Also, Bartlett et al., (2017) use covering numbers
and Rademacher complexity to get generalization bounds on multiclass neural
networks using a margin based approach.

##  2 BACKGROUND

###  2.1 Matrix Definitions

First, we will define a few well-used matrix norms. Let $p,q,r,d\in\mathbb{N}$
and let $W\in\mathbb{R}^{r\times d}$. The first norm, denoted as $\left\lVert
W\right\rVert_{q,p}$, will be defined as $\left\lVert
W\right\rVert_{q,p}=\left\lVert[\left\lVert
W_{:,1}\right\rVert_{q},\dots\left\lVert
W_{:,d}\right\rVert_{q}]^{T}\right\rVert_{p}$ where $W_{:,i}$ is the
$i^{\text{th}}$ column of $W$.

The second, also known as the operator norm, we will denote as $\left\lVert
W\right\rVert_{q\rightarrow p}$. This one is defined as:

$\left\lVert W\right\rVert_{q\rightarrow p}=\sup\frac{\left\lVert
Wx\right\rVert_{p}}{\left\lVert x\right\rVert_{q}}$

One final matrix norm we will review is the Frobenius norm, denoted as
$\left\lVert W\right\rVert_{F}$, which is defined as:

$\left\lVert W\right\rVert_{F}=\sqrt{\sum_{i=1}^{r}\sum_{j=1}^{d}W_{ij}^{2}}$

We will also denote $\left\lVert W\right\rVert_{2\rightarrow 2}$ as
$\left\lVert W\right\rVert_{2}$. A well known property of the
$\left\lVert\cdot\right\rVert_{2\rightarrow 2}$ operator is that it is equal
to the largest singular value of the input matrix. The Frobenius norm is also
well known to be equal to the the square root of the squared sum of the
singular values of a matrix. Therefore, we have $\left\lVert
W\right\rVert_{2\rightarrow 2}\leq\left\lVert W\right\rVert_{F}$ for any
matrix $W$.

###  2.2 Generalization Bounds

When training machine learning algorithms, we can only use a finite amount of
data to learn from, however, we want our resulting function to generalize well
outside of our training sample. Thus, having guarantees with high probability
on the difference between the loss on our training sample and the loss on our
testing population is extremely important. Generalization bounds try to upper
bound this loss gap.

Mathematically, if we have a hypothesis class $\mathcal{H}$, sample space
$\mathcal{X}$, label space $\mathcal{Y}$, loss function $\ell$, and
distribution over the sample and label space $\mathcal{D}$, then our
generalization gap for a set of samples and labels
$S=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, $x_{i}\in\mathcal{X}$,
$y_{i}\in\mathcal{Y}$, on the hypothesis $h\in\mathcal{H}$ is defined to be

$\left|\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\ell(h(x),y)\right]-\frac{1}{n}\sum_{i=1}^{n}\ell(h(x_{i}),y_{i})\right|$

Notice how if we can have this value go to 0 with high probability over all
sets of samples and for all $h\in\mathcal{H}$, then we can be confident that
minimizing the sample loss will not impact our generalization.

###  2.3 Rademacher Complexity

One such tool that can be used to upper bound the generalization gap is the
Rademacher complexity. Let us have the same set up as in the previous section.
Then the Rademacher complexity of a hypothesis class $\mathcal{H}$ is defined
to be

$Rad_{n}(\mathcal{H},S)=\frac{1}{n}\mathbb{E}_{\sigma}\left[\sup_{h\in\mathcal{H}}\sum_{i=1}^{n}\sigma_{i}h(x_{i})\right]$

where each $\sigma_{i}$ are i.i.d. and take values $\pm 1$ each with half
probability and $\sigma=(\sigma_{1},\dots,\sigma_{n})$. It is well known that
(Shalev-Shwartz and Ben-David,, 2014), if the magnitude of our loss function
is bounded above by $c$, with probability greater than $1-\delta$ for all
$h\in\mathcal{H}$, we have

$\displaystyle\left|\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\ell(h(x),y)\right]-\frac{1}{n}\sum_{i=1}^{n}\ell(h(x_{i}),y_{i})\right|\leq$
$\displaystyle
2Rad_{n}(\ell\circ\mathcal{H},S)+4c\sqrt{\frac{2\log(4/\delta)}{m}}$

where
$\ell\circ\mathcal{H}=\\{\ell(h(x),y)\mid(x,y)\in\mathcal{X}\times\mathcal{Y},h\in\mathcal{H}\\}$.
Therefore, if we have an upper bound on the Rademacher complexity, we can have
an upper bound on the generalization gap.

###  2.4 Covering Numbers

The use of covering numbers is one such way we can bound the Rademacher
complexity of a hypothesis class. Let $q\in\mathbb{R}_{>0}$ and let us have a
function class $\mathcal{F}$, $\forall f\in\mathcal{F}$
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$. We say a subset
$\hat{\mathcal{F}}\subset\mathcal{F}$ covers a set of inputs
$\\{x_{i}\\}_{i=1}^{n}$ if for every $f\in\mathcal{F}$,
$\exists\hat{f}\in\hat{\mathcal{F}}$ such that $\sup_{x_{i}}\left\lVert
f(x_{i})-\hat{f}(x_{i})\right\rVert_{q}<\epsilon$. We will use the notation
$N_{\infty}(\mathcal{F},\epsilon,\\{x_{i}\\}_{i=1}^{n},\left\lVert\cdot\right\rVert_{q})$
for this. We will define the covering number,
$N_{\infty}(\mathcal{F},\epsilon,n,\left\lVert\cdot\right\rVert_{q})$ as

$\sup_{\\{x_{i}\\}_{i=1}^{n}}N_{\infty}(\mathcal{F},\epsilon,\\{x_{i}\\}_{i=1}^{n},\left\lVert\cdot\right\rVert_{q})$

It has been shown that for scalar valued hypothesis classes, the Rademacher
complexity can be upper bounded using the covering number of the hypothesis
class (Dudley,, 1967). Using a slightly modified version, we have for a
constant $c$:

$Rad_{n}(f,S)\leq c\inf_{\delta\geq
0}\left(\delta+\int_{\delta}^{\infty}\sqrt{\frac{\log
N_{\infty}(\mathcal{F},\epsilon,n)}{n}}d\epsilon\right)$

Notice that if we have a bounded function class, then the $\infty$ in the
integral limit can become the upper bound of the function class.

###  2.5 Two Types of Bounds

Suppose our inputs have dimension $d$ and the inputs have an upper norm bound
of $B_{x}$. Suppose our matrices have dimension $k\times d$ and have an upper
norm bound of $B_{w}$. Here we will note two different types of generalization
bounds that can one can arrive at depending on the perspective. One is where
you have the norm bounds inside a log term and the dimensions on the outside
(e.g., $O(\sqrt{dk\log(B_{x}B_{w}))/n}$). The other is where you have the
bounds outside the log term and parameters inside (e.g.,
$O(\sqrt{B_{x}B_{w}\log(dk))/n}$). We will refer to the former as parameter-
counting type bounds and the latter as the norm-based type bounds. We note
that these are not the only types of bounds, just these are the ones relevant
to this paper.

Notice how, for parameter counting bounds, over-parameterized architectures
can lead to vacuous bounds. Also notice that parameter counting bounds do not
take full advantage of SGD’s implicit regularization since the norms are
within the logarithm. In contrast, as long as the norm bounds are reasonable,
norm-based generalization bounds work well with over-parameterized
architectures and work well with implicit regularization.

For Transformers, there are norm-based bounds that scale logarithmically with
sequence length (Edelman et al.,, 2022) and parameter counting bounds that do
not scale with sequence length (Zhang et al.,, 2022). This is a gap in the
literature which this paper intends to fill.

###  2.6 Self-Attention and Transformers

We will follow the definition of self-attention and Transformers set forth by
Edelman et al., (2022) and keep with their notation.

Let $X\in\mathbb{R}^{T\times d}$ be the input and $W_{c}\in\mathbb{R}^{k\times
d}$, $W_{v}\in\mathbb{R}^{d\times k}$, and $W_{Q},W_{K}\in\mathbb{R}^{d\times
T}$ be trainable weight matrices. Also, let $\sigma$ be a $L_{\sigma}$
Lipshitz activation function that is applied elementwise and has the property
$\sigma(0)=0$. Finally, let RowSoftmax donote running softmax on each row of
its input. Then, they define a Transformer head as

$\sigma\left(\text{RowSoftmax}\left(XW_{Q}W_{K}^{T}X^{T}\right)XW_{v}\right)W_{c}$

Since $W_{Q}$ and $W_{K}$ are only ever multiplied with each other, we will
combine $W_{Q}W_{K}^{T}$ into a single matrix $W_{QK}\in\mathbb{R}^{d\times
d}$ for convenience of analysis. Once we do this, note that the total
dimensionality (of $W_{QK},W_{c},W_{v}$) is independent of $T$, the sequence
length which counts how many values are in each sample. The embedding
dimension is $d$ since it is the dimension that the values in the sequence are
embedded into and $k$ is the hidden dimension.

For multi-head Transformers, we assume each head is summed up at the end of
each layer. That is, the output for a layer of a multi-head Transformer is:

$\sum_{h=1}^{H}\sigma\left(\text{RowSoftmax}\left(XW_{h,Q}W_{h,K}^{T}X^{T}\right)XW_{h,v}\right)W_{h,c}$

Note how the ouput of a layer can be used as the input to another layer. This
is how multi-layer Transformer networks are created. Standard practice is to
add layer normalization in between each layer as this has been well studied to
aid in optimization and generalization (Ba et al.,, 2016; Wang et al.,, 2019;
Xu et al.,, 2019). Thus, keeping with the definitions and notation previously
set forth, we will inductively define an $L$-layer Transformer block:

Let $\mathcal{W}^{(i)}=\\{W_{v}^{(i)},W_{c}^{(i)},W_{QK}^{(i)}\\}$ and let
$\mathcal{W}^{1:i}=\\{\mathcal{W}^{1},\dots\mathcal{W}^{(i-1)}\\}$. Also, let

$f(X;W^{(i)})=\sigma\left(\text{RowSoftmax}\left(XW_{Q}W_{K}^{T}X^{T}\right)XW_{v}\right)$
$g_{block}^{1}\left(X;W^{1:1}\right)=X$

Then, the output of the $i^{\text{th}}$ layer is defined to be

$\displaystyle g_{block}^{(i+1)}\left(X;W^{1:i+1}\right)=$
$\displaystyle\Pi_{norm}\left(\sigma\left(\Pi_{norm}\left(f\left(g_{block}^{(i)}\left(X;W^{1:i}\right);W^{(i)}\right)\right)\right)W_{c}^{(i)}\right)$

where $\Pi_{norm}$ projects each row onto the unit ball.

In our analysis we will focus on the scalar output setting for Transformers.
Specifically, we will follow how BERT is trained (Devlin et al.,, 2018). In
order to get a scalar output, we add an extra input in the sequence that can
be constant or trained. Let this index be the $[CLS]$ index. Let us also have
a trainable vector $w\in\mathbb{R}^{d}$. Then, at the last layer, take the
output at the $[CLS]$ index, $Y_{[CLS]}\in\mathbb{R}^{d}$, and we multiply it
with $w$ to get our output $w^{T}Y_{[CLS]}\in\mathbb{R}$.

##  3 LINEAR COVERING NUMBER BOUNDS

In this section we will show three different covering number bounds for linear
function classes with different restrictions on input and matrix norms. To
show the first one, we need the following lemmas, the first one is attributed
to Maurey (Pisier,, 1981) and first used in this context by Zhang, (2002):

######  Lemma 3.1.

(Maurey’s Sparsification Lemma) Let $\mathcal{H}$ be a Hilbert space and let
each $f\in\mathcal{H}$ have the representation
$f=\sum_{i=1}^{d}\alpha_{i}V_{i}$ where $V_{i}\in\mathcal{H}$, $\left\lVert
V_{i}\right\rVert\leq b$ and $\alpha_{i}\geq 0$ with
$\gamma=\left\lVert\alpha\right\rVert_{1}\leq 1$. Then, for any
$k\in\mathbb{N}$, there exist $k_{1},\dots,k_{d}$, $k_{i}\in\mathbb{Z}_{\geq
0}$, $\sum_{i=1}^{d}k_{i}\leq k$, such that

$\left\lVert
f-\frac{1}{k}\sum_{i=1}^{d}k_{i}V_{i}\right\rVert_{2}^{2}\leq\frac{\gamma^{2}b^{2}-\left\lVert
f\right\rVert^{2}}{k}$

We note that the total amount of $(k_{1},\dots k_{d})$’s that fit the criteria
above is less than or equal to $d^{k}$. This has been used to upper bound the
covering number for linear functions (Zhang,, 2002; Bartlett et al.,, 2017)
and we will use it similarly in our proofs.

For covering a class of scalar valued linear functions $\\{x\rightarrow
w^{\top}x\mid w\in\mathbb{R}^{d},$w$\text{ norm bounded}\\}$ with inputs
$\\{x_{i}\in\mathbb{R}^{d}\\}_{i=1}^{n}$, it is known that we are able to
remove the dependence on $n$ and replace it with a dependence on $d$.
Kontorovich and Attias, (2021) show this and attribute it to folklore. Given a
cover such as this, it is an immediate extension to create a non-$n$-dependent
cover of the function class $\\{x\rightarrow Wx,W\in\mathcal{W}\\}$ as long as
each row in each $W\in\mathcal{W}$ is bounded by the norm restraint needed for
the scalar valued cover (specific details are in appendix section A).

The next lemma generalizes the above by allowing us to consider more possible
norm bounds on $\mathcal{W}$. It shows that under certain norm restrictions
for our input, the linear transformation covering number for any set of size
$N$ is equivalent to the covering number on the appropriately scaled standard
basis (proof in appendix section B).

######  Lemma 3.2.

Let $\mathcal{W}\subset\mathbb{R}^{k\times d}$ and let
$\mathcal{F}=\\{x\rightarrow Wx\mid W\in\mathcal{W}\\}$ with $\left\lVert
x\right\rVert_{1}\leq B_{x}$. Then, for $N\geq d$, we have

$\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{q}\right)=\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,\\{B_{x}e_{1},\dots,B_{x}e_{d}\\},\left\lVert\cdot\right\rVert_{q}\right)$

###  3.1 Log Covering Number For $\left\lVert\cdot\right\rVert_{1}$ Bounded
Input and $\left\lVert\cdot\right\rVert_{1,\infty}$ Bounded Matrix

Now, we will show our three covering number bounds. Each of the three have
different norm bounds on the inputs and the matrices, allowing for flexibility
when deciding which to use.

######  Lemma 3.3.

Let $N\geq d$, $\mathcal{W}=\\{W\in\mathbb{R}^{k\times d}\mid\left\lVert
W\right\rVert_{1,\infty}\leq B_{w}\\}$, $\mathcal{F}=\\{x\rightarrow Wx\mid
W\in\mathcal{W}\\}$, and let our inputs $x\in\mathbb{R}^{d}$ have the
restriction $\left\lVert x\right\rVert_{1}\leq B_{x}$. Then:

$\log\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{2}\right)\leq\frac{dB_{w}^{2}B_{x}^{2}}{\epsilon^{2}}\log(2k+1)$

###### Proof.

We will abuse notation slightly by referring to $\mathcal{W}$ at times instead
of $\mathcal{F}$ (and similar for $\hat{\mathcal{W}}$ and
$\hat{\mathcal{F}}$).

Let us have the set $V=\\{v\in\mathbb{R}^{k}\mid\left\lVert
v\right\rVert_{1}\leq B_{w}\\}$. Then notice by lemma 3.1 we have that there
exists an $\epsilon/B_{x}$ cover for $V$ that has log size

$\frac{B_{w}^{2}B_{x}^{2}}{\epsilon^{2}}\log(2k+1)$

Let this cover be $\hat{V}$. We claim that

$\hat{\mathcal{W}}=\underbrace{\hat{V}\otimes\hat{V}\dots\otimes\hat{V}}_{\text{$d$
total times}}$

is a cover for $\mathcal{W}$.

To show this, let $W\in\mathcal{W}$ and let $\hat{W}\in\hat{\mathcal{W}}$ be
the one where each column is the vector that would be chosen to cover the
corresponding column in $W$. Then, notice for all $i\in[d]$ we have

$\left\lVert(W-\hat{W})B_{x}e_{i}\right\rVert=B_{x}\left\lVert
W_{:,i}-\hat{W}_{:,i}\right\rVert\leq B_{x}\frac{\epsilon}{B_{x}}=\epsilon$

Therefore

$\sup_{i\in[d]}\left\lVert(W-\hat{W})B_{x}e_{i}\right\rVert\leq\epsilon$

which, by lemma 3.2 shows that

$\log\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{2}\right)\leq\frac{dB_{w}^{2}B_{x}^{2}}{\epsilon^{2}}\log(2k+1)$

∎

###  3.2 Log Covering Number For $\left\lVert\cdot\right\rVert_{1}$ Bounded
Input and $\left\lVert\cdot\right\rVert_{2,1}$ Bounded Matrix

######  Lemma 3.4.

Let $N>d$, $\mathcal{W}=\\{W\in\mathbb{R}^{k\times d}\mid\left\lVert
W\right\rVert_{2,1}\leq B_{w}\\}$, $\mathcal{F}=\\{x\rightarrow Wx\mid
W\in\mathcal{W}\\}$, and let our inputs $x\in\mathbb{R}^{d}$ have the
restriction $\left\lVert x\right\rVert_{1}\leq B_{x}$. Then:

$\log\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{2}\right)\lesssim\frac{B_{w}^{2}B_{x}^{2}}{\epsilon^{2}}\log(dk)$

where $\lesssim$ hides logarithmic dependencies except $T,k,d$.

###### Proof.

This proof uses Lemma 4.6 in Edelman et al., 2022 Edelman et al., (2022),
which is rewritten below for clarity.

######  Lemma 3.5.

(Edelman et al., 2022 Lemma 4.6) Let $\mathcal{W}$ and $\mathcal{F}$ be as
above. Then for any set of points $x_{1},\dots,x_{n}\in R^{d}$ with
$\left\lVert x_{i}\right\rVert_{2}\leq B_{x}$ for all $i$, we have

$\log\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,\\{x_{i}\\}_{i=1}^{n},\left\lVert\cdot\right\rVert_{2}\right)\lesssim\frac{B_{w}^{2}B_{x}^{2}}{\epsilon^{2}}\log(dn)$

With this, let $\hat{\mathcal{W}}$ be an $\epsilon$-cover for $\mathcal{W}$
over the inputs $\\{B_{x}e_{i}\\}_{i=1}^{d}$ as stated in the lemma. Then, by
lemma 3.2, we have that the cardinality of $\hat{\mathcal{W}}$ is also an
upper bound for
$\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{2}\right)$,
which is what we needed to show. ∎

###  3.3 Log Covering Number For $\left\lVert\cdot\right\rVert_{2}$ Bounded
Input and $\left\lVert\cdot\right\rVert_{1,1}$ Bounded Matrix

######  Lemma 3.6.

Let $N\geq d$, $\mathcal{W}=\\{W\in\mathbb{R}^{k\times d}\mid\left\lVert
W\right\rVert_{1,1}\leq B_{w}\\}$, $\mathcal{F}=\\{x\rightarrow Wx\mid
W\in\mathcal{W}\\}$, and let our inputs $x\in\mathbb{R}^{d}$ have the
restriction $\left\lVert x\right\rVert_{2}\leq B_{x}$. Then:

$\log\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{2}\right)\leq\frac{B_{x}^{2}B_{w}^{2}}{\epsilon^{2}}\log(2dk+1)$

###### Proof.

Let $\mathcal{V}$ be the set of all the flatten matrices in $\mathcal{W}$.
Note how this implies $\forall v\in\mathcal{V}$, we have $\left\lVert
v\right\rVert_{1}\leq B_{w}$. Then, by Maurey’s sparification lemma, we have
that there exists an $\epsilon$-cover $\hat{\mathcal{V}}$ of log size at most
$\frac{B_{w}^{2}}{\epsilon^{2}}\log(2dk+1)$. We claim if we unflatten
$\hat{\mathcal{V}}$ (call this $\hat{\mathcal{W}}$), then $\hat{\mathcal{W}}$
is a $(B_{x}\epsilon)$-cover for $\mathcal{W}$. Let $W\in\mathcal{W}$, let $V$
be the flatten version of $W$. Then, let $\hat{V}$ be the flattened vector we
would choose for $V$ in our cover and let $\hat{W}\in\hat{\mathcal{W}}$ be the
unflattened version of $\hat{V}$. Notice for any $x\in\mathbb{R}^{d}$,
$\left\lVert x\right\rVert_{2}\leq B_{x}$:

$\displaystyle\left\lVert Wx-\hat{W}x\right\rVert_{2}\leq\left\lVert
W-\hat{W}\right\rVert_{2\rightarrow 2}\left\lVert x\right\rVert_{2}\leq$
$\displaystyle\left\lVert W-\hat{W}\right\rVert_{F}\left\lVert
x\right\rVert_{2}=\left\lVert V-\hat{V}\right\rVert_{2}\left\lVert
x\right\rVert_{2}\leq$ $\displaystyle\left\lVert
V-\hat{V}\right\rVert_{2}B_{x}\leq B_{x}\epsilon$

Therefore our covering number is at most
$\frac{B_{x}^{2}B_{w}^{2}}{\epsilon^{2}}\log(2dk+1)$ ∎

###  3.4 Observations on Results

Above we have showed a few different sharpenings of linear covering numbers
with matrices instead of vectors. Specifically, these do not rely on the
sample size of the input. Also, all but lemma 3.3 keeps the matrix dimensions
inside the log term. We do note however, the matrix bound in lemma 3.3 is a
$1,\infty$ norm bound while the others are rather $2,1$ or $1,1$ norm bound.
We know that for any matrix $W$, $\left\lVert W\right\rVert_{p,1}\leq
d\left\lVert W\right\rVert_{p,\infty}$. Thus if we were to convert lemmas 3.4
and 3.6 into a norm bound on $2,\infty$ and $1,\infty$ bounds we would have a
$d^{2}B_{w}^{2}$ term. This shows that lemma 3.3 is a stronger bound than it
lets on.

##  4 TRANSFORMER RADEMACHER COMPLEXITY

###  4.1 Analysis for Single Layer Transformer

Let $w\in R^{d}$, $W_{c}\in\mathbb{R}^{k\times d}$,
$W_{v}\in\mathbb{R}^{d\times k}$, $W_{QK}\in\mathbb{R}^{d\times d}$
$\left\lVert w\right\rVert_{1}\leq B_{w}$, $\left\lVert
W_{c}^{T}\right\rVert_{1,\infty}\leq B_{W_{c}}$, and $\left\lVert
W_{v}^{T}\right\rVert_{1,\infty}\leq B_{W_{v}}$. Then we have our scalar one
layer Transformer as $w^{T}Y_{[CLS]}$ where

$Y_{[CLS]}=W_{c}^{T}\sigma\left(W_{v}^{T}X^{T}\text{softmax}\left(XW_{QK}^{T}x_{[CLS]}\right)\right)$

Our Rademacher complexity is thus the following:

$\mathbb{E}\left[\sup_{w,W_{c},W_{v},W_{QK}}\sum_{i=1}^{m}\epsilon_{i}w^{T}W_{c}^{T}\sigma\left(W_{v}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right)\right]$

With this, we have the following theorem:

######  Theorem 4.1.

Suppose we have a log covering number in the form of $C/\epsilon^{2}$ for the
function class $\\{x\rightarrow Wx\mid x\in\mathcal{X},w\in\mathcal{W}\\}$
where $\left\lVert x\right\rVert_{\infty}<B_{x}$ $\forall x\in\mathcal{X}$.
Suppose we also have the norm restrictions above, have $W_{QK}$ meet the
covering norm restrictions, and have $m>d$ and $m>\ln(2d)$. Then, an upper
bound on the Rademacher complexity of a single layer Transformer layer is:

$\displaystyle
O\left(B_{w}B_{W_{c}}L_{\sigma}B_{W_{v}}\left(\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}\left(1+\ln\left(\frac{\sqrt{m}}{2B_{x}\sqrt{C}}\right)\right)+B_{x}\sqrt{\frac{\ln(2d)}{m}}\right)\right)$

The proof is left in appendix section C for ease of presentation.

We can now take lemmas 3.3, 3.4, and 3.6 to get bounds on the Rademacher
complexity. In the proof it can be seen the only matrix that needs to be
covered in $W_{QK}$, thus we will only have a dependence on $d$ and not $k$.
We will show one corollary below and leave the rest to appendix section D.

######  Corollary 4.1.1.

Let us have the requirements needed for Theorem 4.1 along with $\left\lVert
x\right\rVert_{2}\leq B_{x}$ and $\left\lVert W_{QK}\right\rVert_{1,1}\leq
B_{W_{QK}}$ Let

$B=B_{w}B_{W_{c}}L_{\sigma}B_{W_{v}}$

and let

$\alpha=B_{W_{QK}}\sqrt{2\log(2d^{2}+1)}$

Then we have our Transformer Rademacher complexity being less than

$\displaystyle
O\left(B\left(\frac{B_{x}^{3}\alpha}{\sqrt{m}}\left(1+\ln\left(\frac{\sqrt{m}}{B_{x}^{2}\alpha}\right)\right)+B_{x}\sqrt{\frac{\ln(2d)}{m}}\right)\right)$

###  4.2 Single Layer Multiple Heads

Let $H\in\mathbb{N}$ and let $Y_{i}$, $i\in[H]$ each be a Transformer head.
Then notice by linearity of expectation:

$\mathbb{E}\left[\sup_{Y_{1},\dots,Y_{H}}\sum_{i=1}^{m}\epsilon_{i}w^{T}\sum_{j=1}^{H}Y_{j}\right]=\sum_{j=1}^{H}\mathbb{E}\left[\sup_{Y_{j}}\sum_{i=1}^{m}\epsilon_{i}w^{T}Y_{j}\right]$

The expectation above is the same as the single layer, thus multiple heads
just adds a linear $H$ term to the Rademacher complexity.

###  4.3 Multiple Layers

We have seen that we are able to get sequence length independent Rademacher
complexities (and therefore generalization bounds) for a single layer
Transformer architecture. For multiple layers, it suffices to take the proof
found in Edelman et al., (2022) and slightly rework it so that it will work
for an arbitrary linear covering number bound.

######  Theorem 4.2.

(Slight Reworking of Theorem A.17 in Edelman et al., 2022) Suppose we have a
log covering numbers in the form of $C_{1}/\epsilon^{2}$ and
$C_{B_{x}}/\epsilon^{2}$ for the function class $\\{x\rightarrow Wx\mid
x\in\mathcal{X},w\in\mathcal{W}\\}$ where $\left\lVert x\right\rVert_{2}\leq
1$ $\forall x\in\mathcal{X}$ and $\left\lVert x\right\rVert_{2}\leq B_{x}$
$\forall x\in\mathcal{X}$ respectively. Suppose we also have $\left\lVert
W_{c}^{(i)\top}\right\rVert_{2}\leq B_{c2}$, $\left\lVert
W_{v}^{(i)\top}\right\rVert_{2}\leq B_{v2}$, $\left\lVert
W_{QK}^{(i)}\right\rVert_{2}\leq B_{QK2}$, $\left\lVert w\right\rVert\leq
B_{w}$ along with them meeting the needed covering number restrictions. Let

$\displaystyle\alpha_{i}=\prod_{j=i+1}^{L}L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})$
$\displaystyle\tau_{i}=\alpha_{i}^{2/3}+\left(2\alpha_{i}L_{\sigma}B_{c2}B_{v2}\right)^{2/3}+(\alpha_{i}L_{\sigma}B_{v2})^{2/3}$
$\displaystyle\gamma=C_{B_{x}}^{1/3}\left(2L_{\sigma}B_{c2}B_{v2}\alpha_{1}B_{w}\right)^{2/3}+C_{1}^{1/3}\left(1+(B_{w}L_{\sigma}B_{v2})^{2/3}\right)$
$\displaystyle\eta=C_{1}^{1/3}\left(B_{w}^{2/3}\sum_{i=2}^{L}\tau_{i}\right)$

Then, the log covering number of $g_{scalar}^{L+1}$ is

$\displaystyle\frac{(\gamma+\eta)^{3}}{\epsilon^{2}}$

The proof is left in appendix section E for ease of presentation.

Notice this is the covering number of the entire multi-layer Transformer.
Thus, we can recover an upper bound for the Rademacher complexity of it by
using Dudley’s integral.

Substituting our covering number bounds into theorem 4.2 gives us the three
corollaries. We state one below and leave the rest to appendix section F.

######  Corollary 4.2.1.

Suppose we have the norm bounds required in lemma 3.6 for each
$W_{c}^{(i)},W_{v}^{(i)},W_{QK}^{(i)},w$ and let the maximum be $B$. Let
$B_{x}$ be the input bound. Suppose we also have the bounds needed for theorem
4.2. Let

$\displaystyle\alpha_{i}=\prod_{j=i+1}^{L}L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})$
$\displaystyle\tau_{i}=\alpha_{i}^{2/3}+\left(2\alpha_{i}L_{\sigma}B_{c2}B_{v2}\right)^{2/3}+(\alpha_{i}L_{\sigma}B_{v2})^{2/3}$
$\displaystyle\gamma=\left(B^{2}B_{x}^{2}\ln(2dk+1)\right)^{1/3}\left(2L_{\sigma}B_{c2}B_{v2}\alpha_{1}B_{w}\right)^{2/3}+$
$\displaystyle\left(B^{2}\ln(2dk+1)\right)^{1/3}\left(1+(B_{w}L_{\sigma}B_{v2})^{2/3}\right)$
$\displaystyle\eta=\left(B^{2}\ln(2dk+1)\right)^{1/3}\left(B_{w}^{2/3}\sum_{i=2}^{L}\tau_{i}\right)$

Then, the log covering number of $g_{scalar}^{L+1}$ is

$\displaystyle\frac{(\gamma+\eta)^{3}}{\epsilon^{2}}$

The above covering number is precise, but unwieldy to look at. To get a better
sense of it, we can see that, ignoring polylog terms and constants, we get

$B^{2}B_{x}^{2}B_{w}^{2}(L_{\sigma}B_{c2}B_{v2}B_{QK2})^{O(L)}\frac{1}{\epsilon^{2}}$

We do note that the multi-layer method does also work for one layer, however,
they have different norm bounds required so they are not quite comparable. If
we were to look at just the resulting values, the given single layer method
essentially trades the cross product terms in the cubed factor for a factor of
$B_{x}^{2}$, which seems like an acceptable trade. The proof for the single
layer is also much more direct and easy to digest. It also gives a linear
dependence on the amount of heads when the multi-layer method extended to
multiple heads gives a dependence of $H^{1.5}$.

##  5 THEORETICAL EXAMPLE: WORD PREDICTION IN NLP

Suppose we have a word embedding set up and a vocabulary of size $K$. One way
to try to learn is by masking a certain percentage of words in a sentence and
asking the Transformer to predict these words. Masking is done by taking the
row that corresponds to the position of the masked word (let us call this row
$i$) and giving as input a specific vector instead of the actual embedding of
the word. Then the prediction is done by taking the vector in row $i$ in the
final layer of the Transformer and linearly transforming it into a size $K$
vector. Then we can softmax this vector and use cross entropy loss to train.
This is one of the ways BERT (Devlin et al.,, 2018) is trained. Below, we will
suppose only 1 word is masked for each input for ease of presentation. Let us
use the cross entropy loss with softmax:

$\ell_{i}(y,x)=-\sum_{i=1}^{k}y_{i}\log(\text{softmax}\left(x\right))$

where $y\in\\{0,1\\}^{k}$ is a one-hot encoded value that specifies the
correct word and $x\in\mathbb{R}^{k}$ is the output of our Transformer at the
masked index. It turns out this loss function is $\sqrt{2}$-Lipshitz. The
argument comes from the fact the above is differentiable and showing the
squared euclidean norm of its gradient is less than $2$.

Therefore, if we let $W$ be our linear transformation from the Transformer row
to the vocabulary scores, we have by Foster and Rakhlin, (2019):

$\displaystyle\mathbb{E}\left[\sup_{W,Y}\sum_{i=1}^{m}\epsilon_{i}\ell_{i}\left(W(Y_{L}^{(i)})_{\tau}\right)\right]\leq$
$\displaystyle\tilde{\mathcal{O}}(\sqrt{K})\max_{s}\mathbb{E}\left[\sup_{W,Y}\sum_{i=1}^{m}\epsilon_{i}\left(W(Y_{L}^{(i)})_{\tau}\right)_{s}\right]=$
$\displaystyle\tilde{\mathcal{O}}(\sqrt{K})\max_{s}\mathbb{E}\left[\sup_{W_{s},Y}\sum_{i=1}^{m}\epsilon_{i}W_{s}(Y_{L}^{(i)})_{\tau}\right]$

Notice that since $W_{s}\in\mathbb{R}^{d}$, the resulting Rademacher
complexity is of the same form of the scalar problem we found bounds for in
the previous sections. Thus, we can apply those bounds to this set up.

##  6 EMPIRICAL EXAMPLE: SPARSE MAJORITY

The above sections show that, with bounded norms on the weight matrices, our
generalization gap should not grow with sequence length. Thus, in this
section, we will discuss a simulated study to see empirically if we find
results that match our theory. We run a single layer Transformer on a
simulated sparse majority data set on a variety of sequence lengths and we
look at three results: (1) The total $1$-norm of the weights in the
Transformer, (2) The cross entropy generalization gap of the best epoch, (3)
The validation accuracy of the best epoch for each sequence length.

The first two will show whether or not our theoretical findings are found in
practice as well. The last one is more of a practical concern–a situation
where the generalization gap is small but the network does not learn is not
very useful.

The dataset we create is a sequence of zeros and ones where the label is
determined by a majority of a sparse set of the indices. More concretely, if
we have a sequence $S$ of length is $T$, we have a set of indices is $I$,
$|I|<T$, the label is

$y_{i}=\mathbbm{1}_{\left\\{\sum_{i\in I}S_{i}>\frac{|I|}{2}\right\\}}$

In order to more accurately emulate real uses of Transformers, we embed $0$
and $1$ each into a $d$-dimensional vector where these two are orthogonal from
each other. We also add the positional encoding defined by Vaswani et al.,
(2017) to add positional information to the sequence.

For our experiment we used a single layer of Tensorflow’s MultiHeadAttention
layer along with a second layer that extracts the $[CLS]$ layer and linearly
transforms it into a vector of size 2. The loss we use is the cross entropy
loss. Notice how we can use Section 5 to make this fit in the regime we have
been discussing in this paper; we can act as if the $[CLS]$ index is always
masked and we have a vocabulary of size $2$ ($0$ and $1$).

The multihead attention layer has embedding dimension of $64$ and $2$ heads.
The embedding dimension was chosen to be large while still allowing for
moderate computation time. Only two heads was also chosen as well for
computation time concerns. For our dataset, we had the sparse index set
cardinality to $9$ and used $300$ training samples on sequence length $20$,
$40$, $60$, …, $200$ with a validation set size of $10000$. The index set
cardinality and training set size were chosen after finding a small enough
size where the smaller sequence lengths could not always get perfect
validation accuracy.

The Transformer trained on a NVIDIA Tesla V100 GPU for $200000$ epochs with a
batch size of $128$. $200000$ epochs, while a lot, was needed to allow for the
larger sequence lengths to start to overfit. This batch size was also chosen
after trial and error.

We trained our model for each sequence length $5$ times (new data set each
time) and recorded the $1$-norms of the weights, the accuracy, and
generalization gap of the best epoch. Figure 2 shows the worst generalization
gap for each sequence length. Figure 1 shows the largest $1$-norm of the
weights of each sequence length. Figure 3 shows the best accuracy for each
sequence length. We note that each of these do not necessarily represent the
same run per sequence length.

Figure 1: Plot of the max sum of the absolute value of all the weights across
sequence lengths. The lack of any trend further validates our assumption of
bounded weights being credible. Figure 2: Plot of the max generalization gap
across sequence lengths. There is no discernible trend in the plot, giving
empirical validation to our theoretical results Figure 3: Plot of the maximum
accuracy across sequence lengths. While this paper makes no claims on the
accuracy, we can see our accuracy does plateau. Therefore showing it is
learning well at longer sequence lengths.

As we can see, the figure 1 shows that the weights do not increase with
sequence length, lending strength to our matrix norm assumptions.

We can also see in figure 2 the generalization gap also has no discernible
trend and figure 3 shows the accuracy plateaus as sequence length increases.
These results further help validate our theoretical findings that,
surprisingly, large sequence lengths do not seem to affect how well
Transformers learn.

The code for these experiments can be found here.

##  7 CONCLUSION AND FUTURE WORK

In this work, we give norm-based generalization bounds that do not grow with
sequence length. This fills a hole in the literature where we can now have
sequence length independent generalization bounds with the good properties the
norm-based bounds give. We also give empirical evidence to validate our
theoretical assumptions and theorems.

Future work could include sharpening the linear covering number bounds and
generalizing them for more types of matrix/input norm bound combinations.
Another avenue could be analyzing exactly how the norm-based bounds and
parameter counting bounds trade off with each other.

##  8 ACKNOWLEDGEMENTS

This research was supported in part through computational resources and
services provided by Advanced Research Computing at the University of
Michigan, Ann Arbor.

## References

  * Ba et al., (2016) Ba, J. L., Kiros, J. R., and Hinton, G. E. (2016).  Layer normalization.  arXiv preprint arXiv:1607.06450.
  * Bartlett et al., (2017) Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. (2017).  Spectrally-normalized margin bounds for neural networks.  Advances in neural information processing systems, 30.
  * Devlin et al., (2018) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2018).  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805.
  * Dosovitskiy et al., (2020) Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. (2020).  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929.
  * Dudley, (1967) Dudley, R. M. (1967).  The sizes of compact subsets of hilbert space and continuity of gaussian processes.  Journal of Functional Analysis, 1(3):290–330.
  * Edelman et al., (2022) Edelman, B. L., Goel, S., Kakade, S., and Zhang, C. (2022).  Inductive biases and variable creation in self-attention mechanisms.  In International Conference on Machine Learning, pages 5793–5831. PMLR.
  * Foster and Rakhlin, (2019) Foster, D. J. and Rakhlin, A. (2019).  l$\infty$ vector contraction for rademacher complexity.  arXiv preprint arXiv:1911.06468, 6.
  * Fu et al., (2023) Fu, H., Guo, T., Bai, Y., and Mei, S. (2023).  What can a single attention layer learn? a study through the random features lens.  arXiv preprint arXiv:2307.11353.
  * Garg et al., (2020) Garg, V., Jegelka, S., and Jaakkola, T. (2020).  Generalization and representational limits of graph neural networks.  In International Conference on Machine Learning, pages 3419–3430. PMLR.
  * Golowich et al., (2018) Golowich, N., Rakhlin, A., and Shamir, O. (2018).  Size-independent sample complexity of neural networks.  In Conference On Learning Theory, pages 297–299. PMLR.
  * Kakade et al., (2008) Kakade, S. M., Sridharan, K., and Tewari, A. (2008).  On the complexity of linear prediction: Risk bounds, margin bounds, and regularization.  Advances in neural information processing systems, 21.
  * Katz et al., (2023) Katz, D. M., Bommarito, M. J., Gao, S., and Arredondo, P. (2023).  Gpt-4 passes the bar exam.  Available at SSRN 4389233.
  * Kontorovich and Attias, (2021) Kontorovich, A. and Attias, I. (2021).  Fat-shattering dimension of $k$-fold maxima.  arXiv preprint arXiv:2110.04763.
  * Ledoux and Talagrand, (1991) Ledoux, M. and Talagrand, M. (1991).  Probability in Banach Spaces: isoperimetry and processes, volume 23.  Springer Science & Business Media.
  * Lin and Zhang, (2019) Lin, S. and Zhang, J. (2019).  Generalization bounds for convolutional neural networks.  arXiv preprint arXiv:1910.01487.
  * Pettersson and Falkman, (2023) Pettersson, J. and Falkman, P. (2023).  Comparison of lstm, transformers, and mlp-mixer neural networks for gaze based human intention prediction.  Frontiers in Neurorobotics, 17:1157957.
  * Pisier, (1981) Pisier, G. (1981).  Remarques sur un résultat non publié de b. maurey.  Séminaire d’Analyse fonctionnelle (dit” Maurey-Schwartz”), pages 1–12.
  * Shalev-Shwartz and Ben-David, (2014) Shalev-Shwartz, S. and Ben-David, S. (2014).  Understanding Machine Learning: From Theory to Algorithms.  Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
  * Truong, (2022) Truong, L. V. (2022).  On rademacher complexity-based generalization bounds for deep learning.  arXiv preprint arXiv:2208.04284.
  * Vaswani et al., (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017).  Attention is all you need.  Advances in neural information processing systems, 30.
  * Wang et al., (2019) Wang, Q., Li, B., Xiao, T., Zhu, J., Li, C., Wong, D. F., and Chao, L. S. (2019).  Learning deep transformer models for machine translation.  arXiv preprint arXiv:1906.01787.
  * Wei et al., (2022) Wei, C., Chen, Y., and Ma, T. (2022).  Statistically meaningful approximation: a case study on approximating turing machines with transformers.  Advances in Neural Information Processing Systems, 35:12071–12083.
  * Wu et al., (2022) Wu, H., Meng, K., Fan, D., Zhang, Z., and Liu, Q. (2022).  Multistep short-term wind speed forecasting using transformer.  Energy, 261:125231.
  * Xu et al., (2019) Xu, J., Sun, X., Zhang, Z., Zhao, G., and Lin, J. (2019).  Understanding and improving layer normalization.  Advances in Neural Information Processing Systems, 32.
  * Zhang, (2002) Zhang, T. (2002).  Covering number bounds of certain regularized linear function classes.  Journal of Machine Learning Research, 2(Mar):527–550.
  * Zhang et al., (2022) Zhang, Y., Liu, B., Cai, Q., Wang, L., and Wang, Z. (2022).  An analysis of attention via the lens of exchangeability and latent variable models.  arXiv preprint arXiv:2212.14852.

Appendix

##  Appendix A Conversion from Scalar Valued Linear Covering Number Bound to
Linear Transformation Covering Number Bound

Suppose we have sets $\mathcal{X},\mathcal{M}\subset\mathbb{R}^{d}$, where
$\forall w\in\mathcal{M}$, $\left\lVert w\right\rVert_{r}\leq B_{w}$ and
$\forall x\in\mathcal{X}$, $\left\lVert x\right\rVert_{s}\leq B_{x}$ for some
positive values $r$ and $s$. Suppose we also have a function class
$\mathcal{F}=\\{x\rightarrow w^{\top}x\mid w\in\mathcal{W}\\}$ and a log
covering number $C$ for this function class on inputs
$\\{x_{i}\\}_{i=1}^{n}\subset\mathcal{X}$. Let
$\mathcal{W}\subset\mathbb{R}^{k\times d}$, where $\forall W\in\mathcal{W}$,
$\forall i\in[k]$, $\left\lVert W_{i}\right\rVert_{r}\leq B_{w}$.

Now, given a $W\in\mathcal{W}$, let us choose

$\hat{W}=\begin{bmatrix}\hat{W}_{1}\\\ \hat{W}_{2}\\\ \vdots\\\
\hat{W}_{k}\end{bmatrix}\in\mathcal{W}$

where $\hat{W}_{j}^{\top}$ is the column vector that would be chosen to cover
$W_{j}^{\top}$ in the scalar case. Then notice for a positive value $q$ and
for any $t\in[n]$:

$\displaystyle\left\lVert(W-\hat{W})x_{t}\right\rVert_{q}^{q}=\sum_{j=1}^{k}((W_{j}-\hat{W}_{j})x_{t})^{q}\leq
k\epsilon^{q}$

Thus we can see

$\log
N_{\infty}\left(\mathcal{F},k^{1/q}\epsilon,N,\left\lVert\cdot\right\rVert_{q}\right)\leq
kC$

Therefore, if $C$ does not rely on $n$, neither does this bound.

##  Appendix B Proof of Lemma 3.2

Notice how the right hand side is a lower bound for the left hand side. Thus,
we need to show
$\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,\\{B_{x}e_{1},\dots,B_{x}e_{d}\\},\left\lVert\cdot\right\rVert_{q}\right)\geq\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,N,\left\lVert\cdot\right\rVert_{q}\right)$.
To do this, let $\hat{\mathcal{F}}$ be a set of size
$\mathcal{N}_{\infty}\left(\mathcal{F},\epsilon,\\{B_{x}e_{1},\dots,B_{x}e_{d}\\},\left\lVert\cdot\right\rVert_{q}\right)$
such that it covers $\mathcal{F}$ on the set
$\\{B_{x}e_{1},\dots,B_{x}e_{d}\\}$ to size $\epsilon$. We claim
$\hat{\mathcal{F}}$ also covers $\mathcal{F}$ over any set of size $N$ in our
input space. Let $\hat{\mathcal{W}}$ refer to the matrices used in
$\hat{\mathcal{F}}$. Let $W\in\mathcal{W}$ and let
$\hat{W}\in\hat{\mathcal{W}}$ be the matrix we would choose to cover
$\mathcal{W}$. Notice for any $\left\lVert x\right\rVert_{1}\leq B_{x}$, we
have

$\displaystyle\left\lVert(W-\hat{W})x\right\rVert_{q}=\left\lVert\sum_{i=1}^{d}(W-\hat{W})x_{i}e_{i}\right\rVert_{q}\leq\sum_{i=1}^{d}|x_{i}|\left\lVert(W_{i}-\hat{W}_{i})\right\rVert_{q}\leq
B_{x}\max_{i\in[d]}\left(\left\lVert(W_{i}-\hat{W}_{i})\right\rVert_{q}\right)=$
$\displaystyle\max_{i\in[d]}\left(\left\lVert(W-\hat{W})B_{x}e_{i}\right\rVert_{q}\right)\leq\epsilon$

Thus for any set of $\\{x_{i}\\}_{i=1}^{N}$ where $\left\lVert
x\right\rVert_{1}\leq B_{x}$ we have

$\sup_{j\in[N]}\left\lVert(W-\hat{W})x_{j}\right\rVert_{q}\leq\sup_{j\in[N]}\max_{i\in[d]}\left(\left\lVert(W-\hat{W})B_{x}e_{i}\right\rVert_{q}\right)=\max_{i\in[d]}\left(\left\lVert(W-\hat{W})B_{x}e_{i}\right\rVert_{q}\right)\leq\epsilon$

which shows that it is also an upper bound and thus we have an equality.

##  Appendix C Proof of Single Layer Bound (Theorem 4.1)

Before we start the analysis, for any vectors $v,u\in\mathbb{R}^{d}$,
$\left\lVert v\right\rVert_{1}\leq B_{v}$, notice the following inequality:

$v^{T}u\leq B_{v}\max_{j\in[d]}|e_{j}u|=\max_{j\in[d],s\in\\{-1,1\\}}se_{j}u$

We will also need this lemma that can be found in Edelman et al. 2022

######  Lemma C.1.

(Corollary A.7 in Edelman et al. 2022) For
$\theta_{1},\theta_{2}\in\mathbb{R}^{p}$, we have

$\left\lVert\text{softmax}(\theta_{1})-\text{softmax}(\theta_{2})\right\rVert_{1}\leq
2\left\lVert\theta_{1}-\theta_{2}\right\rVert_{\infty}$

Using the fist inequality above we can see we get:

$\displaystyle\mathbb{E}\left[\sup_{w,W_{c},W_{v},W_{QK}}\sum_{i=1}^{m}\epsilon_{i}w^{T}W_{c}^{T}\sigma\left(W_{v}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right)\right]\leq$
$\displaystyle
B_{w}\mathbb{E}\left[\sup_{s,j\in[d]W_{c},W_{v},W_{QK}}s\sum_{i=1}^{m}\epsilon_{i}e_{j}^{T}W_{c}^{T}\sigma\left(W_{v}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right)\right]$

But now notice that $e_{j}^{T}W_{c}^{T}$ is also just a row vector. Thus we
can use the inequality again to get:

$\displaystyle
B_{w}B_{W_{c}}\mathbb{E}\left[\sup_{s,j\in[k]W_{v},W_{QK}}s\sum_{i=1}^{m}\epsilon_{i}e_{j}^{T}\sigma\left(W_{v}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right)\right]\leq$

Since $\sigma$ is applied elementwise, we can bring $e_{j}^{T}$ inside of the
function. Also, since $\sigma(0)=0$, we can see that if we have $W_{v}$ be the
zero matrix, we have $0$ in our function class. Therefore, we can get rid of
the sign function by using the well known property of Rademacher complexities
of:

$Rad_{m}(\mathcal{F}\cup-\mathcal{F},S)\leq 2Rad_{m}(\mathcal{F},S)$

This, along with the contraction inequality Ledoux and Talagrand, (1991)
allows us to upper bound the above by

$2B_{w}B_{W_{c}}L_{\sigma}\mathbb{E}\left[\sup_{j\in[k]W_{v},W_{QK}}\sum_{i=1}^{m}\epsilon_{i}e_{j}^{T}W_{v}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right]$

Continuing using the first inequality in this section again, we see

$\displaystyle
2B_{w}B_{W_{c}}L_{\sigma}\mathbb{E}\left[\sup_{j\in[k]W_{v},W_{QK}}\sum_{i=1}^{m}\epsilon_{i}e_{j}^{T}W_{v}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right]\leq$
$\displaystyle
2B_{w}B_{W_{c}}L_{\sigma}B_{W_{v}}\mathbb{E}\left[\sup_{s,j\in[d]}\sup_{W_{QK}}\sum_{i=1}^{m}s\epsilon_{i}e_{j}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)\right]$

Let us call the expectation above $E$. We will now use covering numbers and
Dudley’s integral to bound $E$ to get our final generalization bound. First,
we will use our covering number bound at scale
$\epsilon^{\prime}=\epsilon/2B_{x}^{2}$. Specifically, we will show that a set
with a log size of $\ln(2d)+\frac{4B_{x}^{4}C}{\epsilon^{2}}$ covers the
function class in the expectation above. The $\ln(2d)$ comes from the fact
that we will have to modify $\hat{\mathcal{W}}$ to have it work for us. We do
this by using the covering function class

$S=\\{X\rightarrow
se_{j}^{T}X^{T}\text{softmax}\left(X\hat{W}_{QK}x_{[CLS]}\right)\mid
s\in\\{-1,1\\},j\in[d],\hat{W}_{QK}\in\hat{\mathcal{W}\\}}$

Notice this allows for every $\hat{W}_{QK}\in\hat{\mathcal{W}}$, we have every
combination of $s$ and $e_{j}$.

Now, using the lemma C.1 and the linear algebra results of $\left\lVert
Pv\right\rVert\leq\left\lVert P\right\rVert_{2,\infty}\left\lVert
v\right\rVert_{1}$ and $\left\lVert
X\right\rVert_{2\rightarrow\infty}=\left\lVert
X^{\top}\right\rVert_{2,\infty}$, we get:

$\displaystyle\left\lVert
se_{j}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)-se_{j}^{T}X_{(i)}^{T}\text{softmax}\left(X_{(i)}\hat{W}_{QK}x_{[CLS]}\right)\right\rVert\leq$
$\displaystyle\left\lVert
X_{(i)}^{T}\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)-X_{(i)}^{T}\text{softmax}\left(X_{(i)}\hat{W}_{QK}x_{[CLS]}\right)\right\rVert\leq$
$\displaystyle\left\lVert
X_{(i)}^{T}\right\rVert_{2,\infty}\left\lVert\text{softmax}\left(X_{(i)}W_{QK}x_{[CLS]}\right)-\text{softmax}\left(X_{(i)}\hat{W}_{QK}x_{[CLS]}\right)\right\rVert_{1}\leq$
$\displaystyle 2\left\lVert X_{(i)}^{T}\right\rVert_{2,\infty}\left\lVert
X_{(i)}W_{QK}x_{[CLS]}-X_{(i)}\hat{W}_{QK}x_{[CLS]}\right\rVert_{\infty}\leq$
$\displaystyle 2\left\lVert X_{(i)}^{T}\right\rVert_{2,\infty}^{2}\left\lVert
W_{QK}x_{[CLS]}-\hat{W}_{QK}x_{[CLS]}\right\rVert\leq$ $\displaystyle
2B_{X}^{2}\frac{\epsilon}{2B_{X}^{2}}=\epsilon$

Therefore, we can see the log covering number of $S$ is
$\ln(2d)+\frac{4B_{x}^{4}C}{\epsilon^{2}}$. Also, notice, due to the softmax
in $S$, the largest value the function class can be is $B_{x}$. Then, using
Dudley’s integral we have a constant $c$ such that

$\displaystyle E/c\leq\inf_{\delta\geq
0}\delta+\int_{\delta}^{B_{x}}\sqrt{\frac{\ln(2d)}{m}+\frac{\frac{4B_{x}^{4}C}{\epsilon^{2}}}{m}}d\epsilon\leq$
$\displaystyle\inf_{\delta\geq
0}\delta+(B_{x}-\delta)\sqrt{\frac{\ln(2d)}{m}}+\int_{\delta}^{B_{x}}\sqrt{\frac{\frac{4B_{x}^{4}C}{\epsilon^{2}}}{m}}d\epsilon\leq$
$\displaystyle\inf_{\delta\geq
0}\delta+(B_{x}-\delta)\sqrt{\frac{\ln(2d)}{m}}+\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}\ln(B_{x}/\delta)$

When $m>\ln(2d)$ standard analysis can find the minimum for $\delta$ is when

$\delta=\frac{\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}}{1-\sqrt{\frac{\ln(2d)}{m}}}=\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}-\sqrt{\ln(2d)}}$

Substituting this in and rearranging we get

$\displaystyle\frac{\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}}{1-\sqrt{\frac{\ln(2d)}{m}}}\left(1-\sqrt{\frac{\ln(2d)}{m}}\right)+B_{x}\sqrt{\frac{\ln(2d)}{m}}+\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}\ln\left(\frac{B_{x}(\sqrt{m}-\sqrt{\ln(2d)})}{2B_{x}^{2}\sqrt{C}}\right)=$
$\displaystyle\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}+B_{x}\sqrt{\frac{\ln(2d)}{m}}+\frac{2B_{x}^{2}\sqrt{C}}{\sqrt{m}}\ln\left(\frac{\sqrt{m}-\sqrt{\ln(2d)}}{2B_{x}\sqrt{C}}\right)$

Thus, multiplying this by $c$ and substituting this in for $E$ gives us our
desired result.

##  Appendix D Corollaries of Theorem 4.1

######  Corollary D.0.1.

Let us have the requirements needed for Theorem 4.1 along with $\left\lVert
x\right\rVert_{1}\leq B_{x}$ and $\left\lVert
W_{QK}\right\rVert_{1,\infty}\leq B_{W_{QK}}$. Let

$B=B_{w}B_{W_{c}}L_{\sigma}B_{W_{v}}$

and let

$\alpha=2B_{W_{QK}}\sqrt{d\log(2d+1)}$

Then we have our Transformer Rademacher complexity being less than

$\displaystyle
O\left(B\left(\frac{B_{x}^{3}\alpha}{\sqrt{m}}\left(1+\ln\left(\frac{\sqrt{m}-\sqrt{\ln(2d)}}{B_{x}^{2}\alpha}\right)\right)+B_{x}\sqrt{\frac{\ln(2d)}{m}}\right)\right)$

######  Corollary D.0.2.

Let us have the requirements needed for Theorem 4.1 along with $\left\lVert
x\right\rVert_{1}\leq B_{x}$ and $\left\lVert W_{QK}\right\rVert_{2,1}\leq
B_{W_{QK}}$ Let

$B=B_{w}B_{W_{c}}L_{\sigma}B_{W_{v}}$

and let

$\alpha=2B_{W_{QK}}\sqrt{2\log(d)}$

Then we have our Transformer Rademacher complexity being less than

$\displaystyle\hat{O}\left(B\left(\frac{B_{x}^{3}\alpha}{\sqrt{m}}\left(1+\ln\left(\frac{\sqrt{m}-\sqrt{\ln(2d)}}{B_{x}^{2}\alpha}\right)\right)+B_{x}\sqrt{\frac{\ln(2d)}{m}}\right)\right)$

Where the $\hat{O}$ denotes normal $O$ but with some logarithms not containing
$T,d,k$ being omitted from inside the formula.

##  Appendix E Proof of Multiple Layers Covering Number (Theorem 4.2)

We will first start with some useful lemmas stated in Edelman et al., (2022).
The proofs of these lemmas will not be reproduced for ease of reading.

######  Lemma E.1.

(Lemma A.8 in Edelman et al. 2022) For $\epsilon,C_{i},\beta_{i}\geq 0$,
$i\in[n]$ the solution to

$\min_{\epsilon_{1},\dots,\epsilon_{n}}\sum_{i=1}^{n}\frac{C_{i}}{\epsilon_{i}^{2}}$

given

$\sum_{i=1}^{n}\beta_{i}\epsilon_{i}=\epsilon$

is $\frac{\gamma^{3}}{\epsilon^{2}}$ where

$\gamma=\sum_{i=1}^{n}C_{i}^{1/3}\beta_{i}^{2/3}$

and

$\epsilon_{i}=\frac{\epsilon}{\gamma}\left(\frac{C_{i}}{\beta_{i}}\right)^{1/3}$

The proof is by using Lagrange multipliers.

######  Lemma E.2.

(Lemma A.15 from Edelman et al. 2022) Suppose $W^{1:i+1}$, $\hat{W}^{1:i+1}$
satisfy our norm bounds. Then we have

$\displaystyle\left\lVert(g_{block}^{(i+1)}(X;W^{1:i+1})-g_{block}^{(i+1)}(X;\hat{W}^{1:i+1}))^{\top}\right\rVert_{2,\infty}\leq$
$\displaystyle\left\lVert(W_{c}^{(i)}-\hat{W}_{c}^{(i)})^{\top}\sigma\left(\Pi_{norm}\left(f(g_{block}^{(i)}(X;\hat{W}^{1:i});\hat{W}^{(i)})\right)\right)^{\top}\right\rVert_{2,\infty}+$
$\displaystyle
L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})\left\lVert(g_{block}^{(i)}(X;W^{1:i})-g_{block}^{(i)}(X;\hat{W}^{1:i}))^{\top}\right\rVert_{2,\infty}+$
$\displaystyle
2L_{\sigma}B_{c2}B_{v2}\left\lVert(W_{QK}^{(i)}-\hat{W}_{QK}^{(i)})^{\top}g_{block}^{(i)}(X;\hat{W}^{1:i})^{\top}\right\rVert_{2,\infty}+$
$\displaystyle
L_{\sigma}B_{c2}\left\lVert(W_{v}^{(i)}-\hat{W}_{v}^{(i)})^{\top}g_{block}^{(i)}(X;\hat{W}^{1:i})^{\top}\right\rVert_{2,\infty}$

######  Lemma E.3.

(Lemma A.16 from Edelman et al. 2022) Given $W^{1:i+1}$,
$\hat{W}^{1:i+1},w,\hat{w}$, we have:

$\displaystyle\left|g_{scalar}(X;W^{1:L+1},w)-g_{scalar}(X;\hat{W}^{1:L+1},\hat{w})\right|\leq$
$\displaystyle\left\lVert w\right\rVert\left\lVert
g_{block}^{(L+1)}(X;W^{1:L+1})_{[CLS]}-g_{block}^{(L+1)}(X;\hat{W}^{1:L+1})_{[CLS]}\right\rVert+$
$\displaystyle\left\lVert(w-\hat{w})^{\top}g_{block}^{(L+1)}(X;\hat{W}^{1:L+1})_{[CLS]}\right\rVert$

The main proof ideas behind the above two lemmas is to unroll them, then use
some norm properties and the triangle inequality to split them up.

Now given these, we will prove the multiple layers covering number theorem.
Suppose we have our linear covering bound described in the theorem statement.
Let $X_{1},\dots,X_{m}$ be the inputs that is within our norm bounds. Let
$\mathcal{W}_{v}^{(i)},\mathcal{W}_{c}^{(i)},\mathcal{W}_{QK}^{(i)}$ be the
sets of all possible values for $W_{v}^{(i)}$, $W_{c}^{(i)},W_{QK}^{(i)}$
respectively. Let $\hat{\mathcal{W}}_{v}^{(i)}$ cover the function class
$\\{x\rightarrow W_{v}^{\top}x\mid W_{v}\in\mathcal{W}_{v}^{(i)},\left\lVert
x\right\rVert_{2}\leq 1\\}$, let $\hat{\mathcal{W}}_{c}^{(i)}$ cover the
function class $\\{x\rightarrow W_{c}^{\top}x\mid
W_{c}\in\mathcal{W}_{c}^{(i)},\left\lVert x\right\rVert_{2}\leq 1\\}$ and let
$\hat{\mathcal{W}}_{QK}^{(i)}$ cover the function class $\\{x\rightarrow
W_{QK}x\mid W_{QK}\in\mathcal{W}_{QK}^{(i)},\left\lVert x\right\rVert_{2}\leq
1\\}$ except for $\hat{\mathcal{W}}_{QK}^{(1)}$, which covers the same
function class, but with $\left\lVert x\right\rVert\leq B_{x}$. Let all of
these classes be covered with $mT$ points and let $\epsilon_{v}^{(i)}$,
$\epsilon_{c}^{(i)}$, $\epsilon_{QK}^{(i)}$ be the resolution for each cover.
Also, let $\hat{\mathcal{W}}$ cover $\\{x\rightarrow w^{\top}x\mid
w\in\mathcal{W},\left\lVert x\right\rVert\leq 1\\}$ at resolution
$\epsilon_{w}$. The exact value of these resolutions will be shown at the end.

We will show that for any $\epsilon>0$ and for any $W^{1:L+1}$ that satisfies
our norm bounds that there exists a

$\hat{W}^{1:L+1}\in\hat{\mathcal{W}}_{c}^{(1)}\otimes\hat{\mathcal{W}}_{v}^{(1)}\otimes\hat{\mathcal{W}}_{QK}^{(1)}\otimes\dots\otimes\hat{\mathcal{W}}_{c}^{(L)}\otimes\hat{\mathcal{W}}_{v}^{(L)}\otimes\hat{\mathcal{W}}_{QK}^{(L)}\otimes\hat{\mathcal{W}}$

such that

$\left|g_{scalar}(X;W^{1:L+1},w)-g_{scalar}(X;\hat{W}^{1:L+1},\hat{w})\right|\leq\epsilon$

To start, we will use lemma E.3 to get

$\displaystyle\left|g_{scalar}(X;W^{1:L+1},w)-g_{scalar}(X;\hat{W}^{1:L+1},\hat{w})\right|\leq$
$\displaystyle\left\lVert w\right\rVert\left\lVert
g_{block}^{(L+1)}(X;W^{1:L+1})_{[CLS]}-g_{block}^{(L+1)}(X;\hat{W}^{1:L+1})_{[CLS]}\right\rVert+\left\lVert(w-\hat{w})^{\top}g_{block}^{(L+1)}(X;\hat{W}^{1:L+1})_{[CLS]}\right\rVert\leq$
$\displaystyle\left\lVert
w\right\rVert\left\lVert(g_{block}^{(L+1)}(X;W^{1:L+1})-g_{block}^{(L+1)}(X;\hat{W}^{1:L+1}))^{\top}\right\rVert_{2,\infty}+\epsilon_{w}$

Now, we use lemma E.2 to see

$\displaystyle\left\lVert(g_{block}^{(L+1)}(X;W^{1:i+1})-g_{block}^{(L+1)}(X;\hat{W}^{1:i+1}))^{\top}\right\rVert_{2,\infty}\leq$
$\displaystyle\left\lVert(W_{c}^{(L)}-\hat{W}_{c}^{(L)})^{\top}\sigma\left(\Pi_{norm}\left(f(g_{block}^{(L)}(X;\hat{W}^{1:L});\hat{W}^{(L)})\right)\right)^{\top}\right\rVert_{2,\infty}+$
$\displaystyle
L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})\left\lVert(g_{block}^{(L)}(X;W^{1:L})-g_{block}^{(L)}(X;\hat{W}^{1:L}))^{\top}\right\rVert_{2,\infty}+$
$\displaystyle
2L_{\sigma}B_{c2}B_{v2}\left\lVert(W_{QK}^{(i)}-\hat{W}_{QK}^{(i)})^{\top}g_{block}^{(i)}(X;\hat{W}^{1:i})^{\top}\right\rVert_{2,\infty}+$
$\displaystyle
L_{\sigma}B_{c2}\left\lVert(W_{v}^{(L)}-\hat{W}_{v}^{(L)})^{\top}g_{block}^{(L)}(X;\hat{W}^{1:L})^{\top}\right\rVert_{2,\infty}$

Notice that if $C^{(i)}\in\mathbb{R}^{d\times T}$, $i\in[m]$,
$W\in\mathbb{R}^{k\times d}$

$\max_{i\in[m]}\left\lVert(W-\hat{W})C^{(i)}\right\rVert_{2,\infty}=\max_{i\in[m],t\in[T]}\left\lVert(W-\hat{W})C^{(i)}_{t}\right\rVert$

Therefore we can use our covering number bounds to bound the values in the
$\left\lVert\cdot\right\rVert_{2,\infty}$.

Thus, we get

$\displaystyle\left\lVert(g_{block}^{(L+1)}(X;W^{1:i+1})-g_{block}^{(L+1)}(X;\hat{W}^{1:i+1}))^{\top}\right\rVert_{2,\infty}\leq$
$\displaystyle\epsilon_{c}^{(L)}+L_{\sigma}B_{c2}\epsilon_{v}^{(L)}+2L_{\sigma}B_{c2}B_{v2}\epsilon_{QK}^{(L)}+L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})\left\lVert(g_{block}^{(L)}(X;W^{1:L})-g_{block}^{(L)}(X;\hat{W}^{1:L}))^{\top}\right\rVert_{2,\infty}$

Now note how we can iteratively do this for
$\left\lVert(g_{block}^{(L)}(X;W^{1:L})-g_{block}^{(L)}(X;\hat{W}^{1:L}))^{\top}\right\rVert_{2,\infty}$
until we have gotten to the base case of
$g_{block}^{(1)}(X;\hat{W}^{1:1}))=X$. Thus, if we let

$\alpha_{i}=\prod_{j=i+1}^{L}L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})$

we can see that

$\displaystyle\max_{i\in{m}}\left|g_{scalar}(X_{i};W^{1:L+1},w)-g_{scalar}(X_{i};\hat{W}^{1:L+1},\hat{w})\right|\leq$
$\displaystyle\epsilon_{w}+B_{w}\left(\sum_{i=2}^{L}\alpha_{i}(\epsilon_{c}^{(i)}+L_{\sigma}B_{c2}\epsilon_{v}^{(i)}+2L_{\sigma}B_{c2}B_{v2}\epsilon_{QK}^{(i)})\right)+B_{w}\alpha_{1}\left(\epsilon_{c}^{(1)}+L_{\sigma}B_{c2}\epsilon_{v}^{(1)}+2L_{\sigma}B_{c2}B_{v2}\epsilon_{QK}^{(1)}\right)$

We left the first layer outside of the sum so we can recall
$\epsilon_{QK}^{(1)}$ has a different input bound than the rest. Now, we can
use lemma E.1 to get our desired sizes for our different $\epsilon$’s and get
our covering number stated in the theorem.

##  Appendix F Other Corollaries of Theorem 4.2

######  Corollary F.0.1.

Suppose we have the norm bounds required in lemma 3.3 for each
$W_{c}^{(i)},W_{v}^{(i)},W_{QK}^{(i)},w$ and let the maximum be $B$. Let
$B_{x}$ be the input bound. Suppose we also have the bounds needed for theorem
4.2. Let

$\displaystyle\alpha_{i}=\prod_{j=i+1}^{L}L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})$
$\displaystyle\tau_{i}=\alpha_{i}^{2/3}+\left(2\alpha_{i}L_{\sigma}B_{c2}B_{v2}\right)^{2/3}+(\alpha_{i}L_{\sigma}B_{v2})^{2/3}$
$\displaystyle\gamma=\left(dB^{2}B_{x}^{2}\ln(2k+1)\right)^{1/3}\left(2L_{\sigma}B_{c2}B_{v2}\alpha_{1}B_{w}\right)^{2/3}+$
$\displaystyle\left(dB^{2}\ln(2k+1)\right)^{1/3}\left(1+(B_{w}L_{\sigma}B_{v2})^{2/3}\right)$
$\displaystyle\eta=\left(dB^{2}\ln(2k+1)\right)^{1/3}\left(B_{w}^{2/3}\sum_{i=2}^{L}\tau_{i}\right)$

Then, the log covering number of $g_{scalar}^{L+1}$ is

$\displaystyle\frac{(\gamma+\eta)^{3}}{\epsilon^{2}}$

######  Corollary F.0.2.

Suppose we have the norm bounds required in lemma 3.4 for each
$W_{c}^{(i)},W_{v}^{(i)},W_{QK}^{(i)},w$ and let the maximum be $B$. Let
$B_{x}$ be the input bound. Suppose we also have the bounds needed for theorem
4.2. Let

$\displaystyle\alpha_{i}=\prod_{j=i+1}^{L}L_{\sigma}B_{c2}B_{v2}(1+4B_{QK2})$
$\displaystyle\tau_{i}=\alpha_{i}^{2/3}+\left(2\alpha_{i}L_{\sigma}B_{c2}B_{v2}\right)^{2/3}+(\alpha_{i}L_{\sigma}B_{v2})^{2/3}$
$\displaystyle\gamma=\left(B^{2}B_{x}^{2}\ln(dk)\right)^{1/3}\left(2L_{\sigma}B_{c2}B_{v2}\alpha_{1}B_{w}\right)^{2/3}+$
$\displaystyle\left(B^{2}\ln(dk)\right)^{1/3}\left(1+(B_{w}L_{\sigma}B_{v2})^{2/3}\right)$
$\displaystyle\eta=\left(B^{2}\ln(dk)\right)^{1/3}\left(B_{w}^{2/3}\sum_{i=2}^{L}\tau_{i}\right)$

Then, the log covering number of $g_{scalar}^{L+1}$ is

$\displaystyle\frac{(\gamma+\eta)^{3}}{\epsilon^{2}}$