# Avoiding C-hacking when evaluating survival distribution predictions with
discrimination measures

Raphael Sonabend<EMAIL_ADDRESS>Department of Computer Science,
Technische Universität Kaiserslautern, Gottlieb-Daimler-Straße 47, 67663,
Kaiserslautern, Germany  Andreas Bender  Department of Statistics, LMU Munich,
Ludwigstr. 33, 80539, Bavaria, Germany  Sebastian Vollmer  Department of
Computer Science, Technische Universität Kaiserslautern, Gottlieb-Daimler-
Straße 47, 67663, Kaiserslautern, Germany  Data Science and its Application,
Deutsches Forschungszentrum für Künstliche Intelligenz (DFKI), Trippstadter
Str. 122, 67663, Kaiserslautern, Germany  Mathematics Institute, University of
Warwick, Zeeman Building, CV4 7AL, Coventry, UK

###### Abstract

In this paper we consider how to evaluate survival distribution predictions
with measures of discrimination. This is a non-trivial problem as
discrimination measures are the most commonly used in survival analysis and
yet there is no clear method to derive a risk prediction from a distribution
prediction. We survey methods proposed in literature and software and consider
their respective advantages and disadvantages. Whilst distributions are
frequently evaluated by discrimination measures, we find that the method for
doing so is rarely described in the literature and often leads to unfair
comparisons. We find that the most robust method of reducing a distribution to
a risk is to sum over the predicted cumulative hazard. We recommend that
machine learning survival analysis software implements clear transformations
between distribution and risk predictions in order to allow more transparent
and accessible model evaluation. The code used in the final experiment is
available at https://github.com/RaphaelS1/distribution_discrimination.

##  1 Introduction

Predictive survival models estimate the distribution of the time until an
event of interest takes place. This prediction may be presented in one of
three ways, as a: i) time-to-event, $Y\in\mathbb{R}_{>0}$, which represents
the time until the event takes place; ii) a relative risk,
$\phi\in\mathbb{R}$, which represents the risk of the event taking place
compared to other subjects in the same sample; or iii) the probability
distribution for the time to the event,
$\mathcal{S}\in\operatorname{Distr}(\mathbb{R}_{>0})$, where
$\operatorname{Distr}(\mathbb{R}_{>0})$ is the set of distributions over
$\mathbb{R}_{>0}$. Less abstractly, consider the Cox PH (Cox, 1972):
$h(t)=h_{0}(t)\exp(X\beta)$ where $h_{0}$ is the ‘baseline’ hazard function,
$X$ are covariates, and $\beta$ are coefficients to be estimated. In practice,
software fits the model by estimating the coefficients, $\hat{\beta}$.
Predictions from the fitted model may then either be returned as a relative
risk prediction, $X\hat{\beta}$ or $\exp(X\hat{\beta})$, or $h_{0}$ is also
estimated and a survival distribution is predicted as
$\hat{h}(t)=\hat{h}_{0}(t)\exp(X\hat{\beta})$.

The Cox PH is a special type of survival model that can naturally return both
a survival distribution and a relative risk prediction, however this is not
the case for all models. For example, random survival forests (Ishwaran et
al., 2008) only return distribution predictions by recursively splitting
observations into increasingly homogeneous groups and then fitting the Nelson-
Aalen estimator in the terminal node.

The most common method of evaluating survival models is with discrimination
measures (Collins et al., 2014; Gönen and Heller, 2005; Rahman et al., 2017),
in particular Harrell’s (Harrell et al., 1982) and Uno’s C (Uno et al., 2011).
These measures determine if relative risk predictions are concordant with the
true event time. To give a real-world example, a physician may predict that a
70-year old patient with cancer is at higher risk of death than a 12-year old
patient with a broken arm. If the 70-year old dies before the 12-year old then
the risk prediction is said to be concordant with the observed event times as
the patient with the predicted higher risk died first.

Despite there being no ‘obvious’ method of evaluating discrimination from a
distribution prediction, papers that compare (or benchmark) model
discrimination, frequently omit stating the software and/or method used for
evaluating distribution predictions (e.g. Fernández et al. (2016); Herrmann et
al. (2020); Spooner et al. (2020); Zhang et al. (2021)).

In this paper, we will consider how to evaluate methods, which only predict
survival distributions, with measures of discrimination. We will consider
these methods in the context of model comparison, i.e. by establishing if the
measure accurately evaluates if one model can be said to be superior to
another. For example, if a given random survival forest (distribution
prediction only) has better discrimination than a support vector machine (risk
prediction only) Van Belle et al. (2007).

We will review methods of discrimination evaluation that are discussed in the
literature and discuss their advantages and disadvantages. First some notation
to be used throughout the paper: let $X_{i}\in\mathbb{R}^{p}$ be $p$
covariates for subject $i$, let $Y_{i}$ be the true (but unobserved) survival
time; $C_{i}$ be the true (but unobserved) censoring time, and
$T_{i}=\min(Y_{i},C_{i})$ be the observed outcome time; finally let
$\Delta_{i}=\mathbb{I}(T_{i}=Y_{i})$ be the survival indicator. In this paper
we do not consider competing risks settings, which require specialised
measures.

##  2 Methods

We consider how discrimination measures are utilised in the literature to
evaluate the predictive performance of models that predict survival
distributions (Section 2.1), we then review the identified methods (Sections
2.2-2.3). To illustrate our findings we provide a worked example in Section 3.
The focus in our review is not to compare the (dis)advantages of measures but
instead their compatibility. For example, we do not compare if Antolini’s C is
‘better’ than Harrell’s C but instead note that the former requires a
distribution prediction and the latter a risk prediction, hence estimated
C-statistics cannot be compared between measures as they evaluate separate
predictions types (we call such a comparison ‘C-hacking’).

###  2.1 Literature Review

We first performed a formal literature review using PubMed and then a less
formal review from articles and software packages that had been drawn to our
attention. The purpose of the review was to determine how model discrimination
predictions have historically been evaluated for machine learning models that
make distributional predictions.

We searched PubMed for ‘(comparison OR benchmark) AND (”survival analysis” OR
”time-to-event analysis”) AND ”machine learning” AND (discrimination OR
concordance OR ”C statistic” OR ”c index”)’. We excluded articles if: i) they
did not use measures of discrimination; ii) no machine learning models were
included; iii) only risk-prediction models were included; iv) the models did
not make survival predictions (e.g. classifiers). We found 22 articles in our
initial search, which were reduced to nine after screening, a full PRISMA
diagram is provided in Figure 1, the diagram includes nine other records which
were identified outside of the search and which are discussed further below.

Figure 1: PRISMA diagram for literature review. Inclusion criteria: Articles
that compare machine learning survival predictions with measures of
discrimination.

A total of nine articles were retained for qualitative assessment (Hadanny et
al., 2022; Johri et al., 2021; Loureiro et al., 2021; Mosquera Orgueira et
al., 2020; Aivaliotis et al., 2021; Kantidakis et al., 2020; Spooner et al.,
2020; Crombé et al., 2021; Herrmann et al., 2020). All of these, without
exception, compared risk-predicting Cox-based models (e.g. regularised,
boosted, neural adaptations) to random survival forests Ishwaran et al.
(2008). scikit-survival (Pölsterl, 2020), randomForestSRC (Ishwaran and
Kogalur, 2018), ranger (Wright and Ziegler, 2017) and mlr (Bischl et al.,
2016) were utilised to implement and evaluate the RSFs. RSFs make
distributional predictions by ensembling a Nelson-Aalen estimator across
bootstrapped models Ishwaran et al. (2008). Transformation from distribution
to risk is handled in randomForestSRC and scikit-survival by taking the sum
over the predicted cumulative hazard function for each observation, which is
recommended by Ishwaran et al. (2008), we refer to this transformation as
‘expected mortality’ (Section 2.3.3). In contrast, no transformation is
provided in ranger, which only returns a distribution prediction, however this
is handled in Spooner et al. (2020) by utilising mlr, which provides the same
expected mortality transformation.

As well as these articles, we were also aware of the following articles and
software that discuss the discrimination of models that make distributional
predictions: Kvamme et al. (2019); Lee et al. (2018); Gensheimer and
Narasimhan (2019); Kvamme and Borgan (2019); Sonabend et al. (2021); Zhao and
Feng (2020); Haider et al. (2020); Mogensen et al. (2014); Schwarzer et al.
(2000). Of these articles the methods of comparing predicted distribution
discriminatory ability are: 1) utilising time-dependent concordance indices
(Kvamme and Borgan, 2019; Kvamme et al., 2019; Lee et al., 2018) (Section
2.2); 2) comparing predicted probabilities at a given time-point (Gensheimer
and Narasimhan, 2019; Mogensen et al., 2014; Schwarzer et al., 2000; Zhao and
Feng, 2020; Zhong and Tibshirani, 2019) (Section 2.3.1); 3) calculating and
comparing a summary statistic (e.g. expected survival time) from the predicted
distributions (Sonabend et al., 2021; Haider et al., 2020) (Section 2.3.2).

These four methods are grouped according to the required measure, i,e.: A)
time-dependent discrimination; and B) time-independent discrimination.
Discussion follows after defining some useful notation.

In practice, software for time-to-event predictions will usually return a
matrix of survival probabilities. Let $[T_{0},T_{N}]$ be the range of observed
survival times in a training dataset, let $M$ be the number of observations in
the test dataset and let $M^{*}\leq M$ be the number of time-points for which
predictions are made, then we predict $\mathbf{S}\in[0,1]^{M\times M^{*}}$,
which correspond to predictions of individual survival functions,
$S_{i}(T),T\in\mathcal{T}\subseteq[T_{0},T_{N}]$.

###  2.2 Time-dependent discrimination

Discrimination measures can be computed as the proportion of concordant pairs
over comparable pairs. Let $i\neq j$ be a pair of observations with observed
outcomes and predicted risks of
$\\{(T_{i},\Delta_{i},\phi_{i}),(T_{j},\Delta_{j},\phi_{j})\\}$ respectively.
Then $(i,j)$ are comparable if $T_{i}<T_{j}\cap\Delta_{i}$ and the predicted
risks are concordant with the outcome times if $\phi_{i}>\phi_{j}$. In this
paper we are concerned with how the values of $(\phi_{i},\phi_{j})$ are
calculated.

Time-dependent discrimination measures define concordance over time either by
taking $\phi_{i}$ to be predicted survival probabilities such as Antolini et
al. (2005), or as predicted linear predictors, such as Heagerty et al. (2000).

Antolini et al. (2005) define a pair of observations as concordant if the
predicted survival probabilities are concordant at the shorter outcome time,

$P(\hat{S}_{i}(T_{i})<\hat{S}_{j}(T_{i})|T_{i}<T_{j}\cap\Delta_{i}=1)$ (1)

In contrast, Heagerty et al. (2000) calculate the AUC by integrating over
specificity and sensitivity measures given by

$\displaystyle\text{sensitivity}(c,t)=P(\phi_{i}>c|T_{i}\leq t)$ (2)
$\displaystyle\text{specificty}(c,t)=P(\phi_{i}\leq c|T_{i}>t)$ (3)

Various metrics have been based on these ideas and several are implemented in
the R package survAUC (Potapov et al., 2012). However, all require a single
relative risk predictor, and therefore require some transformation from a
survival distribution prediction, and secondly all assume a one-to-one
relationship between the predicted value and expected survival times (which is
unlikely in complex machine learning models), for example a proportional
hazards assumption where the predicted risk is related to the predicted
survival distribution by multiplication of a constant (Potapov et al., 2012).

We are unaware of any time-dependent AUC metrics, except for Antolini’s, that
evaluates survival time predictions without a further transformation being
required. This may explain why Antolini’s C-index is seemingly more popular in
the artificial survival network literature (Kvamme and Borgan, 2019; Kvamme et
al., 2019; Lee et al., 2018).

On the surface, time-dependent discrimination measures are optimal for
evaluating distributions by discrimination. However, they are a poor choice
for model comparison. Time-dependent measures that evaluate risk predictions
(such as Heagerty’s) require a transformation from survival distribution
predictions and any such transformation is unlikely to result in the one-to-
one mapping required by the measures. In contrast, Antolini’s C evaluates the
concordance of a distribution, which means that it can only be used to compare
the concordance of two models that make distribution predictions, as opposed
to, say, one model that predicts distributions (e.g. RSFs) and one that
predicts relative risks (e.g. SVMs). The experiment in Section 3 demonstrates
why results from Antolini’s C cannot be simply compared to results from other
concordance indices.

###  2.3 Time-independent discrimination

Time-independent discrimination measures for survival analysis evaluate
relative risk predictions by estimating concordance.

Let $\mathcal{S}\subseteq\operatorname{Distr}(\mathbb{R}_{>0})$ be a convex
set of distributions over the positive Reals; then we define a distribution
reduction method as any function of the form:
$f:\mathcal{S}\rightarrow\mathbb{R}$, which map a survival distribution
prediction, $\zeta\in\mathcal{S}$, to a single relative risk,
$\phi\in\mathbb{R}$. In the discrete software analogue, we consider functions
$f^{\prime}:[0,1]^{M^{*}}\rightarrow\mathbb{R}$.

Distribution reduction methods are required to utilise time-independent
discrimination measures for models that make distribution predictions. We
consider the three from the literature review in turn.

