# Accelerated Minimax Algorithms Flock Together

TaeHo Yoon
Department of Mathematical Sciences
Seoul National University
<EMAIL_ADDRESS>
&Ernest K. Ryu
Department of Mathematical Sciences
Seoul National University
<EMAIL_ADDRESS>
###### Abstract

Several new accelerated methods in minimax optimization and fixed-point
iterations have recently been discovered, and, interestingly, they rely on a
mechanism distinct from Nesterov’s momentum-based acceleration. In this work,
we show that these accelerated algorithms exhibit what we call the merging
path (MP) property; the trajectories of these algorithms merge quickly. Using
this novel MP property, we establish point convergence of existing accelerated
minimax algorithms and derive new state-of-the-art algorithms for the
strongly-convex-strongly-concave setup and for the prox-grad setup.

##  1 Introduction

Minimax optimization problems of the form

$\displaystyle\underset{x\in{\mathcal{X}}}{\textrm{minimize}}\,\,\underset{y\in{\mathcal{Y}}}{\textrm{maximize}}\,\,\,\,\mathbf{L}(x,y)$
(1)

have recently received increased attention in many machine learning
applications including robust optimization [86], adversarial training [55],
fair machine learning [29], and GANs [32]. Consequently, there has been a
large body of research on efficient algorithms for solving minimax
optimization. For the deterministic smooth convex-concave setup, the classical
extragradient (EG) [47] and the optimistic gradient descent (OG) [78, 80, 21]
methods converge with $\mathcal{O}(1/k)$ rate on the squared gradient norm
[85, 33], and accelerated algorithms [100, 49, 92] with $\mathcal{O}(1/k^{2})$
rate, based on an _anchoring_ mechanism retracting iterates toward the initial
point, were recently discovered.

In a different line of work on the fixed-point problem

$\displaystyle\begin{array}[]{cc}\underset{z\in\mathbb{R}^{d}}{\textrm{find}}&z={\varbbT}(z),\end{array}$
(3)

the Halpern iteration [35], which averages the iterates with the initial
point, was shown to achieve an accelerated $\mathcal{O}(1/k^{2})$ rate on the
squared fixed-point residual norm when executed with optimal parameters [51,
43]. Interestingly, both the Halpern iteration and the accelerated minimax
algorithms rely on the anchoring mechanism, but a precise theoretical
explanation of such apparent similarity was, to the best of our knowledge, yet
missing.

(a) Divergent paths of AGM ($\alpha=0.025$)

(b) Merging paths of anchored methods ($\alpha=0.1$)

Figure 1: Trajectories of (left) Nesterov’s accelerated algorithms (AGM [69,
8, 11]; described in Appendix A.2) with distinct momentum parameters and
(right) anchoring-based algorithms. On the right, paths quickly merge and
become indistinguishable in 50 iterations. All algorithms are executed on the
convex minimzation problem with $f(x_{1},x_{2})=\frac{4x_{1}^{2}}{x_{2}}$,
starting at $(x_{1},x_{2})=(-2,3)$.

#### Contribution.

In this work, we identify the _merging path (MP) property_ among anchoring-
based algorithms, which state that the trajectories of these algorithms
quickly merge, and use this novel property to develop new accelerated
algorithms. First, we show that known accelerated minimax algorithms [100, 49,
92] have $\mathcal{O}(1/k^{2})$-merging paths with the optimized Halpern
iteration [35, 51] and thereby identify their point convergence. Second, we
present a new accelerated minimax algorithm for smooth strongly-convex-
strongly-concave setup designed to approximate, in the MP sense, the OC-
Halpern method, which has an optimal accelerated rate. Third, we present a
near-optimal accelerated proximal gradient type algorithm, designed to
approximate, in the MP sense, the Halpern-accelerated Douglas-Rachford
splitting [27, 53].

###  1.1 The merging path (MP) property

Let $\mathfrak{A}$ be a deterministic algorithm. Write
$\mathfrak{A}(x_{0};{\mathcal{P}})=(x_{0},x_{1},x_{2},\dots)$ to denote that
$\mathfrak{A}$ applied to problem ${\mathcal{P}}$ with starting point $x_{0}$
produces iterates $x_{1},x_{2},\dots$. We say two algorithms
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ have $\mathcal{O}(r(k))$-_merging
paths_ if for any problem ${\mathcal{P}}$ and $x_{0}\in\mathbb{R}^{d}$, the
iterates
$\mathfrak{A}_{\ell}(x_{0};{\mathcal{P}})=\big{(}x_{0},x_{1}^{(\ell)},x_{2}^{(\ell)},\dots\big{)}$
for $\ell=1,2$ satisfy
$\big{\|}x_{k}^{(1)}-x_{k}^{(2)}\big{\|}^{2}=\mathcal{O}(r(k))$. More
concisely, we say $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are
$\mathcal{O}(r(k))$-MP if they have $\mathcal{O}(r(k))$-merging paths.

The MP property precisely formalizes a notion of near-equivalence of
algorithms. In particular, it is a stronger notion of approximation compared
to the conceptual ones of prior work [63, 1]. Classical first-order algorithms
for smooth convex minimization are not $\mathcal{O}(r(k))$-MP with
$r(k)\rightarrow 0$. Figure 1 shows that accelerated gradient methods with
different momentum coefficients have divergent paths, even though their
function values (of course) converge to the same optimal value. In this paper,
we show that the accelerated minimax algorithms for smooth convex-concave
minimax optimization are $\mathcal{O}(1/k^{2})$-MP (which is faster than the
$o(1)$-point convergence). Figure 1(b) shows that the algorithms’ paths indeed
merge far before they converge to the limit.

###  1.2 Related work

#### An overview of convex-concave minimax optimization.

The extragradient (EG) [47] and Popov’s algorithm [78], also known as
optimistic gradient (OG) descent [80, 21], have initiated the long stream of
research in the optimization literature on the closely interconnected topics
of minimax optimization [68, 38, 46, 61, 63, 64, 5, 36], variational
inequalities [74, 71, 73, 42, 9, 10, 59, 56, 16, 40, 57], and monotone
inclusion problems [87, 93, 65, 66, 54]. A number of advances in minimax
optimization have been made in the context of practical machine learning
applications, including the multi-player game dynamics [20, 88, 31, 39] and
GANs [97, 30, 14, 50, 61, 85, 77]. A recent trend of the field focuses on
achieving near-optimal efficiency with respect to primal-dual gap or distance
to the optimum for convex-concave minimax problems with distinct strong
convexity, strong concavity and smoothness parameters for each variable [91,
52, 95, 2, 99, 41].

#### Proximal point methods and proximal approximation approaches.

The proximal point method (PPM) [67, 60, 83] is an implicit algorithm for
solving convex minimization, minimax optimization, and, more generally,
monotone inclusion problems. Although PPM is not always directly applicable,
it has been used as the conceptual basis for developing many algorithms with
approximate proximal evaluations [82, 34, 87, 68, 37, 13, 28, 23, 79]. Several
prior works [63, 1] interpreted prominent forward algorithms such as
Nesterov’s accelerated gradient method (AGM), EG, and OG as conceptual
approximations of PPM.

#### Acceleration with respect to gradient norm.

Since the seminal work of Nesterov [69], acceleration of first-order
algorithms has been extensively studied for convex minimization problems [70,
8, 44, 6, 75, 89]. Lately, there has been a rapid progress in the discovery of
accelerated algorithms with respect to the gradient magnitude of the objective
for smooth convex problems [45, 72, 26, 48, 101] and smooth convex-concave
minimax problems [24, 100, 49, 92]. Acceleration of PPM has been achieved for
convex minimization [34] and more recently for monotone inclusions in terms of
the fixed-point residual [43, 76]. Notably, the latter has been shown [76, 84]
to be an instance of the Halpern iteration [35] with optimal parameters [51].
While the accelerated minimax algorithms bear an apparent resemblance to the
Halpern iteration [24, 92], the latest results with optimal rates [100, 49,
92] were not formally understood through this connection.

#### Composite minimax problems and prox-grad-type algorithms.

The particular case of bilinearly-coupled minimax problems,
$\mathbf{L}(x,y)=f(x)+\langle x,Ay\rangle-g(y)$ for some convex functions $f$
and $g$ and a linear operator $A$, have been studied by many researchers. A
line of works [70, 96, 90] considered the setups where $f$ and $g$ are smooth
and one can only access their gradients. Another line of works, more closely
connected to the setup we study in Section 5, considered the cases when $f$ or
$g$ is proximable, and used primal-dual splitting algorithms to solve those
problems [12, 18, 94, 15, 38, 46, 98, 84]. Primal-dual problem setups can
often be reformulated into a more flexible format of composite monotone
inclusion problems and addressed via forward-backward splitting algorithms
[93, 17, 18, 56, 19, 58], which also extend the prox-grad-type methods
including the iterative shrinkage-thresholding algorithms (ISTA) [22, 8]. Our
result of Section 5 can be understood as acceleration of forward-backward
algorithms with respect to the forward-backward residual, which generalizes
the gradient magnitude. For the special case of the projected-gradient setup,
the prior work [24] has also achieved a near-optimal acceleration.

##  2 Background and preliminaries

#### Convex-concave functions and minimax optimization.

A function
$\mathbf{L}(\cdot,\cdot):{\mathcal{X}}\times{\mathcal{Y}}\to\mathbb{R}$ is
_convex-concave_ if ${\mathcal{X}}$ and ${\mathcal{Y}}$ are convex sets,
$\mathbf{L}(x,y)$ is convex as a function of $x$ for all $y$, and
$\mathbf{L}(x,y)$ is concave as a function of $y$ for all $x$. A point
$(x_{\star},y_{\star})\in{\mathcal{X}}\times{\mathcal{Y}}$ is a _saddle point_
, or _(minimax) solution_ of (1) if
$\mathbf{L}(x_{\star},y)\leq\mathbf{L}(x_{\star},y_{\star})\leq\mathbf{L}(x,y_{\star})$
for all $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$.

#### Operators and monotonicity.

An operator on $\mathbb{R}^{d}$, denoted
${\varbbA}\colon\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d}$, is a set-
valued function, i.e., ${\varbbA}(z)\subseteq\mathbb{R}^{d}$ for all
$z\in\mathbb{R}^{d}$. For simplicity, we often write
${\varbbA}z={\varbbA}(z)$. If ${\varbbA}z$ contains exactly one element for
all $z\in\mathbb{R}^{d}$, then we say is _single-valued_ and view it as a
function. An operator
${\varbbA}\colon\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d}$ is _monotone_
if

$\displaystyle\langle{\varbbA}z-{\varbbA}z^{\prime},z-z^{\prime}\rangle\geq
0,\qquad\forall\,z,z^{\prime}\in\mathbb{R}^{d},$

where the notation means that $\langle u-v,z-z^{\prime}\rangle\geq 0$ for any
$u\in{\varbbA}z$ and $v\in{\varbbA}z^{\prime}$. For $\mu>0$, an operator is
$\mu$-_strongly monotone_ if

$\displaystyle\langle{\varbbA}z-{\varbbA}z^{\prime},z-z^{\prime}\rangle\geq\mu\|z-z^{\prime}\|^{2},\qquad\forall\,z,z^{\prime}\in\mathbb{R}^{d}.$

The graph of is denoted
$\mathrm{Gra}\,{\varbbA}=\\{(z,u)\,|\,u\in{\varbbA}z\\}$. A monotone operator
is _maximally monotone_ if there is no monotone operator ′ such that
$\mathrm{Gra}\,{\varbbA}\subset\mathrm{Gra}\,{}^{\prime}$ strictly. In
particular, if is monotone, single-valued, and continuous as a function, then
it is maximally monotone [7, Corollary 20.28]. Define

$\displaystyle({\varbbA}+{\varbbB})(z)=\\{u+v\in\mathbb{R}^{d}\,|\,u\in{\varbbA}z,v\in{\varbbB}z\\},\quad(\alpha{\varbbA})(z)=\\{\alpha
u\in\mathbb{R}^{d}\,|\,u\in{\varbbA}z\\}$

for operators and and scalar $\alpha\in\mathbb{R}$. The inverse of an operator
is the operator ${}^{-1}\colon\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d}$
defined by ${}^{-1}(u)=\\{z\in\mathbb{R}^{d}\,|\,u\in{\varbbA}z\\}$.

#### Monotone inclusion and fixed-point problems.

In a _monotone inclusion problem_ ,

$\displaystyle\begin{array}[]{ll}\underset{z\in\mathbb{R}^{d}}{\textrm{find}}&0\in{\varbbA}(z),\end{array}$
(5)

where ${\varbbA}\colon\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d}$ is
monotone, one finds zeros of an operator . For any $\alpha>0$, we have
$0\in{\varbbA}(z)\iff z\in({\varbbI}+\alpha{\varbbA})(z)\iff
z\in({\varbbI}+\alpha{\varbbA})^{-1}(z)$. Therefore, (5) is equivalent to the
_fixed-point problem_ (3) with
${\varbbT}=({\varbbI}+\alpha{\varbbA})^{-1}={}_{\alpha{\varbbA}}$. We call α
the _resolvent_ of $\alpha{\varbbA}$.

We say ${\varbbT}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is _nonexpansive_ if
it is $1$-Lipschitz continuous and _contractive_ if it is $\rho$-Lipschitz
with $\rho<1$. If is maximally monotone, then α has full domain [62] and is
nonexpansive [83] for any $\alpha>0$. Denoting
$\mathrm{Zer}\,{\varbbA}=\\{z\in\mathbb{R}^{d}\,|\,0\in{\varbbA}(z)\\}$ and
$\mathrm{Fix}\,{\varbbT}=\\{z\in\mathbb{R}^{d}\,|\,z={\varbbT}(z)\\}$, we have
$\mathrm{Zer}\,{\varbbA}=\mathrm{Fix}\,{}_{\alpha{\varbbA}}$. We call the
algorithm $z_{k+1}={}_{\alpha{\varbbA}}(z_{k})$ the _proximal point method
(PPM)_ for .

#### Minimax optimization as monotone inclusion problems.

For differentiable and convex-concave
$\mathbf{L}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$,
define
$\nabla_{\pm}\mathbf{L}(x,y)=(\nabla_{x}\mathbf{L}(x,y),-\nabla_{y}\mathbf{L}(x,y))$
and call it the _saddle operator_ of $\mathbf{L}$. Then
$\nabla_{\pm}\mathbf{L}$ is monotone [82], and
$z_{\star}=(x_{\star},y_{\star})$ is a solution of (1) if and only if
$\nabla_{\pm}\mathbf{L}(z_{\star})=0$. Therefore, a convex-concave minimax
optimization problem (1) can be reformulated as a monotone inclusion problem
(5) with ${\varbbA}=\nabla_{\pm}\mathbf{L}$ and as a fixed-point problem (3)
with ${\varbbT}={}_{\nabla_{\pm}\mathbf{L}}$.

The _fixed-point residual norm_ $\|z-{\varbbT}z\|$ quantifies the rate of
convergence of an algorithm for finding fixed points. When
${\varbbT}={}_{\alpha{\varbbB}}$, we have
$z-{\varbbT}z=z-{}_{\alpha{\varbbB}}(z)\in\alpha{\varbbB}({}_{\alpha{\varbbB}}(z))$,
because

$\displaystyle
u={}_{\alpha{\varbbB}}(z)=({\varbbI}+\alpha{\varbbB})^{-1}(z)\iff
z\in({\varbbI}+\alpha{\varbbB})(u)=u+\alpha{\varbbB}u.$

Thus, when ${\varbbT}={}_{\alpha{\varbbB}}$ and is single-valued, a
convergence rate on $\|z-{\varbbT}z\|$ is equivalent to a convergence rate on
$\|{\varbbB}(\cdot)\|$.

##  3 Accelerated algorithms for smooth minimax optimization are
$\mathcal{O}(1/k^{2})$-MP

In this section, we prove the $\mathcal{O}(1/k^{2})$-MP property among
accelerated minimax algorithms and the optimized Halpern iteration. The
problem setup is: minimax problems with convex-concave $\mathbf{L}$ such that
$\nabla_{\pm}\mathbf{L}$ is $L$-Lipschitz. For notational convenience, write
${\varbbB}=\nabla_{\pm}\mathbf{L}$. Our MP result provides new insight into
these acceleration mechanisms and allows us to establish their point
convergence.

#### Preliminaries: Accelerated minimax and proximal algorithms.

Recently, several accelerated minimax algorithms with rate
$\|{\varbbB}z_{k}\|^{2}=\mathcal{O}(1/k^{2})$ have been proposed. The list
includes the _extra anchored gradient (EAG)_ algorithm [100]

$\displaystyle z_{k+1/2}$
$\displaystyle=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}z_{k}$
$\displaystyle z_{k+1}$
$\displaystyle=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}z_{k+1/2},$

the _fast extragradient (FEG)_ algorithm [49]

$\displaystyle z_{k+1/2}$
$\displaystyle=\beta_{k}z_{0}+(1-\beta_{k})\left(z_{k}-\alpha{\varbbB}z_{k}\right)$
$\displaystyle z_{k+1}$
$\displaystyle=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}z_{k+1/2},$

and the _anchored Popov’s scheme (APS)_ [92], with $v_{0}=z_{0}$,

$\displaystyle v_{k+1}$
$\displaystyle=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}v_{k}$
$\displaystyle z_{k+1}$
$\displaystyle=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}v_{k+1}.$

Prior to the development of these minimax algorithms, the _optimized Halpern’s
method (OHM)_ [51, 43] was presented for solving the fixed-point problem (3)
with nonexpansive operator ${\varbbT}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$:

$\displaystyle\begin{aligned} w_{k+1/2}&=\beta_{k}w_{0}+(1-\beta_{k})w_{k}\\\
w_{k+1}&={\varbbT}(w_{k+1/2}),\end{aligned}$ (6)

where $\beta_{k}=\frac{1}{k+1}$. OHM converges with rate
$\|w_{k+1/2}-{\varbbT}w_{k+1/2}\|^{2}\leq 4\|w_{0}-w_{\star}\|^{2}/(k+1)^{2}$,
if a fixed point $w_{\star}$ exists.

To clarify, the prior works [100, 92] study further general forms of EAG and
APS with iteration-dependent step-sizes. For the sake of simplicity, we
consider the case of constant step-sizes and defer the discussion on varying
step-sizes to Appendix A and F.

#### MP property among accelerated algorithms.

The accelerated forward algorithms, EAG, FEG, and APS, do not merely resemble
OHM in their form. The algorithms are, in fact, near-equivalent in the sense
that they have quickly merging paths.

######  Theorem 1 (EAG$\approx$FEG$\approx$APS$\approx$OHM).

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be monotone and
$L$-Lipschitz and assume
$z_{\star}\in\mathrm{Zer}\,{\varbbB}=\mathrm{Fix}\,{}_{\alpha{\varbbB}}$
exists. Let ${\varbbT}={}_{\alpha{\varbbB}}$ and $\beta_{k}=\frac{1}{k+1}$.
Then FEG and OHM are $\mathcal{O}(\|z_{0}-z_{\star}\|^{2}/k^{2})$-MP for
$\alpha\in\left(0,\frac{1}{L}\right)$, and there exists $\eta>0$ such that
EAG, APS, and OHM are $\mathcal{O}(\|z_{0}-z_{\star}\|^{2}/k^{2})$-MP for
$\alpha\in\left(0,\frac{\eta}{L}\right)$.

###### Proof.

We provide the proof for the FEG case and defer the proofs for EAG and APS to
Appendix B.2. Let $\\{w_{k}\\}_{k=0,1,\dots}$ be the OHM iterates and
$\\{z_{k}\\}_{k=0,1,\dots}$ the FEG iterates, and assume $z_{0}=w_{0}$. Then

