# Moving Anchor extragradient methods for smooth structured minimax problems

James K. Alcala  Department of Mathematics, University of California,
Riverside, USA<EMAIL_ADDRESS>,  Yat Tin Chow  Department of Mathematics,
University of California, Riverside, USA<EMAIL_ADDRESS>and  Mahesh Sunkula
Department of Mathematics, Purdue University, West Lafayette, Indiana, USA
<EMAIL_ADDRESS>
###### Abstract.

This work introduces a moving anchor acceleration technique to extragradient
algorithms for smooth structured minimax problems. The moving anchor is
introduced as a generalization of the original algorithmic anchoring
framework, i.e. the EAG method introduced in [32], in hope of further
acceleration. We show that the optimal order of convergence in terms of worst-
case complexity on the squared gradient, $O(1/k^{2}),$ is achieved by our new
method (where $k$ is the number of iterations). We have also extended our
algorithm to a more general nonconvex-nonconcave class of saddle point
problems using the framework of [14], which slightly generalizes [32]. We
obtain similar order-optimal complexity results in this extended case. In both
problem settings, numerical results illustrate the efficacy of our moving
anchor algorithm variants, in particular by attaining the theoretical optimal
convergence rate for first order methods, as well as suggesting a better
optimized constant in the big O notation which surpasses the traditional fixed
anchor methods in many cases. A proximal-point preconditioned version of our
algorithms is also introduced and analyzed to match optimal theoretical
convergence rates.

James K. Alcala is partially supported by a UCR Dissertation Year Program
Award.

Yat Tin Chow is partially supported by a Regents’ Faculty Fellowship,
University of California, Riverside.

##  1\. Introduction

Minimax, min-max, or saddle point problems of the form

$\displaystyle\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{m}}L(x,y)$ (1.1)

have received considerable attention from optimization researchers and, in
particular, machine learning practitioners because of applications including
but not limited to Game Theory, Online Learning, GANs [9], [3], adversarial
learning [18], and reinforcement learning [7]. Measuring the duality gap
$\sup_{y^{*}\in\mathbb{R}^{m}}L(x,y^{*})-\inf_{x^{*}\in\mathbb{R}^{n}}L(x^{*},y)$
on averaged (ergodic) iterates or last-iterates of algorithms is one natural
way to measure the suboptimality of methods designed to solve (1.1). This is a
clear analog to measuring suboptimality for algorithms for minimization
problems. On the other hand, such a measurement is not as natural to consider
when (1.1) is nonconvex-nonconcave, and as will be discussed, the convergence
guarantees for this kind of measure may be limiting.

When problem (1.1) is differentiable, another meaningful measure of
suboptimality is the squared gradient norm or Hamiltonian of $L$,
$\text{Ham}_{L}(x,y)=\|\nabla L(x,y)\|^{2}.$ (Sometimes this includes an extra
factor of $\frac{1}{2}$, which is not included in this paper. No physical
interpretation of this quantity is used here.) This suboptimality measure
retains meaning for nonconvex-nonconcave problems and convergence rates on the
squared gradient-norm have only recently attained order-optimal convergence
rates in these problem settings. This is especially important, as many machine
learning settings involve neural networks which result in problems that are
inherently nonconvex-nonconcave - and as our results indicate, there may still
be room for numerical improvements.

The EAG (extra-anchored gradient) class of algorithms, first introduced in
[32], combines extragradient and the more recently developed anchoring methods
in a single framework to tackle smooth-structured convex-concave minimax
problems. With the primary assumptions being $R-$smoothness and convexity-
concavity of (1.1), EAG achieved $O(1/k^{2})=\Omega(1/k^{2})$ convergence
rates on the squared gradient-norm; that is, the algorithm is order-optimal.
This achievement has inspired a flurry of research activity in recent years
[13], [28], [32]. To show optimality, the authors of [32] adapt arguments from
[21], [22] to construct a worse-case analysis for a large class of algorithms
that contain EAG.

As anchoring is relatively new compared to extragradient, much of the
literature written as a direct consequence of these results emphasizes
anchoring and other Halpern adjacent techniques [15], [30], [29]. However, the
EAG class is not without limitations. The two sub-variants of EAG, EAG-V with
varying step-size and EAG-C with constant step-size, have difficult
convergence analyses and are both relegated to the convex-concave class of
smooth functions. Addressing some of these issues, the authors of [14]
introduced the Fast ExtraGradient Method, or FEG. This method generalizes the
results of EAG and EG+ [6] to introduce the order-optimal pairing of the
extragradient anchor to the setting of certain nonconvex-nonconcave problems
(specifically, negative comonotone) and introduces an analysis dependent on
terms that are less difficult to work with. Furthermore, their work improves
upon the bounding constant attained in EAG in convex-concave problems while
retaining optimal convergence rates for a broader class of problems that are
of particular importance to machine learning practitioners, among many others.

In the spirit of these previous works, our contributions are as follows.

  1. (1)

We introduce a new technique, the ‘moving anchor,’ into the algorithmic
settings of EAG-V and FEG under minimal assumptions. We demonstrate that in
both settings, introducing the moving anchor retains order-optimal
$O(1/k^{2})$ convergence rates across a range of parameter choices that using
the moving anchor gives one access to. One may recover the original fixed-
anchor algorithms via parameter tuning, so our algorithms generalize much of
the current anchoring literature.

  2. (2)

For both the EAG-V moving anchor and the FEG moving anchor, we run a variety
of numerical examples by comparing multiple versions of our moving anchor
algorithms with their fixed anchor counterparts. These numerical examples
demonstrate the efficacy of our algorithm, as in all cases, a moving anchor
algorithm variant in each example is the fastest algorithm by a constant or is
comparable-to-better for all iterations. In addition, in many cases the
fastest moving anchor algorithm appears to have a massive initial oscillation
towards the fixed point that the fixed point algorithms seem to lack - this
may be beneficial for reaching certain stopping criteria very quickly.

  3. (3)

We develop a theoretical version of the moving anchor algorithms (in both the
convex-concave EAG-V and nonconvex-nonconcave FEG) with a proximal anchoring
step with fruitful implications for future research.

##  2\. Literature Review & Preliminaries

###  2.1. Halpern iteration and anchoring

Introduced in 1967 and inspired by Browder’s classical fixed point theorem,
the Halpern iteration [11] is an algorithm built for approximating fixed
point(s) of nonexpanding maps in a Hilbert space. Its convergence has been
studied in [16], and it is extensively used in monotone inclusion-type problem
settings [5], [30], [2]. A recent paper [29] draws an explicit connection
between Halpern-inspired methods and Nesterov’s AGM [23], linking two very
active strains of acceleration literature.

Directly inspired by Halpern, algorithmic anchoring was recently introduced in
the literature [27] and has since been utilized to establish optimal
$O(1/k^{2})$ convergence rates for smooth-structured convex-concave minimax
problems [32]. Since then, these methods have been extended to the nonconvex-
nonconcave, negative comonotone problem setting [14] and analogous settings
for composite problems in a multi-step framework [15]. Interestingly, this
latter framework introduces ‘semi’-anchoring, where only one part of the
descent-ascent step is anchored, and a unique anchor occurs at each step of
the multi-step. To our knowledge, this is the first instance of an anchoring
method that goes beyond a single fixed anchor. In [30], the authors develop an
anchored Popov’s scheme and a splitting version of the EAG developed in [32],
with a similar analysis.

###  2.2. Extragradient methods

The extragradient method first appeared in [12] and has since been an
important acceleration method extensively studied in the optimization
literature [1], [31], [17], especially in the context of generative
adversarial networks [9], [3] and adversarial training [18]. A classical
result regarding these methods is that if
$X\in\mathbb{R}^{n},Y\in\mathbb{R}^{m}$ are compact domains, then for the
duality gap $\max_{y*\in Y}L(x,y*)-\min_{x*\in X}L(x*,y),$ the ergodic iterate
of extragradient-type methods [19], [24] have an $O(1/k)$ rate, which is
order-optimal [25], [20]. Recently, it was shown that the last iterate
convergence rate for extragradient also attains $O(1/k)$ convergence [10],
with only monotonicity and Lipschitz assumptions. This closes the gap between
the last-iterate and ergodic-iterate convergence rates for extragradient
discussed in [8]. Another recent interesting result was attained in [6], where
the authors developed the Extragradient$+$ method, a variant of extragradient
extended to various nonconvex-nonconcave problem settings.

On the other hand, when the problem at hand has certain smoothness properties,
the squared gradient norm $\|\nabla L\|^{2}$ for extragradient-type algorithms
recently achieved order-optimal convergence of $O(1/k^{2})$ [32], [14], thanks
in part to the synthesis with anchoring. This breaks the bound of the SCLI
class of algorithms discussed in [8], which contains the unmodified
extragradient, because EAG is not SCLI, but specifically 2-CLI or in an
extended class of 1-CLI algorithms. See Appendix D.2 of [32] for a best-
iterate (NOT last iterate, at the time of writing this quantity doesn’t seem
to be known) convergence analysis of extragradient and Appendix E of [32] and
[8] for more details on the relationships between these classes of algorithms.
We conclude this discussion by remarking that for smooth problems, the bound
on the squared gradient norm is meaningful in nonconvex-nonconcave problem
settings, and as demonstrated in this and recent works, has room for numerical
improvement.

###  2.3. Preliminaries

A saddle function $L:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$ is
(non)convex-(non)concave if it is (non)convex in $x$ for any fixed
$y\in\mathbb{R}^{m}$ and (non)concave in $y$ for any fixed
$x\in\mathbb{R}^{n}$. A saddle point
$(\hat{x},\hat{y})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ is any point such
that the inequality $L(\hat{x},y)\leq L(\hat{x},\hat{y})\leq L(x,\hat{y})$ for
all $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}.$ Solutions to (1.1) are
defined as saddle points.

Throughout this paper, we assume the differentiability of $L$, and we are
especially interested in the so-called saddle operator associated to $L$,

$\displaystyle G_{L}(z)$
$\displaystyle=\left[\begin{array}[]{c}\nabla_{x}L(x,y)\\\
-\nabla{y}L(x,y)\end{array}\right]$ (2.3)

where the $L$ subscript is omitted when the underlying saddle function is
known. When our problem is convex-concave, the operator (2.3) is known to be
monotone [26], meaning $\langle
G_{L}(z_{1})-G_{L}(z_{2}),z_{1}-z_{2}\rangle\geq 0\;\forall
z_{1},z_{2}\in\mathbb{R}^{n}\times\mathbb{R}^{m}.$ We assume that this
operator $G_{L}$ is $R$-Lipschitz, or has certain stronger Lipschitz
properties we detail later; this is sometimes referred to as $L$ being
$R$-smooth. With these properties in mind, one may introduce an assumption
that generalizes monotonicity: let $\rho\in(-\frac{1}{2R},+\infty).$ In this
paper, we assume that when $G_{L}$ is not monotone, it satisfies

$\langle
G_{L}(z_{1})-G_{L}(z_{2}),z_{1}-z_{2}\rangle\geq\rho\|G_{L}(z_{1})-G_{L}(z_{2})\|^{2}\;\forall
z_{1},z_{2}\in\mathbb{R}^{n}\times\mathbb{R}^{m}.$

When $\rho>0,$ this is called co-coercivity; when $\rho=0,$ this recovers
monotonicity; when $\rho<0,$ this is called negative comonotonicity. This
latter condition on (2.3) allows one to consider certain nonconvex-nonconcave
problems $L$, and is also going to be a central focus of this work. Note,
however, that these assumptions need not cover all smooth nonconvex-nonconcave
problems of interest. Figure 1, Table 1, and Example 1 of [14] illustrate
broader problem classes than negative comonotonicity that retain smoothness
while being nonconvex-nonconcave.

Finally we state that although $\nabla L\neq G_{L},$ we have $\|\nabla
L\|=\|G_{L}\|,$ so we may use these expressions interchangeably.

##  3\. Original Algorithm, EAG-V

The Extragradient Anchored Algorithm, or EAG with varying step size (EAG-V)
has a simple statement and a relatively simple proof of convergence:

$\displaystyle z^{k+1/2}$
$\displaystyle=z^{k}+\beta_{k}(z^{0}-z^{k})-\alpha_{k}G(z^{k})$ $\displaystyle
z^{k+1}$ $\displaystyle=z^{k}+\beta_{k}(z^{0}-z^{k})-\alpha_{k}G(z^{k+1/2})$
$\displaystyle\alpha_{k+1}$
$\displaystyle=\frac{\alpha_{k}}{1-\alpha_{k}^{2}R^{2}}\left(1-\frac{(k+2)^{2}}{(k+1)(k+3)}\alpha_{k}^{2}R^{2}\right)$
$\displaystyle=\alpha_{k}\left(1-\frac{1}{(k+1)(k+3)}\frac{\alpha_{k}^{2}R^{2}}{1-\alpha_{k}^{2}R^{2}}\right)$

