# Mirror frameworks for relatively Lipschitz and monotone-like variational
inequalities

Hui Zhang  Department of Mathematics, National University of Defense
Technology, Changsha, Hunan 410073, China. Email<EMAIL_ADDRESS>Yu-Hong
Dai Corresponding author. 100190 $\&$ School of Mathematical Sciences, Chinese
Academy of Sciences, Beijing 100049, China, Email<EMAIL_ADDRESS>
###### Abstract

Nonconvex-nonconcave saddle-point optimization in machine learning has
triggered lots of research for studying non-monotone variational inequalities
(VI). In this work, we introduce two mirror frameworks, called mirror
extragradient method and mirror extrapolation method, for approximating
solutions to relatively Lipschitz and monotone-like VIs. The former covers the
well-known Nemirovski’s mirror prox method and Nesterov’s dual extrapolation
method, and the recently proposed Bregman extragradient method; all of them
can be reformulated into a scheme that is very similar to the original form of
extragradient method. The latter includes the operator extrapolation method
and the Bregman extrapolation method as its special cases. The proposed mirror
frameworks allow us to present a unified and improved convergence analysis for
all these existing methods under relative Lipschitzness and monotone-like
conditions that may be the currently weakest assumptions.

Keywords. Extragradient, extrapolation, Bregman distance, saddle-point, mirror
descent, relative Lipschitzness, monotone, variational inequality

AMS subject classifications. 90C25, 90C47

##  1 Introduction

Variational inequalities (VI), as a powerful mathematical tool to reformulate
optimality conditions and saddle-point optimization [14, 15], have recently
attracted renewed attention in the communities of machine learning and
optimization. The most classic method for solving VIs may be the extragradient
(EG) method, which was initially proposed by Korpelevich to modify the
projected gradient method using extrapolation techniques so that the required
strongly monotone assumption can be relaxed [22]. From a mirror descent
perspective, Nemirovski [33] proposed a prox-method, which generalizes the EG
method from the standard Euclidean case to non-Euclidean cases. Another non-
Euclidean extension of EG is Nesterov’s dual extrapolation (EP) proposed via
dual averaging technique [35]. Recently, the authors of [19] unified the
mirror descent and dual averaging and proposed a unified framework which
covers Nemirovski’s and Nesterov’s methods. Besides these extensions and
unifications, there are a huge of research aimed at improving the original EG
methods by reducing the cost of EG per iteration that needs to evaluate
gradients twice; see e.g. [36, 40, 10, 30, 29].

A common assumption behind all these methods above is that the operator in VIs
is Lipschitz continuous and monotone. However, modern nonconvex-nonconcave
saddle-point optimization problems such as those appeared in deep learning go
beyond monotone VIs and hence the existing results fail to apply in non-
monotone settings. This motivates a surge of interest to generalized VIs and
its associated algorithms [12, 45, 26, 13, 23, 25, 16]. We restrict our
attention to the line of research that relaxes the Lipschitz continuity and
monotonicity assumptions.

The revolution of Lipschitzness happened about five years ago in the field of
convex optimization [2, 27]. Following a basic observation on the classic
proximal gradient, the authors of [2] proposed the Lipschitz-like/convexity
condition to replace the usual Lipschitz continuity property. This property
was also independently discovered by the authors of [27] under the name of
relative smoothness. Recently, the notion of relative smoothness was extended
to monotone VIs in [11]. The extension is not trivial since the formulation in
VIs is quiet different from that in optimization. It has been proved that the
relative Lipschitzness is a very suitable tool to convergence analysis for
several extragradient-type methods applied to monotone VIs [11, 43].

Regarding to the relaxing of monotonicity, the work [12] may be the first to
consider generalized monotone VIs whose operators are not necessarily
monotone. In the community of machine learning, the generalized monotone
assumption [12] was rediscovered in the work [45] under the name of
variational coherence. In order to study weakly-convex-weakly-concave min-max
problems for the training of generative adversarial networks, the authors of
[26] proposed a weakly monotone condition for VIs. With the similar
motivation, the authors of [13] introduced a new class of structured
nonconvex-nonconcave min-max optimization problems by proposing a weak MVI
(Minty variational inequality) condition, under which they proved sublinear
convergence on the squared gradient norm for an EG-type method, named EG+
method. Another recent work [23] introduced a generalized strong monotonicity
condition, with which the authors showed linear convergence for their proposed
operator extrapolation method. It should be noted that all these mentioned
works were done under the Lipschitz continuity assumption.

A natural question arises: can we combine the relative Lipschitzness and non-
monotonicity to consider more general VIs? To answer this question, we first
introduce two algorithmic frameworks–mirror EG method and mirror EP method by
utilizing mirror mapping and extrapolation techniques as well as the tool of
generalized Bregman distances. The new frameworks mainly depend on a mirror
mapping function $\omega$. By exploiting the subdifferentiable of $\omega$, we
greatly expand our previously proposed Bregman EG and EP methods [43]. When
the mirror mapping function is specialized to the so-called
${\mathcal{X}}$-regularizer, the mirror EG method recovers the unified mirror
prox method in [19]. Formally, the mirror EG method is very similar to the
original EG method, which helps us clearly distinguish Nemirovski’s mirror
prox method [33], Nesterov’s dual extrapolation method [35], and our Bregman
EG method [43]. The mirror EP method is formally similar to Bregman EP method
and covers the operator EP method [23]. Theoretically, we derive a group of
convergence results for our proposed frameworks under relative Lipschitzness
and generalized monotone-like assumptions, which generalize and improve the
existing theory. For example, Theorem 5.2 for mirror EG method generalizes the
convergence result of EG+ in [13] and Theorem 5.4 for mirror EP method
generalizes and improves the convergence result of operator EP in [23].

The remainder of the paper is organized as follows. In Section 2, we present
some basic notations and elementary preliminaries. In Section 3, the VI
problem of interest and the saddle-point optimization problem are formulated,
along with a group of Lipschitz-like and monotone-like assumptions. In Section
4, by introducing the mirror mapping and extrapolation techniques, we propose
the mirror EG and EP methods. We also present an algorithmic application to a
class of constrained saddle-point optimization problems. In Section 5, we
study convergence properties of the proposed frameworks under relative
Lipschtizness and generalized monotone-type conditions. Section 6 gives some
concluding remarks and several research directions for future work.

##  2 Preliminaries

###  2.1 Notation

In this paper, we restrict our attention to an arbitrary finite dimensional
space $\mathbb{R}^{d}$ associated with inner product
$\langle\cdot,\cdot\rangle$. Denote the norm in $\mathbb{R}^{d}$ by
$\|\cdot\|$ and its dual norm by $\|\cdot\|_{*}$. For a multi-variables
function $f(x,y)$, we use $\nabla_{x}f$ (respectively, $\nabla_{y}f$) to
denote the gradient of $f$ with respective to $x$ (respectively, $y$). Given a
subset $\Omega\subset\mathbb{R}^{d}$, the characteristic function of $\Omega$
is denoted by $I_{\Omega}$ that takes value zero on $\Omega$ and equals to
$+\infty$ elsewhere.

###  2.2 Convex analysis tools

We present some basic notations and facts about convex analysis, which will be
used in our study.

######  Definition 2.1.

A function $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ is
convex if for any $\alpha\in[0,1]$ and $u,v\in\mathbb{R}^{d}$, we have

$\phi(\alpha u+(1-\alpha)v)\leq\alpha\phi(u)+(1-\alpha)\phi(v);$

and strongly convex with modulus $\mu>0$ if for any $\alpha\in[0,1]$ and
$u,v\in\mathbb{R}^{d}$, we have

$\phi(\alpha
u+(1-\alpha)v)\leq\alpha\phi(u)+(1-\alpha)\phi(v)-\frac{1}{2}\mu\alpha(1-\alpha)\|u-v\|^{2}.$

Furthermore, $\phi$ is concave if $-\phi$ is convex.

Let
$f(x,y):\mathbb{R}^{p}\times\mathbb{R}^{q}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$
be a function. If $f(x,y)$ is convex in $x$ for any fixed $y$ and concave in
$y$ for any fixed $x$, then we say it is convex-concave.

######  Definition 2.2.

Let $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ be a convex
function. The subdifferential of $\phi$ at $u\in\mathbb{R}^{d}$ is defined as

$\partial\phi(u):=\\{u^{*}\in\mathbb{R}^{d}:\phi(v)\geq\phi(u)+\langle
u^{*},v-u\rangle,\quad\forall v\in\mathbb{R}^{d}\\}.$

The elements of $\partial\phi(u)$ are called the subgradients of $\phi$ at
$u$. The effective domain of $\phi$ is defined as
${\mathrm{dom}}\,\phi:=\\{x\in\mathbb{R}^{d}:\phi(x)<+\infty\\}$ and the
effective domain of $\partial\phi$ is given by

${\mathrm{dom}}\,\partial\phi:=\\{x\in\mathbb{R}^{d}:\partial\phi(x)\neq\emptyset\\}.$

The subdifferential generalizes the classical concept of differential because
of the well-known fact that $\partial\phi(u)=\\{\nabla\phi(u)\\}$ when the
function $\phi$ is differentiable. In terms of the subdifferential, the strong
convexity in Definition 2.1 can be equivalently stated as [17]: For any
$u,v\in\mathbb{R}^{d}$ and $v^{*}\in\partial\phi(v)$, we have

$\phi(u)\geq\phi(v)+\langle v^{*},u-v\rangle+\frac{\mu}{2}\|u-v\|^{2}.$ (2.1)

######  Definition 2.3.

Let $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ be a convex
function. The conjugate of $\phi$ is defined as

$\phi^{*}(u^{*})=\sup_{v\in\mathbb{R}^{d}}\\{\langle
u^{*},v\rangle-\phi(v)\\}.$

The following facts are well-known, which can be found from the classic
textbooks [38] and [17].

######  Lemma 2.1.

Let $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ be a lower-
semicontinuous convex function with nonempty domain. Then, the conditions
$\phi(u)+\phi^{*}(u^{*})=\langle u,u^{*}\rangle$, $u^{*}\in\partial\phi(u)$,
and $u\in\partial\phi^{*}(u^{*})$ are equivalent.

###  2.3 Bregman distance tools

The Bregman distance, originally introduced in [7], is a very powerful tool in
many fields where distances are involved. Recently, a couple of variants of
Bregman distances were introduced, see e.g. [3, 20, 37]. For simplicity as
well as generality, we define the Bregman distance via a convex function, not
necessarily differentiable.

######  Definition 2.4.

Let $\omega:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ be a
convex function with ${\mathrm{dom}}\,\partial\omega\neq\emptyset$. The
Bregman distance $D_{\omega}^{v^{*}}(u,v)$ between $u\in\mathbb{R}^{d}$ and
$v\in{\mathrm{dom}}\,\partial\omega$ with respect to $\omega$ and a
subgradient $v^{*}\in\partial\omega(v)$ is defined by

$D_{\omega}^{v^{*}}(u,v):=\omega(u)-\omega(v)-\langle v^{*},u-v\rangle.$ (2.2)

If the distance generating function $\omega$ is differentiable at $v$, the
Bregman distance above reduces to

$D_{\omega}(u,v):=\omega(u)-\omega(v)-\langle\nabla\omega(v),u-v\rangle.$
(2.3)

The following results on the Bregman distance, essentially coming from [20,
21], will be used in the later convergence analysis.

######  Lemma 2.2.

Let $\omega:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a convex function with
${\mathrm{dom}}\,\partial\omega\neq\emptyset$. For any
$u,p,q\in\mathbb{R}^{d}$ and
$p^{*}\in\partial\omega(p),q^{*}\in\partial\omega(q)$, we have that

$D_{\omega}^{p^{*}}(u,p)-D_{\omega}^{q^{*}}(u,q)+D_{\omega}^{q^{*}}(p,q)=\langle
q^{*}-p^{*},u-p\rangle.$ (2.4)

If the function $\omega$ is $\mu$-strongly convex, then we have

$D_{\omega}^{q^{*}}(p,q)\geq\frac{\mu}{2}\|p-q\|^{2}.$ (2.5)

##  3 The problem formulation and assumptions

In this section, we first introduce the VI problem of interest. Then, we
discuss a group of assumptions on Lipschitiz-like continuities and monotone-
like conditions.

###  3.1 The problem formulation

Given a nonempty closed convex set ${\mathcal{U}}\subset\mathbb{R}^{d}$ and an
operator $F:{\mathcal{U}}\rightarrow\mathbb{R}^{d}$, the VI problem of interst
consists in finding $\hat{u}$ such that

$\langle F(\hat{u}),u-\hat{u}\rangle\geq 0,\forall u\in{\mathcal{U}}.$ (3.1)

Such a point $\hat{u}$ is referred to as a strong solution of the VI problem
(3.1). We denote the set of all such solutions by ${\mathcal{U}}_{s}$, assumed
to be nonempty. If the operator $F$ is monotone in the sense that

$\langle F(u)-F(u^{\prime}),u-u^{\prime}\rangle\geq 0,\forall
u,u^{\prime}\in{\mathcal{U}},$ (3.2)

