# Personalized Transformer for Explainable Recommendation

Lei Li1 Yongfeng Zhang2 Li Chen1
1Hong Kong Baptist University, Hong Kong, China
2Rutgers University, New Brunswick, USA
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

Personalization of natural language generation plays a vital role in a large
spectrum of tasks, such as explainable recommendation, review summarization
and dialog systems. In these tasks, user and item IDs are important
identifiers for personalization. Transformer, which is demonstrated with
strong language modeling capability, however, is not personalized and fails to
make use of the user and item IDs since the ID tokens are not even in the same
semantic space as the words. To address this problem, we present a
PErsonalized Transformer for Explainable Recommendation
(PETER111https://github.com/lileipisces/PETER), on which we design a simple
and effective learning objective that utilizes the IDs to predict the words in
the target explanation, so as to endow the IDs with linguistic meanings and to
achieve personalized Transformer. Besides generating explanations, PETER can
also make recommendations, which makes it a unified model for the whole
recommendation-explanation pipeline. Extensive experiments show that our small
unpretrained model outperforms fine-tuned BERT on the generation task, in
terms of both effectiveness and efficiency, which highlights the importance
and the nice utility of our design.

10cm(2cm,1cm) Published as a conference paper at ACL-IJCNLP 2021

(a) Standard Transformer model, where the user and the item have no
contribution to each generation step. (b) Our PETER model, where the user and
item IDs play significant roles in the generation steps.

Figure 1: Attention visualization of two models when generating an explanation
for the same user-item pair (see the first two columns). They are both from
the last attention layer, so the target sequences are offset by one position
for better illustration. The larger the attention weights, the lighter the
cells.

##  1 Introduction

Recent years have witnessed the successful application of natural language
generation. Many of the applications in fact require certain degree of
personalization, such as explainable recommendation (Zhang et al., 2014; Li et
al., 2020c; Zhang and Chen, 2020), review generation (Dong et al., 2017),
review summarization (Li et al., 2019), and conversational systems (Zhang et
al., 2018; Chen et al., 2020). In these tasks, user and item IDs that
distinguish one user/item from the others are crucial to personalization. For
example, in recommender systems, different users may care about different item
features (e.g., style vs. quality), and different items may have different
characteristics (e.g., fashionable vs. comfortable). The goal of explainable
recommendation Zhang and Chen (2020) is to provide an explanation to a user
for a recommended item, so as to justify how the recommendation might match
his/her interests. That is, given a pair of user ID and item ID, the system
needs to generate an explanation, such as “the style of the jacket is
fashionable” (see the last column of Table 4 for more examples).

Transformer (Vaswani et al., 2017), whose strong language modeling ability has
been demonstrated on a variety of tasks (Radford et al., 2018; Devlin et al.,
2019; Brown et al., 2020), however, is relatively under-explored for
personalized natural language generation. Since IDs and words are in very
different semantic spaces, it would be problematic to directly put them
together for attention learning, because by doing so, the IDs are treated as
words, but the IDs appear far less frequently than the words. For example, a
paragraph of review (and thus hundreds of words) on e-commerce platform only
corresponds to a single pair of user ID and item ID. As such, the IDs may be
regarded as out-of-vocabulary tokens, to which the model is insensitive. As
shown in Fig. 1(a), when generating an explanation for a user-item pair,
standard Transformer relies heavily on the special $<$bos$>$ token instead of
the user or the item. This would result in identical explanations over
different user-item pairs (see USR score in Table 2), deviating from our
personalization goal.

To address this problem, we bridge IDs and words by designing an elegant task
called context prediction, which maps IDs onto words to be generated by the
explanation task. This in some way resembles one’s drafting-polishing process,
where by predicting some words the context prediction task does the job of
drafting. Then, the explanation generation task polishes these words so as to
form a readable sentence. Meanwhile, we demonstrate that conducting
recommendation task on the same model is also feasible, so we name it PETER,
which stands for PErsonalized Transformer for Explainable Recommendation. As
we can see in Fig. 1(b), when PETER generates an explanation for the same
user-item pair, it can utilize the information of both the user and the item,
which illustrates the effectiveness of our context prediction task.

In addition, PETER is flexible to incorporate item features that can help to
guide its generation. This can be very useful when, for instance, a user
proactively asks the system to explain certain feature(s) of a recommendation
(Li et al., 2020c), e.g., price. Then, we would expect the model to generate a
targeted explanation, such as “great jacket, especially for the price”. PETER
is a small unpretrained Transformer with only 2 layers, yet it outperforms a
fine-tuned BERT (Ni et al., 2019) on most metrics by a large margin, and takes
less time to train, as shown in our experiments. This manifests the
superiority of our model.

In summary, our key contributions are:

  * •

We propose PETER that makes recommendation and generates explanation
simultaneously based on user and item IDs for explainable recommendation. To
the best of our knowledge, we are the first to enable Transformer with
personalized natural language generation.

  * •

We evaluate the generated explanations on not only text quality metrics (such
as BLEU and ROUGE), but also metrics that particularly focus on explainability
from the angle of item features. Extensive experiments show that our model can
outperform state-of-the-art baselines on large datasets.

  * •

Our solution sheds light on a broader scope of fields that also need
personalization (e.g., personalized conversational systems). In addition, it
points out a way for Transformer to deal with heterogeneous inputs, e.g., text
and images in multimodal artificial intelligence.

##  2 Related Work

Explainable recommendation (Zhang et al., 2014; Zhang and Chen, 2020) has been
studied from two major perspectives: human-computer interaction and machine
learning. The former (Gedikli et al., 2014; Chen and Wang, 2017; Chen et al.,
2019b) investigates how people perceive different styles of explanations,
while the latter provides explanations by designing new explainable
recommendation algorithms, to which our work is more related. There exist
various types of explanation styles, such as pre-defined templates (Zhang et
al., 2014; Li et al., 2020a), ranked sentences (Chen et al., 2019d; Li et al.,
2021), image visualizations (Chen et al., 2019c), knowledge graph paths (Ai et
al., 2018; Xian et al., 2019; Fu et al., 2020; Xian et al., 2020), reasoning
rules (Shi et al., 2020; Chen et al., 2021; Zhu et al., 2021), etc., among
which, recently, generated natural language explanations (Ni et al., 2019; Li
et al., 2020c) have received much attention, mainly owing to the advancement
of natural language generation technology and the availability of textual data
on recommendation platforms such as e-commerce. However, previous works mostly
rely on recurrent neural networks (RNN), e.g., LSTM (Hochreiter and
Schmidhuber, 1997) and GRU (Cho et al., 2014), leaving the potentially more
effective Transformer under-explored, which motivates this work.

Transformer (Vaswani et al., 2017) was first brought to machine translation
with the architecture of encoder-decoder. Later works (Liu et al., 2018;
Devlin et al., 2019) show that it remains effective, even when the encoder or
the decoder is removed, reducing nearly half of the parameters. Under the
paradigm of pre-training plus fine-tuning, Transformer’s effectiveness has
been confirmed on a wide range of tasks, including both natural language
understanding and generation (Radford et al., 2018; Devlin et al., 2019; Dong
et al., 2019). Particularly, it is able to perform novel tasks, e.g.,
arithmetic, after scaling up both the model and the training data (Radford et
al., 2019; Brown et al., 2020). However, it may not be friendly to researchers
who do not possess large amounts of computing resources. Instead, our work
explores small unpretrained models, as they are computationally cheaper and
more flexible when being adapted to new applications, e.g., personalized
generation.

Personalized generation usually involves the IDs of users and items. Previous
approaches typically adopt multi-layer perceptron (MLP) to encode the IDs into
a context vector, from which RNN can decode a word sequence. This strategy can
be found in many applications, such as review generation (Dong et al., 2017),
tip generation (Li et al., 2017) and explanation generation (Li et al.,
2020c). However, it does not fit Transformer that relies entirely on self-
attention. Probably because a proper solution to deal with heterogeneous
inputs (i.e., IDs and words) is yet to be found, previous works with
Transformer for personalized generation replace IDs with text segments, such
as persona attributes (Zheng et al., 2020), movie titles (Zhou et al., 2020)
and item features (Ni et al., 2019), which are in the same semantic space as
the word sequence to be generated. In comparison, our solution is to design an
effective task that can give the IDs linguistic meanings, thus connecting IDs
with words.

Figure 2: Our proposed model PETER that contains three tasks. The input
features are optional.

##  3 Problem Formulation

The goal of our explanation task is to generate a natural language sentence
$\hat{E}_{u,i}$ for a pair of user $u$ and item $i$ to justify why $i$ is
recommended to $u$. Meanwhile, our model PETER can also make recommendations
by estimating a rating $\hat{r}_{u,i}$ that predicts $u$’s preference towards
$i$. At the testing stage, only user $u$ and item $i$ are used as inputs for
producing both explanation and recommendation. When item features $F_{u,i}$
are available, our model is flexible to incorporate them by simply
concatenating them at the beginning of the explanation. In this case, the
features are also needed in the testing stage. In the following, we will
discuss both cases.

##  4 Methodology

In this section, we present the details of our model PETER. First, we show how
to encode different types of tokens in a sequence. Then, we briefly review
Transformer and introduce our revised attention masking matrix. At last, we
formulate the three tasks, i.e., explanation generation, context prediction
and recommendation, and integrate them into a multi-task learning framework.

###  4.1 Input Representation

We first introduce our way to encode heterogeneous inputs into vector
representations. As shown in Fig. 2, the input to our model is a sequence,
consisting of user ID $u$, item ID $i$, features $F_{u,i}$, and explanation
$E_{u,i}$. The user and the item serve for the purpose of personalization,
i.e., aiming to make the generated explanation reflect both the user’s
interests and the item’s attributes. The features can guide the model to talk
about certain topics. For instance, a conversational recommender system may
explain a recommendation’s specialty to the user with the goal of knowing more
about his/her preference (Chen et al., 2020). Since the features are not
always available, in our experiments we test both cases (with and without
them). When they are available, the input sequence can be represented as
$S=[u,i,f_{1},\cdots,f_{\left|F_{u,i}\right|},e_{1},\cdots,e_{\left|E_{u,i}\right|}]$,
where $f_{1},\cdots,f_{\left|F_{u,i}\right|}$ are the features and
$e_{1},\cdots,e_{\left|E_{u,i}\right|}$ are the explanation’s word sequence.
$\left|F_{u,i}\right|$ denotes the number of features and
$\left|E_{u,i}\right|$ is the number of words in the explanation.

Figure 3: The attention masking used in our model that we call PETER masking.
The orange box highlights its difference from the Left-to-Right masking.

Clearly there are three types of tokens in the sequence $S$, i.e., users,
items, and words (including features), for which we prepare three sets of
randomly initialized token embeddings $\mathbf{U}$, $\mathbf{I}$ and
$\mathbf{V}$ respectively, besides the positional embeddings $\mathbf{P}$ that
encode the position of each token in the sequence. Notice that, we do not add
users and items to the vocabulary $\mathcal{V}$, given that it costs more time
to predict a word out of the huge amount of IDs (for example, millions of
users and items in e-commerce). After performing embedding look-up, we can
obtain the sequence’s token representation
$[\mathbf{u},\mathbf{i},\mathbf{f}_{1},\cdots,\mathbf{f}_{\left|F_{u,i}\right|},\mathbf{e}_{1},\cdots,\mathbf{e}_{\left|E_{u,i}\right|}]$
and its positional representation
$[\mathbf{p}_{1},\cdots,\mathbf{p}_{\left|S\right|}]$, where $\left|S\right|$
is the length of the sequence. The input representation of the sequence is the
addition of the corresponding token representation and positional
representation, denoted as
$\mathbf{S}_{0}=[\mathbf{s}_{0,1},\cdots,\mathbf{s}_{0,\left|S\right|}]$.

###  4.2 Transformer and Attention Masking

To enable the three tasks, we show how to modify the attention masking
mechanism in Transformer (Vaswani et al., 2017). Transformer consists of $L$
identical layers, each of which is composed of two sub-layers: multi-head
self-attention and position-wise feed-forward network. The $l$-th layer
encodes the previous layer’s output $\mathbf{S}_{l-1}$ into $\mathbf{S}_{l}$,
where $l\in[1,L]$. In the multi-head self-attention sub-layer, the computation
of each attention head is also identical, and among the $H$ heads of the
$l$-th layer, the $h$-th head $\mathbf{A}_{l,h}$ is computed as follows:

$\displaystyle\mathbf{A}_{l,h}$
$\displaystyle=\text{softmax}(\frac{\mathbf{Q}_{l,h}\mathbf{K}_{l,h}^{\top}}{\sqrt{d}}+\mathbf{M})\mathbf{V}_{l,h}$
(1) $\displaystyle\mathbf{Q}_{l,h}$
$\displaystyle=\mathbf{S}_{l-1}\mathbf{W}_{l,h}^{Q},\mathbf{K}_{l,h}=\mathbf{S}_{l-1}\mathbf{W}_{l,h}^{K},$
$\displaystyle\mathbf{V}_{l,h}$
$\displaystyle=\mathbf{S}_{l-1}\mathbf{W}_{l,h}^{V}$ $\displaystyle\mathbf{M}$
$\displaystyle=\begin{cases}0,&\text{Allow to attend}\\\
-\infty,&\text{Prevent from attending}\end{cases}$

where $\mathbf{S}_{l-1}\in\mathbb{R}^{\left|S\right|\times d}$ is the
$(l-1)$-th layer’s output,
$\mathbf{W}_{l,h}^{Q},\mathbf{W}_{l,h}^{K},\mathbf{W}_{l,h}^{V}\in\mathbb{R}^{d\times\frac{d}{H}}$
are projection matrices, $d$ denotes the dimension of embeddings, and
$\mathbf{M}\in\mathbb{R}^{\left|S\right|\times\left|S\right|}$ is the
attention masking matrix.

Each element in $\mathbf{M}$ controls whether a token in the sequence can
attend to another. For example, in the unidirectional left-to-right language
model (Radford et al., 2018), the lower triangular part of $\mathbf{M}$ is set
to $0$ and the remaining part $-\infty$, so as to allow each token to attend
to past tokens (including itself), but prevent it from attending to future
tokens. We call it Left-to-Right Masking. As our model is not limited to the
left-to-right explanation generation task, we modify the masking mechanism to
accommodate the other two tasks (i.e., context prediction and recommendation).
As shown in Fig. 3, the first two tokens $u$ and $i$ in the sequence can
attend to each other, because both context prediction and recommendation tasks
need them. To echo our model, we name it PETER Masking.

###  4.3 Explanation and Recommendation

In the following, we perform the three tasks, after obtaining the sequence’s
final representation
$\mathbf{S}_{L}=[\mathbf{s}_{L,1},\cdots,\mathbf{s}_{L,\left|S\right|}]$ from
Transformer. The key challenge lies in the personalization of explanation
generation task, for which we design the context prediction task. For both
tasks, we apply a linear layer to the final representation of each token to
map it into a $\left|\mathcal{V}\right|$-sized vector. As an example, after
passing through this layer, $\mathbf{s}_{L,t}$ becomes $\mathbf{c}_{t}$:

$\mathbf{c}_{t}=\text{softmax}(\mathbf{W}^{v}\mathbf{s}_{L,t}+\mathbf{b}^{v})$
(2)

where $\mathbf{W}^{v}\in\mathbb{R}^{\left|\mathcal{V}\right|\times d}$ and
$\mathbf{b}^{v}\in\mathbb{R}^{\left|\mathcal{V}\right|}$ are weight
parameters. The vector $\mathbf{c}_{t}$ represents the probability
distribution over the vocabulary $\mathcal{V}$, from which a word $e$ with
probability $c_{t}^{e}$ can be sampled.

#### Explanation Generation:

We adopt the Negative Log-Likelihood (NLL) as the explanation task’s loss
function, and compute the mean of user-item pairs in the training set:

$\mathcal{L}_{e}=\frac{1}{\left|\mathcal{T}\right|}\sum_{(u,i)\in\mathcal{T}}\frac{1}{\left|E_{u,i}\right|}\sum_{t=1}^{\left|E_{u,i}\right|}-\log
c_{2+\left|F_{u,i}\right|+t}^{e_{t}}$ (3)

where $\mathcal{T}$ denotes the training set. The probability $c_{t}^{e_{t}}$
is offset by $2+\left|F_{u,i}\right|$ positions because the explanation is
placed at the end of the sequence, and $\left|F_{u,i}\right|=0$ when the
features are unavailable.

At the testing stage, along with $u$, $i$, and $F_{u,i}$ (if available), we
feed the model a special begin-of-sequence token $<$bos$>$. From its resulting
probability distribution $\mathbf{c}_{<bos>}$, the model can predict a word.
For simplicity, among the many decoding methods, we opt for greedy decoding
that samples the word with the largest probability. Then we can concatenate
this predicted word at the end of the sequence to form a new input sequence
for generating another word. We do this repeatedly until the model produces a
special end-of-sequence token $<$eos$>$, or the generated explanation
$\hat{E}_{u,i}$ reaches a pre-defined length.

#### Context Prediction:

As discussed earlier, when there is only one task of explanation generation,
Transformer fails to make use of user ID and item ID, resulting in identical
sentences. To address this issue, we design this task to map the IDs onto the
words in the explanation, so as to build a connection between them. Since the
first two positions ($u$ and $i$) of the sequence are allowed to attend to
each other, both of their final representations absorb the information of the
user and the item. Thus, we can use either of them to perform this task. Here,
we use the 2nd one for better illustration in Fig. 2. Again, we adopt NLL as
the loss function:

$\mathcal{L}_{c}=\frac{1}{\left|\mathcal{T}\right|}\sum_{(u,i)\in\mathcal{T}}\frac{1}{\left|E_{u,i}\right|}\sum_{t=1}^{\left|E_{u,i}\right|}-\log
c_{2}^{e_{t}}$ (4)

where the difference from Eq. (3) is that all predicted words are from the 2nd
position, which is why they are not sequentially ordered (see Fig. 2).

#### Rating Prediction:

Recommendation can be seen as a prediction problem (Chen et al., 2021) where
the goal is to predict a score $\hat{r}_{u,i}$ based on the IDs of user $u$
and item $i$. As both $u$ and $i$ in the sequence can attend to each other,
their final representations capture the interaction between them. Next, we map
the 1st representation $\mathbf{s}_{L,1}$ into a scalar (because the 2nd one
is used for context prediction). To this end, we employ multi-layer perceptron
(MLP) with one hidden layer as follows:

$\hat{r}_{u,i}=\mathbf{w}^{r}\sigma(\mathbf{W}^{r}\mathbf{s}_{L,1}+\mathbf{b}^{r})+b^{r}$
(5)

where $\mathbf{W}^{r}\in\mathbb{R}^{d\times d}$,
$\mathbf{b}^{r}\in\mathbb{R}^{d}$, $\mathbf{w}^{r}\in\mathbb{R}^{1\times d}$
and $b^{r}\in\mathbb{R}$ are weight parameters, and $\sigma(\cdot)$ is the
sigmoid function. Therefore, it can be seen that it is feasible to do both
recommendation and explanation on Transformer. As recommendation is not the
key focus of this paper, we leave its improvement in the future work. For this
task, we use Mean Square Error (MSE) as the loss function:

$\mathcal{L}_{r}=\frac{1}{\left|\mathcal{T}\right|}\sum_{(u,i)\in\mathcal{T}}(r_{u,i}-\hat{r}_{u,i})^{2}$
(6)

where $r_{u,i}$ is the ground-truth rating.

#### Multi-task Learning:

At last, we integrate the three tasks into a multi-task learning framework
whose objective function is defined as:

$\mathcal{J}=\min_{\Theta}(\lambda_{e}\mathcal{L}_{e}+\lambda_{c}\mathcal{L}_{c}+\lambda_{r}\mathcal{L}_{r})$
(7)

where $\Theta$ denotes all the trainable parameters in the model, and
$\lambda_{e}$, $\lambda_{c}$ and $\lambda_{r}$ are regularization weights that
balance the learning of different tasks. In this way, the model can be trained
efficiently in an end-to-end manner.

##  5 Experimental Setup

###  5.1 Datasets

For experimentation, we adopt three publicly available explainable
recommendation datasets, and their data splits (Li et al., 2020c). During the
splitting process, each dataset is randomly divided into training, validation
and testing sets with ratio 8:1:1 for 5 times, and the training set holds at
least one record for each user and each item. The three datasets are
respectively from TripAdvisor (hotel), Amazon (movies & TV) and Yelp
(restaurant). Each record in the datasets is comprised of a user ID, an item
ID, a rating, an explanation, and a feature. The explanations are sentences
extracted from user reviews. Each explanation contains at least one item
feature, e.g., bedroom, which ensures the explanation quality. Statistics of
the datasets are shown in Table 1. We can see that Yelp is much larger than
the other two in terms of size, making it closer to the real-world situation
where there are millions of users and items.

| Yelp | Amazon | TripAdvisor
---|---|---|---
#users | 27,147 | 7,506 | 9,765
#items | 20,266 | 7,360 | 6,280
#records | 1,293,247 | 441,783 | 320,023
#features | 7,340 | 5,399 | 5,069
#records / user | 47.64 | 58.86 | 32.77
#records / item | 63.81 | 60.02 | 50.96
#words / exp | 12.32 | 14.14 | 13.01
* exp denotes explanation.
Table 1: Statistics of the three datasets.

###  5.2 Evaluation Metrics

To evaluate the recommendation performance, we adopt two commonly used
metrics: Root Mean Square Error (RMSE) and Mean Absolute Error (MAE). As to
explanation performance, we measure the generated explanations from two main
perspectives: text quality and explainability. For the former, we adopt BLEU
(Papineni et al., 2002) in machine translation and ROUGE (Lin, 2004) in text
summarization, and report BLEU-1 and BLEU-4, and Precision, Recall and F1 of
ROUGE-1 and ROUGE-2. Though being widely used, BLUE and ROUGE are not
flawless. For example, it is difficult for them to detect the problem of
identical sentences generated by Transformer. These identical sentences might
not be used as explanations, because they are less likely to well explain the
special property of different recommendations. To quantitatively measure how
severe the problem is, we adopt USR that computes the Unique Sentence Ratio of
generated sentences (Li et al., 2020c).

Text quality, however, is not equal to explainbility. In the case of
explainable recommendation, users may value more an explanation that justifies
a recommendation’s advantages on certain features (Li et al., 2020c; Chen et
al., 2019a). To this end, we adopt the other three metrics proposed by (Li et
al., 2020c): Feature Matching Ratio (FMR), Feature Coverage Ratio (FCR) and
Feature Diversity (DIV). FMR measures whether a generated explanation contains
the feature in the ground-truth. FCR is computed as the number of distinct
features contained in all the generated explanations, divided by the total
number of features in the whole dataset. DIV measures the intersection of
features between any two generated explanations.

For RMSE, MAE and DIV, the lower, the better, while it is opposite for the
rest of metrics.

| Explainability | Text Quality
---|---|---
FMR$\uparrow$ | FCR$\uparrow$ | DIV$\downarrow$ | USR$\uparrow$ | B1$\uparrow$ | B4$\uparrow$ | R1-P$\uparrow$ | R1-R$\uparrow$ | R1-F$\uparrow$ | R2-P$\uparrow$ | R2-R$\uparrow$ | R2-F$\uparrow$
| Yelp
Transformer | 0.06 | 0.06 | 2.46 | 0.01 | 7.39 | 0.42 | 19.18 | 10.29 | 12.56 | 1.71 | 0.92 | 1.09
NRT | 0.07 | 0.11 | 2.37 | 0.12 | 11.66 | 0.65 | 17.69 | 12.11 | 13.55 | 1.76 | 1.22 | 1.33
Att2Seq | 0.07 | 0.12 | 2.41 | 0.13 | 10.29 | 0.58 | 18.73 | 11.28 | 13.29 | 1.85 | 1.14 | 1.31
PETER |  0.08** |  0.19** |  1.54** | 0.13 | 10.77 |  0.73** | 18.54 | 12.20 |  13.77** |  2.02** |  1.38** |  1.49**
ACMLM | 0.05 | 0.31 | 0.95 | 0.95 | 7.01 | 0.24 | 7.89 | 7.54 | 6.82 | 0.44 | 0.48 | 0.39
NETE | 0.80 | 0.27 | 1.48 | 0.52 | 19.31 | 2.69 | 33.98 | 22.51 | 25.56 | 8.93 | 5.54 | 6.33
PETER+ |  0.86** |  0.38** | 1.08 | 0.34 |  20.80** |  3.43** |  35.44** |  26.12** |  27.95** |  10.65** |  7.44** |  7.94**
| Amazon
Transformer | 0.10 | 0.01 | 3.26 | 0.00 | 9.71 | 0.59 | 19.68 | 11.94 | 14.11 | 2.10 | 1.39 | 1.55
NRT | 0.12 | 0.07 | 2.93 | 0.17 | 12.93 | 0.96 | 21.03 | 13.57 | 15.56 | 2.71 | 1.84 | 2.05
Att2Seq | 0.12 | 0.20 | 2.74 | 0.33 | 12.56 | 0.95 | 20.79 | 13.31 | 15.35 | 2.62 | 1.78 | 1.99
PETER |  0.12** | 0.21 |  1.75** | 0.29 | 12.77 |  1.17** | 19.81 | 13.80 | 15.23 | 2.80 |  2.08** |  2.20**
ACMLM | 0.10 | 0.31 | 2.07 | 0.96 | 9.52 | 0.22 | 11.65 | 10.39 | 9.69 | 0.71 | 0.81 | 0.64
NETE | 0.71 | 0.19 | 1.93 | 0.57 | 18.76 | 2.46 | 33.87 | 21.43 | 24.81 | 7.58 | 4.77 | 5.46
PETER+ |  0.77** |  0.31** |  1.20** | 0.46 |  19.75** |  3.06** |  34.71** |  23.99** |  26.35** |  9.04** |  6.23** |  6.71**
| TripAdvisor
Transformer | 0.04 | 0.00 | 10.00 | 0.00 | 12.79 | 0.71 | 16.52 | 16.38 | 15.88 | 2.22 | 2.63 | 2.34
NRT | 0.06 | 0.09 | 4.27 | 0.08 | 15.05 | 0.99 | 18.22 | 14.39 | 15.40 | 2.29 | 1.98 | 2.01
Att2Seq | 0.06 | 0.15 | 4.32 | 0.17 | 15.27 | 1.03 | 18.97 | 14.72 | 15.92 | 2.40 | 2.03 | 2.09
PETER |  0.07** | 0.13 |  2.95** | 0.08 |  15.96** |  1.11* | 19.07 | 16.09 |  16.48** | 2.33 | 2.17 | 2.09
ACMLM | 0.07 | 0.41 | 0.78 | 0.94 | 3.45 | 0.02 | 4.86 | 3.82 | 3.72 | 0.18 | 0.20 | 0.16
NETE | 0.78 | 0.27 | 2.22 | 0.57 | 22.39 | 3.66 | 35.68 | 24.86 | 27.71 | 10.20 | 6.98 | 7.66
PETER+ |  0.89** | 0.35 | 1.61 | 0.25 |  24.32** |  4.55** |  37.48** |  29.21** |  30.49** |  11.92** |  8.98** |  9.24**
Table 2: Performance comparison of the generation methods in terms of
Explainability and Text Quality on three datasets. The methods are divided
into two groups according to whether features are used or not. B1 and B4 stand
for BLEU-1 and BLEU-4. R1-P, R1-R, R1-F, R2-P, R2-R and R2-F denote Precision,
Recall and F1 of ROUGE-1 and ROUGE-2. BLEU and ROUGE are percentage values (%
symbol omitted for table clarity), while the others are absolute values. The
best performing values are boldfaced, and the second best underlined. ** and *
indicate the statistical significance over the second best baseline
respectively for $p<0.01$ and $p<0.05$ via Student’s t-test.

###  5.3 Compared Methods

We introduce baselines, first for explanation and then for recommendation. For
the former, we divide the baselines into two groups, depending on whether the
feature is used or not.

The following models leverage only user and item IDs to generate explanations
(without feature). We denote our model without feature as PETER.

  * •

Transformer (Vaswani et al., 2017) performs the explanation generation task by
treating user and item IDs as words. We also tested encoder-decoder
Transformer, where the encoder encodes the IDs for the decoder to decode, but
its results turned out to be the same, so we do not report it.

  * •

NRT (Li et al., 2017) can predict a rating and generate a tip simultaneously
based on user and item IDs. We take the explanations in the datasets as tips.
Moreover, we found that the model’s problem of generating identical sentences
(as reported in Li et al., 2020c) is caused by the L2 regularization in its
original design. For fair comparison, we removed it.

  * •

Att2Seq (Dong et al., 2017) is a review generation approach and we take the
explanations as reviews. This model has an attention module, but we found that
it makes the generated content unreadable in the task. To be fair, we removed
it as well.

When features are used, we denote our model as PETER+, and compare it with two
recent models:

  * •

ACMLM (Ni et al., 2019) is a fine-tuned BERT (Devlin et al., 2019), where an
attention layer is introduced to encode the features from both the user and
the item. By predicting masked tokens, this model can produce diverse
sentences.

  * •

NETE (Li et al., 2020c) is a tailored GRU (Cho et al., 2014) that incorporates
a given feature into the decoding process to generate template-like
explanations. It can also make recommendations.

For recommendation, besides NRT and NETE, we include another two traditional
methods:

  * •

PMF (Mnih and Salakhutdinov, 2007) is a standard probabilistic matrix
factorization method that characterizes users and items by latent factors.

  * •

SVD++ (Koren, 2008) leverages a user’s interacted items to enhance the latent
factors.

###  5.4 Implementation Details

We train each model on the training set, tune the hyper-parameters on the
validation set, and report the performance on the testing set. The results are
averaged on the 5 data splits. We adopt the codes of ACMLM and NETE, and
implement all the other methods. For NRT, Att2Seq, NETE and our PETER and
PETER+, we set the size of vocabulary to 20,000 by keeping the most frequent
words. We do not apply this to Transformer, otherwise users and items
(regarded as words) may be filtered out. We set both the number of context
words and the length of explanations to 15, because the mean length of
explanations is approximately 13 (see Table 1). ACMLM adopts sub-words, so we
do not apply the above two steps to it. We reuse the other default settings of
the baselines.

| Time | Epochs | Time/Epoch
---|---|---|---
ACMLM | 97.0 | 3 | 32.3
PETER+ | 57.7 | 25 | 2.3
Table 3: Efficiency comparison of two Transformer-based models in terms of training minutes on the TripAdvisor dataset, tested on NVIDIA Tesla P40. | Top-15 Context Words | Explanation
---|---|---
Ground-truth |  | the rooms are spacious and the bathroom has a large tub
PETER |  $<$eos$>$ the and a pool was with nice is very were to good in of | the pool area is nice and the gym is very well equipped $<$eos$>$
PETER+ |  $<$eos$>$ the and a was pool with to nice good very were is of in | the rooms were clean and comfortable $<$eos$>$
Ground-truth |  | beautiful lobby and nice bar
PETER |  $<$eos$>$ the and a was were separate bathroom with shower large very had in is | the bathroom was large and the shower was great $<$eos$>$
PETER+ |  $<$eos$>$ the and a was bathroom shower with large in separate were room very is | the lobby was very nice and the rooms were very comfortable $<$eos$>$
Table 4: Context words and explanations on two different cases as generated by
our PETER and PETER+ on TripAdvisor dataset. The boldfaced words in the
ground-truth are the key features. Generated features are underlined.

For Transformer, PETER and PETER+, we set the embedding size $d$ to 512 and
the dimension of feed-forward network to 2,048, following (Vaswani et al.,
2017), but the number of layers $L$ and attention heads $H$ are both 2. For
our models PETER and PETER+, we set the regularization weights $\lambda_{e}$,
$\lambda_{c}$ and $\lambda_{r}$ to 1.0, 1.0 and 0.1, respectively. We optimize
the model via stochastic gradient descent (Robbins and Monro, 1951), and apply
gradient clipping (Pascanu et al., 2013) with a threshold of 1.0. The batch
size is set to 128, and the learning rate 1.0. At each epoch, we save the
model if it achieves the lowest loss on the validation set, but when there is
no improvement, we decrease the learning rate by a factor of 0.25. When the
latter happens for 5 times, we stop training and load the saved model for
prediction.

##  6 Results and Analysis

###  6.1 Quantitative Analysis on Explanations

In Table 2, we compare the performance of explanation generation methods in
two groups. We first analyze models that make use of item features (i.e.,
ACMLM, NETE and PETER+). Our PETER+ consistently and significantly outperforms
ACMLM and NETE on the three datasets in terms of text quality (BLEU and
ROUGE). This shows the effectiveness of our model in generating high-quality
sentences. Notice that Li et al. (2020b) conducted a user survey and reported
that NETE’s explanations were perceived useful by most participants. It
suggests that our model’s explanations with better quality could also be very
useful to real users.

Again, in terms of text quality, the performance gap between PETER+ and ACMLM
(a fine-tuned BERT) is extremely large, because the latter’s generation is
achieved by predicting masked tokens, which is quite different from word-by-
word generation. This may explain why ACMLM produces diverse sentences (high
USR), which, however, is less meaningful when text quality cannot be
guaranteed. Furthermore, PETER+ beats both ACMLM and NETE on the
explainability metric FMR that cares about whether a generated explanation
mentions the feature in the ground-truth. This is quite useful in real-world
applications when the system is asked to explain a particular feature.
Regarding the other two explainability metrics FCR and DIV, PETER+ is also
very competitive. ACMLM gains better performance on some cases, because at the
training stage it is exposed to more features (from both the user and the
item), which is unfair to both PETER+ and NETE.

Next, we discuss the results of the models that only leverage user and item
IDs for generation. As it can be seen, Transformer generates identical
explanations on each dataset, resulting in nearly 0 score on Unique Sentence
Ratio (USR). Owing to the context prediction task, our PETER successfully
addresses this issue, producing diverse (comparable USR) and high-quality
(best BLEU-4) sentences. In particular, on the largest dataset Yelp, it
achieves the best performance on most of the metrics. This again demonstrates
the effectiveness of our model. On Amazon and TripAdvisor, NRT and Att2Seq are
very competitive, because we fixed their generation issues (see Section 5.3).
In addition, the two datasets are small and thus the training samples are
limited, so our model may underfit, which is why it does not always reach the
best performance.

| Yelp | Amazon | TripAdvisor
---|---|---|---
R$\downarrow$ | M$\downarrow$ | R$\downarrow$ | M$\downarrow$ | R$\downarrow$ | M$\downarrow$
PMF | 1.09 | 0.88 | 1.03 | 0.81 | 0.87 | 0.70
SVD++ | 1.01 | 0.78 | 0.96 | 0.72 | 0.80 | 0.61
NRT | 1.01 | 0.78 | 0.95 | 0.70 | 0.79 | 0.61
NETE | 1.01 | 0.79 | 0.96 | 0.73 | 0.79 | 0.60
PETER | 1.01 | 0.78 | 0.95 | 0.71 | 0.81 | 0.63
Table 5: Recommendation performance comparison in terms of RMSE (R for short) and MAE (denoted as M). The best performing values are boldfaced. | Explainability | Text Quality | Recommendation
---|---|---|---
FMR | FCR | DIV | USR | BLEU-1 | BLEU-4 | RMSE | MAE
Disable $\mathcal{L}_{c}$ | 0.06 $\downarrow$ | 0.03 $\downarrow$ | 5.75 $\downarrow$ | 0.01 $\downarrow$ | 15.37 $\downarrow$ | 0.86 $\downarrow$ | 0.80 $\uparrow$ | 0.61 $\uparrow$
Disable $\mathcal{L}_{r}$ | 0.07 | 0.14 $\uparrow$ | 2.90 $\uparrow$ | 0.10 $\uparrow$ | 16.16 $\uparrow$ | 1.15 $\uparrow$ | 3.23 $\downarrow$ | 3.10 $\downarrow$
Left-to-Right Masking | 0.07 | 0.15 $\uparrow$ | 2.68 $\uparrow$ | 0.12 $\uparrow$ | 15.73 $\downarrow$ | 1.11 | 0.87 $\downarrow$ | 0.68 $\downarrow$
PETER | 0.07 | 0.13 | 2.95 | 0.08 | 15.96 | 1.11 | 0.81 | 0.63
Table 6: Ablation study on the smallest dataset TripAdvisor. Arrows $\uparrow$
and $\downarrow$ respectively denote the performance increase and decrease
compared with PETER.

Besides explanation performance, we also investigate the efficiency of
different Transformer-based models. On the same machine (NVIDIA Tesla P40) and
dataset (TripAdvisor), we compare the training minutes of ACMLM and our PETER+
in Table 3. Compared with ACMLM, our model takes less time to train (2.3
minutes per epoch), since it has only 2 layers and thus less parameters. But
because it is unpretrained and learned from scratch, it needs more training
epochs.

###  6.2 Qualitative Case Study on Explanations

In Table 4, we present two examples generated by PETER and PETER+ on the
TripAdvisor dataset. We can see that PETER generates distinct context words
and explanations for different user-item pairs. This confirms that our
proposed solution can indeed endow the user and item IDs with linguistic
meanings, as well as achieving certain degree of personalization for natural
language generation. Among the commonly used context words, e.g., the, there
are some important features (underlined), according to which the model then
generates an explanation that talks about them. Admittedly, there is still
much room for improvement of the context prediction task, so as to more
accurately predict the features in the ground-truth (e.g., rooms vs. pool in
the first example). One alternative is to leverage the features to guide the
model’s generation. This explains why PETER+ is able to generate an
explanation that talks about rooms rather than pool, making it semantically
closer to the ground-truth. It thus demonstrates our model’s flexibility in
incorporating these features.

###  6.3 Recommendation Performance

Table 5 presents the performance comparison of different recommendation
methods. On the largest dataset Yelp with approximately 1.3 million records,
our model PETER performs as good as the three competitive baselines (i.e.,
SVD++, NRT and NETE), which shows the rationale of our recommendation module.
Since our model PETER has more parameters to learn, it may underfit on small
datasets. This explains why it does not always perform the best on TripAdvisor
and Amazon. When more training data are available to Transformer, usually the
performance will become better, as evidenced by GPT-2 (Radford et al., 2019)
and GPT-3 (Brown et al., 2020). Thus, we can expect our model to perform well
in real-world applications, where the training data are bigger than the
testing datasets, e.g., billion-scale users in Amazon.

###  6.4 Ablation Study

In Table 6, we provide an ablation study conducted on the TripAdvisor dataset.
After disabling the context prediction task $\mathcal{L}_{c}$ by setting
$\lambda_{c}=0$, the performances of both explainability and text quality drop
dramatically, and the unique sentence ratio (USR) is nearly approaching
Transformer’s (see Table 2). It hence confirms this task’s effectiveness. As
$\mathcal{L}_{c}$ is highly correlated with the recommendation task
$\mathcal{L}_{r}$ via the user and item IDs (see Section 4.3), the removal of
$\mathcal{L}_{c}$ leads to slight improvement on recommendation performance.
We can also observe a reversed phenomenon when we disable $\mathcal{L}_{r}$.
When PETER masking is replaced by the Left-to-Right masking that prevents the
model from accessing the item information, the recommendation performance
drops sharply. Overall, PETER reaches an optimal situation, where its
explainability, text quality and recommendation performance are all reasonably
good.

##  7 Conclusion

We propose a simple and effective solution to address the personalized
generation problem of Transformer, unleashing its language modeling power to
generate explanations for recommender systems. Extensive experiments show that
the solution is both effective and efficient. It opens up a new way of
exploiting Transformer by designing good tasks instead of scaling up model
size. There are various applications of personalized generation for which
Transformer is still less explored. Our next step is to adopt our solution for
personalized question answering systems and personalized conversational
agents. We also plan to incorporate item images into the model, so as to
generate visual explanations for recommendations, since “a picture is worth a
thousand words”. Another meaningful extension is to adapt the model to cross-
lingual explanation generation, because international platforms, e.g., Amazon,
may serve users who speak different languages.

## Acknowledgments

This work was partially supported by HKBU IRCMS/19-20/D05, RGC/HKBU12201620,
and NSF IIS-1910154 and IIS-2007907. Any opinions, findings, conclusions or
recommendations expressed in this material are those of the authors and do not
necessarily reflect those of the sponsors.

## References

  * Ai et al. (2018) Qingyao Ai, Vahid Azizi, Xu Chen, and Yongfeng Zhang. 2018.  Learning heterogeneous knowledge base embeddings for explainable recommendation.  _Algorithms_ , 11(9):137.
  * Brown et al. (2020) Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  In _Advances in neural information processing systems_.
  * Chen et al. (2019a) Hanxiong Chen, Xu Chen, Shaoyun Shi, and Yongfeng Zhang. 2019a.  Generate natural language explanations for recommendation.  In _Proceedings of SIGIR’19 Workshop on ExplainAble Recommendation and Search_. ACM.
  * Chen et al. (2021) Hanxiong Chen, Shaoyun Shi, Yunqi Li, and Yongfeng Zhang. 2021.  Neural collaborative reasoning.  In _Proceedings of The Web Conference 2021_.
  * Chen and Wang (2017) Li Chen and Feng Wang. 2017.  Explaining recommendations based on feature sentiments in product reviews.  In _Proceedings of the 22nd International Conference on Intelligent User Interfaces_ , pages 17–28.
  * Chen et al. (2019b) Li Chen, Dongning Yan, and Feng Wang. 2019b.  User evaluations on sentiment-based recommendation explanations.  _ACM Transactions on Interactive Intelligent Systems (TiiS)_ , 9(4):1–38.
  * Chen et al. (2019c) Xu Chen, Hanxiong Chen, Hongteng Xu, Yongfeng Zhang, Yixin Cao, Zheng Qin, and Hongyuan Zha. 2019c.  Personalized fashion recommendation with visual explanations based on multimodal attention network: Towards visually explainable recommendation.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 765–774.
  * Chen et al. (2019d) Xu Chen, Yongfeng Zhang, and Zheng Qin. 2019d.  Dynamic explainable recommendation based on neural attentive models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 53–60.
  * Chen et al. (2020) Zhongxia Chen, Xiting Wang, Xing Xie, Mehul Parsana, Akshay Soni, Xiang Ao, and Enhong Chen. 2020.  Towards explainable conversational recommendation.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence_.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1724–1734.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics_.
  * Dong et al. (2017) Li Dong, Shaohan Huang, Furu Wei, Mirella Lapata, Ming Zhou, and Ke Xu. 2017.  Learning to generate product reviews from attributes.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 623–632.
  * Dong et al. (2019) Li Dong, Nan Yang, Wenhui Wang, Furu Wei, Xiaodong Liu, Yu Wang, Jianfeng Gao, Ming Zhou, and Hsiao-Wuen Hon. 2019.  Unified language model pre-training for natural language understanding and generation.  In _Advances in Neural Information Processing Systems_ , pages 13063–13075.
  * Fu et al. (2020) Zuohui Fu, Yikun Xian, Ruoyuan Gao, Jieyu Zhao, Qiaoying Huang, Yingqiang Ge, Shuyuan Xu, Shijie Geng, Chirag Shah, Yongfeng Zhang, et al. 2020.  Fairness-aware explainable recommendation over knowledge graphs.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Gedikli et al. (2014) Fatih Gedikli, Dietmar Jannach, and Mouzhi Ge. 2014.  How should i explain? a comparison of different explanation types for recommender systems.  _International Journal of Human-Computer Studies_ , 72(4):367–382.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * Koren (2008) Yehuda Koren. 2008.  Factorization meets the neighborhood: a multifaceted collaborative filtering model.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 426–434.
  * Li et al. (2019) Junjie Li, Haoran Li, and Chengqing Zong. 2019.  Towards personalized review summarization via user-aware sequence network.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 6690–6697.
  * Li et al. (2020a) Lei Li, Li Chen, and Ruihai Dong. 2020a.  Caesar: context-aware explanation based on supervised attention for service recommendations.  _Journal of Intelligent Information Systems_ , pages 1–24.
  * Li et al. (2020b) Lei Li, Li Chen, and Yongfeng Zhang. 2020b.  Towards controllable explanation generation for recommender systems via neural template.  In _Companion Proceedings of the Web Conference 2020_ , pages 198–202.
  * Li et al. (2020c) Lei Li, Yongfeng Zhang, and Li Chen. 2020c.  Generate neural template explanations for recommendation.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 755–764.
  * Li et al. (2021) Lei Li, Yongfeng Zhang, and Li Chen. 2021.  Extra: Explanation ranking datasets for explainable recommendation.  In _Proceedings of the 44th International ACM SIGIR conference on Research and Development in Information Retrieval_.
  * Li et al. (2017) Piji Li, Zihao Wang, Zhaochun Ren, Lidong Bing, and Wai Lam. 2017.  Neural rating regression with abstractive tips generation for recommendation.  In _Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 345–354.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81.
  * Liu et al. (2018) Peter J Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. 2018.  Generating wikipedia by summarizing long sequences.  In _The Sixth International Conference on Learning Representations_.
  * Mnih and Salakhutdinov (2007) Andriy Mnih and Russ R Salakhutdinov. 2007.  Probabilistic matrix factorization.  In _Advances in neural information processing systems_ , pages 1257–1264.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying recommendations using distantly-labeled reviews and fine-grained aspects.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 188–197.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Pascanu et al. (2013) Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. 2013.  On the difficulty of training recurrent neural networks.  In _International conference on machine learning_ , pages 1310–1318.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018.  Improving language understanding by generative pre-training.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Robbins and Monro (1951) Herbert Robbins and Sutton Monro. 1951.  A stochastic approximation method.  _The annals of mathematical statistics_ , pages 400–407.
  * Shi et al. (2020) Shaoyun Shi, Hanxiong Chen, Weizhi Ma, Jiaxin Mao, Min Zhang, and Yongfeng Zhang. 2020.  Neural logic reasoning.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 1365–1374.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Xian et al. (2019) Yikun Xian, Zuohui Fu, S Muthukrishnan, Gerard De Melo, and Yongfeng Zhang. 2019\.  Reinforcement knowledge graph reasoning for explainable recommendation.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 285–294.
  * Xian et al. (2020) Yikun Xian, Zuohui Fu, Handong Zhao, Yingqiang Ge, Xu Chen, Qiaoying Huang, Shijie Geng, Zhou Qin, Gerard De Melo, Shan Muthukrishnan, et al. 2020.  Cafe: Coarse-to-fine neural symbolic reasoning for explainable recommendation.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 1645–1654.
  * Zhang and Chen (2020) Yongfeng Zhang and Xu Chen. 2020.  Explainable recommendation: A survey and new perspectives.  _Foundations and Trends® in Information Retrieval_ , 14(1):1–101.
  * Zhang et al. (2018) Yongfeng Zhang, Xu Chen, Qingyao Ai, Liu Yang, and W Bruce Croft. 2018.  Towards conversational search and recommendation: System ask, user respond.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , pages 177–186.
  * Zhang et al. (2014) Yongfeng Zhang, Guokun Lai, Min Zhang, Yi Zhang, Yiqun Liu, and Shaoping Ma. 2014\.  Explicit factor models for explainable recommendation based on phrase-level sentiment analysis.  In _Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval_, pages 83–92.
  * Zheng et al. (2020) Yinhe Zheng, Rongsheng Zhang, Minlie Huang, and Xiaoxi Mao. 2020.  A pre-training based personalized dialogue generation model with persona-sparse data.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 9693–9700.
  * Zhou et al. (2020) Kun Zhou, Wayne Xin Zhao, Shuqing Bian, Yuanhang Zhou, Ji-Rong Wen, and Jingsong Yu. 2020.  Improving conversational recommender systems via knowledge graph based semantic fusion.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1006–1014.
  * Zhu et al. (2021) Yaxin Zhu, Yikun Xian, Zuohui Fu, Gerard de Melo, and Yongfeng Zhang. 2021.  Faithfully explainable recommendation via neural logic reasoning.  In _2021 Annual Conference of the North American Chapter of the Association for Computational Linguistics_.


# Rates of asymptotic regularity for the alternating Halpern-Mann iteration

Laurenţiu Leuşteana,c,d and Pedro Pintob
aLOS, Faculty of Mathematics and Computer Science, University of Bucharest
bDepartment of Mathematics, Technische Universität Darmstadt
c Simion Stoilow Institute of Mathematics of the Romanian Academy
d Institute for Logic and Data Science, Bucharest
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper we extend to $UCW$-hyperbolic spaces the quantitative asymptotic
regularity results for the alternating Halpern-Mann iteration obtained by
Dinis and the second author for CAT(0) spaces. These results are new even for
uniformly convex normed spaces. Furthermore, for a particular choice of the
parameter sequences, we compute linear rates of asymptotic regularity in
$W$-hyperbolic spaces and quadratic rates of $T$\- and $U$-asymptotic
regularity in CAT(0) spaces.

Keywords: Mann iteration; Halpern iteration; Rates of asymptotic regularity;
Uniform convexity; Proof mining.

Mathematics Subject Classification 2020: 47J25, 47H09, 03F10.

##  1 Introduction

Let $X$ be a CAT(0) space, $C\subseteq X$ a convex subset, and $T,U:C\to C$
two nonexpansive mappings. Dinis and the second author introduced recently [7]
the alternating Halpern-Mann iteration $(x_{n})$ as follows: if $x_{0},u\in C$
and $(\alpha_{n})_{n\in{\mathbb{N}}}$, $(\beta_{n})_{n\in{\mathbb{N}}}$ are
sequences in $[0,1]$, then

$\begin{cases}x_{2n+1}&=(1-\alpha_{n})Tx_{2n}+\alpha_{n}u,\\\
x_{2n+2}&=(1-\beta_{n})Ux_{2n+1}+\beta_{n}x_{2n+1}.\end{cases}$ (1)

Thus, the alternating Halpern-Mann iteration is an iterative scheme that
alternates between the well-known Halpern [11] and Mann [22, 18, 10]
iterations. As pointed out in [7], $(x_{n})$ is a generalization of the
Tikhonov-Mann iteration, introduced by Cheval and the first author [5] as an
extension of a modified Mann iteration studied by Yao, Zhou, and Liou [25] and
rediscovered by Boţ, Csetnek, and Meier [3]. The Tikhonov-Mann iteration was
recently shown by Cheval, Kohlenbach, and the first author [6] to be
essentially the modified Halpern iteration, a generalization of the Halpern
iteration due to Kim and Xu [12].

Quantitative theorems, providing rates of asymptotic regularity and rates of
metastability for $(x_{n})$, were proved in [7] by using techniques developed
in [8], under the assumption that $T$ and $U$ have common fixed points and the
parameter sequences $(\alpha_{n})$, $(\beta_{n})$ satisfy certain hypotheses.
In particular, the results in [7] show that, in CAT(0) spaces, the alternating
Halpern-Mann iteration converges strongly to a common fixed point of the
mappings.

Rates of asymptotic regularity were obtained for the Halpern iteration by
Kohlenbach and the first author [17] in the much more general setting of
$W$-hyperbolic spaces [14], and for the Mann iteration by the first author
[19] for $UCW$-hyperbolic spaces [19, 20], a class of geodesic spaces that
generalize both CAT(0) spaces and uniformly convex normed spaces. A natural
question is then

to extend to $UCW$-hyperbolic spaces the quantitative asymptotic regularity
results obtained in [7] for CAT(0) spaces.

In this paper, we give an answer to this question by computing uniform rates
of ($T$\- and $U$-)asymptotic regularity for the alternating Halpern-Mann
iteration. These results are new even for uniformly convex normed spaces.

Moreover, we compute for the first time, for a particular choice of the
parameter sequences, linear rates of asymptotic regularity in $W$-hyperbolic
spaces and quadratic rates of $T$\- and $U$-asymptotic regularity in CAT(0)
spaces. In order to obtain the linear rates, we adapt to our setting a lemma
on sequences of real numbers due to Sabach and Shtern [23].

Let us define the asymptotic regularity notions that we use. Assume that
$(X,d)$ is a metric space. A sequence $(z_{n})_{n\in{\mathbb{N}}}$ in $X$ is
asymptotically regular if $\lim\limits_{n\to\infty}d(z_{n},z_{n+1})=0$. A rate
of asymptotic regularity of $(z_{n})$ is a rate of convergence of
$(d(z_{n},z_{n+1}))$ towards $0$. Assume, furthermore, that $\emptyset\neq
C\subseteq X$, $S:C\to C$ is a mapping and $(z_{n})$ is a sequence in $C$. We
say that $(z_{n})$ is $S$-asymptotically regular if
$\lim\limits_{n\to\infty}d(z_{n},Sz_{n})=0$. A rate of $S$-asymptotic
regularity of $(z_{n})$ is a rate of convergence of $(d(z_{n},Sz_{n}))$
towards $0$.

We recall in the following the main quantitative notions that appear
throughout the paper. If $(a_{n})_{n\in{\mathbb{N}}}$ is a sequence in a
metric space $(X,d)$, $a\in X$ and $\varphi:{\mathbb{N}}\to{\mathbb{N}}$, then

  1. (i)

$\varphi$ is a rate of convergence of $(a_{n})$ (towards $a$) if
$\lim\limits_{n\to\infty}a_{n}=a$ and

$\forall k\in{\mathbb{N}}\,\forall
n\geq\varphi(k)\left(d(a_{n},a)\leq\frac{1}{k+1}\right).$

  2. (ii)

$\varphi$ is a Cauchy modulus of $(a_{n})$ if $(a_{n})$ is Cauchy and

$\forall k\in{\mathbb{N}}\,\forall n\geq\varphi(k)\,\forall
p\in{\mathbb{N}}\left(d(a_{n+p},a_{n})\leq\frac{1}{k+1}\right).$

Consider the series $\sum\limits_{n=0}^{\infty}b_{n}$, where
$(b_{n})_{n\in{\mathbb{N}}}$ is a sequence of nonnegative reals. We say that
the series diverges with rate of divergence
$\theta:{\mathbb{N}}\to{\mathbb{N}}$ if
$\sum\limits_{i=0}^{\theta(n)}b_{i}\geq n$ for all $n\in{\mathbb{N}}$.
Furthermore, if $\sum\limits_{n=0}^{\infty}b_{n}$ converges, then a Cauchy
modulus of the series is a Cauchy modulus of the sequence
$\left(\sum\limits_{i=0}^{n}b_{i}\right)$ of partial sums.

##  2 Preliminaries

###  2.1 $UCW$-hyperbolic spaces

Following [5], a metric space $(X,d)$ endowed with a function $W:X\times
X\times[0,1]\to X$ is said to be a $W$-space. As $W$ is thought as a
generalization to metric spaces of the usual convex combination mapping in
normed spaces, we use the notation $(1-\lambda)x+\lambda y$ for
$W(x,y,\lambda)$. Furthermore, we denote a $W$-space simply by $X$. A nonempty
subset $C\subseteq X$ is said to be convex if for all $x,y\in C$ and all
$\lambda\in[0,1]$, $(1-\lambda)x+\lambda y\in C$.

Motivated by proof-theoretical considerations, Kohlenbach introduced in [14]
the class of $W$-hyperbolic spaces (called by him ‘hyperbolic spaces’). This
class of $W$-spaces is now broadly used in the study of nonlinear iterations.
Let us recall that a $W$-hyperbolic space is a $W$-space $X$ satisfying, for
all $x,y,w,z\in X$ and all $\lambda,~{}\tilde{\lambda}\in[0,1]$,

$\begin{array}[]{ll}\text{(W1)}&d(z,(1-\lambda)x+\lambda
y)\leq(1-\lambda)d(z,x)+\lambda d(z,y),\\\\[2.84526pt]
\text{(W2)}&d((1-\lambda)x+\lambda
y,(1-\tilde{\lambda})x+\tilde{\lambda}y)=|\lambda-\tilde{\lambda}|d(x,y),\\\\[2.84526pt]
\text{(W3)}&(1-\lambda)x+\lambda y=\lambda y+(1-\lambda)x,\\\\[2.84526pt]
\text{(W4)}&d((1-\lambda)x+\lambda z,(1-\lambda)y+\lambda
w)\leq(1-\lambda)d(x,y)+\lambda d(z,w).\end{array}$

The following properties of a $W$-hyperbolic space $X$ are easy to verify: for
all $x,y\in X$ and all $\lambda\in[0,1]$,
$\begin{array}[]{ll}\text{(W5)}&(1-\lambda)x+\lambda x=x,\\\\[2.84526pt]
\text{(W6)}&1x+0y=0y+1x=x,\\\\[2.84526pt] \text{(W7)}&d(x,(1-\lambda)x+\lambda
y)\\!=\\!\lambda d(x,y)\text{~{}and~{}}d(y,(1-\lambda)x+\lambda
y)\\!=\\!(1-\lambda)d(x,y).\end{array}$
An immediate example of a $W$-hyperbolic space is (a convex subset of) a
normed space. An extensive discussion on the relations between $W$-hyperbolic
spaces and other geodesic spaces can be found in [15, pp. 384-387].

The class of uniformly convex $W$-hyperbolic spaces was introduced by the
first author in [19], inspired by [9, p. 105], as a generalization to the
nonlinear setting of the well-known uniformly convex normed spaces. Thus, a
uniformly convex $W$-hyperbolic space is a structure $(X,\eta)$, where $X$ is
a $W$-hyperbolic space and $\eta:(0,\infty)\times(0,2]\to(0,1]$ is a so-called
modulus of uniform convexity, satisfying the following: for all $r>0$ and
$\varepsilon\in(0,2]$, and for any $x,y,a\in X$,

$\text{if~{}}d(x,a),d(y,a)\leq r,\text{~{}and~{}}d(x,y)\geq\varepsilon
r,\text{~{}then~{}}d\left(\frac{1}{2}x+\frac{1}{2}y,a\right)\leq(1-\eta(r,\varepsilon))r.$

Following [20], an $UCW$-hyperbolic space is a uniformly convex $W$-hyperbolic
space $(X,\eta)$ with the property that the modulus of uniform convexity is
monotone in the following sense:

for any $\varepsilon\in(0,2]$, if $0<r\leq s$, then
$\eta(s,\varepsilon)\leq\eta(r,\varepsilon)$.

The class of $UCW$-hyperbolic spaces turns out to be an appropriate setting
for obtaining quantitative results on the asymptotic behaviour of the Mann
iteration for (asymptotically) nonexpansive mappings (see [19, 20, 16]), as
well as of the Picard iteration for firmly nonexpansive mappings (see [2]).

The following property of $UCW$-hyperbolic spaces will be used in Section 3.
We refer to [20, Lemma 2.1(iv)] for its proof.

######  Lemma 2.1.

Let $(X,\eta)$ be a $UCW$-hyperbolic space. Assume that $r>0$,
$\varepsilon\in(0,2]$, and $x,y,a\in X$ satisfy

$d(x,a)\leq r,\,d(y,a)\leq r,\text{~{}and~{}}\,d(x,y)\geq\varepsilon r.$

For all $\lambda\in[0,1]$ and any $s\geq r$,

$d((1-\lambda)x+\lambda
y,a)\leq\left(1-2\lambda(1-\lambda)\eta(s,\varepsilon)\right)r.$

Obviously, uniformly convex normed spaces are $UCW$-hyperbolic spaces. CAT(0)
spaces [1, 4] are a very important class of spaces in geodesic geometry and
geometric group theory. The first author showed in [19] that CAT(0) spaces are
$UCW$-hyperbolic spaces with the following modulus of uniform convexity
$\displaystyle\eta(r,\varepsilon)=\frac{\varepsilon^{2}}{8}$, that does not
depend at all on $r$ and is quadratic in $\varepsilon$.

###  2.2 Alternating Halpern-Mann iteration

We give, in the very general setting of $W$-spaces, a reformulation of the
iterative scheme (1) introduced in [7]. Let $X$ be a $W$-space, $C\subseteq X$
a convex subset and $T,U:C\to C$ be nonexpansive mappings. The alternating
Halpern-Mann iteration is defined by the following scheme:

$\begin{split}x_{n+1}&=(1-\beta_{n})Uy_{n}+\beta_{n}y_{n},\\\
y_{n}&=(1-\alpha_{n})Tx_{n}+\alpha_{n}u,\end{split}$ (2)

where $x_{0},u\in C$ and $(\alpha_{n})_{n\in{\mathbb{N}}}$,
$(\beta_{n})_{n\in{\mathbb{N}}}$ are sequences in $[0,1]$.

Notice that for the iteration (1), the even terms correspond to our $(x_{n})$
and the odd terms to our $(y_{n})$. Indeed, this reformulation is just for
convenience of notation.

######  Remark 2.2.

  1. (i)

If $U=Id_{C}$, then $(y_{n})$ is the Halpern iteration.

  2. (ii)

If $T=Id_{C}$, then $(x_{n})$ is the Tikhonov-Mann iteration [5] and $(y_{n})$
is the modified Halpern iteration [12].

  3. (iii)

If $T=Id_{C}$ and $\alpha_{n}=0$, then $(x_{n})$ is the Mann iteration.

###### Proof.

  1. (i)

By (W5), we have that $x_{n+1}=y_{n}$.

  2. (ii)

Consider the definitions from [6, p.4] and use [6, Proposition 3.2].

  3. (iii)

Apply (W6) to get that $y_{n}=x_{n}$. ∎

Let us recall some useful properties of the alternating Halpern-Mann
iteration. In the sequel, $X$ is a $W$-hyperbolic space.

######  Lemma 2.3.

The following hold for all $n\in{\mathbb{N}}$:

$\displaystyle d(y_{n+1},y_{n})$
$\displaystyle\leq(1-\alpha_{n+1})d(x_{n+1},x_{n})+|\alpha_{n+1}-\alpha_{n}|d(Tx_{n},u),$
(3) $\displaystyle d(x_{n+2},x_{n+1})$ $\displaystyle\leq
d(y_{n+1},y_{n})+|\beta_{n+1}-\beta_{n}|d(Uy_{n},y_{n}).$ (4)

###### Proof.

By the proof of [7, Lemma 3.3]. However, as the notations from [7] are changed
in this paper, we give the proofs below.

$\displaystyle d(y_{n+1},y_{n})$
$\displaystyle=d((1-\alpha_{n+1})Tx_{n+1}+\alpha_{n+1}u,(1-\alpha_{n})Tx_{n}+\alpha_{n}u))$
$\displaystyle\leq
d((1-\alpha_{n+1})Tx_{n+1}+\alpha_{n+1}u,(1-\alpha_{n+1})Tx_{n}+\alpha_{n+1}u)$
$\displaystyle\quad+d((1-\alpha_{n+1})Tx_{n}+\alpha_{n+1}u,(1-\alpha_{n})Tx_{n}+\alpha_{n}u)$
$\displaystyle\leq(1-\alpha_{n+1})d(Tx_{n+1},Tx_{n})+|\alpha_{n+1}-\alpha_{n}|d(Tx_{n},u)$
by (W4) and (W2)
$\displaystyle\leq(1-\alpha_{n+1})d(x_{n+1},x_{n})+|\alpha_{n+1}-\alpha_{n}|d(Tx_{n},u),$
$\displaystyle d(x_{n+2},x_{n+1})$
$\displaystyle=d((1-\beta_{n+1})Uy_{n+1}+\beta_{n+1}y_{n+1},(1-\beta_{n})Uy_{n}+\beta_{n}y_{n})$
$\displaystyle\leq
d((1-\beta_{n+1})Uy_{n+1}+\beta_{n+1}y_{n+1},(1-\beta_{n+1})Uy_{n}+\beta_{n+1}y_{n})$
$\displaystyle\quad+d((1-\beta_{n+1})Uy_{n}+\beta_{n+1}y_{n},(1-\beta_{n})Uy_{n}+\beta_{n}y_{n})$
$\displaystyle\leq(1-\beta_{n+1})d(Uy_{n+1},Uy_{n})+\beta_{n+1}d(y_{n+1},y_{n})$
$\displaystyle\quad+|\beta_{n+1}-\beta_{n}|d(Uy_{n},y_{n})\quad\text{by (W4)
and (W2)}$ $\displaystyle\leq
d(y_{n+1},y_{n})+|\beta_{n+1}-\beta_{n}|d(Uy_{n},y_{n}).\qed$