with $\alpha_{0}\in(0,1/R),$ and R a predetermined constant. Here, $G$ is the
so-called saddle operator, $G:=(\nabla_{x}L,-\nabla_{y}L)$ and $L$ is a
convex-concave saddle function in a minimax optimization problem. It is a
nontrivial fact that $G$ is monotone [32]. The structure of the $\alpha_{k}$’s
and $\beta_{k}$’s are detailed below alongside auxiliary sequences $A_{k}$ and
$B_{k}$. We state the convergence of this algorithm as a theorem and relay the
details of its convergence via a specific Lyapunov functional as a lemma. For
more details, including a version of EAG with a non-varying step size, see
[32].

######  Theorem 3.1 (EAG-V convergence rate [32]).

Assume $L:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$ is an $R$-smooth
convex-concave function with a saddle point $z^{*}.$ Assume further that
$\alpha_{0}\in(0,\frac{3}{4R})$ and define
$\alpha_{\infty}=\lim_{k\to\infty}\alpha_{k}.$ Then EAG-V converges, with rate

$||\nabla
G(z^{k})||^{2}\leq\frac{4(1+\alpha_{0}\alpha_{\infty}R^{2})}{\alpha_{\infty}^{2}}\frac{||z^{0}-z^{*}||^{2}}{(k+1)(k+2)}$

where $G=(\nabla L|_{x\in\mathbb{R}^{n}},-\nabla L|_{-y\in-\mathbb{R}^{m}}).$

Since $z^{*}$ is the saddle point, this theorem demonstrates $O(1/k^{2})$
convergence of the algorithm. To derive this order of convergence, the
following lemma is necessary.

######  Lemma 3.2 (EAG Lyapunov Functional [32]).

Let $\\{\beta_{k}\\}_{k\geq 0}\subseteq(0,1)$ and
$\alpha_{0}\in(0,\frac{1}{R})$ be given. Consider the following sequences
defined by the given recurrence relations for $k\geq 0:$

$\displaystyle A_{k}$ $\displaystyle=\frac{\alpha_{k}}{2\beta_{k}}B_{k}$
$\displaystyle B_{k+1}$ $\displaystyle=\frac{B_{k}}{1-\beta_{k}}$
$\displaystyle\alpha_{k+1}$
$\displaystyle=\frac{\alpha_{k}\beta_{k+1}(1-\alpha_{k}^{2}R^{2}-\beta_{k}^{2})}{\beta_{k}(1-\beta_{k})(1-\alpha_{k}^{2}R^{2})}$
(3.1)

where $B_{0}=1.$ Assume that $\alpha_{k}\in(0,\frac{1}{R})$ holds for all
$k\geq 0,$ and that $L$ is $R-$smooth and convex-concave. Then the sequence
$\\{V_{k}\\}_{k\geq}$ defined as

$\displaystyle V_{k}$ $\displaystyle:=A_{k}\|G(z^{k})\|^{2}+B_{k}\langle
G(z^{k}),z^{k}-z^{0}\rangle$ (3.2)

is non-increasing.

Within (3.2), choosing $\beta_{k}=\frac{1}{k+2}$ yields
$B_{k}=k+1,A_{k}=\frac{\alpha_{k}(k+2)(k+1)}{2},$ and the construction of
$\alpha_{k+1}$ in (3.1).

##  4\. EAG-V with moving anchor

In this section, we construct and analyze a new version of the EAG-V
algorithm. Here, the anchoring point moves at each time step. We call this the
moving anchor algorithm; it utilizes a similar extragradient step. Further
down, we demonstrate comparable rates of convergence to the original EAG
algorithm with varying step-size.

For the $k-th$ iterate of $z^{0}\in\mathbb{R}^{n}\times\mathbb{R}^{m},$ the
EAG-V with moving anchor is defined as

$\displaystyle z^{0}$ $\displaystyle=\bar{z}^{0}$ $\displaystyle z^{k+1/2}$
$\displaystyle=z^{k}+\frac{1}{k+2}(\bar{z}^{k}-z^{k})-\alpha_{k}G(z^{k})$
(4.1) $\displaystyle z^{k+1}$
$\displaystyle=z^{k}+\frac{1}{k+2}(\bar{z}^{k}-z^{k})-\alpha_{k}G(z^{k+1/2})$
(4.2) $\displaystyle\bar{z}^{k+1}$
$\displaystyle=\bar{z}^{k}+\gamma_{k+1}G(z^{k+1})$ (4.3)

The major structural difference here is the introduction of the regularly-
updating $\bar{z}^{k},$ analogous to the role of $z^{0}$ in the EAG-V detailed
in the previous section. (4.3) is the regular update for this anchor; it
depends on the algorithm update (4.2) rather than exclusively on itself. All
previously defined terms are the same as in the fixed anchor algorithm, now
with

$\displaystyle c_{k+1}$ $\displaystyle\leq\frac{c_{k}}{1+\delta_{k}},$ (4.4)
$\displaystyle\gamma_{k+1}$
$\displaystyle\leq\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})}.$ (4.5)

We choose $\delta_{k}$ so that
$\displaystyle\sum_{k=0}^{\infty}\log(1+\delta_{k})<\infty$. The $c_{k}$ terms
are part of the definition of the Lyapunov functional we use in our analysis;
these come in handy when we use $\gamma_{k}$ to absolve terms. Let
$c_{\infty}:=\lim_{k\to\infty}c_{k}=c_{0}\prod_{k=0}^{\infty}\frac{1}{1+\delta_{k}}$.
As a general rule, one wishes to choose $c_{0}$ so that $c_{\infty}$ satisfies
some specified convergence constraint; these constraints will appear
throughout the major convergence theorems in this section and the next
section. While the choice of $c_{0}$ is therefore limited to according to
certain problem/algorithm constraints, in general there seems to be much
freedom in choosing $c_{0}$ and the sequence $\\{\delta_{k}\\}.$ For the rest
of this article, we take (4.4) and (4.5) to be given with equal signs instead
of inequalities. Before we proceed with the analysis, we emphasize that the
original EAG-V algorithm may be recovered simply by setting $\gamma_{k+1}:=0$
for all $k.$

Now, we give the definition of the Lyapunov functional and show that it is
nonincreasing:

######  Lemma 4.1.

The Lyapunov functional

$V_{k}:=A_{k}\|G(z^{k})\|^{2}+B_{k}\langle
G(z^{k}),z^{k}-\bar{z}^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2},$

where all constants have been previously defined, is nonincreasing.

###### Proof.

First we reorganize some of the algorithm statements and label them for use
later.

$\displaystyle
z^{k}-z^{k+1}=\beta_{k}(z^{k}-\bar{z}^{k})+\alpha_{k}G(z^{k+1/2})$ (4.6)
$\displaystyle z^{k+1/2}-z^{k+1}=\alpha_{k}(G(z^{k+1/2})-G(z^{k}))$ (4.7)
$\displaystyle\bar{z}^{k}-z^{k+1}=(1-\beta_{k})(\bar{z}^{k}-z^{k})+\alpha_{k}G(z^{k+1/2})$
(4.8) $\displaystyle\bar{z}^{k}-\bar{z}^{k+1}=-\gamma_{k+1}G(z^{k+1})$ (4.9)

(4.6) comes from rearranging (4.2), (4.7) comes from taking the difference
between (4.1) and (4.2), (4.8) is $\bar{z}^{k}$ minus (4.2), and (4.9) is
(4.3) rearranged. The overall goal of this proof is to show that the
difference $V_{k}-V_{k+1}$ is nonnegative.

$\displaystyle V_{k}$ $\displaystyle-V_{k+1}$ $\displaystyle\geq$
$\displaystyle
A_{k}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}\underbrace{+B_{k}\langle
z^{k}-\bar{z}^{k},G(z^{k})\rangle}_{\text{I}}$
$\displaystyle\underbrace{-B_{k+1}\langle
z^{k+1}-\bar{z}^{k+1},G(z^{k+1})\rangle}_{\text{II}}+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}$
$\displaystyle\underbrace{-\frac{B_{k}}{\beta_{k}}\langle
z^{k}-z^{k+1},G(z^{k})-G(z^{k+1})\rangle}_{\text{III}}$

Notice that the last term above, III, is not part of the definition of $V_{k}$
nor $V_{k+1}.$ It has been introduced to aid in the proof and is nonnegative
by the monotonicity of $G$. We would like to absolve any terms containing the
$\bar{z}^{k},\bar{z}^{k+1}$ terms. To accomplish this, our next goal is to
focus on turning the labeled parts (I, II, III) of the above line into

$\underbrace{\alpha_{k}B_{k+1}\langle
G(z^{k+1/2},G(z^{k+1})\rangle+\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}-\frac{\alpha_{k}B_{k}}{\beta{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle}_{\text{IV}}.$

We now detail this process. The term I does not change. For II, on the other
hand, we have

$\displaystyle\underbrace{-B_{k+1}\langle
z^{k+1}-\bar{z}^{k+1},G(z^{k+1})\rangle}_{\text{II}}$
$\displaystyle=B_{k+1}\langle\bar{z}^{k}-z^{k+1},G(z^{k+1})\rangle-
B_{k+1}\langle\bar{z}^{k}-\bar{z}^{k+1},G(z^{k+1})\rangle$ (4.10)
$\displaystyle=B_{k+1}\langle(1-\beta_{k})(\bar{z}^{k}-z^{k})+\alpha_{k}G(z^{k+1/2}),G(z^{k+1})\rangle-
B_{k+1}\langle-\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle$ (4.11)

where the first equality comes from recognizing
$z^{k+1}-\bar{z}^{k+1}=z^{k+1}-\bar{z}^{k}+\bar{z}^{k}-\bar{z}^{k+1}$ and the
second comes from substituting in equality (4.8) and (4.9). For III,

$\displaystyle\underbrace{-\frac{B_{k}}{\beta_{k}}\langle
z^{k}-z^{k+1},G(z^{k})-G(z^{k+1})\rangle}_{\text{III}}$
$\displaystyle=-\frac{B_{k}}{\beta_{k}}\langle
z^{k}-z^{k+1},G(z^{k})\rangle+\frac{B_{k}}{\beta_{k}}\langle
z^{k}-z^{k+1},G(z^{k+1})\rangle$ (4.12)
$\displaystyle=-\frac{B_{k}}{\beta_{k}}\langle\beta_{k}(z^{k}-\bar{z}^{k})+\alpha_{k}G(z^{k+1/2}),G(z^{k})\rangle+\frac{B_{k}}{\beta_{k}}\langle\beta_{k}(z^{k}-\bar{z}^{k})+\alpha_{k}G(z^{k+1/2}),G(z^{k+1})\rangle,$

where the last equality is a result of substituting in (4.6) in each of the
first arguments of the two terms in (4.12). Now, we can begin simplify
everything we’ve done to obtain IV.

$\displaystyle\underbrace{\langle
z^{k}-\bar{z}^{k},G(z^{k})\rangle}_{\text{I}}$ (4.13)
$\displaystyle\underbrace{\langle(1-\beta_{k})(z^{k}-\bar{z}^{k})-\alpha_{k}G(z^{k+1/2})-\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle}_{\text{II}}$
(4.14)
$\displaystyle\underbrace{-\frac{B_{k}}{\beta_{k}}\langle\beta_{k}(z^{k}-\bar{z}^{k})+\alpha_{k}G(z^{k+1/2}),G(z^{k})\rangle}_{\text{III}}$
(4.15)
$\displaystyle\underbrace{+\frac{B_{k}}{\beta_{k}}\langle\beta_{k}(z^{k}-\bar{z}^{k})+\alpha_{k}G(z^{k+1/2}),G(z^{k+1})\rangle}_{\text{III}}$
(4.16)

From here, we’ll use two facts. First, $B_{k+1}=\frac{B_{k}}{1-\beta_{k}}.$
This allows us to combine and cancel the very first component of (4.14) with
the $\beta_{k}(z^{k}-\bar{z}^{k})$ component of (4.16). Additionally, (4.13)
cancels with the $\beta_{k}(z^{k}-\bar{z}^{k})$ component of (4.15). This
leaves us with

$\displaystyle=$ $\displaystyle\underbrace{\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle+B_{k+1}\langle\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle}_{\text{II}}$
$\displaystyle\underbrace{-\frac{B_{k}\alpha_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})\rangle+\frac{B_{k}\alpha_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle}_{\text{III}}$ $\displaystyle=$
$\displaystyle\underbrace{\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle+\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}}_{\text{IV}}$
$\displaystyle\underbrace{-\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle}_{\text{IV}},$

where the last equality is a result of applying the anchor update to get the
norm squared term, and combining the latter two terms while leaving
$G(z^{k+1/2})$ fixed.

Thus, we’ve shown

$\displaystyle A_{k}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}$
$\displaystyle+$ $\displaystyle B_{k}\langle
z^{k}-\bar{z}^{k},G(z^{k})\rangle-B_{k+1}\langle
z^{k+1}-\bar{z}^{k+1},G(z^{k+1})\rangle$ $\displaystyle+$ $\displaystyle
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}-\frac{B_{k}}{\beta_{k}}\langle
z^{k}-z^{k+1},G(z^{k})-G(z^{k+1})\rangle$ $\displaystyle=$ $\displaystyle
A_{k}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}+\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle$ (4.17) $\displaystyle-$
$\displaystyle\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle$ (4.18) $\displaystyle+$
$\displaystyle
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}+\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$
(4.19)

