On the rate of convergence of an over-parametrized Transformer classifier
learned by gradient descent  *** Running title: Over-parametrized transformers

Michael Kohler1 and Adam Krzyżak2,†††Corresponding author. Tel:
+1-514-848-2424 ext. 3007, Fax:+1-514-848-2830

1 Fachbereich Mathematik, Technische Universität Darmstadt, Schlossgartenstr.
7, 64289 Darmstadt, Germany, email<EMAIL_ADDRESS>
2 Department of Computer Science and Software Engineering, Concordia
University, 1455 De Maisonneuve Blvd. West, Montreal, Quebec, Canada H3G 1M8,
email<EMAIL_ADDRESS>
December 3, 2023

Abstract
Classification from independent and identically distributed random variables
is considered. Classifiers based on over-parametrized transformer encoders are
defined where all the weights are learned by gradient descent. Under suitable
conditions on the a posteriori probability an upper bound on the rate of
convergence of the difference of the misclassification probability of the
estimate and the optimal misclassification probability is derived.

AMS classification: Primary 62G08; secondary 62G20.

Key words and phrases: Gradient descent, over-parametrization, pattern
recognition, rate of convergence, Transformer networks.

##  1 Introduction

###  1.1 Scope of this article

One of the most recent and fascinating breakthroughs in artificial
intelligence is ChatGPT, a chatbot which can simulate human conversation.
ChatGPT is an instance of GPT4, which is a language model based on generative
predictive transformers. So if one wants to study from a theoretical point of
view, how powerful such artificial intelligence can be, one approach is to
consider transformer networks and to study which problems one can solve with
these networks theoretically. Here it is not only important what kind of
models these network can approximate, or how they can generalize their
knowledge learned by choosing the best possible approximation to a concrete
data set, but also how well optimization of such transformer network based on
concrete data set works. In this article we consider all these three different
aspects simultaneously and show a theoretical upper bound on the
missclassification probability of a transformer network fitted to the observed
data. For simplicity we focus in this context on transformer encoder networks
which can be applied to define an estimate in the context of a classification
problem involving natural language.

###  1.2 Pattern recognition

We study these estimates in the context of pattern recognition. Given $(X,Y)$,
$(X_{1},Y_{1})$, …, $(X_{n},Y_{n})$ independent and identically distributed
random variables with values in $\mathbb{R}^{d\cdot l}\times\\{-1,1\\}$, and
given the data set

${\mathcal{D}}_{n}=\\{(X_{1},Y_{1}),\dots,(X_{n},Y_{n})\\}$

the goal is to construct a classifier

$\eta_{n}(\cdot)=\eta_{n}(\cdot,{\mathcal{D}}_{n}):\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}$

such that its misclassification probability

${\mathbf{P}}\\{\eta_{n}(X)\neq Y|{\mathcal{D}}_{n}\\}$

is as small as possible. Here the predictor variable $X$ describes the
encoding of a sequence of length $l$ consisting of words or tokens, and each
word or token is encoded by a value in $\mathbb{R}^{d}$. The goal is to
predict the label $Y$ corresponding to the sentence described by $X$.

Let

$m(x)={\mathbf{P}}\\{Y=1|X=x\\}\quad(x\in\mathbb{R}^{d\cdot l})$ (1)

be the a posteriori probability of class 1. Then

$\eta^{*}(x)=\begin{cases}1,&\mbox{if }m(x)\geq\frac{1}{2}\\\
-1,&\mbox{elsewhere}\end{cases}$

is the Bayes classifier, i.e., the classifier satisfying

${\mathbf{P}}\\{\eta^{*}(X)\neq Y\\}=\min_{\eta:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{\eta(X)\neq Y\\}$

(cf., e.g., Theorem 2.1 in Devroye, Györfi and Lugosi (1996)).

In this paper we derive upper bounds on

$\displaystyle{\mathbf{E}}\left\\{{\mathbf{P}}\\{\eta_{n}(X)\neq
Y|{\mathcal{D}}_{n}\\}-{\mathbf{P}}\\{\eta^{*}(X)\neq Y\\}\right\\}$
$\displaystyle={\mathbf{P}}\\{\eta_{n}(X)\neq
Y\\}-\min_{\eta:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{\eta(X)\neq Y\\}.$ (2)

It is well-known that in order to derive nontrivial rate of convergence
results on the difference between the misclassification probability of any
estimate and the minimal possible value it is necessary to restrict the class
of distributions (cf., e.g., Section 3.1 in Györfi et al. (2002)). In this
context we will assume that the a posteriori probability is smooth in the
following sense:

###### Definition 1

Let $p=q+s$ for some $q\in\mathbb{N}_{0}$ and $0<s\leq 1$. A function
$m:\mathbb{R}^{d\cdot l}\rightarrow\mathbb{R}$ is called $(p,C)$-smooth, if
for every $\mathbf{\alpha}=(\alpha_{1},\dots,\alpha_{d\cdot
l})\in\mathbb{N}_{0}^{d\cdot l}$ with $\sum_{j=1}^{d\cdot l}\alpha_{j}=q$ the
partial derivative $\partial^{q}m/(\partial x_{1}^{\alpha_{1}}\dots\partial
x_{d\cdot l}^{\alpha_{d\cdot l}})$ exists and satisfies

$\left|\frac{\partial^{q}m}{\partial x_{1}^{\alpha_{1}}\dots\partial x_{d\cdot
l}^{\alpha_{d\cdot l}}}(x)-\frac{\partial^{q}m}{\partial
x_{1}^{\alpha_{1}}\dots\partial x_{d\cdot l}^{\alpha_{d\cdot
l}}}(z)\right|\leq C\|\mathbb{x}-\mathbb{z}\|^{s}$

for all $\mathbb{x},\mathbb{z}\in\mathbb{R}^{d\cdot l}$, where $\|\cdot\|$
denotes the Euclidean norm.

In order to show good rates of convergence even for high-dimensional
predictors we use a hierarchical composition model as in Schmidt-Hieber
(2020), where the a posteriori probability is represented by a composition of
several functions and where each of these functions depends only on a few
variables. We use the following definition of Kohler and Langer (2021) to
formalize this assumption.

###### Definition 2

Let $d,l\in\mathbb{N}$, $m:\mathbb{R}^{d\cdot l}\to\mathbb{R}$ and let ${\cal
P}$ be a subset of $(0,\infty)\times\mathbb{N}$.
a) We say that $m$ satisfies a hierarchical composition model of level $0$
with order and smoothness constraint $\mathcal{P}$, if there exists
$K\in\\{1,\dots,{d\cdot l}\\}$ such that

$m(\mathbb{x})=x^{(K)}\quad\mbox{for all
}\mathbb{x}=(x^{(1)},\dots,x^{({d\cdot l})})^{\top}\in\mathbb{R}^{d\cdot l}.$

b) Let $\kappa\in\mathbb{N}_{0}$. We say that $m$ satisfies a hierarchical
composition model of level $\kappa+1$ with order and smoothness constraint
$\mathcal{P}$, if there exist $(p,K)\in{\cal P}$, $C>0$,
$g:\mathbb{R}^{K}\to\mathbb{R}$ and $f_{1},\dots,f_{K}:\mathbb{R}^{d\cdot
l}\to\mathbb{R}$, such that $g$ is $(p,C)$–smooth, $f_{1},\dots,f_{K}$ satisfy
a hierarchical composition model of level $\kappa$ with order and smoothness
constraint $\mathcal{P}$ and

$m(\mathbb{x})=g(f_{1}(\mathbb{x}),\dots,f_{K}(\mathbb{x}))\quad\mbox{for all
}\mathbb{x}\in\mathbb{R}^{d\cdot l}.$

Let ${\cal H}(\kappa,{\cal P})$ be the set of all functions
$m:\mathbb{R}^{d\cdot l}\rightarrow\mathbb{R}$ which satisfy a hierarchical
composition model of level $\kappa$ with order and smoothness constraint
$\mathcal{P}$.

A motivation of hierarchical models from an applied point of view can be found
in Kohler and Langer (2020a).

###  1.3 Learning of a transformer encoder

We apply gradient descent to an over-parametrized model of a transformer
encoder in order to learn its parameter. More precisely, let $\mathbf{\Theta}$
be the set of parameters of the transformer networks
$\\{f_{\mathbf{\vartheta}}:\mathbf{\vartheta}\in\mathbf{\Theta}\\}$ (which we
will introduce in detail in Section 2 below), and consider a linear
combination

$f(x)=f_{(w_{k})_{k=1,\dots,K},(\mathbf{\vartheta}_{k})_{k=1,\dots,K}}(x)=\sum_{k=1}^{K}w_{k}\cdot
f_{\mathbf{\vartheta}_{k}}(x)$

of transformer networks $f_{\mathbf{\vartheta}_{k}}$. Here
$(w_{k})_{k=1,\dots,K}$ are weights satisfying

$w_{k}\geq 0\quad\mbox{and}\sum_{k=1}^{K}w_{k}=1,$ (3)

$\mathbf{\vartheta}_{k}$ are the weights of the transformer networks
$f_{\mathbf{\vartheta}_{k}}$ $(k=1,\dots,K_{n})$, and by choosing $K$ very
large our model becomes over-parametrized in the sense that the number of its
parameters is much larger than the sample size. We will use

$\eta_{n}(X)=sgn(f(X))$

as our prediction of $Y$, and in order to achieve a small missclassification
probability our aim will be to choose the parameters $(w_{k})_{k=1,\dots,K}$
and $(\mathbf{\vartheta}_{k})_{k=1,\dots,K}$ of $f$ such that its logistic
loss

${\mathbf{E}}\left\\{\log\left(1+\exp(-Y\cdot f(X)\right)\right\\}$

is small. To do this, we will randomly initialize its parameter in a proper
way and then perform $t_{n}$ gradient descent steps in view of minimization of
the empirical logistic loss

$\frac{1}{n}\sum_{i=1}^{n}\log\left(1+\exp(-Y_{i}\cdot f(X_{i})\right),$

where proper projection steps will ensure that (3) is satisfied and that the
parameters $\mathbf{\vartheta}_{k}$ will not move away too far from their
random starting values (see Section 2 for details).

###  1.4 Main results

We show, that in case that the a posteriori probability satisfies a
hierarchical composition model with smoothness and order constraint ${\cal
P}$, the corresponding estimate $\eta_{n}$ satisfies

${\mathbf{P}}\\{\eta_{n}(X)\neq Y\\}-\min_{\eta:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{\eta(X)\neq Y\\}\leq c_{1}\cdot(\log
n)^{3}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{2\cdot(2p+K)},\frac{1}{6}\right\\}}.$

And if, in addition,

${\mathbf{P}}\left\\{\max\left\\{\frac{{\mathbf{P}}\\{Y=1|X\\}}{1-{\mathbf{P}}\\{Y=1|X\\}},\frac{1-{\mathbf{P}}\\{Y=1|X\\}}{{\mathbf{P}}\\{Y=1|X\\}}\right\\}>n^{1/3}\right\\}\geq
1-\frac{1}{n^{1/3}}\quad(n\in\mathbb{N})$

holds (which implies that with high probability ${\mathbf{P}}\\{Y=1|X\\}$ is
either close to one or close to zero) then we show that the estimates achieve
the improved rate of convergence

${\mathbf{P}}\\{\eta_{n}(X)\neq Y\\}-\min_{\eta:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{\eta(X)\neq Y\\}\leq c_{2}\cdot(\log
n)^{3}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{2p+K},\frac{1}{3}\right\\}}.$

In order to prove these results we derive a general result which gives an
upper bound on the expected logistic loss of an over-parametrized linear
combination of deep networks learned by minimizing an empirical logistic loss
via gradient descent. In the proof of this result we show that the projection
of the outer weights enables us to bound the generalization error of our over-
parametrized linear combination of deep networks by the Rademacher complexity
of a class of single deep networks. And in the application of this general
result, we derive new approximation properties of Transformer networks with
slightly disturbed weight matrices.

###  1.5 Discussion of related results

Transformers have been introduced by Vaswani et al. (2017). In applications
they are usually combined with unsupervised pre-training and the same pre-
trained transformer encoder is then fine-tuned to a variety of natural
language processing tasks, see Devlin et al. (2019).

Approximation and generalization of Transformer encoder networks has been
studied in Gurevych et al. (2022). There estimates are defined as plug-in
classifiers of the least squares estimates based on transformer networks, and
similar rate of convergence results as in the current paper are shown. The
main difference between our result in this paper and the result in Gurevych et
al. (2022) is that we define our estimates using gradient descent, and
consequently we have to take the optimization error into account too, which
forces us to derive technically much more complex approximation results for
transformer networks.

Much more is known about the deep neural network estimates. There exist quite
a few approximation results for neural networks (cf., e.g., Yarotsky (2018),
Yarotsky and Zhevnerchute (2019), Lu et al. (2020), Langer (2021) and the
literature cited therein), and generalization of deep neural networks can
either be analyzed within the framework of the classical VC theory (using e.g.
the result of Bartlett et al. (2019) to bound the VC dimension of classes of
neural networks) or in case of over-parametrized deep neural networks (where
the number of free parameters adjusted to the observed data set is much larger
than the sample size) by using bounds on the Rademacher complexity (cf., e.g.,
Liang, Rakhlin and Sridharan (2015), Golowich, Rakhlin and Shamir (2019), Lin
and Zhang (2019), Wang and Ma (2022) and the literature cited therein).

Combining such results leads to a rich theory showing that owing to the
network structure the least squares neural network estimates can achieve
suitable dimension reduction in hierarchical composition models for the
function to be estimated. For a simple model this was first shown by Kohler
and Krzyżak (2017) for Hölder smooth function and later extended to arbitrary
smooth functions by Bauer and Kohler (2019). For a more complex hierarchical
composition model and the ReLU activation function this was shown in Schmidt-
Hieber (2020) under the assumption that the networks satisfy some sparsity
constraint. Kohler and Langer (2021) showed that this also possible for fully
connected neural networks, i.e., without imposing a sparsity constraint on the
network. Adaptation of deep neural network to especially weak smoothness
assumptions was shown in Imaizumi and Fukamizu (2018), Suzuki (2018) and
Suzuki and Nitanda (2019).

Less well understood is the optimization of deep neural networks. As was
shown, e.g., in Zou et al. (2018), Du et al. (2019), Allen-Zhu, Li and Song
(2019) and Kawaguchi and Huang (2019) application of gradient descent to over-
parameterized deep neural networks leads to neural network which (globally)
minimizes the empirical risk considered. However, as was shown in Kohler and
Krzyżak (2021), the corresponding estimates do not behave well on new
independent data. So the main question is why gradient descent (and its
variants like stochastic gradient descent) can be used to fit a neural network
to observed data in such a way that the resulting estimate achieves good
results on new independent data. The challenge here is not only to analyze
optimization but to consider it simultaneously with approximation and
generalization.

In case of shallow neural networks (i.e., neural networks with only one hidden
layer) this has been done successfully in Braun et al. (2023). Here it was
possible to show that the classical dimension free rate of convergence of
Barron (1994) for estimation of a regression function where its Fourier
transform has a finite moment can also be achieved by shallow neural networks
learned by gradient descent. The main idea here is that the gradient descent
selects a subset of the neural network where random initialization of the
inner weights leads to values with good approximation properties, and that it
adjusts the outer weights for these neurons properly. A similar idea was also
applied in Gonon (2021). Kohler and Krzyżak (2022) applied this idea in the
context of over-parametrized deep neural networks where a linear combination
of a huge number of deep neural networks of fixed size are computed in
parallel. Here the gradient descent selects again a subset of the neural
networks computed in parallel and chooses a proper linear combination of the
networks. By using metric entropy bounds (cf., e.g., Birman and Solomnjak
(1967) and Li, Gu and Ding (2021)) it is possible to control generalization of
the over-parametrized neural networks, and as a result the rate of convergence
of order close to $n^{-1/(1+d)}$ (or $n^{1/(1+d^{*})}$ in case of interaction
models, where it is assumed that the regression function is a sum of functions
applied to only $d^{*}$ of the $d$ components of the predictor variable) can
be shown for Hölder-smooth regression function with Hölder exponent
$p\in[1/2,1]$. Universal consistency of such estimates for bounded $X$ was
shown in Drews and Kohler (2022).

In all those results adjusting the inner weights with gradient descent is not
important. In fact, Gonon (2021) does not do this at all, while Braun et al.
(2023) and Kohler and Krzyżak (2022) use that the relevant inner weights do
not move too far away from their starting values during gradient descent.
Similar ideas have also been applied in Andoni et al. (2014) and Daniely
(2017). This whole approach is related to random feature networks (cf., e.g.,
Huang, Chen and Siew (2006) and Rahimi and Recht (2008a, 2008b, 2009)), where
the inner weights are chosen randomly and only the outer weights are learned
during gradient descent. Yehudai and Shamir (2022) present a lower bound which
implies that either the number of neurons or the absolute value of the
coefficients must grow exponential in the dimension in order to learn a single
ReLU neuron with random feature networks. But since Braun et al. (2023) was
able to prove a useful rate of convergence result for networks similar to
random feature networks, the practical relevance of this lower bound is not
clear.

The estimates in Kohler and Krzyżak (2022) use a $L_{2}$ regularization on the
outer weights during gradient descent. As was shown in Drews and Kohler
(2023), it is possible to achieve similar results without $L_{2}$
regularization.

Often gradient descent in neural networks is studied in the neural tangent
kernel setting proposed by Jacot, Gabriel and Hongler (2020), where instead of
a neural network estimate a kernel estimate is studied and its error is used
to bound the error of the neural network estimate. For further results in this
context see Hanin and Nica (2019) and the literature cited therein. Nitanda
and Suzuki (2021) were able to analyze the global error of an over-
parametrized shallow neural network learned by gradient descent based on this
approach. However, due to the use of the neural tangent kernel, also the
smoothness assumption of the function to be estimated has to be defined with
the aid of a norm involving the kernel, which does not lead to the classical
smoothness conditions of our paper. Another approach where the estimate is
studied in some asymptotically equivalent model is the mean field approach,
cf., Mei, Montanari, and Nguyen (2018), Chizat and Bach (2018) or Nguyen and
Pham (2020). A survey of various results on over-parametrized deep neural
network estimates learned by gradient descent can be found in Bartlett,
Montanari and Rakhlin (2021).

###  1.6 Notation

The sets of natural numbers, natural numbers including zero, real numbers and
nonnegative real numbers are denoted by $\mathbb{N}$, $\mathbb{N}_{0}$,
$\mathbb{R}$ and $\mathbb{R}_{+}$, respectively. We set
$\bar{\mathbb{R}}=\mathbb{R}\cup\\{-\infty,\infty\\}$. For $z\in\mathbb{R}$,
we denote the smallest integer greater than or equal to $z$ by $\lceil
z\rceil$, and we set $z_{+}=\max\\{z,0\\}$ and $z_{-}=\max\\{-z,0\\}$. The
Euclidean norm of $x\in\mathbb{R}^{d}$ is denoted by $\|x\|$ and for
$x,z\in\mathbb{R}^{d}$ its scalar product is denoted by $<x,z>$. For a closed
and convex set $A\subseteq\mathbb{R}^{d}$ we denote by $Proj_{A}x$ that
element $Proj_{A}x\in A$ such that

$\|x-Proj_{A}x\|=\min_{z\in A}\|x-z\|.$

For $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$

$\|f\|_{\infty}=\sup_{x\in\mathbb{R}^{d}}|f(x)|$

is its supremum norm, and for $A\subseteq\mathbb{R}^{d}$ we set

$\|f\|_{\infty,A}=\sup_{x\in A}|f(x)|.$

For a vector $x=(x^{(1)},\dots,x^{(d)})^{T}$ we denote by

$\|x\|_{\infty}=\max_{i=1,\dots,n}|x^{(i)}|$

its supremum norm, and if $A=(a_{i,j})_{i=1,\dots,I,j=1,\dots,J}$ we set

$\|A\|_{\infty}=\max_{i=1,\dots,I,j=1,\dots,J}|a_{i,j}|.$

For $\mathbf{j}=(j^{(1)},\dots,j^{(d)})\in\mathbb{N}_{0}^{d}$ we write

$\|\mathbf{j}\|_{1}=j^{(1)}+\dots+j^{(d)}$

and for $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ we set

