# Extragradient-Type Methods with $\mathcal{O}\left(1/k\right)$ Last-Iterate
Convergence Rates for Co-Hypomonotone Inclusions

Quoc Tran-Dinh

Department of Statistics and Operations Research

The University of North Carolina at Chapel Hill
318 Hanes Hall, UNC-Chapel Hill, NC 27599-3260.

Email<EMAIL_ADDRESS>
(Version 1: 2023/2/8. This is Version 2: 2023/10/14)

###### Abstract

We develop two “Nesterov’s accelerated” variants of the well-known
extragradient method to approximate a solution of a co-hypomonotone inclusion
constituted by the sum of two operators, where one is Lipschitz continuous and
the other is possibly multivalued. The first scheme can be viewed as an
accelerated variant of Tseng’s forward-backward-forward splitting (FBFS)
method, while the second one is a Nesterov’s accelerated variant of the “past”
FBFS scheme, which requires only one evaluation of the Lipschitz operator and
one resolvent of the multivalued mapping. Under appropriate conditions on the
parameters, we theoretically prove that both algorithms achieve
$\mathcal{O}\left(1/k\right)$ last-iterate convergence rates on the residual
norm, where $k$ is the iteration counter. Our results can be viewed as
alternatives of a recent class of Halpern-type methods for root-finding
problems. For comparison, we also provide a new convergence analysis of the
two recent extra-anchored gradient-type methods for solving co-hypomonotone
inclusions.

Keywords: Accelerated extragradient method; Nesterov’s acceleration; co-
hypomonotone inclusion; Halpern’s fixed-point iteration; last-iterate
convergence rate

Mathematics Subject Classification (2010): 90C25 · 90-08

##  1 Introduction

The goal of this paper is to extend two recent “Halpern’s accelerated”
extragradient-type methods for equation root-finding problems in [40, 75, 79]
to inclusion root-finding settings under a so-called “co-hypomonotone”
assumption [6]. Unlike recent works along this line [13, 14], we exploit a
different view from [73], which establishes the relation between Halpern’s
fixed-point iteration [33] with “optimal” convergence rates [24, 40, 42, 79]
and Nesterov’s accelerated techniques widely extended to root-finding
problems, e.g., in [2, 17, 36, 49, 57, 58]. To set our stage, we consider the
following operator inclusion (also called a generalized equation [67]):

$\textrm{Find $x^{\star}\in\mathbb{R}^{p}$ such that:}\quad 0\in
Fx^{\star}+Tx^{\star},$ (chMI)

where $F$ is a single-valued operator from $\mathbb{R}^{p}\to\mathbb{R}^{p}$,
and $T:\mathbb{R}^{p}\rightrightarrows 2^{\mathbb{R}^{p}}$ is a possibly
multivalued operator, where $2^{\mathbb{R}^{p}}$ is the set of all subsets of
$\mathbb{R}^{p}$. Up to this point, we have not made any assumption on (chMI).
In particular, if $T=0$, then (chMI) reduces to the following equation root-
finding problem:

$\textrm{Find $x^{\star}\in\mathbb{R}^{p}$ such that:}\quad Fx^{\star}=0,$
(chME)

of a [non]linear operator $F$. Alternatively, if
$T:=\mathcal{N}_{\mathcal{C}}$, the normal cone of a nonempty, closed, and
convex set $\mathcal{C}$, then (chMI) reduces to a variational inequality
problem (VIP), widely studied in the literature, see for examples [27, 34, 37,
54]. For our convenience, we denote $G:=F+T$ and assume that the solution set
$\mathrm{zer}(G):=G^{-1}(0)=\\{x^{\star}\in\mathbb{R}^{p}:0\in
Gx^{\star}=Fx^{\star}+Tx^{\star}\\}$ of (chMI) is nonempty.

The inclusion (chME) though looks simple, it covers many fundamental problems
in different fields by appropriately reformulating them into (chMI). These
problems include optimization (both unconstrained and constrained settings),
minimax optimization, two-person game, variational inequality and its special
cases, and more generally, fixed-point problems, see [5, 12, 27, 64, 67, 68,
69]. Alternatively, (chMI) is also ubiquitous in large-scale modern machine
learning and data science applications, especially in stochastic settings,
see, e.g., [11, 39, 72]. However, most existing works often focus on special
cases of (chME) such as optimization, convex-concave minimax, and supervised
learning models as can be found in [15, 27, 37, 38, 50, 51, 53, 55, 59, 65,
71, 77]. A recent trend in adversarial machine learning, reinforcement
learning, online learning, and distributionally robust optimization has
motivated the development of efficient and reliable methods for solving
(chMI), especially in non-monotone cases [1, 4, 7, 29, 35, 41, 43, 47, 66].

Solution approaches for solving (chMI) often rely on a fundamental assumption:
monotonicity of $F$ and $T$, or of $G$. Several methods generalize existing
optimization algorithms such as gradient and proximal-point schemes, and
exploit the splitting structure of (chMI) to use individual operators defined
on $F$ and $T$, respectively. Classical methods include gradient (also known
as forward or fixed-point iteration), extragradient, past-extragradient,
optimistic gradient, proximal-point, forward-backward splitting, forward-
backward-forward splitting, Douglas-Rachford splitting, forward-reflected-
backward splitting, golden ratio, projective splitting methods, and their
variants, see for example [5, 16, 20, 23, 45, 27, 50, 52, 65, 77] for more
details. However, extensions to non-monotone settings remain limited. Under
the non-monotonicity, (chMI) is expected to cover a broader class of problems
arising from modern applications in, e.g., adversarial machine learning,
reinforcement learning, [distributionally] robust optimization, and game
theory. Recent works on nonmonotone (chMI) can be found in [8, 13, 25, 40, 46,
63, 62].

Our goal in this paper is to develop new schemes for solving (chMI) under the
co-hypomonotone structure of $F+T$ (see its definition in Section 2).
Therefore, let us first review some relevant works to our methods in this
paper. Classical splitting methods mentioned above for solving (chMI) or its
special cases heavily rely on the monotonicity of $F+T$ (or each of them) and
the Lipschitz continuity or the co-coerciveness of $F$, see, e.g., [5, 20, 23,
45, 27, 50, 65, 77]. For the nonmonotone case, [62] studied local convergence
of proximal-point methods, while [19] utilized the hypomonotone and co-
hypomonotone structures. Some other works considered minimax problems, special
cases of (chMI), by imposing weak monotonicity or other appropriate regularity
conditions (e.g., two-sided Polyak-Łojasiewicz condition, or interaction
dominance) as in [32, 44, 78]. Recently, convergence rates of extragradient
methods for a class of nonmonotone (i.e. weak Minty) variational inequalities
were studied in [25], and then in [63] for (chMI). These methods only achieve
$\mathcal{O}\big{(}1/\sqrt{k}\big{)}$ \- “best-iterate” convergence rates,
where $k$ is the iteration counter. The work [46] proved
$\mathcal{O}\big{(}1/\sqrt{k}\big{)}$ convergence rates on the last iterate
for these methods to solve the special case (chME) of (chMI) under the co-
hypomonotonicity of $F$. A very recent survey on extragradient-type methods
can be found in [74]. However, hitherto, establishing the last-iterate
convergence rates of classical extragradient-type methods for solving (chMI)
under the nonmonotonicity (e.g., co-hypomonotonicity) remains largely open.

Alternative to classical or “non-accelerated” algorithms for solving (chMI),
there is a line of research that develops accelerated methods to solve (chMI)
under both monotone and co-hypomonotone structures. Early attempts relied on
dual averaging techniques such as [21, 56, 59], which require the monotonicity
or special assumptions. Attouch et al [3] proposed accelerated proximal-point
methods to solve (chMI) under the maximal monotonicity of $G$. Several
following up works have been focussing on Nesterov’s acceleration-type methods
(i.e. exploiting momentum and possibly correction terms) for solving (chMI)
under monotone assumptions such as [2, 9, 10, 36, 49, 48]. Each of these
methods can be viewed as a discretization of an appropriate dynamical system
(i.e. a given ordinary differential equation). Recently, accelerated methods
based on Halpern’s fixed-point iteration [33] have attracted a great
attention. This method was originally developed to approximate a fixed-point
of a non-expansive operator, but can be used to solve monotone inclusions of
the form (chMI). Perhaps, Sabach and Shtern [70] and then Lieder [42] were the
first who proved $\mathcal{O}\left(1/k\right)$ convergence rates for Halpern’s
fixed-point iteration by appropriately choosing its parameters. This method
was further exploited to solve variational inequalities in [24]. Yoon and Ryu
extended Halpern’s fixed-point iteration idea to extragradient methods in [79]
to solve (chME) that remove the co-coerciveness assumption on $F$. Lee and Kim
[40] further advanced [79] to develop similar algorithms for solving (chME)
but under the co-hypomonotonicity (a type of non-monotonicity), while do not
scarify the $\mathcal{O}\left(1/k\right)$-convergence rates. The work [75]
exploited the idea of [79] and developed a Halpern-type variant for the past-
extragradient method in [65], which requires only one operator evaluation per
iteration. Recently, [13, 14] extended [79] and [75] to variational
inequalities and (chMI) under either the monotonicity or the co-
hypomonotonicity assumption. Both Halpern’s fixed-point iteration and
Nesterov’s accelerated schemes for root-finding problems are actually related
to each other. Their relation has recently been studied in [73] for several
schemes. Other related works along this line can be found, e.g., in [8, 9, 10,
28, 30, 31, 44, 76].

Contribution. In this paper, we propose new “Nesterov’s accelerated variants”
of the forward-backward-forward splitting (FBFS) method [77] and its past FBFS
variant. The form of our methods is as simple as the one in [73] for equation
root-finding problems. Our first algorithm can be viewed as an accelerated
FBFS method, but abbreviated by AEG as it is rooted from the extragradient
method in [38]. This algorithm achieves a $\mathcal{O}\left(1/k\right)$ last-
iterate convergence rate on the residual norm of (chMI). However, it requires
two evaluations of $F$ and one evaluation of $J_{\eta T}$ (the resolvent of
$\eta T$ for some $\eta>0$) as often seen in Tseng’s FBFS method [77]. Our
second variant is an accelerated past FBFS scheme (abbreviated by APEG), which
adopts the idea from Popov’s method [65] or optimistic gradient-type
algorithms [22] but using a different past operator value. This algorithm has
almost the same per-iteration complexity as of the forward-reflected-backward
splitting method [52] or the reflected forward-backward splitting scheme [16,
50], but achieves a $\mathcal{O}\left(1/k\right)$ last-iterate convergence
rate on the residual norm of (chMI) as in our first algorithm – AEG. However,
as a compensation, APEG has a smaller stepsize and stricter condition, leading
to a worse convergence upper bound than AEG. Our rates are the same order as
the ones in recent works [13, 14], but we take a different approach and
develop different algorithms with new convergence analysis. We believe that
this paper is the first showing a possibility to develop Nesterov’s
accelerated-type methods for nonmonotone (in particular, nonconvex
optimization) problems by using different convergence criteria. In the second
part of this paper, we conduct a new convergence analysis for the two extra-
anchored gradient-type methods for solving (chMI) proposed in [13, 14]. Our
analysis can be viewed as a natural extension of the techniques for (chME) in
[40, 75, 79] and is different from [13, 14]. Moreover, our second scheme is
still different from the one in [14].

Paper organization. The rest of this paper is organized as follows. In Section
2 we briefly review some related concepts to (chMI) such as Lipschitz
continuity, monotonicity, and co-hypomonotonicity, and recall some preliminary
results used in this paper. Section 3 develops a Nesterov’s accelerated
extragradient method to solve (chMI) and analyzes its convergence rate.
Section 4 derives a Nesterov’s accelerated variant of the past FBFS method to
solve (chMI) and analyzes its convergence rate. For completeness and
comparison, in Section 5, we present an alternative convergence analysis for
the Halpern-type extragradient methods (also called extra-anchored gradient-
type methods) in [13, 14]. However, our second variant is significantly
different from the one in [14] due to the choice of a past value.

##  2 Background and Preliminary Results

We first review some background on monotone operators and related concepts.
Then, we recall Tseng’s classical FBFS method and its past FBFS variant as the
baselines of our development.

###  2.1 Monotone-type operators and related concepts

In this paper, we work with a finite dimensional space $\mathbb{R}^{p}$
equipped with the standard inner product $\langle\cdot,\cdot\rangle$ and
Euclidean norm $\|\cdot\|$. For a single-valued or multivalued mapping
$G:\mathbb{R}^{p}\rightrightarrows 2^{\mathbb{R}^{p}}$,
$\mathrm{dom}(G)=\left\\{x\in\mathbb{R}^{p}:Gx\not=\emptyset\right\\}$ denotes
its domain, $\mathrm{ran}(G):=\left\\{u\in\mathbb{R}^{p}:u\in
Gx,~{}x\in\mathrm{dom}(G)\right\\}$ denotes its range,
$\mathrm{gra}(G)=\left\\{(x,y)\in\mathbb{R}^{p}\times\mathbb{R}^{p}:y\in
Gx\right\\}$ denotes its graph, where $2^{\mathbb{R}^{p}}$ is the set of all
subsets of $\mathbb{R}^{p}$. The inverse of $G$ is defined by
$G^{-1}y:=\\{x\in\mathbb{R}^{p}:y\in Gx\\}$.

(a) Monotonicity. For a multivalued mapping $G:\mathbb{R}^{p}\rightrightarrows
2^{\mathbb{R}^{p}}$, we say that $G$ is $\mu$-monotone for some
$\mu\in\mathbb{R}$ if $\langle u-v,x-y\rangle\geq\mu\|x-y\|^{2}$ for all
$(x,u),(y,v)\in\mathrm{gra}(G)$. If $\mu=0$, then $G$ is called monotone, i.e.
$\langle u-v,x-y\rangle\geq 0$ for all $(x,u),(y,v)\in\mathrm{gra}(G)$. If
$\mu>0$, then $G$ is called strongly monotone with a strong monotonicity
parameter $\mu$. If $\mu<0$, then we say that $G$ is $|\mu|$-hypomonotone or
$|\mu|$-weakly monotone. If $G$ is single-valued, then the above condition
reduces to $\langle Gx-Gy,x-y\rangle\geq\mu\|x-y\|^{2}$ for all
$x,y\in\mathrm{dom}(G)$, which defines the corresponding concepts for the
single-valued mapping $G$. We say that $G$ is $\mu$-maximally monotone if
$\mathrm{gra}(G)$ is not properly contained in the graph of any other
$\mu$-monotone operator.

(b) Lipschitz continuity. A single-valued operator $G$ is called $L$-Lipschitz
continuous if $\|Gx-Gy\|\leq L\|x-y\|$ for all $x,y\in\mathrm{dom}(G)$, where
$L\geq 0$ is a Lipschitz constant. If $L=1$, then we say that $G$ is
nonexpansive, while if $L\in[0,1)$, then we say that $G$ is $L$-contractive,
and $L$ is its contraction factor. If $G$ is $L$-Lipschitz continuous, then by
the Cauchy-Schwarz inequality, we have $\langle Gx-Gy,x-y\rangle\geq-\|Gx-
Gy\|\|x-y\|\geq-L\|x-y\|^{2}$, showing that $G$ is also $L$-hypomonotone.

(c) Co-hypomonotonicity and co-coerciveness. A mapping $G$ is said to be
$\rho$-co-hypomonotone for $\rho>0$ if $\langle
u-v,x-y\rangle\geq-\rho\|u-v\|^{2}$ for all $(x,u),(y,v)\in\mathrm{gra}(G)$.
The co-hypomonotonicity is also referred to as $-\rho$-co-monotonicity with a
parameter $\rho$, see, e.g., [6, 19]. Clearly, a co-hypomonotone operator is
not necessarily monotone. If $\rho=0$, then $G$ is just monotone, while if
$\rho<0$, then $G$ is $\beta$-co-coercive with the parameter $\beta:=-\rho$.
If $\beta=1$, then we say that $G$ is firmly nonexpansive. If $G$ is
$\beta$-co-coercive, then it is also monotone and $\frac{1}{\beta}$-Lipschitz
continuous (by the Cauchy-Schwarz inequality), but the reversed statement is
not true in general.

The co-hypomonotonicity concept was extended to a so-called semimonotonicity
in [26, 60]. It is stronger than the weak Minty solution condition, e.g., in
[25], which only requires to hold at a given solution $x^{\star}$, i.e.
$\langle u,x-x^{\star}\rangle\geq-\rho\|u\|^{2}$ for all
$(x,u)\in\mathrm{gra}(G)$. It is obvious that $G$ is $\rho$-co-hypomonotone if
and only if $G^{-1}$ is $\rho$-hypomonotone, i.e. $\langle
u-v,x-y\rangle\geq-\rho\|u-v\|^{2}$ for all
$(u,x),(v,y)\in\mathrm{gra}(G^{-1})$.

The co-hymonotonicity is also related to a so-called “interaction dominance
condition” studied in [32]. Proposition 4.6 in [26] states that if a minimax
objective function satisfies an interaction dominance condition, then its
gradient is co-hypomonotone. This structure presents in various minimax models
[32].