Now, we continue on with our goal of absolving terms. From Cauchy, we have
that

$\displaystyle\quad||z^{*}-\bar{z}^{k+1}\|^{2}\leq(1+\delta_{k})\|z^{*}-\bar{z}^{k}\|^{2}+(1+\frac{1}{\delta_{k}})\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$
(4.20)

and from the algorithm definition,

$\displaystyle\quad
c_{k+1}=\frac{c_{k}}{1+\delta_{k}},\quad\gamma_{k+1}=\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})}.$
(4.21)

We apply (4.20) to (4.19) to obtain

$\displaystyle\geq$ $\displaystyle
A_{k}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}+\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle$ $\displaystyle-$
$\displaystyle\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle-$ $\displaystyle
c_{k+1}\big{(}(1+\delta_{k})\|z^{*}-\bar{z}^{k}\|^{2}+(1+\frac{1}{\delta_{k}})\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}\big{)}+\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$

and now we apply (4.21):

$\displaystyle\geq$ $\displaystyle
A_{k}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}+\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle$ $\displaystyle-$
$\displaystyle\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle-$ $\displaystyle
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}+\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$
$\displaystyle=$ $\displaystyle
A_{k}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}+\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle$ $\displaystyle-$
$\displaystyle\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle+0.$

At this point, showing that the remaining terms are nonnegative is nontrivial,
but directly follows the arguments made in the proof of Lemma 2 in [32].
Specifically, following $(29)$ onwards in [32], one will find that

$\displaystyle A_{k}$
$\displaystyle\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}+\alpha_{k}B_{k+1}\langle
G(z^{k+1/2}),G(z^{k+1})\rangle$ $\displaystyle-$
$\displaystyle\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1/2}),G(z^{k})-G(z^{k+1})\rangle$ $\displaystyle\geq 0,$

which completes the proof. ∎

Now we have the primary result of this section.

######  Theorem 4.2.

The EAG-V algorithm with moving anchor, described above, together with the
Lyapunov functional described in Lemma 4.1, has convergence rate

$\|G(z^{k})\|^{2}\leq\frac{4(\alpha_{0}R^{2}+c_{0})\|z^{0}-z^{*}\|^{2}}{\alpha_{\infty}(k+1)(k+2)}$

as long as we assume $c_{\infty}\alpha_{\infty}\geq 1.$

###### Proof.

For the most part, this argument parallels the analogous argument found in
[32]. We use the Lyapunov functional to isolate and bound $\|G(z^{k})\|^{2}.$

$\displaystyle V_{k}$ $\displaystyle\leq
V_{0}=\alpha_{0}\|G(z^{0})\|^{2}+c_{0}\|z^{0}-z^{*}\|^{2}$ (4.22)
$\displaystyle\leq(\alpha_{0}R^{2}+c_{0})\|z^{0}-z^{*}\|^{2}$

by $R-$smoothness. On the other hand,

$\displaystyle V_{k}$ $\displaystyle=A_{k}\|G(z^{k})\|^{2}+B_{k}\langle
G(z^{k}),z^{k}-\bar{z}^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle\geq A_{k}\|G(z^{k})\|^{2}+B_{k}\langle
G(z^{k}),z^{*}-\bar{z}^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle\geq\frac{A_{k}}{2}\|G(z^{k})\|^{2}+(c_{k}-\frac{B_{k}^{2}}{2A_{k}})\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle=\frac{\alpha_{k}(k+1)(k+2)}{4}\|G(z^{k})\|^{2}+(c_{k}-\frac{k+1}{\alpha_{k}(k+2)})\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle\geq\frac{\alpha_{\infty}}{4}(k+1)(k+2)\|G(z^{k})\|^{2}+(c_{\infty}-\frac{1}{\alpha_{\infty}})\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle\geq\frac{\alpha_{\infty}}{4}(k+1)(k+2)\|G(z^{k})\|^{2}$

As long as $c_{\infty}\geq\frac{1}{\alpha_{\infty}},$ the second to last line
above is positive, and we may focus on the inequality given to us by the last
line above:

$\frac{\alpha_{\infty}}{4}(k+1)(k+2)\|G(z^{k})\|^{2}\leq(\alpha_{0}R^{2}+c_{0})\|z^{0}-z^{*}\|^{2}.$

Dividing both sides by the constant $\frac{\alpha_{\infty}}{4}(k+1)(k+2)$
gives the desired result. ∎

###  4.1. Proof of convergence for $-\gamma_{k}$

We next show that, for a slightly restricted choice of $\gamma_{k},$ our proof
works for $-\gamma_{k}$ in place of $\gamma_{k}.$ This is of interest as
numerical results indicate that certain problem settings favor $-\gamma_{k}$
in terms of convergence speed by a constant, while $+\gamma_{k}$ seems to be
favored in other settings.

######  Lemma 4.3.

In the setting of Lemma 4.1, replace $\gamma_{k}$ with $-\gamma_{k}$ in the
definition of the EAG-V algorithm with moving anchor, and suppose
$\displaystyle\gamma_{k+1}=\min{\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})},\frac{e_{k+1}}{2B_{k+1}\|G(z^{k+1})\|^{2}}},$
where $\sum e_{k}<\infty.$ Then our Lyapunov functional is nonincreasing, and
we attain the same order of convergence in our algorithm.

###### Proof.

First, note that the anchor update (4.3) has been modified to become

$\displaystyle-\gamma_{k+1}\geq-\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})},$
(4.23)

resulting in the following modification to (4.9):

$\displaystyle\bar{z}^{k}-\bar{z}^{k+1}=\gamma_{k+1}G(z^{k+1}).$ (4.24)

We see the first adjustment in the previous lemma in the transition from line
(4.10) to (4.11); note that we focus only on the terms dependent on (4.24):

$\displaystyle-$ $\displaystyle
B_{k+1}\langle\bar{z}^{k}-\bar{z}^{k+1},G(z^{k+1})\rangle$ $\displaystyle=-$
$\displaystyle B_{k+1}\langle\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle$
$\displaystyle=-$ $\displaystyle
B_{k+1}\langle(2\gamma_{k+1}-\gamma_{k+1})G(z^{k+1}),G(z^{k+1})\rangle$
$\displaystyle=-$ $\displaystyle B_{k+1}\langle
2\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle+B_{k+1}\langle\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle.$
(4.25)

The latter term in line (4.25) will go on and cancel in a quadratic form as in
the proof of the original lemma. Continuing, one will be left over with the
term $-B_{k+1}\langle 2\gamma_{k+1}G(z^{k+1}),G(z^{k+1})\rangle$.

At this point, if we proceed as in Lemma 4.1, we end up with the inequality

$V_{k}-V_{k+1}\geq-2\gamma_{k+1}B_{k+1}\|G(z^{k+1})\|^{2}$

or, after rearranging,

$V_{k}-V_{k+1}+2\gamma_{k+1}B_{k+1}\|G(z^{k+1})\|^{2}\geq 0.$

By construction, the left-hand side of the inequality should remain
nonnegative. Now, because

$\gamma_{k+1}\leq\frac{e_{k+1}}{2B_{k+1}\|G(z^{k+1})\|^{2}},$

when we proceed as in the proof of Theorem 4.2 to show convergence, getting to
the line (4.22), we get the inequality

$\displaystyle V_{k}\leq$ $\displaystyle
V_{0}+\sum_{j=1}^{k-1}2\gamma_{j}B_{j}\|G(z^{j})\|^{2}$ $\displaystyle\leq$
$\displaystyle V_{0}+\sum_{j=1}^{k-1}e_{j}$ $\displaystyle\leq$ $\displaystyle
V_{0}+\sum_{j=1}^{\infty}e_{j}$ $\displaystyle=$ $\displaystyle CV_{0},$

where $C$ is a constant. This completes the proof that our algorithm has both
a nonincreasing Lyapunov functional and the $O(1/k^{2})$ convergence under the
assumption of a (slightly restricted) negative $\gamma_{k}$ term. ∎

It is worth noting that $z^{k+1}$ is computed before $\gamma_{k+1}$ within the
algorithm, so the restriction in Lemma 4.3 and others like it may not be too
restrictive to work with. Our toy numerical tests allowed us to simply put a
negative sign in front of the $\gamma_{k}$ terms to attain convergence
matching the optimal rate, and which is in some cases markedly faster.
Unfortunately, these results do not give much of an indication as to how
exactly the tuning of $\gamma_{k}$ benefits numerical convergence rates. We
leave the theoretical exploration of this phenomena to future work.

##  5\. Moving anchor in nonconvex/nonconcave minmax problems

In [14], the methods in [32] are expanded to a broader class of smooth
structured nonconvex-nonconcave minimax problems at the same accelerated
$O(1/k^{2})$ convergence rate. This new algorithm is called the FEG, or Fast
ExtraGradient method. We bring the idea of the moving anchor to this more
general setting, and show that a moving anchor with more or less the same
conditions in the convex-concave setting is also a feasible approach in this
class of problems. Below we give the explicit definition of this FEG modified
via a moving anchor, and state its convergence results via a nonincreasing
Lyapunov functional and a theorem bounding the squared gradient norm.

The FEG with moving anchor, following [14], is given as

$\displaystyle z^{k+1/2}$
$\displaystyle=z^{k}+\beta_{k}(\bar{z}^{k}-z^{k})-(1-\beta_{k})(\alpha_{k}+2\rho_{k})G(z^{k})$
$\displaystyle z^{k+1}$
$\displaystyle=z^{k}+\beta_{k}(\bar{z}^{k}-z^{k})-\alpha_{k}G(z^{k+1/2})-(1-\beta_{k})2\rho_{k}G(z_{k})$
$\displaystyle\bar{z}^{k+1}$
$\displaystyle=\bar{z}^{k}+\gamma_{k+1}G(z^{k+1})$ $\displaystyle c_{k+1}$
$\displaystyle=\frac{c_{k}}{1+\delta_{k}}$ $\displaystyle\gamma_{k+1}$
$\displaystyle=\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})}$

where $\\{\delta_{k}\\}$ is chosen so that
$\displaystyle\sum_{i=0}^{\infty}\log(1+\delta_{i})<\infty,$ with
$\\{\gamma_{k}\\}$, $\\{c_{k}\\},$ and $c_{\infty}$ chosen in the same method
given in the EAG-V with moving anchor, and, as before, $\bar{z}^{0}=z^{0}$.
Before we state the results, two remarks are needed:

######  Remark 5.1.

For some $\rho\in\big{(}-\frac{1}{2R},\infty\big{)},\langle
G(z)-G(z^{\prime}),z-z^{\prime}\rangle\geq\rho\|G(z)-G(z^{\prime})\|^{2}\;\forall
z,z^{\prime}\in\mathbb{R}^{m}\times\mathbb{R}^{n}$. (Note $z,z^{\prime}$ are
vectors, not matrices.) This is known as $\rho-$comonotonicity, and has three
sub-conditions. For $\rho>0,$ we have cocoercivity; for $\rho=0,$ we have
monotonicity; and with $\rho<0$ we have (negative) comonotonicity. This
condition will hold whenever any FEG variant is discussed throughout this
work.

######  Remark 5.2.

As in the EAG with moving anchor, one may recover the original fixed anchor
FEG by setting $\gamma_{k}=0$ for all $k.$ This allows us to state our
algorithm while also offering an easy reference point for the original fixed
anchor version.

######  Lemma 5.3.

Suppose that the sequences $\\{\alpha_{k}\\}_{k\geq 0},$
$\\{\beta_{k}\\}_{k\geq 0},$ and $\\{R_{k}\\}_{k\geq 0}\subset(0,\infty),$ and
$\\{\rho_{k}\\}_{k\geq 0}\subset\mathbb{R}$ satisfy
$\alpha_{0}\in(0,\infty),\alpha_{k}\in(0,\frac{1}{R_{k}}),\beta_{0}=1,\\{\beta_{k}\\}_{k\geq
1}\subseteq(0,1)$ for all $k$. Additionally, assume that the following bound,
Lipschitz conditions, and comonotonicity conditions respectively hold for all
$k\geq 0:$