$\partial^{\mathbf{j}}f=\frac{\partial^{\|}\mathbf{j}\|_{1}f}{(\partial
x^{(1)})^{j^{(1)}}\dots(\partial x^{(d)})^{j^{(d)}}}.$

For $q\in\mathbb{N}_{0}$ and $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ we set

$\|f\|_{C^{q}(\mathbb{R}^{d})}=\max\left\\{\|\partial^{\mathbf{j}}f\|_{\infty}\,:\,\mathbf{j}\in\mathbb{N}_{0}^{d},\,\|\mathbf{j}\|_{1}\leq
q\right\\}.$

Let ${\cal F}$ be a set of functions $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$,
let $x_{1},\dots,x_{n}\in\mathbb{R}^{d}$, set $x_{1}^{n}=(x_{1},\dots,x_{n})$
and let $p\geq 1$. A finite collection
$f_{1},\dots,f_{N}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is called an $L_{p}$
$\varepsilon$–packing in ${\cal F}$ on $x_{1}^{n}$ if
$f_{1},\dots,f_{N}\in{\cal F}$ and

$\min_{1\leq i<j\leq
N}\left(\frac{1}{n}\sum_{k=1}^{n}|f_{i}(x_{k})-f_{j}(x_{k})|^{p}\right)^{1/p}\geq\varepsilon$

holds. The $L_{p}$ $\varepsilon$–packing number of ${\cal F}$ on $x_{1}^{n}$
is the size $N$ of the largest $L_{p}$ $\varepsilon$–packing of ${\cal F}$ on
$x_{1}^{n}$ and is denoted by ${\mathcal{M}}_{p}(\varepsilon,{\cal
F},x_{1}^{n})$.

For $z\in\mathbb{R}$ and $\beta>0$ we define
$T_{\beta}z=\max\\{-\beta,\min\\{\beta,z\\}\\}$. If
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is a function then we set
$(T_{\beta}f)(x)=T_{\beta}\left(f(x)\right)$. For $z\in\bar{\mathbb{R}}$ we
denote by

$sgn(z)=\begin{cases}1&\mbox{if }z>0,\\\ 0&\mbox{if }z=0,\\\ -1&\mbox{if
}z<0\end{cases}$

its sign. For $i,j\in\mathbb{N}_{0}$ we set

$\delta_{i,j}=\begin{cases}1&\mbox{if }i=j,\\\ 0&\mbox{if }i\neq
j.\end{cases}$

###  1.7 Outline

The over-parametrized transformer classifiers considered in this paper are
introduced in Section 2. The main result is presented in Section 3. In Section
4 we present a general result concerning the expected logistic loss of an
over-parametrized estimate defined by a linear combination of deep networks.
The proof of our main result is given in Section 5.

##  2 Definition of the estimate

###  2.1 Topology of the Transformer networks

Let $K_{n}\in\mathbb{N}$ be the number of transformer networks which we
compute in parallel. The over-parametrized transformer networks which we use
for our classifier are of the form

$f_{(w_{k})_{k=1,\dots,K_{n}},(\mathbf{W}_{k})_{k=1,\dots,K_{n}},(\mathbf{V}_{k})_{k=1,\dots,K_{n}}}(x)=\sum_{k=1}^{K_{n}}w_{k}\cdot
T_{\beta_{n}}(f_{\mathbf{W}_{k},\mathbf{V}_{k}}(x)),$ (4)

where the outer weights $(w_{k})_{k=1,\dots,K_{n}}$ will be chosen such that

$w_{k}\geq
0\quad(k=1,\dots,K_{n})\quad\mbox{and}\quad\sum_{k=1}^{K_{n}}w_{k}\leq 1$ (5)

hold and where $\mathbf{W}_{k}$ and $\mathbf{V}_{k}$ are the weights used in
the $k$-th Transformer network
$T_{\beta_{n}}(f_{\mathbf{W}_{k},\mathbf{V}_{k}})$ and
$\beta_{n}=c_{3}\cdot\log n$. This Transformer network is defined as follows:

For input

$x=(x_{1},\dots,x_{l})\in\mathbb{R}^{l\cdot d}$

it computes in a first step a new representation

$z_{k,0}=(z_{k,0,1},\dots,z_{k,0,l})\in\mathbb{R}^{d_{model}\times l}$

for some $d_{model}\in\mathbb{N}$ (which will be done in the same way for all
$k\in\\{1,\dots,K_{n}\\}$). Here $z_{k,0,j}$ is a new representation of
$x_{j}\in\mathbb{R}^{d}$ of dimension

$d_{model}=h\cdot I$ (6)

(where $h,I\in\mathbb{N}$ with $I\geq d+l+4$) which includes the original
data, coding of the position and additional auxiliary values used for later
computation of function values. More precisely, we set for
$s\in\\{1,\dots,h\cdot I\\}$

$z_{k,0,j}^{(s)}=\begin{cases}x_{j}^{(s)}&\mbox{if }s\in\\{1,\dots,d\\}\\\
1&\mbox{if }s=d+1\\\ \delta_{s-d-1,j}&\mbox{if }s\in\\{d+2,\dots,d+1+l\\}\\\
0&\mbox{if }s\in\\{d+l+2,d+l+3,\dots,h\cdot I\\}\\\ \end{cases}$

For $d=2$, $l=4$, $I=10$ and $h=2$ the transformation of the input is
illustrated in Figure 1.

$x=\begin{pmatrix}x_{1}^{(1)}&x_{2}^{(1)}&x_{3}^{(1)}&x_{4}^{(1)}\\\
x_{1}^{(2)}&x_{2}^{(2)}&x_{3}^{(2)}&x_{4}^{(2)}\\\
\end{pmatrix}\quad\mapsto\quad
z_{k,0}=\begin{pmatrix}x_{1}^{(1)}&x_{2}^{(1)}&x_{3}^{(1)}&x_{4}^{(1)}\\\
x_{1}^{(2)}&x_{2}^{(2)}&x_{3}^{(2)}&x_{4}^{(2)}\\\ 1&1&1&1\\\ 1&0&0&0\\\
0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\\\ 0&0&0&0\\\ \vdots&\vdots&\vdots&\vdots\\\
0&0&0&0\\\ \end{pmatrix}\in\mathbb{R}^{20\times 4}$ Figure 1: Illustration of
the transformation of the input in case $d=2$, $l=4$, $I=10$ and $h=2$.

After that we compute successive representations

$z_{k,r}=(z_{k,r,1},\dots,z_{k,r,l})\in\mathbb{R}^{d_{model}\times l}$ (7)

of the input for $r=1,\dots,N$, and apply a feedforward neural network to
$z_{k,N}$. Here $z_{k,r}$ is the representation of the input in the $k$-th
transformer network in level $r$. It depends on $l$ parts which correspond to
$x_{1}$, …, $x_{l}$. And $N$ is the number of pairs of attention and pointwise
feedforward layers of our transformer encoder.

Given $z_{k,r-1}$ for some $r\in\\{1,\dots,N\\}$ we compute $z_{k,r}$ by
applying first a multi-head attention and afterwards a pointwise feedforward
neural network with one hidden layer. Both times we will use an additional
residual connection.

The computation of the multi-head attention depends on matrices

$W_{query,k,r,s},W_{key,k,r,s}\in\mathbb{R}^{d_{key}\times
d_{model}}\quad\mbox{and}\quad W_{value,k,r,s}\in\mathbb{R}^{d_{v}\times
d_{model}}\quad(s=1,\dots,h),$ (8)

where $h\in\mathbb{N}$ is the number of attentions which we compute in
parallel, where $d_{key}\in\mathbb{N}$ is the dimension of the queries and the
keys, and where $d_{v}=d_{model}/h=I$ is the dimension of the values. Here
each of the $h$ attention heads will be used to compute a new part of length
$d_{v}=I$ of the representation $z_{k,r,i}$ of $x_{i}$ for $i=1,\dots,l$. We
use the above matrices to compute for each component $z_{k,r-1,i}$ of
$z_{k,r-1}$ (i.e., for each representation of $x_{i}$ at level $r-1$
$(i=1,\dots,l)$) corresponding queries

$q_{k,r-1,s,i}=W_{query,k,r,s}\cdot z_{k,r-1,i},$ (9)

keys

$k_{k,r-1,s,i}=W_{key,k,r,s}\cdot z_{k,r-1,i}$ (10)

and values

$v_{k,r-1,s,i}=W_{value,k,r,s}\cdot z_{k,r-1,i}$ (11)

$(s\in\\{1,\dots,h\\},i\in\\{1,\dots,l\\})$. Then the so-called attention
between the component $i$ of $z_{k,r-1}$ and the component $j$ of $z_{k,r-1}$
(i.e., between the representations of $x_{i}$ and $x_{j}$ at level $r-1$) is
defined as the scalar product

$<q_{k,r-1,s,i},k_{k,r-1,s,j}>$ (12)

of the corresponding query and key, and the index $\hat{j}_{k,r-1,s,i}$ for
which the maximal value occurs, i.e.,

$\hat{j}_{k,r-1,s,i}=\arg\max_{j\in\\{1,\dots,l\\}}<q_{k,r-1,s,i},k_{k,r-1,s,j}>,$
(13)

is determined. The value corresponding to this index is multiplied with the
maximal attention in (12) in order to define

$\displaystyle\bar{y}_{k,r,s,i}$ $\displaystyle=$ $\displaystyle
v_{k,r-1,s,\hat{j}_{k,r-1,s,i}}\cdot\max_{j\in\\{1,\dots,l\\}}<q_{k,r-1,s,i},k_{k,r-1,s,j}>$
(14) $\displaystyle=$ $\displaystyle
v_{k,r-1,s,\hat{j}_{r-1,s,i}}\cdot<q_{k,r-1,s,i},k_{k,r-1,s,\hat{j}_{k,r-1,s,i}}>$

$(s\in\\{1,\dots,h\\},i\in\\{1,\dots,l\\})$. Using a residual connection we
compute the output of the multi-head attention by

$y_{k,r}=z_{k,r-1}+(\bar{y}_{k,r,1},\dots,\bar{y}_{k,r,l})$ (15)

where

$\bar{y}_{k,r,i}=(\bar{y}_{k,r,1,i},\dots,\bar{y}_{k,r,h,i})\in\mathbb{R}^{d_{v}\cdot
h}=\mathbb{R}^{d_{model}}\quad(i\in\\{1,\dots,l\\}).$

Here $y_{k,r}\in\mathbb{R}^{d_{model}\times l}$ has the same dimension as
$z_{k,r-1}$.

The output of the pointwise feedforward neural network depends on parameters

$W_{k,r,1}\in\mathbb{R}^{d_{ff}\times
d_{model}},b_{k,r,1}\in\mathbb{R}^{d_{ff}},W_{k,r,2}\in\mathbb{R}^{d_{model}\times
d_{ff}},b_{k,r,2}\in\mathbb{R}^{d_{model}},$ (16)

which describe the weights in a feedforward neural network with one hidden
layer and $d_{ff}\in\mathbb{N}$ hidden neurons. This feedforward neural
network is applied to each component of (15) (which is analogous to a
convolutionary neural network), i.e., to each representation of $x_{1}$, …,
$x_{l}$ computed up to this point on level $r$, and computes

$z_{k,r,s}=y_{k,r,s}+W_{k,r,2}\cdot\sigma\left(W_{k,r,1}\cdot
y_{k,r,s}+b_{k,r,1}\right)+b_{k,r,2}\quad(s\in\\{1,\dots,l\\}),$ (17)

where we use again a residual connection. Here

$\sigma(x)=\max\\{x,0\\}$

is the ReLU activation function, which is applied to a vector by applying it
to each component of the vector separately. After computing $z_{k,r,s}$
$(s\in\\{1,\dots,l\\})$ we define $z_{k,r}$ by (7).

Given the output $z_{k,N}$ of the sequence of $N$ multi-head attention and
pointwise feedforward layers, we apply a (shallow) feedforward neural network
with one hidden layer and $J_{n}$ neurons to $z_{k,N,1}^{(d+l+2)}$, i.e., we
set

$f_{\mathbf{V}_{k}}(z_{k,N,1}^{(d+l+2)})=f_{net,J_{n},\mathbf{V}_{k}}(z_{k,N,1}^{(d+l+2)}),$

where for $z\in\mathbb{R}$ we define

$f_{net,J_{n},\mathbf{V}_{k}}(z)=\sum_{j=1}^{J_{n}}v_{k,j}^{(1)}\cdot\sigma\left(v_{k,j,1}^{(0)}\cdot
z+v_{k,j,0}^{(0)}\right).$

Here $\sigma(x)=\max\\{x,0\\}$ is again the ReLU activation function, and

$\mathbf{V}_{k}=\left((v_{k,j}^{(1)})_{j=1,\dots,J_{n}},(v_{k,j,1}^{(0)})_{j=1,\dots,J_{n}},(v_{k,j,0}^{(0)})_{j=1,\dots,J_{n}}\right)$

is the matrix of the weights of this feedforward neural network.

Because of

$\displaystyle T_{\beta_{n}}(z)$ $\displaystyle=$
$\displaystyle\max\\{-\beta_{n},\min\\{\beta_{n},z\\}\\}=\max\\{0,\beta_{n}-\max\\{-\beta_{n},-z\\}\\}-\beta_{n}$
$\displaystyle=$
$\displaystyle\max\\{0,2\beta_{n}-\max\\{0,-z+\beta_{n}\\}\\}-\beta_{n}=\sigma(2\beta_{n}-\sigma((-1)\cdot
z+\beta_{n}))-\beta_{n},$

$z\mapsto T_{\beta_{n}}(z)$ is a neural network with two layers, one hidden
neuron per layer and ReLU activation function. This implies that
$T_{\beta_{n}}(f_{\mathbf{V}_{k}}(z))$ is a feedforward neural network with
$3$ hidden layers, $J_{n}$ neurons in layer $1$ and one hidden neuron in
layers $2$ and $3$, resp.

The output of our $k$-th transformer network is then

$T_{\beta_{n}}(f_{\mathbf{W}_{k},\mathbf{V}_{k}}(x))=T_{\beta_{n}}(f_{\mathbf{V}_{k}}(z_{k,N,1}^{(d+l+2)})),$

where $z_{k,N,1}^{(d+l+2)}$ is one component of the output $z_{k,N}$ of the
$N$ pairs of attention layers and pointwise feedforward layers.

###  2.2 Initialization of the weights

We initialize the weights
$\mathbf{w}^{(0)}=(w_{k}^{(0)},\mathbf{W}_{k}^{(0)},\mathbf{V}_{k}^{(0)})_{k=1,\dots,K_{n}}$
as follows: We set

$w_{k}^{(0)}=0\quad(k=1,\dots,K_{n})$

and choose the components of all other weight matrices independently from
uniform distributions on the interval

$\left[-c_{4}\cdot n^{c_{5}},c_{4}\cdot n^{c_{5}}\right],$

where $c_{4},c_{5}>0$ are suitably large constants. After that we make a
pruning step which depends on a parameter $\tau\in\mathbb{N}$ chosen in
Theorem 1 below: We choose for each $k\in\\{1,\dots,K_{n}\\}$ and for each
attention head in each matrix in each row $\tau\in\mathbb{N}$ of its weights
randomly by independent uniform distributions and set all weights not chosen
to zero. Similarly, we choose for each $k\in\\{1,\dots,K_{n}\\}$ and for each
matrix $W_{k,r,1}$ in each row and for each matrix $W_{k,r,2}$ in each column
$\tau$ of its weights randomly by uniform distributions and set all weights
not chosen to zero. Furthermore we set all entries in $W_{query,k,r,1}$ and
$W_{key,k,r,1}$, all entries in the first $d+l+1$ columns of $W_{k,r,2}$, and
all entries in the last two rows of $W_{query,k,r,s}$ and $W_{key,k,r,s}$ in
columns greater than $d+l+1$ to zero.

###  2.3 Learning of the weights of the transformer network

The aim in choosing the weights
$\mathbf{w}=(w_{k},\mathbf{W}_{k},\mathbf{V}_{k})_{k=1,\dots,K_{n}}$ of our
transformer network is the minimization of the empirical logistic loss. Let

$\varphi(z)=\log(1+\exp(-z))$

be the logistic loss (or cross entropy loss). Then the empirical logistic loss
of
$f_{\mathbf{w}}=f_{(w_{k})_{k=1,\dots,K_{n}},(\mathbf{W}_{k})_{k=1,\dots,K_{n}},(\mathbf{V}_{k})_{k=1,\dots,K_{n}}}$
is defined by

$F_{n}(\mathbf{w})=\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot
f_{\mathbf{w}}(X_{i})).$ (18)

We use gradient descent together with a projection step in order to minimize
(18). Let $A$ be the set of all $(w_{k})_{k=1,\dots,K_{n}}$ which satisfy (5)
and let $B$ be the set of all
$(\mathbf{W}_{k},\mathbf{V}_{k})_{k=1,\dots,K_{n}}$ which have nonzero
components only in components which have not been set to zero in the pruning
step of the initialization of the weights and which satisfy

$\|(\mathbf{W}_{k},\mathbf{V}_{k})_{k=1,\dots,K_{n}}-(\mathbf{W}_{k}^{(0)},\mathbf{V}_{k}^{(0)})_{k=1,\dots,K_{n}}\|\leq
c_{6},$ (19)

where $c_{6}>0$ is a constant which will be chosen sufficiently small in
Theorem 1 below. Let $\lambda_{n}>0$ be the stepsize of the gradient descent
and let
$\mathbf{w}^{(0)}=(\mathbf{w}_{k}^{(0)},\mathbf{W}_{k}^{(0)},\mathbf{V}_{k}^{(0)})_{k=1,\dots,K_{n}}$
be defined as in Subsection 2.2. Then we define
$\mathbf{w}^{(t)}=(\mathbf{w}_{k}^{(t)},\mathbf{W}_{k}^{(t)},\mathbf{V}_{k}^{(t)})_{k=1,\dots,K_{n}}$
recursively by setting

$\displaystyle\left(w_{k}^{(t+1)}\right)_{k=1,\dots,K_{n}}=Proj_{A}\left(\left(w_{k}^{(t)}-\lambda_{n}\cdot\frac{\partial
F_{n}(\mathbf{w}^{(t)})}{\partial w_{k}}\right)_{k=1,\dots,K_{n}}\right)$

and

$\displaystyle(\mathbf{W}_{k}^{(t+1)},\mathbf{V}_{k}^{(t+1)})_{k=1,\dots,K_{n}}$
$\displaystyle=Proj_{B}\left(\left((\mathbf{W}_{k}^{(t)},\mathbf{V}_{k}^{(t)})-\lambda_{n}\cdot\nabla_{(\mathbf{W}_{k},\mathbf{V}_{k})}(F_{n}(\mathbf{w}^{(t)}))\right)_{k=1,\dots,K_{n}}\right)$

$(t=0,\dots,t_{n}-1)$, where $t_{n}\in\mathbb{N}$ is the number of gradient
descent steps which will be chosen in Theorem 1 below.

###  2.4 Definition of the estimate

We define our estimate as the plug-in classifier corresponding to the over-
parametrized Transformer network network with weight vector
$\mathbf{w}^{(\hat{t})}$ where $\hat{t}\in\\{0,1,\dots,t_{n}\\}$ is the index
for which the empirical logistic loss is minimal during the training, i.e., we
set

$\hat{t}=\arg\min_{t\in\\{0,1,\dots,t_{n}\\}}F_{n}(\mathbf{w}^{(t)}),$ (20)
$f_{n}(x)=f_{\mathbf{w}^{(\hat{t})}}(x)$ (21)

and

$\eta_{n}(x)=sgn(f_{n}(x)).$ (22)

##  3 Main result

Our main result is the following bound on the difference of the
misclassification probability of our estimate and the minimal
misclassification probability.

###### Theorem 1

Let $A\geq 1$. Let $(X,Y)$, $(X_{1},Y_{1})$, …, $(X_{n},Y_{n})$ be independent
and identically distributed $[-A,A]^{d\cdot l}\times\\{-1,1\\}$–valued random
variables, and let $m(x)={\mathbf{P}}\\{Y=1|X=x\\}$ be the corresponding a
posteriori probability. Let ${\cal P}$ be a finite subset of
$[1,\infty)\times\mathbb{N}$ and assume that $m$ satisfies a hierarchical
composition model with some finite level and smoothness and order constraint
${\cal P}$ and that all functions $g:\mathbb{R}^{K}\rightarrow\mathbb{R}$ in
this hierarchical composition model are Lipschitz continuous and satisfy