$\displaystyle z_{k+1}-w_{k+1}$
$\displaystyle=\left(\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}z_{k+1/2}\right)-\left(\beta_{k}w_{0}+(1-\beta_{k})w_{k}-\alpha{\varbbB}w_{k+1}\right)$
$\displaystyle=(1-\beta_{k})(z_{k}-w_{k})+\alpha\left({\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right)$

where we used $({\varbbI}+\alpha{\varbbB})(w_{k+1})=w_{k+1/2}$ in the first
equality and $z_{0}=w_{0}$ in the second. Thus,

$\displaystyle\begin{aligned}
\left\|z_{k+1}-w_{k+1}\right\|^{2}&=(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}+2\left\langle\alpha(1-\beta_{k})(z_{k}-w_{k}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle\\\
&\quad\quad+\alpha^{2}\left\|{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\|^{2}.\end{aligned}$
(7)

Now use the similar identity

$\displaystyle
z_{k+1/2}-w_{k+1}=(1-\beta_{k})(z_{k}-w_{k})-\alpha(1-\beta_{k}){\varbbB}z_{k}+\alpha{\varbbB}w_{k+1}$

to rewrite the inner product term in (7) as

$\displaystyle
2\left\langle\alpha(1-\beta_{k})(z_{k}-w_{k}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle=2\left\langle\alpha(z_{k+1/2}-w_{k+1})+\alpha^{2}(1-\beta_{k}){\varbbB}z_{k}-\alpha^{2}{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle\leq
2\alpha^{2}\left\langle(1-\beta_{k}){\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle,$

where the last inequality follows from monotonicity of . Combining this with
(7), we obtain

$\displaystyle\left\|z_{k+1}-w_{k+1}\right\|^{2}$
$\displaystyle\leq(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}+2\alpha^{2}\left\langle(1-\beta_{k}){\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle\quad+\alpha^{2}\left\|{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\|^{2}$
$\displaystyle=(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}\underbrace{-\,\alpha^{2}\left\|{\varbbB}w_{k+1}\right\|^{2}+2\alpha^{2}(1-\beta_{k})\langle{\varbbB}z_{k},{\varbbB}w_{k+1}\rangle}_{\leq\alpha^{2}(1-\beta_{k})^{2}\|{\varbbB}z_{k}\|^{2}}$
$\displaystyle\quad-2\alpha^{2}(1-\beta_{k})\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\alpha^{2}\|{\varbbB}z_{k+1/2}\|^{2}.$

Plugging in $\beta_{k}=\frac{1}{k+1}$ and multiplying both sides by
$(k+1)^{2}$, we obtain

$\displaystyle(k+1)^{2}\left\|z_{k+1}-w_{k+1}\right\|^{2}\leq$
$\displaystyle\,k^{2}\left\|z_{k}-w_{k}\right\|^{2}+\alpha^{2}\|k{\varbbB}z_{k}-(k+1){\varbbB}z_{k+1/2}\|^{2}.$

The conclusion then follows from the following Lemma 2. ∎

######  Lemma 2.

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be monotone and
$L$-Lipschitz and assume $z_{\star}\in\mathrm{Zer}\,{\varbbB}$ exists. Let
$\\{z_{k}\\}_{k=0,1,\dots}$ be the iterates of FEG with
$\beta_{k}=\frac{1}{k+1}$. For $\alpha\in\left(0,\frac{1}{L}\right)$,

$\displaystyle\sum_{k=0}^{\infty}\|k{\varbbB}z_{k}-(k+1){\varbbB}z_{k+1/2}\|^{2}\leq\frac{1}{\alpha^{2}(1-\alpha^{2}L^{2})}\|z_{0}-z_{\star}\|^{2}<\infty.$

###### Proof outline of Lemma 2.

We show $V_{k}=\frac{\alpha
k^{2}}{2}\|{\varbbB}z_{k}\|^{2}+k\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$
satisfy

$\displaystyle
V_{k}-V_{k+1}\geq\frac{\alpha(1-\alpha^{2}L^{2})}{2}\|k{\varbbB}z_{k}-(k+1){\varbbB}z_{k+1/2}\|^{2}$

and $V_{k}\geq 0$ for $k=0,1,\dots$ (details presented in Appendix B.1). The
conclusion follows by taking $N\to\infty$ in
$\frac{\alpha(1-\alpha^{2}L^{2})}{2}\sum_{k=0}^{N}\|k{\varbbB}z_{k}-(k+1){\varbbB}z_{k+1/2}\|^{2}\leq
V_{0}-V_{N+1}\leq V_{0}=\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$. ∎

As it is well known [7, Theorem 30.1] that OHM converges to

$\Pi_{\mathrm{Fix}{\varbbT}}(z_{0})=\underset{z\in\mathrm{Fix}\,{\varbbT}}{\operatorname*{argmin}}\|z-z_{0}\|,$

Theorem 1 immediately implies point convergence of EAG, FEG, and APS.

######  Corollary 3.

In the setup of Theorem 1, iterates of EAG, FEG, and APS converge to
$\Pi_{\mathrm{Zer}\,{\varbbB}}(z_{0})$.

##  4 Fastest algorithm for smooth strongly-convex-strongly-concave minimax
optimization with respect to gradient norm

In Section 3, we identified that prior accelerated minimax algorithms
approximate, in the MP sense, the optimal proximal algorithm OHM. In this
section, we design a novel algorithm to approximate, in the MP sense, the
optimal proximal algorithm OC-Halpern [76] and thereby achieve the state-of-
the-art rate for minimax problems with $L$-smooth $\mu$-strongly-convex-
strongly-concave $\mathbf{L}$ (so $\nabla_{\pm}\mathbf{L}$ is $L$-Lipschitz
and $\mu$-strongly monotone). Later in Section 5, we repeat the strategy of
designing an algorithm to approximate, in the MP sense, a known accelerated
proximal algorithm.

We design the novel algorithm _S trongly Monotone Extra Anchored
Gradient+_111The “+” follows the nomenclature of [25], where the two-time-
scale EG was named EG+.

$\displaystyle\begin{aligned}
z_{k+1/2}&=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\eta_{k}\alpha{\varbbB}z_{k}\\\
z_{k+1}&=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}z_{k+1/2},\end{aligned}$
(SM-EAG+)

where ${\varbbB}=\nabla_{\pm}\mathbf{L}$,
$\beta_{k}=\frac{1}{\sum_{j=0}^{k}(1+2\alpha\mu)^{j}}$,
$\eta_{k}=\frac{1-\beta_{k}}{1+2\alpha\mu}$, and
$0<\alpha\leq\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}$, to approximate OC-
Halpern in the MP sense. SM-EAG+ inherits the accelerated rate of OC-Halpern
and achieves the fastest known rate in the setup with respect to the gradient
norm, improving upon the prior rates of EG and OG by factors of 8 and 4,
respectively. (OC-Halpern is not a forward algorithm as it uses the proximal
operator α, while SM-EAG+ is a forward algorithm using evaluations of .)

#### Preliminaries: Proximal algorithm with exact optimal complexity.

For the fixed-point problem (3) with a $\gamma^{-1}$-contractive , the
recently presented _OC-Halpern_ [76, Corollary 3.3, Theorem 4.1], which has
the same form (6) as OHM but with
$\beta_{k}=\left(\sum_{j=0}^{k}\gamma^{2j}\right)^{-1}$, achieves the exact
optimal accelerated rate of
$\|w_{k+1/2}-{\varbbT}w_{k+1/2}\|^{2}\leq\left(1+\gamma^{-1}\right)^{2}\left(\sum_{j=0}^{k}\gamma^{j}\right)^{-2}\|w_{0}-w_{\star}\|^{2}$,
where $w_{\star}\in\mathrm{Fix}\,{\varbbB}$. We consider OC-Halpern with
${\varbbT}={}_{\alpha{\varbbB}}$, which is contractive if is maximally
monotone and $\mu$-strongly monotone [7, Proposition 23.8, 23.13].

#### MP property and convergence analysis of SM-EAG+.

SM-EAG+ approximates OC-Halpern in the MP sense.

######  Lemma 4 (SM-EAG+$\approx$OC-Halpern).

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be $\mu$-strongly
monotone and $L$-Lipschitz with $0<\mu\leq L$. Let $z_{\star}$ be the zero of
. If $\alpha\in\big{(}0,\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}\big{)}$, then
for any $\epsilon\in(0,1)$, SM-EAG+ and OC-Halpern with
${\varbbT}={}_{\alpha{\varbbB}}$ and
$\beta_{k}=\frac{1}{\sum_{j=0}^{k}(1+2\alpha\mu)^{j}}$ are
$\mathcal{O}\left(\frac{\|z_{0}-z_{\star}\|^{2}}{(1+2\alpha\mu(1-\epsilon))^{k}}\right)$-MP.

To clarify, in Lemma 4, we view α as a $\gamma^{-1}$-contractive operator with
$\gamma^{-1}=\frac{1}{\sqrt{1+2\alpha\mu}}>\frac{1}{1+\alpha\mu}$, where
$\frac{1}{1+\alpha\mu}$ is the tight contraction factor for α [7, Proposition
23.13], and then apply OC-Halpern. This slack, which is negligible in the
regime $L/\mu\to\infty$, is necessary for proving the MP result.

SM-EAG+ inherits the convergence rate of OC-Halpern, since the paths of OC-
Halpern and SM-EAG+ merge at rate
$\mathcal{O}\left(\frac{\|z_{0}-z_{\star}\|^{2}}{(1+2\alpha\mu(1-\epsilon))^{k}}\right)$
for any $\epsilon>0$, arbitrarily close to the order of convergence
$\|\alpha{\varbbB}w_{k+1}\|^{2}=\mathcal{O}\left(\frac{\|w_{0}-w_{\star}\|^{2}}{(1+2\alpha\mu)^{k}}\right)$
of OC-Halpern [76]. On the other hand, EG and OG can be viewed as
approximations of the proximal point method (PPM) [63], which is slower than
OC-Halpern. Additionally, it is unclear whether EG and OG exhibit an MP
property to PPM fast enough to preserve PPM’s convergence rate since EG and OG
have no anchoring mechanism inducing the MP property.

######  Theorem 5 (Fast rate of SM-EAG+).

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be $\mu$-strongly
monotone and $L$-Lipschitz with $0<\mu\leq L$. Let $z_{\star}$ be the zero of
. For $\alpha\in\big{(}0,\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}\big{]}$, then
SM-EAG+ exhibits the rate

$\displaystyle\|{\varbbB}z_{k}\|^{2}\leq\frac{\left(\sqrt{1+2\alpha\mu}+1\right)^{2}}{\alpha^{2}\left(\sum_{j=0}^{k-1}(1+2\alpha\mu)^{\frac{j}{2}}\right)^{2}}\|z_{0}-z_{\star}\|^{2},\qquad\text{for
}k=1,2,\dots.$

With the choice $\alpha=\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}$, Theorem 5
implies

$\displaystyle\|{\varbbB}z_{k}\|^{2}=\mathcal{O}\left(e^{-2k\frac{\mu}{L}}L^{2}\|z_{0}-z_{\star}\|^{2}\right)$

as $L/\mu\to\infty$. Therefore, SM-EAG+ requires roughly
$\frac{L}{\mu}\log\frac{L\|z_{0}-z_{\star}\|}{\epsilon}$ iterations to achieve
$\|{\varbbB}z_{k}\|\leq\epsilon$. On the other hand, simultaneous gradient
descent-ascent has the rate [7, Proposition 26.16]

$\displaystyle\|{\varbbB}z_{k}\|^{2}\leq
L^{2}\|z_{k}-z_{\star}\|^{2}=\mathcal{O}\left(e^{-k\frac{\mu^{2}}{L^{2}}}L^{2}\|z_{0}-z_{\star}\|^{2}\right)$

as $L/\mu\to\infty$, and therefore requires
$\frac{2L^{2}}{\mu^{2}}\log\frac{L\|z_{0}-z_{\star}\|}{\epsilon}\gg\frac{L}{\mu}\log\frac{L\|z_{0}-z_{\star}\|}{\epsilon}$
iterations to achieve $\|{\varbbB}z_{k}\|\leq\epsilon$. EG and OG has the rate
[63, 5]:

$\displaystyle\|{\varbbB}z_{k}\|^{2}\leq
L^{2}\|z_{k}-z_{\star}\|^{2}=\mathcal{O}\left(e^{-k\frac{\mu}{4L}}L^{2}\|z_{0}-z_{\star}\|^{2}\right),$

as $L/\mu\to\infty$, and therefore requires
$\frac{8L}{\mu}\log\frac{L\|z_{0}-z_{\star}\|}{\epsilon}$ iterations to
achieve $\|{\varbbB}z_{k}\|\leq\epsilon$. Thus, SM-EAG+ is $8\times$ faster
than EG and $4\times$ faster than OG (since OG makes a single call to the
gradient oracle at each iteration).

As a final remark, when $\mu=0$, SM-EAG+ coincides with FEG [49], which has
the fastest known rate of
$\|{\varbbB}z_{k}\|^{2}\leq\frac{4L^{2}\|z_{0}-z_{\star}\|^{2}}{k^{2}}$ when
is (non-strongly) monotone and $L$-Lipschitz. This rate is precisely recovered
by Theorem 5 when $\mu=0$, with $\alpha=\frac{1}{L}$.

##  5 Near-optimal prox-grad-type accelerated minimax algorithm

Consider the setup with minimax objective of the form
$\mathbf{L}(x,y)=\mathbf{L}_{p}(x,y)+\mathbf{L}_{s}(x,y)$, where
$\mathbf{L}_{s}$ is $L$-smooth. Informally assume that $\mathbf{L}_{p}$ is
nonsmooth and proximable (we clarify this notion below). We reformulate the
minimax optimization problem into the monotone inclusion problem

$\displaystyle\begin{array}[]{ll}\underset{z\in\mathbb{R}^{d}}{\textrm{find}}&0\in(\partial_{\pm}\mathbf{L}_{p}+\nabla_{\pm}\mathbf{L}_{s})(z),\end{array}$
(9)

where $\partial_{\pm}$ is the analog of $\nabla_{\pm}$ for nonsmooth convex-
concave functions (precisely defined in Section 5.1). We design the _A nchored
Proximal Gradient* (APG*)_:

$\displaystyle\begin{aligned} z_{k}&=\textbf{SM-
EAG+}\left({\varbbI}+\alpha{\varbbB}-\xi_{k},\xi_{k},\epsilon_{k}\right)\\\
\xi_{k+1}&=\beta_{k}z_{0}+(1-\beta_{k})\left({}_{\alpha{\varbbA}}(z_{k}-\alpha{\varbbB}z_{k})+\alpha{\varbbB}z_{k}\right),\end{aligned}$
(APG*)

where ${\varbbA}=\partial_{\pm}\mathbf{L}_{p}$,
${\varbbB}=\nabla_{\pm}\mathbf{L}_{s}$, $\xi_{0}\in\mathbb{R}^{d}$ is the
initial point, and $\textbf{SM-
EAG+}\left({\varbbI}+\alpha{\varbbB}-\xi_{k},\xi_{k},\epsilon_{k}\right)$
denotes the execution of SM-EAG+ with the $1$-strongly monotone $(1+\alpha
L)$-smooth operator $z\mapsto({\varbbI}+\alpha{\varbbB})(z)-\xi_{k}$ with
$\xi_{k}$ as the initial point using the step-size $\frac{\sqrt{(1+\alpha
L)^{2}+1}+1}{(1+\alpha L)^{2}}$ until reaching the tolerance
$\|({\varbbI}+\alpha{\varbbB})(\cdot)-\xi_{k}\|\leq\epsilon_{k}$.

APG* is a proximal-gradient-type algorithm; each iteration, APG* uses a single
proximal operation ${}_{\alpha\partial_{\pm}\mathbf{L}_{p}}$ and multiple
(logarithmically many) gradient operations $\nabla_{\pm}\mathbf{L}_{s}$. (The
superscript * in the name APG* indicates the multiple gradient evaluations per
iteration.) Thus, APG* is useful when $\mathbf{L}_{p}$ is _proximable_ in the
sense that ${}_{\alpha\partial_{\pm}\mathbf{L}_{p}}$ can be computed
efficiently. APG* is designed to approximate the accelerated proximal
algorithm OHM-DRS, described soon, in the MP sense and thereby achieves a
near-optimal accelerated rate.

###  5.1 Preliminaries: Subdifferential operators and forward-backward
residual

If $\mathbf{L}_{p}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$ is a
finite-valued, not necessarily differentiable convex-concave function, then
its _(saddle) subdifferential_ operator
$\partial_{\pm}\mathbf{L}_{p}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}\times\mathbb{R}^{m}$
defined by

$\displaystyle\partial_{\pm}\mathbf{L}_{p}(x,y)=\\{(v,w)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\,|\,v\in\partial_{x}\mathbf{L}_{p}(x,y),w\in\partial_{y}(-\mathbf{L}_{p})(x,y)\\}$

is maximal monotone [7, Theorem 35.1, Corollary 37.5.2], where $\partial_{x}$
and $\partial_{y}$ respectively denote the convex subdifferential with respect
to the $x$\- and $y$-variables. However, in order to encompass a broader range
of problems, such as constrained minimax optimization problems, it is
necessary to consider $\mathbf{L}_{p}$ taking values in
$\mathbb{R}\cup\\{\pm\infty\\}$. In this case, $\partial\mathbf{L}_{p}$ is
maximal monotone if $\mathbf{L}_{p}$ is _closed_ and _proper_ [81], which we
precisely define and detail in Appendix G. For now, we simply state that most
convex-concave saddle functions considered in practice are closed and proper,
and if that holds, $z_{\star}$ is a solution of (1) if and only if
$0\in\partial_{\pm}\mathbf{L}(z_{\star})$. Therefore, in our setup with
$\mathbf{L}=\mathbf{L}_{p}+\mathbf{L}_{s}$, we rewrite (1) into (9), using the
fact that $\partial_{\pm}=\nabla_{\pm}$ for differentiable convex-concave
functions.

Of particular interest are problems with $\mathbf{L}(x,y)=f(x)+\langle
Ax,y\rangle-g(y)$, with some $A\in\mathbb{R}^{m\times n}$, or, more generally,
$\mathbf{L}(x,y)=f(x)+\mathbf{L}_{s}(x,y)-g(y)$, with some $L$-smooth convex-
concave $\mathbf{L}_{s}$. In this case,
$\partial_{\pm}\mathbf{L}_{p}(x,y)=(\partial f(x),\partial g(y))$, and
${}_{\alpha\partial_{\pm}\mathbf{L}_{p}}(x,y)=(\mathrm{Prox}_{\alpha
f}(x),\mathrm{Prox}_{\alpha g}(y))$, where

$\displaystyle\mathrm{Prox}_{\alpha
f}(x)=\underset{x^{\prime}\in\mathbb{R}^{n}}{\operatorname*{argmin}}\left\\{\alpha
f(x^{\prime})+\frac{1}{2}\|x^{\prime}-x\|^{2}\right\\},\,\,\,\mathrm{Prox}_{\alpha
g}(y)=\underset{y^{\prime}\in\mathbb{R}^{m}}{\operatorname*{argmin}}\left\\{\alpha
g(y^{\prime})+\frac{1}{2}\|y^{\prime}-y\|^{2}\right\\}$

are the proximal operators. When
$f(x)=\delta_{\mathcal{X}}(x)=\begin{cases}0&x\in{\mathcal{X}}\\\
+\infty&x\notin{\mathcal{X}}\end{cases}$, the proximal operator becomes the
projection operator:
$\mathrm{Prox}_{\alpha\delta_{\mathcal{X}}}(x)=\Pi_{{\mathcal{X}}}(x)$ for any
$\alpha>0$. Therefore, the constrained problem (1) with
${\mathcal{X}}\subset\mathbb{R}^{n}$, ${\mathcal{Y}}\subset\mathbb{R}^{m}$ is
recovered with
$\mathbf{L}_{p}(x,y)=\delta_{\mathcal{X}}(x)-\delta_{\mathcal{Y}}(y)$.

Note that $z_{\star}$ is a solution of (9) if and only if
$z_{\star}={}_{\alpha{\varbbA}}(z_{\star}-\alpha{\varbbB}z_{\star})$.
Therefore, the norm of the _forward-backward residual_
${}_{\alpha}(z)=\frac{1}{\alpha}(z-{}_{\alpha{\varbbA}}(z-\alpha{\varbbB}z))$
serves as a measure for the convergence of algorithms solving (9), and it
generalizes the operator norm and the fixed-point residual norm.

###  5.2 Preliminaries: Accelerated proximal splitting algorithm

Consider

$\displaystyle\begin{aligned} w_{k}&={}_{\alpha{\varbbB}}(u_{k})\\\
u_{k+1}&=\beta_{k}u_{0}+(1-\beta_{k})({}_{\alpha{\varbbA}}(w_{k}-\alpha{\varbbB}w_{k})+\alpha{\varbbB}w_{k})\end{aligned}$
(OHM-DRS)

with $\beta_{k}=\frac{1}{k+2}$, which is the application of OHM to the
Douglas–Rachford splitting (DRS) operator [27, 53] defined by
${}_{\textrm{DRS}}={\varbbI}-{}_{\alpha{\varbbB}}+{}_{\alpha{\varbbA}}\circ(2{}_{\alpha{\varbbB}}-{\varbbI})$.
Since ${}_{\textrm{DRS}}$ is nonexpansive [53], OHM-DRS exhibits the
accelerated rate
$\|\alpha{}_{\alpha}(w_{k})\|^{2}=\|u_{k}-{}_{\textrm{DRS}}(u_{k})\|^{2}=\mathcal{O}(1/k^{2})$.
(Here we use the alternative representation of OHM
$u_{k+1}=\beta_{k}u_{0}+(1-\beta_{k}){\varbbT}u_{k}$ with
$\beta_{k}=\frac{1}{k+2}$, which is equivalent to (6) under the identification
$u_{k}=w_{k+1/2}$. We clarify some details in Appendix A.6).

OHM-DRS will serve as a conceptual algorithm (not implemented) that our APG*
(implementable) is designed to $\mathcal{O}(1/k^{2})$-MP approximate, so that
APG* inherits the accelerated rate of OHM-DRS. (OHM-DRS is not prox-grad-type,
while APG* is.)

###  5.3 MP property and convergence of APG*

We now describe the design of APG*. The forms of APG* and OHM-DRS bear a clear
resemblance. The second lines are identical. In the first lines, the resolvent
computation α of OHM-DRS is replaced in APG* by an inner loop with SM-EAG+.
Note, $z={}_{\alpha{\varbbB}}(\xi_{k})$ if and only if it solves

$\displaystyle\begin{array}[]{ll}\underset{z\in\mathbb{R}^{d}}{\textrm{find}}&0=z+\alpha{\varbbB}z-\xi_{k}=({\varbbI}+\alpha{\varbbB}-\xi_{k})(z),\end{array}$
(11)

and ${\varbbI}+\alpha{\varbbB}-\xi_{k}$ is a $1$-strongly monotone, $(1+\alpha
L)$-Lipschitz operator. Therefore, (11) is an instance of the problem class of
Section 4, and SM-EAG+ can efficiently solve it to accuracy
$\|({\varbbI}+\alpha{\varbbB})(z)-\xi_{k}\|\leq\epsilon_{k}$ in
$\mathcal{O}(\log(1/\epsilon_{k}))$ iterations. Therefore the $z_{k}$-iterate
of APG* approximates the $w_{k}={}_{\alpha{\varbbB}}(u_{k})$-iterate of OHM-
DRS.

######  Theorem 6 (APG*$\approx$OHM-DRS).

With $\alpha\in\left(0,\frac{1}{L}\right)$, $\beta_{k}=\frac{1}{k+2}$, and
$\epsilon_{k}=\frac{1+L^{-1}\|{\varbbB}\xi_{0}\|}{(k+1)^{2}(k+2)}$, APG* is
$\mathcal{O}(1/k^{2})$-MP to OHM-DRS; specifically, if $\xi_{k},z_{k}$ are the
APG* iterates and $u_{k},w_{k}$ are the iterates of OHM-DRS, and if
$\xi_{0}=u_{0}$, then

$\displaystyle\max\left\\{\|\xi_{k}-u_{k}\|^{2},\|z_{k}-w_{k}\|^{2}\right\\}\leq\frac{C(\xi_{0})^{2}}{L^{2}(k+1)^{2}},\qquad\text{for
}k=0,1,\dots,$

where $C(\xi_{0})=L(\|\xi_{0}-\xi_{\star}\|+1)+\|{\varbbB}\xi_{\star}\|$ and
$\xi_{\star}=\Pi_{\mathrm{Fix}\,({}_{\textup{DRS}})}(\xi_{0})$.

######  Corollary 7 (Fast rate of APG*).

With the conditions and notations of Theorem 6, $\xi_{k}\to\xi_{\star}$ and
$z_{k}\to{}_{\alpha{\varbbB}}(\xi_{\star})\in\mathrm{Zer}\,({\varbbA}+{\varbbB})$
as $k\to\infty$. Additionally,

$\displaystyle\|{}_{\alpha}(z_{k})\|^{2}\leq\frac{(3+\alpha
L)^{2}C(\xi_{0})^{2}}{\alpha^{2}L^{2}(k+1)^{2}},\qquad\text{for }k=0,1,\dots.$

######  Corollary 8 (Oracle complexity of APG*).

With the conditions and notations of Theorem 6, the $k$th inner loop of SM-
EAG+ in APG* requires
$\mathcal{O}\left(\log\left(k\left(\|\xi_{0}-\xi_{\star}\|+1\right)\right)\right)$
oracle calls of for $k=0,1,\dots$. This implies that the total computational
cost needed to achieve $\|{}_{\alpha}(z_{k})\|\leq\epsilon$ is

$\displaystyle\mathcal{O}\left(\frac{C(\xi_{0})}{\epsilon}\left(C+C\log\frac{C(\xi_{0})}{\epsilon}\right)\right),$

where $C,C$ are upper bounds on the respective costs of evaluating α and .

#### Discussion.

We clarify some key differences between APG* and the prior work of
Diakonikolas [24, Algorithm 3]. First, APG* is a more general proximal-
gradient-type algorithm, while the prior algorithm of Diakonikolas is a
projected-gradient-type algorithm. Second, APG* is an anytime algorithm, as it
requires no a priori specification of the terminal accuracy or the total
iteration count, while the prior algorithm is not an anytime algorithm, as it
requires the terminal accuracy $\epsilon$ to be pre-specified. Third, APG* has
$\mathcal{O}\left(\frac{C}{\epsilon}+\frac{C}{\epsilon}\log\frac{1}{\epsilon}\right)$
total cost (hiding dependency on $\xi_{0},\xi_{\star}$ and $L$), while the
prior algorithm has
$\mathcal{O}\left(\frac{C+C}{\epsilon}\log\frac{1}{\epsilon}\right)$ total
cost, as its inner loops require projections (corresponding to α). Therefore,
APG* offers a speedup for constrained minimax problems when the projection
represents the dominant cost, i.e., when $C\gg C$.

The initial point $\xi_{k}$ for the inner loop $\textbf{SM-
EAG+}\left({\varbbI}+\alpha{\varbbB}-\xi_{k},\xi_{k},\epsilon_{k}\right)$ of
APG* is a crude choice. However, while a more careful warm starting may
improve the iteration complexity by a constant factor, we do not believe it
alone can eliminate the $\mathcal{O}(\log(1/\epsilon))$-factor. In our
analysis of APG* presented in Appendix D, we induce the MP property by solving
the $k$th inner loop up to accuracy $\epsilon_{k}$ satisfying
$\sum_{k=0}^{\infty}k\epsilon_{k}<\infty$. Therefore, unless a mechanism for
finding a warm-starting point $z$ satisfying
$\|({\varbbI}+\alpha{\varbbB})(z)-\xi_{k}\|={\mathcal{O}}(\epsilon_{k})=o(1/k)$
is proposed (which seems nontrivial), the
$\mathcal{O}(\log(1/\epsilon))$-factor will persist. Eliminating the
logarithmic factor probably requires a new additional insight, and we leave it
as a future work.

##  6 Conclusion

In this paper, we identified the novel merging path (MP) property among
accelerated minimax algorithms, EAG [100], FEG [49], and APS [92], and the
accelerated proximal algorithm OHM [35, 51, 43]. We then used this MP property
to design new state-of-the-art algorithms.

We quickly mention that our results straightforwardly extend to the setup
where the underlying space $\mathbb{R}^{d}$ is replaced with an infinite-
dimensional Hilbert space, since our proofs do not rely on the finite-
dimensionality of $\mathbb{R}^{d}$. In particular, the point convergence
results of Corollaries 3 and 7 hold as strong convergence.

The MP property provides the insight that the four different accelerated
algorithms, EAG, FEG, APS, and OHM, actually reduce to one single acceleration
mechanism. However, elucidating the fundamental principle behind this single
anchoring-based acceleration mechanism still remains an open problem, and
further investigating the phenomenon from multiple different viewpoints, as
was done for Nesterov’s acceleration, would be an interesting direction of
future work.

The presence or applicability of the MP property in other setups is another
interesting direction of future work. One question is whether other prior
optimization algorithms exhibit the MP property. In our analysis, we found
that anchoring induces the MP property, so algorithms using similar
regularizations, such as the recursive regularization [4] or the Katyusha
momentum [3], may be approximating some other conceptual algorithm. Another
question is whether the MP property can be used to design new algorithms in
other setups. The strategy of designing efficient algorithms by approximating
a conceptual algorithm, in the MP sense, may be widely applicable in setups
beyond non-stochastic minimax optimization.

## References

  * [1] K. Ahn and S. Sra.  Understanding Nesterov’s acceleration via proximal point method.  Symposium on Simplicity in Algorithms, 2022.
  * [2] M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev, and F. S. Stonyakin.  Accelerated methods for saddle-point problem.  Computational Mathematics and Mathematical Physics, 60(11):1787–1809, 2020.
  * [3] Z. Allen-Zhu.  Katyusha: The first direct acceleration of stochastic gradient methods.  Journal of Machine Learning Research, 18(1):8194–8244, 2017.
  * [4] Z. Allen-Zhu.  How to make the gradients small stochastically: Even faster convex and nonconvex SGD.  Neural Information Processing Systems, 2018.
  * [5] W. Azizian, I. Mitliagkas, S. Lacoste-Julien, and G. Gidel.  A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games.  International Conference on Artificial Intelligence and Statistics, 2020.
  * [6] B. Van Scoy, R. A. Freeman, and K. M. Lynch.  The fastest known globally convergent first-order method for minimizing strongly convex functions.  IEEE Control Systems Letters, 2(1):49–54, 2018.
  * [7] H. H. Bauschke and P. L. Combettes.  Convex Analysis and Monotone Operator Theory in Hilbert Spaces.  Springer International Publishing, second edition, 2017.
  * [8] A. Beck and M. Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM Journal on Imaging Sciences, 2(1):183–202, 2009.
  * [9] Y. Censor, A. Gibali, and S. Reich.  Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space.  Optimization Methods and Software, 26(4-5):827–845, 2011.
  * [10] Y. Censor, A. Gibali, and S. Reich.  The subgradient extragradient method for solving variational inequalities in Hilbert space.  Journal of Optimization Theory and Applications, 148(2):318–335, 2011.
  * [11] A. Chambolle and C. Dossal.  On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm”.  Journal of Optimization Theory and Applications, 166(3):968–982, 2015.
  * [12] A. Chambolle and T. Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011\.
  * [13] A. Chambolle and T. Pock.  On the ergodic convergence rates of a first-order primal-dual algorithm.  Mathematical Programming, 159(1):253–287, 2016.
  * [14] T. Chavdarova, G. Gidel, F. Fleuret, and S. Lacoste-Julien.  Reducing noise in GAN training with variance reduced extragradient.  Neural Information Processing Systems, 2019.
  * [15] Y. Chen, G. Lan, and Y. Ouyang.  Optimal primal-dual methods for a class of saddle point problems.  SIAM Journal on Optimization, 24(4):1779–1814, 2014.
  * [16] Y. Chen, G. Lan, and Y. Ouyang.  Accelerated schemes for a class of variational inequalities.  Mathematical Programming, 165(1):113–149, 2017.
  * [17] P. L. Combettes and J.-C. Pesquet.  Proximal splitting methods in signal processing.  In H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, editors, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pages 185–212. Springer, 2011.
  * [18] L. Condat.  A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms.  Journal of Optimization Theory and Applications, 158(2):460–479, 2013.
  * [19] E. R. Csetnek, Y. Malitsky, and M. K. Tam.  Shadow Douglas–Rachford splitting for monotone inclusions.  Applied Mathematics & Optimization, 80(3):665–678, 2019.
  * [20] C. Daskalakis, A. Deckelbaum, and A. Kim.  Near-optimal no-regret algorithms for zero-sum games.  Games and Economic Behavior, 92:327–348, 2015.
  * [21] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng.  Training GANs with optimism.  International Conference on Learning Representations, 2018.
  * [22] I. Daubechies, M. Defrise, and C. De Mol.  An iterative thresholding algorithm for linear inverse problems with a sparsity constraint.  Communications on Pure and Applied Mathematics, 57(11):1413–1457, 2004.
  * [23] D. Davis and B. Grimmer.  Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems.  SIAM Journal on Optimization, 29(3):1908–1930, 2019.
  * [24] J. Diakonikolas.  Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.  Conference on Learning Theory, 2020.
  * [25] J. Diakonikolas, C. Daskalakis, and M. Jordan.  Efficient methods for structured nonconvex-nonconcave min-max optimization.  International Conference on Artificial Intelligence and Statistics, 2021.
  * [26] J. Diakonikolas and P. Wang.  Potential function-based framework for making the gradients small in convex and min-max optimization.  SIAM Journal on Optimization, To appear. arXiv:2101.12101, 2022\.
  * [27] J. Douglas and H. H. Rachford.  On the numerical solution of heat conduction problems in two and three space variables.  Transactions of the American Mathematical Society, 82(2):421–439, 1956.
  * [28] D. Drusvyatskiy.  The proximal point method revisited.  arXiv preprint arXiv:1712.06038, 2017.
  * [29] H. Edwards and A. J. Storkey.  Censoring representations with an adversary.  International Conference on Learning Representations, 2016.
  * [30] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  International Conference on Learning Representations, 2019.
  * [31] G. Gidel, R. A. Hemmat, M. Pezeshki, R. L. Priol, G. Huang, S. Lacoste-Julien, and I. Mitliagkas.  Negative momentum for improved game dynamics.  International Conference on Artificial Intelligence and Statistics, 2019.
  * [32] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  Neural Information Processing Systems, 2014.
  * [33] E. Gorbunov, N. Loizou, and G. Gidel.  Extragradient method: $O(1/K)$ last-iterate convergence for monotone variational inequalities and connections with cocoercivity.  International Conference on Artificial Intelligence and Statistics, 2022.
  * [34] O. Güler.  New proximal point algorithms for convex minimization.  SIAM Journal on Optimization, 2(4):649–664, 1992.
  * [35] B. Halpern.  Fixed points of nonexpanding maps.  Bulletin of the American Mathematical Society, 73(6):957–961, 1967\.
  * [36] E. Y. Hamedani and N. S. Aybat.  A primal-dual algorithm with line search for general convex-concave saddle point problems.  SIAM Journal on Optimization, 31(2):1299–1329, 2021.
  * [37] B. He and X. Yuan.  Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective.  SIAM Journal on Imaging Sciences, 5(1):119–149, 2012.
  * [38] Y. He and R. D. C. Monteiro.  An accelerated HPE-Type algorithm for a class of composite convex-concave saddle-point problems.  SIAM Journal on Optimization, 26(1):29–56, 2016.
  * [39] Y.-G. Hsieh, K. Antonakopoulos, and P. Mertikopoulos.  Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium.  Conference on Learning Theory, 2021.
  * [40] Y.-G. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos.  On the convergence of single-call stochastic extra-gradient methods.  Neural Information Processing Systems, 2019.
  * [41] Y. Jin, A. Sidford, and K. Tian.  Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods.  arXiv preprint arXiv:2202.04640, 2022.
  * [42] A. Juditsky, A. Nemirovski, and C. Tauvel.  Solving variational inequalities with stochastic mirror-prox algorithm.  Stochastic Systems, 1(1):17–58, 2011.
  * [43] D. Kim.  Accelerated proximal point method for maximally monotone operators.  Mathematical Programming, 190(1–2):57–87, 2021.
  * [44] D. Kim and J. A. Fessler.  Optimized first-order methods for smooth convex minimization.  Mathematical Programming, 159(1-2):81–107, 2016.
  * [45] D. Kim and J. A. Fessler.  Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions.  Journal of Optimization Theory and Applications, 188(1):192–219, 2021.
  * [46] O. Kolossoski and R. Monteiro.  An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems.  Optimization Methods and Software, 32(6):1244–1272, 2017.
  * [47] G. M. Korpelevich.  The extragradient method for finding saddle points and other problems.  Ekonomika i Matematicheskie Metody, 12(4):747–756, 1976.
  * [48] J. Lee, C. Park, and E. K. Ryu.  A geometric structure of acceleration and its role in making gradients small fast.  Neural Information Processing Systems, 2021.
  * [49] S. Lee and D. Kim.  Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems.  Neural Information Processing Systems, 2021.
  * [50] T. Liang and J. Stokes.  Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks.  International Conference on Artificial Intelligence and Statistics, 2019.
  * [51] F. Lieder.  On the convergence rate of the Halpern-iteration.  Optimization Letters, 15(2):405–418, 2021.
  * [52] T. Lin, C. Jin, and M. I. Jordan.  Near-optimal algorithms for minimax optimization.  Conference on Learning Theory, 125, 2020.
  * [53] P. L. Lions and B. Mercier.  Splitting algorithms for the sum of two nonlinear operators.  SIAM Journal on Numerical Analysis, 16(6):964–979, 1979.
  * [54] S. I. Lyashko, V. V. Semenov, and T. A. Voitova.  Low-cost modification of Korpelevich’s methods for monotone equilibrium problems.  Cybernetics and Systems Analysis, 47(4):631, 2011.
  * [55] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  International Conference on Learning Representations, 2018.
  * [56] Y. Malitsky.  Projected reflected gradient methods for monotone variational inequalities.  SIAM Journal on Optimization, 25(1):502–520, 2015.
  * [57] Y. Malitsky.  Golden ratio algorithms for variational inequalities.  Mathematical Programming, 184(1):383–410, 2020.
  * [58] Y. Malitsky and M. K. Tam.  A forward-backward splitting method for monotone inclusions without cocoercivity.  SIAM Journal on Optimization, 30(2):1451–1472, 2020.
  * [59] Y. V. Malitsky and V. V. Semenov.  An extragradient algorithm for monotone variational inequalities.  Cybernetics and Systems Analysis, 50(2):271–277, 2014.
  * [60] B. Martinet.  Régularisation d’inéquations variationnelles par approximations successives.  Revue Française d’Informatique et de Recherche Opérationnelle, Série Rouge, 4(3):154–158, 1970.
  * [61] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras.  Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile.  International Conference on Learning Representations, 2019.
  * [62] G. J. Minty.  Monotone (nonlinear) operators in Hilbert space.  Duke Mathematical Journal, 29(3):341–346, 1962.
  * [63] A. Mokhtari, A. Ozdaglar, and S. Pattathil.  A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.  International Conference on Artificial Intelligence and Statistics, 2020.
  * [64] A. Mokhtari, A. E. Ozdaglar, and S. Pattathil.  Convergence rate of $O(1/k)$ for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems.  SIAM Journal on Optimization, 30(4):3230–3251, 2020.
  * [65] R. D. C. Monteiro and B. F. Svaiter.  On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean.  SIAM Journal on Optimization, 20(6):2755–2787, 2010.
  * [66] 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 Journal on Optimization, 21(4):1688–1720, 2011.
  * [67] J. Moreau.  Proximité et dualité dans un espace hilbertien.  Bulletin de la Société Mathématique de France, 93:273–299, 1965.
  * [68] A. Nemirovski.  Prox-method with rate of convergence $O(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.  SIAM Journal on Optimization, 15(1):229–251, 2004.
  * [69] Y. Nesterov.  A method of solving a convex programming problem with convergence rate $O(1/k^{2})$.  Doklady Akademii Nauk SSSR, 269(3):543–547, 1983.
  * [70] Y. Nesterov.  Smooth minimization of non-smooth functions.  Mathematical Programming, 103(1):127–152, 2005.
  * [71] Y. Nesterov.  Dual extrapolation and its applications to solving variational inequalities and related problems.  Mathematical Programming, 109(2):319–344, 2007.
  * [72] Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky.  Primal–dual accelerated gradient methods with small-dimensional relaxation oracle.  Optimization Methods and Software, pages 1–38, 2020.
  * [73] Y. Nesterov and L. Scrimali.  Solving strongly monotone variational and quasi-variational inequalities.  Discrete & Continuous Dynamical Systems, 31(4):1383–1396, 2011\.
  * [74] M. A. Noor.  New extragradient-type methods for general variational inequalities.  Journal of Mathematical Analysis and Applications, 277(2):379–394, 2003.
  * [75] C. Park, J. Park, and E. K. Ryu.  Factor-$\sqrt{2}$ acceleration of accelerated gradient methods.  arXiv:2102.07366, 2021.
  * [76] J. Park and E. K. Ryu.  Exact optimal accelerated complexity for fixed-point iterations.  International Conference on Machine Learning, 2022.
  * [77] W. Peng, Y.-H. Dai, H. Zhang, and L. Cheng.  Training GANs with centripetal acceleration.  Optimization Methods and Software, 35(5):955–973, 2020.
  * [78] L. D. Popov.  A modification of the Arrow–Hurwicz method for search of saddle points.  Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845–848, 1980.
  * [79] H. Rafique, M. Liu, Q. Lin, and T. Yang.  Weakly-convex–concave min–max optimization: Provable algorithms and applications in machine learning.  Optimization Methods and Software, pages 1–35, 2021.
  * [80] A. Rakhlin and K. Sridharan.  Online learning with predictable sequences.  Conference on Learning Theory, 2013.
  * [81] R. T. Rockafellar.  Convex Analysis.  Princeton University Press, 1970.
  * [82] R. T. Rockafellar.  Monotone operators associated with saddle-functions and minimax problems.  In F. E. Browder, editor, Nonlinear Functional Analysis, Part 1, volume 18 of Proceedings of Symposia in Pure Mathematics, pages 241–250. American Mathematical Society, 1970.
  * [83] R. T. Rockafellar.  Monotone operators and the proximal point algorithm.  SIAM Journal on Control and Optimization, 14(5):877–898, 1976.
  * [84] E. K. Ryu and W. Yin.  Large-Scale Convex Optimization via Monotone Operators.  Cambridge University Press, 2022.
  * [85] E. K. Ryu, K. Yuan, and W. Yin.  ODE analysis of stochastic gradient methods with optimism and anchoring for minimax problems and GANs.  arXiv:1905.10899, 2019.
  * [86] A. Sinha, H. Namkoong, and J. C. Duchi.  Certifying some distributional robustness with principled adversarial training.  International Conference on Learning Representations, 2018.
  * [87] M. V. Solodov and B. F. Svaiter.  A hybrid approximate extragradient – proximal point algorithm using the enlargement of a maximal monotone operator.  Set-Valued Analysis, 7(4):323–345, 1999.
  * [88] V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire.  Fast convergence of regularized learning in games.  Neural Information Processing Systems, 2015.
  * [89] A. Taylor and Y. Drori.  An optimal gradient method for smooth strongly convex minimization.  arXiv:2101.09741, 2021.
  * [90] K. K. Thekumparampil, N. He, and S. Oh.  Lifted primal-dual method for bilinearly coupled smooth minimax optimization.  International Conference on Artificial Intelligence and Statistics, 2022.
  * [91] K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh.  Efficient algorithms for smooth minimax optimization.  Neural Information Processing Systems, 2019.
  * [92] Q. Tran-Dinh and Y. Luo.  Halpern-type accelerated and splitting algorithms for monotone inclusions.  arXiv:2110.08150, 2021.
  * [93] P. Tseng.  A modified forward-backward splitting method for maximal monotone mappings.  SIAM Journal on Control and Optimization, 38(2):431–446, 2000.
  * [94] B. C. Vũ.  A splitting algorithm for dual monotone inclusions involving cocoercive operators.  Advances in Computational Mathematics, 38(3):667–681, 2013.
  * [95] Y. Wang and J. Li.  Improved algorithms for convex-concave minimax optimization.  Neural Information Processing Systems, 2020.
  * [96] G. Xie, Y. Han, and Z. Zhang.  DIPPA: An improved method for bilinear saddle point problems.  arXiv preprint arXiv:2103.08270, 2021.
  * [97] A. K. Yadav, S. Shah, Z. Xu, D. W. Jacobs, and T. Goldstein.  Stabilizing adversarial nets with prediction methods.  International Conference on Learning Representations, 2018.
  * [98] M. Yan.  A new primal-dual algorithm for minimizing the sum of three functions with a linear operator.  Journal of Scientific Computing, 76(3):1698–1717, 2018.
  * [99] J. Yang, S. Zhang, N. Kiyavash, and N. He.  A catalyst framework for minimax optimization.  Neural Information Processing Systems, 2020.
  * [100] 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.  International Conference on Machine Learning, 2021.
  * [101] K. Zhou, L. Tian, A. M.-C. So, and J. Cheng.  Practical schemes for finding near-stationary points of convex finite-sums.  International Conference on Artificial Intelligence and Statistics, 2022.

##  Appendix A Algorithm specifications

###  A.1 Classical minimax optimization algorithms

_Simultaneous gradient descent-ascent_ for smooth minimax optimization is
defined by

$\displaystyle x_{k+1}=x_{k}-\alpha\nabla_{x}\mathbf{L}(x_{k},y_{k})$
$\displaystyle y_{k+1}=y_{k}+\alpha\nabla_{y}\mathbf{L}(x_{k},y_{k})$

where $\alpha>0$ is the step-size. Writing $z_{k}=(x_{k},y_{k})$ and using the
$\nabla_{\pm}$ notation, we can more concisely rewrite this as

$\displaystyle z_{k+1}=z_{k}-\alpha\nabla_{\pm}\mathbf{L}(z_{k}).$

The _extragradient (EG)_ algorithm is defined by

$\displaystyle z_{k+1/2}$
$\displaystyle=z_{k}-\alpha\nabla_{\pm}\mathbf{L}(z_{k}),$ $\displaystyle
z_{k+1}$ $\displaystyle=z_{k}-\alpha\nabla_{\pm}\mathbf{L}(z_{k+1/2}).$

The _optimistic gradient descent (OG)_ algorithm is defined by

$\displaystyle
z_{k+1}=z_{k}-\alpha\nabla_{\pm}\mathbf{L}(z_{k})-\alpha\left(\nabla_{\pm}\mathbf{L}(z_{k})-\nabla_{\pm}\mathbf{L}(z_{k-1})\right),$

where $z_{0}=z_{-1}$ are the starting points.

###  A.2 Nesterov’s AGM and its momentum parameters

In his seminal work [69], Nesterov developed the _accelerated gradient method
(AGM)_ for the smooth convex minimization problem

$\displaystyle\underset{x\in\mathbb{R}^{n}}{\textrm{minimize}}\,\,f(x)$ (12)

where $f\colon\mathbb{R}^{n}\to\mathbb{R}$ is convex and $L$-smooth (i.e.,
differentiable with $L$-Lipschitz continuous gradient). Nesterov’s original
AGM has the form

$\displaystyle x_{k+1}$ $\displaystyle=y_{k}-\alpha\nabla f(y_{k})$
$\displaystyle y_{k+1}$
$\displaystyle=x_{k+1}+\frac{t_{k}-1}{t_{k+1}}(x_{k+1}-x_{k})$

with parameters $\alpha=\frac{1}{L}$, $t_{0}=1$ and
$t_{k+1}=\frac{1+\sqrt{1+4t_{k}^{2}}}{2}$ for $k=0,1,\dots$ and has the
convergence rate

$\displaystyle f(x_{k})-f_{\star}\leq\frac{\|x_{0}-x_{\star}\|^{2}}{2\alpha
t_{k-1}^{2}}=\mathcal{O}\left(\frac{L\|x_{0}-x_{\star}\|^{2}}{k^{2}}\right)$

for $k=1,2,\dots$, where $f_{\star}=\min_{x\in\mathbb{R}^{d}}f(x)$.

In the study [11] on the point convergence of the fast iterative shrinkage-
thresholding algorithm (FISTA), which generalizes AGM to the prox-grad setup,
a relaxed parameter selection rule $\alpha\leq\frac{1}{L}$ and
$t_{k+1}^{2}-t_{k+1}-t_{k}^{2}\leq 0$ was used. In particular, with the choice
$t_{k}=(k+a-1)/a$ with $a>2$, the AGM (and FISTA) exhibits point convergence
to a minimizer ($x_{k}\rightarrow x_{\star}$ for some minimizer $x_{\star}$)
while retaining $\mathcal{O}(\|x_{0}-x_{\star}\|^{2}/\alpha k^{2})$
convergence rate [11]. (While $a=2$ leads to the fastest rate in terms of the
function value suboptimality, whether the iterates convergence when $a=2$
remains an open question.) In Figure 1, we use AGM with parameters
$t_{k}=\frac{k+a-1}{a}$.

###  A.3 EAG and APS with iteration-dependent step-sizes

In Section 3, we introduced EAG and APS with constant step-size $\alpha$. On
the other hand, in the prior works introducing EAG [100] and APS [92], these
algorithms were used with iteration-dependent step-sizes. Specifically, the
EAG-V algorithm [100] takes the form

$\displaystyle\begin{aligned}
z_{k+1/2}&=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha_{k}{\varbbB}z_{k}\\\
z_{k+1}&=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha_{k}{\varbbB}z_{k+1/2}\end{aligned}$
(13)

where
$\alpha_{k+1}=\alpha_{k}\left(1-\frac{1}{(k+1)(k+3)}\frac{\alpha_{k}^{2}L^{2}}{1-\alpha_{k}^{2}L^{2}}\right)$
and $\beta_{k}=\frac{1}{k+2}$. The original anchored Popov’s scheme [92] takes
the form

$\displaystyle\begin{aligned}
v_{k+1}&=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha_{k}{\varbbB}v_{k}\\\
z_{k+1}&=\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha_{k}{\varbbB}v_{k+1}\end{aligned}$
(14)

and the convergence analysis was done for
$\alpha_{k+1}=\frac{\alpha_{k}\beta_{k+1}\left(1-\beta_{k}^{2}-M\alpha_{k}^{2}\right)}{\left(1-M\alpha_{k}^{2}\right)\beta_{k}(1-\beta_{k})}$,
$\beta_{k}=\frac{1}{k+2}$, and $M=2L^{2}(1+\theta)$ for some $\theta>0$. We
provide a brief discussion on the MP results for algorithms with iteration-
dependent step-sizes in Section F.

###  A.4 Equivalent forms of OHM and their convergence

Recall that we used the two distinct forms of OHM (in Sections 3 and 5):

$\displaystyle w_{k+1/2}$
$\displaystyle=\frac{1}{k+1}w_{0}+\frac{k}{k+1}w_{k}$ $\displaystyle w_{k+1}$
$\displaystyle={\varbbT}(w_{k+1/2})$

and

$\displaystyle u_{k+1}=\frac{1}{k+2}u_{0}+\frac{k+1}{k+2}{\varbbT}u_{k}.$ (15)

We show that the two forms are equivalent under the identification
$w_{k+1/2}=u_{k}$ in the sense that if $u_{0}=w_{0}=w_{1/2}$, then
$w_{k+1/2}=u_{k}$ for all $k=0,1,\dots$. Suppose that $w_{k+1/2}=u_{k}$ holds
for some $k\geq 0$. Then $w_{k+1}={\varbbT}w_{k+1/2}={\varbbT}u_{k}$, so

$\displaystyle
w_{k+3/2}=\frac{1}{k+2}w_{0}+\frac{k+1}{k+2}w_{k+1}=\frac{1}{k+2}u_{0}+\frac{k+1}{k+2}{\varbbT}u_{k}=u_{k+1}.$

By induction, this shows that if $u_{0}=w_{0}$, then $w_{k+1/2}=u_{k}$ for all
$k=0,1,\dots$.

It is well-known that if is nonexpansive and
$\mathrm{Fix}\,{\varbbT}\neq\emptyset$, the Halpern iteration of the form

$\displaystyle u_{k+1}=\beta_{k}u_{0}+(1-\beta_{k}){\varbbT}u_{k}$

satisfying $\beta_{k}\in(0,1)$, $\sum_{k=0}^{\infty}\beta_{k}=\infty$, and
$\sum_{k=0}^{\infty}|\beta_{k}-\beta_{k+1}|<\infty$ strongly converges to
$\Pi_{\mathrm{Fix}\,{\varbbT}}(u_{0})$ in Hilbert spaces [7, Theorem 30.1].
The particular choice $\beta_{k}=\frac{1}{k+2}$ satisfies these assumptions,
so we see that the OHM iterates $u_{k}$ converge to
$\Pi_{\mathrm{Fix}\,{\varbbT}}(u_{0})$. Because is continuous, this implies
$w_{k+1}={\varbbT}w_{k+1/2}={\varbbT}u_{k}\to{\varbbT}\left(\Pi_{\mathrm{Fix}\,{\varbbT}}(u_{0})\right)=\Pi_{\mathrm{Fix}\,{\varbbT}}(u_{0})$
as $k\to\infty$. The tight convergence rate of OHM with respect to the fixed-
point residual is [51, Theorem 2.1]

$\displaystyle\|w_{k+1/2}-{\varbbT}w_{k+1/2}\|^{2}=\|u_{k}-{\varbbT}u_{k}\|^{2}\leq\frac{4\|u_{0}-u_{\star}\|^{2}}{(k+1)^{2}}$

for any $u_{\star}\in\mathrm{Fix}\,{\varbbT}$ and $k=0,1,\dots$.

###  A.5 Equivalent forms of OC-Halpern

The original form of OC-Halpern [76] was given by

$\displaystyle
u_{k+1}=\frac{1}{\varphi_{k}}u_{0}+\left(1-\frac{1}{\varphi_{k}}\right){\varbbT}u_{k}$

where $\varphi_{k}=\sum_{j=0}^{k+1}\gamma^{2j}$. Through similar analysis as
in Section A.4, one can check that under the identification $w_{k+1/2}=u_{k}$,
the above form is equivalent to

$\displaystyle\begin{aligned}
w_{k+1/2}&=\frac{1}{\sum_{j=0}^{k}\gamma^{2j}}w_{0}+\left(1-\frac{1}{\sum_{j=0}^{k}\gamma^{2j}}\right)w_{k}\\\
w_{k+1}&={\varbbT}(w_{k+1/2}),\end{aligned}$ (16)

which takes the form of (6) with
$\beta_{k}=\left(\sum_{j=0}^{k}\gamma^{2j}\right)^{-1}$, as we described in
Section 4.

###  A.6 Halpern-accelerated Douglas–Rachford splitting

The DRS operator, defined by
${}_{\textrm{DRS}}={\varbbI}-{}_{\alpha{\varbbB}}+{}_{\alpha{\varbbA}}\circ(2{}_{\alpha{\varbbB}}-{\varbbI})$,
is connected to the monotone inclusion problem

$\displaystyle\begin{array}[]{ll}\underset{z\in\mathbb{R}^{d}}{\textrm{find}}&0\in({\varbbA}+{\varbbB})(z)\end{array}$

in the following way: $u_{\star}\in\mathrm{Fix}\,{}_{\textrm{DRS}}$ if and
only if
$w_{\star}={}_{\alpha{\varbbB}}(u_{\star})\in\mathrm{Zer}\,({\varbbA}+{\varbbB})$.
This holds because

$\displaystyle u_{\star}\in\mathrm{Fix}\,{}_{\textrm{DRS}}$ $\displaystyle\iff
u_{\star}={}_{\textrm{DRS}}(u_{\star})=u_{\star}-{}_{\alpha{\varbbB}}(u_{\star})+{}_{\alpha{\varbbA}}\circ(2{}_{\alpha{\varbbB}}-{\varbbI})(u_{\star})$
$\displaystyle\iff
w_{\star}={}_{\alpha{\varbbA}}(2w_{\star}-u_{\star})={}_{\alpha{\varbbA}}(w_{\star}-\alpha{\varbbB}w_{\star})$
$\displaystyle\iff
w_{\star}+\alpha{\varbbA}w_{\star}=({\varbbI}+\alpha{\varbbA})(w_{\star})\ni
w_{\star}-\alpha{\varbbB}w_{\star}$ $\displaystyle\iff
0\in({\varbbA}+{\varbbB})(w_{\star}),$

where in the second line, we use
$u_{\star}=({\varbbI}+\alpha{\varbbB})(w_{\star})\implies
2w_{\star}-u_{\star}=w_{\star}-\alpha{\varbbB}w_{\star}$.

Given $u_{k}$, letting $w_{k}={}_{\alpha{\varbbB}}(u_{k})$ and
$v_{k}={}_{\alpha{\varbbA}}\circ(2{}_{\alpha{\varbbB}}-{\varbbI})(u_{k})={}_{\alpha{\varbbA}}(2w_{k}-u_{k})$,
we can write ${}_{\textrm{DRS}}(u_{k})=u_{k}-w_{k}+v_{k}$. Therefore, the OHM
(15) applied with ${\varbbT}={}_{\textrm{DRS}}$ can be written as

$\displaystyle w_{k}$ $\displaystyle={}_{\alpha{\varbbB}}(u_{k})$
$\displaystyle v_{k}$ $\displaystyle={}_{\alpha{\varbbA}}(2w_{k}-u_{k})$ (17)
$\displaystyle u_{k+1}$
$\displaystyle=\beta_{k}u_{0}+(1-\beta_{k})(u_{k}+v_{k}-w_{k})$

where $\beta_{k}=\frac{1}{k+2}$. But
$2w_{k}-u_{k}=2w_{k}-(w_{k}+\alpha{\varbbB}w_{k})=w_{k}-\alpha{\varbbB}w_{k}$,
so $v_{k}={}_{\alpha{\varbbA}}(w_{k}-\alpha{\varbbB}w_{k})$. Therefore, we can
rewrite (17) as

$\displaystyle w_{k}$ $\displaystyle={}_{\alpha{\varbbB}}(u_{k})$
$\displaystyle u_{k+1}$
$\displaystyle=\beta_{k}u_{0}+(1-\beta_{k})({}_{\alpha{\varbbA}}(w_{k}-\alpha{\varbbB}w_{k})+\alpha{\varbbB}w_{k})$

by eliminating the second line and replacing $u_{k}$ by
$w_{k}+\alpha{\varbbB}w_{k}$ and $v_{k}$ by
${}_{\alpha{\varbbA}}(w_{k}-\alpha{\varbbB}w_{k})$ in the third line of (17).
The rewritten version precisely agrees with OHM-DRS we presented in Section
5.2. Additionally, observe that

$\displaystyle
u_{k}-{}_{\textrm{DRS}}(u_{k})=w_{k}-v_{k}=w_{k}-{}_{\alpha{\varbbA}}(w_{k}-\alpha{\varbbB}w_{k})=\alpha{}_{\alpha}(w_{k}).$

As ${}_{\textrm{DRS}}$ is nonexpansive [53], by the discussion of Section A.4,
(17) and OHM-DRS satisfy

$\displaystyle\|\alpha{}_{\alpha}(w_{k})\|^{2}=\|u_{k}-{}_{\textrm{DRS}}(u_{k})\|^{2}\leq\frac{4\|u_{0}-u_{\star}\|^{2}}{(k+1)^{2}}$
(18)

where $u_{\star}\in\mathrm{Fix}\,{}_{\textrm{DRS}}$.

##  Appendix B Omitted proofs for Section 3

###  B.1 Proof of Lemma 2

It remains to prove that

$\displaystyle
V_{k}=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$

with $p_{k}=\frac{\alpha k^{2}}{2}$ and $q_{k}=k$ satisfies $V_{k}\geq 0$ and

$\displaystyle
V_{k}-V_{k+1}\geq\frac{\alpha(1-\alpha^{2}L^{2})}{2}\|k{\varbbB}z_{k}-(k+1){\varbbB}z_{k+1/2}\|^{2}$
(19)

for $k=0,1,\dots$. The first part (nonnegativity) is easy to show:

$\displaystyle V_{k}\geq\frac{\alpha
k^{2}}{2}\|{\varbbB}z_{k}\|^{2}+k\langle{\varbbB}z_{k},z_{\star}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}\geq
0,$

where the first inequality follows from monotonicity
$\langle{\varbbB}z_{k},z_{k}-z_{\star}\rangle\geq 0$ (as
${\varbbB}z_{\star}=0$) and the second one is Young’s inequality. Next, we
show (19).

#### Case $k=0$.

We have $z_{1/2}=z_{0}$ and
$z_{1}=z_{0}-\alpha{\varbbB}z_{1/2}=z_{0}-\alpha{\varbbB}z_{0}$,
$V_{0}=\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$, and

$\displaystyle V_{1}$
$\displaystyle=\frac{\alpha}{2}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},z_{1}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$
$\displaystyle=\frac{\alpha}{2}\|{\varbbB}z_{1}\|^{2}-\alpha\langle{\varbbB}z_{1},{\varbbB}z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}.$