We assume, furthermore, that $T$ and $U$ have common fixed points and let $p$
be a common fixed point of $T$ and $U$. Define

$M_{p}=\max\\{d(x_{0},p),d(u,p)\\}.$ (5)

######  Lemma 2.4.

For all $n\in{\mathbb{N}}$,

  1. (i)

$d(x_{n},p)\leq M_{p}$ and $d(y_{n},p)\leq M_{p}$.

  2. (ii)

$d(x_{n+1},x_{n})\leq 2M_{p}$ and $d(y_{n+1},y_{n})\leq 2M_{p}$.

  3. (iii)

$d(Tx_{n},u)\leq 2M_{p}$ and $d(Uy_{n},y_{n})\leq 2M_{p}$.

###### Proof.

For (i) see [7, Lemma 3.2]. (ii), (iii) follow easily from (i). ∎

######  Lemma 2.5.

The following hold for all $n\in{\mathbb{N}}$:

$\displaystyle d(y_{n+1},y_{n})$
$\displaystyle\leq(1-\alpha_{n+1})d(x_{n+1},x_{n})+2M_{p}|\alpha_{n+1}-\alpha_{n}|,$
(6) $\displaystyle\\!\\!\\!\\!d(x_{n+2},x_{n+1})$
$\displaystyle\leq(1-\alpha_{n+1})d(x_{n+1},x_{n})+2M_{p}(|\alpha_{n+1}-\alpha_{n}|+|\beta_{n+1}-\beta_{n}|).$
(7)