$\|g\|_{C^{q}(\mathbb{R}^{K})}\leq c_{7}<\infty,$

where $p=q+s$ with $s\in(0,1]$ and $q\in\mathbb{N}_{0}$ (here $(p,K)\in{\cal
P}$ is the smoothness and order corresponding to $g$ in the hierarchical
composition model). Let $K_{n}\in\mathbb{N}$ be such that

$\frac{K_{n}}{e^{(\log
n)^{3}\cdot\sqrt{n}}}\rightarrow\infty\quad(n\rightarrow\infty).$ (23)

Set $\beta_{n}=c_{3}\cdot\log n$,

$h=\left\lceil\max_{(p,K)\in{\cal P}}n^{\frac{K}{2p+K}}\right\rceil,\quad
d_{ff}=2\cdot h+2,\quad I=\lceil\log n\rceil,\quad J_{n}=\lceil c_{8}\cdot
n^{1/3}\rceil,\quad t_{n}=n\cdot K_{n}$

and

$\lambda_{n}=\frac{1}{t_{n}},$

choose $\tau\in\\{l+1,l+2,,\dots,l+d+1\\}$ and choose $N\in\mathbb{N}$
sufficiently large, $c_{6}>0$ sufficiently small, $c_{4},c_{5}>0$ sufficiently
large, $d_{key}\geq 4$, and define the estimate $\eta_{n}$ as in Section 2.

a) We have for $n$ sufficiently large

${\mathbf{P}}\\{\eta_{n}(X)\neq Y\\}-\min_{\eta:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{\eta(X)\neq Y\\}\leq c_{9}\cdot(\log
n)^{3}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{2\cdot(2p+K)},\frac{1}{6}\right\\}}.$

b) If, in addition,

${\mathbf{P}}\left\\{\max\left\\{\frac{{\mathbf{P}}\\{Y=1|X\\}}{1-{\mathbf{P}}\\{Y=1|X\\}},\frac{1-{\mathbf{P}}\\{Y=1|X\\}}{{\mathbf{P}}\\{Y=1|X\\}}\right\\}>n^{1/3}\right\\}\geq
1-\frac{1}{n^{1/3}}\quad(n\in\mathbb{N})$ (24)

holds, then we have for $n$ sufficiently large

${\mathbf{P}}\\{\eta_{n}(X)\neq Y\\}-\min_{\eta:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{\eta(X)\neq Y\\}\leq c_{10}\cdot(\log
n)^{3}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{(2p+K)},\frac{1}{3}\right\\}}.$

###### Remark 1

The upper bound in parts a) and b) of Theorem 1 do not depend on the dimension
$d\cdot l$ of $X$, hence the Transformer encoder estimate is able to
circumvent the curse of dimensionality in case that the a posteriori
probability satisfies a suitable hierarchical composition model.

###### Remark 2

In the definition of the estimate we use twice a projection step in the
definition of the gradient descent. Here the projection on the outer weights
$(w_{k})_{k=1,\dots,K_{n}}$ is our main tool which enables us to show that the
over-parametrization of the estimate does not hurt the generalization. The
second projection is used to ensure that the change of the inner weights
during gradient descent does not hurt the approximation properties of the
estimate. For neural networks with smooth activation function it is possible
to show that such a projection step is automatically satisfied during gradient
descent steps for suitable chosen stepsizes and number of gradient descent
steps, cf. Lemma 1 in Drews and Kohler (2023).

###### Remark 3

The proof of Theorem 1 implies that the result also holds for an estimate
where gradient descent is only applied to the outer weights
$(w_{k})_{k=1,\dots,K_{n}}$ and for all other weights their initial randomly
chosen values are not changed. Consequently, our estimate is based on
representation guessing and not representation learning.

###### Remark 4

By assumption (23) the number of parameters of our estimate grows exponential
in the sample size, so as in many modern applications of deep learning our
estimate uses a massive overfitting.

##  4 A general result

Let $W\in\mathbb{N}$ and let $\mathbf{\Theta}\subseteq\mathbb{R}^{W}$ be a
closed and convex set of parameter values (weights) for a deep network of a
given topology. In the sequel we assume that our aim is to learn the parameter
$\mathbf{\vartheta}\in\mathbf{\Theta}$ (vector of weights) for a deep network

$f_{\mathbf{\vartheta}}:\mathbb{R}^{d\cdot l}\rightarrow\mathbb{R}$

from the data ${\mathcal{D}}_{n}$ such that

$sgn(f_{\mathbf{\vartheta}}(x))$

is a good classifier. We do this by considering linear combinations

$f_{(\mathbf{w},\mathbf{\vartheta})}(x)=\sum_{k=1}^{K_{n}}w_{k}\cdot
T_{\beta_{n}}(f_{\mathbf{\vartheta}_{k}}(x))$ (25)

of truncated versions of estimates $f_{\mathbf{\vartheta}_{k}}(x)$
$(k=1,\dots,K_{n})$, where $\mathbf{w}=(w_{k})_{k=1,\dots,K_{n}}$ satisfies

$w_{k}\geq
0\quad(k=1,\dots,K_{n})\quad\mbox{and}\quad\sum_{k=1}^{K_{n}}w_{k}\leq 1$ (26)

and
$\mathbf{\vartheta}=(\mathbf{\vartheta}_{1},\dots,\mathbf{\vartheta}_{K_{n}})\in\mathbf{\Theta}^{K_{n}}$.
Observe that by choosing $w_{1}=1$ and $w_{k}=0$ for $k>1$ we get

$f_{(\mathbf{w},\mathbf{\vartheta})}(x)=T_{\beta_{n}}(f_{\mathbf{\vartheta}_{1}}(x))$

and in this way we can construct an estimate which satisfies

$sgn(f_{(\mathbf{w},\mathbf{\vartheta})}(x))=sgn(f_{\mathbf{\vartheta}_{1}}(x))$

for any $\mathbf{\vartheta}_{1}\in\mathbf{\Theta}$. And by choosing $K_{n}$
very large our estimate will be over-parametrized in the sense that the number
of parameters of the estimate is much larger than the sample size.

Let

$\varphi(z)=\log(1+\exp(-z))$

be the logistic loss (or cross entropy loss) and let
$m(x)={\mathbf{P}}\\{Y=1|X=x\\}$. Then

$f_{\varphi^{*}}(x)=\begin{cases}\infty&\mbox{if }m(x)=1,\\\
\log\frac{m(x)}{1-m(x)}&\mbox{if }0<m(x)<1,\\\ -\infty&\mbox{if }m(x)=0\\\
\end{cases}$

minimizes the expected logistic loss, i.e.,

$\displaystyle{\mathbf{E}}\\{\varphi(Y\cdot f_{\varphi^{*}}(X))\\}$
$\displaystyle={\mathbf{E}}\left\\{m(X)\cdot\log(1+\exp(-f_{\varphi^{*}}(X)))+(1-m(X))\cdot\log(1+\exp(f_{\varphi^{*}}(X)))\right\\}$
$\displaystyle=\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\\{\varphi(Y\cdot f(X))\\}$

holds. Because of

$sgn(f_{\varphi^{*}}(x))=\begin{cases}1&\mbox{if }m(x)>\frac{1}{2},\\\
-1&\mbox{if }m(x)<\frac{1}{2},\end{cases}$

this implies

${\mathbf{P}}\\{sgn(f_{\varphi^{*}}(X))\neq Y\\}=\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\\{-1,1\\}}{\mathbf{P}}\\{f(X)\neq Y\\},$

i.e., we can compute the optimal predictor of $Y$ given $X$ by minimizing the
expected logistic loss.

Our aim in choosing $(\mathbf{w},\mathbf{\vartheta})$ is the minimization of
the empirical logistic loss

$F_{n}((\mathbf{w},\mathbf{\vartheta}))=\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot
f_{(\mathbf{w},\mathbf{\vartheta})}(X_{i})).$

In order to achieve this, we start with a random initialization of
$(\mathbf{w},\mathbf{\vartheta})$: We choose

$\mathbf{\vartheta}_{1}^{(0)},\dots,\mathbf{\vartheta}_{K_{n}}^{(0)}$ (27)

randomly from some set $\mathbf{\Theta}^{0}\subseteq\mathbf{\Theta}$ such that
the random variables in (27) are independent and also independent from
$(X,Y)$, $(X_{1},Y_{1})$, …, $(X_{n},Y_{n})$, and we set

$w_{k}^{(0)}=0\quad(k=1,\dots,K_{n}).$

Then we perform $t_{n}\in\mathbb{N}$ gradient descent steps starting with

$\mathbf{\vartheta}^{(0)}=(\mathbf{\vartheta}_{1}^{(0)},\dots,\mathbf{\vartheta}_{K_{n}}^{(0)})\quad\mbox{and}\quad\mathbf{w}^{(0)}=(w_{1}^{(0)},\dots,w_{K_{n}}^{(0)}).$

To do this, we choose a stepsize $\lambda_{n}>0$ and set

$\displaystyle\mathbf{w}^{(t+1)}$ $\displaystyle=$ $\displaystyle
Proj_{A}\left(\mathbf{w}^{(t)}-\lambda_{n}\cdot\nabla_{\mathbf{w}}F_{n}((\mathbf{w}^{(t)},\mathbf{\vartheta}^{(t)}))\right),$
$\displaystyle\mathbf{\vartheta}^{(t+1)}$ $\displaystyle=$ $\displaystyle
Proj_{B}\left(\mathbf{\vartheta}^{(t)}-\lambda_{n}\cdot\nabla_{\mathbf{\vartheta}}F_{n}((\mathbf{w}^{(t)},\mathbf{\vartheta}^{(t)}))\right)$

for $t=1,\dots,t_{n}$. Here $A$ is the set of all $\mathbf{w}$ which satisfy
(26), and

$B=\left\\{\mathbf{\vartheta}\in\mathbf{\Theta}^{K_{n}}\,:\,\|\mathbf{\vartheta}-\mathbf{\vartheta}^{(0)}\|\leq
c_{6}\right\\},$

where $c_{6}>0$ is a constant, and $Proj_{A}$ and $Proj_{B}$ is the $L_{2}$
projection on the closed and convex sets $A$ and $B$. (Here closeness and
convexity of $B$ is implied by the closeness and convexity of
$\mathbf{\Theta}$.) Our estimate is then defined by

$\hat{t}=\arg\min_{t\in\\{0,1,\dots,t_{n}\\}}F_{n}((\mathbf{w}^{(t)},\mathbf{\vartheta}^{(t)}))$
(28)

and

$f_{n}(x)=f_{(\mathbf{w}^{(\hat{t})},\mathbf{\vartheta}^{(\hat{t})})}(x).$
(29)

###### Theorem 2

Let $(X,Y)$, $(X_{1},Y_{1})$, …, $(X_{n},Y_{n})$ be independent and
identically distributed random variables with values in $\mathbb{R}^{d\cdot
l}\times\\{-1,1\\}$. Let $t_{n},N_{n},I_{n}\in\mathbb{N}$, set

$\lambda_{n}=\frac{1}{t_{n}},\quad K_{n}=N_{n}\cdot I_{n},$

choose $c_{6}>0$, and define the estimate $f_{n}$ as above.

Let $\mathbf{\Theta}^{*}\subset\mathbf{\Theta}^{0}$ and set

$\bar{\mathbf{\Theta}}=\left\\{\mathbf{\vartheta}\in\mathbf{\Theta}\;:\,\inf_{\tilde{\mathbf{\vartheta}}\in\mathbf{\Theta}^{0}}\|\mathbf{\vartheta}-\tilde{\mathbf{\vartheta}}\|\leq
c_{6}\right\\}.$

Let $C_{n},D_{n}\geq 0$ and assume

$\|f_{\mathbf{\vartheta}}-f_{\mathbf{\vartheta}^{*}}\|_{\infty,supp(X)}\leq
C_{n}\cdot\|\mathbf{\vartheta}-\mathbf{\vartheta}^{*}\|$ (30)

for all $\mathbf{\vartheta}^{*}\in\mathbf{\Theta}^{*}$ and all
$\mathbf{\vartheta}\in\\{\bar{\mathbf{\vartheta}}\in\mathbf{\Theta}\,:\,\|\bar{\mathbf{\vartheta}}-\mathbf{\vartheta}^{*}\|\leq
c_{6}\\}$,

$\epsilon_{n}={\mathbf{P}}\left\\{\mathbf{\vartheta}^{(0)}_{1}\in\mathbf{\Theta}^{*}\right\\}>0,$
(31) $N_{n}\cdot(1-\epsilon_{n})^{I_{n}}\leq\frac{1}{n}$ (32)

and

$\|\nabla_{\mathbf{w}}F_{n}((\mathbf{w},\mathbf{\vartheta}))\|\leq
D_{n}\quad\mbox{for all }\mathbf{w}\in
A,\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}.$ (33)

Then we have

$\displaystyle{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\right\\}-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}$ $\displaystyle\leq c_{11}\cdot\Bigg{(}\frac{\log
n}{n}+{\mathbf{E}}\left\\{\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\}+\frac{C_{n}+1}{\sqrt{N_{n}}}+\frac{D_{n}^{2}}{t_{n}}$
$\displaystyle\hskip
85.35826pt+\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))\right\\}-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}\Bigg{)},$

where $\epsilon_{1}$, …, $\epsilon_{n}$ are independent and uniformly
distributed on $\\{-1,1\\}$ (so-called Rademacher random variables) and
independent from $X_{1},\dots,X_{n}$.

###### Remark 5

In Theorem 2 the Rademacher complexity

${\mathbf{E}}\left\\{\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\}$

is used to control the generalization error of the estimate,

$\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))\right\\}-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\},$

which describes the worst error occuring in the set $\Theta^{*}$ of ”good”
parameter values, is used to measure the approximation error, and

$\frac{C_{n}+1}{\sqrt{N_{n}}}+\frac{D_{n}^{2}}{t_{n}}$

is used to bound the error occuring due to gradient descent.

Proof of Theorem 2. Let $E_{n}$ be the event that there exist pairwise
distinct $j_{1},\dots,j_{N_{n}}\in\\{1,\dots,K_{n}\\}$ such that

$\mathbf{\vartheta}_{j_{i}}^{(0)}\in\mathbf{\Theta}^{*}$

holds for all $i=1,\dots,N_{n}$. If $E_{n}$ holds set

$w_{j_{i}}^{*}=\frac{1}{N_{n}}\quad(i=1,\dots,N_{n})\quad\mbox{and}\quad
w_{k}^{*}=0\quad(k\in\\{1,\dots,K_{n}\\}\setminus\\{j_{1},\dots,j_{N_{n}}\\})$

and $\mathbf{w}^{*}=(w_{k}^{*})_{k=1,\dots,K_{n}}$, otherwise set
$\mathbf{w}^{*}=0$.

We will use the following error decomposition:

$\displaystyle{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\right\\}-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}$ $\displaystyle={\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\cdot 1_{E_{n}^{c}}\right\\}$
$\displaystyle\quad+{\mathbf{E}}\left\\{\left({\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\big{|}\mathbf{\vartheta}^{(0)},{\mathcal{D}}_{n}\right\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot
f_{n}(X_{i}))\right)\cdot 1_{E_{n}}\right\\}$
$\displaystyle\quad+{\mathbf{E}}\left\\{\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot
f_{n}(X_{i}))\cdot 1_{E_{n}}\right\\}-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}$ $\displaystyle=:T_{1,n}+T_{2,n}+T_{3,n}.$

In the first step of the proof we show

${\mathbf{P}}\\{E_{n}^{c}\\}\leq\frac{1}{n}.$ (34)

To do this we consider a sequential choice of the initial weights
$\mathbf{\vartheta}_{1}^{(0)}$, …, $\mathbf{\vartheta}_{K_{n}}^{(0)}$. By
definition of $\epsilon_{n}$ we know that the probability that none of
$\mathbf{\vartheta}_{1}^{(0)}$, …, $\mathbf{\vartheta}_{I_{n}}^{(0)}$ is
contained in $\mathbf{\Theta}^{*}$ is given by

$(1-\epsilon_{n})^{I_{n}}.$

This implies that the probability that there exists $l\in\\{1,\dots,N_{n}\\}$
such that none of $\mathbf{\vartheta}_{(l-1)*I_{n}+1}^{(0)}$, …,
$\mathbf{\vartheta}_{l\cdot I_{n}}^{(0)}$ is contained in
$\mathbf{\Theta}^{*}$ is upper bounded by

$N_{n}\cdot(1-\epsilon_{n})^{I_{n}}.$

Using (32) we can conclude

${\mathbf{P}}\\{E_{n}^{c}\\}\leq
N_{n}\cdot(1-\epsilon_{n})^{I_{n}}\leq\frac{1}{n}.$

In the second step of the proof we show

$T_{1,n}\leq c_{12}\cdot\frac{(\log n)}{n}.$

To do this, we observe that for $|z|\leq\beta_{n}$ we have

$\varphi(z)=\log(1+\exp(-z))\leq(\log 4)\cdot
I_{\\{z>-1\\}}+\log(2\cdot\exp(-z))\cdot I_{\\{z\leq-1\\}}\leq 3+|z|\leq
c_{13}\cdot\log n,$

from which we can conclude by the first step of the proof

$T_{1,n}\leq c_{13}\cdot(\log n)\cdot{\mathbf{P}}\\{E_{n}^{c}\\}\leq
c_{13}\cdot\frac{(\log n)}{n}.$

Let ${\cal F}$ be the set of all $f_{(\mathbf{w},\mathbf{\vartheta})}$ where
$\mathbf{w}\in A$ and $\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}^{K_{n}}$. In
the third step of the proof we show

$T_{2,n}\leq{\mathbf{E}}\left\\{{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left({\mathbf{E}}\\{\varphi(f(X)\cdot
Y)\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}\cdot 1_{E_{n}}\right\\}.$

This follows from

$\displaystyle T_{2,n}$ $\displaystyle=$
$\displaystyle{\mathbf{E}}\left\\{{\mathbf{E}}\left\\{\left({\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\big{|}\mathbf{\vartheta}^{(0)},{\mathcal{D}}_{n}\right\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot
f_{n}(X_{i}))\right)\big{|}\mathbf{\vartheta}^{(0)}\right\\}\cdot
1_{E_{n}}\right\\}$ $\displaystyle\leq$
$\displaystyle{\mathbf{E}}\left\\{{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left({\mathbf{E}}\\{\varphi(f(X)\cdot
Y)\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot
Y_{i})\right)\bigg{|}\mathbf{\vartheta}^{(0)}\right\\}\cdot
1_{E_{n}}\right\\}$ $\displaystyle=$
$\displaystyle{\mathbf{E}}\left\\{{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left({\mathbf{E}}\\{\varphi(f(X)\cdot
Y)\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}\cdot 1_{E_{n}}\right\\}.$

Here the first inequality followed from $\mathbf{w}^{(t)}\in A$ and
$\mathbf{\vartheta}^{(t)}\in\bar{\mathbf{\Theta}}^{K_{n}}$
$(t\in\\{0,1,\dots,t_{n}\\})$.

In the fourth step of the proof we show

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left({\mathbf{E}}\\{\varphi(f(X)\cdot
Y)\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot Y_{i})\right)\right\\}$
$\displaystyle\leq 2\cdot{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot f(X_{i})\right\\}.$ (35)

Choose random variables $(X_{1}^{\prime},Y_{1}^{\prime})$, …,
$(X_{n}^{\prime},Y_{n}^{\prime})$ such that

$(X_{1},Y_{1}),\dots,(X_{n},Y_{n}),\epsilon_{1},\dots,\epsilon_{n},(X_{1}^{\prime},Y_{1}^{\prime}),\dots,(X_{n}^{\prime},Y_{n}^{\prime})$

are independent and such that

$(X_{1},Y_{1}),\dots,(X_{n},Y_{n}),(X_{1}^{\prime},Y_{1}^{\prime}),\dots,(X_{n}^{\prime},Y_{n}^{\prime})$

are identically distributed and set
$(X,Y)_{1}^{n}=((X_{1},Y_{1}),\dots,(X_{n},Y_{n}))$. We have

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left({\mathbf{E}}\\{\varphi(f(X)\cdot
Y)\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot Y_{i})\right)\right\\}$
$\displaystyle={\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left({\mathbf{E}}\\{\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i}^{\prime})\cdot
Y_{i}^{\prime})|(X,Y)_{1}^{n}\\}-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}$
$\displaystyle\leq{\mathbf{E}}\left\\{{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i}^{\prime})\cdot
Y_{i}^{\prime})-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot
Y_{i})\right)|(X,Y)_{1}^{n}\right\\}\right\\}$
$\displaystyle={\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i}^{\prime})\cdot
Y_{i}^{\prime})-\frac{1}{n}\sum_{i=1}^{n}\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}.$