####  2.3.1 Comparing probabilities

Evaluating discrimination at a given survival time is formally defined by
estimating

$P(\hat{S}_{i}(t)<\hat{S}_{j}(t)|T_{i}<T_{j}\cap\Delta_{i}=1)$ (4)

for some chosen $t\in\mathbb{R}_{>0}$. The distribution is reduced to a
relative risk by evaluating the survival probabilities at a given time-point,
$\phi:=\hat{S}(t^{\prime})$ where $\hat{S}$ is the predicted survival function
and $t^{\prime}\in\mathbb{R}_{>0}$. Note the key difference between this
method and Antolini’s C is that $t$ can be arbitrarily chosen here, whereas
Antolini’s C estimates the concordance at the observed outcome time.

This method assesses how well a model separates patients at a single time-
point; it has several problems: 1) it is not ‘proper’ in the sense that the
optimal model may not maximise the concordance at $t^{\prime}$ (Blanche et
al., 2019); 2) it is prone to manipulation as one could select the
$t^{\prime}$ that maximises the C-index for their chosen model (see Section
3); and 3) if predicted survival curves overlap then evaluation at different
time-points will lead to contradictory results (as the observed event time
will always stay the same). The above issues apply even if evaluated at
several time-points.

####  2.3.2 Distribution summary

The distribution summary statistic method reduces a probability distribution
prediction to a summary statistic, most commonly, the mean or median of the
distribution, i.e.,

$\displaystyle
P(\mathbb{E}[\zeta_{i}]<\mathbb{E}[\zeta_{j}]|T_{i}<T_{j}\cap\Delta_{i}=1)$
(5) $\displaystyle P(m(\zeta_{i})<m(\zeta_{j})|T_{i}<T_{j}\cap\Delta_{i}=1)$
(6)

where $m(\zeta_{i})$ is the median of distribution $\zeta_{i}$. In theory,
this should provide the most meaningful reduction with a natural
interpretation (mean or median survival time), however this is not the case as
the presence of censoring means that the predicted survival predictions will
usually result in ‘improper predictions’, i.e. the basic properties of the
survival function are not satisfied: $\lim_{t\rightarrow+\infty}S_{T}(t)\neq
0$. To see why this is the case, note that the majority of survival
distribution predictions make use of a discrete estimator such as the Kaplan-
Meier estimator, which is defined as follows:

$\hat{S}(t)=\begin{cases}1&t<t_{(1)}\\\ \prod_{i:t_{(i)}\leq
t}\left(1-d_{i}/n_{i}\right)&t\geq t_{(1)}\end{cases}$ (7)

where $d_{i},n_{i}$ are the number of deaths and events (death or censoring)
at ordered events times time $t_{(i)},i=1,\ldots,n$. By definition of this
estimator, unless all observations at risk in the final time-point experience
the event ($d_{i}=n_{i}$), the predicted survival probability in this last
point will be non-zero.

Several methods have been considered to extrapolate predictions to fix this
problem, such as dropping the last predicted probability to zero either at or
just after the last observed time-point (Sonabend et al., 2021), or by linear
extrapolation from the observed range (Haider et al., 2020) (Figure 2).
However these methods require unjustifiable assumptions and result in
misleading quantities. For example, dropping the survival probability to zero
immediately after the study end assumes that all patients (no matter their
risk) instantaneously die at the same time, which will skew the distribution
mean and median towards the final event time (Haider et al., 2020). The
extrapolation method has the opposite problem, if the prediction survival
curves are shallow then the extrapolated predictions can easily result in
impossible (or at least highly unrealistic) values (Figure 2).

However, we note that summarising a ‘proper’ distribution prediction (i.e. one
that doesn’t violate the limit properties) by its mean or median will provide
a natural relative risk. But this is rarely the case for all predicted
distributions in a test set and so the problem remains.

Figure 2: Extrapolation methods to ‘fix’ improper distribution predictions.
Top: Kaplan-Meier estimator fit on the rats (Therneau, 2015) dataset, which
results in an improper distribution as $\lim_{T\rightarrow\infty}=0.81\neq 0$.
Middle: Dropping the survival probability to zero at $T=105$, just after the
study end. Bottom: Dropping the survival probability to zero by linearly
extrapolating from first, $(S(T)=1,T=0)$, and last, $(S(T)=0.81,T=104)$,
observed survival times. Dashed horizontal lines are drawn at $S(T)=0.5$ and
dotted vertical lines at $T=104$, where the observed data ends and the
extrapolation begins. Median ($m$) and mean ($\mu$) are provided for both
extrapolation methods. Both methods result in quantities skewed heavily toward
the final extrapolated time. For the ‘dropping’ method the median is exactly
at the final time. Linear extrapolation results in probabilities that are
unrealistically large.

####  2.3.3 Expected mortality

The final time-dependent discrimination method estimates

$P(\phi_{i}>\phi_{j}|T_{i}<T_{j}\cap\Delta_{i}=1)$ (8)

where

$\phi_{i}:=\sum_{t\in\mathcal{T}}-\log\hat{S}_{i}(t)=\sum_{t\in\mathcal{T}}\hat{H}_{i}(t)$
(9)

and $\hat{H}_{i},\hat{S}_{i}$ are the predicted cumulative hazard and survival
functions respectively. Summing over the predicted cumulative hazard provides
a measure of expected mortality for similar individuals (Hosmer Jr et al.,
2011; Ishwaran et al., 2008) and a closely related quantity can even be used
as measure of calibration (Van Houwelingen, 2000).

The advantage of this method is that it requires no model assumptions, nor
assumptions about the survival distribution before or after the observed time
period, and finally, the reduction method provides an interpretable quantity
that is meaningful as a relative risk: the higher the expected mortality, the
greater the risk of the event.

##  3 Motivating Example

We now present a motivating example to make clear why these different
concordance measures cannot be directly compared in model evaluation and why
it is important to be precise about which method is utilised in model
comparison studies.

##### Experiment Design

We split the rats dataset from R package survival (Therneau, 2015) into a
random holdout split with 2/3 of the dataset for training and 1/3 for testing;
a seed was set for reproducibility. With the training data we fit a Cox PH
(CPH) with package survival, random survival forest (RSF) with package ranger,
and gradient boosting machine with C-index optimisation (GBM) (Mayr and
Schmid, 2014) with package mboost (Hothorn et al., 2020). Note that ranger
only returns distribution predictions for RSFs and mboost only returns risk
predictions.

##### Evaluation Measures

We used each model to make predictions on the holdout data. For the Cox PH we
made linear predictor predictions with survival::coxph and additionally
distribution predictions with survival::survfit. We evaluate the
discrimination of all possible predictions with: Harrell’s C, $C_{H}$,
(Harrell et al., 1982) (‘Harrell’) on the native risk prediction (i.e.
returned by package without further user transformation), Uno’s C (Uno et al.,
2011) (‘Uno’) on the native risk prediction, Antolini’s C (Antolini et al.,
2005) (‘Antolini’), $C_{H}$ computed on the survival probabilities at every
predicted time-point, $C_{H}$ computed on the distribution mean without any
extrapolation (‘Summary (naive)’), $C_{H}$ computed on the distribution mean
with extrapolation method of dropping to zero just after the final time point
(‘Summary (extr)’), and $C_{H}$ computed on the expected mortality
(‘ExpMort’). For reporting the concordance computed on survival probabilities
at each time-point, we reported the time-point which resulted in the maximum
$C_{H}$ for the RSF, the time-point that resulted in the minimum $C_{H}$ for
the RSF, and one randomly sampled time-point. Note that ‘Harrell’ and ‘Uno’ in
Table 1 cannot be computed for RSF, which does not return a native risk
prediction. Similarly, for the GBM only ‘Harrell’ and ‘Uno’ can be computed as
all other methods require a distribution prediction, which does not exist for
C-index boosted GBMs.

##### Results

The results (Table 1) indicate how ranking the performance of different
algorithms changes depending on the C-index used. The following are examples
for how the results in the table could be reported (from most transparent to
least):

  1. 1.

CPH is the best performing for distribution predictions under Antolini’s C
with a C-index of 0.852 compared to RSF’s 0.757

  2. 2.

RSF is the best performing for distribution predictions under the expected
mortality transformation with Harrell’s C with a C-index of 0.878 compared to
CPH’s 0.859.

  3. 3.

CPH is the best performing for risk predictions under Uno’s C with a C-index
of 0.861 compared to GBM’s 0.853

  4. 4.

RSF is the best performing model with a C-index of 0.897, then CPH with
C-index of 0.861 and then GBM with C-index of 0.853.

The first three of these are the clearest as they demonstrate what is being
evaluated and how. However, the difference between the first two demonstrates
how the result can be chosen by the researcher by selecting one measure over
another. The final is clearly the least transparent as it mixes many types of
predicted types and evaluation measures to draw conclusions.

##### Discussion

These examples demonstrate how simply reporting “the C-index” without being
more precise can lead to manipulation of results (deliberate or otherwise).
For example, the absurdly low values for ‘Summary (naive)’ are a result of
attempting to calculate the distribution mean from improper distribution
predictions, which is easily possible with lifelines (Davidson-Pilon, 2019)
and mlr3proba (Sonabend et al., 2021) (the latter has since been updated in
light of this problem). Similarly, despite providing a warning in
documentation and on usage, pec (Mogensen et al., 2014) still allows
concordance evaluation at arbitrary survival points, which could lead to
authors reporting the maximum C-index over all time-points (‘Prob (max)’ in
Table 1).

It is clear that a shift in reporting is required. When a range of C-indices
are tabulated as in Table 1 then dishonest reporting (like the final example
above) is clear however in practice a range of values is not reported and
instead just a vague ‘C-index’. This problem is analogous to any statistical
manipulation, for example p-hacking. The methods of dealing with the problem,
‘C-hacking’, are therefore also the same. Researchers should either: 1) decide
at the beginning of an experiment what method they will use for evaluating
concordance and state this clearly; or 2) report a wide range of methods
depending on utilised software.

Method | CPH | RSF | GBM
---|---|---|---
Harrell | $0.859$ | $-$ | 0.831
Uno | 0.861 | $-$ | 0.853
Antolini | $0.852$ | $0.757$ | $-$
Prob (min) | $0.500$ | $0.500$ | $-$
Prob (max) | $0.859$ | 0.897 | $-$
Prob (rand) | $0.859$ | $0.851$ | $-$
Summary (naive) | $0.141$ | $0.104$ | $-$
Summary (extr) | $0.859$ | $0.871$ | $-$
ExpMort | $0.859$ | $0.878$ | $-$
Table 1: Various C-index calculations from different methods and models.
Included models are Cox PH (CPH), random survival forest (RSF) and gradient
boosting machine with C-index optimisation (CPH). Methods of evaluation are:
Harrell’s C ($C_{H}$) on native risk predictions (i.e. predictions from
software without further transformation) (‘Harrell’), Uno’s C on native risk
predictions (‘Uno’), Antolini’s C on distribution predictions (‘Antolini’),
$C_{H}$ computed on the predicted survival probability at the time-point that
results in the smallest value for RSF (‘Prob (min)’), $C_{H}$ computed on the
predicted survival probability at the time-point that results in the largest
value for RSF (‘Prob (min)’), $C_{H}$ computed on the predicted survival
probability at an arbitrary time-point (‘Prob (rand)’), $C_{H}$ computed on
the distribution expectation without any extrapolation (‘Summary (naive)’),
$C_{H}$ computed on the distribution expectation after extrapolating by
dropping survival probabilities to zero (Fig 2 middle) (‘Summary (extr)’),
$C_{H}$ computed on the expected mortality (‘ExpMort’). Empty values indicate
that the given method is incompatible with the resulting predictions. Values
in bold are the maximum C-index for that model.

##  4 Conclusions

In this paper, we reviewed the literature for different methods of evaluating
survival distribution predictions with methods of concordance. For time-
dependent measures, only Antolini’s C can be directly applied to distribution
predictions. This measure can be utilised to compare the discrimination of
multiple models that make distribution predictions however as it cannot be
applied to models that make risk predictions, its use in benchmark experiments
is more limited. In contrast, methods that reduce a distribution prediction to
a risk prediction allow for time-independent discrimination measures to be
utilised for any combination of survival models. Of the reviewed ‘distribution
reduction’ methods that we found in the literature, the expected mortality
method of summing over the cumulative hazard was the most robust as it
requires no assumptions about the model or prediction and is therefore
applicable to all distribution predictions. Once the distribution is reduced
to a risk, any time-independent discrimination measure can be applied (e.g.
Harrell’s C).

Our motivating example demonstrates why understanding the differences between
these methods is so important and how an imprecise statement of methods can
lead to simple manipulation of results. We believe this is an important change
that must be made from the top-down to ensure it is quickly adopted. Journals
should require clear reporting on how c-statistics are computed in survival
analysis to ensure fair reporting of results and to avoid ‘C-hacking’.
Furthermore, all open-source software should provide methods to transform
distribution to risk predictions, such as the compositions in Sonabend et al.
(2021).

In general, researchers should make use of a wide range of evaluation metrics
including measures of calibration as well as scoring rules. Whichever metrics
are chosen, researchers should be precise about exactly which estimators are
utilised and any post-processing of results that was required.

## Competing interests