Another related concept is the strong metric subregularity (see [18, 67])
widely studied in variational analysis, though it is often defined locally.
More specifically, a mapping $G$ is said to be strongly metrically subregular
at $x$ for $u$ when $u\in Gx$ and there exists $\kappa>0$ along with a
neighborhood $\mathcal{X}$ of $x$ and $\mathcal{U}$ of $u$ such that

$d(y,x)\leq\kappa\hat{d}(u,Gy\cap\mathcal{U}),\quad\forall y\in\mathcal{X},$

where $d$ and $\hat{d}$ are given metrics. Note that the [strong] metric
subregularity is classical and relates to many other common concepts in
variational analysis such as sharp minimizer, Aubin’s property, calmness, and
error bound condition.

More concretely, if $G$ is strongly metric subregular at any $x$ and
additionally $\mu$-hypomonotone (i.e. $\langle
u-v,x-y\rangle\geq-\mu\|x-y\|^{2}$ for all $(x,u),(y,v)\in\mathrm{gra}(G)$. If
the metrics $d$ and $\hat{d}$ are the standard Euclidean distances, i.e.
$d(y,x)=\|y-x\|$ and $\hat{d}(u,v)=\|u-v\|$, then we get $\langle
u-v,x-y\rangle\geq-\mu\|x-y\|^{2}\geq-\mu\kappa^{2}\|u-v\|^{2}$, showing that
$G$ is also $\mu\kappa^{2}$-co-hypomonotone.

Resolvent operator. Given a possibly multivalued mapping $T$, the operator

$J_{T}u:=\left\\{x\in\mathbb{R}^{p}:u\in x+Tx\right\\}$

is called the resolvent of $T$, often denoted by
$J_{T}u=(\mathbb{I}+T)^{-1}u$, where $\mathbb{I}$ is the identity mapping.
Clearly, evaluating $J_{T}$ requires solving an inclusion $0\in y-x+Ty$ in $y$
for given $x$. If $T$ is monotone, then $J_{T}$ is singled-valued, and if $T$
is maximally monotone, then $J_{T}$ is singled-valued and
$\mathrm{dom}(J_{T})=\mathbb{R}^{p}$. If $T$ is monotone, then $J_{T}$ is also
firmly nonexpansive [5, Proposition 23.10], and hence nonexpansive. Moreover
$0\in Tx$ if and only if $x$ is a fixed-point of $J_{T}$. If $T$ is
$\mu$-hypomonotone, then for $\mathbb{I}+\eta T$ is also
$(1-\eta\mu)$-strongly monotone, provided that $\eta\mu<1$. In this case,
$J_{\eta T}$ remains single-valued and $(1-\eta\mu)$-co-coercive.

###  2.2 Preliminary results

Let us recall the following preliminary results, which will be used in the
sequel.

Solution characterization. Let us characterize solutions of (chMI). Assume
that for some $\eta>0$, the resolvent $J_{\eta T}=(\mathbb{I}+\eta T)^{-1}$
associated with (chMI) exists and single-valued. Let us define the following
residual operator associated with (chMI):

$\mathcal{G}_{\eta}x:=\tfrac{1}{\eta}\left(x-J_{\eta T}(x-\eta Fx)\right).$
(1)

Then, $x^{\star}\in\mathrm{zer}(F+T)$ if and only if
$\mathcal{G}_{\eta}x^{\star}=0$. Our goal is to approximate $x^{\star}$ by
$x^{k}$ generated from a given algorithm after $k$ iterations such that
$\|\mathcal{G}_{\eta}x^{k}\|\leq\varepsilon$ for a given tolerance
$\varepsilon>0$. We also characterize the convergence rate of
$\|\mathcal{G}_{\eta}x^{k}\|$.

Another way of characterizing approximate solutions of (chMI) is to use a
residual $r^{k}:=Fx^{k}+\xi^{k}$ of (chMI) at $x^{k}$ for some $\xi^{k}\in
Tx^{k}$. Since $T$ is multivalued, there may exist different residuals $r^{k}$
at $x^{k}$. Clearly, since $r^{k}\in Fx^{k}+Tx^{k}$, if $\|r^{k}\|=0$, then
$x^{k}$ is an exact solution of (chMI). Therefore, if
$\|r^{k}\|\leq\varepsilon$ for some tolerance $\varepsilon>0$, then $x^{k}$
can be viewed as an $\varepsilon$-approximate solution of (chMI). We call
$r^{k}$ a residual of (chMI) at $x^{k}$. In this paper, we will upper bound
the norm $\|r^{k}\|$ of the residual $r^{k}$ at $x^{k}$ to characterize an
approximate solution $x^{k}$. If $x^{k}$ is the last iterate computed by the
algorithm, then we refer to the convergence rate on $\|r^{k}\|$ as the last-
iterate convergence rate. If $x^{k}=x^{k_{b}}$ with
$k_{b}:=\mathrm{arg}\\!\displaystyle\min\\{\|r^{i}\|:0\leq i\leq k\\}$, then
we call the convergence rate on $\|r^{k_{b}}\|$ the best-iterate convergence
rate.

A brief review of extragradient-type methods. The classical extragradient
method [25, 27, 38] is often applied to solve monotone variational
inequalities and their special cases. To solve the inclusion (chMI), its
modification was proposed by Tseng in [77], which is known as a forward-
backward-forward splitting (FBFS) method. This scheme is described as follows:
Given $y^{0}\in\mathbb{R}^{p}$, we update

$\left\\{\begin{array}[]{lcl}x^{k}&:=&J_{\eta T}(y^{k}-\eta
Fy^{k}),\vspace{1ex}\\\ y^{k+1}&:=&x^{k}-(\hat{\eta}Fx^{k}-\eta
Fy^{k}),\end{array}\right.$ (FBFS)

where $\eta>0$ and $\hat{\eta}>0$ are given parameter. Very often, we choose
$\hat{\eta}=\eta\in\left(0,\frac{1}{L}\right)$, where $L$ is the Lipschitz
constant of $F$. However, we can also choose $\hat{\eta}=\frac{\eta}{\beta}$
for some $0<\beta\leq 1$ as in [25, 46], which is called the extragradient
plus (EG+) scheme.

Note that if we replace $Fy^{k}$ by $Fx^{k-1}$ in the extragradient method
from [38], then we obtain Popov’s past-extragradient method in [65].
Similarly, if we replace $Fy^{k}$ in (FBFS) by $Fx^{k-1}$, then we obtain the
following past FBFS scheme:

$\left\\{\begin{array}[]{lcl}x^{k}&:=&J_{\eta T}(y^{k}-\eta
Fx^{k-1}),\vspace{1ex}\\\ y^{k+1}&:=&x^{k}-(\hat{\eta}Fx^{k}-\eta
Fx^{k-1}),\end{array}\right.$ (PFBFS)

where $x^{-1}:=y^{0}$ is given, $\hat{\eta}:=\frac{\eta}{\beta}$ for some
$\beta\in(0,1]$, and $\eta\in\left(1,\frac{1}{3L}\right]$ is a given
parameter. This method requires only one evaluation $Fx^{k}$ of $F$ and one
resolvent $J_{\hat{\eta}T}$. If we eliminate $y^{k}$ and choose
$\hat{\eta}=\eta$, then we obtain $\hat{x}^{k+1}=J_{\eta
T}(\hat{x}^{k}-\eta(2F\hat{x}^{k}-F\hat{x}^{k-1}))$ with
$\hat{x}^{k}:=x^{k-1}$, which is exactly the forward-reflected-backward
splitting scheme in [52]. While the asymptotic convergence and convergence
rates of both (FBFS) and (PFBFS) under the monotonicity of $F$ are classical,
the best-iterate convergence rates of these methods under the co-
hypomonotonicity of $F$ can be found, e.g., in [46]. Note that (PFBFS) is
different from the reflected forward-backward splitting method
$x^{k+1}:=J_{\eta T}(x^{k}-\eta F(2x^{k}-x^{k-1}))$ in [16] (rooted from the
projected reflected gradient method in [50]) or the golden ratio method in
[51] for solving monotone variational inequality, a special case of (chMI).

##  3 Nesterov’s Accelerated FBFS Method for Solving (chMI)

Our goal in this section is to develop an accelerated variant of (FBFS) to
solve (chMI) using Nesterov’s acceleration techniques [58]. Motivated from
recent works [13, 14, 24, 40, 75, 79] on Halpern’s fixed-point iteration with
“optimal” convergence rates on the norm of residual of (chMI), in this section
we exploit the idea from [73] to develop an alternative “Nesterov’s
accelerated” variant of the FBFS method (FBFS) to solve (chMI).

###  3.1 Algorithmic derivation

Our starting point is Nesterov’s acceleration interpretation of (FBFS) to
solve (chME) from [73]. Here, we extend this variant to solve the inclusion
(chMI), which is presented as follows: Starting from an initial point
$x^{0}\in\mathbb{R}^{p}$, set $y^{0}:=x^{0}$ and $z^{0}:=x^{0}$, we update

$\left\\{\begin{array}[]{lcl}z^{k+1}&:=&x^{k}-\gamma(Fx^{k}+\xi^{k}),\vspace{1ex}\\\
y^{k+1}&:=&z^{k+1}+\theta_{k}(z^{k+1}-z^{k})+\nu_{k}(y^{k}-z^{k+1}),\vspace{1ex}\\\
x^{k+1}&:=&y^{k+1}-\eta(Fy^{k+1}+\xi^{k+1})+\hat{\eta}_{k+1}(Fx^{k}+\xi^{k}),\end{array}\right.$
(2)

where $\gamma$, $\eta$, $\hat{\eta}_{k+1}$, $\theta_{k}$ and $\nu_{k}$ are
given parameters, which will be determined later, and $\xi^{k}\in Tx^{k}$ is
an arbitrary element of $Tx^{k}$. Clearly, if $T=0$, then (2) exactly reduces
to the one in [73].

Since $\xi^{k+1}\in Tx^{k+1}$ appears on the right-hand side of the last line
of (2), by conceptually using the resolvent $J_{\eta T}=(\mathbb{I}+\eta
T)^{-1}$ of $\eta T$, we can transform this scheme into an equivalent form
that is more convenient for implementation. First, we switch the first and
last lines of (2) and shift the index from $k+1$ to $k$ as

$x^{k}:=y^{k}-\eta(Fy^{k}+\xi^{k})+\hat{\eta}_{k}(Fx^{k-1}+\xi^{k-1}).$

Next, for simplicity of presentation, we introduce $w^{k}:=Fx^{k}+\xi^{k}$.
Then, from the last expression of $x^{k}$, we have $y^{k}-\eta
Fy^{k}+\hat{\eta}_{k}w^{k-1}=x^{k}+\eta\xi^{k}\in(\mathbb{I}+\eta T)x^{k}$.
Hence, we obtain $x^{k}=J_{\eta T}\big{(}y^{k}-\eta
Fy^{k}+\hat{\eta}_{k}w^{k-1}\big{)}$ provided that $J_{\eta T}$ is single-
valued. In addition, we also have
$x^{k}=y^{k}-\eta(Fy^{k}-Fx^{k}+w^{k})+\hat{\eta}_{k}w^{k-1}$, leading to
$w^{k}=\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}w^{k-1})+Fx^{k}-Fy^{k}$.
Finally, putting these derivations together, we obtain the following
equivalent interpretation of (2):

$\left\\{\begin{array}[]{lcl}{\color[rgb]{0,0,0}x^{k}}&{\color[rgb]{0,0,0}:=}&{\color[rgb]{0,0,0}J_{\eta
T}\big{(}y^{k}-\eta Fy^{k}+\hat{\eta}_{k}w^{k-1}\big{)},\vspace{1ex}}\\\
w^{k}&:=&\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}w^{k-1})+Fx^{k}-Fy^{k},\vspace{1ex}\\\
z^{k+1}&:=&x^{k}-\gamma w^{k},\vspace{1ex}\\\
y^{k+1}&:=&z^{k+1}+\theta_{k}(z^{k+1}-z^{k})+\nu_{k}(y^{k}-z^{k+1}),\end{array}\right.$
(AEG)

where we choose
$w^{-1}:=\frac{\eta}{\hat{\eta}_{0}}w^{0}=\frac{\eta}{\hat{\eta}_{0}}(Fx^{0}+\xi^{0})$
for $\xi^{0}\in Tx^{0}$, and set $z^{0}=y^{0}:=x^{0}$ for a given initial
point $x^{0}\in\mathbb{R}^{p}$. We call this scheme an accelerated FBFS method
to distinguish it from the extra-anchored gradient method in [79] (see also
Section 5).

If $J_{\eta T}$ is computable, then (AEG) is implementable. Nevertheless, we
have not yet obviously seen the connection between (AEG) and (FBFS). Now, let
us eliminate $z^{k}$ to obtain

$\left\\{\begin{array}[]{lcl}{\color[rgb]{0,0,0}x^{k}}&{\color[rgb]{0,0,0}:=}&{\color[rgb]{0,0,0}J_{\eta
T}\big{(}y^{k}-\eta Fy^{k}{\ +\ \hat{\eta}_{k}w^{k-1}}\big{)},\vspace{1ex}}\\\
w^{k}&:=&\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}w^{k-1})+Fx^{k}-Fy^{k},\vspace{1ex}\\\
{\color[rgb]{0,0,0}y^{k+1}}&:=&{\color[rgb]{0,0,0}x^{k}+\theta_{k}(x^{k}-x^{k-1})-\beta_{k}w^{k}+\sigma_{k}w^{k-1}-\eta\nu_{k}(Fx^{k}-Fy^{k}),}\end{array}\right.$
(3)

where $\beta_{k}:=\gamma(1+\theta_{k}-\nu_{k})-\eta\nu_{k}$ and
$\sigma_{k}:=\gamma\theta_{k}-\nu_{k}\hat{\eta}_{k}$. We can view (3) as an
accelerated variant of (FBFS), where a momentum term
${\theta_{k}(x^{k}-x^{k-1})}$ and other simple correction terms are added to
(FBFS) as observed in [48].

Overall, at each iteration $k$, (AEG) requires one evaluation of the resolvent
$J_{\eta T}$ of $\eta T$ and two evaluations $Fx^{k}$ and $Fy^{k}$ of $F$.
This per-iteration complexity is essentially the same as (FBFS). When $T=0$,
as indicated in [73], (2) can be derived from the Halpern-type schemes
developed in [40, 79]. The convergence rates of these Halpern-type schemes
were proven in [40, 79] for both the monotone and co-hypomonotone cases when
$T=0$. When $T\neq 0$, [13, 14] recently proposed corresponding Halpern-type
schemes and analyzed their convergence rates for both the monotone and co-
hypomonotone cases.

######  Remark 3.1.

We can replace the standard resolvent $J_{\eta T}:=(\mathbb{I}+\eta T)^{-1}$
by its generalization $J_{\eta T}:=(D+\eta T)^{-1}\circ D$, where $D$ is a
symmetric and positive semidefinite operator. In addition, our methods and
their convergence results on $\|Fx^{k}+v^{k}\|$ remain valid if $J_{\eta T}$
is a multivalued mapping and satisfies $\mathrm{ran}(J_{\eta
T})\subseteq\mathrm{dom}(F)=\mathbb{R}^{p}$ and $\mathrm{dom}(J_{\eta
T})=\mathbb{R}^{p}$. These conditions guarantee the well-definedness of (AEG).

###  3.2 Convergence analysis

To establish the convergence of (AEG), we use the following potential or
Lyapunov function from [73]:

$\mathcal{P}_{k}:=a_{k}\|w^{k-1}\|^{2}+b_{k}\langle
w^{k-1},z^{k}-y^{k}\rangle+\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}\|^{2},$ (4)

where $a_{k}>0$, $b_{k}>0$, and $t_{k}>0$ are given parameters. Note that [73]
did not provide convergence analysis for (AEG) in the co-hypomonotone case
even when $T=0$. It only established the convergence rate of a Nesterov’s
accelerated variant derived from the extra-anchored gradient method in [79].
Here, we reuse this potential function to analyze the convergence of (AEG) for
solving (chMI) in the co-hypomonotone setting, which obviously covers the
monotone case.

Let us first lower bound the potential function $\mathcal{P}_{k}$ as in the
following lemma.

######  Lemma 3.1.

Let $\\{(x^{k},y^{k},z^{k},w^{k})\\}$ be generated by (AEG) and
$\mathcal{P}_{k}$ be defined by (4). Then, $w^{k}\in Fx^{k}+Tx^{k}$. If
$J_{\eta T}$ is single-valued and nonexpansive for any $\eta>0$, then for
$\mathcal{G}_{\eta}$ defined by (1), we have

$\|\mathcal{G}_{\eta}x^{k}\|\leq\|w^{k}\|.$ (5)

If $F+T$ is $\rho$-co-hypomonotone, then

$\mathcal{P}_{k}\geq\|z^{k}+t_{k}(y^{k}-z^{k})-\tfrac{b_{k}}{2t_{k}}w^{k-1}-x^{\star}\|^{2}+\left(a_{k}-\tfrac{b_{k}^{2}}{4t_{k}^{2}}-\tfrac{(\gamma+\rho)b_{k}}{t_{k}}\right)\|w^{k-1}\|^{2}.$
(6)