Since the joint distribution of
$(X_{1},Y_{1}),\dots,(X_{n},Y_{n}),(X_{1}^{\prime},Y_{1}^{\prime}),\dots,(X_{n}^{\prime},Y_{n}^{\prime})$
does not change if we (randomly) interchange $(X_{i},Y_{i})$ and
$(X_{i}^{\prime},Y_{i}^{\prime})$, the last term is equal to

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot\left(\varphi(f(X_{i}^{\prime})\cdot
Y_{i}^{\prime})-\varphi(f(X_{i})\cdot Y_{i})\right)\right)\right\\}$
$\displaystyle\leq{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot\varphi(f(X_{i}^{\prime})\cdot
Y_{i}^{\prime})\right)\right\\}+{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}(-\epsilon_{i})\cdot\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}$
$\displaystyle=2\cdot{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}.$

Next we use a contraction-style argument. Because of the independence of the
random variables we can compute the expectation by first computing the
expectation with respect to $\epsilon_{1}$ and then computing the expectation
with respect to all other random variables. Consequently, the last term above
is equal to

$\displaystyle 2\cdot{\mathbf{E}}\Bigg{\\{}\frac{1}{2}\cdot\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot\varphi(f(X_{1})\cdot Y_{1})\right)$
$\displaystyle\quad\quad+\frac{1}{2}\cdot\sup_{g\in{\cal
F}}\left(\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})-\frac{1}{n}\cdot\varphi(g(X_{1})\cdot Y_{1})\right)\Bigg{\\}}$
$\displaystyle={\mathbf{E}}\Bigg{\\{}\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot Y_{i})$
$\displaystyle\quad\quad\quad\quad+\frac{1}{n}\cdot\varphi(f(X_{1})\cdot
Y_{1})-\frac{1}{n}\cdot\varphi(g(X_{1})\cdot Y_{1})\Bigg{)}\Bigg{\\}}.$

Because of

$\varphi^{\prime}(z)=\frac{1}{1+\exp(-z)}\cdot\exp(-z)\cdot(-1)\in[-1,0],$

$\varphi$ is Lipschitz continuous with Lipschitz constant $1$ which implies

$\displaystyle\frac{1}{n}\cdot\varphi(f(X_{1})\cdot
Y_{1})-\frac{1}{n}\cdot\varphi(g(X_{1})\cdot Y_{1})$ $\displaystyle\leq$
$\displaystyle\frac{1}{n}\cdot|f(X_{1})\cdot Y_{1}-g(X_{1})\cdot Y_{1}|$
$\displaystyle\leq$ $\displaystyle\frac{1}{n}\cdot|f(X_{1})-g(X_{1})|.$

Hence the last expectation above is upper bounded by

$\displaystyle{\mathbf{E}}\Bigg{\\{}\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot|f(X_{1})-g(X_{1})|\Bigg{)}\Bigg{\\}}.$

For fixed $(X_{1},Y_{1})$, …, $(X_{n},Y_{n})$, $\epsilon_{2}$, …,
$\epsilon_{n}$ the term

$\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot|f(X_{1})-g(X_{1})|$

is symmetric in $f$ and $g$. Therefore we can assume w.l.o.g. that
$f(X_{1})\geq g(X_{1})$ holds which implies that we have

$\displaystyle\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot|f(X_{1})-g(X_{1})|\Bigg{)}$
$\displaystyle=\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot(f(X_{1})-g(X_{1}))\Bigg{)}.$

In the same way we see that the term above is also equal to

$\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})-\frac{1}{n}\cdot(f(X_{1})-g(X_{1}))\Bigg{)},$

and we get

$\displaystyle{\mathbf{E}}\Bigg{\\{}\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot Y_{i})$
$\displaystyle\hskip
56.9055pt+\frac{1}{n}\cdot|f(X_{1})-g(X_{1})|\Bigg{)}\Bigg{\\}}$
$\displaystyle={\mathbf{E}}\Bigg{\\{}\frac{1}{2}\cdot\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot Y_{i})$
$\displaystyle\hskip 56.9055pt+\frac{1}{n}\cdot(f(X_{1})-g(X_{1}))\Bigg{)}$
$\displaystyle\quad\quad+\frac{1}{2}\cdot\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot Y_{i})$
$\displaystyle\hskip
56.9055pt-\frac{1}{n}\cdot(f(X_{1})-g(X_{1}))\Bigg{)}\Bigg{\\}}$
$\displaystyle={\mathbf{E}}\Bigg{\\{}\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot Y_{i})$
$\displaystyle\hskip
56.9055pt+\frac{1}{n}\cdot\epsilon_{1}\cdot(f(X_{1})-g(X_{1}))\Bigg{)}\Bigg{\\}}$
$\displaystyle\leq{\mathbf{E}}\Bigg{\\{}\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot\epsilon_{1}\cdot f(X_{1})\Bigg{)}\Bigg{\\}}$
$\displaystyle\quad\quad+\sup_{f,g\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(g(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot(-\epsilon_{1})\cdot g(X_{1})\Bigg{)}\Bigg{\\}}$
$\displaystyle=2\cdot{\mathbf{E}}\Bigg{\\{}\sup_{f\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot\epsilon_{1}\cdot f(X_{1})\Bigg{)}\Bigg{\\}},$

where we have used that $-\epsilon_{1}$ has the same distribution as
$\epsilon_{1}$.

Arguing in the same way for $i=2,\dots,n$ we get

$\displaystyle 2\cdot{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\left(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})\right)\right\\}$ $\displaystyle\leq
2\cdot{\mathbf{E}}\Bigg{\\{}\sup_{f\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=2}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot\epsilon_{1}\cdot f(X_{1})\Bigg{)}\Bigg{\\}}$
$\displaystyle\leq 2\cdot{\mathbf{E}}\Bigg{\\{}\sup_{f\in{\cal
F}}\Bigg{(}\frac{1}{n}\sum_{i=3}^{n}\epsilon_{i}\cdot\varphi(f(X_{i})\cdot
Y_{i})+\frac{1}{n}\cdot(\epsilon_{1}\cdot f(X_{1})+\epsilon_{2}\cdot
f(X_{2}))\Bigg{)}\Bigg{\\}}$ $\displaystyle\leq\dots$ $\displaystyle\leq
2\cdot{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\frac{1}{n}\cdot\sum_{i=1}^{n}\epsilon_{i}\cdot f(X_{i})\right\\},$

which finishes the fourth step of the proof.

In the fifth step of the proof we show

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot f(X_{i})\right\\}\cdot
1_{E_{n}}\leq{\mathbf{E}}\left\\{\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\}.$

Let ${\mathcal{W}}$ be the set of all weight vectors
$\mathbf{w}=((w_{k})_{k=1,\dots,K_{n}},(\mathbf{\vartheta}_{k})_{k=1,\dots,K_{n}})$
which satisfy
$\mathbf{\vartheta}=(\mathbf{\vartheta}_{k})_{k=1,\dots,K_{n}}\in\bar{\mathbf{\Theta}}^{K_{n}}$
and (26). Because of $f=0$ is contained in ${\cal F}$ it implies

$\sup_{f\in{\cal F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot f(X_{i})\geq 0$

from which we can conclude

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal
F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot f(X_{i})\right\\}\cdot
1_{E_{n}}$
$\displaystyle\leq{\mathbf{E}}\Bigg{\\{}\sup_{\mathbf{w}\in{\mathcal{W}}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot\sum_{j=1}^{K_{n}}w_{j}\cdot(T_{\beta_{n}}f_{\mathbf{\vartheta}_{j}}(X_{i})))\Bigg{\\}}$
$\displaystyle={\mathbf{E}}\Bigg{\\{}\sup_{\mathbf{w}\in{\mathcal{W}}}\sum_{j=1}^{K_{n}}w_{j}\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}f_{\mathbf{\vartheta}_{j}}(X_{i})))\Bigg{\\}}$
$\displaystyle\leq{\mathbf{E}}\Bigg{\\{}\sup_{\mathbf{w}\in{\mathcal{W}}}\sum_{j=1}^{K_{n}}|w_{j}|\cdot\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}f_{\mathbf{\vartheta}_{j}}(X_{i})))\right|\Bigg{\\}}$
$\displaystyle\leq{\mathbf{E}}\Bigg{\\{}\sup_{\mathbf{w}\in{\mathcal{W}}}\sum_{j=1}^{K_{n}}|w_{j}|\cdot\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}^{K_{n}},k\in\\{1,\dots,K_{n}\\}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}f_{\mathbf{\vartheta}_{k}}(X_{i})))\right|\Bigg{\\}}$
$\displaystyle\leq
1\cdot{\mathbf{E}}\Bigg{\\{}\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}^{K_{n}},k\in\\{1,\dots,K_{n}\\}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}f_{\mathbf{\vartheta}_{k}}(X_{i})))\right|\Bigg{\\}}$
$\displaystyle={\mathbf{E}}\Bigg{\\{}\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}^{K_{n}}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}f_{\mathbf{\vartheta}_{1}}(X_{i})))\right|\Bigg{\\}}$
$\displaystyle={\mathbf{E}}\left\\{\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\},$

where the last inequality followed from

$\\{T_{\beta_{n}}f_{\mathbf{\vartheta}_{k}}\,:\,\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}^{K_{n}},k\in\\{1,\dots,K_{n}\\}\\}=\\{T_{\beta_{n}}f_{\mathbf{\vartheta}_{1}}\,:\,\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}\\}.$

In the sixth step of the proof we show

$\displaystyle T_{3,n}$ $\displaystyle\leq$ $\displaystyle
c_{14}\cdot\Bigg{(}\frac{C_{n}+1}{\sqrt{N_{n}}}+\frac{D_{n}^{2}}{t_{n}}+\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))\right\\}$ $\displaystyle\hskip
85.35826pt-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}\Bigg{)}.$

Application of standard techniques concerning the analysis of gradient descent
in case of convex function (cf., Lemma 1) yields

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot f_{n}(X_{i}))\cdot
1_{E_{n}}$
$\displaystyle=\min_{t=0,\dots,t_{n}}F_{n}((\mathbf{w}^{(t)},\mathbf{\vartheta}^{(t)}))\cdot
1_{E_{n}}$ $\displaystyle\leq
F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(0)}))\cdot
1_{E_{n}}+\frac{1}{t_{n}}\cdot\sum_{t=1}^{t_{n}}|F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(t)}))-F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(0)}))|\cdot
1_{E_{n}}$ $\displaystyle\hskip
85.35826pt+\frac{\|\mathbf{w}^{*}\|^{2}}{2}+\frac{D_{n}^{2}}{2\cdot t_{n}}.$

By the definition of $\mathbf{w}^{*}$ we know

$\frac{\|\mathbf{w}^{*}\|^{2}}{2}\leq\frac{1}{2\cdot N_{n}}.$

The logistic loss is convex (since $\varphi^{\prime\prime}(z)\geq 0$ for all
$z\in\mathbb{R}$) from which we can conclude

$\displaystyle{\mathbf{E}}\left\\{F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(0)}))\cdot
1_{E_{n}}\right\\}$
$\displaystyle={\mathbf{E}}\left\\{{\mathbf{E}}\left\\{F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(0)}))\big{|}\mathbf{\vartheta}^{(0)}\right\\}\cdot
1_{E_{n}}\right\\}$
$\displaystyle={\mathbf{E}}\left\\{{\mathbf{E}}\left\\{\frac{1}{n}\sum_{i=1}^{n}\varphi(\frac{1}{N_{n}}\sum_{k=1}^{N_{n}}Y_{i}\cdot
f_{\mathbf{\vartheta}_{j_{k}}^{(0)}}(X_{i}))\big{|}\mathbf{\vartheta}^{(0)}\right\\}\cdot
1_{E_{n}}\right\\}$
$\displaystyle\leq{\mathbf{E}}\left\\{\frac{1}{N_{n}}\sum_{k=1}^{N_{n}}{\mathbf{E}}\left\\{\frac{1}{n}\sum_{i=1}^{n}\varphi(Y_{i}\cdot
f_{\mathbf{\vartheta}_{j_{k}}^{(0)}}(X_{i}))\big{|}\mathbf{\vartheta}^{(0)}\right\\}\cdot
1_{E_{n}}\right\\}$
$\displaystyle\leq\sup_{\mathbf{\vartheta}\in\Theta^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X)\right\\}.$

Finally we conclude from the fact that $\varphi$ is Lipschitz continuous with
Lipschitz constant $1$, the Cauchy-Schwarz inequality and assumption (30) that
we have

$\displaystyle\frac{1}{t_{n}}\cdot\sum_{t=1}^{t_{n}}|F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(t)}))-F_{n}((\mathbf{w}^{*},\mathbf{\vartheta}^{(0)}))|\cdot
1_{E_{n}}$
$\displaystyle=\frac{1}{t_{n}}\cdot\sum_{t=1}^{t_{n}}\left|\frac{1}{n}\sum_{i=1}^{n}\left(\varphi(Y_{i}\cdot
f_{(\mathbf{w}^{*},\mathbf{\vartheta}^{(t)})}(X_{i}))-\varphi(Y_{i}\cdot
f_{(\mathbf{w}^{*},\mathbf{\vartheta}^{(0)})}(X_{i}))\right)\right|\cdot
1_{E_{n}}$
$\displaystyle\leq\max_{t=1,\dots,t_{n}}\max_{i=1,\dots,n}|f_{(\mathbf{w}^{*},\mathbf{\vartheta}^{(t)})}(X_{i})-f_{(\mathbf{w}^{*},\mathbf{\vartheta}^{(0)})}(X_{i})|\cdot
1_{E_{n}}$
$\displaystyle\leq\max_{t=1,\dots,t_{n}}\max_{i=1,\dots,n}\sqrt{\sum_{k=1}^{K_{n}}|w_{k}^{*}|^{2}}\cdot\sqrt{\sum_{i=1}^{N_{n}}|f_{\mathbf{\vartheta}^{(t)}_{j_{i}}}(X_{i})-f_{\mathbf{\vartheta}^{(0)}_{j_{i}}}(X_{i})|^{2}}\cdot
1_{E_{n}}$
$\displaystyle\leq\frac{1}{\sqrt{N_{n}}}\cdot\sqrt{\sum_{i=1}^{N_{n}}C_{n}^{2}\cdot\|\mathbf{\vartheta}^{(t)}_{j_{i}}-\mathbf{\vartheta}^{(0)}_{j_{i}}\|^{2}}=\frac{1}{\sqrt{N_{n}}}\cdot
C_{n}\cdot\sqrt{\sum_{i=1}^{N_{n}}\|\mathbf{\vartheta}^{(t)}_{j_{i}}-\mathbf{\vartheta}^{(0)}_{j_{i}}\|^{2}}$
$\displaystyle\leq\frac{1}{\sqrt{N_{n}}}\cdot
C_{n}\cdot\|\mathbf{\vartheta}^{(t)}-\mathbf{\vartheta}^{(0)}\|\leq
c_{6}\cdot\frac{C_{n}}{\sqrt{N_{n}}}.$

Here (30) is applicable because the definition of the estimate implies

$\displaystyle\|\mathbf{\vartheta}^{(t)}_{j_{i}}-\mathbf{\vartheta}^{(0)}_{j_{i}}\|$
$\displaystyle\leq$
$\displaystyle\sqrt{\sum_{s=1}^{N_{n}}\|\mathbf{\vartheta}^{(t)}_{j_{s}}-\mathbf{\vartheta}^{(0)}_{j_{s}}\|^{2}}\leq\sqrt{\|\mathbf{\vartheta}^{(t)}-\mathbf{\vartheta}^{(0)}\|^{2}}\leq
c_{6}.$

Gathering the above results completes the proof. $\Box$

##  5 Proof of Theorem 1

In the sequel we show

$\displaystyle{\mathbf{E}}\left\\{\varphi(Y\cdot
sgn(\hat{f}_{n}(X)))\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi}^{*}(X))\right\\}$ $\displaystyle\leq c_{85}\cdot(\log
n)^{6}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{(2p+K)},\frac{1}{3}\right\\}}.$ (36)

This implies the assertion, because by Lemma 2 a) we conclude from (5)

$\displaystyle{\mathbf{P}}\left\\{Y\neq
sgn(f_{n}(X))|\right\\}-{\mathbf{P}}\left\\{Y\neq\eta^{*}(X)\right\\}$
$\displaystyle\leq{\mathbf{E}}\left\\{\frac{1}{\sqrt{2}}\cdot\left({\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))|{\mathcal{D}}_{n}\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}\right)^{1/2}\right\\}$
$\displaystyle\leq\frac{1}{\sqrt{2}}\cdot\sqrt{{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}}$ $\displaystyle\leq c_{86}\cdot(\log
n)^{3}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{2\cdot(2p+K)},\frac{1}{6}\right\\}}$

And from Lemma 2 b), (24) and Lemma 2 c) we conclude from (5)

$\displaystyle{\mathbf{P}}\left\\{Y\neq
sgn(f_{n}(X))|\right\\}-{\mathbf{P}}\left\\{Y\neq\eta^{*}(X)\right\\}$
$\displaystyle\leq 2\cdot\left({\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}\right)+4\cdot\frac{c_{87}\cdot\log n}{n^{1/3}}$
$\displaystyle\leq c_{88}\cdot(\log n)^{3}\cdot\max_{(p,K)\in{\cal
P}}n^{-\min\left\\{\frac{p}{2p+K},\frac{1}{3}\right\\}}.$

Here we have used the fact that

$\max\left\\{\frac{{\mathbf{P}}\\{Y=1|X\\}}{1-{\mathbf{P}}\\{Y=1|X\\}},\frac{1-{\mathbf{P}}\\{Y=1|X\\}}{{\mathbf{P}}\\{Y=1|X\\}}\right\\}>n^{1/3}$

is equivalent to

$|f_{\varphi^{*}}(X)|=\left|\log\frac{{\mathbf{P}}\\{Y=1|X\\}}{1-{\mathbf{P}}\\{Y=1|X\\}}\right|>\frac{1}{3}\cdot\log
n.$

So it suffices to prove (5), which we do in the sequel by applying Theorem 2.

In the first step of the proof we define $\mathbf{\Theta}$,
$\mathbf{\Theta}^{0}$ and $\mathbf{\Theta}^{*}$.

Let $\mathbf{\Theta}=\mathbf{\Theta}_{0}$ be the set of all pairs
$(\mathbf{W},\mathbf{V})$ of weight matrices of the transformer networks
$f_{(\mathbf{W}_{k},\mathbf{V}_{k})}$ introduced in Subsection 2.1. In the
supplement we will introduce Transformer networks with good approximation
properties, and we use here these Transformer networks for the definition of
$\mathbf{\Theta}^{*}$: Let $\mathbf{\Theta}^{*}$ be the set of all weight
matrices $(\mathbf{W},\mathbf{V})$ where $\mathbf{W}$ is from the weight
matrices introduced in Theorem 3 in supremum norm not further away than

$\epsilon=\frac{1}{c_{89}\cdot n^{c_{90}}},$

and where $\mathbf{V}$ is from the weight matrix introduced in Lemma 12 in
supremum norm not further away than

$\bar{\epsilon}=\frac{1}{c_{91}\cdot n^{c_{92}}}.$

In the second step of the proof we show that

$C_{n}=c_{93}\cdot n^{c_{94}}$

satisfies (30). We will show this in the Supplement in Lemma 13, which is
applicable provided we choose $c_{6}\leq 1/(2\cdot c_{62})$.

In the third step of the proof we show that $\epsilon_{n}$ defined by (31)
satisfies

$\epsilon_{n}\geq\frac{1}{e^{(\log n)^{2}\cdot\sqrt{n}}}.$