Because is $L$-Lipschitz,

$\displaystyle\|{\varbbB}z_{1}-{\varbbB}z_{0}\|^{2}\leq
L^{2}\|z_{1}-z_{0}\|^{2}=\alpha^{2}L^{2}\|{\varbbB}z_{0}\|^{2}$

and by multiplying $\frac{\alpha}{2}$ on both sides and rearranging terms, we
get

$\displaystyle\frac{\alpha}{2}\|{\varbbB}z_{1}\|^{2}-\alpha\langle{\varbbB}z_{1},{\varbbB}z_{0}\rangle\leq-\frac{\alpha}{2}(1-\alpha^{2}L^{2})\|{\varbbB}z_{0}\|^{2}=-\frac{\alpha}{2}(1-\alpha^{2}L^{2})\|{\varbbB}z_{1/2}\|^{2}.$

Adding $\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$, the above inequality
becomes

$\displaystyle V_{1}\leq
V_{0}-\frac{\alpha}{2}(1-\alpha^{2}L^{2})\|{\varbbB}z_{1/2}\|^{2},$

proving (19) for $k=0$.

#### Case $k\geq 1$.

From the definition of the FEG iterates, we have the identities

$\displaystyle z_{k+1}-z_{0}$
$\displaystyle=(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}z_{k+1/2}$
$\displaystyle z_{k}-z_{k+1}$
$\displaystyle=\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}z_{k+1/2}$ $\displaystyle
z_{k+1/2}-z_{k+1}$
$\displaystyle=\alpha{\varbbB}z_{k+1/2}-\alpha(1-\beta_{k}){\varbbB}z_{k}.$