Consequently, if
$a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{(\gamma+\rho)b_{k}}{t_{k}}\geq 0$
and $J_{\eta T}$ is single-valued and nonexpansive, then we obtain

$\mathcal{P}_{k}\geq\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{(\gamma+\rho)b_{k}}{t_{k}}\right)\|\mathcal{G}_{\eta}x^{k-1}\|^{2}.$
(7)

###### Proof.

From the first line of (AEG), we have $y^{k}-x^{k}+\hat{\eta}_{k}w^{k-1}-\eta
Fy^{k}\in\eta Tx^{k}$. Rearranging this expression, inserting $Fx^{k}$ to both
sides, and using $w^{k}$ from the second line of (AEG), we have
$w^{k}=\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}w^{k-1})-(Fy^{k}-Fx^{k})\in
Fx^{k}+Tx^{k}$. This proves that $w^{k}\in Fx^{k}+Tx^{k}$.

From $w^{k}\in Fx^{k}+Tx^{k}$, we get $x^{k}-\eta Fx^{k}+\eta w^{k}\in
x^{k}+\eta Tx^{k}$, leading to $x^{k}=J_{\eta T}(x^{k}-\eta Fx^{k}+\eta
w^{k})$ due to the single-valued assumption of $J_{\eta T}$. Using this
relation, the definition of $\mathcal{G}_{\eta}$ from (1), and the
nonexpansiveness of $J_{\eta T}$ from our assumption, we have

$\eta\|\mathcal{G}_{\eta}x^{k}\|=\|x^{k}-J_{\eta T}(x^{k}-\eta
Fx^{k})\|=\|J_{\eta T}(x^{k}-\eta Fx^{k}+\eta w^{k})-J_{\eta T}(x^{k}-\eta
Fx^{k})\|\leq\eta\|w^{k}\|.$

This clearly implies that $\|G_{\eta}x^{k}\|\leq\|w^{k}\|$ as in (5).

Next, utilizing $z^{k}=x^{k-1}-\gamma w^{k-1}$ from the third line of (AEG),
and the $\rho$-co-hypomonotonicity of $F+T$ with $\langle
w^{k-1},x^{k-1}-x^{\star}\rangle\geq-\rho\|w^{k-1}\|^{2}$, we can show that

$\begin{array}[]{lcl}\mathcal{P}_{k}&=&\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}-\frac{b_{k}}{2t_{k}}w^{k-1}\|^{2}+\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{\gamma
b_{k}}{t_{k}}\right)\|w^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{b_{k}}{t_{k}}\langle
w^{k-1},x^{k-1}-x^{\star}\rangle\vspace{1ex}\\\
&\geq&\|z^{k}+t_{k}(y^{k}-z^{k})-\frac{b_{k}}{2t_{k}}w^{k-1}-x^{\star}\|^{2}+\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{(\gamma+\rho)b_{k}}{t_{k}}\right)\|w^{k-1}\|^{2}.\end{array}$

This is exactly (6). Combining (6) and $\|G_{\eta}x^{k}\|\leq\|w^{k}\|$, we
obtain (7). $\square$∎

Our first main result is the following theorem showing the convergence rate of
the accelerated FBFS scheme (AEG).

######  Theorem 3.1.

Assume that $F+T$ in (chMI) is $\rho$-co-hypomonotone, $F$ is $L$-Lipschitz
continuous such that $2L\rho<1$, and $x^{\star}\in\mathrm{zer}(F+T)$ is an
arbitrary solution of (chMI). Let $\gamma>0$ be such that $L(2\rho+\gamma)\leq
1$ $($e.g., $\gamma:=\frac{1}{L}-2\rho>0$$)$ and $\\{(x^{k},y^{k},z^{k})\\}$
be generated by (AEG) using the following update rules:

$t_{k}:=k+2,\quad\eta:=\gamma+2\rho,\quad\hat{\eta}_{k}=\frac{(t_{k}-1)\eta}{t_{k}},\quad\theta_{k}:=\frac{t_{k}-1}{t_{k+1}},\quad\text{and}\quad\nu_{k}:=\frac{t_{k}}{t_{k+1}}.$
(8)

Then, the following bound holds:

$\|Fx^{k}+\xi^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+8\gamma(3\gamma+2\rho)\|Fx^{0}+\xi^{0}\|^{2}}{\gamma^{2}(k+2)^{2}},\quad\text{where}\quad\xi^{k}\in
Tx^{k}.$ (9)

If $J_{\eta T}$ is nonexpansive, then for $\mathcal{G}_{\eta}$ defined by (1),
we also have

$\|\mathcal{G}_{\eta}x^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+8\gamma(3\gamma+2\rho)\|Fx^{0}+\xi^{0}\|^{2}}{\gamma^{2}(k+2)^{2}}.$
(10)

Theorem 3.1 provides an alternative view of the “accelerated” FBFS method
based on Nesterov’s accelerated interpretation [73]. Our condition $2L\rho<1$
is the same as in [13, 40] for the Halpern-type variants of (FBFS). Note that
the estimate (9) only requires the $\rho$-co-hypomonotonicity of $F+T$ and the
$L$-Lipschitz continuity of $F$, while (10) additionally requires the
nonexpansiveness of $J_{\eta T}$. If $\rho=0$, i.e. $F+T$ is monotone, then
our condition on the stepsize $\gamma$ becomes $L\gamma<1$, which is used in
the clasical extragradient and FBFS methods, e.g., in [38]. If $\rho<0$, i.e.
$F+T$ is $-\rho$-co-coercive, then our bounds remain valid as long as
$-1<L(\gamma+2\rho)\leq 1$ (or
$\max\left\\{-\frac{1}{L}-2\rho,0\right\\}<\gamma\leq\frac{1}{L}-2\rho)$.
However, we may expect a linear convergence rate instead of a sublinear rate
as in Theorem 3.1. This requires to adapt our analysis by using the
techniques, e.g., in [61], which is beyond the scope of this paper.

Note that we can choose different $\eta$ such that $L\eta\leq 1$, but not
necessary to be $\eta=\gamma+2\rho$ as in (8). The update rule (8) in Theorem
3.1 only provides one choice of $\eta$ and it makes our analysis simpler.
However, other choices of $\eta$ and $\gamma$ can also work as long as they
satisfy the conditions in our analysis below.

###### The proof of Theorem 3.1.

First, by inserting $(t_{k}-1)z^{k+1}-(t_{k}-1)z^{k+1}$, we can easily expand
$\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}\|^{2}$ as follows:

$\begin{array}[]{lcl}\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}\|^{2}&=&\|z^{k+1}-x^{\star}+(t_{k}-1)(z^{k+1}-z^{k})+t_{k}(y^{k}-z^{k+1})\|^{2}\vspace{1ex}\\\
&=&\|z^{k+1}-x^{\star}\|^{2}+(t_{k}-1)^{2}\|z^{k+1}-z^{k}\|^{2}+t_{k}^{2}\|y^{k}-z^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}2(t_{k}-1)\langle
z^{k+1}-z^{k},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\ &&+{~{}}2t_{k}\langle
y^{k}-z^{k+1},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\
&&+{~{}}2(t_{k}-1)t_{k}\langle y^{k}-z^{k+1},z^{k+1}-z^{k}\rangle.\end{array}$

Next, from the fourth line of (AEG), we have
$y^{k+1}-z^{k+1}=\theta_{k}(z^{k+1}-z^{k})+\nu_{k}(y^{k}-z^{k+1})$. Using this
line, we can show that

$\begin{array}[]{lcl}\mathcal{T}_{[1]}&:=&\|z^{k+1}+t_{k+1}(y^{k+1}-z^{k+1})-x^{\star}\|^{2}\vspace{1ex}\\\
&=&\|z^{k+1}-x^{\star}+t_{k+1}[\theta_{k}(z^{k+1}-z^{k})+\nu_{k}(y^{k}-z^{k+1})]\|^{2}\vspace{1ex}\\\
&=&\|z^{k+1}-x^{\star}\|^{2}+t_{k+1}^{2}\theta_{k}^{2}\|z^{k+1}-z^{k}\|^{2}+t_{k+1}^{2}\nu_{k}^{2}\|y^{k}-z^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}2t_{k+1}\theta_{k}\langle
z^{k+1}-z^{k},z^{k+1}-x^{\star}\rangle+2t_{k+1}\nu_{k}\langle
y^{k}-z^{k+1},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\
&&+{~{}}2t_{k+1}^{2}\nu_{k}\theta_{k}\langle
y^{k}-z^{k+1},z^{k+1}-z^{k}\rangle.\end{array}$

Combining the last two expressions, we can easily get

$\begin{array}[]{lcl}\mathcal{T}_{[2]}&:=&\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}\|^{2}-\|z^{k+1}+t_{k+1}(y^{k+1}-z^{k+1})-x^{\star}\|^{2}\vspace{1ex}\\\
&=&\left[(t_{k}-1)^{2}-t_{k+1}^{2}\theta_{k}^{2}\right]\|z^{k+1}-z^{k}\|^{2}+(t_{k}^{2}-\nu_{k}^{2}t_{k+1}^{2})\|y^{k}-z^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}2(t_{k}-1-t_{k+1}\theta_{k})\langle
z^{k+1}-z^{k},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\
&&+{~{}}2(t_{k}-t_{k+1}\nu_{k})\langle
y^{k}-z^{k+1},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\
&&+{~{}}2\left[t_{k}(t_{k}-1)-\theta_{k}\nu_{k}t_{k+1}^{2}\right]\langle
y^{k}-z^{k+1},z^{k+1}-z^{k}\rangle.\end{array}$

Using the above expression $\mathcal{T}_{[2]}$, the definition of
$\mathcal{P}_{k}$ from (4), and the fourth line of (AEG) as
$z^{k+1}-y^{k+1}=-\theta_{k}(z^{k+1}-z^{k})-\nu_{k}(y^{k}-z^{k+1})$, we can
further derive

$\begin{array}[]{lcl}\mathcal{P}_{k}-\mathcal{P}_{k+1}&=&a_{k}\|w^{k-1}\|^{2}-a_{k+1}\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[(t_{k}-1)^{2}-t_{k+1}^{2}\theta_{k}^{2}\right]\|z^{k+1}-z^{k}\|^{2}+(t_{k}^{2}-\nu_{k}^{2}t_{k+1}^{2})\|y^{k}-z^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}b_{k}\langle
w^{k}-w^{k-1},z^{k+1}-z^{k}\rangle+b_{k+1}\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},y^{k}-z^{k+1}\rangle\vspace{1ex}\\\
&&+{~{}}\left(b_{k+1}\theta_{k}-b_{k}\right)\big{[}\langle
w^{k},z^{k+1}-z^{k}\rangle+\langle
w^{k-1},y^{k}-z^{k+1}\rangle\big{]}\vspace{1ex}\\\
&&+{~{}}2(t_{k}-1-t_{k+1}\theta_{k})\langle
z^{k+1}-z^{k},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\
&&+{~{}}2(t_{k}-t_{k+1}\nu_{k})\langle
y^{k}-z^{k+1},z^{k+1}-x^{\star}\rangle\vspace{1ex}\\\
&&+{~{}}2\left[t_{k}(t_{k}-1)-t_{k+1}^{2}\theta_{k}\nu_{k}\right]\langle
y^{k}-z^{k+1},z^{k+1}-z^{k}\rangle.\end{array}$ (11)

Let us choose positive parameters $t_{k}$, $\nu_{k}$, $\theta_{k}$, and
$b_{k}$ such that

$\begin{array}[]{lclclcl}t_{k}-t_{k+1}\nu_{k}&=&0,&&t_{k}(t_{k}-1)-\nu_{k}\theta_{k}t_{k+1}^{2}&=&0,\vspace{1ex}\\\
t_{k}-1-t_{k+1}\theta_{k}&=&0,&\text{and}&b_{k+1}\theta_{k}-b_{k}&=&0.\end{array}$
(12)

These conditions lead to the update of $\theta_{k}$, $\nu_{k}$, and $b_{k}$ as
$\theta_{k}=\frac{t_{k}-1}{t_{k+1}}$, $\nu_{k}=\frac{t_{k}}{t_{k+1}}$, and
$b_{k+1}=\frac{b_{k}}{\theta_{k}}=\frac{b_{k}t_{k+1}}{t_{k}-1}$, respectively.
Clearly, these updates of $\nu_{k}$ and $\theta_{k}$ are exactly shown in (8).

Now, under the choice of parameters as in (12), (11) reduces to

$\begin{array}[]{lcl}\mathcal{P}_{k}-\mathcal{P}_{k+1}&=&a_{k}\|w^{k-1}\|^{2}-a_{k+1}\|w^{k}\|^{2}+b_{k}\langle
w^{k}-w^{k-1},z^{k+1}-z^{k}\rangle\vspace{1ex}\\\
&&+{~{}}b_{k+1}\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},y^{k}-z^{k+1}\rangle.\end{array}$
(13)

As shown in Lemma 3.1, we have $w^{k}\in Fx^{k}+Tx^{k}$. By the $\rho$-co-
hypomonotonicity of $F+T$ and $z^{k+1}=x^{k}-\gamma w^{k}$ from the third line
of (AEG), we have $\langle w^{k}-w^{k-1},z^{k+1}-z^{k}\rangle=\langle
w^{k}-w^{k-1},x^{k}-x^{k-1}\rangle-\gamma\|w^{k}-w^{k-1}\|^{2}\geq-(\rho+\gamma)\|w^{k}-w^{k-1}\|^{2}$.
Therefore, we get

$\begin{array}[]{lcl}\langle
w^{k}-w^{k-1},z^{k+1}-z^{k}\rangle&\geq&-(\gamma+\rho)\left[\|w^{k}\|^{2}+\|w^{k-1}\|^{2}-2\langle
w^{k},w^{k-1}\rangle\right].\end{array}$ (14)

For our convenience, let us denote $\hat{w}^{k}:=w^{k}+Fy^{k}-Fx^{k}$. Then,
it is obvious that $Fy^{k}-Fx^{k}=\hat{w}^{k}-w^{k}$. From the second line of
(AEG) and $Fy^{k}-Fx^{k}=\hat{w}^{k}-w^{k}$, we have
$x^{k}-y^{k}=\hat{\eta}_{k}w^{k-1}-\eta\hat{w}^{k}$. Substituting this into
the third line of (AEG), we get $y^{k}-z^{k+1}=\gamma
w^{k}+\eta\hat{w}^{k}-\hat{\eta}_{k}w^{k-1}$. Using this expression, we can
show that

$\begin{array}[]{lcl}\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},y^{k}-z^{k+1}\rangle&=&\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},\gamma
w^{k}+\eta\hat{w}^{k}-\hat{\eta}_{k}w^{k-1}\rangle\vspace{1ex}\\\
&=&\nu_{k}\gamma\|w^{k}\|^{2}+\theta_{k}\hat{\eta}_{k}\|w^{k-1}\|^{2}+\nu_{k}\eta\langle
w^{k},\hat{w}^{k}\rangle\vspace{1ex}\\\ &&-{~{}}\eta\theta_{k}\langle
w^{k-1},\hat{w}^{k}\rangle-(\nu_{k}\hat{\eta}_{k}+\gamma\theta_{k})\langle
w^{k-1},w^{k}\rangle.\end{array}$ (15)

Substituting (14) and (15) into (13), and utilizing $b_{k}=b_{k+1}\theta_{k}$,
we can show that