The event $\\{\theta_{1}^{(0)}\in\mathbf{\Theta}^{*}\\}$ occurs if the pruning
step selects the right subset of size $L_{n}\leq c_{95}\cdot\sqrt{n}$ out of
all subsets of size $L_{n}$ of the possible set of parameters, which has size
less equal than $c_{96}\cdot n$, and if the uniform distributions (on
intervals of length $2\cdot c_{4}\cdot n^{c_{5}}$) choose each of these
$L_{n}$ parameters correctly from an interval of size $1/(c_{97}\cdot
n^{c_{98}})$. This implies for large $n$

${\mathbf{P}}\\{\theta_{1}^{(0)}\in\mathbf{\Theta}^{*}\\}\geq\frac{1}{(c_{95}\cdot
n)^{c_{96}\cdot\sqrt{n}}}\cdot\left(\frac{1}{2\cdot c_{4}\cdot n^{c_{5}}\cdot
c_{97}\cdot n^{c_{98}}}\right)^{\sqrt{n}}\geq\frac{1}{e^{(\log
n)^{2}\cdot\sqrt{n}}}.$

In the fourth step of the proof we show that

$N_{n}=n^{c_{99}},\quad I_{n}=\lceil(\log n)^{2}\cdot e^{(\log
n)^{2}\cdot\sqrt{n}}\rceil$

satisfies (32) for $n$ large.

This follows from

$\displaystyle N_{n}\cdot(1-\epsilon_{n})^{I_{n}}$ $\displaystyle\leq$
$\displaystyle n^{c_{99}}\cdot\left(1-\frac{1}{e^{(\log
n)^{2}\cdot\sqrt{n}}}\right)^{\lceil(\log n)^{2}\cdot e^{(\log
n)^{2}\cdot\sqrt{n}}\rceil}$ $\displaystyle\leq$ $\displaystyle\frac{1}{n}$

for $n$ large.

In the fifth step of the proof we show that

$D_{n}=\sqrt{K_{n}}\cdot\beta_{n}$

satisfies (33).

We will show this in Lemma 3 in the Supplement.

In the sixth step of the proof we show

$\displaystyle{\mathbf{E}}\left\\{\left|\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\}\leq
c_{100}\cdot(\log n)^{3}\cdot\left(\max_{(p,K)\in{\cal
P}}n^{-\frac{p}{2p+K}}+n^{-\frac{1}{3}}\right).$

To see this, we use standard techniques from empirical process theory which
are summarized in Lemma 4 in the Supplement. From this we conclude

$\displaystyle{\mathbf{E}}\left\\{\left|\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\}$
$\displaystyle\leq c_{101}\cdot\frac{\sqrt{\max\\{h\cdot
I,d_{ff},J_{n}\\}}\cdot(\log n)^{2}}{\sqrt{n}}$ $\displaystyle\leq
c_{102}\cdot\frac{(\sqrt{\log n}\cdot\max_{(p,K)\in{\cal
P}}n^{K/(2\cdot(2\cdot p+K))}+n^{\frac{1}{6}})\cdot(\log n)^{2}}{\sqrt{n}}$
$\displaystyle\leq c_{103}\cdot(\log n)^{3}\cdot\left(\max_{(p,K)\in{\cal
P}}n^{-\frac{p}{2p+K}}+n^{-\frac{1}{3}}\right).$

In the seventh of the proof we show

$\displaystyle\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))\right\\}-\min_{f:\mathbb{R}^{d}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}\leq c_{104}\cdot\frac{\log
n}{n^{1/3}}+c_{105}\cdot\max_{j,i}h^{-p_{j}^{(i)}/K_{j}^{(i)}}.$

We have

$\displaystyle\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))\right\\}-\min_{f:\mathbb{R}^{d}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}$
$\displaystyle=\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))-\varphi(Y\cdot f_{\varphi^{*}}(X))\right\\}$
$\displaystyle=\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\Bigg{\\{}1_{\\{Y=1\\}}\cdot\left(\varphi(f_{\mathbf{\vartheta}}(X))-\varphi(f_{\varphi^{*}}(X))\right)$
$\displaystyle\hskip
85.35826pt+1_{\\{Y=-1\\}}\cdot\left(\varphi(-f_{\mathbf{\vartheta}}(X))-\varphi(-f_{\varphi^{*}}(X))\right)\Bigg{\\}}$
$\displaystyle=\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\Bigg{\\{}m(X)\cdot\left(\varphi(f_{\mathbf{\vartheta}}(X))-\varphi(f_{\varphi^{*}}(X))\right)$
$\displaystyle\hskip
85.35826pt+(1-m(X))\cdot\left(\varphi(-f_{\mathbf{\vartheta}}(X))-\varphi(-f_{\varphi^{*}}(X))\right)\Bigg{\\}}$
$\displaystyle\leq\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}\sup_{x\in\mathbb{R}^{d\cdot
l}}\Bigg{(}|m(x)|\cdot\left|\varphi(f_{\mathbf{\vartheta}}(x))-\varphi(f_{\varphi^{*}}(x))\right|$
$\displaystyle\hskip
85.35826pt+|1-m(x)|\cdot\left|\varphi(-f_{\mathbf{\vartheta}}(x))-\varphi(-f_{\varphi^{*}}(x))\right|\Bigg{)}.$

Application of the approximation results for Transformer networks derived in
the Supplement, i.e., application of Lemma 12 and Theorem 3 (which is
applicable because of the pruning step in the gradient descent introduced in
Section 2, which implies in particular that some components of $z_{k,r}$ do
not change during the computation) yields the assertion.

In the eighth step of the proof we complete the proof by showing (5).

Thanks to the results of the steps 1 through 5 we know that the assumptions of
Theorem 2 are satisfied. Application of Theorem 2 yields

$\displaystyle{\mathbf{E}}\left\\{\varphi(Y\cdot
sgn(f_{n}(X)))\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}$ $\displaystyle\leq
c_{106}\cdot\Bigg{(}\frac{\log
n}{n}+{\mathbf{E}}\left\\{\left|\sup_{\mathbf{\vartheta}\in\bar{\mathbf{\Theta}}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f_{\mathbf{\vartheta}}(X_{i}))\right|\right\\}+\frac{C_{n}+1}{\sqrt{N_{n}}}+\frac{D_{n}^{2}}{t_{n}}$
$\displaystyle\hskip
85.35826pt+\sup_{\mathbf{\vartheta}\in\mathbf{\Theta}^{*}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\mathbf{\vartheta}}(X))\right\\}-\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}\Bigg{)}.$

Plugging in the results of steps 6 and 7 and the values of $C_{n}$, $N_{n}$
and $D_{n}$ derived in steps 2, 4 and 5 yields the assertion. $\Box$

## References

  * [1] Allen-Zhu, Z., Li, Y., und Song, Z. (2019). A convergence theory for deep learning via over-parameterization. Proceedings of the 36th International Conference on Machine Learning (PMLR 2019), Long Beach, California, 97, pp. 242-252.
  * [2] Andoni, A., Panigraphy, R., Valiant, G., and Zhang, L. (2014). Learning polynomials with neural networks. In International Conference on Machine Learning, pages 1908–1916.
  * [3] Barron, A. R. (1994). Approximation and estimation bounds for artificial neural networks. Machine Learning 14, pp. 115-133.
  * [4] Bartlett, P., Harvey, N., Liaw, C., and Mehrabian, A. (2019). Nearly-tight VC-dimension bounds for piecewise linear neural networks. Journal of Machine Learning Research 20, pp. 1-17.
  * [5] Bartlett, P. L., Montanari, A., and Rakhlin, A. (2021). Deep learning: a statistical viewpoint. Preprint, arXiv: 2103.09177.
  * [6] Bauer, B., and Kohler, M. (2019). On deep learning as a remedy for the curse of dimensionality in nonparametric regression. Annals of Statistics 4, pp. 2261–2285.
  * [7] Birman, M. S., and Solomjak, M. Z. (1967). Piece-wise polynomial approximations of functions in the classes $W_{p}^{\alpha}$. Mathematics of the USSR Sbornik 73, pp. 295-317.
  * [8] Braun, A., Kohler, M., Langer, S., and Walk, H. (2023). Convergence rates for shallow neural networks learned by gradient descent. Accepted for publication in Bernoulli. Preprint, arXiv: 2107.09550.
  * [9] Chizat, L., and Bach, F. (2018). On the global convergence of gradient descent for over-parameterized models using optimal transport. Preprint, arXiv: 1805.09545.
  * [10] Daniely, A. (2017). SGD learns the conjugate kernel class of the network. In Advances in Neural Information Processing Systems, pp. 2422–2430.
  * [11] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv: 1810.04805.
  * [12] Devroye, L., Györfi, L., and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition. Springer, New York, USA.
  * [13] Drews, S., and Kohler, M. (2022). On the universal consistency of an over-parametrized deep neural network estimate learned by gradient descent. Preprint.
  * [14] Drews, S., and Kohler, M. (2023). Analysis of the expected $L_{2}$ error of an over-parametrized deep neural network estimate learned by gradient descent without regularization. Preprint.
  * [15] Du, S., Lee, J., Li, H., Wang, L., und Zhai, X. (2019). Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, Preprint, arXiv: 1811.03804.
  * [16] Golowich, N., Rakhlin, A., and Shamir, O. (2019). Size-Independent sample complexity of neural networks. Preprint, arXiv: 1712.06541.
  * [17] Gonon, L. (2021). Random feature networks learn Black-Scholes type PDEs without curse of dimensionality. Preprint, arXiv: 2106.08900.
  * [18] Gurevych, I., Kohler, M., and Şahin, G. (2022). On the rate of convergence of a classifier based on a Transformer encoder. IEEE Transactions Information Theory, 68, pp. 8139-8155. arXiv: 2111.14574.
  * [19] Györfi, L., Kohler, M., Krzyżak, A., and Walk, H. (2002). A Distribution–Free Theory of Nonparametric Regression. Springer.
  * [20] Hanin, B., and Nica, M. (2019). Finite depth and width corrections to the neural tangent kernel. arXiv: 1909.05989.
  * [21] Huang, G. B., Chen, L., and Siew, C.-K. (2006). Universal approximation using incremental constructive feedforward networks with random hidden nodes. IEEE Transactions on Neural Networks 17, pp. 879-892.
  * [22] Imaizumi, M., and Fukamizu, K. (2018). Deep neural networks learn non-smooth functions effectively. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2019), Naha, Okinawa, Japan.
  * [23] Jacot, A., Gabriel, F., and Hongler, C. (2020). Neural Tangent Kernel: Convergence and Generalization in Neural Networks. arXiv: 1806.07572v4.
  * [24] Kawaguchi, K, and Huang, J. (2019). Gradient descent finds global minima for generalizable deep neural networks of practical sizes.  57th IEEE Annual Allerton Conference on Communication, Control, and Computing, Allerton, IL, pp. 92-99.
  * [25] Kim, Y., Ohn, I.S, and Kim, D. (2019). Fast convergence rates of deep neural networks for classification. arXiv: 1812.03599.
  * [26] Kohler, M., and Krzyżak, A. (2017). Nonparametric regression based on hierarchical interaction models. IEEE Transaction on Information Theory 63, pp. 1620-1630.
  * [27] Kohler, M., and Krzyżak, A. (2021). Over-parametrized deep neural networks minimizing the empirical risk do not generalize well. Bernoulli 27, pp. 2564-2597.
  * [28] Kohler, M., and Krzyżak, A. (2022). Analysis of the rate of convergence of an over-parametrized deep neural network estimate learned by gradient descent. Preprint, arXiv: 2210.01443.
  * [29] Kohler, M., and Krzyżak, A. (2023). On the rate of convergence of an over-parametrized deep neural network regression estimate with ReLU activation function learned by gradient descent. Preprint.
  * [30] Kohler, M., and Langer, S. (2020a). Discussion of “Nonparametric regression using deep neural networks with ReLU activation function”. Annals of Statistics 48, pp. 1906-1910.
  * [31] Kohler, M., and Langer, S. (2020b). Statistical theory for image classification using deep convolutional neural networks with cross-entropy loss. Preprint, arXiv: 2011.13602.
  * [32] Kohler, M., and Langer, S. (2021). On the rate of convergence of fully connected deep neural network regression estimates using ReLU activation functions. Annals of Statistics 49, pp. 2231-2249. Preprint, arXiv: 1908.11133.
  * [33] Langer, S. (2021). Approximating smooth functions by deep neural networks with sigmoid activation function. Journal of Multivariate Analysis 182.
  * [34] Li, G., Gu, Y., and Ding, J. (2021). The rate of convergence of variation-constrained deep neural networks. Preprint, arXiv: 2106.12068.
  * [35] Liang, T., Rakhlin, A., and Sridharan, K. (2015). Learning with square loss: localization through offset Rademacher complexity. Preprint, arXiv: 1502.06134.
  * [36] Lin, S., and Zhang, J. (2019). Generalization bounds for convolutional neural networks. Preprint, arXiv: 1910.01487.
  * [37] Lu, J., Shen, Z., Yang, H., and Zhang, S. (2020). Deep network approximation for smooth functions. arxiv: 2001.03040.
  * [38] Mei, S., Montanari, A., and Nguyen, P.-M. (2018). A mean field view of the landscape of two-layer neural networks. In Proceedings of the National Academy of Sciences, 115, pp. E7665-E7671.
  * [39] Nguyen, P.-M., and Pham, H. T. (2020). A rigorous framework for the mean field limit of multilayer neural networks. Preprint, arXiv: 2001.1144.
  * [40] Nitanda, A., and Suzuki, T. (2021). Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. arXiv: 2006.12297.
  * [41] Rahimi, A., and Recht, B. (2008a). Random features for large-scale kernel machines. In Advances in Neural Information Procesing Systems, pp. 1177-1184.
  * [42] Rahimi, A., and Recht, B. (2008b). Uniform approximation of function with random bases. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 555-561, IEEE.
  * [43] Rahimi, A., and Recht, B. (2009). Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In D. Koller, D. Schuurman, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, Curran Associates, Inc. 21, pp. 1313-1320.
  * [44] Schmidt-Hieber, J. (2020). Nonparametric regression using deep neural networks with ReLU activation function (with discussion). Annals of Statistics 48, pp. 1875–1897.
  * [45] Suzuki, T. (2018). Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. Preprint, arXiv: 1810.08033.
  * [46] Suzuki, T., and Nitanda, A. (2019). Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. Preprint, arXiv: 1910.12799.
  * [47] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A., Kaiser, L., and Polosukhin,I. (2017). Attention is all you need. arXiv: 1706.03762.
  * [48] Wang, M., and Ma, C. (2022). Generalization error bounds for deep neural network trained by SGD. Preprint, arXiv: 2206.03299v1.
  * [49] Yarotsky, D. (2018). Optimal approximation of continuous functions by very deep ReLU networks. Preprint, arXiv: 1802.03620.
  * [50] Yarotsky, D., and Zhevnerchuk, A. (2019). The phase diagram of approximation rates for deep neural networks. Preprint, arXiv: 1906.09477.
  * [51] Yehudai, G., and Shamir, O. (2022). On the power and limitations of random features for understanding neural networks. Preprint, arXiv: 1904.00687.
  * [52] Zhang, T. (2004). Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics, 32, pp. 56 - 134.
  * [53] Zou, D., Cao, Y., Zhou, D., und Gu, Q. (2018). Stochastic gradient descent optimizes over-parameterized deep ReLU networks. Preprint, arXiv: 1811.08888.

## SUPPLEMENTARY MATERIAL

###  .1 A result for gradient descent

###### Lemma 1

Let $d_{1},d_{2}\in\mathbb{N}$, let $D_{n}\geq 0$, let
$A\subset\mathbb{R}^{d_{1}}$ and $B\subseteq\mathbb{R}^{d_{2}}$ be closed and
convex, and let
$F:\mathbb{R}^{d_{1}}\times\mathbb{R}^{d_{2}}\rightarrow\mathbb{R}_{+}$ be a
function such that

$u\mapsto F(u,v)\quad\mbox{is differentiable and convex for all
}v\in\mathbb{R}^{d_{2}}$

and

$\|(\nabla_{u}F)(u,v)\|\leq D_{n}$ (37)

for all $(u,v)\in A\times B$. Choose $(u_{0},v_{0})\in A\times B$, let
$v_{1},\dots,v_{t_{n}}\in B$ and set

$u_{t+1}=Proj_{A}\left(u_{t}-\lambda\cdot\left(\nabla_{u}F\right)(u_{t},v_{t})\right)\quad(t=0,\dots,t_{n}-1),$

where

$\lambda=\frac{1}{t_{n}}.$

Let $u^{*}\in A$. Then it holds:

$\displaystyle\min_{t=0,\dots,t_{n}}F(u_{t},v_{t})\leq
F(u^{*},v_{0})+\frac{1}{t_{n}}\sum_{t=1}^{t_{n}}|F(u^{*},v_{t})-F(u^{*},v_{0})|+\frac{\|u^{*}-u_{0}\|^{2}}{2}+\frac{D_{n}^{2}}{2\cdot
t_{n}}.$

Proof. The result follows from the proof of Lemma 1 in Kohler and Krzyżak
(2023). For the sake of completeness we give nevertheless a complete proof
here.

In the first step of the proof we show

$\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}F(u_{t},v_{t})\leq\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}F(u^{*},v_{t})+\frac{\|u^{*}-u_{0}\|^{2}}{2}+\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}.$ (38)

By convexity of $u\mapsto F(u,v_{t})$ and because of $u^{*}\in A$ we have

$\displaystyle F(u_{t},v_{t})-F(u^{*},v_{t})$
$\displaystyle\leq\,<(\nabla_{u}F)(u_{t},v_{t}),u_{t}-u^{*}>$
$\displaystyle=\frac{1}{2\cdot\lambda}\cdot
2\cdot<\lambda\cdot(\nabla_{u}F)(u_{t},v_{t}),u_{t}-u^{*}>$
$\displaystyle=\frac{1}{2\cdot\lambda}\cdot\left(-\|u_{t}-u^{*}-\lambda\cdot(\nabla_{u}F)(u_{t},v_{t})\|^{2}+\|u_{t}-u^{*}\|^{2}+\|\lambda\cdot(\nabla_{u}F)(u_{t},v_{t})\|^{2}\right)$
$\displaystyle\leq\frac{1}{2\cdot\lambda}\cdot\left(-\|Proj_{A}(u_{t}-\lambda\cdot(\nabla_{u}F)(u_{t},v_{t}))-u^{*}\|^{2}+\|u_{t}-u^{*}\|^{2}+\lambda^{2}\cdot\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}\right)$
$\displaystyle=\frac{1}{2\cdot\lambda}\cdot\left(\|u_{t}-u^{*}\|^{2}-\|u_{t+1}-u^{*}\|^{2}+\lambda^{2}\cdot\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}\right).$

This implies

$\displaystyle\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}F(u_{t},v_{t})-\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}F(u^{*},v_{t})$
$\displaystyle=\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}\left(F(u_{t},v_{t})-F(u^{*},v_{t})\right)$
$\displaystyle\leq\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}\frac{1}{2\cdot\lambda}\cdot\left(\|u_{t}-u^{*}\|^{2}-\|u_{t+1}-u^{*}\|^{2}\right)+\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}\frac{\lambda}{2}\cdot\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}$
$\displaystyle=\frac{1}{2}\cdot\sum_{t=0}^{t_{n}-1}\left(\|u_{t}-u^{*}\|^{2}-\|u_{t+1}-u^{*}\|^{2}\right)+\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}$
$\displaystyle\leq\frac{\|u_{0}-u^{*}\|^{2}}{2}+\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}.$

In the second step of the proof we show the assertion.

Using the result of step 1 we get

$\displaystyle\min_{t=0,\dots,t_{n}}F(u_{t},v_{t})$
$\displaystyle\leq\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}F(u_{t},v_{t})$
$\displaystyle\leq\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}F(u^{*},v_{t})+\frac{\|u^{*}-u_{0}\|^{2}}{2}+\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}$
$\displaystyle\leq
F(u^{*},v_{0})+\frac{1}{t_{n}}\sum_{t=0}^{t_{n}-1}|F(u^{*},v_{t})-F(u^{*},v_{0})|+\frac{\|u^{*}-u_{0}\|^{2}}{2}$
$\displaystyle\quad+\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}.$

By (37) we get

$\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}\|(\nabla_{u}F)(u_{t},v_{t})\|^{2}\leq\frac{1}{2\cdot
t_{n}^{2}}\sum_{t=0}^{t_{n}-1}D_{n}^{2}=\frac{D_{n}^{2}}{2\cdot t_{n}}.$