###### Proof.

Apply (3), (4), and Lemma 2.4.(iii). ∎

###  2.3 Quantitative lemmas

The following lemma due to Xu [24] is well-known, as it is one of the main
tools in different convergence proofs for nonlinear iterations.

######  Lemma 2.6.

Let $(s_{n})_{n\in{\mathbb{N}}}$ be a sequence of nonnegative real numbers
satisfying, for all $n\in{\mathbb{N}}$,

$s_{n+1}\leq(1-a_{n})s_{n}+a_{n}b_{n}+c_{n},$

where $(a_{n})_{n\in{\mathbb{N}}}$ is a sequence in $[0,1]$ such that
$\sum\limits_{n=0}^{\infty}a_{n}$ diverges, $(b_{n})_{n\in{\mathbb{N}}}$ is a
sequence of real numbers with $\limsup\limits_{n\to\infty}b_{n}\leq 0$, and
$(c_{n})_{n\in{\mathbb{N}}}$ is a sequence of nonnegative reals such that
$\sum\limits_{n=0}^{\infty}c_{n}$ converges.

Then $\lim\limits_{n\to\infty}s_{n}=0$.

Quantitative versions of this lemma were given for the first time in [17] for
the particular case $c_{n}=0$ and for the general case in [21, Section 3]. We
refer also to [7, Section 2.3] for an extensive discussion on different
quantitative variants of Xu’s lemma. We shall use in this paper a quantitative
version of another particular case of Lemma 2.6, obtained by taking $b_{n}=0$.