$\begin{array}[]{lcl}\mathcal{P}_{k}-\mathcal{P}_{k+1}&\geq&\left[a_{k}+b_{k}\left(\hat{\eta}_{k}-\gamma-\rho\right)\right]\|w^{k-1}\|^{2}+\left[b_{k}\left(\frac{\gamma\nu_{k}}{\theta_{k}}-\gamma-\rho\right)-a_{k+1}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\eta b_{k}\left(\frac{\nu_{k}}{\theta_{k}}-1\right)\langle
w^{k},\hat{w}^{k}\rangle+\eta b_{k}\langle
w^{k}-w^{k-1},\hat{w}^{k}\rangle\vspace{1ex}\\\
&&-{~{}}b_{k}\left(\frac{\hat{\eta}_{k}\nu_{k}}{\theta_{k}}-\gamma-2\rho\right)\langle
w^{k-1},w^{k}\rangle.\end{array}$ (16)

Now, using the Lipschitz continuity of $F$ and the relations
$Fy^{k}-Fx^{k}=\hat{w}^{k}-w^{k}$ and
$x^{k}-y^{k}=\hat{\eta}_{k}w^{k-1}-\eta\hat{w}^{k}$ as above, we have
$\|\hat{w}^{k}-w^{k}\|^{2}=\|Fy^{k}-Fx^{k}\|^{2}\leq
L^{2}\|x^{k}-y^{k}\|^{2}=L^{2}\|\eta\hat{w}^{k}-\hat{\eta}_{k}w^{k-1}\|^{2}$.
This inequality leads to

$\begin{array}[]{lcl}0&\geq&\|w^{k}\|^{2}+(1-L^{2}\eta^{2})\|\hat{w}^{k}\|^{2}-2\left(1-L^{2}\eta\hat{\eta}_{k}\right)\langle
w^{k},\hat{w}^{k}\rangle\vspace{1ex}\\\
&&-{~{}}2L^{2}\eta\hat{\eta}_{k}\langle
w^{k}-w^{k-1},\hat{w}^{k}\rangle-L^{2}\hat{\eta}_{k}^{2}\|w^{k-1}\|^{2}.\end{array}$

Multiplying this inequality by $\frac{b_{k}}{2L^{2}\hat{\eta}_{k}}$ and adding
the result to (16), we get

$\begin{array}[]{lcl}\mathcal{P}_{k}-\mathcal{P}_{k+1}&\geq&\left[a_{k}+\frac{b_{k}}{2}\left(\hat{\eta}_{k}-2\gamma-2\rho\right)\right]\|w^{k-1}\|^{2}+\frac{b_{k}(1-L^{2}\eta^{2})}{2L^{2}\hat{\eta}_{k}}\|\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[b_{k}\left(\frac{\gamma\nu_{k}}{\theta_{k}}+\frac{1}{2L^{2}\hat{\eta}_{k}}-\gamma-\rho\right)-a_{k+1}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}b_{k}\left(\frac{\eta\nu_{k}}{\theta_{k}}-\frac{1}{L^{2}\hat{\eta}_{k}}\right)\langle
w^{k},\hat{w}^{k}\rangle-
b_{k}(\frac{\hat{\eta}_{k}\nu_{k}}{\theta_{k}}-2\rho-\gamma)\langle
w^{k-1},w^{k}\rangle.\end{array}$ (17)

Let us choose $\eta:=\gamma+2\rho$ and
$\hat{\eta}_{k}:=\frac{\eta\theta_{k}}{\nu_{k}}=\frac{\eta(t_{k}-1)}{t_{k}}$
as in (8). Then, using $\nu_{k}=\frac{t_{k}}{t_{k+1}}$,
$\theta_{k}=\frac{t_{k}-1}{t_{k+1}}$, $b_{k+1}=\frac{b_{k}t_{k+1}}{t_{k}-1}$,
and $\eta:=\gamma+2\rho$, we can simplify (17) as

$\begin{array}[]{lcl}\mathcal{P}_{k}-\mathcal{P}_{k+1}&\geq&\left(a_{k}-\frac{b_{k}(\gamma
t_{k}+\eta)}{2t_{k}}\right)\|w^{k-1}\|^{2}+\left[\frac{b_{k}\left(\gamma
t_{k}+\gamma+\eta\right)}{2(t_{k}-1)}-a_{k+1}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{b_{k}(1-L^{2}\eta^{2})t_{k}}{2L^{2}\eta(t_{k}-1)}\|w^{k}-\hat{w}^{k}\|^{2}.\end{array}$
(18)

Next, we impose the following conditions:

$1-L^{2}\eta^{2}\geq 0,\quad a_{k}-\frac{b_{k}(\gamma t_{k}+\eta)}{2t_{k}}\geq
0,\quad\text{and}\quad\frac{b_{k}\left(\gamma
t_{k}+\gamma+\eta\right)}{2(t_{k}-1)}-a_{k+1}\geq 0.$ (19)

Then, under the conditions of (19), (18) reduces to
$\mathcal{P}_{k}-\mathcal{P}_{k+1}\geq 0$ for all $k\geq 0$.

We need to show that with the update rules as in (8), three conditions of (19)
hold. Indeed, the first condition of (19) is equivalent to
$L\eta=L(\gamma+2\rho)\leq 1$. If $2L\rho<1$, then we can always choose
$0<\gamma\leq\frac{1}{L}-2\rho$ such that $1-L^{2}\eta^{2}\geq 0$. This is our
first condition in Theorem 9.

Now, let us choose $a_{k}:=\frac{b_{k}(\gamma t_{k}+\eta)}{2t_{k}}$. Then, the
second condition of (19) automatically holds. The third condition of (19)
becomes $a_{k+1}\leq\frac{b_{k+1}(\gamma t_{k+1}+\eta)}{2t_{k+1}}$ due to
$b_{k+1}=\frac{b_{k}t_{k+1}}{t_{k}-1}$ and $t_{k}=k+2$. By the choice of
$a_{k}$, this condition holds with equality. For $t_{k}:=k+2$, we can easily
obtain $b_{k}:=\frac{b_{0}(k+1)(k+2)}{2}$ for some $b_{0}>0$, and
consequently, $a_{k}=\frac{b_{k}(\gamma
t_{k}+\eta)}{2t_{k}}=\frac{b_{0}(k+1)(\gamma k+3\gamma+2\rho)}{4}$.

Finally, since $\mathcal{P}_{k+1}\leq\mathcal{P}_{k}$, by induction we get

$\begin{array}[]{lcl}\mathcal{P}_{k}&\leq&\mathcal{P}_{0}=a_{0}\|w^{-1}\|^{2}+b_{0}\langle
w^{-1},z^{0}-y^{0}\rangle+\|z^{0}+t_{0}(y^{0}-z^{0})-x^{\star}\|^{2}\vspace{1ex}\\\
&=&4a_{0}\|w^{0}\|^{2}+\|x^{0}-x^{\star}\|^{2}=b_{0}(3\gamma+2\rho)\|w^{0}\|^{2}+\|x^{0}-x^{\star}\|^{2},\end{array}$

due to $z^{0}=y^{0}=x^{0}$ and
$w^{-1}=\frac{\eta}{\hat{\eta}_{0}}w^{0}=2w^{0}$. Combining this expression
and (6), and then using the expressions of $a_{k}$ and $b_{k}$, we get

$\begin{array}[]{lcl}\mathcal{P}_{0}&=&\frac{b_{0}(3\gamma+2\rho)}{2}\|w^{0}\|^{2}+\|x^{0}-x^{\star}\|^{2}\vspace{1ex}\\\
&\geq&\mathcal{P}_{k}\geq\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{(\gamma+\rho)b_{k}}{t_{k}}\right)\|w^{k-1}\|^{2}=\frac{b_{0}(4\gamma-
b_{0})(k+1)^{2}}{16}\|w^{k-1}\|^{2}.\end{array}$

If we choose $b_{0}:=2\gamma$, then the last estimate leads to
$\|w^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}}{\gamma^{2}(k+2)^{2}}+\frac{8(3\gamma+2\rho)}{\gamma(k+2)^{2}}\|w^{0}\|^{2}$,
which is exactly (9) since $w^{0}:=Fx^{0}+\xi^{0}$. If $J_{\eta T}$ is
nonexpansive, then by (5), we obtain (10). $\square$∎

##  4 Nesterov’s Accelerated Past-FBFS Method for Solving (chMI)

Alternative to Section 3, in this section, we develop a new Nesterov’s
accelerated variant of the FBFS method (FBFS) for solving (chMI) by adopting
the ideas from [65, 77]. However, our scheme is different from (PFBFS) since
it replaces $Fx^{k}$ by $Fy^{k-1}$ instead of replacing $Fy^{k}$ by
$Fx^{k-1}$.

###  4.1 Algorithmic derivation

Since (AEG) requires two evaluations $Fx^{k}$ and $Fy^{k}$ of $F$ at each
iteration as in (FBFS), we reduce its per-iteration complexity by replacing
$Fx^{k}$ by $Fy^{k-1}$ computed from the previous iteration. Rearranging the
resulting scheme and using the resolvent of $\eta T$, we obtain the following
new scheme: Given $x^{0}\in\mathbb{R}^{p}$, set $z^{0}=y^{0}:=x^{0}$ and
$\hat{w}^{-1}:=\frac{\eta}{\hat{\eta}_{0}}w^{0}\in\frac{\eta}{\hat{\eta}_{0}}(Fx^{0}+Tx^{0})$,
at each iteration $k$, we update

$\left\\{\begin{array}[]{lcl}x^{k}&:=&J_{\eta T}\big{(}y^{k}-\eta
Fy^{k}+\hat{\eta}_{k}\hat{w}^{k-1}\big{)},\vspace{1ex}\\\
\hat{w}^{k}&:=&\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}\hat{w}^{k-1}),\vspace{1ex}\\\
z^{k+1}&:=&x^{k}-\gamma\hat{w}^{k},\vspace{1ex}\\\
y^{k+1}&:=&z^{k+1}+\theta_{k}(z^{k+1}-z^{k})+\nu_{k}(y^{k}-z^{k+1}),\end{array}\right.$
(APEG)

where $\theta_{k}$, $\nu_{k}$, $\eta$, and $\gamma$ are given parameters,
which will be determined later.

Note that the idea of replacing either $Fx^{k}$ or $Fy^{k}$ by a past value
was proposed by Popov in [65] for the classical extragradient method, and then
extended to FBFS variants as seen from (PFBFS). However, unlike (PFBFS), we
replace $Fx^{k}$ by $Fy^{k-1}$, leading to (APEG). Clearly, at each iteration
$k$, (APEG) only requires one evaluation of $J_{\eta T}$ and one evaluation
$Fy^{k}$ of $F$ compared to (AEG).

If we eliminate $z^{k}$ from (APEG), then we obtain the following scheme:

$\left\\{\begin{array}[]{lcl}x^{k}&:=&J_{\eta T}\big{(}y^{k}-\eta
Fy^{k}+\hat{\eta}_{k}\hat{w}^{k-1}\big{)},\vspace{1ex}\\\
\hat{w}^{k}&:=&\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}\hat{w}^{k-1}),\vspace{1ex}\\\
y^{k+1}&:=&x^{k}+\theta_{k}(x^{k}-x^{k-1})-\beta_{k}\hat{w}^{k}+\sigma_{k}\hat{w}^{k-1},\end{array}\right.$
(20)

where $\beta_{k}:=\gamma(1+\theta_{k}-\nu_{k})-\eta\nu_{k}$ and
$\sigma_{k}:=\gamma\theta_{k}-\hat{\eta}_{k}\nu_{k}$. This representation uses
both $\hat{w}^{k}$ and $\hat{w}^{k-1}$ to update $y^{k+1}$. However, since
(20) uses $Fy^{k-1}$ instead of $Fx^{k-1}$, it is different from (PFBFS) as
well as the reflected-forward-backward splitting method in [16, 50].

###  4.2 Convergence analysis

To form a potential function for (APEG), starting from the first and second
lines of (APEG), we have
$\hat{w}^{k}-Fy^{k}=\frac{1}{\eta}(y^{k}-x^{k}+\hat{\eta}_{k}\hat{w}^{k-1})-Fy^{k}\in
Tx^{k}$. Hence, if we define $w^{k}:=\hat{w}^{k}+Fx^{k}-Fy^{k}$, then
$w^{k}\in Fx^{k}+Tx^{k}$. Therefore, we propose to use the following potential
or Lyapunov function to analyze the convergence of (APEG), which is similar to
$\mathcal{P}_{k}$ in (4):

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}&:=&a_{k}\|w^{k-1}\|^{2}+b_{k}\langle
w^{k-1},z^{k}-y^{k}\rangle+\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}\|^{2}\vspace{1ex}\\\
&&+{~{}}c_{k}\|w^{k-1}-\hat{w}^{k-1}\|^{2}.\end{array}$ (21)

where $a_{k}>0$, $b_{k}>0$, $c_{k}>0$, and $t_{k}>0$ are given parameters,
determined later.

Similar to the proof of (6), using $z^{k}=x^{k-1}-\gamma\hat{w}^{k-1}$ from
the third line of (APEG), the $\rho$-co-hypomonotonicity of $F+T$ as $\langle
w^{k-1},x^{k-1}-x^{\star}\rangle\geq-\rho\|w^{k-1}\|^{2}$, and Young’s
inequality as $-\langle w^{k-1},\hat{w}^{k-1}\rangle=-\langle
w^{k-1},\hat{w}^{k-1}-w^{k-1}\rangle-\|w^{k-1}\|^{2}\geq-\frac{3}{2}\|w^{k-1}\|^{2}-\frac{1}{2}\|w^{k-1}-\hat{w}^{k-1}\|^{2}$,
we can lower bound $\hat{\mathcal{P}}_{k}$ as follows:

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}&=&\|z^{k}+t_{k}(y^{k}-z^{k})-x^{\star}-\frac{b_{k}}{2t_{k}}w^{k-1}\|^{2}+c_{k}\|w^{k-1}-\hat{w}^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}\right)\|w^{k-1}\|^{2}+\frac{b_{k}}{t_{k}}\langle
w^{k-1},x^{k-1}-x^{\star}\rangle-\frac{\gamma b_{k}}{t_{k}}\langle
w^{k-1},\hat{w}^{k-1}\rangle\vspace{1ex}\\\
&\geq&\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{(3\gamma+2\rho)b_{k}}{2t_{k}}\right)\|w^{k-1}\|^{2}+\left(c_{k}-\frac{\gamma
b_{k}}{2t_{k}}\right)\|w^{k-1}-\hat{w}^{k-1}\|^{2}.\end{array}$ (22)

Now, we are ready to establish the convergence of APEG in the following
theorem.

######  Theorem 4.1.

Assume that $F+T$ in (chMI) is $\rho$-co-hypomonotone, $F$ is $L$-Lipschitz
continuous such that $8\sqrt{3}L\rho<1$, and $x^{\star}\in\mathrm{zer}(F+T)$
is an arbitrary solution of (chMI). Let $\gamma>0$ be such that
$16L^{2}\big{[}3(3\gamma+2\rho)^{2}+\gamma(2\gamma+\rho)\big{]}\leq 1$, which
always exists, and $\\{(x^{k},y^{k},z^{k})\\}$ be generated by (APEG) using

$t_{k}:=k+2,\ \ \eta:=2(3\gamma+2\rho),\ \
\hat{\eta}_{k}=\frac{(t_{k}-1)\eta}{t_{k}},\ \
\theta_{k}:=\frac{t_{k}-1}{t_{k+1}},\ \text{and}\ \
\nu_{k}:=\frac{t_{k}}{t_{k+1}}.$ (23)

Then, for $k\geq 0$, the following bound holds:

$\|Fx^{k}+\xi^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+8\gamma(5\gamma+2\rho)\|Fx^{0}+\xi^{0}\|^{2}}{\gamma^{2}(k+2)(k+4)},\quad\text{where}\quad\xi^{k}\in
Tx^{k}.$ (24)

Consequently, if $J_{\eta T}$ is nonexpansive, then for $\mathcal{G}_{\eta}$
defined by (1), we have

${\color[rgb]{0,0,0}\|\mathcal{G}_{\eta}x^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+8\gamma(5\gamma+2\rho)\|Fx^{0}+\xi^{0}\|^{2}}{\gamma^{2}(k+2)(k+4)}.}$
(25)

######  Remark 4.1 (Choice of $\gamma$).

If $8\sqrt{3}L\rho<1$, then
$\bar{\gamma}:=\frac{\sqrt{29-92L^{2}\rho^{2}}-74L\rho}{116L}>0$. In this
case, if we choose $\gamma\in(0,\bar{\gamma}]$, then the condition
$16L^{2}[3(3\gamma+2\rho)^{2}+\gamma(2\gamma+\rho)]\leq 1$ in Theorem 4.1
holds.

###### The proof of Theorem 4.1.

Similar to the proof of (13) in Theorem 3.1, using the last line of (APEG),
the definition (21) of $\hat{\mathcal{P}}_{k}$, and the update rules (23), we
can show that

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}-\hat{\mathcal{P}}_{k+1}&=&a_{k}\|w^{k-1}\|^{2}-a_{k+1}\|w^{k}\|^{2}+c_{k}\|w^{k-1}-\hat{w}^{k-1}\|^{2}-c_{k+1}\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}b_{k}\langle
w^{k}-w^{k-1},z^{k+1}-z^{k}\rangle+b_{k+1}\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},y^{k}-z^{k+1}\rangle.\end{array}$
(26)

By the $\rho$-co-hypomonotonicity of $F+T$, we have $\langle
w^{k}-w^{k-1},x^{k}-x^{k-1}\rangle\geq-\rho\|w^{k}-w^{k-1}\|^{2}$. Using this
expression and $z^{k+1}=x^{k}-\gamma\hat{w}^{k}=x^{k}-\gamma
w^{k}+\gamma(w^{k}-\hat{w}^{k})$ from the third line of (APEG) and both the
Cauchy-Schwarz and Young inequalities, we can derive that

$\begin{array}[]{lcl}\langle w^{k}-w^{k-1},z^{k+1}-z^{k}\rangle&=&\langle
w^{k}-w^{k-1},x^{k}-x^{k-1}\rangle-\gamma\langle
w^{k}-w^{k-1},\hat{w}^{k}-\hat{w}^{k-1}\rangle\vspace{1ex}\\\
&\geq&\gamma\langle
w^{k}-w^{k-1},(w^{k}-\hat{w}^{k})-(w^{k-1}-\hat{w}^{k-1})\rangle\vspace{1ex}\\\
&&-{~{}}(\gamma+\rho)\|w^{k}-w^{k-1}\|^{2}\vspace{1ex}\\\
&\geq&-\left(2\gamma+\rho\right)\|w^{k}-w^{k-1}\|^{2}-\frac{\gamma}{2}\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&-{~{}}\frac{\gamma}{2}\|w^{k-1}-\hat{w}^{k-1}\|^{2}.\end{array}$ (27)