then the VI problem (3.1) has the following equivalent problem that consists
in finding $\hat{u}$ such that

$\langle F(u),\tilde{u}-u\rangle\leq 0,\forall u\in{\mathcal{U}}.$ (3.3)

Such a point $\tilde{u}$ is referred to as a weak solution of the VI problem
(3.1). We denote the set of all such solutions by ${\mathcal{U}}_{w}$, which
equals to ${\mathcal{U}}_{s}$ under the monotonicity of $F$.

As an illustrative example, we consider the following constrained saddle-point
optimization problem, which consists in finding a point pair
$(\hat{x},\hat{y})\in{\mathcal{X}}\times{\mathcal{Y}}$ such that

$f(\hat{x},\hat{y})=\min_{x\in{\mathcal{X}}}\max_{y\in{\mathcal{Y}}}f(x,y),$
(3.4)

where ${\mathcal{X}}\subset\mathbb{R}^{p}$ and
${\mathcal{Y}}\subset\mathbb{R}^{q}$ are closed convex sets, and the saddle-
point function $f:{\mathcal{X}}\times{\mathcal{Y}}\rightarrow\mathbb{R}$ is
smooth convex-concave. Such a point
$(\hat{x},\hat{y})\in{\mathcal{X}}\times{\mathcal{Y}}$ is referred to as a
saddle point (also called a Nash equilibrium), which can be characterized by

$f(\hat{x},y)\leq f(\hat{x},\hat{y})\leq f(x,\hat{y}),\forall
x\in{\mathcal{X}},y\in{\mathcal{Y}}.$

Then, the constrained saddle-point problem can be equivalently reformulated
into the VI problem (3.1) with
${\mathcal{U}}={\mathcal{X}}\times{\mathcal{Y}}$,
$u=(x,y),\hat{u}=(\hat{x},\hat{y})$, and the operator
$F:{\mathcal{U}}\rightarrow\mathbb{R}^{p+q}$ being given by

$F(u)=F(x,y):=(\nabla_{x}f(x,y),-\nabla_{y}f(x,y))^{T}.$ (3.5)

The operator above is called saddle-point gradient operator.

###  3.2 Assumptions

The most common assumption for studying VIs in the literature may be the
$L$-Lipschitz continuity condition of the operator $F$, i.e., form some $L>0$,

$\|F(u)-F(u^{\prime})\|_{*}\leq L\|u-u^{\prime}\|,~{}~{}\forall
u,u^{\prime}\in{\mathcal{U}}.$ (3.6)

If the operator $F$ is specialized to the gradient operator of a function
$\phi$, then the property (3.6) recovers the gradient-Lipschitz-continuity
condition (also called $L$-smoothness, see e.g. the book [5]), which was
recently generalized to so-called relative smoothness for wider first-order
optimization in [2, 27]. Motivated by the relative smoothness and the area
convexity condition of [39], a weaker alternative to the $L$-Lipschitz
continuity condition, called relative Lipschitzness, was introduced recently
in [11] with the form:

$\langle
F(v)-F(u),v-z\rangle\leq\lambda\cdot(D_{\omega}(v,u)+D_{\omega}(z,v)),$

where $\omega$ is a convex and differentiable function and $\lambda>0$ is the
relatively Lipschitz constant. The proposed relative Lipschitzness is well-
suited for the standard analyses of extragradient-type methods, as illustrated
in [11] for mirror prox and dual extrapolation methods and in [43] for Bregman
extragradient and extrapolation methods. In this study, in order to apply the
relative Lipschitzness more widely, we slightly modify it by allowing the
distance generating function $\omega$ to be nondifferentiable.

######  Assumption 3.1.

Let $\omega:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ be a
convex function with ${\mathcal{U}}\subset{\mathrm{dom}}\,\partial\omega$ and
let $\lambda$ be a positive parameter. We say that the operator $F$ is
$\lambda$-relatively Lipschitz continuous with respect to $\omega$ on
${\mathcal{U}}$ if for any $u,v,z\in{\mathcal{U}}$ it holds that

$\langle
F(v)-F(u),v-z\rangle\leq\lambda\cdot(\inf_{u^{*}\in\partial\omega(u)}D_{\omega}^{u^{*}}(v,u)+\inf_{v^{*}\in\partial\omega(v)}D_{\omega}^{v^{*}}(z,v)).$
(3.7)

The following two results, essentially observed in [11], respectively say that
the relative Lipschitzness encapsulates the basic Lipschitz continuity and the
relative smoothness. Note that the relative notions in the second lemma are
more general than the original statement in [11] since we allow the distance
generating function $\omega$ to be nondifferentiable.

######  Lemma 3.1.

If $\omega$ is strongly convex with modulus $\mu$ and $F$ is L-Lipschitz
continuous, then $F$ is $L/\mu$-relatively Lipschitz continuous with respect
to $\omega$ on the whole space $\mathbb{R}^{d}$.

######  Lemma 3.2.

If $\phi$ is $L$-relatively smooth with respect to $\omega$ in the senses that

$\phi(u)-\phi(v)-\langle\nabla\phi(v),u-v\rangle\leq L\cdot
D_{\omega}^{v^{*}}(u,v),\forall
u,v\in\mathbb{R}^{d},~{}v^{*}\in\partial\omega(v),$ (3.8)

then $F$, defined by $F:=\nabla\phi$, is $L$-relatively Lipschitz continuous
with respect to $\omega$ on the whole space $\mathbb{R}^{d}$.

The (relatively) Lipschitz continuity of $F$ defines (relatively) smooth VIs.
In order to solve the VIs globally and more efficiently, monotone-like
assumptions are usually necessary. In what follows, we first list two
monotone-like conditions that can be viewed as direct extensions of (3.2).

######  Assumption 3.2.

We say that the operator $F$ is $\eta$-monotone if for any
$u,u^{\prime}\in{\mathcal{U}}$ it holds that

$\langle
F(u)-F(u^{\prime}),u-u^{\prime}\rangle\geq\eta\cdot\|u-u^{\prime}\|^{2}.$
(3.9)

######  Assumption 3.3.

We say that the operator $F$ is $\tau$-comonotone if for any
$u,u^{\prime}\in{\mathcal{U}}$ it holds that

$\langle
F(u)-F(u^{\prime}),u-u^{\prime}\rangle\geq\tau\cdot\|F(u)-F(u^{\prime})\|_{*}^{2}.$
(3.10)

The $\eta$-monotonicity consists of three cases depending on the parameter:
strong monotonicity when $\eta>0$, weak monotonicity when $\eta<0$, and
monotonicity when $\eta=0$. Similarly, the $\tau$-conmonotonicity also
consists of three cases: cocoercivity when $\tau>0$, comonotonicity [4] when
$\tau<0$, and monotonicity when $\eta=0$. There are interesting links between
monotonicity of operator and convexity of function. A classic result is the
correspondence between the convexity of a function $\phi$ and the monotonicity
of its gradient $\nabla\phi$. Another well-known result is that the saddle-
point gradient operator (3.5) is monotone if the saddle-point function
$f(x,y)$ is smooth convex-concave and vice versa. Based on these facts, we may
guess that some classes of non-convex and non-concave saddle-point functions
could be characterized by certain non-monotonicity conditions. Actually, the
connection between the weak monotonicity of the saddle-point gradient operator
(3.5) and the weakly-convex-weakly-concave of the saddle-point function $f$
was recently established in [26]. Thereby, further relaxed monotonicity
conditions in VIs allow us to cover wider classes of saddle-point optimization
problems.

Note that the monotone-like assumptions previously mentioned are all
characterized by inequalities that require all point pairs $(u,u^{\prime})$ to
satisfy. This requirement is strict but not necessary because we actually only
need these inequalities to hold on some certain point pairs. Hence, it leaves
us space for further relaxation; this idea was developed in convex
optimization for relaxing the strong convexity in [44, 32]. Returning to VIs
and with the same spirit of relaxation, the authors of [12] introduced the
generalized monotone assumption, which was rediscovered in the work [45] under
the name of variational coherence.

######  Assumption 3.4.

We say that the operator $F$ is generalized monotone if for any
$u\in{\mathcal{U}}_{s}$ it holds that

$\langle F(\bar{u}),\bar{u}-u\rangle\geq 0,\forall\bar{u}\in{\mathcal{U}}.$
(3.11)

Obviously, this assumption is implied by the monotonicity and also by the
following pseudo-monotone assumption.

######  Assumption 3.5.

We say that the operator $F$ is pseudo-monotone if for any
$u,u^{\prime}\in{\mathcal{U}}$ it holds that

$\langle F(u),u^{\prime}-u\rangle\geq 0\Rightarrow\langle
F(u^{\prime}),u^{\prime}-u\rangle\geq 0.$ (3.12)

Conversely, the generalized monotonicity does not imply the monotonicity or
the pseudo-monotonicity, and hence its is a strictly weaker assumption; see
the constructed example in [12]. Recently, the authors of [13] introduced the
weak MVI condition, which is further weaker than the generalized monotonicity,
for a class of structured nonconvex-nonconcave min-max optimization.

######  Assumption 3.6.

We say that the operator $F$ is $\rho$-weakly MVI monotone if $\rho>0$ and
there exists $u\in{\mathcal{U}}_{s}$ such that for any
$\bar{u}\in{\mathcal{U}}$ it holds that

$\langle
F(\bar{u}),\bar{u}-u\rangle\geq-\frac{\rho}{2}\|F(\bar{u})\|_{*}^{2}.$ (3.13)

It has been shown in [13] that the $\rho$-weakly MVI monotone assumption is
implied by the $(-\frac{\rho}{2})$-comonotonicity [4] in the case of
${\mathcal{U}}=\mathbb{R}^{d}$. Based on the interaction dominate condition in
[16], the authors of [25] introduced a nonconvex-nonconcave condition that
implies the the $-\frac{\rho}{2}$-comonotonicity and hence implies the
$\rho$-weakly MVI monotonicity.

In order to study linear convergence of the operator extrapolation method, the
authors of [23] proposed a generalized strong monotonicity condition, which is
stronger than the generalized monotonicity but does not imply monotonicity.
Letting $u\in{\mathcal{U}}_{s}$, it reads as

$\langle F(\bar{u}),\bar{u}-u\rangle\geq 2\mu\cdot
D_{\omega}(u,\bar{u}),~{}~{}\forall\bar{u}\in{\mathcal{U}}.$ (3.14)

When $F=\nabla\phi$ and $\omega=\frac{1}{2}\|\cdot\|^{2}$, the above
inequality reduces to

$\langle\nabla\phi(\bar{u}),\bar{u}-u\rangle\geq\mu\cdot\|u-\bar{u}\|^{2},~{}~{}\forall\bar{u}\in{\mathcal{U}},$
(3.15)

which was introduced and studied in [24, 44, 42] under the name of restricted
strongly convex property and in [45] under the name of strongly variational
coherence. Below, we present a modified version of (3.14) by allowing the
distance generating function $\omega$ to be nondifferentiable, and call it
relatively restricted monotonicity.

######  Assumption 3.7.

Let $\omega:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$ be a
convex function with ${\mathcal{U}}\subset{\mathrm{dom}}\,\partial\omega$ and
let $\mu\geq 0$ be a given parameter. We say that the operator $F$ is
$\mu$-relatively restricted monotone with respect to $\omega$ on
${\mathcal{U}}$ if for any $\bar{u}\in{\mathcal{U}}$ and
$u\in{\mathcal{U}}_{s}$ it holds that

$\langle
F(\bar{u}),\bar{u}-u\rangle\geq\sup_{\bar{u}^{*}\in\partial\omega(\bar{u})}2\mu\cdot
D_{\omega}^{\bar{u}^{*}}(u,\bar{u}).$ (3.16)

##  4 Algorithmic frameworks

In this section, we introduce two mirror algorithmic frameworks, both of which
are constructed by coupling the operator
$F:{\mathcal{U}}\rightarrow\mathbb{R}^{d}$ and a convex function
$\omega:\mathbb{R}^{d}\rightarrow\mathbb{R}\bigcup\\{+\infty\\}$.

###  4.1 Two pillars

In this part, we introduce the mirror mapping and extrapolation techniques, as
two basic tools for constructing our mirror frameworks.

####  4.1.1 Mirror mapping technique

The mirror descent (MD) algorithm, originally introduced by Nemirovski and
Yudin in [34], has become a very popular method in many applied mathematical
fields. Here, we briefly recall its algorithmic motivation and the explanation
in terms of nonlinear projection by following [6] and [8].

Suppose that we want to minimize a function $f$ in some Banach space
${\mathcal{B}}$, whose dual space ${\mathcal{B}}^{*}$ is assumed to be
different from ${\mathcal{B}}$. Then, the gradient descent strategy can not be
directly applied to minimizing $f$ since now the formulation

$x-\eta\cdot\nabla f(x)$

makes nonsense if the step size $\eta\neq 0$ due to the fact that
$x\in{\mathcal{B}}$ whilst $\nabla f(x)\in{\mathcal{B}}^{*}$. There are two
possible ways to remedy this: mapping $x$ into ${\mathcal{B}}^{*}$ or mapping
$\nabla f(x)$ back to ${\mathcal{B}}$ so that both of them lie in the same
space. More concretely, we first choose a map
$\Psi:{\mathcal{B}}\rightarrow{\mathcal{B}}^{*}$ and its inverse map
$\Psi^{-1}:{\mathcal{B}}^{*}\rightarrow{\mathcal{B}}$. The first way goes like