Summarizing the above results, the proof is complete.

$\Box$

###  .2 An auxiliary result

###### Lemma 2

Let $\varphi$ be the logistic loss. Let
$(X,Y),(X_{1},Y_{1}),\dots,(X_{n},Y_{n})$ and $\eta^{*}$,
$\mathcal{D}_{n},f_{n}$ and $\eta_{n}$ as in Sections 1 and 2, and set

$f_{\varphi^{*}}=\arg\min_{f:\mathbb{R}^{d\cdot
l}\rightarrow\bar{\mathbb{R}}}{\mathbf{E}}\left\\{\varphi(Y\cdot
f(X))\right\\}.$

a) Then

$\displaystyle{\mathbf{P}}\left\\{Y\neq\eta_{n}(X)|{\mathcal{D}}_{n}\right\\}-{\mathbf{P}}\left\\{Y\neq\eta^{*}(X)\right\\}$
$\displaystyle\leq\frac{1}{\sqrt{2}}\cdot\left({\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))|{\mathcal{D}}_{n}\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}\right)^{1/2}$

holds.
b) Then

$\displaystyle{\mathbf{P}}\left\\{Y\neq\eta_{n}(X)|{\mathcal{D}}_{n}\right\\}-{\mathbf{P}}\left\\{Y\neq\eta^{*}(X)\right\\}$
$\displaystyle\leq 2\cdot\left({\mathbf{E}}\left\\{\varphi(Y\cdot
f_{n}(X))|{\mathcal{D}}_{n}\right\\}-{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}\right)+4\cdot{\mathbf{E}}\left\\{\varphi(Y\cdot
f_{\varphi^{*}}(X))\right\\}.$

holds.
c) Assume that

${\mathbf{P}}\left\\{|f_{\varphi^{*}}(X)|>\tilde{F}_{n}\right\\}\geq
1-e^{-\tilde{F}_{n}}$

for a given sequence $\\{\tilde{F}_{n}\\}_{n\in\mathbb{N}}$ with
$\tilde{F}_{n}\to\infty$. Then

${\mathbf{E}}\left\\{\varphi(Y\cdot f_{\varphi^{*}}(X))\right\\}\leq
c_{15}\cdot\tilde{F}_{n}\cdot e^{-\tilde{F}_{n}}$

holds.

Proof. a) This result follows from Theorem 2.1 in Zhang (2004), where we
choose $s=2$ and $c=2^{-1/2}$.
b) This result follows from Lemma 1 b) in Kohler and Langer (2020b).
c) This result follows from Lemma 3 in Kim, Ohn and Kim (2019). $\Box$

###  .3 A bound on the gradient

In the proof of Theorem 1 we will apply Theorem 2. For this we need the
following bound on the gradient (with respect to the outer weights) of
$F_{n}$.

###### Lemma 3

Let $F_{n}$ be defined by (18). Then we have

$\|\nabla_{(w_{k})_{k=1,\dots,K_{n}}}F_{n}(\mathbf{w})\|\leq\sqrt{K_{n}}\cdot\beta_{n}.$

Proof. For $k\in\\{1,\dots,K_{n}\\}$ we have

$\displaystyle\frac{\partial F_{n}(\mathbf{w})}{\partial
w_{k}}=\frac{1}{n}\sum_{i=1}^{n}\varphi^{\prime}(Y_{i}\cdot
f_{\mathbf{w}}(X_{i}))\cdot Y_{i}\cdot
T_{\beta_{n}}(f_{\mathbf{W}_{k},\mathbf{V}_{k}}(X_{i})).$

Because of $|\varphi^{\prime}(z)|\leq 1$ we can conclude

$\left|\frac{\partial F_{n}(\mathbf{w})}{\partial w_{k}}\right|\leq\beta_{n}$

and

$\displaystyle\|\nabla_{(w_{k})_{k=1,\dots,K_{n}}}F_{n}(\mathbf{w})\|^{2}=\sum_{k=1}^{K_{n}}\left|\frac{\partial
F_{n}(\mathbf{w})}{\partial w_{k}}\right|^{2}\leq K_{n}\cdot\beta_{n}^{2}.$

$\Box$

###  .4 Generalization error

###### Lemma 4

Let $d_{model}=h\cdot I$ and let ${\cal F}$ be the set of all functions

$(x_{1},\dots,x_{l})\mapsto z_{1,N,1}^{(d+l+2)},$

where $z_{1,N,1}$ is defined in Section 2 depending on

$(W_{query,1,r,s},W_{key,1,r,s},W_{value,1,r,s})_{r\in\\{1,\dots,N\\},s\in\\{1,\dots,h\\}}$
(39)

and on

$(W_{1,r,1},b_{1,r,1},W_{1,r,2},b_{1,r,2})_{r\in\\{1,\dots,N\\}}$ (40)

and where the total number of nonzero components in each row in all the
matrices in (39) is bounded by $\tau\in\mathbb{N}$ and where all matrices
$W_{1,r,1}$ and $W_{1,r,2}$ in (40) have the property that in each row in
$W_{1,r,1}$ and in each column in $W_{1,r,2}$ there are at most $\tau$ nonzero
entries. Let ${\cal G}$ be the set of all (shallow) feedforward neural
networks $g:\mathbb{R}\rightarrow\mathbb{R}$ with one hidden layer and $J_{n}$
hidden neurons and ReLU activation function. Assume

$\max\\{N,d_{key},d_{v},l\\}\leq
c_{16}\quad\mbox{and}\quad\max\\{J_{n},h,I,d_{ff}\\}\leq c_{17}\cdot
n^{c_{17}}.$

Let $A\geq 1$, let $X_{1},\dots,X_{n}$ be independent and identically
distributed $[-A,A]^{d\cdot l}$-valued random vectors and let
$\epsilon_{1},\dots,\epsilon_{n}$ be independent Rademacher random variables,
which are independent from $X_{1},\dots,X_{n}$. Then we have