Therefore, because $q_{k+1}=\frac{q_{k}}{1-\beta_{k}}$,

$\displaystyle V_{k}-V_{k+1}$ $\displaystyle\geq
V_{k}-V_{k+1}-\frac{q_{k}}{\beta_{k}}\langle
z_{k}-z_{k+1},{\varbbB}z_{k}-{\varbbB}z_{k+1}\rangle$
$\displaystyle=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle$
$\displaystyle\quad-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}-q_{k+1}\langle{\varbbB}z_{k+1},(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}z_{k+1/2}\rangle$
$\displaystyle\quad-\frac{q_{k}}{\beta_{k}}\langle\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}z_{k+1/2},{\varbbB}z_{k}-{\varbbB}z_{k+1}\rangle$
$\displaystyle=p_{k}\|{\varbbB}z_{k}\|^{2}-\frac{\alpha
q_{k}}{\beta_{k}}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\frac{\alpha
q_{k}}{\beta_{k}(1-\beta_{k})}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}.$

Plugging in $\beta_{k}=\frac{1}{k+1}$, $p_{k}=\frac{\alpha k^{2}}{2}$,
$p_{k+1}=\frac{\alpha(k+1)^{2}}{2}$ and $q_{k}=k$, the inequality becomes

$\displaystyle\begin{aligned} V_{k}-V_{k+1}&\geq\frac{\alpha
k^{2}}{2}\|{\varbbB}z_{k}\|^{2}-\alpha
k(k+1)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle\\\
&\quad+\alpha(k+1)^{2}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-\frac{\alpha(k+1)^{2}}{2}\|{\varbbB}z_{k+1}\|^{2}.\end{aligned}$
(20)