$\displaystyle\frac{(1-\beta_{k+1})}{2\beta_{k+1}}(\alpha_{k+1}+2\rho_{k+1})$
$\displaystyle-\rho_{k}\leq\frac{1}{2\beta_{k}}(\alpha_{k}+2\rho_{k})-\rho_{k}$
$\displaystyle\|G(z^{1})-G(z^{0})\|$ $\displaystyle\leq R_{0}\|z^{1}-z^{0}\|$
$\displaystyle\|G(z^{k+1})-G(z^{k+1/2})\|$ $\displaystyle\leq
R_{k}\|z^{k+1}-z^{k+1/2}\|$ $\displaystyle\langle
G(z^{k+1})-G(z^{k}),z^{k+1}-z^{k}\rangle$
$\displaystyle\geq\rho_{k}\|G(z^{k+1})-G(z^{k})\|^{2}.$

If also $\displaystyle
A_{0}=\frac{\alpha_{0}(L_{0}^{2}\alpha_{0}^{2}-1)}{2},B_{0}=0,B_{1}=1,$ and

$A_{k}=\frac{B_{k}(1-\beta_{k})}{2\beta_{k}}(\alpha_{k}+2\rho_{k})-B_{k}\rho_{k},\;B_{k+1}=\frac{B_{k}}{1-\beta_{k}},$

then the Lyapunov functional

$V_{k}:=A_{k}\|G(z^{k})\|^{2}-B_{k}\langle
G(z^{k}),\bar{z}^{k}-z^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2},$

where $z^{*}$ is a saddle point, is nonincreasing.

###### Proof.

This proof proceeds similarly to that of the convex-concave, monotone case in
the previous section. First, we write out some relations which will be used
shortly:

$\displaystyle\qquad
z^{k+1}-z^{k}=\frac{\beta_{k}}{1-\beta_{k}}(\bar{z}^{k}-z^{k+1})-\frac{\alpha_{k}}{1-\beta_{k}}G(z^{k+1/2})-2\rho_{k}G(z^{k})$
(5.1) $\displaystyle\qquad
z^{k+1}-z^{k}=\beta_{k}(\bar{z}^{k}-z^{k})-\alpha_{k}G(z^{k+1/2})-2\rho_{k}(1-\beta_{k})G(z^{k})$
(5.2) $\displaystyle\qquad
z^{k+1}-z^{k+1/2}=\alpha_{k}((1-\beta_{k})G(z^{k})-G(z^{k+1/2}))$ (5.3)
$\displaystyle\qquad\bar{z}^{k}-\bar{z}^{k+1}=-\gamma_{k+1}G(z^{k+1})$ (5.4)

As in the proof in the convex-concave case of EAG-V with moving anchor, we
introduce a term to the difference of two arbitrary consecutive functionals in
our sequence:

$\displaystyle V_{k}-V_{k+1}$ $\displaystyle\geq$ $\displaystyle
A_{k}\|G(z^{k})\|^{2}-B_{k}\langle G(z^{k}),\bar{z}^{k}-z^{k}\rangle-
A_{k+1}\|G(z^{k+1})\|^{2}+B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k+1}-z^{k+1}\rangle$ $\displaystyle+$ $\displaystyle
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}$
$\displaystyle-$ $\displaystyle\frac{B_{k}}{\beta_{k}}\big{(}\langle
G(z^{k+1})-G(z^{k}),z^{k+1}-z^{k}\rangle-\rho_{k}\|G(z^{k+1})-G(z^{k})\|^{2}\big{)}$
$\displaystyle=$ $\displaystyle A_{k}\|G(z^{k})\|^{2}-B_{k}\langle
G(z^{k}),\bar{z}^{k}-z^{k}\rangle-A_{k+1}\|G(z^{k+1})\|^{2}+B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k+1}-z^{k+1}\rangle$ (5.5) $\displaystyle+$ $\displaystyle
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}$
$\displaystyle-$ $\displaystyle\frac{B_{k}}{\beta_{k}}\langle
G(z^{k+1}),z^{k+1}-z^{k}\rangle+\frac{B_{k}}{\beta_{k}}\langle
G(z^{k}),z^{k+1}-z^{k}\rangle+\frac{B_{k}\rho_{k}}{\beta_{k}}\|G(z^{k+1})-G(z^{k})\|^{2}$

From here, we first simplify the introduced term further and then substitute
(5.1) into the inner product which has a $B_{k}$ out front, and then
substitute (5.2) into the inner product with a $B_{k+1}$ out front; each of
these is in line (5.5). After some computation, this leads to

$\displaystyle V_{k}-V_{k+1}$ $\displaystyle\geq$
$\displaystyle\big{(}A_{k}-\frac{2B_{k}\rho_{k}(1-\beta_{k})}{\beta_{k}}\big{)}\|G(z^{k})\|^{2}-A_{k+1}\|G(z^{k+1})\|^{2}+\frac{\alpha_{k}B_{k}}{\beta_{k}(1-\beta_{k})}\langle
G(z^{k+1}),G(z^{k+1/2})\rangle$ $\displaystyle+$
$\displaystyle\frac{2\rho_{k}B_{k}}{\beta_{k}}\langle
G(z^{k+1}),G(z^{k})\rangle-\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k}),G(z^{k+1/2})\rangle+B_{k+1}\langle
G(z^{k}),\bar{z}^{k+1}-\bar{z}^{k}\rangle$ $\displaystyle+$
$\displaystyle\frac{B_{k}\rho_{k}}{\beta_{k}}\|G(z^{k+1})-G(z^{k})\|^{2}+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}$
$\displaystyle=$
$\displaystyle\big{(}A_{k}-\frac{B_{k}\rho_{k}(1-2\beta_{k})}{\beta_{k}}\big{)}\|G(z^{k})\|^{2}-\big{(}A_{k}-\frac{B_{k}\rho_{k}}{\beta_{k}}\big{)}\|G(z^{k+1})\|^{2}+\frac{\alpha_{k}B_{k}}{\beta_{k}(1-\beta_{k})}\langle
G(z^{k+1}),G(z^{k+1/2})\rangle$ (5.6) $\displaystyle-$
$\displaystyle\frac{\alpha_{k}B_{k}}{\beta_{k}}\langle
G(z^{k}),G(z^{k+1/2})\rangle+B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k+1}-\bar{z}^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}.$
(5.7)

Next, let’s focus on the last three terms in (5.7): $B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k+1}-\bar{z}^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}.$
By Cauchy-Schwartz,

$\|z^{*}-\bar{z}^{k+1}\|^{2}\leq(1+\delta_{k})\|z^{*}-\bar{z}^{k}\|^{2}+(1+\frac{1}{\delta_{k}})\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}.$

Second, by construction

$B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k}-\bar{z}^{k+1}\rangle=\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$

and

$c_{k+1}\leq\frac{c_{k}}{1+\delta_{k}},\;\gamma_{k+1}\leq\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})}.$

Applying these facts to the three terms we’re considering, we get that

$\displaystyle B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k+1}-\bar{z}^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\|z^{*}-\bar{z}^{k+1}\|^{2}$
$\displaystyle\geq$
$\displaystyle\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k+1}-\bar{z}^{k}\|^{2}+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}\big{(}(1+\delta_{k})\|z^{*}-\bar{z}^{k}\|^{2}+(1+\frac{1}{\delta_{k}})\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}\big{)}$
$\displaystyle\geq$
$\displaystyle\frac{B_{k+1}}{B_{k+1}}c_{k+1}(1+\frac{1}{\delta_{k}})\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle-
c_{k+1}(1+\delta_{k})\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}(1+\frac{1}{\delta_{k}})\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$
$\displaystyle\geq$ $\displaystyle
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k+1}(1+\delta_{k})\|z^{*}-\bar{z}^{k}\|^{2}\geq
c_{k}\|z^{*}-\bar{z}^{k}\|^{2}-c_{k}\|z^{*}-\bar{z}^{k}\|^{2}\geq 0.$

While this takes care of the latter three terms in lines (5.6) to (5.7), that
everything else is nonnegative is a nontrivial argument. However, it directly
follows the proof of Lemma 7.1 in [14], so as before we refer to their proof,
and then our Lyapunov functional is also nonincreasing. ∎

######  Theorem 5.4 ($O(1/k^{2})$ convergence rate for FEG with moving
anchor).

For the $R-$Lipschitz continuous and $\rho-$comonotone operator G where
$\rho>-\frac{1}{2R}$, $z^{*}\in
Z_{*}(G),Z_{*}(G):=\\{z^{*}\in\mathbb{R}^{d}:G(z^{*})=0\\},$ and
$c_{\infty}-\frac{1}{\frac{1}{R}+2\rho}\geq 0,$ the sequence
$\\{z^{k}\\}_{k\geq 0}$ generated by FEG with moving anchor satisfies

$\|G(z^{k})\|^{2}\leq\frac{4c_{0}\|z^{0}-z^{*}\|^{2}}{k^{2}(\frac{1}{R}+2\rho)}$

for all $k\geq 1.$

###### Proof.

Under the same assumptions as Lemma 5.3, we take
$\alpha_{k}=1/R,\beta_{k}=\frac{1}{k+1},R_{k}=R,$ which satisfy the conditions
in the statement for all $k$ greater than or equal to $0.$ These give us
$B_{k}=k,A_{k}=\frac{k^{2}}{2}(\frac{1}{R}+2\rho)-k\rho.$

From here,

$c_{0}\|z^{*}-z^{0}\|^{2}=V_{0}\geq
V_{k}=\bigg{(}\frac{k^{2}}{2}(\frac{1}{R}+2\rho)-k\rho\bigg{)}\|G(z^{k})\|^{2}-k\langle
G(z^{k}),\bar{z}^{k}-z^{k}\rangle+c_{k}\|z^{*}-\bar{z}^{k}\|^{2},$

so then

$\displaystyle\frac{k^{2}}{2}$
$\displaystyle(\frac{1}{L}+2\rho)\|G(z^{k})\|^{2}+c_{k}\|z^{*}-\bar{z}^{k}\|^{2}$
$\displaystyle\leq$ $\displaystyle k\langle
G(z^{k}),\bar{z}^{k}-z^{k}\rangle+k\rho\|G(z^{k})\|^{2}+c_{0}\|z^{*}-z_{0}\|^{2}$
$\displaystyle\leq$ $\displaystyle k\langle
G(z^{k}),\bar{z}^{k}-z^{*}\rangle+c_{0}\|z^{*}-z_{0}\|^{2}\text{ (by
comonotonicity condition)}$ $\displaystyle\leq$ $\displaystyle
k\|G(z^{k})\|\|\bar{z}^{k}-z^{*}\|+c_{0}\|z^{*}-z_{0}\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{k^{2}}{2\delta}\|G(z^{k})\|^{2}+\frac{\delta}{2}\|\bar{z}^{k}-z^{*}\|^{2}+c_{0}\|z^{*}-z_{0}\|^{2}.$

From here, define $\frac{1}{\delta}=\frac{1}{2R}+\rho$. Then we have that

$\frac{k^{2}}{2}\bigg{(}\frac{1}{R}+2\rho-\frac{1}{2R}-\rho\bigg{)}\|G(z^{k})\|^{2}+\bigg{(}c_{\infty}-\frac{1}{\frac{1}{R}+2\rho}\bigg{)}\|\bar{z}^{k}-z^{*}\|^{2}\leq
c_{0}\|z^{*}-z_{0}\|^{2},$

and as long as the constant $c_{\infty}-\frac{1}{\frac{1}{R}+2\rho}\geq 0,$ we
obtain the desired result by dividing both sides of the inequality

$\frac{k^{2}}{2}\bigg{(}\frac{1}{2R}+\rho\bigg{)}\|G(z^{k})\|^{2}\leq
c_{0}\|z^{*}-z_{0}\|^{2}$

by $\frac{k^{2}}{2}\bigg{(}\frac{1}{2R}+\rho\bigg{)}$. ∎

See [14]’s proof of Theorem 4.1 for the analogous result with a fixed anchor.
Next, we show that having $-\gamma_{k+1}$ in place of $\gamma_{k+1}$ may also,
with some additional assumptions, provide a convergent algorithm.

######  Lemma 5.5.

In the setting of Lemma 5.3, replace $\gamma_{k}$ with $-\gamma_{k}$ in the
definition of the FEG algorithm with moving anchor, and suppose
$\displaystyle\gamma_{k+1}=\min\frac{B_{k+1}}{c_{k+1}(1+\frac{1}{\delta_{k}})},\frac{e_{k+1}}{2B_{k+1}\|G(z^{k+1})\|^{2}},$
where $\sum e_{k}<\infty.$ Then the Lyapunov functional described in Lemma 5.3
is nonincreasing, and we attain the same order of convergence for the FEG with
moving anchor and $-\gamma_{k}.$

###### Proof.

The proof proceeds in exactly the same manner as that in Lemma 4.3. ∎

As in the EAG-V with moving anchor case, we suspect this restriction is not
too major a restriction based off of numerical results, and that there is a
‘better’ way to show that the $-\gamma_{k}$ version of our algorithm
converges.