$\displaystyle{\mathbf{E}}\left\\{\left|\sup_{f\in{\cal G}\circ{\cal
F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f(X_{i}))\right|\right\\}\leq
c_{18}\cdot\frac{\sqrt{\max\\{h\cdot I,d_{ff},J_{n}\\}}\cdot(\log
n)^{2}}{\sqrt{n}}.$

In order to prove Lemma 4 we need the following bound on the covering number.

###### Lemma 5

Define ${\cal F}$ and ${\cal G}$ as in Lemma 4. Let $\beta\geq 0$ and let
$T_{\beta}{\cal G}\circ{\cal F}$ be the set of all functions $g\circ f$
truncated on height $\beta$ and $-\beta$ where $g\in{\cal G}$ and $f\in{\cal
F}$. Then we have for any $0<\epsilon<\beta/2$

$\displaystyle\sup_{z_{1}^{n}\in(\mathbb{R}^{d\cdot
l})^{n}}\log{\mathcal{M}}_{1}(\epsilon,T_{\beta}{\cal G}\circ{\cal
F},z_{1}^{n})$ $\displaystyle\leq c_{19}\cdot\tau\cdot\max\\{h\cdot
I,d_{ff},J_{n}\\}\cdot
N^{3}\cdot\log(\max\\{J_{n},N,h,d_{ff},I,d_{key},d_{v},l,2\\})\log\left(\frac{\beta}{\epsilon}\right).$

In order to prove Lemma 5 we will first show the following bound on the VC-
dimension of subsets of ${\cal F}$, where the nonzero components appear only
at fixed positions.

###### Lemma 6

Let ${\cal F}$ be the set of all functions

$(x_{1},\dots,x_{l})\mapsto z_{1,N,1}^{(d+l+2)},$

where $z_{1,N,1}$ is defined in Section 2 depending on (39) and (40) and where
in all matrics in (39) there are in each row at most $\tau$ fixed components
where the entries are allowed to be nonzero, and where all matrices
$W_{1,r,1}$ and $W_{1,r,2}$ in (40) have the property that in each row in
$W_{1,r,1}$ and in each column in $W_{1,r,2}$ there are at most $\tau$ fixed
components (depending on $r$) where the entries are allowed to be nonzero. Let
${\cal G}$ be defined as in Lemma 4. Then we have

$V_{({\cal G}\circ{\cal F})^{+}}\leq c_{20}\cdot\tau\cdot\max\\{h\cdot
I,d_{ff},J_{n}\\}\cdot
N^{3}\cdot\log(\max\\{J_{n},N,h,d_{ff},d_{key},d_{v},l,2\\}).$

The proof of Lemma 6 is a modification of the proof of Lemma 9 in Gurevych,
Kohler and Sarin (2022), which in turn is based on the proof of Theorem 6 in
Bartlett et al. (1999). In the proof of Lemma 6 we will need the following two
auxiliary results.

###### Lemma 7

Suppose $W\leq m$ and let $f_{1},...,f_{m}$ be polynomials of degree at most
$D$ in $W$ variables. Define

$K:=|\\{\left(sgn(f_{1}(\mathbf{a})),\dots,sgn(f_{m}(\mathbf{a}))\right):\mathbf{a}\in\mathbb{R}^{W}\\}|.$

Then we have

$K\leq 2\cdot\left(\frac{2\cdot e\cdot m\cdot D}{W}\right)^{W}.$

Proof. See Theorem 8.3 in Anthony and Bartlett (1999). $\Box$

###### Lemma 8

Suppose that $2^{m}\leq 2^{L}\cdot(m\cdot R/w)^{w}$ for some $R\geq 16$ and
$m\geq w\geq L\geq 0$. Then,

$m\leq L+w\cdot\log_{2}(2\cdot R\cdot\log_{2}(R)).$

Proof. See Lemma 16 in Bartlett et al. (2019). $\Box$

Proof of Lemma 6. Let ${\cal H}$ be the set of all functions $h$ defined by

$h:\mathbb{R}^{d\cdot l}\times\mathbb{R}\rightarrow\mathbb{R},\quad
h(x,y)=g(x)-y$

for some $g\in{\cal G}\circ{\cal F}$. Let $(x_{1},y_{1})$,
…$(x_{m},y_{m})\in\mathbb{R}^{d\cdot l}\times\mathbb{R}$ be such that

$|\\{(sgn(h(x_{1},y_{1})),\dots,sgn(h(x_{m},y_{m})))\,:\,h\in{\cal
H}\\}|=2^{m}.$ (41)

It suffices to show

$m\leq c_{20}\cdot\tau\cdot\max\\{h\cdot I,d_{ff},J_{n}\\}\cdot
N^{3}\cdot\log(\max\\{J_{n},N,h,d_{ff},d_{key},d_{v},l,2\\}).$ (42)

To show this we partition ${\cal G}\circ{\cal F}$ in subsets such that for
each subset all

$g\circ f(x_{i})\quad(i=1,\dots,m)$

are polynomials of some fixed degree and use Lemma 7 in order to derive an
upper bound on the left-hand side of (41). This upper bound will depend
polynomially on $m$ which will enable us to conclude (42) by an application of
Lemma 8.

Let

$\displaystyle\bar{\theta}$ $\displaystyle=$
$\displaystyle\Bigg{(}(W_{query,r,s},W_{key,r,s},W_{value,r,s})_{r\in\\{1,\dots,N\\},s\in\\{1,\dots,h\\}},$
$\displaystyle\quad(W_{r,1},b_{r,1},W_{r,2},b_{r,2})_{r\in\\{1,\dots,N\\}},(v_{r}^{(1)})_{r\in\\{1,\dots,J_{n}\\}},(v_{r,s}^{(0)})_{r\in\\{1,\dots,J_{n}\\},s\in\\{0,1\\}}\Bigg{)}$

be the parameters which determine a function in ${\cal G}\circ{\cal F}$. By
assumption, each function in ${\cal G}\circ{\cal F}$ can be also described by
such a parameter vector. Here only

$\bar{L}_{n}=N\cdot h\cdot(2\cdot
d_{key}+d_{v})\cdot\tau+N\cdot(d_{ff}\cdot(\tau+1)+h\cdot
I\cdot(\tau+1))+3\cdot J_{n}$

components of the matrices and vectors occuring in the parameter vector are
allowed to be nonzero and the positions where these nonzero parameters can
occur are fixed. Denote the vector in $\mathbb{R}^{\bar{L}_{n}}$ which
contains all values of these possible nonzero parameters by $\theta$. Then we
can write

${\cal G}\circ{\cal F}=\\{g(\cdot,\theta):\mathbb{R}^{d\cdot
l}\rightarrow\mathbb{R}\,:\,\theta\in\mathbb{R}^{\bar{L}_{n}}\\}.$

In the sequel we construct a partition ${\cal P}_{N+1}$ of
$\mathbb{R}^{\bar{L}_{n}}$ such that for all $S\in{\cal P}_{N+1}$ we have that

$g(x_{1},\theta),\dots,g(x_{m},\theta)$

(considered as functions of $\theta$) are polynomials of degree at most
$8^{N}+2$ for $\theta\in S$.

In order to construct this partition we construct first recursively partitions
${\cal P}_{0}$, …, ${\cal P}_{N}$ of $\mathbb{R}^{\bar{L}_{n}}$ such that for
each $r\in\\{1,\dots,N\\}$ and all $S\in{\cal P}_{r}$ all components in

$z_{r}=z_{r}(x)\quad(x\in\\{x_{1},\dots,x_{m}\\})$

(considered as a function of $\theta$) are polynomials of degree at most
$8^{r}$ in $\theta$ for $\theta\in S$.

Since all components of $z_{0}$ are constant as functions of $\theta$ this
holds for $r=0$ if we set ${\cal P}_{0}=\\{\mathbb{R}^{\bar{L}_{n}}\\}$.

Let $r\in\\{1,\dots,N\\}$ and assume that for all $S\in{\cal P}_{r-1}$ all
components in

$z_{r-1}(x)\quad(x\in\\{x_{1},\dots,x_{m}\\})$

(considered as a function of $\theta$) are polynomials of degree at most
$8^{r-1}$ in $\theta$ for $\theta\in S$. Then all components in

$q_{r-1,s,i}(x),k_{r-1,s,i}(x)\quad\mbox{and}\quad
v_{r-1,s,i}(x)\quad(x\in\\{x_{1},\dots,x_{m}\\})$

are on each set $S\in{\cal P}_{r-1}$ polynomials of degree at most
$8^{r-1}+1$. Consequently, for each $S\in{\cal P}_{r-1}$ each value

$<q_{r-1,s,i}(x),k_{r-1,s,j}(x)>\quad(x\in\\{x_{1},\dots,x_{m}\\})$

is (considered as a function of $\theta$) a polynomial of degree at most
$2\cdot 8^{r-1}+2$ for $\theta\in S$. Application of Lemma 7 yields that

$<q_{r-1,s,i}(x),k_{r-1,s,j_{1}}(x)>-<q_{r-1,s,i}(x),k_{r-1,s,j_{2}}(x)>$

$(s\in\\{1,\dots,h\\},i,j_{1},j_{2}\in\\{1,\dots,l\\},x\in\\{x_{1},\dots,x_{m}\\})$
has at most

$\Delta=2\cdot\left(\frac{2\cdot e\cdot h\cdot l^{3}\cdot m\cdot(2\cdot
8^{r-1}+2)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$

different sign patterns. If we partition each set in ${\cal P}_{r-1}$
according to these sign patterns in $\Delta$ subsets, then on each set in the
new partition all components in

$v_{r-1,s,\hat{j}_{r-1,s,i}}(x)\cdot<q_{r-1,s,i}(x),k_{r-1,s,\hat{j}_{r-1,s,i}}(x)>\quad(x\in\\{x_{1},\dots,x_{m}\\})$

are polynomials of degree at most $3\cdot 8^{r-1}+3$ (since on each such set

$<q_{r-1,s,i}(x),k_{r-1,s,\hat{j}_{r-1,s,i}}(x)>$

is equal to one of the $<q_{r-1,s,i}(x),k_{r-1,s,j}(x)>$). On each set within
this partition every component of the $\mathbb{R}^{d_{ff}}$-valued vectors

$W_{r,1}\cdot
y_{r,s}(x)+b_{r,1}\quad(s=1,\dots,h,x\in\\{x_{1},\dots,x_{m}\\})$

is (considered as a function of $\theta$) a polynomial of degree at most
$3\cdot 8^{r-1}+4$.

By another application of Lemma 7 we can refine each set in this partition
into

$2\cdot\left(\frac{2\cdot e\cdot h\cdot d_{ff}\cdot m\cdot(3\cdot
8^{r-1}+4)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$

sets such that all components in

$W_{r,1}\cdot y_{r,s}(x)+b_{r,1}\quad(x\in\\{x_{1},\dots,x_{m}\\})$ (43)

have the same sign patterns within the refined partition. We call this refined
partition ${\cal P}_{r}$. Since on each set of ${\cal P}_{r}$ the sign of all
components in (43) does not change we can conclude that all components in

$\sigma(W_{r,1}\cdot y_{r,s}(x)+b_{r,1})\quad(x\in\\{x_{1},\dots,x_{m}\\})$
(44)

are either equal to zero or they are equal to a polynomial of degree at most
$3\cdot 8^{r-1}+4$. Consequently we have that on each set in ${\cal P}_{r}$
all components of

$z_{r}(x)\quad(x\in\\{x_{1},\dots,x_{m}\\})$

are equal to a polynomial of degree at most $3\cdot 8^{r-1}+5\leq 8^{r}$.

The partition ${\cal P}_{N}$ satisfies

$|{\cal P}_{N}|=\prod_{r=1}^{N}\frac{|{\cal P}_{r}|}{|{\cal
P}_{r-1}|}\leq\prod_{r=1}^{N}2\cdot\left(\frac{2\cdot e\cdot h\cdot l^{3}\cdot
m\cdot 8^{r}}{\bar{L}_{n}}\right)^{\bar{L}_{n}}\cdot 2\cdot\left(\frac{2\cdot
e\cdot h\cdot d_{ff}\cdot m\cdot 8^{r}}{\bar{L}_{n}}\right)^{\bar{L}_{n}}.$

Next we construct a partition ${\cal P}_{N+1}$ of $\mathbb{R}^{\bar{L}_{n}}$
such that for all $S\in{\cal P}_{N+1}$

$g(z_{N,1}^{(d+l+2)}(x))=\sum_{j=1}^{J_{n}}v_{j}^{(1)}\cdot\sigma\left(v_{j,1}^{(0)}\cdot
z_{N,1}^{(d+l+2)}(x)+v_{j,0}^{(0)}\right)\quad(x\in\\{x_{1},\dots,x_{m}\\})$

(considered as a function of $\theta$) is a polynomial of degree at most
$8^{N}+2$ for $\vartheta\in S$.

For all $S\in{\cal P}_{N}$ all components in

$\left(v_{j,1}^{(0)}\cdot
z_{N,1}^{(d+l+2)}(x)+v_{j,0}^{(0)}\right)_{j=1,\dots,J_{n}}\quad(x\in\\{x_{1},\dots,x_{m}\\})$

(considered as a function of $\theta$) are polynomials of degree at most
$8^{N}+1$. Application of Lemma 7 implies

$v_{j,1}^{(0)}\cdot
z_{N,1}^{(d+l+2)}(x)+v_{j,0}^{(0)}\quad(j\in\\{1,\dots,J_{n}\\},x\in\\{x_{1},\dots,x_{m}\\})$

has at most

$\Delta=2\cdot\left(\frac{2\cdot e\cdot J_{n}\cdot
m\cdot(8^{N}+1)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$

different sign patterns. If we partition in each set in ${\cal P}_{N}$
according to these sign patterns in $\Delta$ subsets, then on each set in the
new partition ${\cal P}_{N+1}$ all components in

$\sigma\left(v_{j,1}^{(0)}\cdot
z_{N,1}^{(d+l+2)}(x)+v_{j,0}^{(0)}\right)\quad(j\in\\{1,\dots,J_{n}\\},x\in\\{x_{1},\dots,x_{m}\\})$

are polynomials of degree at most $8^{N}+1$ (since after the application of
$\sigma(z)=\max\\{z,0\\}$ the component is either equal to zero on the set or
equal to the argument of $\sigma$). Consequently on each set in ${\cal
P}_{N+1}$

$g(x,\theta)=\sum_{j=1}^{J_{n}}v_{j}^{(1)}(x)\cdot\sigma\left(v_{j,1}^{(0)}\cdot(z_{N,1}^{(d+l+2)}+v_{j,0}^{(0)}\right)\quad(x\in\\{x_{1},\dots,x_{m}\\})$

(considered as a function of $\theta$) is a polynomial of degree $8^{N}+2$.

The partition ${\cal P}_{N+1}$ satisfies

$\displaystyle|{\cal P}_{N+1}|$ $\displaystyle=$ $\displaystyle\frac{|{\cal
P}_{N+1}|}{|{\cal P}_{N}|}\cdot|{\cal P}_{N}|$ $\displaystyle\leq$
$\displaystyle 2\cdot\left(\frac{2\cdot e\cdot J_{n}\cdot
m\cdot(8^{N}+1)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}\cdot\Bigg{(}\prod_{r=1}^{N}2\cdot\left(\frac{2\cdot
e\cdot h\cdot l^{3}\cdot m\cdot 8^{r}}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$
$\displaystyle\hskip 56.9055pt\cdot 2\cdot\left(\frac{2\cdot e\cdot h\cdot
d_{ff}\cdot m\cdot 8^{r}}{\bar{L}_{n}}\right)^{\bar{L}_{n}}\Bigg{)}$

and has the property that for all $S\in{\cal P}_{N+1}$ and for all
$(x,y)\in\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$

$g(x)=g(x,\theta)\quad\mbox{and}\quad h(x,y)=g(x,\theta)-y$

(considered as a function of $\theta$) are polynomials of degree at most
$8^{N}+2$ in $\theta$ for $\theta\in S$.

Using

$\displaystyle|\\{(sgn(h(x_{1},y_{1})),\dots,sgn(h(x_{m},y_{m})))\,:\,h\in{\cal
H}\\}|$ $\displaystyle\leq\sum_{S\in{\cal
P}_{N+1}}|\\{(sgn(g(x_{1},\theta)-y_{1}),\dots,sgn(g(x_{m},\theta)-y_{m}))\,:\,\theta\in
S\\}|$

we can apply one more time Lemma 7 to conclude

$\displaystyle 2^{m}$
$\displaystyle=|\\{(sgn(h(x_{1},y_{1})),\dots,sgn(h(x_{m},y_{m})))\,:\,h\in{\cal
H}\\}|$ $\displaystyle\leq|{\cal P}_{N+1}|\cdot 2\cdot\left(\frac{2\cdot
e\cdot m\cdot(8^{N}+2)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$ $\displaystyle\leq
2\cdot\left(\frac{2\cdot e\cdot
m\cdot(8^{N}+2)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}\cdot\Bigg{(}\prod_{r=1}^{N}2\cdot\left(\frac{2\cdot
e\cdot h\cdot l^{3}\cdot m\cdot 8^{r}}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$
$\displaystyle\hskip 28.45274pt\cdot 2\cdot\left(\frac{2\cdot e\cdot h\cdot
d_{ff}\cdot m\cdot 8^{r}}{\bar{L}_{n}}\right)^{\bar{L}_{n}}\Bigg{)}\cdot
2\cdot\left(\frac{2\cdot e\cdot J_{n}\cdot
m\cdot(8^{N}+1)}{\bar{L}_{n}}\right)^{\bar{L}_{n}}$ $\displaystyle\leq
2^{2\cdot N+2}\cdot$ $\displaystyle\left(\frac{m\cdot
2e\cdot(2N+2)\cdot\max\\{J_{n},h\\}\cdot(\max\\{l,d_{ff}\\})^{3}\cdot(8^{N}+2)}{(2N+2)\cdot\bar{L}_{n}}\right)^{(2N+2)\cdot\bar{L}_{n}}.$

Assume $m\geq(2N+2)\cdot(N\cdot h\cdot(2\cdot
d_{key}+d_{v})\cdot\tau+N\cdot(d_{ff}\cdot(\tau+1)+h\cdot
I\cdot(\tau+1))+3\cdot J_{n})$. Application of Lemma 8 with $L=2\cdot N+2$,
$R=2e\cdot(2N+2)\cdot\max\\{J_{n},h\\}\cdot(\max\\{l,d_{ff}\\})^{3}\cdot(8^{N}+2)$
and $w=(2N+2)\cdot\bar{L}_{n}$ yields

$\displaystyle m$ $\displaystyle\leq$ $\displaystyle(2\cdot
N+2)+(2N+2)\cdot\bar{L}_{n}\cdot\log_{2}(2\cdot R\cdot\log_{2}(R))$
$\displaystyle\leq$ $\displaystyle c_{21}\cdot\tau\cdot\max\\{h\cdot
I,d_{ff},J_{n}\\}\cdot N^{3}\cdot\log(\max\\{J_{n},N,h,d_{ff},l,2\\}),$

which implies (42). $\Box$

Proof of Lemma 5. The functions in the function set $T_{\beta}{\cal
G}\circ{\cal F}$ depend on at most

$\lceil c_{22}\cdot(N\cdot h^{2}+J_{n})\cdot
I\cdot\max\\{d_{k},d_{ff},d_{v}\\}\rceil$

many parameters, and of these parameters at most

$\bar{L}_{n}=N\cdot h\cdot(2\cdot
d_{key}+d_{v})\cdot\tau+N\cdot(d_{ff}\cdot(\tau+1)+h\cdot
I\cdot(\tau+1))+3\cdot J_{n}$

are allowed to be nonzero. We have

$\displaystyle\left({\lceil c_{22}\cdot(N\cdot h^{2}+J_{n})\cdot
I\cdot\max\\{d_{key},d_{ff},d_{v}\\}\rceil\atop\bar{L}_{n}}\right)$
$\displaystyle\leq\left(\lceil c_{22}\cdot(N\cdot h^{2}+J_{n})\cdot
I\cdot\max\\{d_{key},d_{ff},d_{v}\\}\rceil\right)^{\bar{L}_{n}}$

many possibilities to choose these positions. If we fix these positions, we
get one function space ${\cal G}\circ{\cal F}$ for which we can bound its VC
dimension by Lemma 6. Using Lemma 6, $V_{(T_{\beta}{\cal G}\circ{\cal
F})^{+}}\leq V_{({\cal G}\circ{\cal F})^{+}},$ and Theorem 9.4 in Györfi et
al. (2002) we get

$\displaystyle\mathcal{M}_{1}\left(\epsilon,T_{\beta}{\cal G}\circ{\cal
F},\mathbf{x}_{1}^{n}\right)$ $\displaystyle\leq$ $\displaystyle
3\cdot\left(\frac{4e\cdot\beta}{\epsilon}\cdot\log\frac{6e\cdot\beta}{\epsilon}\right)^{V_{(T_{\beta}{\cal
G}\circ{\cal F})^{+}}}$ $\displaystyle\leq$ $\displaystyle
3\cdot\left(\frac{6e\cdot\beta}{\epsilon}\right)^{2\cdot
c_{20}\cdot\tau\cdot\max\\{h\cdot I,d_{ff},J_{n}\\}\cdot
N^{3}\cdot\log(\max\\{J_{n},N,h,d_{ff},d_{key},d_{v},l,2\\})}.$

From this we conclude

$\displaystyle\sup_{z_{1}^{n}\in(\mathbb{R}^{d\cdot
l})^{n})}\log{\mathcal{M}}_{1}(\epsilon,T_{\beta}{\cal G}\circ{\cal
F},z_{1}^{n})$ $\displaystyle\leq\bar{L}_{n}\cdot\log\left(\lceil
c_{22}\cdot(N\cdot h^{2}+J_{n})\cdot
I\cdot\max\\{d_{key},d_{ff},d_{v}\\}\rceil\right)$ $\displaystyle\quad+2\cdot
c_{20}\cdot\tau\cdot\max\\{h\cdot I,d_{ff},J_{n}\\}\cdot
N^{3}\cdot\log(\max\\{J_{n},N,h,d_{ff},d_{key},d_{v},l,2\\})\cdot\log\left(\frac{\beta}{\epsilon}\right)$
$\displaystyle\leq c_{23}\cdot\tau\cdot\max\\{h\cdot I,d_{ff},J_{n}\\}\cdot
N^{3}\cdot\log(\max\\{J_{n},N,h,I,d_{ff},d_{key},d_{v},2\\})\cdot\log\left(\frac{\beta}{\epsilon}\right).$

$\Box$

Proof of Lemma 4. For $\delta_{n}>0$ we have

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal G}\circ{\cal
F}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f(X_{i}))\right|\right\\}$
$\displaystyle=\int_{0}^{\infty}{\mathbf{P}}\left\\{\sup_{f\in{\cal
G}\circ{\cal
F}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f(X_{i}))\right|>t\right\\}\,dt$
$\displaystyle\leq\delta_{n}+\int_{\delta_{n}}^{\infty}{\mathbf{P}}\left\\{\sup_{f\in{\cal
G}\circ{\cal
F}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f(X_{i}))\right|>t\right\\}\,dt.$

Using a standard covering argument from empirical process theory we see that
for any $\beta_{n}\geq t\geq\delta_{n}$ we have

$\displaystyle{\mathbf{P}}\left\\{\sup_{f\in{\cal G}\circ{\cal
F}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f(X_{i}))\right|>t\right\\}$
$\displaystyle\leq\sup_{x_{1}^{n}\in(\mathbb{R}^{d\cdot
l})^{n}}{\mathcal{M}}_{1}\left(\frac{\delta_{n}}{2},\left\\{T_{\beta_{n}}f:f\in{\cal
G}\circ{\cal F}\right\\},x_{1}^{n}\right)$ $\displaystyle\hskip
85.35826pt\cdot\sup_{f\in{\cal G}\circ{\cal
F}}{\mathbf{P}}\left\\{\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f(X_{i}))\right|>\frac{t}{2}\right\\}.$

By Lemma 5 we know

$\sup_{x_{1}^{n}\in(\mathbb{R}^{d\cdot
l})^{n}}{\mathcal{M}}_{1}\left(\frac{\delta_{n}}{2},\left\\{T_{\beta_{n}}f:f\in{\cal
G}\circ{\cal F}\right\\},x_{1}^{n}\right)\leq
c_{24}\cdot\left(\frac{c_{25}\cdot\beta_{n}}{\delta_{n}}\right)^{c_{26}\cdot\max\\{h\cdot
I\cdot d_{ff},J_{n}\\}\cdot\log(n)}.$

By the inequality of Hoeffding (cf., e.g., Lemma A.3 in Györfi et al. (2002))
and

$|T_{\beta_{n}}(f(x))|\leq\beta_{n}\quad(x\in\mathbb{R}^{d})$

we have for any $f\in{\cal G}\circ{\cal F}$

${\mathbf{P}}\left\\{\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot
T_{\beta_{n}}(f(X_{i}))\right|>t\right\\}\leq 2\cdot\exp\left(-\frac{2\cdot
n\cdot t^{2}}{4\cdot\beta_{n}^{2}}\right).$

Hence we get

$\displaystyle{\mathbf{E}}\left\\{\sup_{f\in{\cal G}\circ{\cal
F}}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\cdot(T_{\beta_{n}}(f(X_{i}))\right|\right\\}$
$\displaystyle\leq\delta_{n}+\int_{\delta_{n}}^{\beta_{n}}c_{24}\cdot\left(\frac{c_{25}\cdot\beta_{n}}{\delta_{n}}\right)^{c_{26}\cdot\max\\{h\cdot
I\cdot d_{ff},J_{n}\\}\cdot\log(n)}\cdot 2\cdot\exp\left(-\frac{2\cdot n\cdot
t^{2}}{4\cdot\beta_{n}^{2}}\right)\,dt$
$\displaystyle\leq\delta_{n}+\int_{\delta_{n}}^{\beta_{n}}c_{24}\cdot\left(\frac{c_{25}\cdot\beta_{n}}{\delta_{n}}\right)^{c_{26}\cdot\max\\{h\cdot
I\cdot d_{ff},J_{n}\\}\cdot\log(n)}\cdot
2\cdot\exp\left(-\frac{n\cdot\delta_{n}\cdot
t}{2\cdot\beta_{n}^{2}}\right)\,dt$
$\displaystyle\leq\delta_{n}+c_{24}\cdot\left(\frac{c_{25}\cdot\beta_{n}}{\delta_{n}}\right)^{c_{26}\cdot\max\\{h\cdot
I\cdot
d_{ff},J_{n}\\}\cdot\log(n)}\frac{4\cdot\beta_{n}^{2}}{n\cdot\delta_{n}}\cdot\exp\left(-\frac{n\cdot\delta_{n}^{2}}{2\cdot\beta_{n}^{2}}\right).$

With

$\delta_{n}=\sqrt{\max\\{h\cdot I\cdot d_{ff},J_{n}\\}}\cdot\log
n\cdot\sqrt{\frac{2\cdot\beta_{n}^{2}}{n}}$

we get the assertion. $\Box$

###  .5 Approximation error

###### Lemma 9

Let $\tau\in\\{l+1,l+2,\dots,l+d+1\\}$. Let $l,h,I\in\mathbb{N}$ and set
$d_{model}=h\cdot I$. Let $d_{key}\geq 3$. Set $d_{v}=d_{model}/h=I$. Let
$s_{0}\in\\{1,\dots,h\\}$, $s_{1},s_{2}\in\\{1,\dots,d_{model}\\}$,
$j\in\\{1,\dots,l\\}$, $k\in\\{1,\dots,l\\}\setminus\\{j\\}$,
$s_{3}\in\\{(s_{0}-1)\cdot d_{v}+1,\dots,s_{0}\cdot d_{v}\\}$,
$\beta\in\mathbb{R}$, $\delta\geq 0$ and

$B\geq 168\cdot d_{key}\cdot\tau^{2}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{2}\cdot\max\\{\delta^{2},1\\},\quad
0\leq\epsilon\leq\min\left\\{1,\frac{1}{36\cdot\tau\cdot\|z_{0}\|_{\infty}^{2}}\right\\}.$
(45)

Then there exist

$\mathbf{W}_{query,0,s_{0}},\quad\mathbf{W}_{key,0,s_{0}}\quad\mbox{and}\quad\mathbf{W}_{value,0,s_{0}}$

such that in each row of the above matrices at most $\tau$ of its entries are
not equal to zero, such that in the last two rows of
$\mathbf{W}_{query,0,s_{0}}$ and $\mathbf{W}_{key,0,s_{0}}$ all entries in any
column greater than $d+1+l$ are zero, such that all entries are bounded in
absolute value by $2\cdot B$, and such that we have for all
$z_{0,r},\tilde{z}_{0,r}\in\mathbb{R}^{d_{model}}$ satisfying

$z_{0,r}^{(s)}=\tilde{z}_{0,r}^{(s)}=\begin{cases}x_{r}^{(s)}&\mbox{if
}s\in\\{1,\dots,d\\},\\\ 1&\mbox{if }s=d+1,\\\ \delta_{s-d-1,r}&\mbox{if
}s\in\\{d+2,\dots,d+1+l\\}\\\ \end{cases}$ (46)

$(r\in\\{1,\dots,l\\})$ and

$\|\tilde{z}_{0,r}-z_{0,r}\|_{\infty}\leq\delta,$

$(r\in\\{1,\dots,l\\})$ and all

$\tilde{\mathbf{W}}_{query,0,s},\quad\tilde{\mathbf{W}}_{key,0,s}\quad\mbox{and}\quad\tilde{\mathbf{W}}_{value,0,s}$

$(s\in\\{1,\dots,h\\})$ which satisfy

$\|\tilde{\mathbf{W}}_{query,0,s_{0}}-\mathbf{W}_{query,0,s_{0}}\|_{\infty}\leq\epsilon,$
$\|\tilde{\mathbf{W}}_{key,0,s_{0}}-\mathbf{W}_{key,0,s_{0}}\|_{\infty}\leq\epsilon,$
$\|\tilde{\mathbf{W}}_{value,0,s_{0}}-\mathbf{W}_{value,0,s_{0}}\|_{\infty}\leq\epsilon,$

and where in the last two rows of $\tilde{\mathbf{W}}_{query,0,s_{0}}$ and
$\tilde{\mathbf{W}}_{key,0,s_{0}}$ all entries in any column greater than
$d+l+1$ are zero and where in
$\tilde{\mathbf{W}}_{query,0,s_{0}}-\mathbf{W}_{query,0,s_{0}}$,
$\tilde{\mathbf{W}}_{key,0,s_{0}}-\mathbf{W}_{key,0,s_{0}}$ and
$\tilde{\mathbf{W}}_{value,0,s_{0}}-\mathbf{W}_{value,0,s_{0}}$ in each row at
most $\tau$ entries are nonzero, that the following holds:

If we set for $s\in\\{1,\dots,h\\}$, $i\in\\{1,\dots,l\\}$

$q_{0,s,i}=\tilde{W}_{query,0,s}\cdot\tilde{z}_{0,i},\quad
k_{0,s,i}=\tilde{W}_{key,0,s}\cdot\tilde{z}_{0,i}\quad\mbox{and}\quad
v_{0,s,i}=\tilde{W}_{value,0,s}\cdot\tilde{z}_{0,i},$
$\hat{j}_{s,i}=\arg\max_{j\in\\{1,\dots,l\\}}<q_{0,s,i},k_{0,s,j}>,$
$\bar{y}_{0,s,i}=v_{0,s,\hat{j}_{s,i}}\cdot<q_{0,s,i},k_{0,s,\hat{j}_{s,i}}>,$
$\bar{y}_{0,i}=(\bar{y}_{0,1,i},\dots,\bar{y}_{0,h,i})$

and

$\tilde{y}_{0,i}=\tilde{z}_{0,i}+\bar{y}_{0,i}$

then we have:

$\hat{j}_{s_{0},1}=j,\quad\hat{j}_{s_{0},r}=k\quad\mbox{if }r>1,$ (47)
$\displaystyle|\tilde{y}_{0,1}^{(s_{3})}-(z_{0,1}^{(s_{3})}+z_{0,1}^{(s_{1})}\cdot(z_{0,j}^{(s_{2})}+\beta))|$
$\displaystyle\leq 136\cdot d_{key}\cdot\tau^{3}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{3}\cdot
B\cdot\max\\{\delta^{3},1\\}\cdot\epsilon$
$\displaystyle\quad+25\cdot\tau\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{\delta,1\\}\cdot\delta$
(48)

and

$\displaystyle|\tilde{y}_{0,r}^{(s)}|$ $\displaystyle\leq$ $\displaystyle
136\cdot d_{key}\cdot\tau^{3}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{3}\cdot
B\cdot\max\\{\delta^{3},1\\}\cdot\epsilon$ (49)
$\displaystyle\quad+25\cdot\tau\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{\delta,1\\}\cdot\delta$

whenever $r>1$ or $s\in\\{(s_{0}-1)\cdot d_{v}+1,\dots,s_{0}\cdot
d_{v}\\}\setminus\\{s_{3}\\}$.

Proof of Lemma 9. W.l.o.g. we assume $d_{key}=3$.

In the first step of the proof we define $\mathbf{W}_{query,0,s_{0}}$,
$\mathbf{W}_{key,0,s_{0}}$ and $\mathbf{W}_{value,0,s_{0}}$ and present some
of their properties.

Set

$W_{query,0,s_{0}}=\left(\begin{array}[]{cccccccccccccccc}0&\dots&0&0&0&0&0&\dots&0&0&\dots&0&1&0&\dots&0\\\
0&\dots&0&-B&0&0&0&\dots&0&0&\dots&0&0&0&\dots&0\\\
0&\dots&0&0&0&1&1&\dots&1&0&\dots&0&0&0&\dots&0\\\ \end{array}\right)$

where all columns are zero except columns number $d+1$, $d+3$, $d+4$, …,
$d+1+l$ and $s_{1}$,

$\displaystyle W_{key,0,s_{0}}=$
$\displaystyle\left(\begin{array}[]{cccccccccccccccccccccc}0&\dots&0&\beta&0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&\dots&0&1&0&\dots&0\\\
0&\dots&0&0&1&\dots&1&1&1&\dots&1&0&1&\dots&1&0&\dots&0&0&0&\dots&0\\\
0&\dots&0&0&0&\dots&0&2\cdot
B&0&\dots&0&0&0&\dots&0&0&\dots&0&0&0&\dots&0\end{array}\right)$

where in the first row only the entries in columns $d+1$ and $s_{2}$ are
nonzero, where in the second row only the entries in columns $d+2$, $d+3$, …,
$d+1+j-1$, $d+1+j+1$, $d+1+j+2$, …, $d+1+l$ are nonzero, and where in the
third row only the entry in column $d+1+k$ is nonzero, and

$W_{value,0,s_{0}}=\left(\begin{array}[]{ccccccc}0&\dots&0&0&0&\dots&0\\\
\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots\\\ 0&\dots&0&0&0&\dots&0\\\
0&\dots&0&1&0&\dots&0\\\ 0&\dots&0&0&0&\dots&0\\\
\vdots&\dots&\vdots&\vdots&\vdots&\dots&\vdots\\\ 0&\dots&0&0&0&\dots&0\\\
\end{array}\right)$

where all rows and all columns are zero except column number $d+1+j$ and row
number $s_{3}-(s_{0}-1)\cdot d_{v}$.

Then we have

$W_{query,0,s_{0}}\cdot
z_{0,r_{1}}=\left(\begin{matrix}z_{0,r_{1}}^{(s_{1})}\\\ -B\\\
\sum_{i=2}^{l}\delta_{r_{1},i}\end{matrix}\right),\quad W_{key,0,s_{0}}\cdot
z_{0,r_{2}}=\left(\begin{matrix}\beta+z_{0,r_{2}}^{(s_{3})}\\\
\sum_{i\in\\{1,\dots,l\\}\setminus\\{j\\}}\delta_{r_{2},i}\\\
\delta_{r_{2},k}\cdot 2\cdot B\end{matrix}\right)$

and

$W_{value,0,s_{0}}\cdot
z_{0,r_{2}}=\delta_{r_{2},j}\cdot\mathbf{e}_{s_{3}-(s_{0}-1)\cdot d_{v}}$

where $\mathbf{e}_{r}$ denotes the $r$-th unit vector in $\mathbb{R}^{d_{v}}$.
Hence

$\displaystyle<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>$
$\displaystyle=z_{0,r_{1}}^{(s_{1})}\cdot(\beta+z_{0,r_{2}}^{(s_{3})})-B\cdot\sum_{i\in\\{1,\dots,l\\}\setminus\\{j\\}}\delta_{r_{2},i}+\sum_{i=2}^{l}\delta_{r_{1},i}\cdot\delta_{r_{2},k}\cdot
2\cdot B,$

which implies

$<W_{query,0,s_{0}}z_{0,1},W_{key,0,s_{0}}z_{0,j}>\quad=\quad
z_{0,1}^{(s_{1})}\cdot(\beta+z_{0,j}^{(s_{2})}),$ (51)

for $r_{2}\neq j$

$<W_{query,0,s_{0}}z_{0,1},W_{key,0,s_{0}}z_{0,r_{2}}>\quad=\quad
z_{0,1}^{(s_{1})}\cdot(\beta+z_{0,r_{2}}^{(s_{2})})-B,$

for $r_{1}>1$

$<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,k}>\quad=\quad
z_{0,r_{1}}^{(s_{1})}\cdot(\beta+z_{0,k}^{(s_{2})})+B,$

and for $r_{1}>1$, $r_{2}\in\\{1,\dots,l\\}\setminus\\{k\\}$

$<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>\quad=\quad
z_{0,r_{1}}^{(s_{1})}\cdot(\beta+z_{0,r_{2}}^{(s_{2})})-B\cdot(1-\delta_{r_{2},j}).$

Because of

$B>4\cdot\max_{r_{1},r_{2}}|z_{0,r_{1}}^{(s_{1})}\cdot(\beta+z_{0,r_{2}}^{(s_{2})})|$

we conclude

$\displaystyle<W_{query,0,s_{0}}z_{0,1},W_{key,0,s_{0}}z_{0,j}>$
$\displaystyle>\frac{B}{2}+\max_{r_{2}\neq
j}<W_{query,0,s_{0}}z_{0,1},W_{key,0,s_{0}}z_{0,r_{2}}>$ (52)

and for $r_{1}>1$

$\displaystyle<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,k}>$
$\displaystyle>\frac{B}{2}+\max_{r_{2}\neq
k}<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>.$ (53)

Furthermore we have

$W_{value,0,s_{0}}z_{0,r}=\delta_{r,j}\cdot\mathbf{e}_{s_{3}-(s_{0}-1)\cdot
d_{v}}.$ (54)

In the second step of the proof we bound the difference between

$<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>\quad\mbox{and}\quad<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>.$

We have

$\displaystyle|<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>-<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle=|<(\tilde{W}_{query,0,s_{0}}-W_{query,0,s_{0}})\tilde{z}_{0,r_{1}}+W_{query,0,s_{0}}(\tilde{z}_{0,r_{1}}-z_{0,r_{1}})+W_{query,0,s_{0}}z_{0,r_{1}},$
$\displaystyle\hskip
56.9055pt(\tilde{W}_{key,0,s_{0}}-W_{key,0,s_{0}})\tilde{z}_{0,r_{2}}+W_{key,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})+W_{key,0,s_{0}}z_{0,r_{2}}>$
$\displaystyle\quad-<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle\leq|<(\tilde{W}_{query,0,s_{0}}-W_{query,0,s_{0}})\tilde{z}_{0,r_{1}}),(\tilde{W}_{key,0,s_{0}}-W_{key,0,s_{0}})\tilde{z}_{0,r_{2}}>|$
$\displaystyle\quad+|<(\tilde{W}_{query,0,s_{0}}-W_{query,0,s_{0}})\tilde{z}_{0,r_{1}}),W_{key,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})>|$
$\displaystyle\quad+|<(\tilde{W}_{query,0,s_{0}}-W_{query,0,s_{0}})\tilde{z}_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle\quad+|<W_{query,0,s_{0}}(\tilde{z}_{0,r_{1}}-z_{0,r_{1}}),(\tilde{W}_{key,0,s_{0}}-W_{key,0,s_{0}})\tilde{z}_{0,r_{2}}>|$
$\displaystyle\quad+|<W_{query,0,s_{0}}(\tilde{z}_{0,r_{1}}-z_{0,r_{1}}),W_{key,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})>|$
$\displaystyle\quad+|<W_{query,0,s_{0}}(\tilde{z}_{0,r_{1}}-z_{0,r_{1}}),W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle\quad+|<W_{query,0,s_{0}}z_{0,r_{1}},(\tilde{W}_{key,0,s_{0}}-W_{key,0,s_{0}})\tilde{z}_{0,r_{2}}>|$
$\displaystyle\quad+|<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})>|$
$\displaystyle=:\sum_{i=1}^{8}T_{i}.$

We have

$T_{1}\leq
d_{key}\cdot\tau^{2}\cdot(\|z_{0}\|_{\infty}+\delta)^{2}\cdot\epsilon^{2},$
$T_{2}\leq\tau\cdot(\|z_{0}\|_{\infty}+\delta)\cdot\epsilon\cdot\delta$

(where we have used the fact that $\tilde{z}_{0,r_{2}}-z_{0,r_{2}}$ is zero in
components less than $d+l+2$ and consequently only the first component of
$W_{key,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})$ is nonzero),