Recall that is $L$-Lipschitz, so

$\displaystyle 0$ $\displaystyle\geq
L^{2}\|z_{k+1/2}-z_{k+1}\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}$
$\displaystyle=\alpha^{2}L^{2}\left\|{\varbbB}z_{k+1/2}-\frac{k}{k+1}{\varbbB}z_{k}\right\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}.$

Multiplying $\frac{\alpha(k+1)^{2}}{2}$ to the above inequality and combining
with (20), we lower-bound $V_{k}-V_{k+1}$ as

$\displaystyle V_{k}-V_{k+1}$ $\displaystyle\geq\frac{\alpha
k^{2}}{2}\|{\varbbB}z_{k}\|^{2}-\alpha
k(k+1)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\alpha(k+1)^{2}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-\frac{\alpha(k+1)^{2}}{2}\|{\varbbB}z_{k+1}\|^{2}$
$\displaystyle\quad-\frac{\alpha(k+1)^{2}}{2}\left(\alpha^{2}L^{2}\left\|{\varbbB}z_{k+1/2}-\frac{k}{k+1}{\varbbB}z_{k}\right\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}\right)$
$\displaystyle=\left(\frac{\alpha
k^{2}}{2}-\frac{\alpha^{3}L^{2}}{2}k^{2}\right)\|{\varbbB}z_{k}\|^{2}+\left(\alpha^{3}L^{2}k(k+1)-\alpha
k(k+1)\right)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle$
$\displaystyle\quad+\frac{\alpha(k+1)^{2}}{2}(1-\alpha^{2}L^{2})\|{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle=\frac{\alpha(1-\alpha^{2}L^{2})}{2}\|k{\varbbB}z_{k}-(k+1){\varbbB}z_{k+1/2}\|^{2},$

proving (19).

###  B.2 Remaining proof of Theorem 1

We first consider the case of EAG. As before, denote the Halpern iterates by
$\\{w_{k}\\}_{k=0,1,\dots}$ and the EAG iterates by
$\\{z_{k}\\}_{k=0,1,\dots}$. Then in the exact same way as before, we have

$\displaystyle z_{k+1}-w_{k+1}$
$\displaystyle=\left(\beta_{k}z_{0}+(1-\beta_{k})z_{k}-\alpha{\varbbB}z_{k+1/2}\right)-\left(\beta_{k}w_{0}+(1-\beta_{k})w_{k}-\alpha{\varbbB}w_{k+1}\right)$
$\displaystyle=(1-\beta_{k})(z_{k}-w_{k})+\alpha\left({\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right),$

and

$\displaystyle\begin{aligned}
\left\|z_{k+1}-w_{k+1}\right\|^{2}&=(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}+2\left\langle\alpha(1-\beta_{k})(z_{k}-w_{k}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle\\\
&\quad\quad+\alpha^{2}\left\|{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\|^{2}.\end{aligned}$
(21)

The different part is

$\displaystyle
z_{k+1/2}-w_{k+1}=(1-\beta_{k})(z_{k}-w_{k})-\alpha{\varbbB}z_{k}+\alpha{\varbbB}w_{k+1}$

so that inner product term in (21) is rewritten as

$\displaystyle
2\left\langle\alpha(1-\beta_{k})(z_{k}-w_{k}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle=2\left\langle\alpha(z_{k+1/2}-w_{k+1})+\alpha^{2}\left({\varbbB}z_{k}-{\varbbB}w_{k+1}\right),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle\leq
2\alpha^{2}\left\langle{\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle.$

Combining this with (21), we obtain

$\displaystyle\left\|z_{k+1}-w_{k+1}\right\|^{2}$
$\displaystyle\leq(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}+2\alpha^{2}\left\langle{\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle+\alpha^{2}\left\|{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\|^{2}$
$\displaystyle=(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}\underbrace{-\,\alpha^{2}\left\|{\varbbB}w_{k+1}\right\|^{2}+2\alpha^{2}\langle{\varbbB}z_{k},{\varbbB}w_{k+1}\rangle}_{\leq\alpha^{2}\|{\varbbB}z_{k}\|^{2}}-2\alpha^{2}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\alpha^{2}\|{\varbbB}z_{k+1/2}\|^{2}$

Plugging in $\beta_{k}=\frac{1}{k+1}$ and multiplying both sides by
$(k+1)^{2}$ gives

$\displaystyle(k+1)^{2}\left\|z_{k+1}-w_{k+1}\right\|^{2}\leq$
$\displaystyle\,k^{2}\left\|z_{k}-w_{k}\right\|^{2}+\alpha^{2}(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}.$

Now, with the following Lemma 9, the proof for EAG is done.

######  Lemma 9.

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be monotone and
$L$-Lipschitz and assume $z_{\star}\in\mathrm{Zer}\,{\varbbB}$ exists. Let
$\\{z_{k}\\}_{k=0,1,\dots}$ be the iterates of EAG with
$\beta_{k}=\frac{1}{k+1}$. Then there exists $\eta\in(0,1)$ and $C>0$ such
that for $\alpha\in\left(0,\frac{\eta}{L}\right)$,

$\displaystyle\sum_{k=0}^{\infty}(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\leq\frac{C}{\alpha^{2}}\|z_{0}-z_{\star}\|^{2}<\infty.$

For the case of APS, proceeding with ${\varbbB}z_{k},{\varbbB}z_{k+1/2}$
replaced by ${\varbbB}v_{k},{\varbbB}v_{k+1}$ respectively, we get

$\displaystyle(k+1)^{2}\left\|z_{k+1}-w_{k+1}\right\|^{2}\leq$
$\displaystyle\,k^{2}\left\|z_{k}-w_{k}\right\|^{2}+\alpha^{2}(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$

and the proof is complete once we show:

######  Lemma 10.

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be monotone and
$L$-Lipschitz and assume $z_{\star}\in\mathrm{Zer}\,{\varbbB}$ exists. Let
$\\{z_{k}\\}_{k=0,1,\dots}$ be the iterates of APS with
$\beta_{k}=\frac{1}{k+1}$. Then there exists $\eta\in(0,1)$ and $C>0$ such
that for $\alpha\in\left(0,\frac{\eta}{L}\right)$,

$\displaystyle\sum_{k=0}^{\infty}(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}\leq\frac{C}{\alpha^{2}}\|z_{0}-z_{\star}\|^{2}<\infty.$

The proofs of Lemmas 9 and 10 follow from arguments similar to that of Lemma
2. However, they are much more lengthy, so defer their proofs to Appendix E.

##  Appendix C Omitted proofs for Section 4

###  C.1 Proof of Lemma 4

Denote the iterates of OC-Halpern (16) by $\\{w_{k}\\}_{k=0,1,\dots}$ and SM-
EAG+ iterates by $\\{z_{k}\\}_{k=0,1,\dots}$. Then as in Section 3, we have

$\displaystyle\left\|z_{k+1}-w_{k+1}\right\|^{2}$
$\displaystyle=(1-\beta_{k})^{2}\left\|z_{k}-w_{k}\right\|^{2}+2\left\langle\alpha(1-\beta_{k})(z_{k}-w_{k}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle\quad+\alpha^{2}\left\|{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\|^{2}.$

Using

$\displaystyle
z_{k+1/2}-w_{k+1}=(1-\beta_{k})(z_{k}-w_{k})-\eta_{k}\alpha{\varbbB}z_{k}+\alpha{\varbbB}w_{k+1},$

we get

$\displaystyle
2\left\langle\alpha(1-\beta_{k})(z_{k}-w_{k}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle=2\left\langle\alpha(z_{k+1/2}-w_{k+1})+\alpha^{2}(\eta_{k}{\varbbB}z_{k}-{\varbbB}w_{k+1}),{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
$\displaystyle\leq-2\alpha\mu\|z_{k+1/2}-w_{k+1}\|^{2}+2\alpha^{2}\left\langle\eta_{k}{\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle$
(22)

where the last line uses $\mu$-strong monotonicity of . For any
$\epsilon\in(0,1)$ and $x,y\in\mathbb{R}^{d}$, we have

$\displaystyle\epsilon\|x\|^{2}+\frac{1}{\epsilon}\|y\|^{2}\geq 2\langle
x,y\rangle\implies\|x-y\|^{2}\geq(1-\epsilon)\|x\|^{2}-\left(\frac{1}{\epsilon}-1\right)\|y\|^{2}.$

Using the last inequality with $x=z_{k+1}-w_{k+1}$ and
$y=z_{k+1}-z_{k+1/2}=\alpha(\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2})$, we
can upper-bound (22) by

$\displaystyle-2\alpha\mu\left((1-\epsilon)\|z_{k+1}-w_{k+1}\|^{2}-\left(\frac{1}{\epsilon}-1\right)\alpha^{2}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\right)$
$\displaystyle\quad+2\alpha^{2}\left\langle\eta_{k}{\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle.$

Thus,

$\displaystyle\|z_{k+1}-w_{k+1}\|^{2}$
$\displaystyle\leq(1-\beta_{k})^{2}\|z_{k}-w_{k}\|^{2}-2\alpha\mu\left((1-\epsilon)\|z_{k+1}-w_{k+1}\|^{2}-\left(\frac{1}{\epsilon}-1\right)\alpha^{2}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\right)$
$\displaystyle\quad+2\alpha^{2}\left\langle\eta_{k}{\varbbB}z_{k}-{\varbbB}w_{k+1},{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\rangle+\alpha^{2}\left\|{\varbbB}w_{k+1}-{\varbbB}z_{k+1/2}\right\|^{2}$

and rearranging, we obtain

$\displaystyle(1+2\alpha\mu(1-\epsilon))\|z_{k+1}-w_{k+1}\|^{2}$
$\displaystyle\leq(1-\beta_{k})^{2}\|z_{k}-w_{k}\|^{2}+2\alpha\mu\left(\frac{1}{\epsilon}-1\right)\alpha^{2}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\quad\underbrace{-\alpha^{2}\|{\varbbB}w_{k+1}\|^{2}+2\eta_{k}\alpha^{2}\langle{\varbbB}w_{k+1},{\varbbB}z_{k}\rangle}_{\leq\eta_{k}^{2}\alpha^{2}\|{\varbbB}z_{k}\|^{2}}-2\eta_{k}\alpha^{2}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\alpha^{2}\|{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\leq(1-\beta_{k})^{2}\|z_{k}-w_{k}\|^{2}+\left(1+2\alpha\mu\left(\frac{1}{\epsilon}-1\right)\right)\alpha^{2}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$

Thus, provided that the following Lemma 11 (in particular (23)) holds, we have

$\displaystyle(1+2\alpha\mu(1-\epsilon))^{k+1}\|z_{k+1}-w_{k+1}\|^{2}$
$\displaystyle\quad\quad\leq(1+2\alpha\mu(1-\epsilon))^{k}\|z_{k}-w_{k}\|^{2}+(1+2\alpha\mu)^{k}\left(1+2\alpha\mu\left(\frac{1}{\epsilon}-1\right)\right)\alpha^{2}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\quad\quad\leq\cdots\leq\left(1+2\alpha\mu\left(\frac{1}{\epsilon}-1\right)\right)\alpha^{2}\sum_{j=0}^{k}(1+2\alpha\mu)^{j}\|\eta_{j}{\varbbB}z_{j}-{\varbbB}z_{j+1/2}\|^{2}$
$\displaystyle\quad\quad\leq\left(1+2\alpha\mu\left(\frac{1}{\epsilon}-1\right)\right)\frac{1+2\alpha\mu}{1+2\alpha\mu-\alpha^{2}L^{2}}\|z_{0}-z_{\star}\|^{2},$

i.e., the two algorithms have
$\mathcal{O}\left(\frac{\|z_{0}-z_{\star}\|^{2}}{(1+2\alpha\mu(1-\epsilon))^{k}}\right)=\mathcal{O}\left(e^{-2k\alpha\mu(1-\epsilon)}\|z_{0}-z_{\star}\|^{2}\right)$-MP.

######  Lemma 11.

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be a $\mu$-strongly
monotone, $L$-Lipschitz operator ($0<\mu\leq L$), and let
$\\{z_{k}\\}_{k=0,1,\dots}$ be the iterates of SM-EAG+ with
$\beta_{k}=\frac{1}{\sum_{j=0}^{k}(1+2\alpha\mu)^{j}}$. Then, the quantities

$\displaystyle
V_{k}=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k}-\mu(z_{k}-z_{0}),z_{k}-z_{0}\rangle+\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}$

with $p_{0}=q_{0}=0$ and
$q_{k}=\frac{1}{(1+2\alpha\mu)^{k-1}}\frac{1}{\beta_{k-1}}$,
$p_{k}=\frac{\eta_{k}\alpha q_{k}}{2\beta_{k}}$ for $k=1,2,\dots$ satisfy
$V_{k}\geq 0$,
$V_{0}-V_{1}\geq\frac{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})}{2}\|{\varbbB}z_{0}\|^{2}$,
and

$\displaystyle
V_{k}-V_{k+1}\geq\frac{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})q_{k}}{2\beta_{k}(1-\beta_{k})}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$

for $k=1,2,\dots$. In particular, if
$\alpha\in\big{(}0,\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}\big{]}$, $V_{k}$ is
a Lyapunov function for the algorithm, and if
$\alpha\in\big{(}0,\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}\big{)}$, we
additionally have the summability result

$\displaystyle\sum_{k=0}^{\infty}(1+2\alpha\mu)^{k}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\leq\frac{1+2\alpha\mu}{\alpha^{2}(1+2\alpha\mu-\alpha^{2}L^{2})}\|z_{0}-z_{\star}\|^{2}<\infty.$
(23)

###  C.2 Proof of Lemma 11

Due to the subtlety caused by setting $\beta_{0}=1$, we divide the cases $k=0$
and $k\geq 1$.

#### Case $k=0$.

We have $z_{1/2}=z_{0}$, $z_{1}=z_{0}-\alpha{\varbbB}z_{0}$,
$V_{0}=\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}$, and

$\displaystyle V_{1}$
$\displaystyle=\frac{\alpha}{2}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1}-\mu(z_{1}-z_{0}),z_{1}-z_{0}\rangle+\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}$
$\displaystyle=\frac{\alpha}{2}\|{\varbbB}z_{1}\|^{2}-\alpha\langle{\varbbB}z_{1},{\varbbB}z_{0}\rangle-\alpha^{2}\mu\|{\varbbB}z_{0}\|^{2}+\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}.$

Because is $L$-Lipschitz,

$\displaystyle 0$ $\displaystyle\leq
L^{2}\|z_{1}-z_{0}\|^{2}-\|{\varbbB}z_{1}-{\varbbB}z_{0}\|^{2}$
$\displaystyle=(\alpha^{2}L^{2}-1)\|{\varbbB}z_{0}\|^{2}+2\langle{\varbbB}z_{0},{\varbbB}z_{1}\rangle-\|{\varbbB}z_{1}\|^{2}.$

Therefore,

$\displaystyle V_{0}-V_{1}$
$\displaystyle=\alpha^{2}\mu\|{\varbbB}z_{0}\|^{2}+\alpha\langle{\varbbB}z_{0},{\varbbB}z_{1}\rangle-\frac{\alpha}{2}\|{\varbbB}z_{1}\|^{2}$
$\displaystyle=\frac{\alpha}{2}(1+2\alpha\mu-\alpha^{2}L^{2})\|{\varbbB}z_{0}\|^{2}+\frac{\alpha}{2}\left((\alpha^{2}L^{2}-1)\|{\varbbB}z_{0}\|^{2}+2\langle{\varbbB}z_{0},{\varbbB}z_{1}\rangle-\|{\varbbB}z_{1}\|^{2}\right)$
$\displaystyle\geq\frac{\alpha}{2}(1+2\alpha\mu-\alpha^{2}L^{2})\|{\varbbB}z_{0}\|^{2}$
$\displaystyle=\frac{\alpha}{2}(1+2\alpha\mu-\alpha^{2}L^{2})\|\eta_{0}{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}$

where the last equality holds because $\eta_{0}=0$ and $z_{1/2}=z_{0}$.

#### Case $k\geq 1$.

We have the identities

$\displaystyle z_{k+1}-z_{0}$
$\displaystyle=(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}z_{k+1/2}$ (24)
$\displaystyle z_{k}-z_{k+1}$
$\displaystyle=\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}z_{k+1/2}$ (25)
$\displaystyle z_{k+1/2}-z_{k+1}$
$\displaystyle=\alpha{\varbbB}z_{k+1/2}-\eta_{k}\alpha{\varbbB}z_{k}.$ (26)

Note that $\beta_{k}=\frac{1}{\sum_{j=0}^{k}(1+2\alpha\mu)^{j}}$ satisfies

$\displaystyle\frac{1}{\beta_{k+1}}=\sum_{j=0}^{k+1}(1+2\alpha\mu)^{j}=1+(1+2\alpha\mu)\sum_{j=0}^{k}(1+2\alpha\mu)^{j}=1+\frac{1+2\alpha\mu}{\beta_{k}}$

for all $k=0,1,\dots$, so
$q_{k}=\frac{1}{(1+2\alpha\mu)^{k-1}}\frac{1}{\beta_{k-1}}$ satisfies the
recurrence relation

$\displaystyle
q_{k+1}=\frac{q_{k}}{\beta_{k}}\frac{\beta_{k-1}}{(1+2\alpha\mu)}=\frac{q_{k}}{\beta_{k}}\frac{1}{\frac{1}{\beta_{k}}-1}=\frac{q_{k}}{1-\beta_{k}}$
(27)

for $k=1,2,\dots$. Additionally, because
$\eta_{k}=\frac{1-\beta_{k}}{1+2\alpha\mu}$ and $p_{k}=\frac{\eta_{k}\alpha
q_{k}}{2\beta_{k}}$,

$\displaystyle
p_{k}=\frac{\alpha(1-\beta_{k})q_{k}}{2\beta_{k}(1+2\alpha\mu)}=\frac{\alpha}{2}\left(\frac{1}{\beta_{k}}-1\right)\frac{q_{k}}{1+2\alpha\mu}=\frac{\alpha}{2}\frac{1}{\beta_{k-1}}q_{k}=\frac{\alpha}{2}(1+2\alpha\mu)^{k-1}q_{k}^{2}$
(28)

and

$\displaystyle p_{k+1}$ $\displaystyle=\frac{\eta_{k+1}\alpha
q_{k+1}}{2\beta_{k+1}}=\frac{\alpha
q_{k+1}}{2\beta_{k+1}}\frac{1-\beta_{k+1}}{1+2\alpha\mu}=\frac{\alpha
q_{k}}{2(1-\beta_{k})}\frac{1-\beta_{k+1}}{(1+2\alpha\mu)\beta_{k+1}}$
$\displaystyle=\frac{\alpha
q_{k}}{2(1-\beta_{k})}\frac{1}{1+2\alpha\mu}\left(\frac{1}{\beta_{k+1}}-1\right)=\frac{\alpha
q_{k}}{2\beta_{k}(1-\beta_{k})}.$ (29)

The identities (27) through (29) will be useful for the subsequent arguments.

Using $\mu$-strong monotonicity of and the identities (24), (25) and (27), we
have

$\displaystyle V_{k}-V_{k+1}$ $\displaystyle\geq
V_{k}-V_{k+1}-\frac{q_{k}}{\beta_{k}}\langle
z_{k}-z_{k+1},{\varbbB}z_{k}-{\varbbB}z_{k+1}-\mu(z_{k}-z_{k+1})\rangle$
$\displaystyle=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle-
q_{k}\mu\|z_{k}-z_{0}\|^{2}$ $\displaystyle\quad-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}-q_{k+1}\langle{\varbbB}z_{k+1},(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}z_{k+1/2}\rangle$
$\displaystyle\quad+q_{k+1}\mu\left\|(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}z_{k+1/2}\right\|^{2}$
$\displaystyle\quad-\frac{q_{k}}{\beta_{k}}\langle\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}z_{k+1/2},{\varbbB}z_{k}-{\varbbB}z_{k+1}\rangle$
$\displaystyle\quad+\frac{q_{k}\mu}{\beta_{k}}\left\|\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}z_{k+1/2}\right\|^{2}$
$\displaystyle\begin{aligned} &=p_{k}\|{\varbbB}z_{k}\|^{2}-\frac{\alpha
q_{k}}{\beta_{k}}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\mu\alpha^{2}\left(\frac{q_{k}}{\beta_{k}}+q_{k+1}\right)\|{\varbbB}z_{k+1/2}\|^{2}\\\
&\quad+\alpha\left(\frac{q_{k}}{\beta_{k}}+q_{k+1}\right)\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}\\\
&\quad+2\mu\alpha\left(q_{k}-(1-\beta_{k})q_{k+1}\right)\langle{\varbbB}z_{k+1/2},z_{k}-z_{0}\rangle\\\
&\quad+(q_{k}-(1-\beta_{k})q_{k+1})\langle{\varbbB}z_{k+1},z_{k}-z_{0}\rangle\\\
&\quad+\mu(1-\beta_{k})((1-\beta_{k})q_{k+1}-q_{k})\|z_{k}-z_{0}\|^{2}\end{aligned}$
$\displaystyle\begin{aligned} &=p_{k}\|{\varbbB}z_{k}\|^{2}-\frac{\alpha
q_{k}}{\beta_{k}}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\frac{\mu\alpha^{2}q_{k}}{\beta_{k}(1-\beta_{k})}\|{\varbbB}z_{k+1/2}\|^{2}\\\
&\quad+\frac{\alpha
q_{k}}{\beta_{k}(1-\beta_{k})}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}.\end{aligned}$ (30)