##  6\. Introducing a proximal term

###  6.1. Modified EAG-V with moving anchor

Throughout these notes, each of the algorithms thus far developed are explicit
in nature. In this section we introduce and develop a version of these moving
anchor algorithms that features a proximal term, and discuss this as a
potential future avenue of exploration. We begin with developing the proximal
version of the EAG-V with moving anchor.

######  Definition 6.1 (Modified EAG-V with moving anchor).

In the setting of EAG-V with moving anchor, consider equation (4.9) from the
proof of Lemma 4.1:

$\bar{z}^{k}-\bar{z}^{k+1}=-\gamma_{k+1}G(z^{k+1})$

and now let us consider the same equation with an additional term introduced:

$\displaystyle\bar{z}^{k}-\bar{z}^{k+1}$
$\displaystyle=-\gamma_{k+1}G(z^{k+1})-t_{k}(H(\bar{z}^{k})-H(\bar{z}^{k+1})),$
(6.1)

where $H$ is a monotone operator and $t_{k}$ is nonnegative. This only
modifies the anchor update within the algorithm itself, and it does so in the
following way:

$\displaystyle\bar{z}^{k+1}$
$\displaystyle=(I+t_{k}H)^{-1}(\bar{z}^{k}+\gamma_{k+1}G(z^{k+1})+t_{k}H(\bar{z}^{k})).$
(6.2)

This is the modified EAG-V with moving anchor.

######  Lemma 6.2.

Under the same conditions as Lemma 4.1 and with $H$ any monotone operator,
$t_{k}$ a nonnegative parameter, the Lyapunov functional for the modified
EAG-V algorithm with moving anchor is nonincreasing. Specifically, replacing
the previous $\bar{z}^{k+1}$ update in the unmodified EAG-V moving anchor
algorithm with equation (6.2) still results in a nonincreasing Lyapunov
functional.

###### Proof.

Within the proof of Lemma 4.1 recall the following line:

$\displaystyle-B_{k+1}\langle z^{k+1}$
$\displaystyle-\bar{z}^{k+1},G(z^{k+1})\rangle$
$\displaystyle=B_{k+1}\langle\bar{z}^{k}-z^{k+1},G(z^{k+1})\rangle-
B_{k+1}\langle\bar{z}^{k}-\bar{z}^{k+1},G(z^{k+1})\rangle.$

Within this proof that the functional is nonincreasing, the primary change is
that we must use equation (6.1) for substituting $G(z^{k+1}).$ This results in

$\displaystyle-B_{k+1}\langle\bar{z}^{k}$
$\displaystyle-\bar{z}^{k+1},G(z^{k+1})\rangle$
$\displaystyle=-B_{k+1}\bigg{\langle}\bar{z}^{k}-\bar{z}^{k+1},\frac{\bar{z}^{k}-\bar{z}^{k+1}+t_{k}(H(\bar{z}^{k})-H(\bar{z}^{k+1}))}{-\gamma_{k+1}}\bigg{\rangle}$
$\displaystyle=\frac{B_{k+1}}{\gamma_{k+1}}\bigg{(}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}+t_{k}\langle\bar{z}^{k}-\bar{z}^{k+1},H(\bar{z}^{k})-H(\bar{z}^{k+1}\rangle\bigg{)}.$