$\Psi^{-1}(\Psi(x)-\eta\cdot\nabla f(x)).$

The second way works as

$x-\eta\cdot\Psi^{-1}(\nabla f(x)).$

The MD algorithm follows from the first way by setting $\Psi=\nabla\omega$ and
$\Psi^{-1}=\nabla\omega^{*}$ with a differentiable function $\omega$; while
the dual space preconditional gradient descent, recently introduced in [28],
follows from the second way.

Now, we describe the basic step of the MD as follows; see also Figure 1.

$x^{+}=\nabla\omega^{*}(\nabla\omega(x)-\eta\cdot\nabla f(x)).$ (4.1)

$\bullet$$x$$\nabla\omega$$\bullet$$\nabla\omega(x)$$\bullet$$\bullet$$\nabla\omega(x)-\eta\nabla
f(x)$$-\eta\nabla f(x)$$\nabla\omega^{*}$$\bullet$$x^{+}$primal space
${\mathcal{B}}$dual space ${\mathcal{B}}^{*}$ Figure 1: Mirror Descent

Note that if $\omega$ is strongly convex, then (4.1) is just the first-order
optimality condition of the following convex optimization:

$\displaystyle\begin{array}[]{lll}x^{+}&=&\arg\min_{z}\\{\langle\eta\nabla
f(x),z\rangle+\omega(z)-\langle\nabla\omega(x),z\rangle\\}\\\
&=&\arg\min_{z}\\{\langle\eta\nabla
f(x),z\rangle+D_{\omega}(z,x)\\}.\end{array}$ (4.4)

This is exactly the nonlinear projection explanation introduced in [6]. If let
$\omega=\frac{1}{2}\|\cdot\|_{2}^{2}$ with $\|\cdot\|_{2}$ being the Euclidean
norm, then we have

$x^{+}=x-\eta\nabla f(x)=\arg\min_{z}\\{\langle\eta\nabla
f(x),z\rangle+\frac{1}{2}\|z-x\|_{2}^{2}\\}.$ (4.5)

Therefore, (4.4) can be viewed as a generalized gradient descent (also called
Bregman gradient descent) since it replaces the Euclidean distance proximity
term $\frac{1}{2}\|z-x\|_{2}^{2}$ with the Bregman distance $D_{\omega}(z,x)$.
In order to further generalize (4.4), we consider to replace the term
$D_{\omega}(z,x)$ by the generalized Bregman distance
$D_{\omega}^{x^{*}}(z,x)$ with $x^{*}\in\partial\omega(x)$; that is

$\displaystyle\begin{array}[]{lll}x^{+}&=&\arg\min_{z}\\{\langle\eta\nabla
f(x),z\rangle+D^{x^{*}}_{\omega}(z,x)\\}\\\
&=&\nabla\omega^{*}(x^{*}-\eta\nabla f(x)).\end{array}$ (4.8)

We call the update (4.8) generalized mirror descent method; see also Figure 2.
Note that this update not only depends on the function $\omega$ but also the
subgradient $x^{*}$. Different setting rules of such $x^{*}$ will correspond
to different algorithmic schemes.

####  4.1.2 Extrapolation technique

The extragradient (EG) method, originally introduced by Karpelevich in 1976
[22], is also a modified gradient method using the idea of extrapolation
rather than the mirror mapping. It first makes a trial step along a negative
gradient direction to produce an “extrapolated” point, and then proceeds
actual movement along the gradient at the extrapolated point. Applying this
idea to the VI problem 3.1 with ${\mathcal{U}}=\mathbb{R}^{d}$, the basic step
of the EG method can be described as follows:

$\displaystyle\left\\{\begin{array}[]{lll}\bar{u}_{k}=u_{k}-\eta F(u_{k}),\\\
u_{k+1}=u_{k}-\eta F(\bar{u}_{k}).\end{array}\right.$ (4.11)

Here, $\bar{u}_{k}$ is the extrapolated point and $u_{k+1}$ is the actually
updated point from $u_{k}$. In (4.11), two gradient-like sequences
$\\{F(u_{k})\\}$ and $\\{F(\bar{u}_{k})\\}$ need to compute. Recently, a
single-call EG variant, which only requires to compute the sequence
$\\{F(\bar{u}_{k})\\}$, received lots of attention [18, 41, 9, 1]. This
variant reads as

$\displaystyle\left\\{\begin{array}[]{lll}\bar{u}_{k}=u_{k}-\eta
F(\bar{u}_{k-1}),\\\ u_{k+1}=u_{k}-\eta F(\bar{u}_{k}).\end{array}\right.$
(4.14)

One can see that the new extrapolated point $\bar{u}_{k}$ is obtained along
the history gradient $F(\bar{u}_{k-1})$ rather than $F(u_{k})$. This slight
modification provides us with the following equivalent form of (4.14), that is

$\bar{u}_{k+1}=\bar{u}_{k}-\eta
F(\bar{u}_{k})-\eta(F(\bar{u}_{k})-F(\bar{u}_{k-1})).$ (4.15)

The term $F(\bar{u}_{k})-F(\bar{u}_{k-1})$ is referred to as an operator
extrapolated term. At last, it should be noted that (4.15) can also be derived
from Popov’s modification [36], which reads as

$\displaystyle\left\\{\begin{array}[]{lll}\bar{u}_{k}=\bar{u}_{k-1}-\eta
F(u_{k}),\\\ u_{k+1}=\bar{u}_{k}-\eta F(u_{k}).\end{array}\right.$ (4.18)

Eliminating the element $\bar{u}_{k}$, we can get

$u_{k+1}=u_{k}-\eta F(u_{k})-\eta(F(u_{k})-F(u_{k-1})),$ (4.19)

which is essentially (4.15). Note that Popov’s method is also a single-call
EG-type variant.

$\bullet$$x$$\partial\omega$$\bullet$$x^{*}\in\partial\omega(x)$$\bullet$$\bullet$$x^{*}-\eta\nabla
f(x)$$-\eta\nabla f(x)$$\nabla\omega^{*}$$\bullet$$x^{+}$primal space
${\mathcal{B}}$dual space ${\mathcal{B}}^{*}$ Figure 2: Generalized Mirror
Descent

###  4.2 The proposed methods

Very recently, we introduced two new EG variants, namely Bregman EG and EP
methods in [43], by applying the generalized mirror descent (4.8) to the EG
method (4.11) and to its extrapolated variant (4.19), respectively. Now, let
us recall these two methods. The Bregman EG method generates the iterates
$\\{u_{k}\\}$ for $k\geq 0$ via the following scheme:

$\displaystyle\left\\{\begin{array}[]{lll}\bar{u}_{k}=\nabla\omega^{*}(u_{k}^{*}-\alpha_{k}F(u_{k})),\\\
u_{k+1}=\nabla\omega^{*}(u_{k}^{*}-\alpha_{k}F(\bar{u}_{k})),\\\
u_{k+1}^{*}=u_{k}^{*}-\alpha_{k}F(\bar{u}_{k}).\end{array}\right.$ (4.23)

The Bregman EP method generates the iterates $\\{u_{k}\\}$ for $k\geq 0$ via
the following scheme:

$\displaystyle\left\\{\begin{array}[]{lll}u_{k+1}=\nabla\omega^{*}(u_{k}^{*}-\alpha_{k}F(u_{k})-\alpha_{k}\beta_{k}(F(u_{k})-F(u_{k-1}))),\\\
u_{k+1}^{*}=u_{k}^{*}-\alpha_{k}F(u_{k})-\alpha_{k}\beta_{k}(F(u_{k})-F(u_{k-1})).\end{array}\right.$
(4.26)

In this study, we further generalize the Bregman EG and EP methods to solve
VIs by utilizing other possible subgradiens from the subdifferential
$\partial\omega(u_{k})$. Corresponding to the Bregman EG method, we propose
the following scheme, called mirror EG method.

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\bar{u}_{k}=\nabla\omega^{*}(u_{k,1}^{*}-\frac{\alpha_{k}}{\beta}F(u_{k})),u^{*}_{k,1}\in\partial\omega(u_{k}),$
(4.27a) $\displaystyle
u_{k+1}=\nabla\omega^{*}(u_{k,2}^{*}-\alpha_{k}F(\bar{u}_{k})),u^{*}_{k,2}\in\partial\omega(u_{k}),$
(4.27b) $\displaystyle\langle u_{k,2}^{*}-u_{k,1}^{*},u-u_{k}\rangle\leq
0,\forall u\in{\mathcal{U}},$ (4.27c) $\displaystyle\langle
u_{k+1,2}^{*}-u_{k,2}^{*}+\alpha_{k}F(\bar{u}_{k}),u-u_{k+1}\rangle\geq
0,\forall u\in{\mathcal{U}}.$ (4.27d)

In (4.27a) and (4.27b), we utilize two different subgradient sequences
$\\{u_{k,1}^{*}\\}$ and $\\{u_{k,2}^{*}\\}$, which distinguishes the mirror EG
method from the Bregman EG method. Of course, the choosing of subgradients can
not be arbitrary. In (4.27c), we add a constraint on them, in order to ensure
the convergence analysis of the Bregman EG in [43] still to be feasible. The
reader who will go through our forthcoming analysis could find that it is
sufficient to require the weaker constraint $\langle
u_{k,2}^{*}-u_{k,1}^{*},u_{k+1}-u_{k}\rangle\leq 0$, or equivalently,

$D_{\omega}^{u^{*}_{k,1}}(u_{k+1},u_{k})-D_{\omega}^{u^{*}_{k,2}}(u_{k+1},u_{k})\leq
0.$

From (4.27d), we have
$\langle\alpha_{k}F(\bar{u}_{k}),u_{k+1}-u\rangle\leq\langle
u_{k+1,2}^{*}-u_{k,2}^{*},u-u_{k+1}\rangle$, which actually relaxes the
equality

$\langle\alpha_{k}F(\bar{u}_{k}),u_{k+1}-u\rangle=\langle
u_{k+1,2}^{*}-u_{k,2}^{*},u-u_{k+1}\rangle.$

This relaxation does not affect the estimation of
$\langle\alpha_{k}F(\bar{u}_{k}),u_{k+1}-u\rangle$ by $\langle
u_{k+1,2}^{*}-u_{k,2}^{*},u-u_{k+1}\rangle.$ At last, the introduction of
parameter $\beta$ was inspired by the EG+ method, recently suggested in [13].
The reader will find that if $\beta$ is strictly less than one, then sublinear
convergence of the mirror EG method may follow under the weakly MVI
monotonicity.

In all, our motivation of proposing the mirror EG method is to exploit the
subdifferential $\partial\omega(u_{k})$ more sufficiently and meanwhile
guarantee it to converge nicely.

Corresponding to the Bregman EP method, we similarly propose the mirror EP
method as follows.

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\xi_{k}=\alpha_{k}F(u_{k})+\alpha_{k}\beta_{k}(F(u_{k})-F(u_{k-1})),$
(4.28a) $\displaystyle
u_{k+1}=\nabla\omega^{*}(u_{k}^{*}-\xi_{k}),u^{*}_{k}\in\partial\omega(u_{k}),$
(4.28b) $\displaystyle\langle
u_{k+1}^{*}-u_{k}^{*}+\xi_{k},u-u_{k+1}\rangle\geq 0,\forall
u\in{\mathcal{U}}.$ (4.28c)

In order to guarantee that the sequences $\\{\bar{u}_{k}\\}$ and $\\{u_{k}\\}$
in (4.27) and (4.28) are well-defined, we need to choose suitable functions
$\omega$, called mirror mapping function, such that: 1) the subdifferential
$\partial\omega(u_{k})$ should be nonempty, otherwise $u^{*}_{k,i}$ can not be
defined; 2) the conjugate $\omega^{*}$ should be differentiable on
$\mathbb{R}^{d}$ and the generated points $\bar{u}_{k}$ and $u_{k}$ by the
mapping $\nabla\omega^{*}$ need to lie in ${\mathcal{U}}$, otherwise
$F(\bar{u}_{k})$ and $F(u_{k})$ would make nonsense since the operator $F$ is
defined on ${\mathcal{U}}$. To this end, we propose the following condition:

$u_{0}\in{\mathrm{dom}}\,\partial\omega,~{}~{}\nabla\omega^{*}(\mathbb{R}^{d})\subset{\mathcal{U}},$
(4.29)

with which we immediately have
$\bar{u}_{k},u_{k}\in\nabla\omega^{*}(\mathbb{R}^{d})\subset{\mathcal{U}}$ and
hence $F(\bar{u}_{k})$ and $F(u_{k})$ are well-defined. Let us check that
$\partial\omega(u_{k})\neq\emptyset$. It suffices to show
$\nabla\omega^{*}(\mathbb{R}^{d})\subset{\mathrm{dom}}\,\partial\omega$ since
$u_{k}\in\nabla\omega^{*}(\mathbb{R}^{d})$. In fact, for any
$v\in\nabla\omega^{*}(\mathbb{R}^{d})$, there exists $y\in\mathbb{R}^{d}$ such
that $v=\nabla\omega^{*}(\mathbb{R}^{d})$ and hence $y\in\partial\omega(v)$,
which means $v\in{\mathrm{dom}}\,\partial\omega$. Thus,
$\nabla\omega^{*}(\mathbb{R}^{d})\subset{\mathrm{dom}}\,\partial\omega$.

In the case of ${\mathcal{U}}=\mathbb{R}^{d}$, (4.29) holds trivially. In the
case of ${\mathcal{U}}\neq\mathbb{R}^{d}$, we may take $\omega$ to be of the
form $\psi+I_{\mathcal{U}}$ with some convex function $\psi$. Then, (4.29)
also holds because of

$\nabla\omega^{*}(\mathbb{R}^{d})\subset{\mathrm{dom}}\,\omega\subset{\mathcal{U}},$

where the left-hand side inclusion is due to the following observation

$\displaystyle\begin{array}[]{lll}v=\nabla\omega^{*}(y)&\Rightarrow&y\in\partial\omega(v)\\\
&\Rightarrow&v\in\arg\min_{x\in\mathbb{R}^{d}}\\{\omega(x)-\langle
y,x\rangle\\}\\\ &\Rightarrow&v\in{\mathrm{dom}}\,\omega.\end{array}$ (4.33)

For certain setups on the function $\psi$, the reader may refer to Section
4.4.

###  4.3 Related unified framework

Recently, the authors of [19] introduced and analyzed a unified mirror descent
method which unifies both the mirror descent and dual averaging algorithms.
Moreover, they applied it to solving Lipschitz continuous and monotone VI
problems and proposed the unified mirror prox (UMP) method. Their methods and
convergence analysis depend on a multi-valued prox-mapping
$\Pi_{\omega}:\mathbb{R}^{d}\rightrightarrows{\mathcal{U}}\times\mathbb{R}^{d}$.
Concretely, $\Pi_{\omega}(\zeta)$ is the set of couples $(u,\upsilon)$
satisfying

$\displaystyle[left=\empheqlbrace\,]$ $\displaystyle
u=\nabla\omega^{*}(\zeta),$ $\displaystyle\upsilon\in\partial\omega(u),$
$\displaystyle\langle\upsilon-\zeta,u^{\prime}-u\rangle\geq 0,\forall
u^{\prime}\in{\mathcal{U}}.$

With this operator, their UMP can be described as follows:

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\zeta_{k}\in\partial\omega(u_{k}),$ (4.34a)
$\displaystyle\langle\upsilon_{k}-\zeta_{k},u-u_{k}\rangle\leq 0,\forall
u\in{\mathcal{U}},$ (4.34b)
$\displaystyle\bar{u}_{k}=\nabla\omega^{*}(\zeta_{k}-\gamma F(u_{k})),$
(4.34c)
$\displaystyle(u_{k+1},\upsilon_{k+1})\in\Pi_{\omega}(\upsilon_{k}-\gamma
F(\bar{u}_{k})).$ (4.34d)

It was verified that both of Nemirovski’s mirror prox method [33] and
Nesterov’s dual extrapolation [35] method are special cases of UMP.
Interestingly, we find when the mirror mapping function $\omega$ is
specialized to the ${\mathcal{X}}$-regularizer defined in [19], UMP can be
transformed into the scheme (4.27). In other words, they are equivalent in
this special setting. This sounds surprising since they are designed with
different motivations and hence have quite different appearances. We believe
that each of them complements to the other. On one hand, the existing theory
on UMP will help us exploit the mirror EG method more deeply; on the other
hand, the reader may be more familiar with the formulation of the mirror EG
method since it is very similar to the original form of the EG method. The
latter will be highlighted by reformulating Nemirovski’s mirror prox method,
Nesterov’s dual extrapolation method, and the Bregman EG method as special
cases of the mirror EG method.

###  4.4 Specialization

Abstract algorithmic frameworks have been constructed in the previously
subsections. Now, we try to specialize the mirror mapping function $\omega$ so
that concrete algorithmic examples could be discussed. First, we need the
concept of compatible mirror map and its associated properties [19].

######  Definition 4.1.

Let $\psi:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ be a function. Denote
$\mathcal{D}_{\psi}:={\mathrm{int}}{\mathrm{dom}}\,\psi$. We say that $\psi$
is a ${\mathcal{U}}$-compatible _mirror map_ if

  1. 1.

$\psi$ is lower-semicontinous and strictly convex,

  2. 2.

$\psi$ is differentiable on $\mathcal{D}_{\psi}$,

  3. 3.

the gradient of $\psi$ takes all possible values, i.e.
$\nabla\psi(\mathcal{D}_{\psi})=\mathbb{R}^{d}$.

  4. 4.

${\mathcal{U}}\subset\textrm{cl}(\mathcal{D}_{\psi})$,

  5. 5.

${\mathcal{U}}\cap\mathcal{D}_{\psi}\neq\varnothing$.

######  Lemma 4.1.

Let $\psi:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ be a
${\mathcal{U}}$-compatible _mirror map_. Then, we have

  1. (a).

$\nabla\psi^{*}(\mathbb{R}^{d})={\mathrm{int}}{\mathrm{dom}}\,\psi$,

  2. (b).

$\nabla\psi(\nabla\psi^{*}(v))=v,\forall v\in\mathbb{R}^{d}$,

  3. (c).

if $z\in{\mathrm{int}}{\mathrm{dom}}\,\psi$, then
$\arg\min_{u\in{\mathcal{U}}}D_{\psi}(u,z)$ exists and is unique, belonging to
${\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$,

  4. (d).

if $\omega=\psi+I_{\mathcal{U}}$, then $\omega^{*}$ is differentiable on
$\mathbb{R}^{d}$ and $\nabla\psi(u)\in\partial\omega(u),\forall
u\in{\mathrm{int}}{\mathrm{dom}}\,\psi$.

The definition of compatible mirror map and the listed properties above help
us reformulate Nemirovski’s mirror prox method, Nesterov’s dual extrapolation
method, and the operator extrapolation method.

######  Proposition 4.1.

Let $\psi:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ be a
${\mathcal{U}}$-compatible _mirror map_ and let
$u_{0}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$. Describe the
basic steps of Nemirovski’s mirror prox method as follows:

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\bar{u}_{k}=\arg\min_{u\in{\mathcal{U}}}\\{\langle\alpha_{k}F(u_{k}),u\rangle+D_{\psi}(u,u_{k})\\}$
(4.35a) $\displaystyle
u_{k+1}=\arg\min_{u\in{\mathcal{U}}}\\{\langle\alpha_{k}F(\bar{u}_{k}),u\rangle+D_{\psi}(u,u_{k})\\}.$
(4.35b)

Let $\omega:=\psi+I_{\mathcal{U}}$. Then Nemirovski’s mirror prox method can
be equivalently described as

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\bar{u}_{k}=\nabla\omega^{*}(\nabla\psi(u_{k})-\alpha_{k}F(u_{k})),$
(4.36a) $\displaystyle
u_{k+1}=\nabla\omega^{*}(\nabla\psi(u_{k})-\alpha_{k}F(\bar{u}_{k})).$ (4.36b)

Moreover, it is a special case of the mirror EG method with
$u^{*}_{k,i}=\nabla\psi(u_{k}),i=1,2.$

###### Proof.

First, we assume that
$u_{k}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$. Starting
with (4.35a), we derive that

$\displaystyle\begin{array}[]{lll}\bar{u}_{k}&=&\arg\min_{u\in{\mathcal{U}}}\\{\langle\alpha_{k}F(u_{k}),u\rangle+\psi(u)-\langle\nabla\psi(u_{k}),u\rangle\\}\\\
&=&\arg\min_{u\in{\mathcal{U}}}\\{\psi(u)-\langle\nabla\psi(\nabla\psi^{*}(\nabla\psi(u_{k})-\alpha_{k}F(u_{k}))),u\rangle\\}\\\
&=&\arg\min_{u\in{\mathcal{U}}}\\{D_{\psi}(u,\nabla\psi^{*}(\nabla\psi(u_{k})-\alpha_{k}F(u_{k})))\\},\end{array}$
(4.40)

where the second relationship follows from (b) of Lemma 4.1. Using (a) of
Lemma 4.1, we have

$\nabla\psi^{*}(\nabla\psi(u_{k})-\alpha_{k}F(u_{k}))\in{\mathrm{int}}{\mathrm{dom}}\,\psi.$

Thus, from (c) of Lemma 4.1, it follows that
$\bar{u}_{k}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$.
Similarly, we have
$u_{k+1}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$. By
induction and the assumption
$u_{0}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$, we actually
have shown that
$u_{k}\subset{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$. Hence,
$\\{\nabla\psi(u_{k})\\}$ are well-defined. Moreover, from (d) of Lemma 4.1,
we have $\nabla\psi(u_{k})\in\partial\omega(u_{k})$ since
$u_{k}\in{\mathrm{int}}{\mathrm{dom}}\,\psi$.

Using the first-order optimality condition of (4.35a), we obtain

$0\in\partial\omega(\bar{u}_{k})+\alpha_{k}F(u_{k})-\nabla\psi(u_{k}),$

which can be equivalently written as (4.36a) by using Lemma 2.1. Similarly,
(4.35b) is equivalent to (4.36b). The condition
$u_{0}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$ and the form
$\omega=\psi+I_{u}$ ensure (4.33) to hold, partially due to
${\mathrm{int}}{\mathrm{dom}}\,\psi\subset\nabla\omega^{*}(\mathbb{R}^{d})$
from (d) of Lemma 4.1. To show (4.35) is a special case of the mirror EG
method, it remains to show that

$\langle\nabla\psi(U_{k+1})-\nabla\psi(u_{k})+\alpha_{k}F(\bar{u}_{k}),u-u_{k+1}\rangle\geq
0,\forall u\in{\mathcal{U}},$

which is just the first-order optimality condition of (4.35b). This completes
the proof. ∎

######  Proposition 4.2.

Let $\psi:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ be
${\mathcal{U}}$-compatible _mirror map_ and let
$u_{0}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$. Denote
$\omega:=\psi+I_{\mathcal{U}}$. Describe the basic steps of Nesterov’s dual
extrapolation method as follows:

$\displaystyle[left=\empheqlbrace\,]$ $\displaystyle
u_{k}=\nabla\omega^{*}(\upsilon_{k}),$ (4.41a)
$\displaystyle\bar{u}_{k}=\arg\min_{u\in{\mathcal{U}}}\\{\langle\alpha_{k}F(u_{k}),u\rangle+D_{\psi}(u,u_{k})\\}$
(4.41b) $\displaystyle\upsilon_{k+1}=\upsilon_{k}-\alpha_{k}F(\bar{u}_{k}).$
(4.41c)

Then, Nesterov’s dual extrapolation method can be equivalently described as

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\bar{u}_{k}=\nabla\omega^{*}(\nabla\psi(u_{k})-\alpha_{k}F(u_{k})),$
(4.42a) $\displaystyle
u_{k+1}=\nabla\omega^{*}(\upsilon_{k}-\alpha_{k}F(\bar{u}_{k})),$ (4.42b)
$\displaystyle\upsilon_{k+1}=\upsilon_{k}-\alpha_{k}F(\bar{u}_{k}).$ (4.42c)

Moreover, it is a special case of the mirror EG method with
$u^{*}_{k,1}=\nabla\psi(u_{k})$ and $u^{*}_{k,2}=\upsilon_{k}$.

###### Proof.

Repeating the argument in the proof of Proposition 4.1, we deduce (4.42a) from
(4.41b). Using (4.41a) and (4.41c), we deduce that
$u_{k+1}=\nabla\omega^{*}(\upsilon_{k+1})=\nabla\omega^{*}(\upsilon_{k}-\alpha_{k}F(\bar{u}_{k}))$,
which is just (4.42b). Thus, the equivalence between (4.41) and (4.42)
follows. To show that both of them are special cases of the mirror EG method,
it remains to show that

$\langle\upsilon_{k}-\nabla\psi(u_{k}),u-u_{k}\rangle\leq 0,\forall
u\in{\mathcal{U}},$

which follows by observing that $u_{k}=\nabla\omega^{*}(\upsilon_{k})$ implies

$\upsilon_{k}\in\partial\omega(u_{k})=\nabla\psi(u_{k})+N_{\mathcal{U}}(u_{k}),$

where $N_{\mathcal{U}}(u_{k})=\\{y:\langle y,u-u_{k}\rangle\leq 0,\forall
u\in{\mathcal{U}}\\}.$ This completes the proof. ∎

######  Proposition 4.3.

Let $\psi:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ be a
${\mathcal{U}}$-compatible _mirror map_ and let
$u_{0}\in{\mathrm{int}}{\mathrm{dom}}\,\psi\bigcap{\mathcal{U}}$. Denote
$\omega:=\psi+I_{\mathcal{U}}$. Describe the basic steps of operator
extrapolation method as follows:

$u_{k+1}=\arg\min_{u\in{\mathcal{U}}}\\{\langle\alpha_{k}F(u_{k})+\alpha_{k}\beta_{k}(F(u_{k})-F(u_{k-1})),u\rangle+D_{\psi}(u,u_{k})\\}.$
(4.43)

Then, the operator extrapolation method can be equivalently described as

$u_{k+1}=\nabla\omega^{*}(\nabla\psi(u_{k})-\alpha_{k}F(u_{k})-\alpha_{k}\beta_{k}(F(u_{k})-F(u_{k-1}))).$
(4.44)

Moreover, it is a special case of the mirror EP method with
$u^{*}_{k}=\nabla\psi(u_{k})$.

The proof is similar to that of Proposition 4.2; we omit the details here.
Comparing the equivalent reformulations (4.36) and (4.42) with the Bregman EG
method (4.23), we find that the latter is indeed a new algorithm in the sense
it does not need to compute $\nabla\psi(u_{k})$ at all. Also, the Bregman EP
method (4.26) is new, compared with (4.43), in the same sense.

###  4.5 Examplary applications

In this part, we apply our algorithmic frameworks to the constrained saddle
point optimization problem (3.4) with the constraints given by

${\mathcal{X}}=\Delta_{p},{\mathcal{Y}}=\Delta_{q}.$

Thus, the constraint set in the corresponding VI problem (3.1) is
${\mathcal{U}}={\mathcal{X}}\times{\mathcal{Y}}$. We choose
$\omega=\psi+I_{\mathcal{U}}$ with $\psi(u)=\sum u_{i}\ln u_{i}-u_{i}$, whose
conjugate function and gradients can be computed as follows:

$\psi^{*}(v)=\sum_{i}\exp(v_{i}),\nabla\psi(u)=\ln(u),\nabla\psi^{*}(v)=\exp(v).$

Note that the dimensions of variables in the above functions are not indexed
so that the functions could be applied to different dimensions of variables.

In our algorithmic frameworks, the most important ingredient is to compute
$\nabla\omega^{*}$. To do this, we deduce the computing
$u=\nabla\omega^{*}(v)$ with $v\in\mathbb{R}^{p+q}$ being given as follows:

$\displaystyle\begin{array}[]{lll}u&=&\arg\min_{z}\\{\omega(z)-\langle
v,z\rangle\\}\\\ &=&\arg\min_{z\in{\mathcal{U}}}\\{\psi(z)-\langle
v,z\rangle\\}.\end{array}$ (4.47)

Denote $z=(z_{x},z_{y})$ and $v=(v_{x},v_{y})$, where $z_{x}$ means the
subvector of $z$ that lies in ${\mathcal{X}}$. Using the separability of the
objective function and the variables $x,y$. The computing (4.47) can be
transformed into the following two problems:

$\displaystyle x=\arg\min_{z_{x}\in{\mathcal{X}}}\\{\psi(z_{x})-\langle
v_{x},z_{x}\rangle\\},$ (4.48a) $\displaystyle
y=\arg\min_{z_{y}\in{\mathcal{Y}}}\\{\psi(z_{y})-\langle
v_{y},z_{y}\rangle\\}.$ (4.48b)

Both of them can be expressed as Bregman’s projection onto the constrained
sets, since

$\displaystyle\begin{array}[]{lll}x&=\arg\min_{z_{x}\in{\mathcal{X}}}\\{\psi(z_{x})-\langle\nabla\psi(\nabla\psi^{*}(v_{x})),z_{x}\rangle\\}\\\
&=\arg\min_{z_{x}\in{\mathcal{X}}}\\{D_{\psi}(z_{x},\nabla\psi(\nabla\psi^{*}(v_{x})))\\}.\end{array}$
(4.51)

Thus, using the formula in Example 6.15 in [3], we obtain

$x=\frac{\nabla\psi(\nabla\psi^{*}(v_{x}))}{\sum_{i}(\nabla\psi(\nabla\psi^{*}(v_{x})))_{i}},~{}~{}y=\frac{\nabla\psi(\nabla\psi^{*}(v_{y}))}{\sum_{i}(\nabla\psi(\nabla\psi^{*}(v_{y})))_{i}}.$
(4.52)

Now, we are ready to present the following algorithmic schemes for the
constrained saddle point problem. The first is obtained by applying
Nemirovski’s mirror prox method (4.36):

$\displaystyle[left=\empheqlbrace\,]$ $\displaystyle\bar{x}_{k}=\frac{\exp(\ln
x_{k}-\alpha_{k}\nabla_{x}f(x_{k},y_{k}))}{\sum_{i}(\exp(\ln
x_{k}-\alpha_{k}\nabla_{x}f(x_{k},y_{k})))_{i}},~{}\bar{y}_{k}=\frac{\exp(\ln
y_{k}-\alpha_{k}\nabla_{y}f(x_{k},y_{k}))}{\sum_{i}(\exp(\ln
y_{k}-\alpha_{k}\nabla_{y}f(x_{k},y_{k})))_{i}},$ (4.53a) $\displaystyle
x_{k+1}=\frac{\exp(\ln
x_{k}-\alpha_{k}\nabla_{x}f(\bar{x}_{k},\bar{y}_{k}))}{\sum_{i}(\exp(\ln
x_{k}-\alpha_{k}\nabla_{x}f(\bar{x}_{k},\bar{y}_{k})))_{i}},~{}y_{k+1}=\frac{\exp(\ln
y_{k}-\alpha_{k}\nabla_{y}f(\bar{x}_{k},\bar{y}_{k}))}{\sum_{i}(\exp(\ln
y_{k}-\alpha_{k}\nabla_{y}f(\bar{x}_{k},\bar{y}_{k})))_{i}}.$ (4.53b)

The second is obtained by applying Nesterov’s dual extrapolation method
(4.42):

$\displaystyle[left=\empheqlbrace\,]$ $\displaystyle\bar{x}_{k}=\frac{\exp(\ln
x_{k}-\alpha_{k}\nabla_{x}f(x_{k},y_{k}))}{\sum_{i}(\exp(\ln
x_{k}-\alpha_{k}\nabla_{x}f(x_{k},y_{k})))_{i}},~{}\bar{y}_{k}=\frac{\exp(\ln
y_{k}-\alpha_{k}\nabla_{y}f(x_{k},y_{k}))}{\sum_{i}(\exp(\ln
y_{k}-\alpha_{k}\nabla_{y}f(x_{k},y_{k})))_{i}},$ (4.54a) $\displaystyle
x_{k+1}=\frac{\exp(x_{k}^{*}-\alpha_{k}\nabla_{x}f(\bar{x}_{k},\bar{y}_{k}))}{\sum_{i}(\exp(x_{k}^{*}-\alpha_{k}\nabla_{x}f(\bar{x}_{k},\bar{y}_{k})))_{i}},~{}y_{k+1}=\frac{\exp(y_{k}^{*}-\alpha_{k}\nabla_{y}f(\bar{x}_{k},\bar{y}_{k}))}{\sum_{i}(\exp(y_{k}^{*}-\alpha_{k}\nabla_{y}f(\bar{x}_{k},\bar{y}_{k})))_{i}},$
(4.54b)
$\displaystyle(x^{*}_{k+1},y^{*}_{k+1})=(x^{*}_{k},y^{*}_{k})-\alpha_{k}(\nabla_{x}f(\bar{x}_{k},\bar{y}_{k}),-\nabla_{y}f(\bar{x}_{k},\bar{y}_{k})).$
(4.54c)

The third is obtained by applying Bregman EG method (4.23):

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\bar{x}_{k}=\frac{\exp(x_{k}^{*}-\alpha_{k}\nabla_{x}f(x_{k},y_{k}))}{\sum_{i}(\exp(x^{*}_{k}-\alpha_{k}\nabla_{x}f(x_{k},y_{k})))_{i}},~{}\bar{y}_{k}=\frac{\exp(y_{k}^{*}-\alpha_{k}\nabla_{y}f(x_{k},y_{k}))}{\sum_{i}(\exp(y^{*}_{k}-\alpha_{k}\nabla_{y}f(x_{k},y_{k})))_{i}},$
(4.55a) $\displaystyle
x_{k+1}=\frac{\exp(x_{k}^{*}-\alpha_{k}\nabla_{x}f(\bar{x}_{k},\bar{y}_{k}))}{\sum_{i}(\exp(x_{k}^{*}-\alpha_{k}\nabla_{x}f(\bar{x}_{k},\bar{y}_{k})))_{i}},~{}y_{k+1}=\frac{\exp(y_{k}^{*}-\alpha_{k}\nabla_{y}f(\bar{x}_{k},\bar{y}_{k}))}{\sum_{i}(\exp(y_{k}^{*}-\alpha_{k}\nabla_{y}f(\bar{x}_{k},\bar{y}_{k})))_{i}},$
(4.55b)
$\displaystyle(x^{*}_{k+1},y^{*}_{k+1})=(x^{*}_{k},y^{*}_{k})-\alpha_{k}(\nabla_{x}f(\bar{x}_{k},\bar{y}_{k}),-\nabla_{y}f(\bar{x}_{k},\bar{y}_{k})).$
(4.55c)

Denote

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\xi_{k}^{x}:=\alpha_{k}\nabla_{x}f(x_{k},y_{k})+\alpha_{k}\beta_{k}(\nabla_{x}f(x_{k},y_{k})-\nabla_{x}f(x_{k-1},y_{k-1})),$
(4.56a)
$\displaystyle\xi_{k}^{y}:=\alpha_{k}\nabla_{y}f(x_{k},y_{k})+\alpha_{k}\beta_{k}(\nabla_{y}f(x_{k},y_{k})-\nabla_{y}f(x_{k-1},y_{k-1})).$
(4.56b)

Then, the fourth scheme is obtained by applying the operator extrapolation
method (4.43):

$x_{k+1}=\frac{\exp(\ln x_{k}-\xi_{k}^{x})}{\sum_{i}(\exp(\ln
x_{k}-\xi_{k}^{x}))_{i}},~{}y_{k+1}=\frac{\exp(\ln
y_{k}-\xi_{k}^{y})}{\sum_{i}(\exp(\ln y_{k}-\xi_{k}^{y}))_{i}}.$ (4.57)

The last one is obtained by applying the EP method (4.26):

$\displaystyle[left=\empheqlbrace\,]$ $\displaystyle
x_{k+1}=\frac{\exp(x_{k}^{*}-\xi_{k}^{x})}{\sum_{i}(\exp(x_{k}^{*}-\xi_{k}^{x}))_{i}},~{}y_{k+1}=\frac{\exp(y_{k}^{*}-\xi_{k}^{y})}{\sum_{i}(\exp(y_{k}^{*}-\xi_{k}^{y}))_{i}},$
(4.58a)
$\displaystyle(x^{*}_{k+1},y^{*}_{k+1})=(x^{*}_{k},y^{*}_{k})-(\xi_{k}^{x},\xi_{k}^{y}).$
(4.58b)

It should be noted that the choices of parameters $\alpha_{k}$ and $\beta_{k}$
depends on the saddle-point functions.

##  5 Convergence analysis

In this section, we deduce a group of convergence results for the proposed
mirror frameworks.

###  5.1 Convergence analysis for mirror EG method

This part is devoted to the convergence analysis for the mirror EG method. We
first introduce an important lemma.

######  Lemma 5.1.

Suppose that the operator $F$ is $\lambda$-relatively Lipschitz continuous
with respect to $\omega$. Let $\\{\bar{u}_{k},u_{k}\\}_{k\geq 0}$ be generated
by the mirror extragradient method with the step parameters $\alpha_{k}$ and
$\beta$ satisfying $0<\lambda\alpha_{k}\leq\beta$. Then, for any
$u\in{\mathcal{U}}$ we have

$\langle\alpha_{k}F(\bar{u}_{k}),\bar{u}_{k}-u\rangle\leq
D_{\omega}^{u_{k,2}^{*}}(u,u_{k})-D_{\omega}^{u_{k+1,2}^{*}}(u,u_{k+1})+(\beta-1)D_{\omega}^{u_{k,2}^{*}}(u_{k+1},u_{k}).$
(5.1)

Moreover, if $\omega$ is a $\mu_{0}$-strongly convex function with
$L_{0}$-Lipschitz-continuous gradient, then we have the following tight
estimation:

$\frac{\mu_{0}\alpha^{2}_{k}}{2L_{0}^{2}}\|F(\bar{u}_{k})\|_{*}^{2}\leq
D_{\omega}(u_{k+1},u_{k})\leq\frac{\alpha^{2}_{k}}{2\mu_{0}}\|F(\bar{u}_{k})\|_{*}^{2}.$
(5.2)

###### Proof.

It follows from (4.27a) that

$\bar{u}_{k}^{*}:=u^{*}_{k,1}-\frac{\alpha_{k}}{\beta}F(u_{k})\in\partial\omega(\bar{u}_{k}).$

Noting that $u^{*}_{k,1}\in\partial\omega(u_{k})$ and applying Lemma 2.2, for
any $u\in{\mathcal{U}}$ we have that

$\displaystyle\begin{array}[]{lll}\langle\frac{\alpha_{k}}{\beta}F(u_{k}),\bar{u}_{k}-u\rangle&=&\langle
u^{*}_{k,1}-\bar{u}_{k}^{*},\bar{u}_{k}-u\rangle\\\
&=&D_{\omega}^{u_{k,1}^{*}}(u,u_{k})-D_{\omega}^{\bar{u}_{k}^{*}}(u,\bar{u}_{k})-D_{\omega}^{u_{k,1}^{*}}(\bar{u}_{k},u_{k}).\end{array}$
(5.5)

Using (4.27d) and applying Lemma 2.2 again, for any $u\in{\mathcal{U}}$ we
have that

$\displaystyle\begin{array}[]{lll}\langle\alpha_{k}F(\bar{u}_{k}),u_{k+1}-u\rangle&\leq&\langle
u_{k+1,2}^{*}-u^{*}_{k,2},u-u_{k+1}\rangle\\\
&=&D_{\omega}^{u_{k,2}^{*}}(u,u_{k})-D_{\omega}^{u_{k+1,2}^{*}}(u,u_{k+1})-D_{\omega}^{u_{k,2}^{*}}(u_{k+1},u_{k}).\end{array}$
(5.8)

Combining (5.5) with $u=u_{k+1}$ and (5.8), we get

$\displaystyle\begin{array}[]{lll}&&\langle\alpha_{k}F(\bar{u}_{k}),\bar{u}_{k}-u\rangle\\\
&\leq&D_{\omega}^{u_{k,2}^{*}}(u,u_{k})-D_{\omega}^{u_{k+1,2}^{*}}(u,u_{k+1})+\beta
D_{\omega}^{u_{k,1}^{*}}(u_{k+1},u_{k})-D_{\omega}^{u_{k,2}^{*}}(u_{k+1},u_{k})+\\\
&&\alpha_{k}\langle F(\bar{u}_{k})-F(u_{k}),\bar{u}_{k}-u_{k+1}\rangle-\beta
D_{\omega}^{u_{k,1}^{*}}(\bar{u}_{k},u_{k})-\beta
D_{\omega}^{\bar{u}_{k}^{*}}(u_{k+1},\bar{u}_{k}).\end{array}$ (5.12)

From (4.27c) it follows that

$D_{\omega}^{u^{*}_{k,1}}(u_{k+1},u_{k})-D_{\omega}^{u^{*}_{k,2}}(u_{k+1},u_{k})=\langle
u_{k,2}^{*}-u_{k,1}^{*},u_{k+1}-u_{k}\rangle\leq 0.$ (5.13)

Invoking the relatively Lipschitz continuity of $F$ and noting that
$\lambda\alpha_{k}\leq\beta$, we obtain

$\alpha_{k}\langle
F(\bar{u}_{k})-F(u_{k}),\bar{u}_{k}-u_{k+1}\rangle\leq\beta(D_{\omega}^{u_{k,1}^{*}}(\bar{u}_{k},u_{k})-D_{\omega}^{\bar{u}_{k}^{*}}(u_{k+1},\bar{u}_{k})).$
(5.14)

Therefore, (5.1) follows by combining (5.12)-(5.14).

Now, let us show (5.2). Using (4.27d) with $u=u_{k}$ and the strong convexity
of $\omega$, we deduce that

$\displaystyle\begin{array}[]{lll}\langle\alpha_{k}F(\bar{u}_{k}),u_{k}-u_{k+1}\rangle&\geq&\langle
u_{k+1,2}^{*}-u_{k,2}^{*},u_{k+1}-u_{k}\rangle\\\
&=&D_{\omega}^{u^{*}_{k,2}}(u_{k+1},u_{k})+D_{\omega}^{u^{*}_{k+1,2}}(u_{k},u_{k+1})\\\
&\geq&D_{\omega}^{u^{*}_{k,2}}(u_{k+1},u_{k})+\frac{\mu_{0}}{2}\|u_{k}-u_{k+1}\|^{2}.\end{array}$
(5.18)

Using the Cauchy-Schwartz inequality, we have

$\langle\alpha_{k}F(\bar{u}_{k}),u_{k}-u_{k+1}\rangle\leq\frac{\mu_{0}}{2}\|u_{k}-u_{k+1}\|^{2}+\frac{\alpha_{k}^{2}}{2\mu_{0}}\|F(\bar{u}_{k})\|_{*}^{2}.$
(5.19)

Combining (5.18) and (5.19) and using the implied fact that $\omega$ is
differentiable, we obtain

$D_{\omega}(u_{k+1},u_{k})=D_{\omega}^{u^{*}_{k,2}}(u_{k+1},u_{k})\leq\frac{\alpha^{2}_{k}}{2\mu_{0}}\|F(\bar{u}_{k})\|_{*}^{2}.$

It remains to show the left-hand side inequality of (5.2). Note that
$u^{*}_{k,i}=\nabla\omega(u_{k}),i=1,2$. Using (4.27b) and the fact that
$\nabla\omega^{*}=(\nabla\omega)^{-1}$, we have

$\nabla\omega(u_{k+1})=\nabla\omega(u_{k})-\alpha_{k}F(\bar{u}_{k}).$

Finally, using the fact that $\omega$ is a $\mu_{0}$-strongly convex function
with $L_{0}$-Lipschitz-continuous gradient, we derive that

$\|\alpha_{k}F(\bar{u}_{k})\|_{*}^{2}=\|\nabla\omega(u_{k+1})-\nabla\omega(u_{k})\|_{*}^{2}\leq
L_{0}^{2}\|u_{k+1}-u_{k}\|^{2}\leq\frac{2L_{0}^{2}}{\mu_{0}}D_{\omega}(u_{k+1},u_{k}).$

Note that the inequalities in (5.2) become equalities when
$\omega=\frac{1}{2}\|\cdot\|^{2}$, i.e., $\mu_{0}=L_{0}=1$. Hence, the
estimation is tight. This completes the proof. ∎

Now, we state a sublinear convergence guarantee that generalizes the original
result–Theorem 2 in [35] for Nesterov’s dual extrapolation method and the
newly developed result–Theorem 7.4 in [19] for UMP.

######  Theorem 5.1.

Suppose that the operator $F$ is monotone and $\lambda$-relatively Lipschitz
continuous with respect to $\omega$. Let $\\{\bar{u}_{k},u_{k}\\}_{k\geq 0}$
be the iterates generated by the mirror extragradient method with the step
parameters $\alpha_{k}$ and $\beta$ satisfying
$0<\lambda\alpha_{k}\leq\beta\leq 1$. Denote $s_{t}:=\sum_{k=0}^{t}\alpha_{k}$
and $\tilde{u}_{t}:=\frac{1}{s_{t}}\sum_{k=0}^{t}\alpha_{k}\bar{u}_{k}$. Then,
for any $u\in{\mathcal{U}}$ and $t\geq 0$ we have

$\langle
F(u),\tilde{u}_{t}-u\rangle\leq\frac{1}{s_{t}}D_{\omega}^{u^{*}_{0,2}}(u,u_{0}).$
(5.20)

###### Proof.

Summing up (5.1) in Lemma 5.1 from $k=0$ to $t$ and noting that $\beta\leq 1$,
we have

$\sum_{k=0}^{t}\alpha_{k}\langle F(\bar{u}_{k}),\bar{u}_{k}-u\rangle\leq
D_{\omega}^{u^{*}_{0,2}}(u,u_{0}).$ (5.21)

Using the monotonicity of $F$, we derive that

$\displaystyle\begin{array}[]{lll}\langle
F(u),\tilde{u}_{t}-u\rangle&=&\frac{1}{s_{t}}\sum_{k=0}^{t}\langle
F(u),\alpha_{k}(\bar{u}_{k}-u)\rangle\\\
&\leq&\frac{1}{s_{t}}\sum_{k=0}^{t}\alpha_{k}\langle
F(\bar{u}_{k}),\bar{u}_{k}-u\rangle\\\
&\leq&\frac{1}{s_{t}}D_{\omega}^{u^{*}_{0,2}}(u,u_{0}),\end{array}$ (5.25)

which completes the proof. ∎

The result above with $\alpha_{k}\equiv\frac{\beta}{\lambda}$ gives

$\langle F(u),\tilde{u}_{t}-u\rangle\leq\frac{\lambda
D_{\omega}^{u^{*}_{0,2}}(u,u_{0})}{\beta(t+1)},$

which implies that $\tilde{u}_{t}$ tends to a weak solution $\tilde{u}$ with
the convergence rate $\frac{1}{t}$ if ${\mathcal{U}}$ is bounded (the
boundedness could be dropped; see e.g. [43]) However, if $F$ is non-monotone,
then it will make nonsense to find weak solutions for VIs. The following is a
sublinear convergence result on the squared norm of the operator $F$, which
generalizes the result–Theorem 3.2 in [13].

######  Theorem 5.2.

Let $\omega$ be a $\mu_{0}$-strongly convex function with $L_{0}$-Lipschitz-
continuous gradient; denote $\kappa_{0}:=\frac{\mu_{0}}{L_{0}}$. Suppose that
the operator $F$ is $\lambda$-relatively Lipschitz continuous with respect to
$\omega$ and $\rho$-weakly MVI monotone with
$\rho<\frac{\kappa_{0}}{\lambda}$. Let $\\{\bar{u}_{k},u_{k}\\}_{k\geq 0}$ be
the iterates generated by the mirror extragradient method with
$\alpha_{k}\equiv\frac{1}{2\lambda}$ and $\beta=\frac{1}{2}$. Then, there
exists $\hat{u}\in{\mathcal{U}}_{s}$ such that for any $t\geq 0$ we have

$\frac{1}{t+1}\sum_{k=0}^{t}\|F(\bar{u}_{k})\|_{*}^{2}\leq\frac{16\lambda^{2}}{(t+1)(\kappa_{0}-4\lambda\rho)}D_{\omega}(\hat{u},u_{0}).$
(5.26)

In particular, we have

$\min_{0\leq k\leq
t}\|F(\bar{u}_{k})\|_{*}^{2}\leq\frac{16\lambda^{2}}{(t+1)(\kappa_{0}-4\lambda\rho)}D_{\omega}(\hat{u},u_{0}).$
(5.27)

###### Proof.

Using (5.1) in Lemma 5.1, the fact that $\omega$ is $\mu_{0}$-strongly convex
function with $L_{0}$-Lipschitz-continuous gradient, and the $\rho$-weakly
monotone property, we have

$-\frac{\rho}{4\lambda}\|F(\bar{u}_{k})\|_{*}^{2}\leq
D_{\omega}(u,u_{k})-D_{\omega}(u,u_{k+1})-\frac{1}{2}D_{\omega}(u_{k+1},u_{k}).$
(5.28)

Based on the estimation (5.2) in Lemma 5.1, we further get

$\frac{\kappa_{0}-4\lambda\rho}{16\lambda^{2}}\|F(\bar{u}_{k})\|_{*}^{2}\leq
D_{\omega}(u,u_{k})-D_{\omega}(u,u_{k+1}).$ (5.29)

Now, summing up (5.29) from $k=0$ to $t$ gives (5.26). This completes the
proof. ∎

###  5.2 Convergence analysis for mirror EP method

This part is devoted to the convergence analysis for the mirror EP method. We
begin with an important lemma as well.

######  Lemma 5.2.

Let $\\{u_{k}\\}_{k\geq 0}$ be the iterates generated by the mirror
extrapolation method. Denote $\Delta F_{k}:=F(u_{k})-F(u_{k-1})$ and $\Delta
D_{k}(u):=D_{\omega}^{u_{k}^{*}}(u,u_{k})-D_{\omega}^{u_{k+1}^{*}}(u,u_{k+1}).$
Then, for any $u\in{\mathcal{U}}$ and $k\geq 0$ we have

$\displaystyle\begin{array}[]{lll}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle&\leq&\alpha_{k}\langle\Delta
F_{k+1},u_{k+1}-u\rangle-\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u\rangle+\\\ &&\Delta
D_{k}(u)-D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})+\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u_{k+1}\rangle.\end{array}$ (5.32)

###### Proof.

On one hand, it follows from (4.28c) and the notation $\Delta D_{k}(u)$ that

$\displaystyle\begin{array}[]{lll}\langle\xi_{k},u_{k+1}-u\rangle&\leq&\langle
u_{k+1}^{*}-u^{*}_{k},u-u_{k+1}\rangle\\\
&=&D_{\omega}^{u_{k}^{*}}(u,u_{k})-D_{\omega}^{u_{k+1}^{*}}(u,u_{k+1})-D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})\\\
&=&\Delta D_{k}(u)-D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k}).\end{array}$ (5.36)