Alternatively, from the second lines of (APEG), we have
$x^{k}=y^{k}-\eta\hat{w}^{k}+\hat{\eta}_{k}\hat{w}^{k-1}$. Combining this
expression and the third line of (APEG), we get
$y^{k}-z^{k+1}=(\gamma+\eta)\hat{w}^{k}-\hat{\eta}_{k}\hat{w}^{k-1}=\gamma
w^{k}+\eta\hat{w}^{k}-\hat{\eta}_{k}w^{k-1}+\gamma(\hat{w}^{k}-w^{k})-\hat{\eta}_{k}(\hat{w}^{k-1}-w^{k-1})$.
Utilizing this expression, and both the Cauchy-Schwarz and Young inequalities
again, for any $\beta>0$, we can show that

$\begin{array}[]{lcl}\mathcal{T}_{[3]}&:=&\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},y^{k}-z^{k+1}\rangle\vspace{1ex}\\\
&=&\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},\gamma
w^{k}+\eta\hat{w}^{k}-\hat{\eta}_{k}w^{k-1}\rangle\vspace{1ex}\\\
&&+{~{}}\langle\nu_{k}w^{k}-\theta_{k}w^{k-1},\gamma(\hat{w}^{k}-w^{k})-\hat{\eta}_{k}(\hat{w}^{k-1}-w^{k-1})\rangle\vspace{1ex}\\\
&\geq&\gamma\nu_{k}\|w^{k}\|^{2}+\hat{\eta}_{k}\theta_{k}\|w^{k-1}\|^{2}-(\hat{\eta}_{k}\nu_{k}+\gamma\theta_{k})\langle
w^{k},w^{k-1}\rangle\vspace{1ex}\\\
&&-{~{}}\eta\theta_{k}\langle\hat{w}^{k},w^{k-1}\rangle+\eta\nu_{k}\langle
w^{k},\hat{w}^{k}\rangle-\frac{\beta}{2\nu_{k}}\|\nu_{k}w^{k}-\theta_{k}w^{k-1}\|^{2}\vspace{1ex}\\\
&&-{~{}}\frac{\gamma^{2}\nu_{k}}{\beta}\|w^{k}-\hat{w}^{k}\|^{2}-\frac{\hat{\eta}_{k}^{2}\nu_{k}}{\beta}\|w^{k-1}-\hat{w}^{k-1}\|^{2}.\end{array}$
(28)

Further expanding (27) and (28), and then substituting their results into
(26), and using $b_{k+1}\theta_{k}=b_{k}$ from (12), we can derive

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}-\hat{\mathcal{P}}_{k+1}&\geq&\left[c_{k}-b_{k}\left(\frac{\gamma}{2}+\frac{\hat{\eta}_{k}^{2}\nu_{k}}{\beta\theta_{k}}\right)\right]\|w^{k-1}-\hat{w}^{k-1}\|^{2}\vspace{1ex}\\\
&&-{~{}}\left[c_{k+1}+b_{k}\left(\frac{\gamma}{2}+\frac{\gamma^{2}\nu_{k}}{\beta\theta_{k}}\right)\right]\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[a_{k}-b_{k}\left(2\gamma+\rho+\frac{\beta\theta_{k}}{2\nu_{k}}-\hat{\eta}_{k}\right)\right]\|w^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[b_{k}\left(\frac{(2\gamma-\beta)\nu_{k}}{2\theta_{k}}-2\gamma-\rho\right)-a_{k+1}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}b_{k}\left(3\gamma+2\rho+\beta-\frac{\nu_{k}\hat{\eta}_{k}}{\theta_{k}}\right)\langle
w^{k},w^{k-1}\rangle+\eta
b_{k}\langle\hat{w}^{k},w^{k}-w^{k-1}\rangle\vspace{1ex}\\\ &&+{~{}}\eta
b_{k}\left(\frac{\nu_{k}}{\theta_{k}}-1\right)\langle
w^{k},\hat{w}^{k}\rangle.\end{array}$ (29)

Next, by the Lipschitz continuity of $F$, $w^{k}-\hat{w}^{k}=Fx^{k}-Fy^{k}$,
and $y^{k}-x^{k}=\eta\hat{w}^{k}-\hat{\eta}_{k}\hat{w}^{k-1}$, we can show
that $\|w^{k}-\hat{w}^{k}\|^{2}=\|Fx^{k}-Fy^{k}\|^{2}\leq
L^{2}\|x^{k}-y^{k}\|^{2}=L^{2}\|\eta\hat{w}^{k}-\hat{\eta}_{k}\hat{w}^{k-1}\|^{2}$.
Therefore, for any $\omega>0$, using Young’s inequality, this expression leads
to
$0\geq\omega\|w^{k}-\hat{w}^{k}\|^{2}+\|w^{k}-\hat{w}^{k}\|^{2}-2(1+\omega)L^{2}\|\eta\hat{w}^{k}-\hat{\eta}_{k}w^{k-1}\|^{2}-2(1+\omega)L^{2}\hat{\eta}_{k}^{2}\|w^{k-1}-\hat{w}^{k-1}\|^{2}$.
Denoting $M:=2(1+\omega)L^{2}$ and expanding the last inequality, we get

$\begin{array}[]{lcl}0&\geq&\omega\|w^{k}-\hat{w}^{k}\|^{2}+\|w^{k}\|^{2}+(1-M\eta^{2})\|\hat{w}^{k}\|^{2}-2(1-M\eta\hat{\eta}_{k})\langle
w^{k},\hat{w}^{k}\rangle\vspace{1ex}\\\
&&-{~{}}2M\eta\hat{\eta}_{k}\langle\hat{w}^{k},w^{k}-w^{k-1}\rangle-M\hat{\eta}_{k}^{2}\|w^{k-1}\|^{2}-M\hat{\eta}_{k}^{2}\|w^{k-1}-\hat{w}^{k-1}\|^{2}.\end{array}$

Multiplying this inequality by $\frac{b_{k}}{2M\hat{\eta}_{k}}$ and adding the
result to (29), we obtain

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}-\hat{\mathcal{P}}_{k+1}&\geq&\left[c_{k}-b_{k}\left(\frac{\gamma}{2}+\frac{\hat{\eta}_{k}^{2}\nu_{k}}{\beta\theta_{k}}+\frac{\hat{\eta}_{k}}{2}\right)\right]\|w^{k-1}-\hat{w}^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[b_{k}\left(\frac{\omega}{2M\hat{\eta}_{k}}-\frac{\gamma}{2}-\frac{\gamma^{2}\nu_{k}}{\beta\theta_{k}}\right)-c_{k+1}\right]\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[a_{k}-b_{k}\left(2\gamma+\rho+\frac{\beta\theta_{k}}{2\nu_{k}}-\frac{\hat{\eta}_{k}}{2}\right)\right]\|w^{k-1}\|^{2}+\frac{(1-M\eta^{2})b_{k}}{2M\hat{\eta}_{k}}\|\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[b_{k}\left(\frac{1}{2M\hat{\eta}_{k}}+\frac{(2\gamma-\beta)\nu_{k}}{2\theta_{k}}-2\gamma-\rho\right)-a_{k+1}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}b_{k}\left(3\gamma+2\rho+\beta-\frac{\nu_{k}\hat{\eta}_{k}}{\theta_{k}}\right)\langle
w^{k},w^{k-1}\rangle-
b_{k}\left(\frac{1}{M\hat{\eta}_{k}}-\frac{\eta\nu_{k}}{\theta_{k}}\right)\langle
w^{k},\hat{w}^{k}\rangle.\end{array}$