There is NO Competing Interest.

## Author contributions statement

RS conceptualised the article. All authors contributed equally to writing and
editing.

## Funding

AB has been funded by the German Federal Ministry of Education and Research
(BMBF) under Grant No. 01IS18036A. The authors of this work take full
responsibilities for its content.

## References

  * Aivaliotis et al. [2021] G. Aivaliotis, J. Palczewski, R. Atkinson, J. E. Cade, and M. A. Morris.  A comparison of time to event analysis methods, using weight status and breast cancer as a case study.  _Scientific Reports_ , 11(1):14058, 2021.  ISSN 2045-2322.  doi: 10.1038/s41598-021-92944-z.
  * Antolini et al. [2005] L. Antolini, P. Boracchi, and E. Biganzoli.  A time-dependent discrimination index for survival data.  _Statistics in Medicine_ , 24(24):3927–3944, dec 2005.  ISSN 0277-6715.  doi: 10.1002/sim.2427.
  * Bischl et al. [2016] B. Bischl, M. Lang, L. Kotthoff, J. Schiffner, J. Richter, E. Studerus, G. Casalicchio, and Z. M. Jones.  mlr: Machine Learning in R.  _Journal of Machine Learning Research_ , 17(170):1—-5, 2016.  URL http://jmlr.org/papers/v17/15-066.html https://cran.r-project.org/package=mlr.
  * Blanche et al. [2019] P. Blanche, M. W. Kattan, and T. A. Gerds.  The c-index is not proper for the evaluation of $t$-year predicted risks.  _Biostatistics_ , 20(2):347–357, 2019.  ISSN 1465-4644.  doi: 10.1093/biostatistics/kxy006.
  * Collins et al. [2014] G. S. Collins, J. A. De Groot, S. Dutton, O. Omar, M. Shanyinde, A. Tajar, M. Voysey, R. Wharton, L. M. Yu, K. G. Moons, and D. G. Altman.  External validation of multivariable prediction models: A systematic review of methodological conduct and reporting.  _BMC Medical Research Methodology_ , 14(1):1–11, 2014.  ISSN 14712288.  doi: 10.1186/1471-2288-14-40.
  * Cox [1972] D. R. Cox.  Regression Models and Life-Tables.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 34(2):187–220, 1972.
  * Crombé et al. [2021] A. Crombé, S. Cousin, M. Spalato-Ceruso, F. Le Loarer, M. Toulmonde, A. Michot, M. Kind, E. Stoeckle, and A. Italiano.  Implementing a Machine Learning Strategy to Predict Pathologic Response in Patients With Soft Tissue Sarcomas Treated With Neoadjuvant Chemotherapy.  _JCO Clinical Cancer Informatics_ , (5):958–972, sep 2021.  doi: 10.1200/CCI.21.00062.
  * Davidson-Pilon [2019] C. Davidson-Pilon.  lifelines: survival analysis in python.  _Journal of Open Source Software_ , 4(40):1317, 2019.  doi: 10.21105/joss.01317.  URL https://doi.org/10.21105/joss.01317.
  * Fernández et al. [2016] T. Fernández, N. N. Rivera, and Y. W. Teh.  Gaussian Processes for Survival Analysis.  _Neural Information Processing Systems_ , (Nips), 2016.  ISSN 10495258.  URL http://arxiv.org/abs/1611.00817.
  * Gensheimer and Narasimhan [2019] M. F. Gensheimer and B. Narasimhan.  A scalable discrete-time survival model for neural networks.  _PeerJ_ , 7:e6257, 2019.  ISSN 2167-8359.
  * Gönen and Heller [2005] M. Gönen and G. Heller.  Concordance Probability and Discriminatory Power in Proportional Hazards Regression.  _Biometrika_ , 92(4):965–970, 2005.
  * Hadanny et al. [2022] A. Hadanny, R. Shouval, J. Wu, C. P. Gale, R. Unger, D. Zahger, S. Gottlieb, S. Matetzky, I. Goldenberg, R. Beigel, and Z. Iakobishvili.  Machine learning-based prediction of 1-year mortality for acute coronary syndrome.  _Journal of Cardiology_ , jan 2022.  ISSN 0914-5087.  doi: 10.1016/j.jjcc.2021.11.006.
  * Haider et al. [2020] H. Haider, B. Hoehn, S. Davis, and R. Greiner.  Effective ways to build and evaluate individual survival distributions.  _Journal of Machine Learning Research_ , 21(85):1–63, 2020.  ISSN 1533-7928.
  * Harrell et al. [1982] F. E. Harrell, R. M. Califf, and D. B. Pryor.  Evaluating the yield of medical tests.  _JAMA_ , 247(18):2543–2546, may 1982.  ISSN 0098-7484.  doi: 10.1001/jama.1982.03320430047030.
  * Heagerty et al. [2000] P. J. Heagerty, T. Lumley, and M. S. Pepe.  Time-Dependent ROC Curves for Censored Survival Data and a Diagnostic Marker.  _Biometrics_ , 56(2):337–344, 2000.  ISSN 0006-341X.  doi: 10.1111/j.0006-341X.2000.00337.x.
  * Herrmann et al. [2020] M. Herrmann, P. Probst, R. Hornung, V. Jurinovic, and A.-L. Boulesteix.  Large-scale benchmark study of survival prediction methods using multi-omics data.  _arXiv preprint arXiv:2003.03621_ , 2020.
  * Hosmer Jr et al. [2011] D. W. Hosmer Jr, S. Lemeshow, and S. May.  _Applied survival analysis: regression modeling of time-to-event data_ , volume 618.  John Wiley & Sons, 2011.  ISBN 1118211588.
  * Hothorn et al. [2020] T. Hothorn, P. Buehlmann, T. Kneib, M. Schmid, and B. Hofner.  mboost: Model-Based Boosting, 2020.  URL https://cran.r-project.org/package=mboost.
  * Ishwaran et al. [2008] B. H. Ishwaran, U. B. Kogalur, E. H. Blackstone, and M. S. Lauer.  Random survival forests.  _The Annals of Statistics_ , 2(3):841–860, 2008\.  doi: 10.1214/08-AOAS169.
  * Ishwaran and Kogalur [2018] H. Ishwaran and U. B. Kogalur.  randomForestSRC, 2018.  URL https://cran.r-project.org/package=randomForestSRC.
  * Johri et al. [2021] A. M. Johri, L. E. Mantella, A. D. Jamthikar, L. Saba, J. R. Laird, and J. S. Suri.  Role of artificial intelligence in cardiovascular risk prediction and outcomes: comparison of machine-learning and conventional statistical approaches for the analysis of carotid ultrasound features and intra-plaque neovascularization.  _The International Journal of Cardiovascular Imaging_ , 37(11):3145–3156, 2021.  ISSN 1573-0743.  doi: 10.1007/s10554-021-02294-0.
  * Kantidakis et al. [2020] G. Kantidakis, H. Putter, C. Lancia, J. de Boer, A. E. Braat, and M. Fiocco.  Survival prediction models since liver transplantation - comparisons between Cox models and machine learning techniques.  _BMC Medical Research Methodology_ , 20(1):277, 2020.  ISSN 1471-2288.  doi: 10.1186/s12874-020-01153-1.
  * Kvamme and Borgan [2019] H. Kvamme and Ø. Borgan.  Continuous and discrete-time survival prediction with neural networks.  _arXiv preprint arXiv:1910.06724_ , 2019.
  * Kvamme et al. [2019] H. Kvamme, Ø. Borgan, and I. Scheel.  Time-to-event prediction with neural networks and Cox regression.  _Journal of Machine Learning Research_ , 20(129):1–30, 2019.  ISSN 1533-7928.
  * Lee et al. [2018] C. Lee, W. R. Zame, J. Yoon, and M. van der Schaar.  Deephit: A deep learning approach to survival analysis with competing risks.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Loureiro et al. [2021] H. Loureiro, T. Becker, A. Bauer-Mehren, N. Ahmidi, and J. Weberpals.  Artificial Intelligence for Prognostic Scores in Oncology: a Benchmarking Study, 2021.  URL https://www.frontiersin.org/article/10.3389/frai.2021.625573.
  * Mayr and Schmid [2014] A. Mayr and M. Schmid.  Boosting the concordance index for survival data–a unified framework to derive and evaluate biomarker combinations.  _PloS one_ , 9(1):e84483–e84483, jan 2014.  ISSN 1932-6203.  doi: 10.1371/journal.pone.0084483.  URL https://pubmed.ncbi.nlm.nih.gov/24400093 https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3882229/.
  * Mogensen et al. [2014] U. B. Mogensen, H. Ishwaran, and T. A. Gerds.  Evaluating Random Forests for Survival Analysis using Prediction Error Curves, 2014.
  * Mosquera Orgueira et al. [2020] A. Mosquera Orgueira, J. Á. Díaz Arias, M. Cid López, A. Peleteiro Raíndo, B. Antelo Rodríguez, C. Aliste Santos, N. Alonso Vence, Á. Bendaña López, A. Abuín Blanco, L. Bao Pérez, M. S. González Pérez, M. M. Pérez Encinas, M. F. Fraga Rodríguez, and J. L. Bello López.  Improved personalized survival prediction of patients with diffuse large B-cell Lymphoma using gene expression profiling.  _BMC Cancer_ , 20(1):1017, 2020.  ISSN 1471-2407.  doi: 10.1186/s12885-020-07492-y.
  * Pölsterl [2020] S. Pölsterl.  scikit-survival: A Library for Time-to-Event Analysis Built on Top of scikit-learn.  _Journal of Machine Learning Research_ , 21(212):1—-6, 2020.  URL http://jmlr.org/papers/v21/20-729.html.
  * Potapov et al. [2012] S. Potapov, W. Adler, and M. Schmid.  survAUC: Estimators of prediction accuracy for time-to-event data., 2012\.
  * Rahman et al. [2017] M. S. Rahman, G. Ambler, B. Choodari-Oskooei, and R. Z. Omar.  Review and evaluation of performance measures for survival prediction models in external validation settings.  _BMC Medical Research Methodology_ , 17(1):1–15, 2017.  ISSN 14712288.  doi: 10.1186/s12874-017-0336-2.
  * Schwarzer et al. [2000] G. Schwarzer, W. Vach, and M. Schumacher.  On the misuses of artificial neural networks for prognostic and diagnostic classification in oncology.  _Statistics in Medicine_ , 19(4):541–561, feb 2000.  ISSN 0277-6715.  doi: 10.1002/(SICI)1097-0258(20000229)19:4¡541::AID-SIM355¿3.0.CO;2-V.
  * Sonabend et al. [2021] R. Sonabend, F. J. Király, A. Bender, B. Bischl, and M. Lang.  mlr3proba: An R Package for Machine Learning in Survival Analysis.  _Bioinformatics_ , feb 2021.  ISSN 1367-4803.  doi: 10.1093/bioinformatics/btab039.  URL https://cran.r-project.org/package=mlr3proba.
  * Spooner et al. [2020] A. Spooner, E. Chen, A. Sowmya, P. Sachdev, N. A. Kochan, J. Trollor, and H. Brodaty.  A comparison of machine learning methods for survival analysis of high-dimensional clinical data for dementia prediction.  _Scientific Reports_ , 10(1):20410, 2020.  ISSN 2045-2322.  doi: 10.1038/s41598-020-77220-w.
  * Therneau [2015] T. M. Therneau.  A Package for Survival Analysis in S, 2015.  URL https://cran.r-project.org/package=survival.
  * Uno et al. [2011] H. Uno, T. Cai, M. J. Pencina, R. B. D’Agostino, and L. J. Wei.  On the C-statistics for Evaluating Overall Adequacy of Risk Prediction Procedures with Censored Survival Data.  _Statistics in Medicine_ , 30(10):1105–1117, 2011\.  ISSN 02776715.  doi: 10.1002/sim.4154.
  * Van Belle et al. [2007] V. Van Belle, K. Pelckmans, J. A. Suykens, and S. Van Huffel.  Support Vector Machines for Survival Analysis.  In _In Proceedings of the Third International Conference on Computational Intelligence in Medicine and Healthcare_ , number 1, 2007.  doi: 10.1016/j.microrel.2005.05.002.
  * Van Houwelingen [2000] H. C. Van Houwelingen.  Validation, calibration, revision and combination of prognostic survival models.  _Statistics in Medicine_ , 19(24):3401–3415, 2000\.  ISSN 02776715.  doi: 10.1002/1097-0258(20001230)19:24¡3401::AID-SIM554¿3.0.CO;2-2.
  * Wright and Ziegler [2017] M. N. Wright and A. Ziegler.  ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R.  _Journal of Statistical Software_ , 77(1):1—-17, 2017.
  * Zhang et al. [2021] Y. Zhang, G. Wong, G. Mann, S. Muller, and J. Y. H. Yang.  SurvBenchmark: comprehensive benchmarking study of survival analysis methods using both omics data and clinical data.  _bioRxiv_ , page 2021.07.11.451967, jan 2021.  doi: 10.1101/2021.07.11.451967.
  * Zhao and Feng [2020] L. Zhao and D. Feng.  DNNSurv: Deep Neural Networks for Survival Analysis Using Pseudo Values.  2020\.  URL https://arxiv.org/abs/1908.02337.
  * Zhong and Tibshirani [2019] C. Zhong and R. Tibshirani.  Survival analysis as a classification problem.  sep 2019.  URL http://arxiv.org/abs/1909.11171.