######  Proposition 2.7.

Let $(s_{n}),(c_{n})\subseteq[0,+\infty)$ and $(a_{n})\subseteq[0,1]$ satisfy,
for all $n\in{\mathbb{N}}$,

$s_{n+1}\leq(1-a_{n})s_{n}+c_{n}.$

Assume that $L\in{\mathbb{N}}^{*}$ is an upper bound on $(s_{n})$,
$\sum\limits_{n=0}^{\infty}a_{n}$ diverges with rate of divergence $\theta$,
and $\sum\limits_{n=0}^{\infty}c_{n}$ converges with Cauchy modulus $\chi$.

Then $\lim\limits_{n\to\infty}s_{n}=0$ with rate of convergence $\Sigma$
defined by

$\Sigma(k)=\theta\big{(}\chi(2k+1)+1+\lceil\ln(2L(k+1))\rceil\big{)}+1.$ (8)

###### Proof.

See [7, Lemma 2.9(1)]. ∎

Sabach and Shtern [23, Lemma 3] proved a particularly interesting version of
Xu’s lemma that allowed them, for a clever choice for the sequence $(a_{n})$,
to obtain linear rates of asymptotic regularity for the sequential averaging
method (SAM), a generalization of the Halpern iteration. Recently, Cheval,
Kohlenbach, and the first author [6] applied [23, Lemma 3] to compute linear
rates for the Tikhonov-Mann iteration and the modified Halpern iteration in
$W$-hyperbolic spaces.