The term $\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}$ will
be utilized elsewhere (see Lemma 4.1) so we don’t need to worry about it here,
and the term
$\frac{B_{k+1}}{\gamma_{k+1}}t_{k}\langle\bar{z}^{k}-\bar{z}^{k+1},H(\bar{z}^{k})-H(\bar{z}^{k+1}\rangle$
is nonnegative by monotonicity and the fact that $t_{k}$ is also nonnegative.
This completes the proof. ∎

######  Theorem 6.3.

The modified EAG-V algorithm with moving anchor has convergence rate
$O(1/k^{2}).$

######  Remark 6.4.

While $H$ may be any monotone operator, in practice one may wish to take
$H=G.$

###  6.2. Modified FEG with moving anchor

######  Definition 6.5 (Proximal FEG with moving anchor).

In the setting of FEG with moving anchor, consider (5.4) from the proof of
Lemma 5.3:

$\bar{z}^{k}-\bar{z}^{k+1}=-\gamma_{k+1}G(z^{k+1})$

and now let’s consider the same term with a proximal term introduced:

$\displaystyle\bar{z}^{k}-\bar{z}^{k+1}$
$\displaystyle=-\gamma_{k+1}G(z^{k+1})-t_{k}(H(\bar{z}^{k})-H(\bar{z}^{k+1})),$

where $H$ is a monotone operator just as before. This modification affects the
anchor update in the same way as in the previous case:

$\displaystyle\bar{z}^{k+1}$
$\displaystyle=(I+t_{k}H)^{-1}(\bar{z}^{k}+\gamma_{k+1}G(z^{k+1})+t_{k}H(\bar{z}^{k}))$
(6.3)

######  Lemma 6.6.

Under the same conditions as Lemma 5.3 and with $H$ any monotone operator,
$t_{k}$ nonnegative for all $k$, the Lyapunov functional for the modified FEG
algorithm with moving anchor is nonincreasing. Specifically, replacing the
previous $\bar{z}^{k+1}$ update in the unmodified FEG moving anchor algorithm
with (6.3) still results in a nonincreasing Lyapunov functional.

###### Proof.

The proof proceeds in the same manner as in that of Lemma 6.2. The only minor
difference is that in this case, we begin with $B_{k+1}\langle
G(z^{k+1}),\bar{z}^{k+1}-\bar{z}^{k}\rangle$. We still obtain from this the
terms

$\frac{B_{k+1}}{\gamma_{k+1}}\|\bar{z}^{k}-\bar{z}^{k+1}\|^{2}+\frac{B_{k+1}}{\gamma_{k+1}}t_{k}\langle\bar{z}^{k}-\bar{z}^{k+1},H(\bar{z}^{k})-H(\bar{z}^{k+1}\rangle,$

where the first term is utilized elsewhere in the larger proof of the
functional being nonincreasing and the latter term is monotone, thus
nonnegative. ∎

######  Theorem 6.7.

The modified FEG algorithm with moving anchor has convergence rate
$O(1/k^{2}).$

##  7\. Numerical experiments

In this section we detail several numerical experiments. First, we visualize
two thousand iterations of EAG-V and FEG, each moving anchor versus the fixed
anchor, on a toy ‘almost bilinear’ example. Next, we look at the log of the
grad norm squared versus the log of iterations for the EAG examples. Note that
this error graph is an example in the monotone convex-concave case. We then
run a nonconvex-nonconcave negative comonotone example for FEG variants, where
some interesting convergence behaviors among the moving anchor variants are
exhibited. Finally, we study monotone FEG variants (moving and fixed anchor)
on a nonlinear two player game. Throughout all of these examples,
$c_{1}=\pi^{2}/6,$ $c_{k}=\frac{c_{k-1}}{1+\delta_{k-1}}(k=2,3,...),$ and in
all except for the last example, $\delta_{k}$ is chosen to be $\exp(k^{2})-1.$

Figure 1. The first two thousand iterations of the EAG algorithm with varying
step-size, or EAG-V, compared to the first two thousand iterations of the
moving anchor EAG-V algorithm.

Figure 1 compares the iterations of EAG-V with a fixed anchor to the
iterations for the moving anchor EAG-V. Figure 1, Figure 2, and Figure 3 all
display iterations where the function used is the ‘almost bilinear’ function
$f:\mathbb{R}^{2}\to\mathbb{R},f(x,y)=\epsilon\frac{\|x\|^{2}}{2}+\langle
x,y\rangle-\epsilon\frac{\|y\|^{2}}{2}.$ Here, $\epsilon$ is small, for these
experiments set to $0.01,$ and the straightforward nature of the example
allows for ease of visualizing the iterations as well as their differences
when it comes to comparing convergence rates. In particular, the unique
saddle-point is $(0,0).$

Figure 2. The two moving anchor EAG-V variants compared in red, along with
their anchors in green.

Figure 2 compares, via the same function as Figure 1, the two moving anchor
variants of EAG-V. When the $\gamma_{k}$ parameter is positive, the anchor
iterations moves away from the saddle and the algorithm updates very rapidly.
When $\gamma_{k}$ has only its sign changed to negative, the anchor (seen in
green) seems to stay much closer to the iterations and the saddle-point. The
iterations appear to converge at a markedly faster rate (by a constant) for
this latter case over both the fixed anchor and the positive $\gamma_{k}$
setting, an observation that is confirmed below.

Figure 3. The two moving anchor FEG variants compared in red, along with their
anchors in green.

Figure 3 compares the two moving anchor version of the FEG method, in the same
manner as the comparison shown in Figure 2: red dots are the algorithm
updates, green dots are the anchor updates, and the function is the ‘almost
bilinear’ one previously described. Note that in both cases, the iterations
seem to zone in on and converge to the saddle point in a much faster manner.
In [14], the authors established that even on convex-concave problems, FEG
performs at the same optimal order of convergence as EAG, but at a
significantly faster rate. This behavior seems to have carried over to our
algorithm where we introduce the moving anchor to these frameworks.

Figure 4. Comparison of the grad-norm squared of three EAG-V variants of
interest on a toy ‘almost bilinear’ problem.

Figure 4 captures the behavior of $\|G(z^{k})\|^{2}$ across all three convex-
concave algorithms of interest: EAG-V, moving anchor EAG-V with positive
$\gamma_{k},$ and moving anchor EAG-V with negative $\gamma_{k}.$ Each
algorithm attains the optimal order of convergence, while the negative
$\gamma_{k}$ algorithm is markedly faster than both algorithms by a constant.
Identical behavior occurrs under the same problem setting with the FEG and FEG
with moving anchors (positive and negative $\gamma_{k}$), with the negative
$\gamma_{k}$ algorithm again being the fastest, so we do not include this
figure here.

Figure 5. Comparison of the errors of three FEG variants in a nonconvex-
nonconcave setting. Note the positive $\gamma$ converges fastest by a
constant.

Figure 5 captures the error of FEG across all three anchor variants in a
numerical example that is explicitly comonotone and nonconvex-nonconcave:

$L(x,y)=\frac{\rho R^{2}}{2}x^{2}+R\sqrt{1-\rho^{2}R^{2}}xy-\frac{\rho
R^{2}}{2}y^{2}$

with $L:\mathbb{R}^{2}\to\mathbb{R},R=1,\rho=-1/3$ $1-$smooth and
$-1/3$-negative comonotone. Interestingly, this is the only numerical example
where the moving anchor with positive $\gamma_{k}$ \- of any variant - was the
fastest of all three algorithms. The intuition is that the positive
$\gamma_{k}$ functions as negative $\gamma_{k}$ in the monotone, convex-
concave problem settings, pulling the iterations closer to the saddle. More
examples in this vein may verify that this behavior with positive $\gamma_{k}$
occurs only in the negative comonotone problem setting. More theoretical work
to verify this observed numerical behavior will be one of our goals in a
future work.

Figure 6. $\log$ of iterations versus $\log$ of the gradient norm-squared for
monotone (that is, $\rho=0$) FEG variants studied on a particular nonlinear
game.

The final figure, Figure 6, compares three different monotone FEG variants on
a particular nonlinear game that was studied extensively in [4]:

$\min_{x\in\Delta^{n}}\max_{y\in\Delta^{m}}\frac{1}{2}\langle
Qx,x\rangle+\langle Kx,y\rangle$

where $Q=A^{T}A$ is positive semidefinite for $A\in\mathbb{R}^{k\times n}$
which has entries generated independently from the standard normal
distribution, $K\in\mathbb{R}^{m\times n}$ with entries generated uniformly
and independently from the interval $[-1,1],$ and $\Delta^{n},\Delta^{m}$ are
the $n-$ and $m-$simplices, respectively:

$\Delta^{n}:=\Big{\\{}x\in\mathbb{R}_{+}^{n}:\sum_{i=1}^{n}x_{i}=1\Big{\\}},\;\Delta^{m}:=\Big{\\{}y\in\mathbb{R}_{+}^{m}:\sum_{j=1}^{m}y_{j}=1\Big{\\}}.$

One may interpret this as a two person game where player one has $n$
strategies to choose from, choosing strategy $i$ with probability
$x_{i}\;(i=1,...,n)$ to attempt to minimize a loss, while the second player
attempt to maximize their gain among $m$ strategies with strategy $j$ chosen
with probability $y_{j}\;(j=1,...,m).$ The payoff is a quadratic function that
depends on the strategy of both players. For this example, we used FEG fixed
and moving anchor variants in the monotone (that is, $\rho=0$) setting of the
algorithm. We compare $20,000$ iterations of the log of the grad norm squared
of the fixed anchor versus the same for a negative $\gamma_{k}$ variant where
the parameter $\delta$ is scaled by $1/10$ and a negative $\gamma_{k}$ variant
where $\delta$ is scaled by $1/100.$ This is the first numerical example where
we tune $\delta,$ a parameter used in controlling the step size. We chose
$m=500,$ $k=1000$, and $n=2500.$

We remark that, initially, it seems the $\frac{1}{10}\delta$ variant is
fastest by a constant, and then is overtaken by the $\frac{1}{100}\delta$
variant and then the fixed anchor while the initially faster
$\frac{1}{10}\delta$ ‘flattens out’ rather quickly. For much of this
experiment, it appears that the $\frac{1}{100}\delta$ variant and the fixed
anchor very closely parallel one another - there seems to be a slight
advantage to the $\frac{1}{100}\delta$ moving anchor for the majority of the
experiment after between two and three dozen iterations, and then at the tail
end of the experiment the fixed anchor may have a marginal lead.

##  8\. Conclusion

The moving anchor acceleration methods retain optimal convergence rates and
also demonstrate superior-to-comparable numerical performance with some
parameter tuning. The optimal order of convergence is obtained across
different problem settings, from convex-concave to negative co-monotone
problems. Interestingly, across numerous problem settings there exists a
version of the moving anchor algorithm, parametrized by $\gamma_{k},$ that
demonstrates superior numerical performance compared to other state-of-the-art
algorithms. The variety of numerical examples demonstrates a wide array of
applications for our algorithms in both theoretical and applied settings. In
addition, we develop a ‘proximal’ version of the moving anchor in both the
convex-concave and negative co-monotone problem settings and demonstrate its
convergence. Of future interest, one may consider numerical and practical
implementations of the proximal moving anchor, parallelized/asynchronous
implementations of moving anchor saddle point algorithms, a tighter analysis
of $-\gamma_{k}$ convergence, a theoretical understanding of how the
$\gamma_{k}$ and other parameters such as $\delta$ affect convergence rates,
and the identification of problem settings which our moving anchor may exploit
effectively among many other topics.

## Acknowledgements

We thank Donghwan Kim, Ernest K. Ryu, and Taeho Yoon for their invaluable
suggestions that have greatly improved and inspired this work.

## References

  * [1] Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel, _A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games_ , International conference on artificial intelligence and statistics, PMLR, 2020, pp. 2863–2873.
  * [2] Xufeng Cai, Chaobing Song, Cristóbal Guzmán, and Jelena Diakonikolas, _A stochastic halpern iteration with variance reduction for stochastic monotone inclusion problems_ , arXiv preprint arXiv:2203.09436 (2022).
  * [3] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien, _Reducing noise in gan training with variance reduced extragradient_ , Advances in Neural Information Processing Systems 32 (2019).
  * [4] Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang, _Optimal primal-dual methods for a class of saddle point problems_ , SIAM Journal on Optimization 24 (2014), no. 4, 1779–1814.
  * [5] Jelena Diakonikolas, _Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities_ , Conference on Learning Theory, PMLR, 2020, pp. 1428–1451.
  * [6] Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan, _Efficient methods for structured nonconvex-nonconcave min-max optimization_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 2746–2754.
  * [7] Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou, _Stochastic variance reduction methods for policy evaluation_ , International Conference on Machine Learning, PMLR, 2017, pp. 1049–1058.
  * [8] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar, _Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems_ , 2020.
  * [9] Ian J Goodfellow, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, Yoshua Bengio, and Jean Pouget-Abadie, _Generative adversarial nets_ , Advances in neural information processing systems 27 (2014), 2672–2680.
  * [10] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel, _Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2022, pp. 366–402.
  * [11] Benjamin Halpern, _Fixed points of nonexpanding maps_ , Bulletin of the American Mathematical Society 73 (1967), no. 6, 957–961.
  * [12] Galina M Korpelevich, _The extragradient method for finding saddle points and other problems_ , Matecon 12 (1976), 747–756.
  * [13] Jongmin Lee and Ernest K Ryu, _Accelerating value iteration with anchoring_ , arXiv preprint arXiv:2305.16569 (2023).
  * [14] Sucheol Lee and Donghwan Kim, _Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems_ , (2021).
  * [15] Sucheol Lee and Donghwan Kim, _Semi-anchored multi-step gradient descent ascent method for structured nonconvex-nonconcave composite minimax problems_ , arXiv preprint arXiv:2105.15042 (2021).
  * [16] Felix Lieder, _On the convergence rate of the halpern-iteration_ , Optimization letters 15 (2021), no. 2, 405–418.
  * [17] Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang, _Towards better understanding of adaptive gradient algorithms in generative adversarial nets_ , arXiv preprint arXiv:1912.11940 (2019).
  * [18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, _Towards deep learning models resistant to adversarial attacks_ , arXiv preprint arXiv:1706.06083 (2017).
  * [19] Arkadi 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 (2004), no. 1, 229–251.
  * [20] Arkadij Semenovič Nemirovskij and David Borisovich Yudin, _Problem complexity and method efficiency in optimization_ , (1983).
  * [21] Arkadi S Nemirovsky, _On optimality of krylov’s information when solving linear operator equations_ , Journal of Complexity 7 (1991), no. 2, 121–130.
  * [22] by same author, _Information-based complexity of linear operator equations_ , Journal of Complexity 8 (1992), no. 2, 153–175.
  * [23] Yurii Nesterov, _A method for unconstrained convex minimization problem with the rate of convergence o (1/k^ 2)_ , Doklady an ussr, vol. 269, 1983, pp. 543–547.
  * [24] by same author, _Dual extrapolation and its applications to solving variational inequalities and related problems_ , Mathematical Programming 109 (2007), no. 2-3, 319–344.
  * [25] Yuyuan Ouyang and Yangyang Xu, _Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems_ , Mathematical Programming 185 (2021), no. 1-2, 1–35.
  * [26] R Tyrrell Rockafellar, _Monotone operators associated with saddle-functions and minimax problems_ , Proceedings of Symposia in Pure Mathematics, vol. 18, American Mathematical Society, 1970, pp. 241–250.
  * [27] Ernest K Ryu, Kun Yuan, and Wotao Yin, _Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems and gans_ , (2019).
  * [28] Jaewook J Suh, Jisun Park, and Ernest K Ryu, _Continuous-time analysis of anchor acceleration_ , arXiv preprint arXiv:2304.00771 (2023).
  * [29] Quoc Tran-Dinh, _The connection between nesterov’s accelerated methods and halpern fixed-point iterations_ , arXiv preprint arXiv:2203.04869 (2022).
  * [30] Quoc Tran-Dinh and Yang Luo, _Halpern-type accelerated and splitting algorithms for monotone inclusions_ , arXiv preprint arXiv:2110.08150 (2021).
  * [31] Paul Tseng, _On linear convergence of iterative methods for the variational inequality problem_ , Journal of Computational and Applied Mathematics 60 (1995), no. 1-2, 237–252.
  * [32] Taeho Yoon and Ernest K Ryu, _Accelerated algorithms for smooth convex-concave minimax problems with $o(1/k^{2})$ rate on squared gradient norm_, Proceedings of the 38th International Conference on Machine Learning 139 (2021), 12098–12109.


# Content Masked Loss: Human-Like Brush Stroke Planning in a Reinforcement
Learning Painting Agent

Peter Schaldenbrand, Jean Oh

###### Abstract

The objective of most Reinforcement Learning painting agents is to minimize
the loss between a target image and the paint canvas. Human painter artistry
emphasizes important features of the target image rather than simply
reproducing it (DiPaola 2007). Using adversarial or $L_{2}$ losses in the RL
painting models, although its final output is generally a work of finesse,
produces a stroke sequence that is vastly different from that which a human
would produce since the model does not have knowledge about the abstract
features in the target image. In order to increase the human-like planning of
the model without the use of expensive human data, we introduce a new loss
function for use with the model’s reward function: Content Masked Loss. In the
context of robot painting, Content Masked Loss employs an object detection
model to extract features which are used to assign higher weight to regions of
the canvas that a human would find important for recognizing content. The
results, based on 332 human evaluators, show that the digital paintings
produced by our Content Masked model show detectable subject matter earlier in
the stroke sequence than existing methods without compromising on the quality
of the final painting.

## Introduction

While there are numerous differences between the methods used by a skilled
human painter and a machine printer, the end products may look similar. As is
the case with photo-realistic portraits, a human painter hopes to recreate a
target image as closely as possible with paint. A printer, though not using
paint and a brush, would have a similar objective, however, would go about it
in a completely different fashion. A printer may use a simple heuristic to
render the image such as starting from the top left and working left-to-right
and top-top-bottom, but a human painter would likely take an abstract
approach. As a painter paints using the commonly used “blocking in” (Scott
2017) technique, you can recognize the subject of the painting early in the
painting process, and the fidelity of the rendering improves with time. In
this way, painting can be considered an anytime algorithm: If the painting
process is interrupted at any point, a valid solution should be available, but
the solution becomes better the longer the process executes for.

The goal of Stroke Based Rendering (SBR) is to find methods to reproduce a
target image using visual elements, such as paint brush strokes. Many SBR
methods (Hertzmann 2003) were deterministic algorithms which placed strokes
onto a canvas that would minimize the loss between the next canvas and the
target image. Modern SBR methods (Ganin et al. 2018) (Huang, Heng, and Zhou
2019) (Nakano 2019) (Xie, Hachiya, and Sugiyama 2012) use Reinforcement
Learning models to generate the stroke sequences. All of these RL methods use
an adversarial or $L_{2}$ loss in their reward functions which are designed to
minimize the difference between the canvas and the target image. These loss
functions are oblivious to abstract content of the image and the stroke
sequence can follow any method that the model finds on its way to minimizing
the loss.

Figure 1: The Reinforcement Learning painting models are adapted from (Huang,
Heng, and Zhou 2019) with brush stroke constraints. Our model uses a clipped
$L_{1}$ loss with Content Masking in its reward function, while the baseline
does not use the Content Masking. Figure 2: The Reinforcement Learning Painter
generated brush strokes to paint the target image. The strokes can be
renderered into an image by feeding them to the Neural Renderer or the robot
painting agent as seen above. The robot painter is a TinkerKit Braccio robotic
arm. 10 paint colors, that are chosen by running k-means clustering on the
target image, are mixed by a human and provided to the robot. The arm has a
single paint brush and can clean it using water and a towel. The robot is
fully autonomous while painting.

With existing SBR RL, it is often not clear what the models are painting until
the last set of brush strokes are performed as seen in Figure 3. In this way,
the SBR RL models are similar to printers and deterministic SBR models. In
generative art such as GANs (Elgammal et al. 2017), only the final output
image is used for evaluating models. In machine painting, however, the whole
performance needs to be evaluated in addition to the final canvas. In this
paper, we view painting as a plan that is a sequence of actions (or brush
strokes) towards an end output. In this context, the proposed idea is to
improve the quality of a painting plan according to human-like painting
techniques where a subject of the painting becomes incrementally more
recognizable as brush strokes are added.

One approach for guiding a RL painting model to paint more like a human would
be to collect brush stroke level data from real human painters. This method
would require collecting a large number of samples, each of which would take a
long time to produce. The samples would need to be diverse so that the model
generalizes on multiple different types of paintings such as portraits or
landscapes. All-in-all it would be an expensive, time-consuming process.

Our research goal in this paper is to make the brush stroke planning of a
reinforcement learning painter model more human-like. We focus on the common
painting technique of “blocking-in” where the subject of a painting is
recognizable early in the painting process. We introduce Content Masked Loss
which gives more reward to painting regions of the canvas that are important
for recognizing the subject matter of the painting. An object recognition
model is used to extract which regions of the image are important for
recognition. Amazon Mechanical Turk workers found that the subject matter of
the paintings produced from our models that used Content Masked Loss was
apparent far earlier in the brush stroke planning than baseline models using
adversarial or $L_{2}$ loss.

Figure 3: Row (a) is the (Huang, Heng, and Zhou 2019) model and row (b) is our
baseline model trained using a constrained Neural Renderer. The constraints
assume that the brush strokes are fixed width, opaque, and do not exceed a
maximum length. Our baseline model also assumes a white starting canvas
whereas (Huang, Heng, and Zhou 2019) starts with a black canvas.

## Related Work

Stroke-based Rendering (SBR) is the process of layering individual elements,
such as shapes or brush strokes, onto a digital canvas in order to reproduce a
given image. The goal of SBR may be to perfectly recreate an image with a
given set of tools, or it may be to add creative abstractions while rendering.

Recent methods attempt to tackle SBR using deep learning (Ganin et al. 2018)
(Huang, Heng, and Zhou 2019) (Nakano 2019) (Xie, Hachiya, and Sugiyama 2012),
though the field has existed long before these tools became popular (Hertzmann
2003). “Artist Agent” (Xie, Hachiya, and Sugiyama 2012) was an approach to
modelling brush strokes on paper using a reinforcement learning agent. The
agent designed brush strokes and received feedback as to whether the strokes
were believably made by a human or not. The individual brush strokes produced
by Artist Agent were believably human but in order to render a whole painting,
the stroke planning was manually produced by humans.

Other SBR work attempts to create an agent that can produce whole paintings
rather than single brush strokes. SPIRAL (Ganin et al. 2018) used
reinforcement learning to generate brush strokes that would render into a
painting that minimized the difference between the canvas and the given image.
Work that builds off of SPIRAL, such as (Nakano 2019) (Zheng, Jiang, and Huang
2019) (Huang, Heng, and Zhou 2019), often use the world model concept (Ha and
Schmidhuber 2018) in order to speed up training. In the case of painting, the
world model is called a Neural Renderer. The Neural Renderer is implemented
with a differentiable neural network so that the loss can be back-propagated
through it. (Huang, Heng, and Zhou 2019) achieves the best results at
decomposing an image into a series of strokes. The objective of their
reinforcement learning algorithm is to minimize the difference between the
generated painting and the given painting. The authors find that using WGAN
loss known as Wasserstein-l distance, or Earth-Mover distance, generates
better results than the $L_{2}$ distance. The results from this paper are very
successful, for with enough strokes, the model is able to almost completely
recreate the input image, but the planning process shows no indication of what
the subject matter of the painting is.

Existing datasets that have paired images with strokes lack quality for
painting portraits. For instance, the QuickDraw (Ha and Eck 2017) dataset,
which contains cartoon sketches that users create while trying to render a
given image or noun, contain both the brush strokes and image data, however,
these sketches are too simple for learning real painting. SketchRNN (Ha and
Eck 2017) does use paired data, but it can only draw objects that have been
labelled in its training data. This dataset encodes the planning method for
how humans sketch, but we need the method of how humans paint.

Reinforcement Learning models such as (Huang, Heng, and Zhou 2019) and SPIRAL
(Ganin et al. 2018) learn through trial and error how to paint images. The
reward functions are designed to make the model learn which strokes will
decrease the loss between the painting and the target image. Because these
models learn without human data guidance, they do not encode how a human
painter would paint. In this paper, we introduce Content Masked Loss which
increases the human-like brush stroke planning abilities of the RL model
without the use of human painter data.

The brush strokes used in the planning of (Huang, Heng, and Zhou 2019) are not
capable of being reproduced by a standard paint brush, as seen in Figure 3.
Because these brush strokes are not reproducible by a real paint brush, we
cannot evaluate if the brush stroke planning is human-like or not.
Constraining the model to use only realistic brush strokes will make it
possible to evaluate whether the planning if human-like or not. In this paper,
we constrain our Reinforcement Learning method of Stroke-Based Rendering to
produce brush stroke instructions that are realistic and can easily be fed to
a painting agent to be painted accurately. An example of feeding these paint
brush instructions can be seen in Figure 2.

## Approach

A robot painting problem is informally defined as follows. Given an input
image and a blank canvas, the goal is to generate a sequence of brush strokes
that will turn the canvas into a recreation of the input image, following a
human-like painting style. This section describes an RL formulation of the
task, focusing on how the proposed reward functions induce human-like plans.

### Reinforcement Learning Painter Model

The proposed work builds on the deep reinforcement learning framework from
(Huang, Heng, and Zhou 2019). The original framework is based on several
unrealistic assumptions; We modify the framework to address realistic
constraints. First, the brush strokes are allowed to be unrealistically large,
e.g., more than half the width of the canvas as seen in Figure 3. We constrain
what is possible for the brush strokes based on what our robot painting agent
is able to do with a single paint brush. In this way, we can easily feed the
brush stroke instructions to a robot such as the one used in our experiments
shown in Figure 2. Specifically, we constrained them to be fixed width and
only 5% of the width of the canvas which is consistent with the robot’s brush
width. Second, it was assumed that the blank starting canvas is black which is
not consistent with the white paper or canvas that a painter would generally
use; we changed this assumption to be white in our model. Third, a paint brush
can only hold so much paint, so we add the maximum length of one half of the
canvas width to the brush strokes based on the robots attempts at painting on
a 20cm piece of paper. Additionally, since the acrylic paint that the robot
utilizes is opaque, we add this as a constraint for the purpose of our study.

We formulate painting as a reinforcement learning task, following the problem
formulation in (Huang, Heng, and Zhou 2019). Here, states represent the canvas
from blank to completion. The action space describes the brush strokes in the
form of Bézier curves with values for three position coordinates, thickness of
the brush stroke at both ends, opacity of the paint at both ends, and color.
The Neural Renderer is the transition function which paints a brush stroke in
this action space onto a given canvas.

As the action space is continuous, our model adopts the Deep Deterministic
Policy Gradient (DDPG) (Lillicrap et al. 2016). The reward function is
calculated by computing the difference between the losses at time $t$ and
$t+1$ as seen in Equation 1. Huang et al. uses an adversarial model to compute
the loss function (Equation 2). The model based DDPG critic predicts an
expected reward function:

$\displaystyle V(c_{t})=r(c_{t},a_{t})+\gamma V(c_{t+1})$

where $r(c_{t},a_{t})$ is the reward of performing action $a_{t}$ on canvas
$c_{t}$, and $\gamma$ is a penalty parameter which controls how influencial
future value is. $c_{t+1}$ can be renderered using the Neural Renderer to
apply the brush stroke $a_{t}$ to the canvas $c_{t+1}$, seen below as
$trans(c_{t},a_{t})$. The actor in the DDPG, $\pi(c_{t})$, is trained to
maximize the expected reward:

$\displaystyle r(c_{t},\pi(c_{t}))+\gamma V(trans(c_{t},\pi(c_{t})))$

$\displaystyle Reward$
$\displaystyle=mean\left[L(c_{t},y)-L(c_{t+1},y)\right]$ (1)

Baseline

$\displaystyle L_{GAN}(c,y)$ $\displaystyle=1-Discriminator(c,y)$ (2)
$\displaystyle L_{L2}(c,y)$ $\displaystyle=(c-y)^{2}$ (3)

Ours

$\displaystyle L_{CL}(c,y)$ $\displaystyle=(VGG_{l}(c)-VGG_{l}(y))^{2}$ (4)
$\displaystyle L_{CM+L2}(c,y)$ $\displaystyle=(c-y)^{2}*norm(VGG_{l}(y)$ (5)
$\displaystyle L_{L1^{*}}(c,y)$ $\displaystyle=min(|c-y|,\lambda)$ (6)
$\displaystyle L_{CM+L1^{*}}(c,y)$
$\displaystyle=min(|c-y|,\lambda)*norm(VGG_{l}(y))$ (7)

Figure 4: The reward function is the per-pixel average of the loss between the
canvas at time $t$ and the canvas with an additional stroke at time $t+1$. The
various loss functions used in this paper follow, where $c$ is the canvas and
$y$ is the target image. The $Discriminator$ is a model used to differentiate
paintings of an image and the actual image, and $norm()$ is a 0-1 normalizing
function.

### Reward Functions

The (Huang, Heng, and Zhou 2019) model used the adversarial loss as seen in
Equation 2 and is used in the baseline model in this paper. The
$Discriminator$ model outputs 1 if the canvas and target image are the same
and 0 if they are completely different. The $Discriminator$ is only trained to
determine visual differences between the paintings and the target image so it
does not factor in content and abstract detail from the images.

Painters take an abstract approach when painting and consider the subject of
the target image. Human painters use techniques such as “blocking-in” (Scott
2017) which ensure that the subject of the image is recognizable early in the
painting process. We took two different approaches to increasing the
recognizability of the painting strokes: Content Loss Reward and Content
Masked Reward.

#### Content Loss Reward

In Content Loss (Equation 4), we used the $L_{2}$ loss on the features
extracted from the canvas and target images instead of the images themselves.
We used the VGG-16 (Simonyan and Zisserman 2015) model to extract the
features. The VGG-16 parameters were fixed. The intuition behind Content Loss
is that if a painting and the target image have similar features extracted
from an object detection model, then they should recognizably be paintings of
the same object.

The VGG-16 (Simonyan and Zisserman 2015) object detection model was trained on
photographs, so it is not expected to generalize to paintings. We attempt to
use Content Loss but recognize that a feature extractor that is robust to both
photographs and paintings may be necessary to make this loss function work
properly.

#### Content Masked Loss Reward

Content Masked Loss was designed to increase the weight of the per-pixel loss
in “important” regions of the canvas. The “importance” of a region is
determined by extracting features using the VGG-16 (Simonyan and Zisserman
2015) model. As seen in Figure 5, the Content Masking can be added to the
$L_{2}$ distance to weight the difference between a canvas and the target
image. The features are computed by feeding the target image into the VGG-16
model, taking the output of an intermediate layer, averaging the image across
the channels, and then 0-1 normalizing it. We experimented using the output
from different layers in the VGG-16 model in Figures 8 and 9.

Figure 5: Content Masking added to the $L_{2}$ loss is defined as the
difference between a canvas and the target image weighted by the features
extracted from the target image.

#### L1 with Loss Clipping

Certain biases of the painting model may cover up the effects of Content
Masking. All of the loss functions except Content Loss rely on measures of
distance between pixels in the canvas and the target image. Since the images
are in RGB format, the largest distance would be between a white and black
pixel. The canvas is initially white, so the model will have a bias towards
painting darker colors, since it can get more reward with them. We reduced
this bias by experimenting with $L_{1}$ instead of $L_{2}$ losses. We also set
a constant maximum value for the per-pixel loss. Loss Clipping used in a loss
function can be seen in Figure 4 with $L_{1}$ ($L1*$) and in conjunction with
Content Masked Loss ($CM+L1*$).

Figure 6: On the left is the target image. The paintings were created by the
model generating 125 strokes looking at the whole canvas and then 125 strokes
in each of 25 evenly distributed subsections of the canvas. (a) was created
using the (Huang, Heng, and Zhou 2019) model as is while (b) used constraints
on the brush’s abilities.

## Results

The effects of the brush stroke constraints (fixed brush width, maximum brush
stroke length, fully opaque strokes, and starting with white canvas) can be
seen in Figure 3. Our baseline model is able to reproduce the target image but
not with as high fidelity as the (Huang, Heng, and Zhou 2019) model. The
strokes are now fixed width and smaller than what the (Huang, Heng, and Zhou
2019) model allows, so it takes more strokes to reproduce the target image in
our baseline model. The fixed width strokes are too big to make out details
such as mouth and eyes. In order to paint with a smaller brush size, the
canvas is divided up into subsections, then the model is run over each
subsection. So if we divide an image into quadrants and run our baseline model
over each, this is equivalent to painting with a brush half the width of fixed
width constraint.

The last canvases in Figure 3 show a significant difference in fidelity
between our baseline model and the (Huang, Heng, and Zhou 2019) model. One of
the most impressive aspects of the (Huang, Heng, and Zhou 2019) model was that
it could nearly replicate an image given enough strokes. We tested whether our
baseline model could also achieve this accuracy. In Figure 6, the models
generated 125 strokes using the entire image as input, then 125 strokes for
each non-overlapping 1/25th of the image. Our baseline model produces a
painting with a similar loss to the (Huang, Heng, and Zhou 2019) model’s
painting.

### Content Loss Reward

Figure 7: The top left three images are output from the model painting the
target image in the top right. The second row are the features extracted from
their corresponding image above them using the first 17 layers of the VGG-16
model.

We tried to use this content loss (Equation 4) reward function, but the model
would only go to a local minimum and produce blank canvases no matter what
parameters we used. The main reason why the Content Loss Reward function was
unsuccessful was the feature extraction process does not translate well to the
paintings. The VGG-16 model (Simonyan and Zisserman 2015) was trained on
photographs. The canvases (especially with only a few strokes) are so vastly
different from photographs that the extracted features appear random. As seen
in Figure 7, even when the painting is extremely similar to the target image,
the features extracted are very different from those extracted from the
photograph. The features extracted from the photographic target image make
semantic, abstract sense while the features from the paintings are
unintelligible. In future work we will attempt to use feature extraction
models that are robust to texture variance, such as (Geirhos et al. 2019) who
minimized the texture bias in an ImageNet (Deng et al. 2009) classifier model.

Figure 8: Features extracted from a given image at various layers within the
VGG-16 (Simonyan and Zisserman 2015) model. Figure 9: Models were trained
using Content Masked Reward where the features were generated using various
layers in the VGG-16 model.

### Content Masked Reward

The VGG-16 model has 31 layers in the feature extraction portion of the
architecture. To compute the feature mask, the output of a layer is averaged
across channels and 0-1 normalized. The output of each of the first 29 layers
of the pretrained VGG-16 model are shown in Figure 8. The initial layers
extract features such as edges and texture, while the later layers extract
higher level information such as eyes and mouths.

We trained the model using the Content Masked Loss (Equation 5) in the reward
function using various layers from the VGG-16 model. After the models were
trained, the painting process for each model was tested in Figure 9. The lower
level layers produced models that focused more broadly on the subjects face
while higher layers were focused on abstract features such as eyes. All models
performed very similar in their final results, however, the intermediate
strokes varied. The models that used latter layers performed more human-like
since they focused on the high level features of the image.

Layer 17 was chosen for future experiments since it was a good balance between
using high and low level features.

### Final Painting Quality

We wanted to test whether there was a difference in quality of paintings
amongst the models trained with different reward functions. We used both the
Fréchet Inception Distance (FID) (Heusel et al. 2017) and Inception Score
(Salimans et al. 2016). These measures have known issues (Barratt and Sharma
2018) such as using the metric on data that is not from the ImageNet (Deng et
al. 2009) dataset, however, most of the problems occur when comparing the
Inception Scores of vastly different models. Since we are merely comparing
reward functions and the models have otherwise been trained in the exact same
fashion, we can use these scores for comparison.

We computed the FID and Inception Scores for 2000 held out images from the
CelebA dataset. The FID and Inception Scores are shown in Table 1. They were
computed using 5 fold cross validation on 2000 held out images from the CelebA
dataset. We note that both FID and IS scores from our experiments seem far
outside the normal range of those scores found in GANs literature (Ostrovski,
Dabney, and Munos 2018); the reason for this is that the generated output in
our case are paintings that are visually very different from photorealistic
input images as in other works. While the values reported in this paper are
low compared to those from GANs, we still see a significant difference in
quality amongst the different models.

Loss Function | FID | IS
---|---|---
GAN | 240.05 $\pm$ 0.43 | 3.05 $\pm$ .08
L2 | 241.02 $\pm$ 0.24 | 3.05 $\pm$ .14
CM + L2 | 242.67 $\pm$ 0.24 | 3.01 $\pm$ .04
L1* | 241.58 $\pm$ 0.14 | 3.45 $\pm$ .09
CM + L1* | 243.13 $\pm$ 0.20 | 3.47 $\pm$ .05
Table 1: A small Fréchet Inception Distance (FID shown in column 2) indicates
that the generated paintings are visually similar to the photographs. The
larger the Inception Score (IS shown in column 3), the more similar the
distributions of the paintings and target images are.

### Human-Like Planning

Figure 10: The painting process for models trained using different loss
functions in their reward functions.

As a human painter paints, the subject of the painting should be apparent per
the common “blocking-in” (Scott 2017) technique. As seen in Figure 10, the
loss function used to train the painter model affects the intermediate outputs
of the model. For instance, the GAN, $L1^{*}$, and $L2$ Loss models show that
the painting model is not influenced by the content in the target image. The
CM + L2 and CM + L1* models add incentive to paint regions of the image that
are important for understanding the content of the image, and so observers can
recognize what the model is painting early in the stroke sequence.

We hypothesize that our model, aiming at a human-like planning, produces
stroke sequences that can be recognized from early strokes. To verify this
hypothesis, we conduct two experiments: first, we use a facial detection AI
model on the canvas as the model painted; and second, we ran a study on Amazon
Mechanical Turk for human evaluation.

We note on the difference between AI and human perception. In general, humans
tend to focus on shape-based features in recognizing objects, whereas
Convolutional Neural Networks including FaceNet (Schroff, Kalenichenko, and
Philbin 2015) used in our experiment exhibit strong texture biases (Geirhos et
al. 2019). Due to the nature of binary classification used in the experiment,
the two experiments are not designed in the identical format, i.e., binary
classification vs. ranking; however, the results agree that at early stage of
under 200 strokes the proposed approach generates paintings where the subject
is more easily recognizable when compared to the baseline approaches.

We tested the following five models, each varying with only the loss function
used to compute the reward:

  * •

GAN - Adversarial Loss. Equivalent to (Huang, Heng, and Zhou 2019) but with
brush stroke constraints (Equation 2).

  * •

L2 - $L_{2}$ Loss (Equation 3).

  * •

L1* - $L_{1}$ with Clipping Loss (Equation 6).

  * •

CM + L2 - Content Masked $L_{2}$ Loss (Equation 5).

  * •

CM + L1* - Content Masked, $L_{1}$ with Clipping Loss (Equation 7).

Figure 11: The proportion of paintings produced by each model that had faces
detected by a model (Schroff, Kalenichenko, and Philbin 2015) within the
specified number of brush strokes.

#### AI evaluation.

In our AI test, each model painted 2000 portraits from a subset of data held
out from training. After each brush stroke, the painting was tested by the
FaceNet facial detection model. The proportion of paintings with detected
faces within a certain number of strokes is plotted in Figure 11. Adding
content masking generally improved facial detection in early strokes (50-200),
although Content Masking’s effect on L2 was not strong, likely due to the
color bias concealing it. The proposed CM + L1* model produced the most face
detected paintings.

#### Human evaluation.

Each model painted the images stroke by stroke. We showed the workers the
canvases produced from each of the five models at various points in the
painting process: 10, 30, 100, 200, and 750 strokes. An example of what the
Mechanical Turk workers saw in the study is shown in Figure 12. The order of
algorithms was randomized, as was the order of the number of strokes in each
image. 332 unique MTurk workers evaluated images. 400 images were used for the
paintings, and each question (sample questions are shown in Figure 12) was
evaluated by 4 different workers.

Figure 12: Example of questions in a HIT in our study carried out on Amazon
MTurk. Workers viewed paintings by each of the models trained with different
loss functions and selected the painting that looked most like a face.

The results of the study are shown in Figure 13. Adding Content Masking to L1*
loss improved the face-like qualities of the paintings that contained between
30 and 200 brush strokes. Adding Content Masking to L2 did not significantly
improve the face-like qualities of the paintings, and we suspect that this is
because of the dark color bias since L1, which is less affected by a color
bias, with Content Masking was successful. Overall, Content Masking with L1
loss proves to create the painter model that produces the most face-like
paintings through the painting process.

Figure 13: Results from the MTurk study. Workers chose which painting
(performed using 10, 30, 100, 200, or 750 brush strokes) looks most like a
face given five paintings from each model.

## Conclusion and Future Work

This paper presents a reinforcement learning approach towards a human-like
brush stroke planning, focusing on the procedure of the painting in addition
to the final quality. Experimental results from both AI and human evaluations
show that adding Content Masking to the loss functions greatly improves the
facial detection abilities of the model’s stroke sequence, without sacrificing
the quality of the final painting results. Content Masked Loss provides a
data-efficient way to increase the human-like abilities of the model’s brush
stroke sequence without needing additional, expensive human labeling.

We found that the features generated by the VGG-16 object detection model
correlate with facial features as seen in Figure 8 which allowed us to use
these features to weight the loss in Content Masking. In future work, in order
to address the texture bias issue prevalent in CNN-based perception models, we
plan to explore using more robust object classifiers as tools for producing
the weight matrix in Content Masking that may correlate better with human
evaluation.

## Acknowledgements

We thank Zhewei Huang, Wen Heng, and Shuchang Zhou who made their code
(https://github.com/hzwer/ICCV2019-LearningToPaint) open source, allowing us
to modify it for this paper.

Thank you to Nicholas Eisley (http://neisley.squarespace.com/) for the
photographs used in Figures 1, 3, 6, 7, and 10.

## References

  * Barratt and Sharma (2018) Barratt, S.; and Sharma, R. 2018.  A Note on the Inception Score.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.; Kai Li; and Li Fei-Fei. 2009\.  ImageNet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , 248–255.
  * DiPaola (2007) DiPaola, S. 2007.  Painterly rendered portraits from photographs using a knowledge-based approach.  In Rogowitz, B. E.; Pappas, T. N.; and Daly, S. J., eds., _Human Vision and Electronic Imaging XII_ , volume 6492, 24 – 33. International Society for Optics and Photonics, SPIE.  doi:10.1117/12.706594.  URL https://doi.org/10.1117/12.706594.
  * Elgammal et al. (2017) Elgammal, A. M.; Liu, B.; Elhoseiny, M.; and Mazzone, M. 2017.  CAN: Creative Adversarial Networks, Generating ”Art” by Learning About Styles and Deviating from Style Norms.  _CoRR_ abs/1706.07068.  URL http://arxiv.org/abs/1706.07068.
  * Ganin et al. (2018) Ganin, Y.; Kulkarni, T.; Babuschkin, I.; Eslami, S. M. A.; and Vinyals, O. 2018\.  Synthesizing Programs for Images using Reinforced Adversarial Learning.  _CoRR_ abs/1804.01118.  URL http://arxiv.org/abs/1804.01118.
  * Geirhos et al. (2019) Geirhos, R.; Rubisch, P.; Michaelis, C.; Bethge, M.; Wichmann, F. A.; and Brendel, W. 2019.  ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness.  In _International Conference on Learning Representations_.  URL https://openreview.net/forum?id=Bygh9j09KX.
  * Ha and Eck (2017) Ha, D.; and Eck, D. 2017.  A Neural Representation of Sketch Drawings.  _CoRR_ abs/1704.03477.  URL http://arxiv.org/abs/1704.03477.
  * Ha and Schmidhuber (2018) Ha, D.; and Schmidhuber, J. 2018.  Recurrent World Models Facilitate Policy Evolution.  _CoRR_ abs/1809.01999.  URL http://arxiv.org/abs/1809.01999.
  * Hertzmann (2003) Hertzmann, A. 2003.  A Survey of Stroke-Based Rendering.  _IEEE Computer Graphics and Applications_ 23(4): 70–81.  doi:http://doi.ieeecomputersociety.org/10.1109/MCG.2003.1210867.  Special Issue on Non-Photorealistic Rendering.
  * Heusel et al. (2017) Heusel, M.; Ramsauer, H.; Unterthiner, T.; Nessler, B.; Klambauer, G.; and Hochreiter, S. 2017.  GANs Trained by a Two Time-Scale Update Rule Converge to a Nash Equilibrium.  _CoRR_ abs/1706.08500.  URL http://arxiv.org/abs/1706.08500.
  * Huang, Heng, and Zhou (2019) Huang, Z.; Heng, W.; and Zhou, S. 2019.  Learning to Paint with Model-based Deep Reinforcement Learning.  _CoRR_ abs/1903.04411.  URL http://arxiv.org/abs/1903.04411.
  * Lillicrap et al. (2016) Lillicrap, T. P.; Hunt, J. J.; Pritzel, A.; Heess, N.; Erez, T.; Tassa, Y.; Silver, D.; and Wierstra, D. 2016.  Continuous control with deep reinforcement learning.  In Bengio, Y.; and LeCun, Y., eds., _ICLR_.  URL http://dblp.uni-trier.de/db/conf/iclr/iclr2016.html#LillicrapHPHETS15.
  * Nakano (2019) Nakano, R. 2019.  Neural Painters: A learned differentiable constraint for generating brushstroke paintings.  _CoRR_ abs/1904.08410.  URL http://arxiv.org/abs/1904.08410.
  * Ostrovski, Dabney, and Munos (2018) Ostrovski, G.; Dabney, W.; and Munos, R. 2018.  Autoregressive Quantile Networks for Generative Modeling.  _CoRR_ abs/1806.05575.  URL http://arxiv.org/abs/1806.05575.
  * Salimans et al. (2016) Salimans, T.; Goodfellow, I. J.; Zaremba, W.; Cheung, V.; Radford, A.; and Chen, X. 2016.  Improved Techniques for Training GANs.  _CoRR_ abs/1606.03498.  URL http://arxiv.org/abs/1606.03498.
  * Schroff, Kalenichenko, and Philbin (2015) Schroff, F.; Kalenichenko, D.; and Philbin, J. 2015.  FaceNet: A unified embedding for face recognition and clustering.  In _CVPR_ , 815–823. IEEE Computer Society.  ISBN 978-1-4673-6964-0.  URL http://dblp.uni-trier.de/db/conf/cvpr/cvpr2015.html#SchroffKP15.
  * Scott (2017) Scott, D. 2017.  Blocking In URL https://drawpaintacademy.com/blocking-in/.
  * Simonyan and Zisserman (2015) Simonyan, K.; and Zisserman, A. 2015.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  In _International Conference on Learning Representations_.
  * Xie, Hachiya, and Sugiyama (2012) Xie, N.; Hachiya, H.; and Sugiyama, M. 2012.  Artist Agent: A Reinforcement Learning Approach to Automatic Stroke Generation in Oriental Ink Painting.  _CoRR_ abs/1206.4634.  URL http://arxiv.org/abs/1206.4634.
  * Zheng, Jiang, and Huang (2019) Zheng, N.; Jiang, Y.; and Huang, D. 2019.  StrokeNet: A Neural Painting Environment.  In _International Conference on Learning Representations_.  URL https://openreview.net/forum?id=HJxwDiActX.