d_{model}\cdot(\delta+\epsilon).$

We have

$\displaystyle\|\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}-(W_{r,1}\cdot
y_{r,s}+b_{r,1})\|_{\infty}$
$\displaystyle\leq\|(\tilde{W}_{r,1}-W_{r,1})\cdot\tilde{y}_{r,s}\|_{\infty}+\|W_{r,1}\cdot(\tilde{y}_{r,s}-y_{r,s})\|_{\infty}+\epsilon$
$\displaystyle\leq
d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+\delta)+\delta+\epsilon$
$\displaystyle\leq\delta+d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+1+\delta),$

which implies

$\displaystyle\|\sigma(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1})-\sigma(W_{r,1}\cdot
y_{r,s}+b_{r,1})\|_{\infty}$
$\displaystyle\leq\delta+d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+1+\delta)$

and

$\displaystyle\|\sigma(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1})\|_{\infty}$
$\displaystyle\leq\delta+d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+1+\delta)+\|\sigma(W_{r,1}\cdot
y_{r,s}+b_{r,1})\|_{\infty}$
$\displaystyle\leq\delta+d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+1+\delta)+\|y_{r,s}\|_{\infty}.$

From this we conclude

$\displaystyle|\tilde{z}_{r,s}^{(j)}-z_{r,s}^{(j)}|$
$\displaystyle\leq\bigg{\|}\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}$
$\displaystyle\hskip
85.35826pt-\left(y_{r,s}+W_{r,2}\cdot\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right)+b_{r,2}\right)\bigg{\|}_{\infty}$
$\displaystyle\leq\delta+\left\|\tilde{W}_{r,2}\cdot\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)-W_{r,2}\cdot\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right)\right\|_{\infty}+\epsilon$
$\displaystyle\leq\delta+\left\|(\tilde{W}_{r,2}-W_{r,2})\cdot\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)\right\|_{\infty}$
$\displaystyle\quad+\left\|W_{r,2}\cdot\left(\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)-\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right)\right)\right\|_{\infty}+\epsilon$
$\displaystyle\leq\delta+d_{ff}\cdot\left\|\tilde{W}_{r,2}-W_{r,2}\right\|_{\infty}\cdot\left\|\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)\right\|_{\infty}$
$\displaystyle\quad+d_{ff}\cdot\left\|W_{r,2}\right\|_{\infty}\cdot\left\|\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)-\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right)\right\|_{\infty}+\epsilon$
$\displaystyle\leq\delta+d_{ff}\cdot\epsilon\cdot(\delta+d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+1+\delta)+\|y_{r,s}\|_{\infty})$
$\displaystyle\quad+d_{ff}\cdot\max\\{|\alpha|,1\\}\cdot(\delta+d_{model}\cdot\epsilon\cdot(\|y_{r,s}\|_{\infty}+1+\delta))+\epsilon$
$\displaystyle\leq 5\cdot
d_{ff}\cdot\max\\{|\alpha|,1\\}\cdot(\|y_{r,s}\|_{\infty}+1)\cdot
d_{model}\cdot(\delta+\epsilon).$

By slightly changing the matrix $W_{r,2}$ we conclude that the assertion also
holds upon replacing $\alpha\cdot\max\\{y_{r,s}^{(j_{2})},0\\}$ by
$\alpha\cdot y_{r,s}^{(j_{2})}$. $\Box$

###### Lemma 11

Let $I\geq d+l+4$, let $\tau\in\\{l+1,l+2,\dots,l+d+1\\}$. Let $c\geq A\geq
1$, let $K\in\mathbb{N}$, let $u_{k}\in[-A,A]$ $(k=1,\dots,K-1)$, set

$B_{j}(x)=x^{j}\quad\mbox{for }j=0,1,\dots,M$

and set

$B_{j}(x)=(x-u_{j-M})_{+}^{M}\quad\mbox{for }j=M+1,M+2,\dots,M+K-1.$

Let $i\in\\{d+l+4,\dots,I\\}$. Let $h\in\mathbb{N}$ with $1\leq h\leq n$ and
for $s\in\\{2,\dots,h\\}$ let $j_{s,1},\dots,j_{s,d}\in\\{0,1,\dots,M+K-1\\}$
and $\alpha_{s}\in\mathbb{R}$. Let $d_{key}\geq 3$ and set $d_{ff}=2\cdot
h+2$. Then there exists a transformer encoder consisting of $M\cdot(d\cdot
l)+1$ pairs of layers, where the first layer is a multi-head attention layer
with $h$ attention units and the second layer is a pointwise feedforward
neural network, and where all matrices in the attention heads have in each row
at most $\tau$ nonzero entries, and where all matrices $W_{r,1}$ and $W_{r,2}$
in the pointwise feedforward neural networks have the property that in each
row in $W_{r,1}$ and in each column in $W_{r,2}$ at most $\tau$ of the entries
are nonzero and where all matrices and vectors depend only on $(u_{k})_{k}$
and $\alpha_{s}$ $(s\in\\{1,\dots,k\\})$ and all entries are bounded in
absolute value by

$c_{27}\cdot n^{12^{M\cdot(d\cdot l)}}\cdot(d_{model})^{12^{M\cdot(d\cdot
l)}}\cdot c^{2\cdot 12^{M\cdot(d\cdot l)}},$

and where the matrices $\tilde{W}_{query,0,s}$, $\tilde{W}_{key,0,s}$ and
$\tilde{W}_{value,0,s}$ satisfy the assumptions of Lemma 9, which has the
following property: Any transformer network which has the same structure as
the above Transformer network and whose weights are in supremum norm no
further than $\epsilon$ away from the weights of the above network for some

$0\leq\epsilon\leq\min\left\\{1,\frac{1}{36\cdot\tau\cdot(2\cdot A)^{M\cdot
d\cdot l}}\right\\}$

has the property that if it gets as input $\tilde{z}_{0}$ which satisfies (46)
and

$\|\tilde{z}_{0}-z_{0}\|_{\infty}\leq c\cdot\epsilon$

for some $z_{0}\in[-A,A]^{l\cdot d_{model}}$ defined as in Subsection 2.1
(which encodes in particular
$x=(x_{1}^{T},\dots,x_{l}^{T})\in\mathbb{R}^{d\cdot l}$) it produces as output
$\tilde{z}_{M\cdot d+1}$, which satisfies for $n$ sufficiently large

$|\tilde{z}_{M\cdot d,1}^{(i)}-\sum_{s=2}^{h}\alpha_{s}\prod_{k=1}^{d\cdot
l}B_{j_{s,k}}(x^{(k)})|\leq c_{28}\cdot n^{6^{M\cdot(d\cdot
l)}+1}\cdot(d_{model})^{6^{M\cdot(d\cdot l)}+1}\cdot c^{8^{M\cdot(d\cdot
l)+2}+2\cdot(M\cdot d\cdot l+1)}\cdot\epsilon$

and

$|\tilde{z}_{M\cdot d,j}^{(l)}-z_{M\cdot d,j}^{(l)}|\leq c_{28}\cdot
n^{6^{M\cdot(d\cdot l)}+1}\cdot(d_{model})^{6^{M\cdot(d\cdot l)}+1}\cdot
c^{8^{M\cdot(d\cdot l)+2}\cdot(M\cdot d\cdot l+1)}\cdot\epsilon$

whenever $j>1$ or

$\displaystyle l\in\\{1,\dots,d_{model}\\}\setminus\\{i,I+d+l+2,I+d+l+3,2\cdot
I+d+l+2,$ $\displaystyle\hskip 71.13188pt2\cdot I+d+l+3,\dots,(h-1)\cdot
I+d+l+2,(h-1)\cdot I+d+l+3\\}.$

Proof. In the first step of the proof we show that the $h-1$ products of the
B-splines in the sum above can be computed in the first $M\cdot(d\cdot l)$
pairs of attention heads and pointwise feedforward network.

The basic idea is as follows. Each attention head of the network works only on
one of the parts $2,\dots,h$ of length $I$ of the input. It uses the fact that
each $B_{j}(x)$ can be written as

$B_{j}(x)=\prod_{k=1}^{M}B_{j,k}(x)$

where $B_{j,k}(x)$ is one of the functions

$x\mapsto 1,\quad x\mapsto x\quad\mbox{and}\quad x\mapsto(x-u_{r})_{+}.$

Using Lemma 9 (with a suitable value for $B$, which will be chosen in the
third step of the proof) and Lemma 10 we can combine an attention layer and a
pointwise feedforward layer such that the following holds: They get as input
an approximation $\tilde{z}_{0,j}$ of $z_{0,j}$ where $z_{0,j}$ is given as in
Lemma 9 and where the component $(s-1)\cdot I+d+l+2$ of $z_{0,j}$ is zero, and
they modify the components $(s-1)\cdot I+d+l+2$ and $(s-1)\cdot I+d+l+3$ of
$z_{0,j}$. More precisely, they combine the attention head of Lemma 9 and the
pointwise feedforward neural network of Lemma 10 such that they produce an
output $\tilde{y}_{j}$ where $\tilde{y}_{1}^{((s-1)\cdot I+d+l+3)}$ is an
approximation of the product of an approximation of either $z_{0,1}^{(d+1)}=1$
or $z_{0,1}^{((s-1)\cdot I+d+l+3)}$ and one of the functions

$x^{(k)}\mapsto 1,\quad x^{(k)}\mapsto x^{(k)}\quad\mbox{and}\quad
x^{(k)}\mapsto(x^{(k)}-u_{r})_{+}\quad(r\in\\{1,\dots,K-1\\})$

and where $\tilde{y}_{j}^{(r)}$ is approximately equal to $z_{0,j}^{(r)}$
otherwise $(r\in\\{(s-1)\cdot I+1,\dots,s\cdot I\\}\setminus\\{(s-1)\cdot
I+d+l+2,(s-1)\cdot I+d+l+3\\})$. Using this $M\cdot(d\cdot l)$ times we get an
approximation of

$\alpha_{s}\prod_{k=1}^{d\cdot l}B_{j_{s,k}}(x^{(k)})$ (57)

in $z_{M\cdot d,1}^{((s-1)\cdot I+(d+l+3))}$ for $s=2,\dots,h$.

In the second step of the proof we show how one pair of attention head and
pointwise feedforward neural network can be used to compute the sum of the
values in (57). To do this, we choose $W_{value,M\cdot(d\cdot l)+1}=0$ (which
results in $y_{M\cdot(d\cdot l)+1}=z_{M\cdot(d\cdot l)}$ and
$\tilde{y}_{M\cdot(d\cdot l)+1}\approx\tilde{z}_{M\cdot(d\cdot l)}$) and
choose $W_{1,M\cdot(d\cdot l)+1}$, $b_{1,M\cdot(d\cdot l)+1}$,
$W_{2,M\cdot(d\cdot l)+1}$, $b_{2,M\cdot(d\cdot l)+1}$, such that

$\displaystyle W_{2,M\cdot(d\cdot l)+1}\cdot\sigma\left(W_{1,M\cdot(d\cdot
l)+1}\cdot y_{M\cdot(d\cdot l)+1}+b_{1,M\cdot(d\cdot
l)+1}\right)+b_{2,M\cdot(d\cdot l)+1}$
$\displaystyle=\left(\begin{array}[]{c}0\\\ \vdots\\\ 0\\\ -(\sigma(y_{M\cdot
d+1,1}^{(i)})-\sigma(-y_{M\cdot d+1,1}^{(i)}))+\sigma(\sum_{s=2}^{h}y_{M\cdot
d+1,1}^{(s-1)\cdot I+(d+l+3)})-\sigma(-\sum_{s=2}^{h}y_{M\cdot
d+1,1}^{(s-1)\cdot I+(d+l+3)})\\\ 0\\\ \vdots\\\ 0\\\ \end{array}\right)$

holds, where the nonzero entry is in row number $i$.

In the third step of the proof we analyze the error occurring in the above
approximation. Here we describe in particular how the values of $B$ in the
application of Lemma 9 need to be chosen. In the applications of Lemma 9 we
will have

$\|z_{0}\|_{\infty}\leq(2\cdot A)^{M\cdot d\cdot
l}\quad\mbox{and}\quad|\beta|\leq A.$

In the first layer we set

$B=B_{1}=c_{29}\cdot c^{2\cdot M\cdot d\cdot l+3},$

which implies

$\displaystyle 168\cdot d_{key}\cdot\tau^{2}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{2}\cdot\max\\{(c\cdot\epsilon)^{2},1\\}\leq
c_{30}\cdot A^{2\cdot M\cdot d\cdot l+1}\cdot\max\\{(c\cdot\epsilon)^{2},1\\}$
$\displaystyle\leq c_{30}\cdot c^{2\cdot M\cdot d\cdot
l+3}\cdot\max\\{\epsilon^{2},1\\}\leq B_{1}.$

From this we can conclude by Lemma 9 that the output of the first attention
head has an error not exceeding