In this paper we shall use a version of Sabach and Shtern’s lemma to obtain
linear rates of asymptotic regularity for the alternating Halpern-Mann
iteration, too. We give the proof, for completeness.

######  Lemma 2.8.

Let $L>0$, $J\geq N\geq 2$, and $\gamma\in(0,1]$. Assume that
$a_{n}=\frac{N}{\gamma(n+J)}$ and $c_{n}\leq L$ for all $n\in{\mathbb{N}}$.
Consider a sequence of nonnegative real numbers $(s_{n})$ satisfying the
following: $s_{0}\leq L$ and, for all $n\in{\mathbb{N}}$,

$s_{n+1}\leq(1-\gamma a_{n+1})s_{n}+(a_{n}-a_{n+1})c_{n}.$

Then

$s_{n}\leq\frac{JL}{\gamma(n+J)}\quad\text{for all~{}}n\in{\mathbb{N}}.$

###### Proof.

We show the result by induction on $n$.

$n=0$: We trivially have that $s_{0}\leq\frac{L}{\gamma}$, as
$\gamma\in(0,1]$.

$n\Rightarrow n+1$: We get that

$\displaystyle s_{n+1}$ $\displaystyle\leq(1-\gamma
a_{n+1})s_{n}+(a_{n}-a_{n+1})L$
$\displaystyle\leq\left(1-\frac{N}{n+1+J}\right)\frac{JL}{\gamma(n+J)}+\left(\frac{N}{\gamma(n+J)}-\frac{N}{\gamma(n+1+J)}\right)L$
by the induction hypothesis
$\displaystyle=\frac{(n+1+J-N)JL}{\gamma(n+1+J)(n+J)}+\frac{NL}{\gamma(n+J)(n+1+J)}$
$\displaystyle\leq\frac{(n+1+J-N)JL}{\gamma(n+1+J)(n+J)}+\frac{JL}{\gamma(n+J)(n+1+J)}\quad\text{as~{}}J\geq
N$
$\displaystyle=\frac{(n+J+2-N)JL}{\gamma(n+J)(n+1+J)}\leq\frac{JL}{\gamma(n+1+J)}\quad\text{as~{}}N\geq
2.\qed$