On the other hand, using (4.28a) and the notation $\Delta F_{k}$, we derive
that

$\displaystyle\begin{array}[]{lll}\langle\xi_{k},u_{k+1}-u\rangle&=&\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle-\alpha_{k}\langle\Delta
F_{k+1},u_{k+1}-u\rangle+\\\ &&\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u\rangle-\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u_{k+1}\rangle.\end{array}$ (5.39)

Combining (5.36) and (5.39), we immediately obtain (5.32). ∎

Now, we state the sublinear convergence for the mirror EP method.

######  Theorem 5.3.

Suppose that the operator $F$ is monotone and $\lambda$-relatively Lipschitz
continuous with respect to $\omega$. Let $\\{u_{k}\\}_{k\geq 0}$ be generated
by the mirror EP method with the initial conditions $u_{0}=u_{-1}$ and the
step parameters $\alpha_{k}$ and $\beta_{k}$ satisfying

$\displaystyle\left\\{\begin{array}[]{lll}\alpha_{k}\beta_{k}=\alpha_{k-1},\\\
\lambda(\alpha_{k}+\alpha_{k-1})\leq 1.\end{array}\right.$ (5.42)

Denote $s_{t}:=\sum_{k=0}^{t}\alpha_{k}$ and
$\tilde{u}_{t}:=\frac{1}{s_{t}}\sum_{k=0}^{t}\alpha_{k}u_{k+1}$. Then, for any
$u\in{\mathcal{U}}$ and $t\geq 0$ we have

$\langle
F(u),\tilde{u}_{t}-u\rangle\leq\frac{1}{s_{t}}D_{\omega}^{u^{*}_{0}}(u,u_{0}).$
(5.43)

###### Proof.

First, using the relatively Lipschitz continuity, we have

$\displaystyle\begin{array}[]{lll}\langle\Delta
F_{k},u_{k}-u_{k+1}\rangle&=&\langle
F(u_{k})-F(u_{k-1}),u_{k}-u_{k+1}\rangle\\\ &\leq&\lambda
D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})+\lambda
D_{\omega}^{u_{k-1}^{*}}(u_{k},u_{k-1}).\end{array}$ (5.46)