Now because is $L$-Lipschitz,

$\displaystyle\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}\leq
L^{2}\|z_{k+1/2}-z_{k+1}\|^{2}=L^{2}\|\alpha{\varbbB}z_{k+1/2}-\eta_{k}\alpha{\varbbB}z_{k}\|^{2}$

where we applied the identity (26) for the last equality. Hence, using the
above inequality, we obtain

$\displaystyle\eqref{eqn:sm-
EAG_Lyapunov_monotone}-p_{k+1}\left(L^{2}\|\alpha{\varbbB}z_{k+1/2}-\eta_{k}\alpha{\varbbB}z_{k}\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}\right)$
$\displaystyle=(p_{k}-p_{k+1}\eta_{k}^{2}\alpha^{2}L^{2})\|{\varbbB}z_{k}\|^{2}-\left(\frac{\alpha
q_{k}}{\beta_{k}}-2p_{k+1}\eta_{k}\alpha^{2}L^{2}\right)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle$
$\displaystyle\quad+\left(\frac{\mu\alpha^{2}q_{k}}{\beta_{k}(1-\beta_{k})}+p_{k+1}(1-\alpha^{2}L^{2})\right)\|{\varbbB}z_{k+1/2}\|^{2}+\left(\frac{\alpha
q_{k}}{\beta_{k}(1-\beta_{k})}-2p_{k+1}\right)\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle$
$\displaystyle\begin{aligned} &=\frac{\eta_{k}\alpha
q_{k}}{2\beta_{k}}\left(1-\frac{\eta_{k}\alpha^{2}L^{2}}{1-\beta_{k}}\right)\|{\varbbB}z_{k}\|^{2}-\frac{\alpha
q_{k}}{\beta_{k}}\left(1-\frac{\eta_{k}\alpha^{2}L^{2}}{1-\beta_{k}}\right)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle\\\
&\quad+\frac{\alpha
q_{k}}{2\beta_{k}(1-\beta_{k})}(1+2\alpha\mu-\alpha^{2}L^{2})\|{\varbbB}z_{k+1/2}\|^{2},\end{aligned}$
(31)

where the coefficient of the $\|{\varbbB}z_{k+1}\|^{2}$ vanishes due to (29).
Because $\eta_{k}=\frac{1-\beta_{k}}{1+2\alpha\mu}$, we have

$\displaystyle
1-\frac{\eta_{k}\alpha^{2}L^{2}}{1-\beta_{k}}=\eta_{k}\left(\frac{1}{\eta_{k}}-\frac{\alpha^{2}L^{2}}{1-\beta_{k}}\right)=\frac{\eta_{k}(1+2\alpha\mu-\alpha^{2}L^{2})}{1-\beta_{k}}$

and thus, (31) becomes

$\displaystyle\frac{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})q_{k}}{2\beta_{k}(1-\beta_{k})}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}.$

As $1+2\alpha\mu-\alpha^{2}L^{2}\geq 0$ if
$0<\alpha\leq\frac{\sqrt{L^{2}+\mu^{2}}+\mu}{L^{2}}$, for this range of
$\alpha$,

$\displaystyle V_{k}-V_{k+1}$
$\displaystyle\geq\frac{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})q_{k}}{2\beta_{k}(1-\beta_{k})}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\geq\frac{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})}{2}(1+2\alpha\mu)^{k}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\geq
0,$

where we used $\frac{q_{k}}{1-\beta_{k}}=q_{k+1}>1$ and
$\frac{1}{\beta_{k}}=\sum_{j=0}^{k}(1+2\alpha\mu)^{j}>(1+2\alpha\mu)^{k}$.
Therefore, once we show that $V_{N}\geq 0$ holds for any $N\in\mathbb{N}$, we
obtain

$\displaystyle\sum_{k=0}^{N}(1+2\alpha\mu)^{k}\|\eta_{k}{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\leq\frac{2}{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})}(V_{0}-V_{N+1})$
$\displaystyle\quad\leq\frac{2}{\alpha(1+2\alpha\mu-\alpha^{2}L^{2})}\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}=\frac{1+2\alpha\mu}{\alpha^{2}(1+2\alpha\mu-\alpha^{2}L^{2})}\|z_{0}-z_{\star}\|^{2}.$

Taking $N\to\infty$, we conclude that (23) holds.

#### Nonnegativity of $V_{k}$.

Define

$\displaystyle
W_{k}=V_{k}-\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k}-\mu(z_{k}-z_{0}),z_{k}-z_{0}\rangle,$

which is a shifted version of $V_{k}$. Because is $\mu$-strongly monotone, we
have

$\displaystyle\langle{\varbbB}z_{k}-\mu(z_{k}-z_{\star}),z_{k}-z_{\star}\rangle\geq
0.$

Subtracting $\lambda\geq 0$ times the above inequality from $W_{k}$ gives

$\displaystyle W_{k}$ $\displaystyle\geq
p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k}-\mu(z_{k}-z_{0}),z_{k}-z_{0}\rangle-\lambda\langle{\varbbB}z_{k}-\mu(z_{k}-z_{\star}),z_{k}-z_{\star}\rangle$
$\displaystyle=p_{k}\|{\varbbB}z_{k}\|^{2}+\langle{\varbbB}z_{k},q_{k}(z_{k}-z_{0})-\lambda(z_{k}-z_{\star})\rangle-
q_{k}\mu\|z_{k}-z_{0}\|^{2}+\lambda\mu\|z_{k}-z_{\star}\|^{2}$
$\displaystyle\begin{aligned}
&=p_{k}\|{\varbbB}z_{k}\|^{2}+\langle{\varbbB}z_{k},(q_{k}-\lambda)z_{k}-q_{k}z_{0}+\lambda
z_{\star}\rangle\\\ &\quad+\mu(\lambda-q_{k})\|z_{k}\|^{2}+2\mu\langle
z_{k},q_{k}z_{0}-\lambda z_{\star}\rangle-
q_{k}\mu\|z_{0}\|^{2}+\lambda\mu\|z_{\star}\|^{2}\end{aligned}$ (32)

Observe that if $\lambda>q_{k}$, we can rewrite the terms not involving
${\varbbB}z_{k}$ in (32) as

$\displaystyle\mu(\lambda-q_{k})\|z_{k}\|^{2}+2\mu\langle
z_{k},q_{k}z_{0}-\lambda z_{\star}\rangle-
q_{k}\mu\|z_{0}\|^{2}+\lambda\mu\|z_{\star}\|^{2}$
$\displaystyle=\frac{\mu}{\lambda-q_{k}}\left\|(\lambda-
q_{k})z_{k}+q_{k}z_{0}-\lambda z_{\star}\right\|^{2}-\frac{\mu}{\lambda-
q_{k}}\|q_{k}z_{0}-\lambda
z_{\star}\|^{2}-q_{k}\mu\|z_{0}\|^{2}+\lambda\mu\|z_{\star}\|^{2}$
$\displaystyle=\frac{\mu}{\lambda-q_{k}}\left\|(\lambda-
q_{k})z_{k}+q_{k}z_{0}-\lambda z_{\star}\right\|^{2}$
$\displaystyle\quad\quad-\frac{q_{k}^{2}\mu+(\lambda-q_{k})q_{k}\mu}{\lambda-
q_{k}}\|z_{0}\|^{2}-\frac{\lambda^{2}\mu-(\lambda-q_{k})\lambda\mu}{\lambda-
q_{k}}\|z_{\star}\|^{2}+\frac{2q_{k}\lambda\mu}{\lambda-q_{k}}\langle
z_{0},z_{\star}\rangle$ $\displaystyle=\frac{\mu}{\lambda-
q_{k}}\left\|(\lambda-q_{k})z_{k}+q_{k}z_{0}-\lambda
z_{\star}\right\|^{2}-\frac{q_{k}\lambda\mu}{\lambda-
q_{k}}\|z_{0}-z_{\star}\|^{2}.$

Therefore, by adding $\frac{q_{k}\lambda\mu}{\lambda-
q_{k}}\|z_{0}-z_{\star}\|^{2}$ to both sides of the inequality (32), we obtain

$\displaystyle W_{k}+\frac{q_{k}\lambda\mu}{\lambda-
q_{k}}\|z_{0}-z_{\star}\|^{2}$ $\displaystyle\geq
p_{k}\|{\varbbB}z_{k}\|^{2}+\langle{\varbbB}z_{k},(q_{k}-\lambda)z_{k}-q_{k}z_{0}+\lambda
z_{\star}\rangle$ $\displaystyle\quad\quad+\frac{\mu}{\lambda-
q_{k}}\left\|(\lambda-q_{k})z_{k}+q_{k}z_{0}-\lambda z_{\star}\right\|^{2}$
$\displaystyle\begin{aligned} &=\left(p_{k}-\frac{\lambda-
q_{k}}{4\mu}\right)\|{\varbbB}z_{k}\|^{2}\\\ &\quad\quad+\frac{\mu}{\lambda-
q_{k}}\left\|\frac{\lambda-q_{k}}{2\mu}{\varbbB}z_{k}-(\lambda-
q_{k})z_{k}-q_{k}z_{0}+\lambda z_{\star}\right\|^{2}\end{aligned}$ (33)

provided that $\lambda>q_{k}$. In particular, taking $\lambda=q_{k}+4\mu
p_{k}$ in (33), we conclude that

$\displaystyle 0$
$\displaystyle\leq\frac{1}{4p_{k}}\left\|2p_{k}{\varbbB}z_{k}-4\mu
p_{k}z_{k}-q_{k}z_{0}+(q_{k}+4\mu p_{k})z_{\star}\right\|^{2}$
$\displaystyle\leq W_{k}+\left(\frac{q_{k}^{2}}{4p_{k}}+\mu
q_{k}\right)\|z_{0}-z_{\star}\|^{2}$
$\displaystyle=W_{k}+\left(\frac{1}{2\alpha(1+2\alpha\mu)^{k-1}}+\mu\frac{(1+2\alpha\mu)^{k}-1}{2\alpha\mu(1+2\alpha\mu)^{k-1}}\right)\|z_{0}-z_{\star}\|^{2}$
$\displaystyle=W_{k}+\frac{1+2\alpha\mu}{2\alpha}\|z_{0}-z_{\star}\|^{2}=V_{k},$

where in the third line we use (28) and
$q_{k}=\frac{1}{(1+2\alpha\mu)^{k-1}}\frac{1}{\beta_{k-1}}=\frac{1}{(1+2\alpha\mu)^{k-1}}\frac{(1+2\alpha\mu)^{k}-1}{2\alpha\mu}$.

###  C.3 Proof of Theorem 5

Recall the shifted version $W_{k}$ of $V_{k}$, defined within the proof of
Lemma 11. Because the subtracted term
$\left(\frac{1}{2\alpha}+\mu\right)\|z_{0}-z_{\star}\|^{2}$ does not depend on
$k$, we immediately see that $W_{k}$ inherits nonincreasingness from $V_{k}$,
i.e., $W_{k}\leq\cdots\leq W_{0}=0$. Therefore, from (33) , we have

$\displaystyle\frac{q_{k}\lambda\mu}{\lambda-q_{k}}\|z_{0}-z_{\star}\|^{2}\geq
W_{k}+\frac{q_{k}\lambda\mu}{\lambda-
q_{k}}\|z_{0}-z_{\star}\|^{2}\geq\left(p_{k}-\frac{\lambda-
q_{k}}{4\mu}\right)\|{\varbbB}z_{k}\|^{2}$
$\displaystyle\iff\|{\varbbB}z_{k}\|^{2}\leq\left(p_{k}-\frac{\lambda-
q_{k}}{4\mu}\right)^{-1}\frac{q_{k}\lambda\mu}{\lambda-
q_{k}}\|z_{0}-z_{\star}\|^{2}$ (34)

provided that $q_{k}<\lambda<q_{k}+4\mu p_{k}$. One can straightforwardly
verify that

$\displaystyle\lambda_{\star}=(q_{k}(q_{k}+4\mu p_{k}))^{1/2}$ (35)

lies between $q_{k}$ and $q_{k}+4\mu p_{k}$, and minimizes the factor
$\left(p_{k}-\frac{\lambda-
q_{k}}{4\mu}\right)^{-1}\frac{q_{k}\lambda\mu}{\lambda-q_{k}}$ in the
convergence rate (34). Plugging in the explicit expressions

$\displaystyle q_{k}$
$\displaystyle=\frac{(1+2\alpha\mu)^{k}-1}{2\alpha\mu(1+2\alpha\mu)^{k-1}}$
$\displaystyle p_{k}$
$\displaystyle=\frac{\alpha}{2}(1+2\alpha\mu)^{k-1}q_{k}^{2}=\frac{((1+2\alpha\mu)^{k}-1)^{2}}{8\alpha\mu^{2}(1+2\alpha\mu)^{k-1}}$

into (35) (where the second line uses (28)), we obtain

$\displaystyle 4\mu p_{k}+q_{k}$
$\displaystyle=\frac{(1+2\alpha\mu)((1+2\alpha\mu)^{k}-1)}{2\alpha\mu}=(1+2\alpha\mu)^{k}q_{k}$
$\displaystyle\lambda_{\star}$
$\displaystyle=(1+2\alpha\mu)^{\frac{k}{2}}q_{k}$

and therefore,

$\displaystyle\left(p_{k}-\frac{\lambda_{\star}-q_{k}}{4\mu}\right)^{-1}\frac{q_{k}\lambda_{\star}\mu}{\lambda_{\star}-q_{k}}$
$\displaystyle=\frac{4\mu^{2}}{((1+2\alpha\mu)^{\frac{k}{2}}-1)^{2}}$
$\displaystyle=\frac{4\mu^{2}}{(\sqrt{1+2\alpha\mu}-1)^{2}\left(\sum_{j=0}^{k-1}(1+2\alpha\mu)^{\frac{j}{2}}\right)^{2}}$
$\displaystyle=\frac{(\sqrt{1+2\alpha\mu}+1)^{2}}{\alpha^{2}\left(\sum_{j=0}^{k-1}(1+2\alpha\mu)^{\frac{j}{2}}\right)^{2}},$

which concludes the proof.

##  Appendix D Omitted proofs for Section 5

###  D.1 Proof of Theorem 6

We first state and prove some preliminary results. The following Lemma 12,
which characterizes the forward-backward residual, has been used in [92] for
developing accelerated splitting algorithms.

######  Lemma 12 ([92, Lemma 3]).

Suppose that , are maximal monotone operators on $\mathbb{R}^{d}$, and is
single-valued. For $\alpha>0$, let
${}_{\alpha}(v)=\frac{1}{\alpha}\left(v-{}_{\alpha{\varbbA}}(v-\alpha{\varbbB}v)\right)$.
Then for any $v,w\in\mathbb{R}^{d}$,

$\displaystyle\left\langle{}_{\alpha}(v)-{}_{\alpha}(w),({\varbbI}+\alpha{\varbbB})(v)-({\varbbI}+\alpha{\varbbB})(w)\right\rangle\geq\alpha\|{}_{\alpha}(v)-{}_{\alpha}(w)\|^{2}.$

###### Proof.

Observe that

$\displaystyle{}_{\alpha}(v)={}_{\alpha{\varbbA}}(v-\alpha{\varbbB}v)+{\varbbB}v,$

where ${}_{\alpha{\varbbA}}(u):=\frac{1}{\alpha}(u-{}_{\alpha{\varbbA}}(u))$
of is the Moreau–Yosida approximation of . It is known that α is
$\alpha$-cocoercive [7, Corollary 23.11], and in particular, for
$\tilde{v}=v-\alpha{\varbbB}v$ and $\tilde{w}=w-\alpha{\varbbB}w$, we have

$\displaystyle\alpha\left\|({}_{\alpha}(v)-{}_{\alpha}(w))-({\varbbB}v-{\varbbB}w)\right\|^{2}$
$\displaystyle=\alpha\left\|{}_{\alpha{\varbbA}}(\tilde{v})-{}_{\alpha{\varbbA}}(\tilde{w})\right\|^{2}$
$\displaystyle\leq\left\langle{}_{\alpha{\varbbA}}(\tilde{v})-{}_{\alpha{\varbbA}}(\tilde{w}),\tilde{v}-\tilde{w}\right\rangle$
$\displaystyle=\langle({}_{\alpha}(v)-{}_{\alpha}(w))-({\varbbB}v-{\varbbB}w),(v-w)-\alpha({\varbbB}v-{\varbbB}w)\rangle.$

Expanding and rearranging the terms, and using monotonicity of , we get

$\displaystyle\alpha\|{}_{\alpha}(v)-{}_{\alpha}(w)\|^{2}$
$\displaystyle\leq\left\langle{}_{\alpha}(v)-{}_{\alpha}(w),(v-w)+\alpha({\varbbB}v-{\varbbB}w)\right\rangle-\langle{\varbbB}v-{\varbbB}w,v-w\rangle$
$\displaystyle\leq\left\langle{}_{\alpha}(v)-{}_{\alpha}(w),(v-w)+\alpha({\varbbB}v-{\varbbB}w)\right\rangle$

as desired. ∎

######  Lemma 13.

Let $\\{(u_{k},w_{k})\\}_{k=0,1,\dots,}$ be the iterates of OHM-DRS and
$\\{(\xi_{k},z_{k})\\}_{k=0,1,\dots,}$ be the iterates of APG*. If
$u_{0}=\xi_{0}$, then for $k=1,2,\dots$, we have

$\displaystyle(k+1)\|\xi_{k}-u_{k}\|\leq
k\|z_{k-1}+\alpha{\varbbB}z_{k-1}-u_{k-1}\|$ (36)

and

$\displaystyle(k+1)\|z_{k}+\alpha{\varbbB}z_{k}-u_{k}\|$ $\displaystyle\leq
k\|z_{k-1}+\alpha{\varbbB}z_{k-1}-u_{k-1}\|+(k+1)\epsilon_{k}.$ (37)

where each $\epsilon_{k}$ is an upper bound on
$\|z_{k}+\alpha{\varbbB}z_{k}-\xi_{k}\|$.

###### Proof.

Observe that
${}_{\alpha{\varbbA}}(z-\alpha{\varbbB}z)+\alpha{\varbbB}z=z+\alpha{\varbbB}z-\alpha{}_{\alpha}(z)$
for any $z\in\mathbb{R}^{d}$, so

$\displaystyle\xi_{k}=\frac{1}{k+1}\xi_{0}+\frac{k}{k+1}(z_{k-1}+\alpha{\varbbB}z_{k-1}-\alpha{}_{\alpha}(z_{k-1})).$

Similarly, we have

$\displaystyle u_{k}$
$\displaystyle=\frac{1}{k+1}u_{0}+\frac{k}{k+1}(w_{k-1}+\alpha{\varbbB}w_{k-1}-\alpha{}_{\alpha}(w_{k-1})).$

Therefore, provided that $u_{0}=\xi_{0}$,

$\displaystyle\xi_{k}-u_{k}=\frac{k}{k+1}\left(({\varbbI}+\alpha{\varbbB})(z_{k-1})-({\varbbI}+\alpha{\varbbB})(w_{k-1})-\alpha({}_{\alpha}(z_{k-1})-{}_{\alpha}(w_{k-1}))\right),$

which gives