$\displaystyle 136\cdot d_{key}\cdot\tau^{3}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{3}\cdot
B_{1}\cdot\max\\{(c\cdot\epsilon)^{3},1\\}\cdot\epsilon$
$\displaystyle\quad+25\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{c\cdot\epsilon,1\\}\cdot(c\cdot\epsilon)$
$\displaystyle\leq c_{31}\cdot c^{5\cdot M\cdot d\cdot l+7}\cdot\epsilon.$

Application of Lemma 10 (where the input is bounded in absolute value by
$c_{32}\cdot A^{M\cdot d\cdot l}\leq c_{32}\cdot c^{M\cdot d\cdot l}$) yields
that after the pointwise feedforward neural network the error is maximal

$\delta_{1}=c_{33}\cdot n\cdot d_{model}\cdot c^{6\cdot M\cdot d\cdot
l+7}\cdot\epsilon.$

In the second level we set

$B=B_{2}=c_{34}\cdot n^{2}\cdot d_{model}^{2}\cdot c^{14\cdot M\cdot d\cdot
l+14}$

which implies

$\displaystyle 168\cdot d_{key}\cdot\tau^{2}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{2}\cdot\max\\{\delta_{1}^{2},1\\}$
$\displaystyle\leq c_{35}\cdot c^{2\cdot M\cdot d\cdot l}\max\\{(n\cdot
d_{model}\cdot c^{6\cdot M\cdot d\cdot l+7}\cdot\epsilon)^{2},1\\}$
$\displaystyle\leq c_{35}\cdot n^{2}\cdot d_{model}^{2}\cdot c^{14\cdot M\cdot
d\cdot l+14}\cdot\max\\{\epsilon^{2},1\\}\leq B_{2}.$

From this we can conclude by Lemma 9 that the output of the second attention
head has error not exceeding

$\displaystyle 136\cdot d_{key}\cdot\tau^{3}\cdot
l\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}^{3}\cdot
B_{2}\cdot\max\\{(c_{33}\cdot n\cdot d_{model}\cdot c^{14\cdot M\cdot d\cdot
l+14}\cdot\epsilon)^{3},1\\}\cdot\epsilon$
$\displaystyle\quad+25\cdot(|\beta|+1)\cdot\|z_{0}\|_{\infty}\cdot\max\\{c_{33}\cdot
n\cdot d_{model}\cdot c^{14\cdot M\cdot d\cdot
l+14}\cdot\epsilon,1\\}\cdot(c_{33}\cdot n\cdot d_{model}$
$\displaystyle\quad\cdot c^{14\cdot M\cdot d\cdot l+14}\cdot\epsilon)$
$\displaystyle\leq c_{36}\cdot n^{5}\cdot(d_{model})^{5}\cdot c^{59\cdot
M\cdot d\cdot l+57}\cdot\epsilon.$

Application of Lemma 10 (where the input is bounded in absolute value by
$c_{37}\cdot c^{M\cdot d\cdot l}$) yields that after the second pointwise
feedforward neural network the error is bounded above by

$c_{38}\cdot n\cdot c^{M\cdot d\cdot l}\cdot d_{model}\cdot n^{5}\cdot
d_{model}\cdot c^{59\cdot M\cdot d\cdot l+57}\cdot\epsilon\leq c_{38}\cdot
n^{6^{1}}\cdot(d_{model})^{6^{1}}\cdot c^{8^{2}\cdot(M\cdot d\cdot
l+1)}\cdot\epsilon=:\delta_{2}.$

Arguing recursively with value

$B_{r}=c_{39,r}\cdot n^{2\cdot 6^{r-1}}\cdot(d_{model})^{2\cdot 6^{r-1}}\cdot
c^{4\cdot 8^{r}\cdot(M\cdot d\cdot l+1)}$

on level $r\in\\{1,\dots,M\cdot(d\cdot l)\\}$ we see that after level $r$ the
error of the output is at most

$\delta_{r}=c_{40,r}\cdot n^{6^{r}}\cdot(d_{model})^{6^{r}}\cdot
c^{8^{r+1}\cdot(M\cdot d\cdot l+1)}\cdot\epsilon.$

The last pair of attention head and pointwise feedforward neural network in
level $M\cdot(d\cdot l)+1$, where the entries in all matrices are bounded by a
constant and all entries in all matrices in the attention head are all close
to zero, increases this error at most by a factor

$\|z_{M\cdot(d\cdot l)}\|_{\infty}\cdot c_{41}\cdot h\cdot d_{model}$

(cf., Step 2 in the proof of Lemma 10), which implies that the error of the
output of our transformer network is bounded by

$c_{42}\cdot n^{6^{M\cdot d\cdot l}+1}\cdot(d_{model})^{6^{M\cdot d\cdot
l}+1}\cdot c^{8^{M\cdot d\cdot l+2}\cdot(M\cdot d\cdot l+1)}\cdot\epsilon.$

$\Box$

Next we show how we can approximate a function which satisfies a hierarchical
composition model by a Transformer encoder. In order to formulate this result,
we introduce some additional notation. In order to compute a function
$h_{1}^{(\kappa)}\in\mathcal{H}(\kappa,\mathcal{P})$ one has to compute
different hierarchical composition models of some level $i$
$(i\in\\{1,\dots,\kappa-1\\})$. Let $\tilde{N}_{i}$ denote the number of
hierarchical composition models of level $i$, needed to compute
$h_{1}^{(\kappa)}$. Let

$\displaystyle h_{j}^{(i)}:\mathbb{R}^{d\cdot l}\to\mathbb{R}$ (59)

be the $j$–th hierarchical composition model of some level $i$
($j\in\\{1,\ldots,\tilde{N}_{i}\\},i\in\\{1,\ldots,\kappa\\}$), that applies a
$(p_{j}^{(i)},C)$–smooth function
$g_{j}^{(i)}:\mathbb{R}^{K_{j}^{(i)}}\to\mathbb{R}$ with
$p_{j}^{(i)}=q_{j}^{(i)}+s_{j}^{(i)}$, $q_{j}^{(i)}\in\mathbb{N}_{0}$ and
$s_{j}^{(i)}\in(0,1]$, where $(p_{j}^{(i)},K_{j}^{(i)})\in\mathcal{P}$ (and
$K_{j}^{(1)}=d\cdot l$ $(j=1,\dots,\tilde{N}_{1})$). With this notation we can
describe the computation of $h_{1}^{(\kappa)}(\mathbb{x})$ recursively as
follows:

$h_{j}^{(i)}(\mathbb{x})=g_{j}^{(i)}\left(h^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,h^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)$
(60)

holds for $j\in\\{1,\dots,\tilde{N}_{i}\\}$ and $i\in\\{2,\dots,\kappa\\}$,
and

$h_{j}^{(1)}(\mathbb{x})=g_{j}^{(1)}\left(x_{\pi(\sum_{t=1}^{j-1}K_{t}^{(1)}+1)},\dots,x_{\pi(\sum_{t=1}^{j}K_{t}^{(1)})}\right)$
(61)

holds for $j\in\\{1,\dots,\tilde{N}_{1}\\}$ for some function
$\pi:\\{1,\dots,\tilde{N}_{1}\\}\to\\{1,\dots,d\\}$. Here the recursion

$\displaystyle\tilde{N}_{l}=1\ \text{and}\
\tilde{N}_{i}=\sum_{j=1}^{\tilde{N}_{i+1}}K_{j}^{(i+1)}\quad(i\in\\{1,\dots,\kappa-1\\})$
(62)

holds.

###### Theorem 3

Let $\tau\in\\{l+1,l+2,\dots,l+d+1\\}$. Let $A\geq 1$, let
$m:\mathbb{R}^{d\cdot l}\to\mathbb{R}$ be contained in the class
$\mathcal{H}(\kappa,\mathcal{P})$ for some $\kappa\in\mathbb{N}$ and
$\mathcal{P}\subseteq[1,\infty)\times\mathbb{N}$. Let $\tilde{N}_{i}$ be
defined as in (62). Each $m$ consists of different functions $h_{j}^{(i)}$
$(j\in\\{1,\ldots,\tilde{N}_{i}\\},$ $i\in\\{1,\dots,\kappa\\})$ defined as in
(59), (60) and (61). Assume that the corresponding functions $g_{j}^{(i)}$ are
Lipschitz continuous with Lipschitz constant $C_{Lip}\geq 1$ and satisfy

$\|g_{j}^{(i)}\|_{C^{q_{j}^{(i)}}(\mathbb{R}^{K_{j}^{(i)}})}\leq c_{43}$

for some constant $c_{43}>0$. Denote by $K_{max}=\max_{i,j}K_{j}^{(i)}<\infty$
the maximal input dimension and set $q_{max}=\max_{i,j}q_{j}^{(i)}<\infty$,
where $q_{j}^{(i)}$ is the integer part of the smoothness $p_{j}^{(i)}$ of
$g_{j}^{(i)}$. Let $A\geq 1$. Choose $h\in\mathbb{N}$ such that

$c_{44}\leq h\leq n$ (63)

holds for $n$ large and for some sufficiently large constant $c_{44}$, choose

$I\geq\sum_{i=1}^{\kappa}\tilde{N}_{i}+d+l+4\quad\mbox{and}\quad d_{key}\geq
3$

and set

$N=I\cdot(q_{max}\cdot K_{max}+1),\quad d_{model}=h\cdot I,\quad d_{v}=I.$

Then there exists a transformer network $f_{\vartheta}$, where the matrices in
the attention heads have in each row at most nonzero $\tau$ entries, where all
matrices $W_{r,1}$ and $W_{r,2}$ in the pointwise feedforward neural networks
have the property that in each row of $W_{r,1}$ and in each column of
$W_{r,2}$ there are at most $\tau$ nonzero components, and where all
parameters are bounded in absolute value by $c_{45}\cdot n^{c_{46}}$ provided
$c_{45},c_{46}>0$ are sufficiently large, such that for each Transformer
network $f_{\tilde{\vartheta}}$ which has the same structure and which weights
are in supremum norm not further away than

$0\leq\epsilon\leq\frac{1}{c_{47}}$

from the weights of this network for some suitable large constant $c_{47}\geq
1$ and where the matrices $\tilde{W}_{query,r,s}$, $\tilde{W}_{key,r,s}$ and
$\tilde{W}_{value,r,s}$ satisfy the assumptions of Lemma 9, satisfies for $n$
large

$\displaystyle\|f_{\tilde{\vartheta}}-m\|_{\infty,[-A,A]^{d\cdot l}}$
$\displaystyle\leq$ $\displaystyle
c_{48}\cdot(K_{max}+1)^{\kappa}\cdot\max_{j,i}h^{-p_{j}^{(i)}/K_{j}^{(i)}}$
$\displaystyle+c_{49}\cdot n^{(I+1)\cdot(q_{max}\cdot K_{max}+2)}\cdot
d_{model}^{(I+1)\cdot(q_{max}\cdot K_{max}+1)}\cdot\epsilon$

provided $\epsilon\geq 0$ satisfies

$\epsilon\leq\frac{1}{2\cdot c_{50}\cdot
n^{8^{(\sum_{i=1}^{\kappa}\tilde{N}_{s})\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{i=1}^{\kappa}\tilde{N}_{s})\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}}.$ (64)

Proof. From the Lipschitz continuity of the $g_{j}^{(i)}$ and the recursive
definition of the $h_{j}^{(i)}$ we conclude that there exists
$1\leq\bar{A}\leq c_{51}\cdot A$ such that

$h_{j}^{(i)}(x)\in[-\bar{A},\bar{A}]$ (65)

holds for all $x\in[-A,A]^{d\cdot l}$, $j\in\\{1,\dots,\tilde{N}_{i}\\}$ and
$i\in\\{1,\dots,\kappa-1\\}$.

Our transformer encoder successively approximates $h_{1}^{(1)}(x)$, …,
$h_{N_{1}}^{(1)}(x)$, $h_{1}^{(2)}(x)$, …, $h_{N_{2}}^{(2)}(x)$, …,
$h^{(\kappa)}_{1}(x)$ and saves the computed values successively in
$z_{r,1}^{(d+l+5)}$, $z_{r,1}^{(d+l+6)}$, …,
$z_{r,1}^{(d+l+4+\sum_{i=1}^{\kappa}\tilde{N}_{i})}$. Here $h_{i}^{(j)}$ is
approximated by computing in a first step a truncated power basis of a tensor
product spline space of degree $q_{i}^{(j)}$ on an equidistant grid in

$[-\bar{A}-1,\bar{A}+1]^{K_{i}^{(j)}}$

consisting of $h-1$ basis functions, which are evaluated at the arguments of
$h_{i}^{(j)}$ in (61), and by using in a second step a linear combination of
these basis functions to approximate

$g_{j}^{(i)}\left(h^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,h^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right).$

The approximate computation of this truncated power basis can be done as in
Lemma 11 using layers $(\tilde{N}_{i-1}+j-1)\cdot(q_{max}\cdot K_{max}+1)+1$
till $(\tilde{N}_{i-1}+j)\cdot(q_{max}\cdot K_{max}+1)$ of our transformer
encoder. Here the computed values of this basis will have an error not
exceeding

$c_{51}\cdot n^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}\cdot\epsilon.$

Using standard approximation results from spline theory (cf., e.g., Theorem
15.2 and proof of Theorem 15.1 in Györfi et al. (2002) and Lemma 1 in Kohler
(2014)) and the Lipschitz continuity of $g_{j}^{(i)}$ this results in an
approximation