Now, using (5.46), (5.32) in Lemma 5.2, and the parameter relations (5.42), we
obtain

$\displaystyle\begin{array}[]{lll}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle&\leq&\alpha_{k}\langle\Delta
F_{k+1},u_{k+1}-u\rangle-\alpha_{k-1}\langle\Delta F_{k},u_{k}-u\rangle+\\\
&&D_{\omega}^{u_{k}^{*}}(u,u_{k})-D_{\omega}^{u_{k+1}^{*}}(u,u_{k+1})+\\\
&&\lambda\alpha_{k-1}D_{\omega}^{u_{k-1}^{*}}(u_{k},u_{k-1})-\lambda\alpha_{k}D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k}).\end{array}$
(5.50)

Summing up (5.50) from $k=0$ to $t$ and noting that $u_{0}=u_{-1}$, we have

$\displaystyle\begin{array}[]{lll}\sum_{k=0}^{t}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle&\leq&\alpha_{t}\langle\Delta
F_{t+1},u_{t+1}-u\rangle+D_{\omega}^{u_{0}^{*}}(u,u_{0})-\\\
&&D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1})-\lambda\alpha_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t}).\end{array}$
(5.53)

Using again the relatively Lipschitz continuity and noting that
$\lambda\alpha_{t}\leq 1$, we have