$\displaystyle\|\xi_{k}-u_{k}\|^{2}$
$\displaystyle=\left(\frac{k}{k+1}\right)^{2}\left\|({\varbbI}+\alpha{\varbbB})(z_{k-1})-({\varbbI}+\alpha{\varbbB})(w_{k-1})-\alpha({}_{\alpha}(z_{k-1})-{}_{\alpha}(w_{k-1}))\right\|^{2}$
$\displaystyle=\left(\frac{k}{k+1}\right)^{2}\big{(}\|({\varbbI}+\alpha{\varbbB})(z_{k-1})-({\varbbI}+\alpha{\varbbB})(w_{k-1})\|^{2}+\alpha^{2}\|{}_{\alpha}(z_{k-1})-{}_{\alpha}(w_{k-1})\|^{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad-2\alpha\left\langle({\varbbI}+\alpha{\varbbB})(z_{k-1})-({\varbbI}+\alpha{\varbbB})(w_{k-1}),{}_{\alpha}(z_{k-1})-{}_{\alpha}(w_{k-1})\right\rangle\big{)}$
$\displaystyle\leq\left(\frac{k}{k+1}\right)^{2}\big{(}\|({\varbbI}+\alpha{\varbbB})(z_{k-1})-({\varbbI}+\alpha{\varbbB})(w_{k-1})\|^{2}-\alpha^{2}\|{}_{\alpha}(z_{k-1})-{}_{\alpha}(w_{k-1})\|^{2}\big{)}$
$\displaystyle\leq\left(\frac{k}{k+1}\right)^{2}\|({\varbbI}+\alpha{\varbbB})(z_{k-1})-({\varbbI}+\alpha{\varbbB})(w_{k-1})\|^{2}$
$\displaystyle=\left(\frac{k}{k+1}\right)^{2}\|({\varbbI}+\alpha{\varbbB})(z_{k-1})-u_{k-1}\|^{2}$

where the first inequality follows from Lemma 12 and the last equality from
$w_{k-1}={}_{\alpha{\varbbB}}(u_{k-1})$. This proves (36). Then (37) follows
from

$\displaystyle\|z_{k}+\alpha{\varbbB}z_{k}-u_{k}\|$
$\displaystyle\leq\|z_{k}+\alpha{\varbbB}z_{k}-\xi_{k}\|+\|\xi_{k}-u_{k}\|$
$\displaystyle\leq\epsilon_{k}+\frac{k}{k+1}\|(z_{k-1}+\alpha{\varbbB}z_{k-1})-u_{k-1}\|.$

∎

We now prove Theorem 6.

###### Proof of Theorem 6.

Let $M=1+\frac{1}{L}\|{\varbbB}\xi_{0}\|$, so that
$\epsilon_{j}=\frac{M}{(j+1)^{2}(j+2)}$ and

$\displaystyle M=\sum_{j=0}^{\infty}(j+1)\epsilon_{j}.$

Then by Lemma 13, for each $k=1,2,\dots$,

$\displaystyle(k+1)\|\xi_{k}-u_{k}\|$ $\displaystyle\leq
k\|z_{k-1}+\alpha{\varbbB}z_{k-1}-u_{k-1}\|$
$\displaystyle\leq(k-1)\|z_{k-2}+\alpha{\varbbB}z_{k-2}-u_{k-2}\|+k\epsilon_{k}$
$\displaystyle\leq\cdots\leq\|z_{0}+\alpha{\varbbB}z_{0}-u_{0}\|+\sum_{j=1}^{k}(j+1)\epsilon_{j}$
$\displaystyle\leq\sum_{j=0}^{k}(j+1)\epsilon_{j}\leq M.$

This shows that $\|\xi_{k}-u_{k}\|^{2}\leq\left(\frac{M}{k+1}\right)^{2}$ for
$k=0,1,\dots$ (note that $\|\xi_{0}-u_{0}\|=0$). Additionally, for each
$k=0,1,\dots$ we have $(k+1)\|z_{k}+\alpha{\varbbB}z_{k}-u_{k}\|\leq M$, and
because ${}_{\alpha{\varbbB}}=({\varbbI}+\alpha{\varbbB})^{-1}$ is
nonexpansive, we have

$\displaystyle(k+1)\|z_{k}-w_{k}\|$
$\displaystyle=(k+1)\|{}_{\alpha{\varbbB}}\circ({\varbbI}+\alpha{\varbbB})(z_{k})-{}_{\alpha{\varbbB}}(u_{k})\|$
$\displaystyle\leq(k+1)\|z_{k}+\alpha{\varbbB}z_{k}-u_{k}\|\leq M,$

i.e., $\|z_{k}-w_{k}\|\leq\left(\frac{M}{k+1}\right)^{2}$. Finally, the proof
is complete by using

$\displaystyle M\leq
1+\frac{1}{L}(\|{\varbbB}\xi_{\star}\|+\|{\varbbB}\xi_{0}-{\varbbB}\xi_{\star}\|)\leq
1+\frac{1}{L}\|{\varbbB}\xi_{\star}\|+\|\xi_{0}-\xi_{\star}\|=\frac{C(\xi_{0})}{L}.$

∎

###  D.2 Proof of Corollary 7

As ${}_{\textrm{DRS}}$ is nonexpansive [53], by the discussion of Section A.4,
we have
$u_{k}\to\Pi_{\mathrm{Fix}({}_{\textrm{DRS}})}(u_{0})=\Pi_{\mathrm{Fix}({}_{\textrm{DRS}})}(\xi_{0})=\xi_{\star}$.
Because α is nonexpansive, this implies
$z_{k}={}_{\alpha{\varbbB}}(u_{k})\to{}_{\alpha{\varbbB}}(\xi_{\star})\in\mathrm{Zer}\,({\varbbA}+{\varbbB})$.
Due to the MP property proved in Theorem 6, we immediately obtain
$\xi_{k}\to\xi_{\star}$ and $z_{k}\to{}_{\alpha{\varbbB}}(\xi_{\star})$.

Next, note that Lemma 12 implies that α is $\left(\frac{1+\alpha
L}{\alpha}\right)$-Lipschitz, because

$\displaystyle\alpha\|{}_{\alpha}(v)-{}_{\alpha}(w)\|^{2}$
$\displaystyle\leq\left\langle{}_{\alpha}(v)-{}_{\alpha}(w),({\varbbI}+\alpha{\varbbB})(v)-({\varbbI}+\alpha{\varbbB})(w)\right\rangle$
$\displaystyle\leq\left\|{}_{\alpha}(v)-{}_{\alpha}(w)\right\|\left\|({\varbbI}+\alpha{\varbbB})(v)-({\varbbI}+\alpha{\varbbB})(w)\right\|$
$\displaystyle\leq\left\|{}_{\alpha}(v)-{}_{\alpha}(w)\right\|(1+\alpha
L)\|v-w\|$

for any $v,w\in\mathbb{R}^{d}$. Therefore, we obtain

$\displaystyle\|{}_{\alpha}(z_{k})\|^{2}$
$\displaystyle=\|{}_{\alpha}(w_{k})+\left({}_{\alpha}(z_{k})-{}_{\alpha}(w_{k})\right)\|^{2}$
$\displaystyle\leq(1+\nu)\|{}_{\alpha}(w_{k})\|^{2}+\left(1+\frac{1}{\nu}\right)\|{}_{\alpha}(z_{k})-{}_{\alpha}(w_{k})\|^{2}$
(38)
$\displaystyle\leq(1+\nu)\frac{4\|\xi_{0}-\xi_{\star}\|^{2}}{\alpha^{2}(k+1)^{2}}+\left(1+\frac{1}{\nu}\right)\left(\frac{1+\alpha
L}{\alpha}\right)^{2}\|z_{k}-w_{k}\|^{2}$ (39)
$\displaystyle\leq(1+\nu)\frac{4C(\xi_{0})^{2}}{\alpha^{2}L^{2}(k+1)^{2}}+\left(1+\frac{1}{\nu}\right)\left(\frac{1+\alpha
L}{\alpha}\right)^{2}\frac{C(\xi_{0})^{2}}{L^{2}(k+1)^{2}}$ (40)
$\displaystyle=\frac{C(\xi_{0})^{2}}{\alpha^{2}L^{2}(k+1)^{2}}\left(4(1+\nu)+\left(1+\frac{1}{\nu}\right)(1+\alpha
L)^{2}\right)$ (41)

where $\nu>0$ is arbitrary, (38) uses Young’s inequality, (39) uses the
convergence rate of OHM (from Section A.4) and Lipschitzness of α, and (40)
uses $L\|\xi_{0}-\xi_{\star}\|\leq C(\xi_{0})$ and Theorem 6. Now choosing
$\nu=\frac{1+\alpha L}{2}$, which minimizes the quantity (41), we obtain

$\displaystyle\|{}_{\alpha}(z_{k})\|^{2}\leq\frac{C(\xi_{0})^{2}}{\alpha^{2}L^{2}(k+1)^{2}}\left(4+(1+\alpha
L)^{2}+4(1+\alpha L)\right)=\frac{(3+\alpha
L)^{2}C(\xi_{0})^{2}}{\alpha^{2}L^{2}(k+1)^{2}},$

which completes the proof.

###  D.3 Proof of Corollary 8

We first state and prove some lemmas, which will be useful for the main proof.

######  Lemma 14.

Let ${\varbbB}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ be a monotone,
$L$-Lipschitz operator, and let $\alpha\in\left(0,\frac{1}{L}\right)$. Then
for any $u\in\mathbb{R}^{d}$,

$\displaystyle\|u-{}_{\alpha{\varbbB}}(u)\|\leq\frac{\alpha}{1-\alpha
L}\|{\varbbB}u\|.$

###### Proof.

Let $v={}_{\alpha{\varbbB}}(u)$. Then $u=v+\alpha{\varbbB}v$, so

$\displaystyle\|{\varbbB}v\|-\|{\varbbB}u\|\leq\|{\varbbB}v-{\varbbB}u\|\leq
L\|v-u\|=\alpha L\|{\varbbB}v\|\implies\|{\varbbB}v\|\leq\frac{1}{1-\alpha
L}\|{\varbbB}u\|.$

Therefore,

$\displaystyle\|u-{}_{\alpha{\varbbB}}(u)\|=\|u-v\|=\alpha\|{\varbbB}v\|\leq\frac{\alpha}{1-\alpha
L}\|{\varbbB}u\|.$

∎

######  Lemma 15.

Let $\xi_{\star}\in\mathrm{Fix}\,{}_{\textrm{DRS}}$ and
$z_{\star}={}_{\alpha{\varbbB}}(\xi_{\star})$. $\epsilon_{k}>0$
($k=0,1,\dots$) satisfy

$\displaystyle\sum_{k=0}^{\infty}(k+1)\epsilon_{k}=M<\infty.$

Then APG* iterates $\xi_{k},z_{k}$ satisfy
$\max\left\\{\|\xi_{k}-\xi_{\star}\|,\|z_{k}-z_{\star}\|\right\\}\leq\|\xi_{0}-\xi_{\star}\|+M$
for $k=0,1,\dots$.

###### Proof.

Let $u_{k},w_{k}$ be the iterates of OHM-DRS with $u_{0}=\xi_{0}$. Because
$\xi_{\star}\in\mathrm{Fix}({}_{\textrm{DRS}})$ and ${}_{\textrm{DRS}}$ is
nonexpansive, we have

$\displaystyle\|u_{k+1}-\xi_{\star}\|$
$\displaystyle=\left\|\beta_{k}u_{0}+(1-\beta_{k}){}_{\textrm{DRS}}(u_{k})-\xi_{\star}\right\|$
$\displaystyle\leq\beta_{k}\|u_{0}-\xi_{\star}\|+(1-\beta_{k})\|{}_{\textrm{DRS}}(u_{k})-\xi_{\star}\|$
$\displaystyle\leq\beta_{k}\|\xi_{0}-\xi_{\star}\|+(1-\beta_{k})\|u_{k}-\xi_{\star}\|$

for $k=0,1,\dots$. Therefore, by induction on $k$,
$\|u_{k}-\xi_{\star}\|\leq\|\xi_{0}-\xi_{\star}\|$ for all $k=0,1,\dots$. Then
by Theorem 6,

$\displaystyle\|\xi_{k}-\xi_{\star}\|\leq\|\xi_{k}-u_{k}\|+\|u_{k}-\xi_{\star}\|\leq\frac{M}{k+1}+\|\xi_{0}-\xi_{\star}\|\leq\|\xi_{0}-\xi_{\star}\|+M$

and

$\displaystyle\|z_{k}-z_{\star}\|$
$\displaystyle\leq\|z_{k}-w_{k}\|+\|w_{k}-z_{\star}\|\leq\frac{M}{k+1}+\|{}_{\alpha{\varbbB}}(u_{k})-{}_{\alpha{\varbbB}}(\xi_{\star})\|$
$\displaystyle\leq\frac{M}{k+1}+\|u_{k}-\xi_{\star}\|\leq\|\xi_{0}-\xi_{\star}\|+M$

for $k=0,1,\dots$. ∎

We now prove Corollary 8.

###### Proof of Corollary 8.

Recall that each outer loop of APG* performs a single evaluation of α, a
forward evaluation ${\varbbB}z_{k}$, and an inner loop, which starts with
$z_{k}^{(0)}=\xi_{k}$ and solves

$\displaystyle\begin{array}[]{ll}\underset{z\in\mathbb{R}^{d}}{\textrm{find}}&0=z+\alpha{\varbbB}z-\xi_{k}\end{array}$
(43)

using SM-EAG+. The distance from the initial point $z_{k}^{(0)}$ to the true
solution ${}_{\alpha{\varbbB}}(\xi_{k})$ of (43) is

$\displaystyle d_{k}^{(0)}$
$\displaystyle:=\|z_{k}^{(0)}-{}_{\alpha{\varbbB}}(\xi_{k})\|=\|\xi_{k}-{}_{\alpha{\varbbB}}(\xi_{k})\|\leq\frac{\alpha}{1-\alpha
L}\|{\varbbB}\xi_{k}\|$

where the inequality holds due to Lemma 14. Observe that by $L$-Lipschitzness
of and Lemma 15, we have

$\displaystyle\|{\varbbB}\xi_{k}\|\leq\|{\varbbB}\xi_{\star}\|+\|{\varbbB}\xi_{k}-{\varbbB}\xi_{\star}\|\leq\|{\varbbB}\xi_{\star}\|+L\|\xi_{k}-\xi_{\star}\|\leq\|{\varbbB}\xi_{\star}\|+L\|\xi_{0}-\xi_{\star}\|+LM,$

so $d_{k}^{(0)}\leq\frac{\alpha}{1-\alpha
L}\left(\|{\varbbB}\xi_{\star}\|+L\|\xi_{0}-\xi_{\star}\|+LM\right)$. Because
the inner loop objective (43) is $1$-strongly monotone and $(\alpha
L+1)$-Lipschitz, by Theorem 5, the total number of inner loop iterations
needed to achieve the error $\|z+\alpha{\varbbB}z-\xi_{k}\|\leq\epsilon_{k}$
is

$\displaystyle\mathcal{O}\left((\alpha
L+1)\log\frac{d_{k}^{(0)}}{\epsilon_{k}}\right)$
$\displaystyle=\mathcal{O}\left((\alpha L+1)\log\frac{\frac{\alpha}{1-\alpha
L}\left(\|{\varbbB}\xi_{\star}\|+L\|\xi_{0}-\xi_{\star}\|+LM\right)}{Mk^{-1}(k+1)^{-2}}\right)$
$\displaystyle=\mathcal{O}\left(\log\frac{k(\|{\varbbB}\xi_{0}\|+2L\|\xi_{0}-\xi_{\star}\|+LM)}{LM}\right)$

where the last ${\mathcal{O}}$ expression holds because $\alpha L\in(0,1)$ is
a constant. Now recalling that $M=1+\frac{1}{L}\|{\varbbB}\xi_{0}\|$, we
obtain

$\displaystyle\log\frac{k(\|{\varbbB}\xi_{0}\|+2L\|\xi_{0}-\xi_{\star}\|+LM)}{LM}$
$\displaystyle\leq\log\left(k\left(\frac{\|{\varbbB}\xi_{0}\|}{LM}+\frac{2\|\xi_{0}-\xi_{\star}\|}{M}+1\right)\right)$
$\displaystyle\leq\log\left(k\left(1+2\|\xi_{0}-\xi_{\star}\|+1\right)\right)$
$\displaystyle=\mathcal{O}(\log(k(\|\xi_{0}-\xi_{\star}\|+1))).$

By Theorem 7, it requires at most
$\mathcal{O}\left(\frac{C(\xi_{0})}{\epsilon}\right)=\mathcal{O}\left(\frac{L(\|\xi_{0}-\xi_{\star}\|+1)+\|{\varbbB}\xi_{\star}\|}{\epsilon}\right)$
to achieve $\|{}_{\alpha}(z_{k})\|\leq\epsilon$. Up to this range of $k$, each
inner loop performs

$\displaystyle\mathcal{O}(\log(k(\|\xi_{0}-\xi_{\star}\|+1)))=\mathcal{O}\left(\log\frac{L(\|\xi_{0}-\xi_{\star}\|+1)+\|{\varbbB}\xi_{\star}\|}{\epsilon}\right)=\mathcal{O}\left(\log\frac{C(\xi_{0})}{\epsilon}\right)$

evaluations of . Therefore, we conclude that the total computational cost of
APG* is

$\displaystyle\mathcal{O}\left(\frac{C(\xi_{0})}{\epsilon}\left(C+C\log\frac{C(\xi_{0})}{\epsilon}\right)\right).$

∎

##  Appendix E Proof of the remaining summability lemmas

We first state a simple lemma, which will be useful within the proofs of
Lemmas 9 and 10 for arguing the positivity of certain expressions.

######  Lemma 16.

Let $N$ be a fixed positive integer. Suppose $H^{(\ell)}(r)$,
$\ell=0,\dots,N$, are continuous functions in $r\in\mathbb{R}$, and consider
the expression

$\displaystyle H(r,k)=H^{(N)}(r)k^{N}+\cdots+H^{(1)}(r)k+H^{(0)}.$

If $H^{(N)}(0)>0$ and $H^{(\ell)}(0)\geq 0$ for all $\ell=0,\dots,N-1$, then
there exists $\eta>0$ such that $H(r,k)>0$ for all $r\in(0,\eta)$ and
$k=1,2,\dots$.

###### Proof.

Let $J=\left\\{\ell\in\\{0,\dots,N-1\\}\,|\,H^{(\ell)}(0)=0\right\\}$ (so
$H^{(\ell)}(r)>0$ for $\ell\in\\{0,\dots,N-1\\}\setminus J$). As
$H^{(\ell)}(r)$ are continuous, one can choose $\eta>0$ small enough so that
$|r|<\eta$ implies

$\displaystyle\sum_{\ell\in J}\left|H^{(\ell)}(r)\right|<\frac{H^{(N)}(0)}{2}$

and $H^{(\ell)}(r)>0$ for all $\ell\in\\{0,\dots,N-1\\}\setminus J$. Then for
$k=1,2,\dots$, we have

$\displaystyle H(r,k)$
$\displaystyle=k^{N}\left(H^{(N)}(0)+\sum_{\ell=0}^{N-1}H^{(\ell)}(r)k^{\ell-N}\right)$
$\displaystyle>k^{N}\left(H^{(N)}(0)+\sum_{\ell\in
J}H^{(\ell)}(r)k^{\ell-N}\right)$ $\displaystyle\geq
k^{N}\left(H^{(N)}(0)-\sum_{\ell\in
J}\left|H^{(\ell)}(r)\right|k^{\ell-N}\right)$ $\displaystyle\geq
k^{N}\left(H^{(N)}(0)-\sum_{\ell\in J}\left|H^{(\ell)}(r)\right|\right)$
$\displaystyle>\frac{H^{(N)}(0)k^{N}}{2}>0$

provided that $r\in(0,\eta)$. ∎

###### Proof of Lemma 9.

We show the given statement by establishing the following result: by defining
the sequences $p_{k},q_{k}$ by $q_{k}=k$ ($k=0,1,\dots$) and

$\displaystyle p_{0}$ $\displaystyle=\frac{\alpha(1-3\alpha
L+6\alpha^{2}L^{2}-2\alpha^{4}L^{4})}{2(1-\alpha L)^{2}(1+\alpha L)(2+\alpha
L)}$ $\displaystyle p_{k}$ $\displaystyle=\frac{\alpha(k+1)(k+\alpha
L(k-1))}{2(1+\alpha L)},\quad k=1,2,\dots,$

we have $p_{0}>0$,

$\displaystyle
V_{k}=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}\geq
0,$

and

$\displaystyle
V_{k}-V_{k+1}\geq\epsilon(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$

for $\alpha\in\left(0,\frac{\eta}{L}\right)$,
$\epsilon=\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}$ with $\eta\in(0,1)$
sufficiently small. Once this is shown, we can conclude that for any positive
integer $N$,