$\tilde{g}_{j}^{(i)}$

of $g_{j}^{(i)}$ which satisfies

$\displaystyle\|\tilde{g}_{j}^{(i)}-g_{j}^{(i)}\|_{\infty,[-\bar{A}-1,\bar{A}+1]^{K_{j}^{(i)}}}$
(66) $\displaystyle\leq c_{52}\cdot h^{-p_{j}^{(i)}/K_{j}^{(i)}}+c_{51}\cdot
h\cdot n^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}\cdot\epsilon$ $\displaystyle\leq c_{52}\cdot
h^{-p_{j}^{(i)}/K_{j}^{(i)}}+c_{51}\cdot
n^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}\cdot\epsilon.$

The approximation $\tilde{h}_{1}^{(\kappa)}(\mathbb{x})$ of
$h_{1}^{(\kappa)}(\mathbb{x})$ which our transformer encoder computes is
defined as follows:

$\tilde{h}_{j}^{(1)}(\mathbb{x})=\tilde{g}_{j}^{(1)}\left(x_{\pi(\sum_{t=1}^{j-1}K_{t}^{(1)}+1)},\dots,x_{\pi(\sum_{t=1}^{j}K_{t}^{(1)})}\right)$

for $j\in\\{1,\dots,\tilde{N}_{1}\\}$ and

$\tilde{h}_{j}^{(i)}(\mathbb{x})=\tilde{g}_{j}^{(i)}\left(\tilde{h}^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,\tilde{h}^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)$

for $j\in\\{1,\dots,\tilde{N}_{i}\\}$ and $i\in\\{2,\dots,\kappa\\}$.

Assume that (65) holds. From (64), (65) and (66) we conclude

$|\tilde{h}_{j}^{(i)}(\mathbb{x})|\leq|\tilde{h}_{j}^{(i)}(\mathbb{x})-h_{j}^{(i)}(\mathbb{x})|+|h_{j}^{(i)}(\mathbb{x})|\leq\bar{A}+1.$

Consequently we get from (66) for $n$ sufficiently large

$\displaystyle|\tilde{h}_{j}^{(i)}(\mathbb{x})-h_{j}^{(i)}(\mathbb{x})|$
$\displaystyle\leq|\tilde{g}_{j}^{(i)}\left(\tilde{h}^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,\tilde{h}^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)-g_{j}^{(i)}\left(\tilde{h}^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,\tilde{h}^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)|$
$\displaystyle\quad+|g_{j}^{(i)}\left(\tilde{h}^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,\tilde{h}^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)-g_{j}^{(i)}\left(h^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,h^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)|$
$\displaystyle\leq c_{52}\cdot h^{-p_{j}^{(i)}/K_{j}^{(i)}}+c_{51}\cdot
n^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}\cdot\epsilon$
$\displaystyle\quad+|g_{j}^{(i)}\left(\tilde{h}^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,\tilde{h}^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)-g_{j}^{(i)}\left(h^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+1}(\mathbb{x}),\dots,h^{(i-1)}_{\sum_{t=1}^{j}K_{t}^{(i)}}(\mathbb{x})\right)|$
$\displaystyle\leq c_{52}\cdot h^{-p_{j}^{(i)}/K_{j}^{(i)}}+c_{51}\cdot
n^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{s=1}^{i-1}\tilde{N}_{s}+j)\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}\cdot\epsilon$
$\displaystyle\quad+c_{53}\cdot\sum_{s=1}^{K_{j}^{(i)}}|\tilde{h}^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+s}(\mathbb{x})-h^{(i-1)}_{\sum_{t=1}^{j-1}K_{t}^{(i)}+s}(\mathbb{x})|,$

where the last inequality follows from the Lipschitz continuity of
$g_{j}^{(i)}$. Together with