$\alpha_{t}\langle\Delta F_{t+1},u_{t+1}-u\rangle\leq
D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1})+\lambda\alpha_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t}).$

Thus, we get

$\sum_{k=0}^{t}\alpha_{k}\langle F(u_{k+1}),u_{k+1}-u\rangle\leq
D_{\omega}^{u_{0}^{*}}(u,u_{0}).$ (5.54)

Finally, using the monotonicity of $F$, we derive that

$\displaystyle\begin{array}[]{lll}\langle
F(u),\tilde{u}_{t}-u\rangle&=&\frac{1}{s_{t}}\sum_{k=0}^{t}\langle
F(u),\alpha_{k}(u_{k+1}-u)\rangle\\\
&\leq&\frac{1}{s_{t}}\sum_{k=0}^{t}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle\\\
&\leq&\frac{1}{s_{t}}D_{\omega}^{u^{*}_{0}}(u,u_{0}).\end{array}$ (5.58)

This completes the proof. ∎

We are now ready to show the linear convergence of the mirror EP method for
relatively Lipschitiz and relatively restricted monotone VIs, partially
inspired by the recent works [29, 23].

######  Theorem 5.4.

Suppose that the operator $F$ is $\lambda$-relatively Lipschitz continuous and
$\mu$-relatively restricted monotone with respect to $\omega$ and the
condition number of $F$ is denoted by $\kappa:=\frac{\mu}{\lambda}$. Let
$\\{u_{k}\\}_{k\geq 0}$ be generated by the mirror EP method with the initial
conditions $u_{0}=u_{-1}$ and the step parameters $\alpha_{k}$ and $\beta_{k}$
satisfying

$\displaystyle[left=\empheqlbrace\,]$
$\displaystyle\alpha_{k}\beta_{k}\gamma_{k}=\alpha_{k-1}\gamma_{k-1},$ (5.59a)
$\displaystyle\gamma_{k}\leq\gamma_{k-1}(1+2\mu\alpha_{k-1}),$ (5.59b)
$\displaystyle\lambda(\alpha_{k}+\alpha_{k}\beta_{k})\leq 1,$ (5.59c)
$\displaystyle 1+2\alpha_{k}\mu-\alpha_{k}\lambda\geq 0.$ (5.59d)

Then, for any $u\in{\mathcal{U}}$ and $t\geq 0$ we have

$D_{\omega}^{u^{*}_{t+1}}(u,u_{t+1})\leq\frac{\gamma_{0}D_{\omega}^{u^{*}_{0}}(u,u_{0})}{\gamma_{t}(1+2\mu\alpha_{t}-\lambda\alpha_{t})}.$
(5.60)

In particular, if $\alpha_{k}\equiv\frac{\theta}{2\lambda}$ and
$\beta_{k}\equiv\beta$ with $\theta>0,\beta>0$ that satisfy the conditions
(5.59a)-(5.59d), then the best convergence rate, obtained by setting
$\theta=\theta_{0}$ and $\beta=\frac{1}{1+\kappa\theta_{0}}$ with
$\theta_{0}=\frac{\kappa-1+\sqrt{1+\kappa^{2}}}{\kappa}$, reads as

$D_{\omega}^{u^{*}_{t+1}}(u,u_{t+1})\leq(\sqrt{1+\kappa^{2}}-\kappa)^{t+1}(2+\frac{1}{\kappa})D_{\omega}^{u^{*}_{0}}(u,u_{0}).$
(5.61)

###### Proof.

Multiplying (5.32) in Lemma 5.2 with $\gamma_{k}$, we obtain

$\displaystyle\begin{array}[]{lll}\gamma_{k}\Delta
D_{k}(u)&\geq&\gamma_{k}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle-\gamma_{k}\alpha_{k}\langle\Delta
F_{k+1},u_{k+1}-u\rangle+\\\ &&\gamma_{k}\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u\rangle+\gamma_{k}D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})-\gamma_{k}\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u_{k+1}\rangle.\end{array}$ (5.64)

Summing up (5.64) from $k=0$ to $t$, using the relationship (5.59a), and
noting that $\Delta F_{0}=0$, we derive that

$\displaystyle\begin{array}[]{lll}\sum_{k=0}^{t}\gamma_{k}\Delta
D_{k}(u)&\geq&\sum_{k=0}^{t}\left[\gamma_{k}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle\right]-\gamma_{t}\alpha_{t}\langle\Delta
F_{t+1},u_{t+1}-u\rangle+S_{t},\end{array}$ (5.66)

where

$S_{t}:=\sum_{k=0}^{t}\left[\gamma_{k}D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})-\gamma_{k}\alpha_{k}\beta_{k}\langle\Delta
F_{k},u_{k}-u_{k+1}\rangle\right].$

Invoking the relatively Lipschitz continuity to yield

$\displaystyle\begin{array}[]{lll}\langle\Delta
F_{k},u_{k}-u_{k+1}\rangle\leq\lambda
D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})+\lambda
D_{\omega}^{u_{k-1}^{*}}(u_{k},u_{k-1}).\end{array}$ (5.68)

Thus, we can derive that

$\displaystyle\begin{array}[]{lll}S_{t}&\geq&\sum_{k=0}^{t}\left[(\gamma_{k}-\alpha_{k}\beta_{k}\gamma_{k}\lambda)D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})-\alpha_{k}\beta_{k}\gamma_{k}\lambda
D_{\omega}^{u_{k-1}^{*}}(u_{k},u_{k-1})\right]\\\
&=&\sum_{k=0}^{t}\left[\mu_{k}D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})-\nu_{k}D_{\omega}^{u_{k-1}^{*}}(u_{k},u_{k-1})\right]\\\
&=&\sum_{k=0}^{t-1}\left[(\mu_{k}-\nu_{k+1})D_{\omega}^{u_{k}^{*}}(u_{k+1},u_{k})\right]+\mu_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t}),\end{array}$
(5.72)

where $\mu_{k}=\gamma_{k}-\alpha_{k}\beta_{k}\gamma_{k}\lambda$ and
$\nu_{k}=\alpha_{k}\beta_{k}\gamma_{k}\lambda$. Using the relationships
(5.59a) and (5.59c), we derive that

$\displaystyle\begin{array}[]{lll}\mu_{k}-\nu_{k+1}&=&\gamma_{k}-\alpha_{k}\beta_{k}\gamma_{k}\lambda-\alpha_{k+1}\beta_{k+1}\gamma_{k+1}\lambda\\\
&=&\gamma_{k}-\alpha_{k}\beta_{k}\gamma_{k}\lambda-\alpha_{k}\gamma_{k}\lambda\geq
0.\end{array}$ (5.75)

Thereby, it follows from (5.72) that

$S_{t}\geq\mu_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t}).$ (5.76)

Now, combining (5.66) and (5.76), we obtain

$\displaystyle\begin{array}[]{lll}\sum_{k=0}^{t}\gamma_{k}\Delta
D_{k}(u)&\geq&\sum_{k=0}^{t}\left[\gamma_{k}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle\right]-\\\ &&\gamma_{t}\alpha_{t}\langle\Delta
F_{t+1},u_{t+1}-u\rangle+\mu_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t}).\end{array}$
(5.79)

Invoking the relatively Lipschitz continuity again, we derive that

$\displaystyle\begin{array}[]{lll}&&-\gamma_{t}\alpha_{t}\langle\Delta
F_{t+1},u_{t+1}-u\rangle+\mu_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t})\\\
&\geq&-\alpha_{t}\gamma_{t}\lambda
D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t})-\alpha_{t}\gamma_{t}\lambda
D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1})+\mu_{t}D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t})\\\
&=&(\mu_{t}-\alpha_{t}\gamma_{t}\lambda)D_{\omega}^{u_{t}^{*}}(u_{t+1},u_{t})-\alpha_{t}\gamma_{t}\lambda
D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1}).\end{array}$ (5.83)

Note that from (5.59c), we have

$\mu_{t}-\alpha_{t}\gamma_{t}\lambda=\gamma_{t}-\alpha_{t}\beta_{t}\gamma_{t}\lambda-\alpha_{t}\gamma_{t}\lambda\geq
0.$

Thus, combining (5.79), (5.83), and using the relatively restricted
monotonicity, we derive that

$\displaystyle\begin{array}[]{lll}\sum_{k=0}^{t}\gamma_{k}\Delta
D_{k}(u)&\geq&\sum_{k=0}^{t}\left[\gamma_{k}\alpha_{k}\langle
F(u_{k+1}),u_{k+1}-u\rangle\right]-\alpha_{t}\gamma_{t}\lambda
D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1})\\\
&\geq&\sum_{k=0}^{t}\left[2\alpha_{k}\gamma_{k}\mu
D_{\omega}^{u_{k+1}^{*}}(u,u_{k+1})\right]-\alpha_{t}\gamma_{t}\lambda
D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1}).\end{array}$ (5.86)

Now, using the expression of $\Delta D_{k}(u)$ and (5.59b), we further derive
that

$\displaystyle\begin{array}[]{lll}&&\sum_{k=0}^{t}\left[(\gamma_{k}+2\alpha_{k}\gamma_{k}\mu)D_{\omega}^{u_{k+1}^{*}}(u,u_{k+1})\right]-\alpha_{t}\gamma_{t}\lambda
D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1})\\\
&\leq&\sum_{k=0}^{t}\gamma_{k}D_{\omega}^{u_{k}^{*}}(u,u_{k})=\gamma_{0}D_{\omega}^{u_{0}^{*}}(u,u_{0})+\sum_{k=1}^{t}\gamma_{k}D_{\omega}^{u_{k}^{*}}(u,u_{k})\\\
&\leq&\gamma_{0}D_{\omega}^{u_{0}^{*}}(u,u_{0})+\sum_{k=1}^{t}(\gamma_{k-1}+2\alpha_{k-1}\gamma_{k-1}\mu)D_{\omega}^{u_{k}^{*}}(u,u_{k})\\\
&\leq&\gamma_{0}D_{\omega}^{u_{0}^{*}}(u,u_{0})+\sum_{k=0}^{t-1}(\gamma_{k}+2\alpha_{k}\gamma_{k}\mu)D_{\omega}^{u_{k+1}^{*}}(u,u_{k+1}).\end{array}$
(5.91)

Thereby,

$(\gamma_{t}+2\alpha_{t}\gamma_{t}\mu-\alpha_{t}\gamma_{t}\lambda)D_{\omega}^{u_{t+1}^{*}}(u,u_{t+1})\leq\gamma_{0}D_{\omega}^{u_{0}^{*}}(u,u_{0}).$
(5.92)