$T_{3}\leq\tau\cdot(\|z_{0}\|_{\infty}+\delta)\cdot\epsilon\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}+\tau\cdot\|z_{0}\|_{\infty}\cdot\epsilon\cdot
l\cdot\|z_{0}\|_{\infty}+\tau\cdot\|z_{0}\|_{\infty}\cdot\epsilon\cdot 2\cdot
B$

(that is the consequence of the fact that the last two components of
$(\tilde{W}_{query,0,s_{0}}-W_{query,0,s_{0}})\tilde{z}_{0,r_{1}}$ depend on
$z_{0,r_{1}}$ and not on $\tilde{z}_{0,r_{1}}$, which follows from the
assumption that in the last two rows of $\tilde{W}_{query,0,s_{0}}$ and
$\tilde{W}_{key,0,s_{0}}$ all entries in columns greater than $d+l+1$ are
zero),

$T_{4}\leq\delta\cdot\tau\cdot(\|z_{0}\|_{\infty}+\delta)\cdot\epsilon$

(where we have used the fact that only the first component of
$W_{query,0,s_{0}}(\tilde{z}_{0,r_{1}}-z_{0,r_{1}})$ is nonzero)

$T_{5}\leq\delta\cdot\delta,$
$T_{6}\leq\delta\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty},$
$T_{7}\leq\|z_{0}\|_{\infty}\cdot\tau\cdot\epsilon\cdot(\|z_{0}\|_{\infty}+\delta)+(B+l)\cdot\|z_{0}\|_{\infty}\cdot\tau\cdot\epsilon\cdot\|z_{0}\|_{\infty}$

(where we have used the fact that the last two components of
$(\tilde{W}_{key,0,s_{0}}-W_{key,0,s_{0}})\tilde{z}_{0,r_{2}}$ depend on
$z_{0,r_{2}}$ and not on $\tilde{z}_{0,r_{2}}$, which follows as above from
the assumption that in the last two rows of $\tilde{W}_{query,0,s_{0}}$ and
$\tilde{W}_{key,0,s_{0}}$ all entries in columns greater than $d+l+1$ are
zero), and

$T_{8}\leq\|z_{0}\|_{\infty}\cdot(|\beta|+1)\cdot\delta$

(where we have used the fact that $\tilde{z}_{0,r_{2}}-z_{0,r_{2}}$ is zero in
components greater $d+l+1$ and consequently only the first component of
$W_{key,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})$ is nonzero). This proves

$\displaystyle|<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>-<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle\leq 14\cdot d_{key}\cdot\tau^{2}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{2}\cdot\max\\{\delta^{2},1\\}\cdot\epsilon$
$\displaystyle\quad+3\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{\delta,1\\}\cdot\delta$
$\displaystyle\quad+3\cdot
B\cdot\epsilon\cdot\tau\cdot\|z_{0}\|_{\infty}^{2}.$ (55)

Since we have

$\epsilon\leq\min\left\\{1,\frac{1}{36\cdot\tau\cdot\|z_{0}\|_{\infty}^{2}}\right\\},\quad
B>36\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{2}\cdot\max\\{\delta,1\\}\cdot\epsilon$

and

$B>168\cdot d_{key}\cdot\tau^{2}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|^{2}\cdot\max\\{\delta^{2},1\\}\cdot\epsilon$

the right-hand side of (55) is less than $B/4$.

In the third step of the proof we show (47).

To do this, we conclude from step 2 that we have

$\displaystyle<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>-\max_{r_{3}\neq
r_{2}}<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{3}}>$
$\displaystyle>\quad<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>-\max_{r_{3}\neq
r_{2}}<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{3}}>-\frac{B}{2}.$

The assertion follows from (.5) and (.5).

In the fourth step of the proof we show the assertion. Because of (47), (51)
and (54) it suffices to show

$\displaystyle\Bigg{\|}\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}\cdot<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>$
$\displaystyle\hskip 85.35826pt-
W_{value,0,s_{0}}z_{0,r_{2}}<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>\Bigg{\|}_{\infty}$
$\displaystyle\leq 144\cdot d_{key}\cdot\tau^{3}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{3}\cdot
B\cdot\max\\{\delta^{3},1\\}\cdot\epsilon$
$\displaystyle\quad+24\cdot\tau\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{\delta,1\\}\cdot\delta.$

We have

$\displaystyle\Bigg{\|}\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}\cdot<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>$
$\displaystyle\hskip 85.35826pt-
W_{value,0,s_{0}}z_{0,r_{2}}<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>\Bigg{\|}_{\infty}$
$\displaystyle\leq\Bigg{\|}\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}\cdot\Big{(}<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>$
$\displaystyle\hskip
142.26378pt-<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>\Big{)}\Bigg{\|}_{\infty}$
$\displaystyle\quad+\Bigg{\|}(\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}-W_{value,0,s_{0}}z_{0,r_{2}})\cdot<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>\Bigg{\|}_{\infty}$
$\displaystyle\leq\|\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}\|_{\infty}$
$\displaystyle\hskip
28.45274pt\cdot|<\tilde{W}_{query,0,s_{0}}\tilde{z}_{0,r_{1}},\tilde{W}_{key,0,s_{0}}\tilde{z}_{0,r_{2}}>-<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle\quad+\|\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}-W_{value,0,s_{0}}z_{0,r_{2}}\|_{\infty}\cdot|<W_{query,0,s_{0}}z_{0,r_{1}},W_{key,0,s_{0}}z_{0,r_{2}}>|$
$\displaystyle\leq(\tau+1)\cdot(1+\epsilon)\cdot(\|z\|_{\infty}+\delta)\cdot(14\cdot
d_{key}\cdot\tau^{2}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{2}\cdot\max\\{\delta^{2},1\\}\cdot\epsilon$
$\displaystyle\quad\hskip
28.45274pt+3\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{\delta,1\\}\cdot\delta+3\cdot
B\cdot\epsilon\cdot\tau\cdot\|z_{0}\|_{\infty}^{2})$
$\displaystyle\quad+\|\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}-W_{value,0,s_{0}}z_{0,r_{2}}\|_{\infty}\cdot(\|z_{0}\|_{\infty}\cdot(|\beta|+\|z_{0}\|_{\infty})+2\cdot
B).$

With

$\displaystyle\|\tilde{W}_{value,0,s_{0}}\tilde{z}_{0,r_{2}}-W_{value,0,s_{0}}z_{0,r_{2}}\|_{\infty}$
$\displaystyle\leq\|(\tilde{W}_{value,0,s_{0}}-W_{value,0,s_{0}})\tilde{z}_{0,r_{2}}\|_{\infty}+\|W_{value,0,s_{0}}(\tilde{z}_{0,r_{2}}-z_{0,r_{2}})\|_{\infty}$
$\displaystyle\leq\tau\cdot\epsilon\cdot(\|z_{0}\|_{\infty}+\delta)+0$

(where we have used that $\tilde{z}_{0,r_{2}}-z_{0,r_{2}}$ is zero in
components less than $d+l+2$) we get the assertion. $\Box$

###### Lemma 10

Let $\epsilon\in[0,1)$, let $\delta\geq 0$ and let $\alpha\in\mathbb{R}$. Let
$d_{ff},d_{model}\in\mathbb{N}$ and assume $d_{ff}\geq 4$. Let
$j_{1},j_{2}\in\\{1,\dots,d_{model}\\}$ with $j_{1}\neq j_{2}$. Then there
exist

$W_{r,1}\in\mathbb{R}^{d_{ff}\times
d_{model}},b_{r,1}\in\mathbb{R}^{d_{ff}},W_{r,2}\in\mathbb{R}^{d_{model}\times
d_{ff}},b_{r,2}\in\mathbb{R}^{d_{model}},$

where in $W_{r,1}$ in each row and in $W_{r,2}$ in each column at most $2$
components are not equal to zero and where all entries are bounded in absolute
value by $\max\\{|\alpha|,1\\}$, such that for all
$\tilde{W}_{r,1}\in\mathbb{R}^{d_{ff}\times d_{model}}$,
$\tilde{b}_{r,1}\in\mathbb{R}^{d_{ff}}$,
$\tilde{W}_{r,2}\in\mathbb{R}^{d_{model}\times d_{ff}}$,
$\tilde{b}_{r,2}\in\mathbb{R}^{d_{model}}$ with

$\|W_{r,1}-\tilde{W}_{r,1}\|_{\infty}<\epsilon,\quad\|b_{r,1}-\tilde{b}_{r,1}\|_{\infty}<\epsilon,\quad\|W_{r,2}-\tilde{W}_{r,2}\|_{\infty}<\epsilon,\quad\|b_{r,2}-\tilde{b}_{r,2}\|_{\infty}<\epsilon,$

and all $y_{r,i},\tilde{y}_{r,i}\in\mathbb{R}^{d_{model}}$
$(i\in\\{1,\dots,l\\})$ with

$\|y_{r,i}-\tilde{y}_{r,i}\|_{\infty}<\delta\quad(i\in\\{1,\dots,l\\})$

and

$\tilde{z}_{r,s}=\tilde{y}_{r,s}+\tilde{W}_{r,2}\cdot\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)+\tilde{b}_{r,2}\quad(s\in\\{1,\dots,l\\})$

we have:

$\left|\tilde{z}_{r,s}^{(j_{1})}-\alpha\cdot\max\\{y_{r,s}^{(j_{2})},0\\}\right|\leq
5\cdot d_{ff}\cdot\max\\{|\alpha|,1\\}\cdot(\|y_{r,s}\|_{\infty}+1)\cdot
d_{model}\cdot(\delta+\epsilon),$ $|\tilde{z}_{r,s}^{(j_{2})}|\leq 5\cdot
d_{ff}\cdot\max\\{|\alpha|,1\\}\cdot(\|y_{r,s}\|_{\infty}+1)\cdot
d_{model}\cdot(\delta+\epsilon)$

and

$|\tilde{z}_{r,s}^{(j)}-y_{r,s}^{(j)}|\leq 5\cdot
d_{ff}\cdot\max\\{|\alpha|,1\\}\cdot(\|y_{r,s}\|_{\infty}+1)\cdot
d_{model}\cdot(\delta+\epsilon)$

whenever $j\in\\{1,\dots,d_{model}\\}\setminus\\{j_{1},j_{2}\\}.$

Furthermore, the assertion of the lemma holds also if we replace
$\alpha\cdot\max\\{y_{r,s}^{(j_{2})},0\\}$ by $\alpha\cdot y_{r,s}^{(j_{2})}$.

Proof. Set

$z_{r,s}=y_{r,s}+W_{r,2}\cdot\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right)+b_{r,2}\quad(s\in\\{1,\dots,l\\}).$

In the first step of the proof we show that we can choose

$W_{r,1}\in\mathbb{R}^{d_{ff}\times
d_{model}},b_{r,1}\in\mathbb{R}^{d_{ff}},W_{r,2}\in\mathbb{R}^{d_{model}\times
d_{ff}},b_{r,2}\in\mathbb{R}^{d_{model}},$

such that at most $9$ components are not equal to zero and such that

$z_{r,s}^{(j_{1})}=\alpha\cdot\max\\{y_{r,s}^{(j_{2})},0\\},\quad
z_{r,s}^{(j_{2})}=0\quad\mbox{and}\quad z_{r,s}^{(j)}=y_{r,s}^{(j)}$

hold whenever $j\in\\{1,\dots,d_{model}\\}\setminus\\{j_{1},j_{2}\\}.$

W.l.o.g. we assume $d_{ff}=4$ and $j_{1}<j_{2}$. We choose $b_{r,1}=0$,
$b_{r,2}=0$,

$W_{r,1}=\left(\begin{array}[]{ccccccccccc}0&\dots&0&1&0&\dots&0&0&0&\dots&0\\\
0&\dots&0&-1&0&\dots&0&0&0&\dots&0\\\ 0&\dots&0&0&0&\dots&0&1&0&\dots&0\\\
0&\dots&0&0&0&\dots&0&-1&0&\dots&0\\\ \end{array}\right),$

where all columns except columns number $j_{1}$ and $j_{2}$ are zero, and

$W_{r,2}=\left(\begin{array}[]{cccc}0&0&0&0\\\ \vdots&&&\vdots\\\ 0&0&0&0\\\
-1&1&\alpha&0\\\ 0&0&0&0\\\ \vdots&&&\vdots\\\ 0&0&0&0\\\ 0&0&-1&1\\\
0&0&0&0\\\ \vdots&&&\vdots\\\ 0&0&0&0\end{array}\right),$

where all rows except row number $j_{1}$ and $j_{2}$ are zero. Then we have

$\displaystyle W_{2,r}\cdot\sigma\left(W_{1,r}\cdot
y_{r,s}+b_{1,r}\right)+b_{2,r}$ $\displaystyle=\left(\begin{array}[]{c}0\\\
\vdots\\\ 0\\\
\alpha\cdot\sigma(y_{r,s}^{(j_{2})})-(\sigma(y_{r,s}^{(j_{1})})-\sigma(-y_{r,s}^{(j_{1}}))\\\
0\\\ \vdots\\\ 0\\\ -(\sigma(y_{r,s}^{(j_{2})})-\sigma(-y_{r,s}^{(j_{2})}))\\\
0\\\ \vdots\\\ 0\\\ \end{array}\right).$

Because of

$\sigma(u)-\sigma(-u)=u$

for $u\in\mathbb{R}$ this implies the assertion of the first step.

In the second step of the proof we show

$|\tilde{z}_{r,s}^{(j)}-z_{r,s}^{(j)}|\leq 5\cdot
d_{ff}\cdot\max\\{|\alpha|,1\\}\cdot(\|y_{r,s}\|_{\infty}+1)\cdot