$|\tilde{h}_{j}^{(1)}(\mathbb{x})-h_{j}^{(1)}(\mathbb{x})|\leq c_{54}\cdot
h^{-p_{j}^{(1)}/K_{j}^{(1)}}+c_{55}\cdot n^{8^{j\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{j\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot\epsilon,$

which follows again from (66), an easy induction shows

$\displaystyle|\tilde{h}_{1}^{(\kappa)}(\mathbb{x})-h_{1}^{(\kappa)}(\mathbb{x})|$
$\displaystyle\leq$ $\displaystyle
c_{56}\cdot(K_{max}+1)^{\kappa}\cdot\max_{j,i}h^{-p_{j}^{(i)}/K_{j}^{(i)}}$
$\displaystyle+c_{57}\cdot
n^{8^{(\sum_{s=1}^{\kappa}\tilde{N}_{s})\cdot(2\cdot q_{max}\cdot
K_{max}+4)}}\cdot d_{model}^{8^{(\sum_{s=1}^{\kappa}\tilde{N}_{s})\cdot(2\cdot
q_{max}\cdot K_{max}+4)}}\cdot\epsilon.$

$\Box$

###### Remark 6

It follows from the proof of Theorem 3 (i.e., in particular from the proof of
Lemma 9) that even if $\epsilon$ does not satisfy (66) then the all maximal
attentions are attended at some data-independent indices provided
$0\leq\epsilon\leq 1/c_{58}$ holds.

###### Lemma 12

Set

$f(z)=\begin{cases}\infty&,z=1\\\ \log\frac{z}{1-z}&,0<z<1\\\
-\infty&,z=0,\end{cases}$

let $K\in\mathbb{N}$ with $K\geq 6$ and let $A\geq 1$. Let
$m:\mathbb{R}^{d\cdot l}\rightarrow[0,1]$ and let $\bar{g}:\mathbb{R}^{d\cdot
l}\rightarrow\mathbb{R}$ such that $\|\bar{g}-m\|_{\infty,[-A,A]^{d\cdot
l}}\leq\epsilon$ for some

$0\leq\epsilon\leq\frac{1}{K}.$

Then there exists a neural network $\bar{f}:\mathbb{R}\rightarrow\mathbb{R}$
with ReLU activation function, and one hidden layer with $3\cdot K+9$ neurons,
where all the weights are bounded in absolute value by $K$, such that for each
network $\tilde{f}:\mathbb{R}\rightarrow\mathbb{R}$ which has the same
structure and which has weights which are in supremum norm not more than

$0\leq\bar{\epsilon}\leq 1$

away from the weights of the above network we have

$\displaystyle\sup_{x\in[-A,A]^{d\cdot
l}}\Bigg{(}\left|m(x)\cdot\left(\varphi(\tilde{f}(\bar{g}(x))-\varphi(f(m(x))\right)\right|$
$\displaystyle\hskip
113.81102pt+\left|(1-m(x))\cdot\left(\varphi(-\tilde{f}(\bar{g}(x)))-\varphi(-f(m(x))\right)\right|\Bigg{)}$
$\displaystyle\leq c_{58}\cdot\left(\frac{\log K}{K}+\epsilon\right)+132\cdot
K^{2}\cdot\bar{\epsilon}.$

Proof. In the first part part of the proof we show the assertion in case
$\bar{\epsilon}=0$.

For $k\in\\{-1,0,\dots,K+1\\}$ define

$B_{k}(z)=\begin{cases}0&,z<\frac{k-1}{K}\\\
K\cdot(z-\frac{k-1}{K})&,\frac{k-1}{K}\leq z<\frac{k}{K}\\\
K\cdot(\frac{k+1}{K}-z)&,\frac{k}{K}\leq z<\frac{k+1}{K}\\\
0&,z\geq\frac{k+1}{K},\end{cases}$

(which implies $B_{k}(k/K)=1$ and $B_{k}(j/K)=0$ for
$j\in\mathbb{Z}\setminus\\{k\\}$) and set

$\displaystyle\bar{f}(z)$ $\displaystyle=$ $\displaystyle
f(1/K)\cdot(B_{-1}(z)+B_{0}(z))+\sum_{k=1}^{K-1}f(k/K)\cdot
B_{k}(z)+f(1-1/K)\cdot(B_{K}(z)+B_{K+1}(z))$ $\displaystyle=:$
$\displaystyle\sum_{k=-1}^{K+1}a_{k}\cdot B_{k}(z).$

Then $\bar{f}$ interpolates the points $(-1/K,f(1/K))$, $(0,f(1/K))$,
$(1/K,f(1/K))$, $(2/K,f(2/K))$, …, $((K-1)/K,f((K-1)/K))$, $(1,f((K-1)/K))$
and $(1+1/K,f((K-1)/K))$, is zero outside of $(-2/K,1+2/K)$ and is linear on
each interval $[k/K,(k+1)/K]$ $(k\in\\{-2,\dots,K+1\\})$. Because of

$B_{k}(z)=\sigma\left(K\cdot\left(z-\frac{k-1}{K}\right)\right)-2\cdot\sigma\left(K\cdot\left(z-\frac{k}{K}\right)\right)+\sigma\left(K\cdot\left(z-\frac{k+1}{K}\right)\right),$

$\bar{f}$ can be computed by a neural network with ReLU activation function
and one hidden layer with $3\cdot(K+3)=3\cdot K+9$ neurons. Set

$h_{1}(z)=\varphi(f(z))=\log\left(1+\exp\left(-\log\frac{z}{1-z}\right)\right)=\log\left(1+\frac{1-z}{z}\right)=-\log
z$

and

$h_{2}(z)=\varphi(-f(z))=\log\left(1+\exp\left(\log\frac{z}{1-z}\right)\right)=-\log(1-z).$

First we consider the case $m(\mathbf{x})\in[0,2/K]$, which implies

$f(m(\mathbf{x}))\leq f(2/K)=-\log(K/2-1)<0.$

In this case we have $-1/K\leq\bar{g}(\mathbf{x})\leq 3/K$ and

$-\log(K-1)=f(1/K)\leq\bar{f}(\bar{g}(\mathbf{x}))\leq f(3/K)=-\log(K/3-1)$

(where we have used that $\bar{f}$ is monotone increasing and satisfies
$\bar{f}(-\frac{1}{K})=f(\frac{1}{K})$ and
$\bar{f}(\frac{3}{K})=f(\frac{3}{K})$). Consequently we get

$\displaystyle\left|m(\mathbf{x})\cdot\left(\varphi(\bar{f}(\bar{g}(\mathbf{x}))-\varphi(f(m(\mathbf{x}))\right)\right|$
$\displaystyle\leq$ $\displaystyle
m(\mathbf{x})\cdot\varphi(\bar{f}(\bar{g}(\mathbf{x}))+m(\mathbf{x})\cdot
h_{1}(m(\mathbf{x}))$ $\displaystyle\leq$
$\displaystyle\frac{2}{K}\cdot\log(1+\exp(\log(K-1)))+m(\mathbf{x})\cdot\log(\frac{1}{m(\mathbf{x})})$
$\displaystyle\leq$ $\displaystyle 4\cdot\frac{\log K}{K}$

(where we have used the inequality $z\cdot\log(1/z)\leq(2/K)\cdot\log(K/2)$
for $0<z<2/K$) and

$\displaystyle\left|(1-m(\mathbf{x}))\cdot\left(\varphi(-\bar{f}(\bar{g}(\mathbf{x}))-\varphi(-f(m(\mathbf{x}))\right)\right|$
$\displaystyle\leq\varphi(-\bar{f}(\bar{g}(\mathbf{x}))+\varphi(-f(m(\mathbf{x}))$
$\displaystyle=\log(1+\exp(\bar{f}(\bar{g}(\mathbf{x}))))+\log(1+\exp(f(m(\mathbf{x}))))$
$\displaystyle\leq\log(1+\exp(-\log(K/3-1)))+\log(1+\exp(-\log(K/2-1)))$
$\displaystyle\leq 2\cdot\exp(-\log(K/3-1))=\frac{6}{K-3}.$

Similarly we get in case $m(\mathbf{x})\geq 1-2/K$

$\displaystyle\left|m(\mathbf{x})\cdot\left(\varphi(\bar{f}(\bar{g}(\mathbf{x}))-\varphi(f(m(\mathbf{x}))\right)\right|+\left|(1-m(\mathbf{x}))\cdot\left(\varphi(-\bar{f}(\bar{g}(\mathbf{x}))-\varphi(-f(m(\mathbf{x}))\right)\right|$
$\displaystyle\leq 12\cdot\frac{\log K}{K-3}.$

Hence it suffices to show

$\displaystyle\sup_{\mathbf{x}\in\mathbb{R}^{d},\atop
m(\mathbf{x})\in[2/K,1-2/K]}\Bigg{(}\left|m(\mathbf{x})\cdot\left(\varphi(\bar{f}(\bar{g}(\mathbf{x}))-\varphi(f(m(\mathbf{x}))\right)\right|$
$\displaystyle\hskip
85.35826pt+\left|(1-m(\mathbf{x}))\cdot\left(\varphi(-\bar{f}(\bar{g}(\mathbf{x}))-\varphi(-f(m(\mathbf{x}))\right)\right|\Bigg{)}$
$\displaystyle\leq c_{59}\cdot(\frac{\log K}{K}+\epsilon).$

By the monotonicity of $f$, $|f^{\prime}(z)|=\frac{1}{z\cdot(1-z)}\geq 1$ for
$z\in(0,1)$, the mean value theorem and the definition of $\bar{f}$ we
conclude that for any $\mathbf{x}\in\mathbb{R}^{d\cdot l}$ with
$m(\mathbf{x})\in[2/K,1-2/K]$ we find
$\xi_{x},\delta_{\mathbf{x}}\in\mathbb{R}$ with $|\xi_{x}|\leq\frac{1}{K}$,
$|\delta_{\mathbf{x}}|\leq\frac{1}{K}+\epsilon$ and
$m(\mathbf{x})+\delta_{\mathbf{x}}\in[1/K,1-1/K]$ such that

$\bar{f}(\bar{g}(\mathbf{x}))=f(\bar{g}(\mathbf{x})+\xi_{x})=f(m(\mathbf{x})+\delta_{\mathbf{x}}).$
(67)

This implies

$\displaystyle\sup_{\mathbf{x}\in\mathbb{R}^{d},\atop
m(\mathbf{x})\in[2/K,1-2/K]}\Bigg{(}\left|m(\mathbf{x})\cdot\left(\varphi(\bar{f}(\bar{g}(\mathbf{x}))-\varphi(f(m(\mathbf{x}))\right)\right|$
$\displaystyle\hskip
85.35826pt+\left|(1-m(\mathbf{x}))\cdot\left(\varphi(-\bar{f}(\bar{g}(\mathbf{x}))-\varphi(-f(m(\mathbf{x}))\right)\right|\Bigg{)}$
$\displaystyle=\sup_{\mathbf{x}\in\mathbb{R}^{d},\atop
m(\mathbf{x})\in[2/K,1-2/K]}\Bigg{(}|m(\mathbf{x})|\cdot|h_{1}(m(\mathbf{x})+\delta_{\mathbf{x}})-h_{1}(m(\mathbf{x}))|$
$\displaystyle\hskip
85.35826pt+|1-m(\mathbf{x})|\cdot|h_{2}(m(\mathbf{x})+\delta_{\mathbf{x}})-h_{2}(m(\mathbf{x}))|\Bigg{)}.$

Consequently it suffices to show that there exist constants $c_{60},c_{61}>0$
such that we have for any $z\in[2/K,1-2/K]$ and any $\delta\in\mathbb{R}$ with
$|\delta|\leq\frac{1}{K}+\epsilon$ and $z+\delta\in[1/K,1-1/K]$

$|z|\cdot|h_{1}(z+\delta)-h_{1}(z)|\leq
c_{60}\cdot\left(\frac{1}{K}+\epsilon\right)$ (68)

and

$|1-z|\cdot|h_{2}(z+\delta)-h_{2}(z)|\leq
c_{61}\cdot\left(\frac{1}{K}+\epsilon\right).$ (69)

Obviously

$h_{1}^{\prime}(z)=-\frac{1}{z}.$

By the mean value theorem we get for some
$\xi\in[\min\\{z+\delta,z\\},\max\\{z+\delta,z\\}]$

$|z|\cdot|h_{1}(z+\delta)-h_{1}(z)|=|z|\cdot\frac{1}{|\xi|}\cdot|\delta|\leq
4\cdot|\delta|\leq 4\cdot\left(\frac{1}{K}+\epsilon\right),$

where we have used that $z,z+\delta\in[1/K,1-1/K]$ and $|\delta|\leq 2/K$
imply $4|\xi|\geq|z|$.

In the same way we get

$h_{2}^{\prime}(z)=\frac{1}{1-z}$

and

$|1-z|\cdot|h_{2}(z+\delta)-h_{2}(z)|=|1-z|\cdot\frac{1}{|1-\xi|}\cdot|\delta|\leq
4\cdot|\delta|\leq 4\cdot\left(\frac{1}{K}+\epsilon\right).$

In the second step of the proof we show that if a network $\tilde{f}$ has the
same structure as the network $\bar{f}$ in the first step of the proof and if
the supremum norm distance between the weights of $\tilde{f}$ and $\bar{f}$ is
at most $\epsilon$, then we have:

$\sup_{x\in\mathbb{R}^{d\cdot
l}}\left|\tilde{f}(\bar{g}(x)-\bar{f}(\bar{g}(x))\right|\leq 11\cdot(3\cdot
K+9)\cdot K\cdot\bar{\epsilon}.$

Let

$f(z)=\sum_{j=1}^{J_{n}}v_{j}^{(1)}\cdot\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)$

be a neural network with one hidden layer with $J_{n}$ neurons, where all the
weights are bounded in absolute value by $\beta=K$. It suffices to show that
for any $z\in[-1,2]$ and any network $\tilde{f}$ which has the same structure
as $f$ and where the weights are in supremum norm not further away from the
weights of $f$ than $\bar{\epsilon}$, it holds

$|\tilde{f}(z)-f(z)|\leq 11\cdot\beta\cdot J_{n}\cdot\bar{\epsilon}.$

To prove this we observe

$\displaystyle|\tilde{v}_{i,1}^{(0)}\cdot
z+\tilde{v}_{i,0}^{(0)}-(v_{i,1}^{(0)}\cdot
z+v_{i,0}^{(0)})|\leq|(\tilde{v}_{i,1}^{(0)}-v_{i,1}^{(0)})\cdot
z|+\bar{\epsilon}\leq
2\cdot\bar{\epsilon}+\bar{\epsilon}=3\cdot\bar{\epsilon},$

which implies

$|\sigma(\tilde{v}_{i,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{i,0}^{(0)})-\sigma(v_{i,1}^{(0)}\cdot
z+v_{i,0}^{(0)})|\leq 3\cdot\bar{\epsilon},$

and

$|\sigma(\tilde{v}_{i,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{i,0}^{(0)})|\leq
3\cdot\bar{\epsilon}+|\sigma(v_{i,1}^{(0)}\cdot z+v_{i,0}^{(0)})|\leq
3\cdot\bar{\epsilon}+5\beta\leq 8\beta.$

Hence we have

$\displaystyle|\tilde{f}(z)-f(z)|$ $\displaystyle=$
$\displaystyle\left|\sum_{j=1}^{J_{n}}\tilde{v}_{j}^{(1)}\cdot\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot
z+\tilde{v}_{j,0}^{(0)}\right)-\sum_{j=1}^{J_{n}}v_{j}^{(1)}\cdot\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)\right|$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{J_{n}}|\tilde{v}_{j}^{(1)}-v_{j}^{(1)}|\cdot\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot
z+\tilde{v}_{j,0}^{(0)}\right)$
$\displaystyle+\sum_{j=1}^{J_{n}}|v_{j}^{(1)}|\cdot\left|\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot
z+\tilde{v}_{j,0}^{(0)}\right)-\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)\right|$ $\displaystyle\leq$ $\displaystyle
8\cdot\beta\cdot J_{n}\cdot\bar{\epsilon}+\beta\cdot J_{n}\cdot
3\cdot\bar{\epsilon}\leq 11\cdot\beta\cdot J_{n}\cdot\bar{\epsilon},$

which yields the assertion.

Since $\varphi$ is Lipschitz continuous the assertion of Lemma 12 follows from
steps 1 and 2. $\Box$

###### Lemma 13

Let $A\geq 1$ and let $0\leq\epsilon\leq 1/(2\cdot c_{62})$. Let
$f_{\mathbf{\vartheta}}$ be a transformer classifier defined as in Section 2
where the weights in all attention units and in all piecewise feedforward
networks are in supremum norm not further away than $1/(2\cdot c_{62})$ from
the weights of the transformer network in Theorem 3, and where the weights in
the feedfoward network are not further away than $\epsilon$ from the weights
of the feedforward neural network in Lemma 12. Let
$f_{\tilde{\mathbf{\vartheta}}}$ be a transformer classifier of the same form
which satisfies

$\|\tilde{\mathbf{\vartheta}}-\mathbf{\vartheta}\|_{\infty}\leq\epsilon.$

Assume $d_{ff}=2\cdot h+2$, $h\leq c_{64}\cdot n$, $d_{model}=h\cdot I$ and
$I=\lceil\log n\rceil$. Then we have for $c_{65},c_{66}>0$ sufficiently large

$\|f_{\tilde{\mathbf{\vartheta}}}-f_{\mathbf{\vartheta}}\|_{[-A,A]^{d\cdot
l},\infty}\leq c_{65}\cdot
n^{c_{66}}\cdot\|\tilde{\mathbf{\vartheta}}-\mathbf{\vartheta}\|_{\infty}.$

Proof. Since the weights in the transformer classifiers
$f_{\mathbf{\vartheta}}$ and $f_{\mathbf{\vartheta}^{*}}$ are not further away
than $1/c_{63}$ from the weights of the transformer network in Theorem 3, it
follows from the proof of Theorem 3 that in both transformer network all
maximal attention are attained at the same indices, namely at the indices
where the transformer network in Theorem 3 attains its maximal attentions
(cf., Remark 6). Consequently we can ignore the selection of the maximal
attention in the rest of the proof.

Let

$q_{k,r-1,s,i}=W_{query,k,r,s}\cdot z_{k,r-1,i},\quad
k_{k,r-1,s,i}=W_{key,k,r,s}\cdot z_{k,r-1,i},$
$v_{k,r-1,s,i}=W_{value,k,r,s}\cdot
z_{k,r-1,i},\quad\tilde{q}_{k,r-1,s,i}=\tilde{W}_{query,k,r,s}\cdot\tilde{z}_{k,r-1,i},$
$\tilde{k}_{k,r-1,s,i}=\tilde{W}_{key,k,r,s}\cdot\tilde{z}_{k,r-1,i},\quad\tilde{v}_{k,r-1,s,i}=\tilde{W}_{value,k,r,s}\cdot\tilde{z}_{k,r-1,i}$

where all the weights in the matrices above are bounded in absolute value by
$B\geq 1$, and set

$y_{k,r,i}=z_{k,r-1,i}+v_{k,r-1,s,r_{1}}\cdot<q_{k,r-1,s,i},k_{k,r-1,s,r_{1}}>$

and

$\tilde{y}_{k,r,i}=\tilde{z}_{k,r-1,i}+\tilde{v}_{k,r-1,s,r_{1}}\cdot<\tilde{q}_{k,r-1,s,i},\tilde{k}_{k,r-1,s,r_{1}}>.$

In the first step of the proof we show

$\displaystyle\|\tilde{y}_{k,r,i}-y_{k,r,i}\|_{\infty}$ $\displaystyle\leq
c_{67}\cdot d_{key}\cdot d_{model}^{3}\cdot
B^{2}\cdot\left(\max\\{\|z_{k,r-1,i}\|_{\infty},\|\tilde{z}_{k,r-1,i}\|_{\infty},1\\}\right)^{3}$
$\displaystyle\hskip
28.45274pt\cdot\max\Big{\\{}\|\tilde{W}_{query,k,r-1,s}-W_{query,k,r-1,s}\|_{\infty},\|\tilde{W}_{key,k,r-1,s}-W_{key,k,r-1,s}\|_{\infty},$
$\displaystyle\hskip
56.9055pt\|\tilde{W}_{value,k,r-1,s}-W_{value,k,r-1,s}\|_{\infty}\Big{\\}}$
$\displaystyle\quad+c_{68}\cdot d_{key}\cdot d_{model}^{3}\cdot
B^{3}\cdot\left(\max\\{\|z_{k,r-1,i}\|_{\infty},\|\tilde{z}_{k,r-1,i}\|_{\infty},1\\}\right)^{2}\cdot\|\tilde{z}_{k,r-1}-z_{k,r-1}\|_{\infty}.$

We have

$\displaystyle\|\tilde{y}_{k,r,i}-y_{k,r,i}\|_{\infty}$
$\displaystyle\leq\|\tilde{z}_{k,r,i}-z_{k,r,i}\|_{\infty}+\|\tilde{v}_{k,r,r_{1}}-v_{k,r,r_{1}}\|_{\infty}\cdot|<\tilde{q}_{k,r,i},\tilde{k}_{k,r,r_{1}}>|$
$\displaystyle\quad+\|v_{k,r,r_{1}}\|_{\infty}\cdot|<\tilde{q}_{k,r,i},\tilde{k}_{k,r,r_{1}}>-<q_{k,r,i},k_{k,r,r_{1}}>|.$

With

$\displaystyle\|\tilde{v}_{k,r,r_{1}}-v_{k,r,r_{1}}\|_{\infty}$
$\displaystyle\leq\|(\tilde{W}_{value,k,r,s}-W_{value,k,r,s})\cdot\tilde{z}_{k,r-1,r_{1}}\|_{\infty}+\|W_{value,k,r,s}\cdot(\tilde{z}_{k,r-1,r_{1}}-z_{k,r-1,r_{1}})\|_{\infty}$
$\displaystyle\leq
d_{model}\cdot\|\tilde{W}_{value,k,r,s}-W_{value,k,r,s}\|_{\infty}\cdot\|\tilde{z}_{k,r-1,r_{1}}\|_{\infty}$
$\displaystyle\quad+d_{model}\cdot
B\cdot\|\tilde{z}_{k,r-1,r_{1}}-z_{k,r-1,r_{1}}\|_{\infty},$
$\displaystyle|<\tilde{q}_{k,r,i},\tilde{k}_{k,r,r_{1}}>|\leq d_{key}\cdot
B^{2}\cdot d_{model}\cdot\|\tilde{z}_{k,r-1,r_{1}}\|_{\infty}^{2},$
$\|v_{k,r,i}\|_{\infty}\leq d_{model}\cdot B\cdot\|z_{k,r-1,i}\|_{\infty}$

and

$\displaystyle|<\tilde{q}_{k,r,i},\tilde{k}_{k,r,r_{1}}>-<q_{k,r,i},k_{k,r,r_{1}}>|$
$\displaystyle\leq|<\tilde{q}_{k,r,i}-q_{k,r,i},\tilde{k}_{k,r,r_{1}}>|+|<q_{k,r,i},\tilde{k}_{k,r,r_{1}}-k_{k,r,r_{1}}>|$
$\displaystyle\leq
d_{key}\cdot\Big{(}\|(\tilde{W}_{query,k,r,s}-W_{query,k,r,s})\cdot\tilde{z}_{k,r-1,i}\|_{\infty}$
$\displaystyle\hskip
56.9055pt+\|W_{query,k,r,s}\cdot(\tilde{z}_{k,r-1,i}-z_{k,r-1,i})\|_{\infty}\Big{)}\cdot\|\tilde{k}_{k,r,r_{1}}\|_{\infty}$
$\displaystyle\quad+d_{key}\cdot\|q_{k,r,i}\|_{\infty}\cdot\Big{(}\|(\tilde{W}_{key,k,r,s}-W_{key,k,r,s})\cdot\tilde{z}_{k,r-1,i}\|_{\infty}$
$\displaystyle\hskip
56.9055pt+\|W_{key,k,r,s}\cdot(\tilde{z}_{k,r-1,i}-z_{k,r-1,i})\|_{\infty}\Big{)}$
$\displaystyle\leq
d_{key}\cdot(d_{model}\cdot\|\tilde{W}_{query,k,r,s}-W_{query,k,r,s}\|_{\infty}\cdot\|\tilde{z}_{k,r-1}\|_{\infty}$
$\displaystyle\hskip 56.9055pt+d_{model}\cdot
B\cdot\|\tilde{z}_{k,r-1}-z_{k,r-1}\|_{\infty})\cdot d_{model}\cdot
B\cdot\|\tilde{z}_{k,r-1}\|_{\infty}$ $\displaystyle\quad+d_{key}\cdot
d_{model}\cdot
B\cdot\|z_{k,r-1}\|_{\infty}\cdot(d_{model}\cdot\|\tilde{W}_{key,k,r,s}-W_{key,k,r,s}\|_{\infty}\cdot\|\tilde{z}_{k,r-1}\|_{\infty}$
$\displaystyle\hskip 56.9055pt+d_{model}\cdot
B\cdot\|\tilde{z}_{k,r-1}-z_{k,r-1}\|_{\infty})$

we get the assertion.

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}$

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},$

where all weights of the neural networks above are bounded in absolute value
by $B\geq 1$. In the second step of the proof we show

$\displaystyle\|z_{r,s}-\tilde{z}_{r,s}\|_{\infty}$ $\displaystyle\leq
c_{69}\cdot d_{ff}\cdot d_{model}\cdot
B\cdot\max\\{\|y_{r,s}\|_{\infty},\|\tilde{y}_{r,s}\|_{\infty},1\\}$
$\displaystyle\hskip
56.9055pt\cdot\max\left\\{\|\tilde{W}_{r,2}-W_{r,2}\|_{\infty},\|\tilde{W}_{r,1}-W_{r,1}\|_{\infty},\|\tilde{b}_{r,2}-b_{r,2}\|_{\infty},\|\tilde{b}_{r,1}-b_{r,1}\|_{\infty}\right\\}$
$\displaystyle\quad+c_{70}\cdot d_{ff}\cdot d_{model}\cdot
B^{2}\cdot\|\tilde{y}_{r,s}-y_{r,s}\|_{\infty}.$

We have

$\displaystyle\|z_{r,s}-\tilde{z}_{r,s}\|_{\infty}$
$\displaystyle\leq\|y_{r,s}-\tilde{y}_{r,s}\|_{\infty}+\|\tilde{W}_{r,2}\cdot\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)-W_{r,2}\cdot\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right)\|_{\infty}$ $\displaystyle\hskip
28.45274pt+\|\tilde{b}_{r,2}-b_{r,2}\|_{\infty}$
$\displaystyle\leq\|y_{r,s}-\tilde{y}_{r,s}\|_{\infty}+\|(\tilde{W}_{r,2}-W_{r,2})\cdot\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)\|_{\infty}$
$\displaystyle\quad+\|W_{r,2}\cdot(\sigma\left(\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\right)-\sigma\left(W_{r,1}\cdot
y_{r,s}+b_{r,1}\right))\|_{\infty}+\|\tilde{b}_{r,2}-b_{r,2}\|_{\infty}$
$\displaystyle\leq\|y_{r,s}-\tilde{y}_{r,s}\|_{\infty}+d_{ff}\cdot\|\tilde{W}_{r,2}-W_{r,2}\|_{\infty}\cdot\|\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\|_{\infty}$
$\displaystyle\quad+d_{ff}\cdot
B\cdot\|\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}-W_{r,1}\cdot
y_{r,s}+\tilde{b}_{r,1}-b_{r,1}\|_{\infty}+\|\tilde{b}_{r,2}-b_{r,2}\|_{\infty}.$

Using

$\|\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}+\tilde{b}_{r,1}\|_{\infty}\leq
d_{model}\cdot B\cdot\|\tilde{y}_{r,s}\|_{\infty}+B$

and

$\displaystyle\|\tilde{W}_{r,1}\cdot\tilde{y}_{r,s}-W_{r,1}\cdot
y_{r,s}\|_{\infty}$
$\displaystyle\leq\|(\tilde{W}_{r,1}-W_{r,1})\cdot\tilde{y}_{r,s}\|_{\infty}+\|W_{r,1}\cdot(\tilde{y}_{r,s}-y_{r,s})\|_{\infty}$
$\displaystyle\leq
d_{model}\cdot\|\tilde{W}_{r,1}-W_{r,1}\|_{\infty}\cdot\|\tilde{y}_{r,s}\|_{\infty}+d_{model}\cdot
B\cdot\|\tilde{y}_{r,s}-y_{r,s}\|_{\infty}$

we get the assertion.

Let

$f(z)=\sum_{j=1}^{J_{n}}v_{j}^{(1)}\cdot\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)$

and

$\tilde{f}(\tilde{z})=\sum_{j=1}^{J_{n}}\tilde{v}_{j}^{(1)}\cdot\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}\right),$

where all the weights of the networks above are bounded in absolute value by
$B\geq 1$. In the third part of the proof we show

$\displaystyle|\tilde{f}(\tilde{z})-f(z)|$ $\displaystyle\leq$ $\displaystyle
c_{71}\cdot J_{n}\cdot
B\cdot\max\\{\tilde{z},z,1\\}\cdot\max\\{|\tilde{v}_{j}^{(1)}-v_{j}^{(1)}|,|\tilde{v}_{j,1}^{(0)}-v_{j,1}^{(0)}|,|\tilde{v}_{j,0}^{(0)}-v_{j,0}^{(0)}|\\}$
$\displaystyle+c_{72}\cdot J_{n}\cdot B^{2}\cdot|\tilde{z}-z|.$

We have

$\displaystyle|\tilde{f}(\tilde{z})-f(z)|$
$\displaystyle\leq\sum_{j=1}^{J_{n}}|\tilde{v}_{j}^{(1)}\cdot\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}\right)-v_{j}^{(1)}\cdot\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)|$ $\displaystyle\leq
J_{n}\cdot\max_{j=1,\dots,J_{n}}\Big{(}|\tilde{v}_{j}^{(1)}-v_{j}^{(1)}|\cdot\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}\right)$
$\displaystyle\hskip
85.35826pt+|v_{j}^{(1)}|\cdot|\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}\right)-\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)|\Big{)}.$

With

$\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}\right)\leq|\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}|\leq
B\cdot|\tilde{z}|+B$

and

$\displaystyle|\sigma\left(\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}+\tilde{v}_{j,0}^{(0)}\right)-\sigma\left(v_{j,1}^{(0)}\cdot
z+v_{j,0}^{(0)}\right)|$
$\displaystyle\leq|\tilde{v}_{j,1}^{(0)}\cdot\tilde{z}-v_{j,1}^{(0)}\cdot
z+\tilde{v}_{j,0}^{(0)}-v_{j,0}^{(0)}|\leq|\tilde{v}_{j,1}^{(0)}\cdot(\tilde{z}-z)|+|(\tilde{v}_{j,1}^{(0)}-v_{j,1}^{(0)})\cdot
z|+|\tilde{v}_{j,0}^{(0)}-v_{j,0}^{(0)}|$ $\displaystyle\leq
B\cdot|\tilde{z}-z|+|\tilde{v}_{j,1}^{(0)}-v_{j,1}^{(0)}|\cdot|z|+|\tilde{v}_{j,0}^{(0)}-v_{j,0}^{(0)}|$