This together with (5.59d) implies (5.60).

It remains to determine the best convergence rate when the parameters
$\alpha_{k},\beta_{k}$ are fixed constants with the form of
$\alpha_{k}\equiv\frac{\theta}{2\lambda}$ and $\beta_{k}\equiv\beta$. In such
setting, it follows from (5.59a) that

$\gamma_{k}=\frac{1}{\beta}\gamma_{k-1}=\cdots=\left(\frac{1}{\beta}\right)^{k}\gamma_{0}.$

Now, eliminating $\gamma_{k}$ from (5.59b) and using (5.59c)-(5.59d), we get

$\displaystyle[left=\empheqlbrace\,]$ $\displaystyle\frac{1}{\beta}\leq
1+\kappa\theta,$ (5.93a) $\displaystyle\theta\beta\leq 2-\theta,$ (5.93b)
$\displaystyle 1+\kappa\theta-\frac{\theta}{2}\geq 0.$ (5.93c)

From (5.93b), we observe that $\theta\leq 2$. Thus, a product of (5.93a) and
(5.93b) shows that the parameter $\theta$ must satisfy the inequality

$\theta\leq(2-\theta)(1-\kappa\theta),$

from which it must hold that

$0<\theta\leq\theta_{0}:=\frac{\kappa-1+\sqrt{1+\kappa^{2}}}{\kappa}.$

Note that $\theta\leq\theta_{0}<2$ ensures (5.93c) to hold. Therefore,
$\theta_{0}$ is the largest possible value of $\theta$ that satisfies
(5.93a)-(5.93c). Hence, we could use (5.93a) and (5.93b) to bound $\beta$ as
follows.

$\frac{1}{1+\kappa\theta_{0}}\leq\frac{1}{1+\kappa\theta}\leq\beta\leq\frac{2}{\theta}-1.$

Thus, the smallest possible value of $\beta$ is
$\frac{1}{1+\kappa\theta_{0}}$, which corresponds to the best convergence rate
by observing that $\frac{\gamma_{0}}{\gamma_{k}}=\beta^{k}$. Finally, after
some simple relaxations, we could get

$\frac{1}{1+2\mu\alpha_{t}-\lambda\alpha_{t}}\leq 2+\frac{1}{\kappa}.$

Thereby, we obtain (5.61). This completes the proof. ∎

######  Remark 5.1.

If $\omega$ is differentiable and 1-strongly convex and $F$ is
$\lambda$-Lipschitz continuous and $\mu$-relatively restricted monotone with
respect to $\omega$, then the authors of [23] obtained the convergence result

$D_{\omega}(u,u_{t+1})\leq(\frac{1}{1+\kappa})^{t+1}(1+\frac{1}{\kappa})D_{\omega}^{u^{*}_{0}}(u,u_{0}),$
(5.94)

for the OE method (4.3) by taking
$\alpha_{t}\equiv\frac{1}{2\lambda},\beta_{t}\equiv\frac{1}{1+\kappa}$; the
corresponding extrapolation value is
$\alpha_{t}\beta_{t}=\frac{1}{2\lambda(1+\kappa)}$. Our convergence rate in
Theorem 5.4 specialized to the OE method (4.3) is better since

$\sqrt{1+\kappa^{2}}-\kappa=\frac{1}{\sqrt{1+\kappa^{2}}+\kappa}<\frac{1}{1+\kappa}.$

The reason may lie in that we choose larger step sizes
$\alpha_{t}\equiv\frac{\theta_{0}}{2\lambda}$ and larger extrapolation value
since in our setting

$\alpha_{t}\beta_{t}=\frac{1}{2\lambda(1+\kappa)}\frac{\theta_{0}+\kappa\theta_{0}}{1+\kappa\theta_{0}}>\frac{1}{2\lambda(1+\kappa)},$

by noting $\theta_{0}>1$.

##  6 Conclusion

In this study, we introduced two unified algorithmic frameworks–mirror EG and
EP methods for solving relatively Lipschitz and generalized monotone VIs. The
proposed frameworks provide us with equivalent formulations, similar to the
original EG method, for the well-known Nemirovski’s mirror prox method and
Nesterov’s dual extrapolation method as well as the Bregman EG method. The
equivalent formulations help us clearly see the essential difference between
these methods. Theoretically, we are able to analyze (or even improve) the
convergence for all these methods in a unified way with currently weakest
assumptions. Nevertheless, the convergence theory is far from completion. For
example, it is unclear whether one could derive linear convergence for the
mirror EG method under the relatively restricted monotonicity, and derive
sublinear convergence in the sense of (5.26) in Theorem 5.2 for the mirror EP
method under the weakly MVI monotone assumption. Moreover, the research
directions, briefly described below, may be considered as future work as well.

It is wel-known that VIs can be reformulated as monotone inclusions. Recently,
the author of [29] proposed the forward-reflected-backward (FRB) splitting for
approximating a solution to monotone inclusions and showed its linear
convergence under Lipschitz continuity and strong monotonicity. One of the
main contributions made in [29] is that the authors could relax the
cocoercivity assumption to Lipschitz continuity. Since the FRB splitting
shares the same extrapolation technique with the operator extrapolation method
in [23], we wonder whether the Lipschitz continuity and strong monotonicity
assumed by FRB for linear convergence can be relaxed into relative versions.

A slightly more general VIs than (3.1) is to find a point $\hat{u}$ such that

$\langle F(\hat{u}),u-\hat{u}\rangle+r(u)-r(\hat{u})\geq 0,\forall
u\in{\mathcal{U}},$ (6.1)

where $r$ is a proper lower semicontinuous convex function, usually played a
regularization role. The entropy-regularized constrained saddle-point problem
[31, 9] can be reformulated as its special case. We wonder whether our
proposed mirror frameworks could be extended to study (6.1).

Last but not least, it would be interesting to extend our results to
stochastic VIs.

## Acknowledgements

The first author was supported by the National Science Foundation of China
(No.11971480), the Natural Science Fund of Hunan for Excellent Youth
(No.2020JJ3038), and the Fund for NUDT Young Innovator Awards (No. 20190105).
The second author was supported by the Natural Science Foundation of China
(Nos. 11991020, 11631013, 12021001, 11971372 and 11991021) and the Strategic
Priority Research Program of Chinese Academy of Sciences (No. XDA27000000).

## References

  * [1] W. Azizian, F. Iutzeler, J. Malick, and P. Mertikopoulos, The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities, in COLT 2021: The 34th Annual Conference on Learning Theory, 2021.
  * [2] H. H. Bauschke, J. Bolte, and M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications, Math. Oper. Res., 42 (2016), pp. 330–348.
  * [3] H. H. Bauschke and J. M. Borwein, Legendre functions and the method of random Bregman projections, Journal of Convex Analysis, 4 (1997), pp. 27–67.
  * [4] H. H. Bauschke, W. M. Moursi, and X. Wang, Generalized monotone operators and their averaged resolvents, Mathematical Programming, (2020), pp. 1–20.
  * [5] A. Beck, First-Order Methods in Optimization, SIAM-Society for Industrial and Applied Mathematicsq, 2017.
  * [6] A. Beck and M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters, 31 (2003), pp. 167–175.
  * [7] L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, Ussr Computational Mathematics and Mathematical Physics, 7 (1967), pp. 200–217.
  * [8] S. Bubeck, Convex optimization: Algorithms and complexity, Foundations and Trends in Machine Learning, 8 (2014), pp. 231–357.
  * [9] S. Cen, Y. Wei, and Y. Chi, Fast policy extragradient methods for competitive games with entropy regularization., arXiv: Optimization and Control, (2021).
  * [10] Y. Censor, A. Gibali, and S. Reich, The subgradient extragradient method for solving variational inequalities in Hilbert space, J. Optim. Theory. Appl., 148 (2011), pp. 318–335.
  * [11] M. B. Cohen, A. Sidford, and K. Tian, Relative Lipschitzness in extragradient methods and a direct recipe for acceleration, arXiv:2011.06572 [math.OC], (2020).
  * [12] C. D. Dang and G. Lan, On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators, Comput. Optim. Appl., 60 (2015), pp. 277–310.
  * [13] J. Diakonikolas, C. Daskalakis, and M. I. Jordan, Efficient methods for structured nonconvex-nonconcave min-max optimization, arXiv:2011.00364 [math.OC], (2020).
  * [14] F. Facchinei and J. S. Pang, Finite-dimensional variational inequalities and complementarity problems, Springer-Verlag New York, 2003.
  * [15] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien, A variational inequality perspective on generative adversarial networks, in International Conference on Learning Representations, 2018.
  * [16] B. Grimmer, H. Lu, P. Worah, and V. Mirrokni, The landscape of the proximal point method for nonconvex-nonconcave minimax optimization, 2021.
  * [17] J.-B. Hiriart-Urruty and C. Lemarechal, Foundations of convex analysis, Springer-Verlag Publishers, 2004.
  * [18] Y.-G. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos, On the convergence of single-call stochastic extra-gradient methods, in Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, eds., vol. 32, Curran Associates, Inc., 2019.
  * [19] A. Juditsky, J. Kwon, and . Moulines, Unifying mirror descent and dual averaging, arXiv:1910.13742v2[math.OC], (2019).
  * [20] K. C. Kiwiel, Free-steering relaxation methods for problems with strictly convex costs and linear constraints, Math. Oper. Res., 22 (1997), pp. 326–349.
  * [21] , Proximal minimization methods with generalized Bregman functions, SIAM J. Control Optim., 35 (1997), p. 1142 C1168.
  * [22] G. M. Korpelevich, An extragradient method for finding saddle points and for other problems., Matecon, 12 (1976), pp. 747–756.
  * [23] G. Kotsalis, G. Lan, and L. Tianjiao, Simple and optimal methods for stochastic variational inequalities, I: Operator extrapolation, arXiv:2011.02987v3 [math.OC], (2020).
  * [24] M.-J. Lai and W. Yin, Augmented $\ell_{1}$ and nuclear-norm models with a globally linearly convergent algorithm, SIAM J. Imaging Sci., 6 (2013), pp. 1059–1091.
  * [25] S. Lee and D. Kim, Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems, arXiv preprint arXiv:2106.02326, (2021).
  * [26] M. Liu, H. Rafique, Q. Lin, and T. Yang, First-order convergence theory for weakly-convex-weakly-concave min-max problems, Journal of Machine Learning Research, 22 (2021), pp. 1–34.
  * [27] H. Lu, R. M. Freund, and Y. Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim., 28 (2018), pp. 333–354.
  * [28] C. J. Maddison, D. Paulin, Y. W. Teh, and A. Doucet, Dual space preconditioning for gradient descent, SIAM Journal on Optimization, 31 (2021), pp. 991–1016.
  * [29] Y. Malitsky and M. K. Tam, A forward-backward splitting method for monotone inclusions without cocoercivity, SIAM J. Optim., 30 (2020), pp. 1451–1472.
  * [30] Y. V. Malitsky, Projected reflected gradient methods for monotone variational inequalities, Siam Journal on Optimization, 25 (2015), pp. 502–520.
  * [31] P. Mertikopoulos and W. H. Sandholm, Learning in games via reinforcement and regularization, Mathematics of Operations Research, 41 (2016), pp. 1297–1324.
  * [32] I. Necoara, Y. E. Nesterov, and F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Mathematical Programming, 175 (2019), pp. 69–107.
  * [33] A. S. Nemirovski, 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 (2004), pp. 229–251.
  * [34] A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, John Wiley and Sons, Chichester, 1983.
  * [35] Y. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems, Mathematical Programming, 109 (2007), pp. 319–344.
  * [36] L. D. Popov, A modification of the arrow-hurwicz method for search of saddle points, Mathematical Notes, 28 (1980), pp. 845–848.
  * [37] D. Reem, S. Reich, and A. R. D. Pierro, Re-examination of bregman functions and new properties of their divergences, Optimization, 68 (2019), pp. 279–348.
  * [38] R. T. Rockafellar, Convex Analysis, Princeton University Press, 2015\.
  * [39] J. Sherman, Area-convexity, $\ell_{\infty}$ regularization, and undirected multicommodity flow, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 452–460.
  * [40] P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38, pp. 431–446.
  * [41] C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo, Linear last-iterate convergence in constrained saddle-point optimization, in ICLR 2021: The Ninth International Conference on Learning Representations, 2021.
  * [42] H. Zhang, The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth, Optimization Letters, 11 (2017), pp. 817–833.
  * [43] H. Zhang, Extragradient and extrapolation methods with generalized bregman distances for saddle point problems, arXiv:2101.09916v3[math.OC], (2021).
  * [44] H. Zhang and W. Yin, Gradient methods for convex minimization: better rates under weaker conditions, CAM Report 13-17, UCLA, (2013).
  * [45] Z. Zhou, P. Mertikopoulos, N. Bambos, S. P. Boyd, and P. W. Glynn, Stochastic mirror descent in variationally coherent optimization problems, in NIPS ’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, vol. 30, 2017, pp. 7040–7049.