$\displaystyle\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}\sum_{k=0}^{N}(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\leq V_{0}-V_{N+1}$ $\displaystyle\leq
V_{0}=p_{0}\|{\varbbB}z_{0}\|^{2}+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$
$\displaystyle\leq\left(p_{0}L^{2}+\frac{1}{2\alpha}\right)\|z_{0}-z_{\star}\|^{2}$

holds, which gives

$\displaystyle\sum_{k=0}^{\infty}(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}\leq\frac{2}{\alpha^{2}L(1-\alpha^{2}L^{2})}\left(p_{0}L^{2}+\frac{1}{2\alpha}\right)\|z_{0}-z_{\star}\|^{2}=\frac{C}{\alpha^{2}}\|z_{0}-z_{\star}\|^{2}$

where

$\displaystyle
C=\frac{2-r-2r^{2}-2r^{3}+7r^{4}-2r^{6}}{r(1-r)^{3}(1+r)^{2}(2+r)}\quad(r=\alpha
L)$

is a positive constant provided that $r<\eta$ for $\eta$ small enough.

#### Case $k=0$.

We have $z_{1/2}=z_{0}-\alpha{\varbbB}z_{0}$ and
$z_{1}=z_{0}-\alpha{\varbbB}z_{1/2}$. By monotonicity and Lipschitzness of ,
we have

$\displaystyle
V_{1}+\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}\|{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}$
$\displaystyle=\frac{\alpha}{1+\alpha
L}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},z_{1}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}+\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}\|{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}$
(44) $\displaystyle\leq\frac{\alpha}{1+\alpha
L}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},z_{1}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}+\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}\|{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}$
$\displaystyle\quad+\frac{\alpha}{1+\alpha
L}\left(L^{2}\|z_{1/2}-z_{1}\|^{2}-\|{\varbbB}z_{1/2}-{\varbbB}z_{1}\|^{2}\right)+\frac{1-\alpha
L}{1+\alpha L}\langle z_{0}-z_{1},{\varbbB}z_{0}-{\varbbB}z_{1}\rangle$
$\displaystyle=\frac{\alpha}{1+\alpha
L}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},-\alpha{\varbbB}z_{1/2}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}+\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}\|{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}$
$\displaystyle\quad+\frac{\alpha}{1+\alpha
L}\left(\alpha^{2}L^{2}\|{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}-\|{\varbbB}z_{1/2}-{\varbbB}z_{1}\|^{2}\right)+\frac{1-\alpha
L}{1+\alpha
L}\langle\alpha{\varbbB}z_{1/2},{\varbbB}z_{0}-{\varbbB}z_{1}\rangle$
$\displaystyle\begin{aligned}
&=\frac{\alpha}{2(1+r)}\big{(}r(1+3r-r^{2}-r^{3})\|{\varbbB}z_{0}\|^{2}-(1-r)^{2}(1+r)(2+r)\|{\varbbB}z_{1/2}\|^{2}\\\
&\quad\quad\quad\quad\quad+2(1+r)(1-3r+r^{3})\langle{\varbbB}z_{0},{\varbbB}z_{1/2}\rangle\big{)}+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}\end{aligned}$
(45)

where $r=\alpha L$. Next, using Young’s inequality, we can bound the inner
product term in (45) as

$\displaystyle
2(1+r)(1-3r+r^{3})\langle{\varbbB}z_{0},{\varbbB}z_{1/2}\rangle$
$\displaystyle\leq(1-r)^{2}(1+r)(2+r)\|{\varbbB}z_{1/2}\|^{2}+\frac{(1+r)(1-3r+r^{3})^{2}}{(1-r)^{2}(2+r)}\|{\varbbB}z_{0}\|^{2}.$

Plugging this back into (45) and rearranging, we obtain

$\displaystyle
V_{1}+\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2}\|{\varbbB}z_{0}-{\varbbB}z_{1/2}\|^{2}\leq\frac{\alpha(1-3r+6r^{2}-2r^{4})}{2(1-r)^{2}(1+r)(2+r)}\|{\varbbB}z_{0}\|^{2}+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}=V_{0}.$

Clearly, if $r$ is small enough,
$p_{0}=\frac{\alpha(1-3r+6r^{2}-2r^{4})}{2(1-r)^{2}(1+r)(2+r)}>0$.

#### Case $k\geq 1$.

From the definition of the EAG iterates, we have

$\displaystyle z_{k+1}-z_{0}$
$\displaystyle=(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}z_{k+1/2}$
$\displaystyle z_{k}-z_{k+1}$
$\displaystyle=\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}z_{k+1/2}$ $\displaystyle
z_{k+1/2}-z_{k+1}$
$\displaystyle=\alpha{\varbbB}z_{k+1/2}-\alpha{\varbbB}z_{k}.$

Therefore, as in previous sections, we can lower-bound $V_{k}-V_{k+1}$ as

$\displaystyle V_{k}-V_{k+1}\geq V_{k}-V_{k+1}-\frac{q_{k}}{\beta_{k}}\langle
z_{k}-z_{k+1},{\varbbB}z_{k}-{\varbbB}z_{k+1}\rangle$
$\displaystyle\quad=p_{k}\|{\varbbB}z_{k}\|^{2}-\frac{\alpha
q_{k}}{\beta_{k}}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\frac{\alpha
q_{k}}{\beta_{k}(1-\beta_{k})}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}$
$\displaystyle\quad=p_{k}\|{\varbbB}z_{k}\|^{2}-\alpha
k(k+1)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\alpha(k+1)^{2}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}.$ (46)

As is $L$-Lipschitz,

$\displaystyle 0$ $\displaystyle\leq
L^{2}\|z_{k+1/2}-z_{k+1}\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}$
$\displaystyle=\alpha^{2}L^{2}\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k}\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}.$

Combining this with (E), we obtain

$\displaystyle
V_{k}-V_{k+1}-\epsilon(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\geq p_{k}\|{\varbbB}z_{k}\|^{2}-\alpha
k(k+1)\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\alpha(k+1)^{2}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}$
$\displaystyle\quad-\epsilon(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}-\tau\left(\alpha^{2}L^{2}\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k}\|^{2}-\|{\varbbB}z_{k+1/2}-{\varbbB}z_{k+1}\|^{2}\right)$
$\displaystyle=(p_{k}-\alpha^{2}L^{2}\tau-\epsilon(k+1)^{2})\left\|{\varbbB}z_{k}\right\|^{2}+(\tau(1-\alpha^{2}L^{2})-\epsilon(k+1)^{2})\left\|{\varbbB}z_{k+1/2}\right\|^{2}+(\tau-
p_{k+1})\left\|{\varbbB}z_{k+1}\right\|^{2}$
$\displaystyle\quad+\left(2\alpha^{2}L^{2}\tau+2\epsilon(k+1)^{2}-\alpha
k(k+1)\right)\,\left\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\right\rangle+\left(\alpha(k+1)^{2}-2\tau\right)\,\left\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\right\rangle$
$\displaystyle=\mathrm{Tr}\left(\mathbf{M}_{k}\mathbf{S}_{k}\mathbf{M}_{k}^{\intercal}\right),$

where $\tau>0$,
$\mathbf{M}_{k}:=\begin{bmatrix}{\varbbB}z_{k}&{\varbbB}z_{k+1/2}&{\varbbB}z_{k+1}\end{bmatrix}$
and

$\displaystyle\mathbf{S}_{k}=\begin{bmatrix}p_{k}-\alpha^{2}L^{2}\tau-\epsilon(k+1)^{2}&\alpha^{2}L^{2}\tau+\epsilon(k+1)^{2}-\frac{\alpha}{2}k(k+1)&0\\\
\alpha^{2}L^{2}\tau+\epsilon(k+1)^{2}-\frac{\alpha}{2}k(k+1)&\tau(1-\alpha^{2}L^{2})-\epsilon(k+1)^{2}&\frac{1}{2}\alpha(k+1)^{2}-\tau\\\
0&\frac{1}{2}\alpha(k+1)^{2}-\tau&\tau-p_{k+1}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}s_{11}&s_{12}&0\\\ s_{12}&s_{22}&s_{23}\\\
0&s_{23}&s_{33}\end{bmatrix}.$

Now, we choose $\tau$ as

$\displaystyle\tau$ $\displaystyle=\frac{(k+1)\left(k(1-\alpha
L+\alpha^{2}L^{2}+\alpha^{3}L^{3})-\alpha L(2-\alpha
L-\alpha^{2}L^{2})\right)}{4\alpha L^{2}}.$

For notational simplicity, let $\alpha L=r$. Then by direct computation we
obtain

$\displaystyle
s_{11}=\frac{\alpha}{4(1+r)}\left((1-r^{2})^{2}k^{2}+(1-2r-3r^{2}+2r^{4})k-r(2+r-r^{3})\right)$
$\displaystyle
s_{12}=-\frac{\alpha(1-r)(k+1)\left((1-r^{2})k-r^{2}\right)}{4}.$

By Lemma 16, $s_{11}>0$ for sufficiently small $r$, and in that case, Young’s
inequality gives

$\displaystyle
s_{11}\|{\varbbB}z_{k}\|^{2}+2s_{12}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\frac{s_{12}^{2}}{s_{11}}\|{\varbbB}z_{k+1/2}\|^{2}\geq
0.$

Continuing on, we compute

$\displaystyle t_{22}$ $\displaystyle=s_{22}-\frac{s_{12}^{2}}{s_{11}}$
$\displaystyle=\frac{(1-r^{2})\left(T_{22}^{(3)}(r)k^{3}+T_{22}^{(2)}(r)k^{2}+T_{22}^{(1)}(r)k+T_{22}^{(0)}(r)\right)}{4Lr\left(\left(1-r^{2}\right)^{2}k-r\left(2+r-r^{3}\right)\right)}$

where $T_{22}^{(\ell)}(r)$, $\ell=0,1,2,3$, are polynomials in $r$ defined by

$\displaystyle T_{22}^{(0)}(r)$ $\displaystyle=r^{2}(4+r^{2}-r^{3})$
$\displaystyle T_{22}^{(1)}(r)$
$\displaystyle=-r\left(4-6r-2r^{2}-3r^{3}+3r^{4}\right)$ $\displaystyle
T_{22}^{(2)}(r)$ $\displaystyle=1-5r+4r^{3}+3r^{4}-3r^{5}$ $\displaystyle
T_{22}^{(3)}(r)$ $\displaystyle=(1+r)^{2}(1-r)^{3},$

and

$\displaystyle s_{23}=-\frac{(1+r)(k+1)\left((1-r)^{2}k-r(2-r)\right)}{4Lr}$

By Lemma 16 again, $t_{22}>0$ for sufficiently small $r$ and then Young’s
inequality implies that

$\displaystyle
t_{22}\|{\varbbB}z_{k+1/2}\|^{2}+2s_{23}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle+\frac{s_{23}^{2}}{t_{22}}\|{\varbbB}z_{k+1}\|^{2}\geq
0.$

Finally, we have

$\displaystyle\mathrm{Tr}\left(\mathbf{M}_{k}\mathbf{S}_{k}\mathbf{M}_{k}^{\intercal}\right)$
$\displaystyle=\left(s_{11}\|{\varbbB}z_{k}\|^{2}+2s_{12}\langle{\varbbB}z_{k},{\varbbB}z_{k+1/2}\rangle+\frac{s_{12}^{2}}{s_{11}}\|{\varbbB}z_{k+1/2}\|^{2}\right)$
$\displaystyle\quad+\left(t_{22}\|{\varbbB}z_{k+1/2}\|^{2}+2s_{23}\langle{\varbbB}z_{k+1/2},{\varbbB}z_{k+1}\rangle+\frac{s_{23}^{2}}{t_{22}}\|{\varbbB}z_{k+1}\|^{2}\right)+\left(s_{33}-\frac{s_{23}^{2}}{t_{22}}\right)\|{\varbbB}z_{k+1}\|^{2}$
$\displaystyle\geq 0,$

as the following computation and Lemma 16 shows that
$s_{33}-\frac{s_{23}^{2}}{t_{22}}>0$ for sufficiently small $r$:

$\displaystyle s_{33}-\frac{s_{23}^{2}}{t_{22}}=\frac{\alpha
r\left((1-4r-2r^{2}+r^{4})k-r(6-r-r^{3})\right)}{2(1-r^{2})\left((1+r)^{2}(1-r)k-r(2+r+r^{2})\right)}.$

Therefore, we have established $V_{k}-V_{k+1}\geq 0$ for small $r$.

#### Nonnegativity.

Observe that

$\displaystyle p_{k}-\frac{\alpha k^{2}}{2}=\frac{\alpha(k+1)(k+\alpha
L(k-1))-\alpha(1+\alpha L)k^{2}}{2(1+\alpha L)}=\frac{\alpha(k-\alpha
L)}{2(1+\alpha L)}>0$

provided that $k\geq 1$ and $\alpha<\frac{1}{L}$. Thus,

$\displaystyle V_{k}$ $\displaystyle\geq\frac{\alpha
k^{2}}{2}\|{\varbbB}z_{k}\|^{2}+k\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$
$\displaystyle\geq\frac{\alpha
k^{2}}{2}\|{\varbbB}z_{k}\|^{2}+k\langle{\varbbB}z_{k},z_{\star}-z_{0}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}\geq
0$

by monotonicity and Young’s inequality.

∎

###### Proof of Lemma 10.

We establish the following Lyapunov analysis: with same $p_{k},q_{k}$ as in
Lemma 9,

$\displaystyle
V_{k}=p_{k}\|{\varbbB}z_{k}\|^{2}+q_{k}\langle{\varbbB}z_{k},z_{k}-z_{0}\rangle+p_{k}L^{2}\|z_{k}-v_{k}\|^{2}+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}$

satisfies $V_{k}\geq 0$ and
$V_{k}-V_{k+1}\geq\epsilon(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$
for $k=0,1,\dots$, $\alpha\in\left(0,\frac{\eta}{L}\right)$, and
$\epsilon=\frac{\alpha^{2}L\left(1-\alpha
L-\alpha^{2}L^{2}-\alpha^{3}L^{3}\right)}{2(1+\alpha L)}$ with $\eta\in(0,1)$
sufficiently small. This will imply

$\displaystyle\epsilon\sum_{k=0}^{N}(k+1)^{2}\|{\varbbB}z_{k}-{\varbbB}z_{k+1/2}\|^{2}$
$\displaystyle\leq
V_{0}\leq\left(p_{0}L^{2}+\frac{1}{2\alpha}\right)\|z_{0}-z_{\star}\|^{2},$

so that

$\displaystyle\sum_{k=0}^{\infty}(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}\leq\frac{1}{\epsilon}\left(p_{0}L^{2}+\frac{1}{2\alpha}\right)\|z_{0}-z_{\star}\|^{2}=\frac{C}{\alpha^{2}}\|z_{0}-z_{\star}\|^{2}$

with

$\displaystyle
C=\frac{2-r-2r^{2}-2r^{3}+7r^{4}-2r^{6}}{r(1-r)^{2}(2+r)(1-r-r^{2}-r^{3})}>0$

provided that $r=\alpha L\in(0,\eta)$ for $\eta$ small enough.

#### Nonnegativity.

Proved in the exact same way as in Lemma 9, except that we have an additional
nonnegative term $p_{k}L^{2}\|z_{k}-v_{k}\|^{2}$.

#### Case $k=0$.

We have $v_{1}=z_{0}-\alpha{\varbbB}v_{0}=z_{0}-\alpha{\varbbB}z_{0}$ and
$z_{1}=z_{0}-\alpha{\varbbB}v_{1}$. Observe that

$\displaystyle V_{1}+\epsilon\|{\varbbB}v_{0}-{\varbbB}v_{1}\|^{2}$
$\displaystyle=\frac{\alpha}{1+\alpha
L}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},z_{1}-z_{0}\rangle+p_{1}L^{2}\|z_{1}-v_{1}\|^{2}+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}+\epsilon\|{\varbbB}z_{0}-{\varbbB}v_{1}\|^{2}$
$\displaystyle=\frac{\alpha}{1+\alpha
L}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},-\alpha{\varbbB}v_{1}\rangle+p_{1}L^{2}\|\alpha({\varbbB}z_{0}-{\varbbB}v_{1})\|^{2}+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}+\epsilon\|{\varbbB}z_{0}-{\varbbB}v_{1}\|^{2}$
$\displaystyle=\frac{\alpha}{1+\alpha
L}\|{\varbbB}z_{1}\|^{2}+\langle{\varbbB}z_{1},-\alpha{\varbbB}v_{1}\rangle+\frac{1}{2\alpha}\|z_{0}-z_{\star}\|^{2}+\left(\alpha^{2}L^{2}p_{1}+\epsilon\right)\|{\varbbB}z_{0}-{\varbbB}v_{1}\|^{2}.$
(47)

Because

$\displaystyle\alpha^{2}L^{2}p_{1}+\epsilon=\alpha^{2}L^{2}\frac{\alpha}{1+\alpha
L}+\frac{\alpha^{2}L\left(1-\alpha
L-\alpha^{2}L^{2}-\alpha^{3}L^{3}\right)}{2(1+\alpha
L)}=\frac{\alpha^{2}L(1-\alpha^{2}L^{2})}{2},$

we see that the expression (47) coincides with (44), except that
${\varbbB}z_{1/2}$ is replaced with ${\varbbB}v_{1}$. Therefore, the rest of
the proof is exactly the same as in Lemma 9 (add the same set of inequalities
to (47) with $v_{1}$ and ${\varbbB}v_{1}$ in places of $z_{1/2}$ and
${\varbbB}z_{1/2}$, respectively).

#### Case $k\geq 1$.

Using the identities

$\displaystyle z_{k+1}-z_{0}$
$\displaystyle=(1-\beta_{k})(z_{k}-z_{0})-\alpha{\varbbB}v_{k+1}$
$\displaystyle z_{k}-z_{k+1}$
$\displaystyle=\beta_{k}(z_{k}-z_{0})+\alpha{\varbbB}v_{k+1}$ $\displaystyle
v_{k}-z_{k}$ $\displaystyle=\alpha{\varbbB}v_{k}-\alpha{\varbbB}v_{k-1}$
$\displaystyle v_{k+1}-z_{k+1}$
$\displaystyle=\alpha{\varbbB}v_{k+1}-\alpha{\varbbB}v_{k},$

we begin with

$\displaystyle V_{k}-V_{k+1}\geq V_{k}-V_{k+1}-\frac{q_{k}}{\beta_{k}}\langle
z_{k}-z_{k+1},{\varbbB}z_{k}-{\varbbB}z_{k+1}\rangle$
$\displaystyle\quad=p_{k}\|{\varbbB}z_{k}\|^{2}-\frac{\alpha
q_{k}}{\beta_{k}}\langle{\varbbB}z_{k},{\varbbB}v_{k+1}\rangle+\frac{\alpha
q_{k}}{\beta_{k}(1-\beta_{k})}\langle{\varbbB}v_{k+1},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}$
$\displaystyle\quad\quad+\alpha^{2}p_{k}L^{2}\|{\varbbB}v_{k-1}-{\varbbB}v_{k}\|^{2}-\alpha^{2}p_{k+1}L^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$
$\displaystyle\begin{aligned} &\quad=p_{k}\|{\varbbB}z_{k}\|^{2}-\alpha
k(k+1)\langle{\varbbB}z_{k},{\varbbB}v_{k+1}\rangle+\alpha(k+1)^{2}\langle{\varbbB}v_{k+1},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}\\\
&\quad\quad+\alpha^{2}p_{k}L^{2}\|{\varbbB}v_{k-1}-{\varbbB}v_{k}\|^{2}-\alpha^{2}p_{k+1}L^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}.\end{aligned}$
(48)

Following the idea in the prior work [92] which introduced the anchored
Popov’s scheme, we use the following inequality:

$\displaystyle\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$
$\displaystyle=\|({\varbbB}v_{k}-{\varbbB}z_{k})+({\varbbB}z_{k}-{\varbbB}v_{k+1})\|^{2}$
$\displaystyle\leq
2\|{\varbbB}v_{k}-{\varbbB}z_{k}\|^{2}+2\|{\varbbB}z_{k}-{\varbbB}v_{k+1}\|^{2}$
$\displaystyle\leq
2L^{2}\|v_{k}-z_{k}\|^{2}+2\|{\varbbB}z_{k}-{\varbbB}v_{k+1}\|^{2}$
$\displaystyle=2\alpha^{2}L^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k-1}\|^{2}+2\|{\varbbB}z_{k}-{\varbbB}v_{k+1}\|^{2},$

which implies

$\displaystyle
2\alpha^{2}L^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k-1}\|^{2}+2\|{\varbbB}z_{k}-{\varbbB}v_{k+1}\|^{2}-\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}\geq
0.$ (49)

Additionally, note the simple Lipschitzness inequality

$\displaystyle 0$ $\displaystyle\leq
L^{2}\|z_{k+1}-v_{k+1}\|^{2}-\|{\varbbB}z_{k+1}-{\varbbB}v_{k+1}\|^{2}$
$\displaystyle=\alpha^{2}L^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}-\|{\varbbB}z_{k+1}-{\varbbB}v_{k+1}\|^{2}.$
(50)

Then, given positive constants $\tau_{1},\tau_{2}$, we can lower-bound
$V_{k}-V_{k+1}-\epsilon(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$ by
using (48) and subtracting
$\frac{\tau_{1}}{2}\times\eqref{eqn:APS_Lipschitz_with_parallelogram}$ and
$\tau_{2}\times\eqref{eqn:APS_Lipschitz_only}$ as

$\displaystyle
V_{k}-V_{k+1}-\epsilon(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$
$\displaystyle\quad\geq p_{k}\|{\varbbB}z_{k}\|^{2}-\alpha
k(k+1)\langle{\varbbB}z_{k},{\varbbB}v_{k+1}\rangle+\alpha(k+1)^{2}\langle{\varbbB}v_{k+1},{\varbbB}z_{k+1}\rangle-
p_{k+1}\|{\varbbB}z_{k+1}\|^{2}$
$\displaystyle\quad\quad+\alpha^{2}p_{k}L^{2}\|{\varbbB}v_{k-1}-{\varbbB}v_{k}\|^{2}-\alpha^{2}p_{k+1}L^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}-\epsilon(k+1)^{2}\|{\varbbB}v_{k}-{\varbbB}v_{k+1}\|^{2}$