we get the assertion.

In the fourth part of the proof we use the above results to show the assertion
of the lemma.

All weights in the above transformer classifiers are bounded in absolute value
by

$c_{73}\cdot n^{c_{74}}+\epsilon\leq 2\cdot c_{73}\cdot n^{c_{74}}=:B.$

Because of

$\|y_{k,r}\|_{\infty}\leq 2\cdot d_{ff}\cdot d_{key}^{2}\cdot d_{model}\cdot
B^{3}\cdot\max\\{\|z_{k,r-1}\|_{\infty}^{3},1\\},$ $\|z_{k,r}\|_{\infty}\leq
4\cdot d_{ff}\cdot d_{model}\cdot B^{2}\cdot\max\\{\|y_{k,r}\|_{\infty},1\\}$

and

$\|z_{0,r}\|_{\infty}\leq A$

an easy induction shows

$\|y_{k,r}\|_{\infty}\leq 128^{3^{2\cdot r-2}}\cdot d_{ff}^{4^{2\cdot
r-2}}\cdot d_{model}^{4^{2\cdot r-2}}\cdot B^{9^{2\cdot r-2}}\cdot A^{3^{r}}$

and

$\|z_{k,r}\|_{\infty}\leq 128^{3^{2\cdot r-2}}\cdot d_{ff}^{4^{2\cdot
r-2}+1}\cdot d_{model}^{4^{2\cdot r-2}+1}\cdot B^{9^{2\cdot r-2}+2}\cdot
A^{3^{r}}$

for $r\geq 1$. The same inequalities also hold for $\tilde{y}_{k,r}$ and
$\tilde{z}_{k,r}$. This implies

$\max\left\\{\|y_{k,r}\|_{\infty},\|\tilde{y}_{k,r}\|_{\infty},\|z_{k,r}\|_{\infty},\|\tilde{z}_{k,r}\|_{\infty}\right\\}\leq
c_{75}\cdot n^{c_{76}}$

for $r\leq N$, where $c_{75}=c_{75}(N),c_{76}=c_{76}(N)>0$ are finite
constants.

Consequently we can conclude from Step 1

$\displaystyle\|\tilde{y}_{k,r,i}-y_{k,r,i}\|_{\infty}$ $\displaystyle\leq
c_{77}\cdot
n^{c_{78}}\cdot\max\Big{\\{}\|\tilde{W}_{query,k,r-1,s}-W_{query,k,r-1,s}\|,\|\tilde{W}_{key,k,r-1,s}-W_{key,k,r-1,s}\|,$
$\displaystyle\hskip
28.45274pt\|\tilde{W}_{value,k,r-1,s}-W_{value,k,r-1,s}\|,\|\tilde{z}_{k,r-1}-z_{k,r-1}\|_{\infty}\Big{\\}},$

from Step 2

$\displaystyle\|z_{r,s}-\tilde{z}_{r,s}\|_{\infty}$ $\displaystyle\leq
c_{79}\cdot
n^{c_{80}}\cdot\max\Big{\\{}\|\tilde{W}_{r,2}-W_{r,2}\|_{\infty},\|\tilde{W}_{r,1}-W_{r,1}\|_{\infty},\|\tilde{b}_{r,2}-b_{r,2}\|_{\infty},$
$\displaystyle\hskip
85.35826pt\|\tilde{b}_{r,1}-b_{r,1}\|_{\infty},\|\tilde{y}_{r,s}-y_{r,s}\|_{\infty}\Big{\\}},$

and from Step 3

$\displaystyle\|f_{\tilde{\mathbf{\vartheta}}}-f_{\mathbf{\vartheta}}\|_{[-A,A]^{d\cdot
l},\infty}$ $\displaystyle\leq c_{81}\cdot
n^{c_{82}}\cdot\max\\{|\tilde{v}_{j}^{(1)}-v_{j}^{(1)}|,|\tilde{v}_{j,1}^{(0)}-v_{j,1}^{(0)}|,|\tilde{v}_{j,0}^{(0)}-v_{j,0}^{(0)}|,\|\tilde{z}_{N,1}-z_{N,1}\|_{\infty}\\}.$

Using these relations recursively we conclude

$\|f_{\tilde{\mathbf{\vartheta}}}-f_{\mathbf{\vartheta}}\|_{[-A,A]^{d\cdot
l},\infty}\leq c_{83}\cdot n^{c_{84}}$

for $c_{83},c_{84}>0$ sufficiently large (and depending on $N$). $\Box$