Let us choose $\beta:=3\gamma+2\rho$, and $\eta:=2(3\gamma+2\rho)=2\beta$ and
$\hat{\eta}_{k}:=\frac{\eta\theta_{k}}{\nu_{k}}$. Then, we have
$3\gamma+2\rho+\beta-\frac{\nu_{k}\hat{\eta}_{k}}{\theta_{k}}=0$. In this
case, we can simplify the last expression as

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}-\hat{\mathcal{P}}_{k+1}&\geq&\left[c_{k}-\frac{b_{k}}{2}\big{(}\gamma+\frac{5\eta\theta_{k}}{\nu_{k}}\big{)}\right]\|w^{k-1}-\hat{w}^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[\frac{b_{k}}{2\theta_{k}}\big{(}\frac{(\omega-4M\gamma^{2})\nu_{k}}{M\eta}-\gamma\theta_{k}\big{)}-c_{k+1}\right]\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[a_{k}-b_{k}\big{(}2\gamma+\rho-\frac{\eta\theta_{k}}{4\nu_{k}}\big{)}\right]\|w^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{(1-M\eta^{2})b_{k}\nu_{k}}{2M\eta\theta_{k}}\left(\|\hat{w}^{k}\|^{2}-2\langle
w^{k},\hat{w}^{k}\rangle\right)\vspace{1ex}\\\
&&+{~{}}\left[b_{k}\big{(}\frac{\nu_{k}}{2M\eta\theta_{k}}+\frac{(4\gamma-\eta)\nu_{k}}{4\theta_{k}}-2\gamma-\rho\big{)}-a_{k+1}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&=&\left[c_{k}-\frac{b_{k}}{2}\big{(}\gamma+\frac{5\eta\theta_{k}}{\nu_{k}}\big{)}\right]\|w^{k-1}-\hat{w}^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[\frac{b_{k}}{2\theta_{k}}\big{(}\frac{(1+\omega-M\eta^{2}-4M\gamma^{2})\nu_{k}}{M\eta}-\gamma\theta_{k}\big{)}-c_{k+1}\right]\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[a_{k}-b_{k}\big{(}2\gamma+\rho-\frac{\eta\theta_{k}}{4\nu_{k}}\big{)}\right]\|w^{k-1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[b_{k}\big{(}\frac{(\eta+4\gamma)\nu_{k}}{4\theta_{k}}-2\gamma-\rho\big{)}-a_{k+1}\right]\|w^{k}\|^{2}.\end{array}$
(30)

Let us impose the following conditions on the parameters:

$\left\\{\begin{array}[]{lcl}1+\omega-M\eta^{2}&\geq&0,\vspace{1ex}\\\
a_{k}-b_{k}\big{(}2\gamma+\rho-\frac{\eta\theta_{k}}{4\nu_{k}}\big{)}&\geq&0,\vspace{1ex}\\\
b_{k}\left[\frac{(\eta+4\gamma)\nu_{k}}{4\theta_{k}}-2\gamma-\rho\right]-a_{k+1}&\geq&0,\vspace{1ex}\\\
c_{k}-\frac{b_{k}}{2}\big{(}\gamma+\frac{5\eta\theta_{k}}{\nu_{k}}\big{)}&\geq&0,\vspace{1ex}\\\
\frac{b_{k}}{2\theta_{k}}\left[\frac{(1+\omega-M\eta^{2}-4M\gamma^{2})\nu_{k}}{M\eta}-\gamma\theta_{k}\right]-c_{k+1}&\geq&0.\end{array}\right.$
(31)

Then, (30) reduces to $\hat{\mathcal{P}}_{k+1}\leq\hat{\mathcal{P}}_{k}$ for
all $k\geq 0$.

We still update $b_{k}=\frac{b_{0}(k+1)(k+2)}{2}$ as in (AEG), which leads to
$b_{k+1}=\frac{b_{k}}{\theta_{k}}=\frac{b_{k}t_{k+1}}{t_{k}-1}$ by (23). Our
next step is to show that the parameters updated by (23) guarantee the five
conditions of (31). First, let us choose
$a_{k}:=b_{k}\left(2\gamma+\rho-\frac{\eta\theta_{k}}{4\nu_{k}}\right)=\frac{b_{k}(2\gamma
t_{k}+\eta)}{4t_{k}}=\frac{b_{0}(k+1)(\gamma k+5\gamma+2\rho)}{4}$. Then, the
second condition of (31) is automatically satisfied. Since
$b_{k+1}=\frac{b_{k}t_{k+1}}{t_{k}-1}$ and $t_{k+1}=t_{k}+1$ by (23), the
choice of $a_{k+1}=\frac{b_{0}(k+2)(\gamma k+6\gamma+2\rho)}{4}$ also
guarantees the third condition of (31).

If we choose
$c_{k}:=\frac{b_{k}}{2}\big{(}\gamma+\frac{5\eta\theta_{k}}{\nu_{k}}\big{)}=\frac{b_{0}(k+1)[(31\gamma+20\rho)(k+1)+\gamma]}{4}$,
then the fourth condition of (31) is obviously satisfied with an equality. The
last condition of (31) holds if $M(6\eta^{2}+2\gamma\eta+4\gamma^{2})\leq
1+\omega$. Using $\eta=2(3\gamma+2\rho)$ and $M=2(1+\omega)L^{2}$ for any
$\omega>0$, the last condition is equivalent to

$8L^{2}[6(3\gamma+2\rho)^{2}+\gamma(3\gamma+2\rho)+\gamma^{2}]\leq 1.$

This condition is exactly equivalent to
$16L^{2}[3(3\gamma+2\rho)^{2}+\gamma(2\gamma+\rho)]\leq 1$ in Theorem 4.1.
Moreover, it also guarantee that $2L^{2}\eta^{2}\leq 1$, which shows that the
first condition of (31) holds.

Using the parameters in (23), $a_{k}$, $b_{k}$, and $c_{k}$ above, and (22),
we can show that

$\begin{array}[]{lcl}\hat{\mathcal{P}}_{k}&\geq&\left(a_{k}-\frac{b_{k}^{2}}{4t_{k}^{2}}-\frac{(3\gamma+2\rho)b_{k}}{2t_{k}}\right)\|w^{k-1}\|^{2}+\left(c_{k}-\frac{\gamma
b_{k}}{2t_{k}}\right)\|w^{k-1}-\hat{w}^{k-1}\|^{2}\vspace{1ex}\\\
&=&\frac{b_{0}(k+1)[(4\gamma-
b_{0})(k+1)+4\gamma]}{16}\|w^{k-1}\|^{2}+\frac{(31\gamma+20\rho)b_{0}(k+1)^{2}}{4}\|w^{k-1}-\hat{w}^{k-1}\|^{2}.\end{array}$

Let us choose $b_{0}:=2\gamma$. Then, we have
$\hat{\mathcal{P}}_{k}\geq\frac{\gamma^{2}(k+1)(k+3)}{4}\|w^{k-1}\|^{2}$.
Since
$\hat{\mathcal{P}}_{k}\leq\hat{\mathcal{P}}_{0}=a_{0}\|w^{-1}\|^{2}+b_{0}\langle
w^{-1},z^{0}-y^{0}\rangle+\|z^{0}+t_{0}(y^{0}-z^{0})-x^{\star}\|^{2}+c_{0}\|w^{-1}-\hat{w}^{-1}\|^{2}$,
and $y^{0}=z^{0}=x^{0}$ and $w^{-1}=\hat{w}^{-1}$, we get
$\hat{\mathcal{P}}_{k}\leq\hat{\mathcal{P}}_{0}=a_{0}\|w^{-1}\|^{2}+\|x^{0}-x^{\star}\|^{2}=2\gamma(5\gamma+2\rho)\|w^{0}\|^{2}+\|x^{0}-x^{\star}\|^{2}$
since $w^{-1}=2w^{0}$. Combining these derivations, we finally get
$\|w^{k-1}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+8\gamma(5\gamma+2\rho)\|w^{0}\|^{2}}{\gamma^{2}(k+1)(k+3)}$,
which implies (24). If $J_{\eta T}$ is nonexpansive, then using
$\|\mathcal{G}_{\eta}x^{k}\|\leq\|w^{k}\|$ from Lemma 3.1, we obtain (25).
$\square$∎

##  5 The Extra-Anchored Gradient-Type Methods for Solving (chMI)

In this section, we provide an alternative convergence analysis for Halpern’s
fixed-point-type variants of (FBFS) and its past FBFS scheme, which is called
EAG (extra-anchored gradient) method [40, 79] and PEAG (past extra-anchored
gradient) method in [75], respectively, where their names are stemmed from
[79]. These schemes have been extended to (chMI) in [13] and [14],
respectively. Our algorithmic derivation as well as our analysis can be viewed
as direct extensions of the results in [40, 75, 79]. Moreover, together with
the new analysis, our PEAG is significantly different from that of [14] since
we replace $Fx^{k}$ by $Fy^{k-1}$ instead of replacing $Fy^{k}$ by $Fx^{k-1}$
as often seen in past extragradient-type methods.

###  5.1 The extra-anchored gradient method for solving (chMI)

We first derive a variant of the extra-anchored gradient method (EAG) from
[40, 79] to solve (chMI). We call this method (EAG) as in [79], which can be
described as follows: Starting from $x^{0}\in\mathbb{R}^{p}$, at each
iteration $k\geq 0$, we update

$\left\\{\begin{array}[]{lcl}y^{k}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-(\hat{\eta}_{k}-2\rho(1-\tau_{k}))(Fx^{k}+\xi^{k}),\vspace{1ex}\\\
x^{k+1}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-\eta(Fy^{k}+\xi^{k+1})+2\rho(1-\tau_{k})(Fx^{k}+\xi^{k}),\end{array}\right.$
(EAG)

where $\xi^{k}\in Tx^{k}$, $\tau_{k}\in(0,1)$, $\eta>0$, and
$\hat{\eta}_{k}>0$ are determined later.

This variant was studied in [13]. However, if $T=0$, then (EAG) reduces to the
EAG variant in [40]. We introduce the following quantities to simplify our
analysis:

$w^{k}:=Fx^{k}+\xi^{k}\in
Fx^{k}+Tx^{k}\quad\text{and}\quad\hat{w}^{k}:=Fy^{k-1}+\xi^{k}.$ (32)

Then, we can rewrite (EAG) as follows:

$\left\\{\begin{array}[]{lcl}y^{k}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-(\hat{\eta}_{k}-2\rho(1-\tau_{k}))w^{k},\vspace{1ex}\\\
x^{k+1}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-\eta\hat{w}^{k+1}+2\rho(1-\tau_{k})w^{k}.\end{array}\right.$
(33)

The interpretation (33) looks very similar to the fast extragradient scheme in
[40] for root-finding problem (chME), where $w^{k}$ and $\hat{w}^{k+1}$ play
the roles of $Fx^{k}$ and $Fy^{k}$, respectively in [40].

Since $x^{k+1}$ appears on both sides of the second line of (33), we will use
the resolvent $J_{\eta T}$ to rewrite it as follows:

$\left\\{\begin{array}[]{lcl}y^{k}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-(\hat{\eta}_{k}-2\rho(1-\tau_{k}))(Fx^{k}+\xi^{k}),\vspace{1ex}\\\
x^{k+1}&:=&J_{\eta T}\big{(}y^{k}-\eta
Fy^{k}+\hat{\eta}_{k}(Fx^{k}+\xi^{k})\big{)},\vspace{1ex}\\\
\xi^{k+1}&:=&\frac{1}{\eta}\big{(}y^{k}-x^{k+1}-\eta
Fy^{k}+\hat{\eta}_{k}(Fx^{k}+\xi^{k})\big{)},\end{array}\right.$ (34)

where $\tau_{k}\in(0,1)$ and $\xi^{0}\in Tx^{0}$ is arbitrary.

To establish convergence of (EAG), we use the following Lyapunov function:

$\mathcal{V}_{k}:=a_{k}\|w^{k}\|^{2}+b_{k}\langle w^{k},x^{k}-x^{0}\rangle,$
(35)

where $a_{k}>0$ and $b_{k}>0$ are given parameters. This function is similar
to the one in [40, 79] and is the same as the one in [13]. The following
theorem states the convergence of (EAG).

######  Theorem 5.1.

Assume that $F+T$ in (chMI) is $\rho$-co-hypomonotone, $F$ is $L$-Lipschitz
continuous such that $2L\rho<1$, and $\mathrm{zer}(F+T)\neq\emptyset$. Let
$\\{(x^{k},y^{k})\\}$ be generated by (EAG) using

$\tau_{k}:=\frac{1}{k+2},\quad\eta\in\left(2\rho,\frac{1}{L}\right],\quad\text{and}\quad\hat{\eta}_{k}:=(1-\tau_{k})\eta.$
(36)

Then, for all $k\geq 0$ and any $x^{\star}\in\mathrm{zer}(F+T)$, the following
result holds:

$\|Fx^{k}+\xi^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+2\eta(\eta-2\rho)\|Fx^{0}+\xi^{0}\|^{2}}{(\eta-2\rho)^{2}(k+1)^{2}},\quad\text{where}\quad\xi^{k}\in
Tx^{k}.$ (37)

Consequently, if $J_{\eta T}$ is nonexpansive, then for $\mathcal{G}_{\eta}$
defined by (1), we have

${\color[rgb]{0,0,0}\|\mathcal{G}_{\eta}x^{k}\|^{2}\leq\frac{4\|x^{0}-x^{\star}\|^{2}+2\eta(\eta-2\rho)\|Fx^{0}+\xi^{0}\|^{2}}{(\eta-2\rho)^{2}(k+1)^{2}}.}$
(38)

###### Proof.

Since (EAG) is equivalent to (33), from the second line of (EAG), we have

$\left\\{\begin{array}[]{lcl}x^{k+1}-x^{k}&=&-\tau_{k}(x^{k}-x^{0})-\eta\hat{w}^{k+1}+2\rho(1-\tau_{k})w^{k}\vspace{1ex}\\\
x^{k+1}-x^{k}&=&-\tfrac{\tau_{k}}{1-\tau_{k}}(x^{k+1}-x^{0})-\tfrac{\eta}{1-\tau_{k}}\hat{w}^{k+1}+2\rho
w^{k}.\end{array}\right.$ (39)

Next, since $F+T$ is $\rho$-co-hypomonotone and $w^{k}\in Fx^{k}+Tx^{k}$, we
have $\langle w^{k+1}-w^{k},x^{k+1}-x^{k}\rangle+\rho\|w^{k+1}-w^{k}\|^{2}\geq
0$. This relation leads to

$\begin{array}[]{lcl}0&\leq&\langle w^{k+1},x^{k+1}-x^{k}\rangle-\langle
w^{k},x^{k+1}-x^{k}\rangle+\rho\|w^{k+1}-w^{k}\|^{2}\vspace{1ex}\\\
&\overset{\tiny\eqref{eq:EAG_proof1}}{=}&\tau_{k}\langle
w^{k},x^{k}-x^{0}\rangle-\frac{\tau_{k}}{1-\tau_{k}}\langle
w^{k+1},x^{k+1}-x^{0}\rangle+\eta\langle
w^{k},\hat{w}^{k+1}\rangle-2\rho(1-\tau_{k})\|w^{k}\|^{2}\vspace{1ex}\\\
&&-{~{}}\frac{\eta}{1-\tau_{k}}\langle
w^{k+1},\hat{w}^{k+1}\rangle+2\rho\langle
w^{k+1},w^{k}\rangle+\rho\|w^{k+1}-w^{k}\|^{2}.\end{array}$

Multiplying this expression by $\frac{b_{k}}{\tau_{k}}$, rearranging the
result, and using $b_{k+1}=\frac{b_{k}}{1-\tau_{k}}$, we obtain the following
expression

$\begin{array}[]{lcl}\mathcal{T}_{[1]}&:=&b_{k}\langle
w^{k},x^{k}-x^{0}\rangle-b_{k+1}\langle
w^{k+1},x^{k+1}-x^{0}\rangle\vspace{1ex}\\\ &\geq&\frac{\eta
b_{k+1}}{\tau_{k}}\langle w^{k+1}-w^{k},\hat{w}^{k+1}\rangle+\eta
b_{k+1}\langle\hat{w}^{k+1},w^{k}\rangle-\frac{\rho
b_{k}}{\tau_{k}}\|w^{k+1}\|^{2}+\frac{\rho
b_{k}(1-2\tau_{k})}{\tau_{k}}\|w^{k}\|^{2}.\end{array}$

Adding $a_{k}\|w^{k}\|^{2}-a_{k+1}\|w^{k+1}\|^{2}$ to $\mathcal{T}_{[1]}$ and
using $\mathcal{V}_{k}$ from (35), we can show that

$\begin{array}[]{lcl}\mathcal{V}_{k}-\mathcal{V}_{k+1}&=&a_{k}\|w^{k}\|^{2}-a_{k+1}\|w^{k+1}\|^{2}+b_{k}\langle
w^{k},x^{k}-x^{0}\rangle-b_{k+1}\langle
w^{k+1},x^{k+1}-x^{0}\rangle\vspace{1ex}\\\ &\geq&\big{(}a_{k}+\frac{\rho
b_{k}(1-2\tau_{k})}{\tau_{k}}\big{)}\|w^{k}\|^{2}-\big{(}a_{k+1}+\frac{\rho
b_{k}}{\tau_{k}}\big{)}\|w^{k+1}\|^{2}\vspace{1ex}\\\ &&+{~{}}\frac{\eta
b_{k+1}}{\tau_{k}}\langle w^{k+1}-w^{k},\hat{w}^{k+1}\rangle+\eta
b_{k+1}\langle\hat{w}^{k+1},w^{k}\rangle.\end{array}$ (40)

Next, from (33), we have
$x^{k+1}-y^{k}=-\eta\hat{w}^{k+1}+\hat{\eta}_{k}w^{k}$. By the $L$-Lipschitz
continuity of $F$, we have
$\|w^{k+1}-\hat{w}^{k+1}\|^{2}=\|Fx^{k+1}-Fy^{k}\|^{2}\leq
L^{2}\|x^{k+1}-y^{k}\|^{2}=L^{2}\|\eta\hat{w}^{k+1}-\hat{\eta}_{k}w^{k}\|^{2}$.
Expanding this inequality and rearranging the result, we get

$\begin{array}[]{lcl}0&\geq&\|w^{k+1}\|^{2}+(1-L^{2}\eta^{2})\|\hat{w}^{k+1}\|^{2}-2\langle
w^{k+1}-w^{k},\hat{w}^{k+1}\rangle\vspace{1ex}\\\
&&-{~{}}2\big{(}1-L^{2}\eta\hat{\eta}_{k})\langle\hat{w}^{k+1},w^{k}\rangle-L^{2}\hat{\eta}_{k}^{2}\|w^{k}\|^{2}.\end{array}$

Multiplying this inequality by $\frac{\eta b_{k+1}}{2\tau_{k}}$ and adding the
result to (40), we get

$\begin{array}[]{lcl}\mathcal{V}_{k}-\mathcal{V}_{k+1}&\geq&\left(a_{k}-\frac{L^{2}\eta\hat{\eta}_{k}^{2}b_{k+1}-2\rho
b_{k}(1-2\tau_{k})}{2\tau_{k}}\right)\|w^{k}\|^{2}+\left(\frac{\eta
b_{k+1}-2\rho b_{k}}{2\tau_{k}}-a_{k+1}\right)\|w^{k+1}\|^{2}\vspace{2ex}\\\
&&+{~{}}\frac{\eta(1-L^{2}\eta^{2})b_{k+1}}{2\tau_{k}}\|\hat{w}^{k+1}\|^{2}-\frac{\eta(1-\tau_{k}-L^{2}\eta\hat{\eta}_{k})b_{k+1}}{\tau_{k}}\langle\hat{w}^{k+1},w^{k}\rangle.\end{array}$
(41)

Let us choose $\tau_{k}:=\frac{1}{k+2}$ and $\hat{\eta}_{k}:=(1-\tau_{k})\eta$
as in (36). We also choose
$a_{k+1}:=\frac{b_{k+1}[\eta-2\rho(1-\tau_{k})]}{2\tau_{k}}=\frac{[(\eta-2\rho)(k+2)+2\rho]b_{k+1}}{2}$
provided that $\eta>2\rho$. By the update of $b_{k}$ as
$b_{k+1}=\frac{b_{k}}{1-\tau_{k}}$, we can easily show that $b_{k}=b_{0}(k+1)$
for $k\geq 0$. Therefore, we get
$a_{k}=\frac{b_{0}[(\eta-2\rho)(k+1)+2\rho](k+1)}{2}$.

Using these parameters and assuming that $L\eta\leq 1$, we can simplify (41)
as

$\begin{array}[]{lcl}\mathcal{V}_{k}-\mathcal{V}_{k+1}&\geq&\frac{\eta(1-L^{2}\eta^{2})b_{k+1}}{2\tau_{k}}\|\hat{w}^{k+1}-(1-\tau_{k})w^{k}\|^{2}\geq
0.\end{array}$ (42)

Finally, since $0\in Fx^{\star}+Tx^{\star}$, we have $\langle
w^{k},x^{k}-x^{\star}\rangle\geq-\rho\|w^{k}\|^{2}$. Using this inequality,
the definition of $\mathcal{V}_{k}$, and Young’s inequality, we can show that

$\begin{array}[]{lcl}\mathcal{V}_{k}&=&a_{k}\|w^{k}\|^{2}+b_{k}\langle
w^{k},x^{\star}-x^{0}\rangle+b_{k}\langle
w^{k},x^{k}-x^{\star}\rangle\vspace{1ex}\\\ &\geq&(a_{k}-\rho
b_{k})\|w^{k}\|^{2}-b_{k}\|w^{k}\|\|x^{0}-x^{\star}\|\vspace{1ex}\\\
&\geq&\left(a_{k}-\rho
b_{k}-\frac{(\eta-2\rho)b_{k}^{2}}{4b_{0}}\right)\|w^{k}\|^{2}-\frac{b_{0}}{\eta-2\rho}\|x^{0}-x^{\star}\|^{2}\vspace{1ex}\\\
&=&\frac{b_{0}(\eta-2\rho)(k+1)^{2}}{4}\|w^{k}\|^{2}-\frac{b_{0}}{\eta-2\rho}\|x^{0}-x^{\star}\|^{2}.\end{array}$

Moreover, we also have $\mathcal{V}_{0}=a_{0}\|w^{0}\|^{2}+b_{0}\langle
w^{0},x^{0}-x^{0}\rangle=\frac{\eta b_{0}}{2}\|w^{0}\|^{2}$. Combining all
these derivations and using (42) to get
$\mathcal{V}_{k}\leq\mathcal{V}_{0}=\frac{\eta b_{0}}{2}\|w^{0}\|^{2}$, we
obtain (37). The conditions $\eta>2\rho$ and $L\eta\leq 1$ imply that
$2\rho<\eta\leq\frac{1}{L}$, which is satisfied if $2L\rho<1$. The bound (38)
is a consequence of (37) and
$\|\mathcal{G}_{\eta}x^{k}\|\leq\|Fx^{k}+\xi^{k}\|$ in Lemma 3.1. $\square$∎

Clearly, the condition on $L$ and $\rho$, and the convergence rate bounds (9)
and (37) of (AEG) are similar to the ones in (EAG), respectively. As shown in
[40] for the case $T=0$, these convergence rates are tight.

###  5.2 The past extra-anchored gradient method for solving (chMI)

We now develop a variant of the past extra-anchored gradient method (PEAG)
from [75] to solve (chMI). We still call this method (PEAG) and it is
presented as follows: Starting from $x^{0}\in\mathbb{R}^{p}$, we set
$y^{-1}:=x^{0}$, and for $k\geq 0$ we update

$\left\\{\begin{array}[]{lcl}y^{k}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-(\hat{\eta}_{k}-\beta_{k})(Fy^{k-1}+\xi^{k}),\vspace{1ex}\\\
x^{k+1}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-\eta(Fy^{k}+\xi^{k+1})+\beta_{k}(Fy^{k-1}+\xi^{k}),\end{array}\right.$
(PEAG)

where $\xi^{k}\in Tx^{k}$ is an arbitrary element of $Tx^{k}$,
$\tau_{k}\in(0,1)$, $\eta>0$, $\hat{\eta}_{k}>0$, and $\beta_{k}>0$ are given
parameters, which will be determined later.

Note that if $T=0$, then (PEAG) reduces to the past extra-anchored gradient
scheme in [75]. This scheme can be considered as a modification of (EAG) by
replacing $Fx^{k}$ by $Fy^{k-1}$ using Popov’s idea in [65]. However, it is
different from (PFBFS) as we do not replace $Fy^{k}$ by $Fx^{k-1}$. Compared
to [14], since their method is rooted from the reflected gradient method in
[50], it is also different from (PEAG) though both methods have the same per-
iteration complexity and convergence rate. Moreover, our condition
$2\sqrt{34}L\rho<1$ in Theorem 5.2 below is better than $12\sqrt{3}L\rho<1$ in
[14]. Our proof below is also different from [14], where we follow the proof
technique in [75].

Let us rewrite (PEAG) into a different form. We introduce
$w^{k}:=Fx^{k}+\xi^{k}\in Fx^{k}+Tx^{k}$ and $\hat{w}^{k}:=Fy^{k-1}+\xi^{k}$
as in (EAG). Then, we can rewrite (PEAG) as

$\left\\{\begin{array}[]{lcl}y^{k}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-(\hat{\eta}_{k}-\beta_{k})\hat{w}^{k},\vspace{1ex}\\\
x^{k+1}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-\eta\hat{w}^{k+1}+\beta_{k}\hat{w}^{k}.\end{array}\right.$
(43)

This scheme has the same form as [75] but with different parameters, where
$\hat{w}^{k}$ plays the same role as $Fy^{k}$ in [75].

Note that the second line of (PEAG) is an implicit update since $x^{k+1}$ is
also in $\xi^{k+1}\in Tx^{k+1}$ on the right-hand side of this line. To
resolve this implicit issue, we rewrite it as follows:

$\left\\{\begin{array}[]{lcl}y^{k}&:=&x^{k}+\tau_{k}(x^{0}-x^{k})-(\hat{\eta}_{k}-\beta_{k})\hat{w}^{k},\vspace{1ex}\\\
x^{k+1}&:=&J_{\eta T}\big{(}y^{k}-\eta
Fy^{k}+\hat{\eta}_{k}\hat{w}^{k}\big{)},\vspace{1ex}\\\
\hat{w}^{k+1}&:=&\frac{1}{\eta}\big{(}y^{k}-x^{k+1}+\hat{\eta}_{k}\hat{w}^{k}\big{)},\end{array}\right.$
(44)

where $x^{0}\in\mathbb{R}^{p}$ is given, $y^{-1}:=x^{0}$, and
$\hat{w}^{0}:=w^{0}\in Fx^{0}+Tx^{0}$ is arbitrary.

To establish convergence of (PEAG), we use the following Lyapunov function:

$\hat{\mathcal{V}}_{k}:=a_{k}\|w^{k}\|^{2}+b_{k}\langle
w^{k},x^{k}-x^{0}\rangle+c_{k}\|w^{k}-\hat{w}^{k}\|^{2},$ (45)

where $w^{k}:=\hat{w}^{k}+Fx^{k}-Fy^{k-1}=Fx^{k}+\xi^{k}$, $a_{k}>0$,
$b_{k}>0$, and $c_{k}>0$ are given parameters. Then, the following theorem
states the convergence rate of (PEAG).

######  Theorem 5.2.

Assume that $F+T$ in (chMI) is $\rho$-co-hypomonotone, $F$ is $L$-Lipschitz
continuous such that $2\sqrt{34}L\rho<1$, and
$\mathrm{zer}(F+T)\neq\emptyset$. Let $\eta:=\frac{1}{L}\sqrt{\frac{2}{17}}$
be a given stepsize, and $\\{(x^{k},y^{k})\\}$ be generated by (PEAG) using
the following parameters:

$\tau_{k}:=\frac{1}{k+2},\quad\beta_{k}:=\frac{4\rho(1-\tau_{k})}{1+\tau_{k}},\quad\text{and}\quad\hat{\eta}_{k}:=(1-\tau_{k})\eta.$
(46)

Then, for all $k\geq 0$ and any $x^{\star}\in\mathrm{zer}(F+T)$, we have

$\|Fx^{k}+\xi^{k}\|^{2}\leq\frac{1}{(k+1)^{2}}\left[\frac{4}{(\eta-4\rho)^{2}}\|x^{0}-x^{\star}\|^{2}+\frac{2(3\eta-2\rho)}{3(\eta-4\rho)}\|Fx^{0}+\xi^{0}\|^{2}\right],$
(47)

where $\xi^{k}\in Tx^{k}$ and $\xi^{0}\in Tx^{0}$.

Consequently, if $J_{\eta T}$ is nonexpansive, then for $\mathcal{G}_{\eta}$
defined by (1), we have

${\color[rgb]{0,0,0}\|\mathcal{G}_{\eta}x^{k}\|^{2}\leq\frac{1}{(k+1)^{2}}\Big{[}\frac{4}{(\eta-4\rho)^{2}}\|x^{0}-x^{\star}\|^{2}+\frac{2(3\eta-2\rho)}{3(\eta-4\rho)}\|Fx^{0}+\xi^{0}\|^{2}\Big{]}.}$
(48)

###### Proof.

Since (PEAG) is equivalent to (43), from (43), we can easily show that

$\left\\{\begin{array}[]{lcl}x^{k+1}-x^{k}&=&-\tau_{k}(x^{k}-x^{0})-\eta\hat{w}^{k+1}+\beta_{k}w^{k}+\beta_{k}(\hat{w}^{k}-w^{k})\vspace{1ex}\\\
x^{k+1}-x^{k}&=&-\tfrac{\tau_{k}}{1-\tau_{k}}(x^{k+1}-x^{0})-\tfrac{\eta}{1-\tau_{k}}\hat{w}^{k+1}+\frac{\beta_{k}}{1-\tau_{k}}w^{k}+\frac{\beta_{k}}{1-\tau_{k}}(\hat{w}^{k}-w^{k}).\end{array}\right.$
(49)

Next, since $F+T$ is $\rho$-co-hypomonotone and $w^{k}=Fx^{k}+\xi^{k}\in
Fx^{k}+Tx^{k}$, we have $\langle
w^{k+1}-w^{k},x^{k+1}-x^{k}\rangle+\rho\|w^{k+1}-w^{k}\|^{2}\geq 0$. Using
(49) into this inequality, we can expand it as

$\begin{array}[]{lcl}\mathcal{T}_{[1]}&:=&\tau_{k}\langle
w^{k},x^{k}-x^{0}\rangle-\frac{\tau_{k}}{1-\tau_{k}}\langle
w^{k+1},x^{k+1}-x^{0}\rangle\vspace{1ex}\\\
&\geq&\frac{\eta}{1-\tau_{k}}\langle w^{k+1},\hat{w}^{k+1}\rangle-\eta\langle
w^{k},\hat{w}^{k+1}\rangle-\rho\|w^{k+1}-w^{k}\|^{2}+\beta_{k}\|w^{k}\|^{2}\vspace{1ex}\\\
&&-{~{}}\frac{\beta_{k}}{1-\tau_{k}}\langle
w^{k+1},w^{k}\rangle-\frac{\beta_{k}}{1-\tau_{k}}\langle
w^{k+1}-(1-\tau_{k})w^{k},\hat{w}^{k}-w^{k}\rangle.\end{array}$

Using Young’s inequality and choosing
$\beta_{k}:=\frac{4\rho(1-\tau_{k})}{1+\tau_{k}}$, we can further derive

$\begin{array}[]{lcl}\mathcal{T}_{[1]}&:=&\tau_{k}\langle
w^{k},x^{k}-x^{0}\rangle-\frac{\tau_{k}}{1-\tau_{k}}\langle
w^{k+1},x^{k+1}-x^{0}\rangle\vspace{1ex}\\\
&\geq&\frac{\eta}{1-\tau_{k}}\langle w^{k+1},\hat{w}^{k+1}\rangle-\eta\langle
w^{k},\hat{w}^{k+1}\rangle-\rho\|w^{k+1}-w^{k}\|^{2}+\beta_{k}\|w^{k}\|^{2}\vspace{1ex}\\\
&&-{~{}}\frac{\beta_{k}}{1-\tau_{k}}\langle
w^{k+1},w^{k}\rangle-\frac{\beta_{k}}{4(1-\tau_{k})}\|w^{k+1}-(1-\tau_{k})w^{k}\|^{2}-\frac{\beta_{k}}{1-\tau_{k}}\|\hat{w}^{k}-w^{k}\|^{2}\vspace{1ex}\\\
&=&\frac{\eta}{1-\tau_{k}}\langle w^{k+1},\hat{w}^{k+1}\rangle-\eta\langle
w^{k},\hat{w}^{k+1}\rangle-\left[\frac{(1+\tau_{k})\beta_{k}}{2(1-\tau_{k})}-2\rho\right]\langle
w^{k+1},w^{k}\rangle\vspace{1ex}\\\
&&-{~{}}\left[\frac{\beta_{k}}{4(1-\tau_{k})}+\rho\right]\|w^{k+1}\|^{2}+\left[\beta_{k}-\frac{\beta_{k}(1-\tau_{k})}{4}-\rho\right]\|w^{k}\|^{2}-\frac{\beta_{k}}{1-\tau_{k}}\|\hat{w}^{k}-w^{k}\|^{2}\vspace{1ex}\\\
&=&\frac{\eta}{1-\tau_{k}}\langle w^{k+1},\hat{w}^{k+1}\rangle-\eta\langle
w^{k},\hat{w}^{k+1}\rangle-\frac{\rho(2+\tau_{k})}{1+\tau_{k}}\|w^{k+1}\|^{2}+\frac{\rho(2-3\tau_{k}-\tau_{k}^{2})}{1+\tau_{k}}\|w^{k}\|^{2}\vspace{1ex}\\\
&&-{~{}}\frac{4\rho}{1+\tau_{k}}\|\hat{w}^{k}-w^{k}\|^{2}.\end{array}$

Multiplying $\mathcal{T}_{[1]}$ by $\frac{b_{k}}{\tau_{k}}$, rearranging the
result, and using $b_{k+1}=\frac{b_{k}}{1-\tau_{k}}$, we can show that

$\begin{array}[]{lcl}\hat{\mathcal{T}}_{[1]}&:=&b_{k}\langle
w^{k},x^{k}-x^{0}\rangle-b_{k+1}\langle
w^{k+1},x^{k+1}-x^{0}\rangle\vspace{1ex}\\\
&\geq&\frac{b_{k+1}\eta}{\tau_{k}}\langle
w^{k+1}-w^{k},\hat{w}^{k+1}\rangle+b_{k+1}\eta\langle
w^{k},\hat{w}^{k+1}\rangle-\frac{\rho
b_{k}(2+\tau_{k})}{\tau_{k}(1+\tau_{k})}\|w^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{\rho
b_{k}(2-3\tau_{k}-\tau_{k}^{2})}{\tau_{k}(1+\tau_{k})}\|w^{k}\|^{2}-\frac{4\rho
b_{k}}{\tau_{k}(1+\tau_{k})}\|\hat{w}^{k}-w^{k}\|^{2}.\end{array}$

Adding
$a_{k}\|w^{k}\|^{2}-a_{k+1}\|w^{k+1}\|^{2}+c_{k}\|w^{k}-\hat{w}^{k}\|^{2}-c_{k+1}\|w^{k+1}-\hat{w}^{k+1}\|^{2}$
to both sides of $\hat{\mathcal{T}}_{[1]}$, then using $\hat{\mathcal{V}}_{k}$
defined by (45), we can show that

$\begin{array}[]{lcl}\hat{\mathcal{V}}_{k}-\hat{\mathcal{V}}_{k+1}&\geq&\left[a_{k}+\frac{\rho
b_{k}(2-3\tau_{k}-\tau_{k}^{2})}{\tau_{k}(1+\tau_{k})}\right]\|w^{k}\|^{2}-\left[a_{k+1}+\frac{\rho
b_{k}(2+\tau_{k})}{\tau_{k}(1+\tau_{k})}\right]\|w^{k+1}\|^{2}\vspace{1ex}\\\
&&+\left[c_{k}-\frac{4\rho
b_{k}}{\tau_{k}(1+\tau_{k})}\right]\|w^{k}-\hat{w}^{k}\|^{2}-c_{k+1}\|w^{k+1}-\hat{w}^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{\eta b_{k+1}}{\tau_{k}}\langle
w^{k+1}-w^{k},\hat{w}^{k+1}\rangle+\eta
b_{k+1}\langle\hat{w}^{k+1},w^{k}\rangle.\end{array}$ (50)

Now, from (43), we have
$x^{k+1}-y^{k}=-\eta\hat{w}^{k+1}+\hat{\eta}_{k}\hat{w}^{k}$. Therefore, using
the $L$-Lipschitz continuity of $F$ and Young’s inequality, we can show that

$\begin{array}[]{lcl}\|w^{k+1}-\hat{w}^{k+1}\|^{2}&=&\|Fx^{k+1}-Fy^{k}\|^{2}\leq
L^{2}\|x^{k+1}-y^{k}\|^{2}=L^{2}\|\eta\hat{w}^{k+1}-\hat{\eta}_{k}\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&\leq&2L^{2}\|\eta\hat{w}^{k+1}-\hat{\eta}_{k}w^{k}\|^{2}+2L^{2}\hat{\eta}_{k}^{2}\|w^{k}-\hat{w}^{k}\|^{2}.\end{array}$

Multiplying this inequality by $(1+\omega)$ for some $\omega>0$, defining
$M:=2(1+\omega)L^{2}$, and expanding and rearranging the result, we obtain

$\begin{array}[]{lcl}0&\geq&\omega\|w^{k+1}-\hat{w}^{k+1}\|^{2}+\|w^{k+1}\|^{2}+(1-M\eta^{2})\|\hat{w}^{k+1}\|^{2}-2\langle
w^{k+1}-w^{k},\hat{w}^{k+1}\rangle\vspace{1ex}\\\
&&-{~{}}2(1-M\eta\hat{\eta}_{k})\langle\hat{w}^{k+1},w^{k}\rangle-M\hat{\eta}_{k}^{2}\|w^{k}\|^{2}-M\hat{\eta}_{k}^{2}\|w^{k}-\hat{w}^{k}\|^{2}.\end{array}$

Multiplying this inequality by $\frac{\eta b_{k+1}}{2\tau_{k}}$ and adding the
result to (50), we get

$\begin{array}[]{lcl}\hat{\mathcal{V}}_{k}-\hat{\mathcal{V}}_{k+1}&\geq&\left[c_{k}-\frac{4\rho
b_{k}}{\tau_{k}(1+\tau_{k})}-\frac{Mb_{k+1}\eta\hat{\eta}_{k}^{2}}{2\tau_{k}}\right]\|w^{k}-\hat{w}^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left(\frac{\omega\eta
b_{k+1}}{2\tau_{k}}-c_{k+1}\right)\|w^{k+1}-\hat{w}^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[a_{k}+\frac{\rho
b_{k}(2-3\tau_{k}-\tau_{k}^{2})}{\tau_{k}(1+\tau_{k})}-\frac{Mb_{k+1}\eta\hat{\eta}_{k}^{2}}{2\tau_{k}}\right]\|w^{k}\|^{2}\vspace{1ex}\\\
&&+{~{}}\left[\frac{\eta b_{k+1}}{2\tau_{k}}-\frac{\rho
b_{k}(2+\tau_{k})}{\tau_{k}(1+\tau_{k})}-a_{k+1}\right]\|w^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{\eta(1-M\eta^{2})b_{k+1}}{2\tau_{k}}\|\hat{w}^{k+1}\|^{2}-\frac{\eta\left(1-\tau_{k}-M\eta\hat{\eta}_{k}\right)b_{k+1}}{\tau_{k}}\langle\hat{w}^{k+1},w^{k}\rangle.\end{array}$
(51)

Let us choose $\tau_{k}:=\frac{1}{k+2}$, $\hat{\eta}_{k}:=(1-\tau_{k})\eta$,
$a_{k}:=\frac{b_{k}}{2}\left(\eta(k+1)-4\rho k+\frac{2\rho(k-1)}{k+3}\right)$,
and
$c_{k}:=\frac{b_{k}}{2}\left(M\eta^{3}(k+1)+\frac{8\rho(k+2)^{2}}{k+3}\right)$.
Then, utilizing these choices and $b_{k+1}(1-\tau_{k})=b_{k}$, (51) reduces to

$\begin{array}[]{lcl}\hat{\mathcal{V}}_{k}-\hat{\mathcal{V}}_{k+1}&\geq&\frac{\eta(1-M\eta^{2})b_{k+1}}{2\tau_{k}}\|\hat{w}^{k+1}-(1-\tau_{k})w^{k}\|^{2}+\frac{2\rho
b_{k+1}(k+2)}{(k+3)(k+4)}\|w^{k+1}\|^{2}\vspace{1ex}\\\
&&+{~{}}\frac{b_{k+1}(k+2)}{2}\left(\omega\eta-M\eta^{3}-\frac{8\rho(k+3)^{2}}{(k+2)(k+4)}\right)\|w^{k+1}-\hat{w}^{k+1}\|^{2}.\end{array}$
(52)

Clearly, we need to choose $\omega$ such that $\omega\eta\geq
M\eta^{3}+\frac{8\rho(k+3)^{2}}{(k+2)(k+4)}$, which holds if $\omega\eta\geq
M\eta^{3}+9\rho$. Moreover, to guarantee $a_{k}>0$, we need to choose
$\eta>4\rho$. Therefore, if the following three conditions hold:

$2(1+\omega)L^{2}\eta^{2}\leq 1,\quad\omega\eta\geq
2(1+\omega)L^{2}\eta^{3}+9\rho,\quad\text{and}\quad\eta>4\rho,$ (53)

then, from (52), we have $\hat{\mathcal{V}}_{k+1}\leq\hat{\mathcal{V}}_{k}$
for all $k\geq 0$.

For simplicity of our analysis, let us choose $\omega:=\frac{13}{4}$ and
$\eta:=\frac{1}{L\sqrt{2(1+\omega)}}=\frac{\sqrt{2}}{\sqrt{17}L}$. Then, the
last two conditions of (53) become
$L\rho\leq\frac{\omega-1}{9\sqrt{2(1+\omega)}}=\frac{1}{2\sqrt{34}}$ and
$L\rho<\frac{1}{4\sqrt{2(1+\omega)}}=\frac{1}{2\sqrt{34}}$, respectively.
Therefore, if $2\sqrt{34}L\rho<1$, then all the conditions of (53) hold.

Since $\tau_{k}:=\frac{1}{k+2}$, we can easily show that $b_{k}=b_{0}(k+1)$
for some $b_{0}>0$. Moreover, since $0\in Fx^{\star}+Tx^{\star}$, we have
$\langle w^{k},x^{k}-x^{\star}\rangle\geq-\rho\|w^{k}\|^{2}$. Using this
inequality, the definition (45) of $\hat{\mathcal{V}}_{k}$, Young’s
inequality, $b_{k}=b_{0}(k+1)$, and the choice of $a_{k}$, we can show that

$\begin{array}[]{lcl}\hat{\mathcal{V}}_{k}&\geq&\left(a_{k}-b_{k}\rho-\frac{(\eta-4\rho)b_{k}^{2}}{4b_{0}}\right)\|w^{k}\|^{2}-\frac{b_{0}}{\eta-4\rho}\|x^{0}-x^{\star}\|^{2}\vspace{1ex}\\\
&\geq&\frac{b_{0}(\eta-4\rho)(k+1)^{2}}{4}\|w^{k}\|^{2}-\frac{b_{0}}{\eta-4\rho}\|x^{0}-x^{\star}\|^{2}.\end{array}$

Since $y^{-1}=x^{0}$, we have
$\hat{\mathcal{V}}_{0}=a_{0}\|w^{0}\|^{2}+b_{0}\langle
w^{0},x^{0}-x^{0}\rangle+c_{0}\|w^{0}-\hat{w}^{0}\|^{2}=a_{0}\|w^{0}\|^{2}=b_{0}\left(\frac{\eta}{2}-\frac{\rho}{3}\right)\|Fx^{0}+\xi^{0}\|^{2}$.
Therefore, we get
$\hat{\mathcal{V}}_{k}\leq\hat{\mathcal{V}}_{0}=b_{0}\left(\frac{\eta}{2}-\frac{\rho}{3}\right)\|Fx^{0}+\xi^{0}\|^{2}$
from (52). Combining this and the lower bound of $\hat{\mathcal{V}}_{k}$
above, we obtain

$\begin{array}[]{lcl}\|w^{k}\|^{2}&\leq&\frac{1}{(k+1)^{2}}\left[\frac{4}{(\eta-4\rho)^{2}}\|x^{0}-x^{\star}\|^{2}+\frac{2(3\eta-2\rho)}{3(\eta-4\rho)}\|Fx^{0}+\xi^{0}\|^{2}\right],\end{array}$

which is exactly (47) by using $w^{k}:=Fx^{k}+\xi^{k}\in Fx^{k}+Tx^{k}$. The
last bound (48) is a direct consequence of (47) and
$\|\mathcal{G}_{\eta}x^{k}\|\leq\|Fx^{k}+\xi^{k}\|$ in Lemma 3.1. $\square$∎

##  6 Concluding Remarks

In this paper, we have developed two “Nesterov’s accelerated” variants of the
FBFS method and its past-FBFS scheme. Our approach is different from Halpern’s
fixed-point iteration in, e.g., [13, 14, 40, 75, 79]. These two types of
methods are though different, they are related to each other as discussed in
[73]. We have established $\mathcal{O}\left(1/k\right)$ last-iterate
convergence rates of both new schemes using explicit parameter update rules
and different Lyapunov functions. We have also provided an alternative
convergence rate analysis of the extra-anchored gradient-type methods in [13,
14] for solving (chMI). Our analysis exploits the proof techniques in [40, 75,
79] and our second scheme is also different from the one in [14].

Beyond the results of this paper, several research questions remain open to
us. We discuss some of them here. First, though both proposed algorithms
theoretically achieve better convergence rates than the classical non-
accelerated (FBFS) and (PFBFS) schemes, their practical performance remains
unclear. It is important to develop practical variants of these methods so
that they can perform better or at least not worse than (FBFS) and (PFBFS) on
concrete applications. One idea is to use adaptive techniques to update the
algorithmic parameters without knowing $L$ and $\rho$. Second, it is also
interesting to establish $o\left(1/k\right)$ (small-o) convergence rates of
the proposed methods by using different parameter update rules, at least for
the monotone case. In addition, the convergence of iterate sequences and their
convergence rates remains open. Third, improving the range of $L\rho$ is also
interesting, at least theoretically. The classical methods (FBFS) and (PFBFS)
have tight bounds on the range of $L$ and $\rho$, while our conditions remain
suboptimal and can be improved, especially for (APEG). Fourth, one can also
extend our methods to solve $0\in Fx+Hx+Tx$ and provide rigorous convergence
rate analysis as we have done in this paper. Finally, developing stochastic
and randomized block coordinate variants for these methods to solve (chMI) is
also interesting and expected to make significant impact in machine learning
applications and distributed systems.

Data availability. The author confirms that this paper does not contain any
data.

Acknowledgements. The author is grateful to the anonymous reviewers for their
helpful comments and suggestions. This paper is based upon work partially
supported by the National Science Foundation (NSF), grant no. NSF-RTG
DMS-2134107 and the Office of Naval Research (ONR), grant No. N00014-20-1-2088
and No. N00014-23-1-2588.

## References

  * [1] M. Arjovsky, S. Chintala, and L. Bottou.  Wasserstein generative adversarial networks.  In International Conference on Machine Learning, pages 214–223, 2017.
  * [2] H. Attouch and A. Cabot.  Convergence of a relaxed inertial proximal algorithm for maximally monotone operators.  Math. Program., 184(1):243–287, 2020.
  * [3] H. Attouch and J. Peypouquet.  Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators.  Math. Program., 174(1-2):391–432, 2019.
  * [4] M. G. Azar, I. Osband, and R. Munos.  Minimax regret bounds for reinforcement learning.  In International Conference on Machine Learning, pages 263–272. PMLR, 2017.
  * [5] H. H. Bauschke and P. Combettes.  Convex analysis and monotone operators theory in Hilbert spaces.  Springer-Verlag, 2nd edition, 2017.
  * [6] H. H. Bauschke, W. M. Moursi, and X. Wang.  Generalized monotone operators and their averaged resolvents.  Math. Program., pages 1–20, 2020.
  * [7] K. Bhatia and K. Sridharan.  Online learning with dynamics: A minimax perspective.  Advances in Neural Information Processing Systems, 33:15020–15030, 2020.
  * [8] A. Böhm.  Solving nonconvex-nonconcave min-max problems exhibiting weak Minty solutions.  Transactions on Machine Learning Research, 2022.
  * [9] R. I. Bot, E. R. Csetnek, and D. K. Nguyen.  Fast OGDA in continuous and discrete time.  arXiv preprint arXiv:2203.10947, 2022.
  * [10] R. I. Bot and D. K. Nguyen.  Fast Krasnoselśkii-Mann algorithm with a convergence rate of the fixed point iteration of $o(1/k)$.  arXiv preprint arXiv:2206.09462, 2022.
  * [11] L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization Methods for Large-Scale Machine Learning.  SIAM Rev., 60(2):223–311, 2018.
  * [12] R. S. Burachik and A. Iusem.  Set-Valued Mappings and Enlargements of Monotone Operators.  New York: Springer, 2008.
  * [13] Y. Cai, A. Oikonomou, and W. Zheng.  Accelerated algorithms for monotone inclusions and constrained nonconvex-nonconcave min-max optimization.  arXiv preprint arXiv:2206.05248, 2022.
  * [14] Y. Cai and W. Zheng.  Accelerated single-call methods for constrained min-max optimization.  arXiv preprint arXiv:2210.03096, 2022.
  * [15] Y. Censor, A. Gibali, and S. Reich.  The subgradient extragradient method for solving variational inequalities in hilbert space.  J. Optim. Theory Appl., 148(2):318–335, 2011.
  * [16] V. Cevher and B.C. Vũ.  A reflected forward-backward splitting method for monotone inclusions involving Lipschitzian operators.  Set-Valued and Variational Analysis, 29(1):163–174, 2021.
  * [17] Y. Chen, G. Lan, and Y. Ouyang.  Accelerated schemes for a class of variational inequalities.  Math. Program., 165(1):113–149, 2017.
  * [18] R. Cibulka, A. L. Dontchev, and A. Y. Kruger.  Strong metric subregularity of mappings in variational analysis and optimization.  J. Math. Anal. Appl., 457(2):1247–1282, 2018.
  * [19] P. L. Combettes and T. Pennanen.  Proximal methods for cohypomonotone operators.  SIAM J. Control Optim., 43(2):731–742, 2004.
  * [20] P. L. Combettes and V. R. Wajs.  Signal recovery by proximal forward-backward splitting.  Multiscale Model. Simul., 4:1168–1200, 2005.
  * [21] D. D. Cong and G. Lan.  On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators.  Comput. Optim. Appl., 60(2):277–310, 2015.
  * [22] C. Daskalakis and I. Panageas.  The limit points of (optimistic) gradient descent in min-max optimization.  Advances in neural information processing systems, 31, 2018.
  * [23] D. Davis and W. Yin.  A three-operator splitting scheme and its optimization applications.  Set-Valued Var. Anal., 25(4):829–858, 2017.
  * [24] J. Diakonikolas.  Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.  In Conference on Learning Theory, pages 1428–1451. PMLR, 2020.
  * [25] J. Diakonikolas, C. Daskalakis, and M. Jordan.  Efficient methods for structured nonconvex-nonconcave min-max optimization.  In International Conference on Artificial Intelligence and Statistics, pages 2746–2754. PMLR, 2021.
  * [26] B. Evens, P. Pas, P. Latafat, and P. Patrinos.  Convergence of the preconditioned proximal point method and Douglas-Rachford splitting in the absence of monotonicity.  arXiv preprint arXiv:2305.03605, 2023.
  * [27] F. Facchinei and J.-S. Pang.  Finite-dimensional variational inequalities and complementarity problems, volume 1-2.  Springer-Verlag, 2003.
  * [28] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  arXiv preprint arXiv:1802.10551, 2018.
  * [29] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  In Advances in neural information processing systems, pages 2672–2680, 2014.
  * [30] E. Gorbunov, N. Loizou, and G. Gidel.  Extragradient method: $\mathcal{O}(1/k)$ last-iterate convergence for monotone variational inequalities and connections with cocoercivity.  In International Conference on Artificial Intelligence and Statistics, pages 366–402. PMLR, 2022.
  * [31] E. Gorbunov, A. Taylor, and G. Gidel.  Last-iterate convergence of optimistic gradient method for monotone variational inequalities.  arXiv preprint arXiv:2205.08446, 2022.
  * [32] B. Grimmer, H. Lu, P. Worah, and V. Mirrokni.  The landscape of the proximal point method for nonconvex–nonconcave minimax optimization.  Math. Program., 201(1-2):373–407, 2023.
  * [33] B. Halpern.  Fixed points of nonexpanding maps.  Bull. Am. Math. Soc., 73(6):957–961, 1967.
  * [34] P. T. Harker and J.-S. Pang.  Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications.  Mathematical programming, 48(1):161–220, 1990.
  * [35] Abdul Jabbar, Xi Li, and Bourahla Omar.  A survey on generative adversarial networks: Variants, applications, and training.  ACM Computing Surveys (CSUR), 54(8):1–49, 2021.
  * [36] D. Kim.  Accelerated proximal point method for maximally monotone operators.  Math. Program., pages 1–31, 2021.
  * [37] I.V. Konnov.  Combined relaxation methods for variational inequalities. Springer-Verlag, 2001.
  * [38] G.M. Korpelevich.  The extragradient method for finding saddle points and other problems.  Matecon, 12:747–756, 1976.
  * [39] G. Lan.  First-order and Stochastic Optimization Methods for Machine Learning.  Springer, 2020.
  * [40] S. Lee and D. Kim.  Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems.  Thirty-fifth Conference on Neural Information Processing Systems (NeurIPs2021), 2021.
  * [41] D. Levy, Y. Carmon, J. C. Duchi, and A. Sidford.  Large-scale methods for distributionally robust optimization.  Advances in Neural Information Processing Systems, 33:8847–8860, 2020.
  * [42] F. Lieder.  On the convergence rate of the halpern-iteration.  Optim. Letters, 15(2):405–418, 2021.
  * [43] F. Lin, X. Fang, and Z. Gao.  Distributionally robust optimization: A review on theory and applications.  Numerical Algebra, Control & Optimization, 12(1):159, 2022.
  * [44] Q. Lin, M. Liu, H. Rafique, and T. Yang.  Solving weakly-convex-weakly-concave saddle-point problems as weakly-monotone variational inequality.  arXiv preprint arXiv:1810.10207, 2018.
  * [45] P. L. Lions and B. Mercier.  Splitting algorithms for the sum of two nonlinear operators.  SIAM J. Num. Anal., 16:964–979, 1979.
  * [46] Y. Luo and Q. Tran-Dinh.  Extragradient-type methods for co-monotone root-finding problems.  (Manuscript), 2022.
  * [47] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations, 2018.
  * [48] P.-E. Maingé.  Accelerated proximal algorithms with a correction term for monotone inclusions.  Applied Mathematics & Optimization, 84(2):2027–2061, 2021.
  * [49] P. E. Maingé.  Fast convergence of generalized forward-backward algorithms for structured monotone inclusions.  J. Convex Anal., 29:893–920, 2022.
  * [50] Y. Malitsky.  Projected reflected gradient methods for monotone variational inequalities.  SIAM J. Optim., 25(1):502–520, 2015.
  * [51] Y. Malitsky.  Golden ratio algorithms for variational inequalities.  Math. Program., pages 1–28, 2019.
  * [52] Y. Malitsky and M. K. Tam.  A forward-backward splitting method for monotone inclusions without cocoercivity.  SIAM J. Optim., 30(2):1451–1472, 2020.
  * [53] Y. V. Malitsky and V. V. Semenov.  An extragradient algorithm for monotone variational inequalities.  Cybernetics and Systems Analysis, 50(2):271–277, 2014.
  * [54] P. Marcotte.  Application of Khobotov’s algorithm to variational inequalities and network equilibrium problems.  INFOR: Information Systems and Operational Research, 29(4):258–270, 1991.
  * [55] R.D.C. Monteiro and B.F. Svaiter.  Complexity of variants of Tseng’s modified F-B splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems.  SIAM J. Optim., 21(4):1688–1720, 2011.
  * [56] A. Nemirovskii.  Prox-method with rate of convergence $\mathcal{O}(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.  SIAM J. Optim., 15(1):229–251, 2004.
  * [57] Y. Nesterov.  A method for unconstrained convex minimization problem with the rate of convergence $\mathcal{O}(1/k^{2})$.  Doklady AN SSSR, 269:543–547, 1983.  Translated as Soviet Math. Dokl.
  * [58] Y. Nesterov.  Introductory lectures on convex optimization: A basic course, volume 87 of Applied Optimization.  Kluwer Academic Publishers, 2004.
  * [59] Y. Nesterov.  Dual extrapolation and its applications to solving variational inequalities and related problems.  Math. Program., 109(2–3):319–344, 2007.
  * [60] R. G. Otero and A. Iusem.  Regularity results for semimonotone operators.  Computational & Applied Mathematics, 30:5–17, 2011.
  * [61] J. Park and E. K. Ryu.  Exact optimal accelerated complexity for fixed-point iterations.  https://arxiv.org/pdf/2201.11413.pdf, 2022.
  * [62] T. Pennanen.  Local convergence of the proximal point algorithm and multiplier methods without monotonicity.  Math. Oper. Res., 27(1):170–191, 2002.
  * [63] T. Pethick, P. Patrinos, O. Fercoq, and V. Cevher.  Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems.  In International Conference on Learning Representations, 2022.
  * [64] R. R. Phelps.  Convex functions, monotone operators and differentiability, volume 1364.  Springer, 2009.
  * [65] L. D. Popov.  A modification of the Arrow-Hurwicz method for search of saddle points.  Math. notes of the Academy of Sciences of the USSR, 28(5):845–848, 1980.
  * [66] H. Rahimian and S. Mehrotra.  Distributionally robust optimization: A review.  arXiv preprint arXiv:1908.05659, 2019.
  * [67] R. Rockafellar and R. Wets.  Variational Analysis, volume 317.  Springer, 2004.
  * [68] R.T. Rockafellar.  Monotone operators and the proximal point algorithm.  SIAM J. Control Optim., 14:877–898, 1976.
  * [69] E. K. Ryu and S. Boyd.  Primer on monotone operator methods.  Appl. Comput. Math, 15(1):3–43, 2016.
  * [70] S. Sabach and S. Shtern.  A first order method for solving convex bilevel optimization problems.  SIAM J. Optim., 27(2):640–660, 2017.
  * [71] M. V. Solodov and B. F. Svaiter.  A new projection method for variational inequality problems.  SIAM J. Control Optim., 37(3):765–776, 1999.
  * [72] S. Sra, S. Nowozin, and S. J. Wright.  Optimization for Machine Learning.  MIT Press, 2012.
  * [73] Q. Tran-Dinh.  From Halpern’s fixed-point iterations to Nesterov’s accelerated interpretations for root-finding problems.  Comput. Optim. Appl., in press, 2023.
  * [74] Q. Tran-Dinh.  Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments.  arXiv preprint arXiv:2303.17192, 2023.
  * [75] Q. Tran-Dinh and Y. Luo.  Halpern-type accelerated and splitting algorithms for monotone inclusions.  arXiv preprint arXiv:2110.08150, 2021.
  * [76] Q. Tran-Dinh and Y. Luo.  Randomized block-coordinate optimistic gradient algorithms for root-finding problems.  arXiv preprint arXiv:2301.03113, 2023.
  * [77] P. Tseng.  A modified forward-backward splitting method for maximal monotone mappings.  SIAM J. Control and Optim., 38(2):431–446, 2000.
  * [78] J. Yang, N. Kiyavash, and N. He.  Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems.  arXiv preprint arXiv:2002.09621, 2020.
  * [79] T. Yoon and E. K. Ryu.  Accelerated algorithms for smooth convex-concave minimax problems with $\mathcal{O}(1/k^{2})$ rate on squared gradient norm.  In International Conference on Machine Learning, pages 12098–12109. PMLR, 2021.