##  3 Main results

The main results of the paper provide effective rates of ($T$\- and
$U$-)asymptotic regularity of the alternating Halpern-Mann iteration.

Consider throughout that $X$ is a $W$-hyperbolic space, $C\subseteq X$ is a
convex subset, and $T,U:C\to C$ are nonexpansive mappings. We assume that $T$
and $U$ have common fixed points, hence the set $Fix(T)\cap Fix(U)$ is
nonempty, where $Fix(T)$ (resp. $Fix(U)$ is the set of fixed points of $T$
(resp. $U$).

The sequences $(x_{n})$, $(y_{n})$ are defined by (2), $p\in Fix(T)\cap
Fix(U)$, $M_{p}$ is given by (5), and $K\in{\mathbb{N}}^{*}$ is such that
$K\geq M_{p}$.

We shall use the following quantitative hypotheses on the parameter sequences
$(\alpha_{n})$, $(\beta_{n})$ from (2):
$(Q1)$ $\lim\limits_{n\to\infty}\alpha_{n}=0$ with rate of convergence
$\sigma_{1}$; $(Q2)$ $\sum\limits_{n=0}^{\infty}\alpha_{n}$ diverges with rate
of divergence $\sigma_{2}$; $(Q3)$
$\sum\limits_{n=0}^{\infty}|\alpha_{n+1}-\alpha_{n}|$ converges with Cauchy
modulus $\sigma_{3}$; $(Q4)$
$\sum\limits_{n=0}^{\infty}|\beta_{n+1}-\beta_{n}|$ converges with Cauchy
modulus $\sigma_{4}$; $(Q5)$ $\Lambda\in{\mathbb{N}}$ satisfies $\Lambda\geq
2$ and $\frac{1}{\Lambda}\leq\beta_{n}\leq 1-\frac{1}{\Lambda}$ for all $n\in
N$.

These hypotheses were used in [7] for the quantitative study of the Halpern-
Mann iteration in CAT(0) spaces.

###  3.1 Asymptotic regularity in $W$-hyperbolic spaces

The first asymptotic regularity results are essentially reformulations of [7,
Pro-position 3.3(i),(ii)] obtained by using $\frac{1}{k+1}$ instead of
$\varepsilon$.

######  Proposition 3.1.

Assume that (Q2), (Q3), and (Q4) hold. Define

$\chi:{\mathbb{N}}\to{\mathbb{N}},\quad\chi(k)=\max\\{\sigma_{3}(4K(k+1)-1),\sigma_{4}(4K(k+1)-1)\\}.$
(9)

The following hold:

  1. (i)

$(x_{n})$ is asymptotically regular with rate $\Gamma_{1}$ defined by

$\Gamma_{1}(k)=\sigma_{2}\left(\chi(2k+1)+2+\lceil\ln(4K(k+1))\rceil\right)+1.$
(10)

  2. (ii)

$(y_{n})$ is asymptotically regular with rate $\Gamma_{2}$ defined by

$\Gamma_{2}(k)=\max\left\\{\Gamma_{1}(2k+1),\sigma_{3}(4K(k+1)-1)+1\right\\}.$
(11)

###### Proof.

  1. (i)

As (7) holds, we can apply Proposition 2.7 with $s_{n}=d(x_{n+1},x_{n})$,
$a_{n}=\alpha_{n+1}$, and
$c_{n}=2K(|\alpha_{n+1}-\alpha_{n}|+|\beta_{n+1}-\beta_{n}|)$. By Lemma
2.4.(ii), $L=2K$ is an upper bound for $(s_{n})$. Furthermore, one can easily
see that $\chi$ defined by (9) is a Cauchy modulus for
$\sum\limits_{n=0}^{\infty}c_{n}$ and that $\theta(n)=\sigma_{2}(n+1)$ is a
rate of divergence for $\sum\limits_{n=0}^{\infty}a_{n}$.

  2. (ii)

By (6), we get that for all $n\in{\mathbb{N}}$,

$\displaystyle d(y_{n+1},y_{n})$ $\displaystyle\leq
d(x_{n+1},x_{n})+2K|\alpha_{n+1}-\alpha_{n}|.$

The fact that $\Gamma_{2}$ is a rate of asymptotic regularity of $(y_{n})$
follows easily from (i) and (Q3).

∎

######  Remark 3.2.

The rates $\Gamma_{1}$ and $\Gamma_{2}$ depend on $X$, $C$, $T$, $U$, $x_{0}$,
$u$ only via $K$, an integer upper bound of $M_{p}$ defined by (5). In
particular, if $C$ is bounded, then one can take $M_{p}$ to be the diameter
$d_{C}$ of $C$ and $K=\left\lceil d_{C}\right\rceil$.

######  Remark 3.3.

Without loss of generality we can assume that $\sigma_{3}$ is increasing (by
taking instead of $\sigma_{3}$ the increasing mapping
$\sigma_{3}^{M}(k)=\max\\{\sigma_{3}(i)\mid i\leq k\\}$). In this case,

$\Gamma_{2}(k)=\Gamma_{1}(2k+1).$ (12)

###### Proof.

For all $k\in{\mathbb{N}}$, we have that $\sigma_{2}(k+1)\geq k$, as
$\alpha_{k}\leq 1$. It follows that

$\displaystyle\Gamma_{1}(2k+1)$
$\displaystyle>\chi(4k+3)+2\geq\sigma_{3}(16K(k+1)-1)+2$
$\displaystyle>\sigma_{3}(4K(k+1)-1)+1.\qed$

By Remark 2.2(ii), for $T=id_{C}$, $\Gamma_{1}$ (resp. $\Gamma_{2}$) is a rate
of asymptotic regularity of the Tikhonov-Mann (resp. modified Halpern)
iteration. One can easily see that $\Gamma_{1}$ is slightly better than the
rate obtained in [5, Theorem 4.1(i)]. Furthermore, in the case that
$\sigma_{3}$ is increasing, $\Gamma_{2}$ given by (12) has a similar form with
the rate computed in [6, Proposition 4.4(i)].

####  3.1.1 Linear rates

Let us consider the following parameter sequences:

$\alpha_{n}=\frac{2}{n+2}$ and $\beta_{n}=\beta\in(0,1)$.

As pointed out in [7], one can apply Proposition 3.1 to get exponential rates
of asymptotic regularity. The next result shows that we can obtain, as an
application of Lemma 2.8, linear rates of asymptotic regularity.

######  Proposition 3.4.

For all $n\in{\mathbb{N}}$,

$d(x_{n},x_{n+1})\leq\frac{4K}{n+2}\quad\text{and}\quad
d(y_{n},y_{n+1})\leq\frac{4K}{n+3}.$ (13)

Thus, $(x_{n})$ is asymptotically regular with rate $\Sigma_{1}(k)=4K(k+1)-2$
and $(y_{n})$ is asymptotically regular with rate $\Sigma_{2}(k)=4K(k+1)-3$.

###### Proof.

Applying (7), we get that for all $n\in{\mathbb{N}}$,

$\displaystyle d(x_{n+2},x_{n+1})$
$\displaystyle\leq\left(1-\frac{2}{n+3}\right)d(x_{n},x_{n+1})+\left(\frac{2}{n+2}-\frac{2}{n+3}\right)2K.$
(14)

One can easily see that we can apply Lemma 2.8 with $s_{n}=d(x_{n},x_{n+1})$,
$L=2K$, $N=J=2$, $\gamma=1$, $a_{n}=\alpha_{n}=\frac{2}{n+2}$, and $c_{n}=2K$
to get that for all $n\in{\mathbb{N}}$,

$d(x_{n},x_{n+1})\leq\frac{4K}{n+2}.$

Furthermore, by (6), we have that for all $n\in{\mathbb{N}}$,

$d(y_{n},y_{n+1})\leq\frac{4K}{n+3}.$

The conclusion follows immediately. ∎

###  3.2 $T$\- and $U$-asymptotic regularity in $UCW$-hyperbolic spaces

Rates of $T$\- and $U$-asymptotic regularity for $(x_{n})$, $(y_{n})$ were
also computed in [7] in the setting of CAT(0) spaces. We now show that these
results can be generalized to $UCW$-hyperbolic spaces.

######  Proposition 3.5.

Let $(X,\eta)$ be a $UCW$-hyperbolic space. Assume that (Q1) and (Q5) hold and
that $(x_{n})$ is asymptotically regular with rate $\Delta$.

The following are satisfied:

  1. (i)

$(y_{n})$ is $U$-asymptotically regular with rate $\Gamma_{3}$ defined by

$\Gamma_{3}(k)=\max\\{\Delta(2P(k+1)-1),\sigma_{1}(2PK(k+1)-1)\\},$

where $\displaystyle
P=\left\lceil\frac{\Lambda^{2}}{\eta\left(K,\frac{1}{K(k+1)}\right)}\right\rceil$.

  2. (ii)

$\lim\limits_{n\to\infty}d(x_{n},y_{n})=0$ with rate of convergence

$\Omega(k)=\max\\{\Delta(2k+1),\Gamma_{3}(2k+1)\\}.$ (15)

  3. (iii)

$(y_{n})$ is $T$-asymptotically regular with rate

$\Gamma_{4}(k)=\max\\{\Omega(2k+1),\sigma_{1}(4K(k+1)-1)\\}.$ (16)

  4. (iv)

$(x_{n})$ is $U$-asymptotically regular with rate

$\Gamma_{5}(k)=\max\\{\Omega(4k+3),\Gamma_{3}(2k+1)\\}.$ (17)

  5. (v)

$(x_{n})$ is $T$-asymptotically regular with rate

$\Gamma_{6}(k)=\max\\{\Omega(4k+3),\Gamma_{4}(2k+1)\\}.$ (18)

###### Proof.

  1. (i)

Let $k\in{\mathbb{N}}$ and $n\geq\Gamma_{3}(k)$. Assume that
$d(Uy_{n},y_{n})>\frac{1}{k+1}$. Since $d(y_{n},p)\leq K$, by Lemma 2.4(i),
and $d(Uy_{n},y_{n})\leq d(Uy_{n},p)+d(y_{n},p)\leq 2d(y_{n},p)$, we get that

$\frac{1}{2(k+1)}<d(y_{n},p)\leq K.$ (19)

Furthermore, $d(Uy_{n},p)\leq d(y_{n},p)\leq K$,
$d(Uy_{n},y_{n})>\frac{1}{K(k+1)}d(y_{n},p)$, and $\frac{1}{K(k+1)}<2$. It
follows that we can apply Lemma 2.1 with $x=Uy_{n}$, $y=y_{n}$, $a=p$,
$r=d(y_{n},p)$, $\varepsilon=\frac{1}{K(k+1)}$, $\lambda=\beta_{n}$, and $s=K$
to conclude that

$\displaystyle d(x_{n+1},p)$
$\displaystyle=d((1-\beta_{n})Uy_{n}+\beta_{n}y_{n},p)$
$\displaystyle\leq\left(1-2\beta_{n}(1-\beta_{n})\eta\left(K,\frac{1}{K(k+1)}\right)\right)d(y_{n},p)$
$\displaystyle=d(y_{n},p)-2d(y_{n},p)\beta_{n}(1-\beta_{n})\eta\left(K,\frac{1}{K(k+1)}\right)$
$\displaystyle\leq
d(y_{n},p)-2d(y_{n},p)\frac{1}{\Lambda^{2}}\eta\left(K,\frac{1}{K(k+1)}\right)$
$\displaystyle\quad\text{as, ~{}by
(Q5),~{}}\beta_{n},1-\beta_{n}\geq\frac{1}{\Lambda}$
$\displaystyle<d(y_{n},p)-\frac{1}{(k+1)\Lambda^{2}}\eta\left(K,\frac{1}{K(k+1)}\right)\quad\text{by
\eqref{2dynp}}.$

Since, by (W1), $d(y_{n},p)\leq(1-\alpha_{n})d(Tx_{n},p)+\alpha_{n}d(u,p)\leq
d(x_{n},p)+\alpha_{n}K$, we get that

$\displaystyle d(x_{n+1},p)$
$\displaystyle<d(x_{n},p)+\alpha_{n}K-\frac{1}{(k+1)\Lambda^{2}}\eta\left(K,\frac{1}{K(k+1)}\right).$

It follows that

$\displaystyle\frac{1}{P(k+1)}$
$\displaystyle\leq\frac{1}{(k+1)\Lambda^{2}}\eta\left(K,\frac{1}{K(k+1)}\right)$
$\displaystyle<d(x_{n},p)-d(x_{n+1},p)+\alpha_{n}K\leq
d(x_{n+1},x_{n})+\alpha_{n}K$
$\displaystyle\leq\frac{1}{P(k+1)},\text{~{}as~{}}n\geq\Gamma_{3}(k).$

We have obtained a contradiction.

  2. (ii)-(v)

are obtained easily from the following inequalities

$\displaystyle d(x_{n},y_{n})$ $\displaystyle\leq
d(x_{n+1},x_{n})+d(x_{n+1},y_{n})$
$\displaystyle\stackrel{{\scriptstyle(W7)}}{{=}}d(x_{n+1},x_{n})+(1-\beta_{n})d(Uy_{n},y_{n})$
$\displaystyle\leq d(x_{n+1},x_{n})+d(Uy_{n},y_{n}),$ $\displaystyle
d(Ty_{n},y_{n})$ $\displaystyle\leq
d(Ty_{n},Tx_{n})+d(Tx_{n},y_{n})\stackrel{{\scriptstyle(W7)}}{{=}}d(Tx_{n},Ty_{n})+\alpha_{n}d(Tx_{n},u)$
$\displaystyle\leq d(x_{n},y_{n})+2K\alpha_{n},$ $\displaystyle
d(Ux_{n},x_{n})$ $\displaystyle\leq
d(Ux_{n},Uy_{n})+d(Uy_{n},y_{n})+d(y_{n},x_{n})$ $\displaystyle\leq
2d(x_{n},y_{n})+d(Uy_{n},y_{n}),$ $\displaystyle d(Tx_{n},x_{n})$
$\displaystyle\leq d(Tx_{n},Ty_{n})+d(Ty_{n},y_{n})+d(y_{n},x_{n})$
$\displaystyle\leq 2d(x_{n},y_{n})+d(Ty_{n},y_{n}).\qed$

######  Corollary 3.6.

Assume that $(X,\eta)$ is a $UCW$-hyperbolic space and (Q1)-(Q6) hold. Then
$(x_{n})$ and $(y_{n})$ are $U$\- and $T$-asymptotically regular with rates
obtained from the ones in Proposition 3.5 by replacing $\Delta$ with
$\Gamma_{1}$.

###### Proof.

By Proposition 3.1(i), under the hypotheses (Q2), (Q3), (Q4), $(x_{n})$ is
asymptotically regular with rate $\Gamma_{1}$. ∎

The following observation is inspired by [19, Remark 15]; see also [13,
Theorem 3.4] for a similar remark in the context of uniformly convex normed
spaces.

######  Remark 3.7.

Assume that

(*) $\eta(r,\varepsilon)=\varepsilon\cdot\tilde{\eta}(r,\varepsilon)$ for some
$\tilde{\eta}$ that increases with $\varepsilon$ (for a fixed $r$).

Then Proposition 3.5(i) holds with

$\widetilde{\Gamma_{3}}(k)=\max\\{\Delta(2\tilde{P}(k+1)-1),\sigma_{1}(2\tilde{P}K(k+1)-1)\\}.$

where
$\tilde{P}=\left\lceil\frac{\Lambda^{2}}{\tilde{\eta}\left(K,\frac{1}{K(k+1)}\right)}\right\rceil$.

###### Proof.

Let $k\in{\mathbb{N}}$ and $n\geq\widetilde{\Gamma_{3}}(k)$. Assume that
$d(Uy_{n},y_{n})>\frac{1}{k+1}$. Follow the proof of Proposition 3.5.(i), but
replace $\varepsilon=\frac{1}{K(k+1)}$ with
$\varepsilon=\frac{1}{d(y_{n},p)(k+1)}$. Then we get that

$\displaystyle d(x_{n+1},p)$ $\displaystyle\leq
d(y_{n},p)-\frac{2}{(k+1)\Lambda^{2}}\tilde{\eta}\left(K,\frac{1}{d(y_{n},p)(k+1)}\right)$
$\displaystyle<d(y_{n},p)-\frac{1}{(k+1)\Lambda^{2}}\tilde{\eta}\left(K,\frac{1}{d(y_{n},p)(k+1)}\right).$

As $d(y_{n},p)\leq K$ and $\tilde{\eta}$ is increasing with $\varepsilon$, we
have that
$\tilde{\eta}\left(K,\frac{1}{d(y_{n},p)(k+1)}\right)\geq\tilde{\eta}\left(K,\frac{1}{K(k+1)}\right)$.
It follows that

$\displaystyle
d(x_{n+1},p)<d(y_{n},p)-\frac{1}{(k+1)\Lambda^{2}}\tilde{\eta}\left(K,\frac{1}{K(k+1)}\right).$

Continue as in the proof of Proposition 3.5(i) with $\tilde{P},\tilde{\eta}$
instead of $P,\eta$. ∎

####  3.2.1 Quadratic rates in CAT(0) spaces

For the remainder of this section, consider $X$ to be a CAT(0) space. As
CAT(0) spaces are $UCW$-hyperbolic spaces with modulus
$\eta(r,\varepsilon)=\frac{\varepsilon^{2}}{8}$ that obviously satisfies (*)
from Remark 3.7 with $\tilde{\eta}(r,\varepsilon)=\frac{\varepsilon}{8}$, we
get the following.

######  Proposition 3.8.

Assume that (Q1) and (Q5) hold and that $(x_{n})$ is asymptotically regular
with rate $\Delta$.

Then $(y_{n})$ is $U$-asymptotically regular with rate $\Gamma_{0}$ defined by

$\Gamma_{0}(k)=\max\\{\Delta(2P_{0}(k+1)-1),\sigma_{1}(2P_{0}K(k+1)-1)\\},$

where $P_{0}=8K\Lambda^{2}(k+1)$.

Furthermore, Proposition 3.5 holds with $\Gamma_{3}$ replaced by $\Gamma_{0}$.
As in Corollary 3.6, if, moreover, (Q2)-(Q4) hold, then one can take
$\Delta=\Gamma_{1}$, with $\Gamma_{1}$ defined by (10). One can easily verify
that our results, when particularized to CAT(0) spaces, actually recover the
rates of ($T$\- and $U$-)asymptotic regularity from [7].

For the particular parameter sequences considered in Subsubsection 3.1.1, we
get quadratic rates of $T$\- and $U$-asymptotic regularity.

######  Proposition 3.9.

Let $\alpha_{n}=\frac{2}{n+2}$ and $\beta_{n}=\beta\in(0,1)$. Define

$\Lambda=\left\lceil\max\left\\{\frac{1}{\beta},\frac{1}{1-\beta}\right\\}\right\rceil.$
(20)

The following hold:

  1. (i)

$\Sigma_{3}(k)\\!=\\!2^{6}K^{2}\Lambda^{2}(k+1)^{2}\\!-\\!2$ is a rate of
$U$-asymptotic regularity of $(y_{n})$.

  2. (ii)

$\lim\limits_{n\to\infty}d(x_{n},y_{n})=0$ with rate of convergence
$\Theta(k)=2^{8}K^{2}\Lambda^{2}(k+1)^{2}\\!-\\!2$.

  3. (iii)

$\Sigma_{4}(k)=2^{10}K^{2}\Lambda^{2}(k+1)^{2}\\!-\\!2$ is a rate of
$T$-asymptotic regularity of $(y_{n})$.

  4. (iv)

$\Sigma_{5}(k)=2^{12}K^{2}\Lambda^{2}(k+1)^{2}\\!-\\!2$ is a rate of $T$\- and
$U$-asymptotic regularity of $(x_{n})$.

###### Proof.

Obviously, $\sigma_{1}(k)=2k$ is a rate of convergence for
$\left(\frac{2}{n+2}\right)$. By Proposition 3.4, $\Sigma_{1}(k)=4K(k+1)-2$ is
a rate of asymptotic regularity of $(x_{n})$. Furthermore, $(Q5)$ holds with
$\Lambda$ defined by (20). To obtain (i) apply Proposition 3.8 with
$\Delta=\Sigma_{1}$. For (ii)-(iv) we use Proposition 3.5(ii)-(v) with
$\Delta=\Sigma_{1}$ and $\Gamma_{3}=\Sigma_{3}$. ∎

## Acknowledgements

The first author thanks Adriana Nicolae for useful discussions on the subject
of the paper. The second author was supported by the German Science Foundation
(DFG Project KO 1737/6-2).

## References

  * [1] S. Alexander, V. Kapovitch, and A. Petrunin.  An Invitation to Alexandrov Geometry. CAT(0) Spaces.  Springer, 2019.
  * [2] D. Ariza-Ruiz, L. Leuştean, and G. López-Acedo.  Firmly nonexpansive mappings in classes of geodesic spaces.  Trans. Amer. Math. Soc., 366:4299–4322, 2014.
  * [3] R.I. Boţ, E.R. Csetnek, and D. Meier.  Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces.  Optim. Methods Softw., 34:489–514, 2019.
  * [4] M. Bridson and A. Haefliger.  Metric Spaces of Non-Positive Curvature.  Springer, 1999.
  * [5] H. Cheval and L. Leuştean.  Quadratic rates of asymptotic regularity for the Tikhonov-Mann iteration.  Optim. Methods Softw., 37:2225-2240 (2022).
  * [6] H. Cheval, U. Kohlenbach, and L. Leuştean.  On Modified Halpern and Tikhonov-Mann Iterations. arXiv:2203.11003, 2023.
  * [7] B. Dinis and P. Pinto.  Strong convergence for the alternating Halpern-Mann iteration in CAT(0) spaces. arXiv:2112.14525, 2021.
  * [8] F. Ferreira, L. Leuştean, and P. Pinto.  On the removal of weak compactness arguments in proof mining.  Adv. Math., 354:106728, 2019.
  * [9] K. Goebel and S. Reich.  Uniform convexity, hyperbolic geometry, and nonexpansive mappings.  Marcel Dekker Inc., 1984.
  * [10] C.W. Groetsch.  A note on segmenting Mann iterates.  J. Math. Anal. Appl., 40:369–372, 1972.
  * [11] B. Halpern.  Fixed points of nonexpanding maps.  Bull. Amer. Math. Soc., 73:957–961, 1967.
  * [12] T.H. Kim and H.K. Xu.  Strong convergence of modified Mann iterations.  Nonlinear Anal., 61:51–60, 2005.
  * [13] U. Kohlenbach.  Uniform asymptotic regularity for Mann iterates.  J. Math. Anal. Appl., 279:531-544, 2003.
  * [14] U. Kohlenbach.  Some logical metatheorems with applications in functional analysis.  Trans. Amer. Math. Soc., 357:89–128, 2005.
  * [15] U. Kohlenbach.  Applied Proof Theory: Proof Interpretations and their Use in Mathematics.  Springer, 2008.
  * [16] U. Kohlenbach and L. Leuştean.  Asymptotically nonexpansive mappings in uniformly convex hyperbolic spaces.  J. Eur. Math. Soc., 12:71–92, 2010.
  * [17] U. Kohlenbach, L. Leuştean.  Effective metastability of Halpern iterates in CAT(0) spaces.  Adv. Math., 231:2526–2556, 2012.
  * [18] M.A. Krasnoselskii.  Two remarks on the method of successive approximations.  Uspehi Mat. Nauk (N.S.), 10:123–127, 1955.
  * [19] L. Leuştean.  A quadratic rate of asymptotic regularity for CAT(0)-spaces.  J. Math. Anal. Appl., 325:386–399, 2007.
  * [20] L. Leuştean.  Nonexpansive iterations in uniformly convex $W$-hyperbolic spaces.  In Nonlinear Analysis and Optimization I : Nonlinear Analysis, A. Leizarowitz, B.S. Mordukhovich, I. Shafrir, and A. Zaslavski, eds., American Mathematical Society, pp. 193–209, 2010.
  * [21] L. Leuştean and P. Pinto.  Quantitative results on a Halpern-type proximal point algorithm.  Comput. Optim. Appl. 79:101-125, 2021.
  * [22] W.R. Mann.  Mean value methods in iteration.  Proc. Amer. Math. Soc., 4:506–510, 1953.
  * [23] S. Sabach, S. Shtern.  A first order method for solving convex bilevel optimization problems.  SIAM J. Optim., 27:640-660, 2017.
  * [24] H.-K. Xu.  Iterative algorithms for nonlinear operators.  J. London Math. Soc., 66:240-256, 2002.
  * [25] Y. Yao, H. Zhou, and Y.-C. Liou.  Strong convergence of a modified Krasnoselski-Mann iterative algorithm for non-expansive mappings.  J. Appl. Math. Comput., 29:383–389, 2009.