# Potential Function-based Framework for Making the Gradients Small in Convex
and Min-Max Optimization††thanks: This research was partially supported by the
NSF grant CCF-2007757 and by the Office of the Vice Chancellor for Research
and Graduate Education at the University of Wisconsin–Madison with funding
from the Wisconsin Alumni Research Foundation. Part of this research was done
while PW was attending UW-Madison as part of the Visiting International
Student Program (VISP).

Jelena Diakonikolas
Department of Computer Sciences
University of Wisconsin-Madison
<EMAIL_ADDRESS>Puqian Wang
School of Mathematics
Shandong University
<EMAIL_ADDRESS>
###### Abstract

Making the gradients small is a fundamental optimization problem that has
eluded unifying and simple convergence arguments in first-order optimization,
so far primarily reserved for other convergence criteria, such as reducing the
optimality gap. We introduce a novel potential function-based framework to
study the convergence of standard methods for making the gradients small in
smooth convex optimization and convex-concave min-max optimization. Our
framework is intuitive and it provides a lens for viewing algorithms that make
the gradients small as being driven by a trade-off between reducing either the
gradient norm or a certain notion of an optimality gap. On the lower bounds
side, we discuss tightness of the obtained convergence results for the convex
setup and provide a new lower bound for minimizing norm of cocoercive
operators that allows us to argue about optimality of methods in the min-max
setup.

##  1 Introduction

One of the most basic facts in convex optimization is that a differentiable
convex function attains its minimum at a point where its gradient equals zero,
provided such a point exists. Thus, it is tempting to conclude that there is
no difference between minimizing the function value or its gradient (in any
suitable norm). This is only partially true, as we are almost never guaranteed
to find a point at which the function is minimized; instead, we opt for a more
modest goal of approximating such points. As it turns out, from an algorithmic
point of view, there are major differences between guarantees provided for the
function value (or optimality gap) and norm of its gradient.

Much of the standard optimization literature on smooth (gradient-Lipschitz)
convex first-order optimization has been concerned with providing guarantees
for the optimality gap. There is comparatively much less work on guarantees
for the norm of the gradient, most of it being initiated after the work of
Nesterov [41], which argued that such guarantees are natural and more
informative than those based on the function value for certain linearly
constrained optimization problems that frequently arise in applications.
Further, unlike the optimality gap, which would require knowledge of the
minimum function value to be usable as a stopping criterion, the norm of the
gradient is readily available to the algorithm as a stopping criterion, as
standard first-order methods define their iterates based on the gradient
information. This insight is particularly useful for the design of parameter-
free algorithms (i.e., algorithms that do not require knowledge of function
parameters such as smoothness, strong convexity, or sharpness/constants of
Łojasiewicz inequality; see, e.g., [36, 37, 11, 5]), and as such has been used
to design parameter-free algorithms that are near-optimal in terms of
iteration complexity (i.e., optimal up to poly-logarithmic factors) [42, 35,
25].

As for $L$-smooth functions the norm of the gradient can be bounded above as a
function of the optimality gap $f(\bm{x})-f(\bm{x}^{*}),$ where
$\bm{x}^{*}\in\operatorname*{argmin}_{\bm{x}}f(\bm{x})$, using

$\frac{1}{2L}\|\nabla f(\bm{x})\|^{2}\leq f(\bm{x})-f(\bm{x}^{*}),$ (1.1)

it is not surprising that convergence rates can be established for gradient
norm minimization. What _is_ surprising, however, is that those rates can be
faster than what is implied by Eq. (1.1) and existing results for convergence
in function value/optimality gap. In particular, methods that are optimal in
terms of iteration complexity for minimizing the optimality gap are not
necessarily optimal for gradient norm optimization, and vice-versa. More
specifically, the fast gradient method (FGM) of Nesterov [44] is iteration
complexity-optimal for minimizing the optimality gap, but it is suboptimal for
minimizing the gradient norm [27, 13].

More generally, the existing literature has not yet shed light on what is the
basic mechanism that drives algorithms for gradient norm minimization. The
only known iteration complexity-optimal algorithm for minimizing norm of the
gradient of a smooth convex function is due to Kim and Fessler [28].111The
optimality of the algorithm can be certified using the lower bound from [13].
This algorithm was obtained by using the performance estimation framework of
Drori and Teboulle [20], originally developed for understanding the worst-case
performance of optimization algorithms. The algorithm [28] itself and its
convergence analysis are inferred from numerical solutions to a semidefinite
program (SDP). As such, the intuition behind what is driving the convergence
analysis of the algorithm and how the improved convergence rate is obtained is
lacking, which constitutes an impediment to possibly generalizing this
algorithm to other optimization settings.

Even less is known in the setting of smooth convex-concave min-max
optimization, where (near-)optimal convergence results have been established
only recently [15, 26, 33, 48] and the problem has been much less studied from
the aspect of oracle lower bounds [46, 15, 22]. In particular, similar as in
the case of convex optimization, classical methods for min-max optimization
that are optimal for reducing the primal-dual gap, such as, e.g., the
extragradient method [29], mirror-prox [39], and dual extrapolation [40], are
suboptimal in terms of iteration complexity for minimizing the gradient norm.
Interestingly, however, the methods that turn out to be (near-)optimal were
originally studied in the context of fixed point iterations [30, 38, 23].

In this paper, we introduce a novel potential function-based framework to
study the convergence in gradient norm for smooth convex and convex-concave
optimization problems. Our framework is intuitive, as it relies on
establishing convergence of standard methods by interpreting it as a trade-off
between reducing the gradient norm and reducing a notion of an optimality gap.
The same view can be adopted in a unifying manner for methods such as standard
gradient descent, Nesterov FGM [44], optimized method of Kim and Fessler [28],
gradient descent-ascent (which is equivalent to Krasnosel’skiı-Mann iteration
[30, 38]; see Section 3.1), and Halpern iteration [23]. We further complement
these results with a discussion of optimality of the considered methods for
convex optimization, and with a new lower bound for minimizing the norm of
cocoercive operators (see Section 1.2 for a precise definition and
relationship to min-max optimization), which allows us to discuss optimality
of gradient descent-ascent and Halpern iteration as methods for minimizing the
gradient norm in smooth convex-concave min-max optimization.

###  1.1 Further Related Work

Understanding the phenomenon of acceleration and providing a unifying theory
of first-order optimization algorithms has been an important topic in
optimization research, with a flurry of recent research activity in this area
[55, 1, 4, 7, 53, 56, 57, 59, 50, 31, 49, 12, 21, 34, 10, 18, 19, 8, 24, 32,
51, 17, 6]. However, the existing literature has almost exclusively focused on
the optimality gap guarantees, with only a small subset of results seeking to
provide guarantees for gradient norm and primarily addressing FGM-type
algorithms with suboptimal rates [17, 50, 6].

Complementary to the literature discussed above, whose focus has been on
deriving intuitive convergence analysis frameworks, another line of work has
focused on using the SDP-based performance estimation framework of Drori and
Teboulle [20] to investigate the worst-case performance of optimization
algorithms [27, 26, 28, 33, 14, 54]. Most relevant to our work among these
results are: [27], which investigated the worst-case performance of FGM-type
methods in terms of gradient norm minimization, [28], which obtained the first
(and so far, the only) iteration complexity-optimal algorithm for minimizing
the gradient norm of smooth convex functions, and [33], which obtained a tight
worst-case convergence bound for Halpern iteration. While the SDP-based
approach used in this line of work is useful for understanding the worst-case
performance of existing algorithms (and even obtaining new algorithms [28]),
its downside is that, because the convergence arguments are computer-assisted
(namely, they are inferred from numerical solutions to SDPs), they are
generally not suitable for developing intuition about what is driving the
methods and their analysis. Our work fills this gap by providing intuitive
convergence proofs based on potential function arguments.

###  1.2 Notation and Preliminaries

Throughout the paper, we consider the Euclidean space
$(\mathbb{R}^{d},\|\cdot\|),$ where
$\|\cdot\|=\sqrt{\left\langle\cdot,\cdot\right\rangle}$ is the Euclidean norm
and $\left\langle\cdot,\cdot\right\rangle$ denotes any inner product on
$\mathbb{R}^{d}$. We use $\\{A_{k}\\}_{k\geq 0}$ and $\\{B_{k}\\}_{\geq 0}$ to
denote sequences of nondecreasing nonnegative numbers, and define
$a_{0}=A_{0},$ $a_{k}=A_{k}-A_{k-1}$ for $k\geq 1,$ and, similarly,
$b_{0}=B_{0},$ $b_{k}=B_{k}-B_{k-1}$ for $k\geq 1.$

We consider two main problem setups: (i) making the gradients small in convex
optimization, and (ii) making the gradients small in min-max optimization.

##### Convex optimization.

In the first setup, we assume we are given first-order oracle access to a
convex continuously differentiable function $f:\mathbb{R}^{d}\to\mathbb{R}.$
The first-order definition of convexity then applies, and we have:

$(\forall\bm{x},\bm{y}\in\mathbb{R}^{d}):\quad f(\bm{y})\geq
f(\bm{x})+\left\langle\nabla f(\bm{x}),\bm{y}-\bm{x}\right\rangle.$

We further assume that $f$ is $L$-smooth, i.e., that its gradients are
$L$-Lipschitz continuous:

$(\forall\bm{x},\bm{y}\in\mathbb{R}^{d}):\quad\|\nabla f(\bm{x})-\nabla
f(\bm{y})\|\leq L\|\bm{x}-\bm{y}\|.$

Recall that smoothness of $f$ implies:

$(\forall\bm{x},\bm{y}\in\mathbb{R}^{d}):\quad f(\bm{y})\leq
f(\bm{x})+\left\langle\nabla
f(\bm{x}),\bm{y}-\bm{x}\right\rangle+\frac{L}{2}\|\bm{y}-\bm{x}\|^{2}.$ (1.2)

The goal of the first setup is to, given $\epsilon>0,$ construct a point
$\bm{x}$ such that $\|\nabla f(\bm{x})\|\leq\epsilon$ in as few iterations
(oracle queries to the gradient of $f$) as possible. A useful fact that turns
out to be crucial for the analysis in the convex case is the following (see,
e.g., [58, Section 3.5]).

######  Fact 1.1.

A continuously differentiable function $f:\mathbb{R}^{d}\to\mathbb{R}$ is
$L$-smooth and convex if and only if

$(\forall\bm{x},\bm{y}\in\mathbb{R}^{d}):\quad\frac{1}{2L}\|\nabla
f(\bm{y})-\nabla f(\bm{x})\|^{2}\leq f(\bm{y})-f(\bm{x})-\left\langle\nabla
f(\bm{x}),\bm{y}-\bm{x}\right\rangle.$ (1.3)

Observe that Fact 1.1 fully characterizes the class of smooth convex
functions, and, as such, should be sufficient for analyzing any algorithm that
addresses problems from this class. An immediate consequence of Fact 1.1 is
that the gradient of a smooth convex function is cocoercive, i.e.,

$\left\langle\nabla f(\bm{x})-\nabla
f(\bm{y}),\bm{x}-\bm{y}\right\rangle\geq\frac{1}{L}\|\bm{x}-\bm{y}\|^{2}.$
(1.4)

##### Min-max optimization.

In the second setup, we are given oracle access to gradients of a function
$\phi:\mathbb{R}^{d_{1}}\times\mathbb{R}^{d_{2}}\to\mathbb{R}$, where
$d_{1}+d_{2}=d.$ Function $\phi(\bm{x},\bm{y})$ is assumed to be convex-
concave: convex in the first argument ($\bm{x}$) when the second argument
($\bm{y}$) is fixed and concave in the second argument ($\bm{y}$) when the
first argument ($\bm{x}$) is fixed, for any values of $\bm{x},\bm{y}$. Similar
to the case of convex optimization, the goal in this case is, given
$\epsilon>0,$ to find a pair of points
$(\bm{x},\bm{y})\in\mathbb{R}^{d_{1}}\times\mathbb{R}^{d_{2}}$ such that
$\|\nabla\phi(\bm{x},\bm{y})\|\leq\epsilon$ in as few iterations (oracle
queries to the gradient of $\phi$) as possible.

We consider the problem of minimizing the norm of the gradient of $\phi$ as
the problem of minimizing the norm of the operator
$F(\bm{u})=\big{[}\vbox{\Let@\restore@math@cr\default@tag\halign{\hfil$\m@th\scriptstyle#$&$\m@th\scriptstyle{}#$\hfil\cr\nabla_{\bm{x}}\phi(\bm{x},\bm{y})\\\
-\nabla_{\bm{y}}\phi(\bm{x},\bm{y})\crcr}}\big{]},$ where
$\bm{u}=\big{[}\vbox{\Let@\restore@math@cr\default@tag\halign{\hfil$\m@th\scriptstyle#$&$\m@th\scriptstyle{}#$\hfil\cr\bm{x}\\\
\bm{y}\crcr}}\big{]}.$ When $\phi$ is convex-concave, $F$ is monotone, i.e.,
it holds

$(\forall\bm{u},\bm{v}\in\mathbb{R}^{d}):\quad\left\langle
F(\bm{u})-F(\bm{v}),\bm{u}-\bm{v}\right\rangle\geq 0.$ (1.5)

We will assume throughout that $F$ is $\frac{1}{L}$-cocoercive, i.e., that

$(\forall\bm{u},\bm{v}\in\mathbb{R}^{d}):\quad\left\langle
F(\bm{u})-F(\bm{v}),\bm{u}-\bm{v}\right\rangle\geq\frac{1}{L}\|F(\bm{u})-F(\bm{v})\|^{2}.$
(1.6)

Cocoercivity of $F$ implies that it is monotone and $L$-Lipschitz. The
opposite does not hold in general, unless $F$ is the gradient of a smooth
convex function (as we saw in the case of convex optimization described
earlier). Nevertheless, cocoercivity is sufficient to capture the main
algorithmic ideas of smooth min-max optimization, and the extensions to
general smooth min-max optimization are possible through the use of
approximate resolvent operators (see, e.g., [15]). Further, it suffices to
consider unconstrained problems, as extensions to constrained optimization
problems are possible in a straightforward manner using a notion of _operator
mapping_ (see, e.g., [15], where a similar idea was used).

We assume here that there exists a point $\bm{u}^{*}\in\mathbb{R}^{d}$ such
that $F(\bm{u}^{*})=0.$ Due to cocoercivity of $F$ (Eq. (1.6)), this
assumption implies that

$(\forall\bm{u}\in\mathbb{R}^{d}):\quad\left\langle
F(\bm{u}),\bm{u}-\bm{u}^{*}\right\rangle\geq\frac{1}{L}\|F(\bm{u})\|^{2}.$
(1.7)

It will be useful to think of $\left\langle
F(\bm{u}),\bm{u}-\bm{u}^{*}\right\rangle$ as a notion of “optimality gap” for
min-max optimization problems, as, using convexity-concavity of $\phi$, we
have

$(\forall(\bm{x},\bm{y})\in\mathbb{R}^{d_{1}}\times\mathbb{R}^{d_{2}}):\quad\phi(\bm{x},\bm{y}^{*})-\phi(\bm{x}^{*},\bm{y}^{*})+\phi(\bm{x}^{*},\bm{y}^{*})-\phi(\bm{x}^{*},\bm{y})\leq\left\langle
F(\bm{u}),\bm{u}-\bm{u}^{*}\right\rangle.$

##  2 Small Gradients in Convex Optimization

In this section, we consider the problem of minimizing norm of the gradient of
a smooth convex function. We show that all standard methods, including
standard gradient descent, fast gradient method of Nesterov [44], and the
optimized gradient method of Kim and Fessler [28], can be captured within an
intuitive potential function-based framework, where the progress of a method
is established through a trade-off between the norm of the gradient and the
optimality gap. Further, the complete convergence analysis of each of the
methods can be fully carried out using only the cocoercivity inequality from
Eq. (1.3), which fully characterizes the class of smooth convex functions.

###  2.1 Gradient Descent

As a warmup, we start by considering $L$-smooth but possibly nonconvex
objectives $f.$ In this case, all that can be said about $f$ is that its
gradients are $L$-Lipschitz, which implies Eq. (1.2). Further, for any method
that does not converge to local maxima (unless initialized at one), we cannot
hope to bound the norm of the last gradient – all that we can hope for is the
average or the minimum over all seen gradients. The simplest way to see this
is by considering the one dimensional case: if the function is locally concave
and the algorithm moves in the direction that reduces the function value, the
absolute value of the function derivative must increase.

Thus, assuming that the function is bounded below by some $f_{\star}>-\infty$,
it is natural to consider methods that in each iteration either reduce the
function value or the norm of the gradient. Such methods ensure that, $\forall
k\geq 0:$

$a_{k}\|\nabla f(\bm{x}_{k})\|^{2}+f(\bm{x}_{k+1})-f(\bm{x}_{k})\leq 0,$

or, equivalently, that the following potential function

$\mathcal{C}_{k}=\sum_{i=0}^{k}a_{i}\|\nabla
f(\bm{x}_{i})\|^{2}+f(\bm{x}_{i+1})$ (2.1)

is non-increasing, where $a_{i}$ is some sequence of positive numbers.
Equivalently, such methods ensure that $a_{k}\|\nabla
f(\bm{x}_{k})\|^{2}+f(\bm{x}_{k+1})-f(\bm{x}_{k})\leq 0,$ $\forall k\geq 0.$

As the only assumption we are making about $f$ is that it is $L$-smooth, the
most we can do to bound $f(\bm{x}_{k+1})-f(\bm{x}_{k})$ is use Eq. (1.2). The
tightest bound on $f(\bm{x}_{k+1})-f(\bm{x}_{k})$ that can be obtained from
Eq. (1.2) is attained when $\bm{x}_{k+1}=\bm{x}_{k}-\frac{1}{L}\nabla
f(\bm{x}_{k})$ (i.e., for the standard gradient descent step) and is given by
$f(\bm{x}_{k+1})-f(\bm{x}_{k})\leq-\frac{1}{2L}\|\nabla f(\bm{x}_{k})\|^{2}$,
in which case the largest $a_{k}$ we can choose is $a_{k}=\frac{1}{2L}.$ As
$\mathcal{C}_{k}$ is non-increasing, it follows that
$\mathcal{C}_{k}\leq\mathcal{C}_{0},$ and we recover the familiar convergence
bound of gradient descent:

$\frac{1}{k+1}\sum_{i=0}^{k}\|\nabla
f(\bm{x}_{i})\|^{2}\leq\frac{2L(f(\bm{x}_{0})-f(\bm{x}_{k+1}))}{k+1}\leq\frac{2L(f(\bm{x}_{0})-f_{\star})}{k+1}.$
(2.2)

When considering the case of a convex objective function $f,$ the first
question to ask is how would convexity help to improve the bound from Eq.
(2.2). The first observation to make is that Fact 1.1 fully characterizes the
class of smooth convex functions, and, thus, Eq. (1.3) should be enough to
carry out the analysis of any algorithm for smooth convex functions.

Given that the function is convex, in this case it seems reasonable to hope
that we can obtain a bound on the gradient norm at the last iterate. Thus, we
could consider a potential function of the form

$\mathcal{C}_{k}=A_{k}\|\nabla f(\bm{x}_{k})\|^{2}+f(\bm{x}_{k})$

and try enforcing the condition that $\mathcal{C}_{k}\leq\mathcal{C}_{k-1}$
for $A_{k}$ that grows as fast as possible with the iteration count $k.$ This
approach precisely gives the bound $\|\nabla
f(\bm{x}_{k})\|^{2}\leq\frac{2L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{2k+1},$ which is
tight (see, e.g., [28, Lemma 5.2]).

######  Lemma 2.1 (Convergence of Gradient Descent).

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be an $L$-smooth function that attains its
minimum on $\mathbb{R}^{d}$ and let
$\bm{x}^{*}\in\operatorname*{argmin}_{\bm{x}\in\mathbb{R}^{d}}f(\bm{x})$. Let
$\bm{x}_{0}\in\mathbb{R}^{d}$ be an arbitrary initial point and assume that
the sequence $\\{\bm{x}_{k}\\}_{k\geq 0}$ evolves according to the standard
gradient descent, i.e., $\bm{x}_{k+1}=\bm{x}_{k}-\frac{1}{L}\nabla
f(\bm{x}_{k}),$ $\forall k\geq 0$. Then

$\mathcal{C}_{k}=\frac{k}{L}\|\nabla f(\bm{x}_{k})\|^{2}+f(\bm{x}_{k})$

is non-increasing with $k,$ and we can conclude that, $\forall k\geq 0$

$\|\nabla
f(\bm{x}_{k})\|^{2}\leq\frac{2L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{2k+1}.$

###### Proof.

We start by showing that $\mathcal{C}_{k+1}\leq\mathcal{C}_{k},$ $\forall
k\geq 0.$ By the definition of $\mathcal{C}_{k},$

$\mathcal{C}_{k+1}-\mathcal{C}_{k}\leq\frac{k+1}{L}\|\nabla
f(\bm{x}_{k+1})\|^{2}-\frac{k}{L}\|\nabla
f(\bm{x}_{k})\|^{2}+f(\bm{x}_{k+1})-f(\bm{x}_{k}).$

Applying Fact 1.1 with $\bm{x}=\bm{x}_{k+1}=\bm{x}_{k}-\frac{1}{L}\nabla
f(\bm{x}_{k})$ and $\bm{y}=\bm{x}_{k}$, it follows that
$f(\bm{x}_{k+1})-f(\bm{x}_{k})\leq-\frac{1}{2L}\|\nabla
f(\bm{x}_{k+1})\|^{2}-\frac{1}{2L}\|\nabla f(\bm{x}_{k})\|^{2},$ and, thus

$\mathcal{C}_{k+1}-\mathcal{C}_{k}\leq\frac{2k+1}{2L}\|\nabla
f(\bm{x}_{k+1})\|^{2}-\frac{2k+1}{2L}\|\nabla f(\bm{x}_{k})\|^{2}.$

To complete the proof that $\mathcal{C}_{k+1}\leq\mathcal{C}_{k},$ it remains
to argue that $\|\nabla f(\bm{x}_{k+1})\|\leq\|\nabla f(\bm{x}_{k})\|,$
$\forall k\geq 0.$ This is clearly true if $\|\nabla f(\bm{x}_{k+1})\|=0,$ so
assume $\|\nabla f(\bm{x}_{k+1})\|\neq 0$. Applying Eq. (1.6) with
$\bm{x}=\bm{x}_{k+1}=\bm{x}_{k}-\frac{1}{L}\nabla f(\bm{x}_{k})$,
$\bm{y}=\bm{x}_{k}$, and simplifying, it follows that:

$\|\nabla f(\bm{x}_{k+1})\|^{2}\leq\left\langle\nabla f(\bm{x}_{k+1}),\nabla
f(\bm{x}_{k})\right\rangle\leq\|\nabla f(\bm{x}_{k+1})\|\|\nabla
f(\bm{x}_{k})\|,$

where the last inequality is by Cauchy-Schwarz. To conclude that $\|\nabla
f(\bm{x}_{k+1})\|\leq\|\nabla f(\bm{x}_{k})\|,$ it remains to divide both
sides of the last inequality by $\|\nabla f(\bm{x}_{k+1})\|.$

From the first part of the proof, it follows that
$\mathcal{C}_{k}\leq\mathcal{C}_{0},$ and, thus

$\frac{k}{L}\|\nabla f(\bm{x}_{k})\|^{2}\leq
f(\bm{x}_{0})-f(\bm{x}_{k})=f(\bm{x}_{0})-f(\bm{x}^{*})+f(\bm{x}^{*})-f(\bm{x}_{k}).$

It remains to observe that
$f(\bm{x}^{*})-f(\bm{x}_{k})\leq-\frac{1}{2L}\|\nabla f(\bm{x}_{k})\|^{2},$
which follows by applying Fact 1.1 with $\bm{x}=\bm{x}^{*},$
$\bm{y}=\bm{x}_{k}$, and rearrange. ∎

###  2.2 Methods that are Faster than Gradient Descent

The potential functions we have seen so far (for gradient descent) trade off
the gradient norm (squared) with the function value. Equivalently, we can view
them as trading off the gradient norm with the optimality gap
$f(\bm{x}_{k})-f(\bm{x}^{*}),$ as $f(\bm{x}^{*})$ would cancel out in the
analysis and the same argument would go through.

It is reasonable to ask whether we can obtain faster algorithms by using a
different trade off, say, by considering potential functions of the form
$\mathcal{C}_{k}=A_{k}\|\nabla
f(\bm{x}_{k})\|^{2}+B_{k}(f(\bm{x}_{k})-f(\bm{x}^{*}))$ or
$\mathcal{C}_{k}=\sum_{i=0}^{k}a_{i}\|\nabla
f(\bm{x}_{i})\|^{2}+B_{k}(f(\bm{x}_{k})-f(\bm{x}^{*})),$ where $B_{k}$ is some
positive function of the iteration count $k$.

Observe that for non-constant $B_{k},$ one way or another, we would need to
account for $\bm{x}^{*},$ which is not known to the algorithm. However, there
are at least two ways around this issue. The first one is to utilize Eq. (1.3)
to bound below $f(\bm{x}^{*})$. This approach does not lead to the optimal
iteration complexity, but improves the overall bound compared to gradient
descent and recovers a variant of Nesterov FGM. The second approach is to
replace the optimality gap with a gap to some reference point. In particular,
as we show below, optimized gradient method [28] can be viewed as using the
final point of the algorithm $\bm{x}_{N}$ as the reference (or anchor) point.

####  2.2.1 Fast Gradient Method

We start by considering a potential function that offers a different trade-off
between the norm of the gradient and the optimality gap, defined by

$\mathcal{C}_{k}=\sum_{i=0}^{k-1}a_{i}\|\nabla
f(\bm{x}_{i})\|^{2}+B_{k}(f(\bm{x}_{k})-f(\bm{x}^{*})),$ (2.3)

where $a_{i}>0,$ $\forall i\geq 0$ and the sequence of scalars $B_{k}>0$,
$\forall k\geq 0$, is strictly increasing. We also define
$b_{k}=B_{k}-B_{k-1}>0.$ By convention, the summation from $i$ to $j$ where
$j<i$ is taken to be zero. Observe that

$\mathcal{C}_{0}=B_{0}(f(\bm{x}_{0})-f(\bm{x}^{*})).$ (2.4)

While, in principle, one could also consider $\mathcal{C}_{k}=A_{k}\|\nabla
f(\bm{x}_{k})\|^{2}+B_{k}(f(\bm{x}_{k})-f(\bm{x}^{*}))$ hoping to obtain a
bound on the last gradient, it is not clear that such a bound is even possible
for non-constant $B_{k}$ (see Section 2.3).

We first show that there is a natural algorithm that ensures
$\mathcal{C}_{k+1}-\mathcal{C}_{k}\leq E_{k},$ $\forall k\geq 0$, where
$E_{k}$ contains only telescoping terms. As it turns out, this algorithm is
precisely Nesterov FGM.

######  Lemma 2.2.

Given an arbitrary initial point $\bm{x}_{0}\in\mathbb{R}^{d}$, assume that
for $k\geq 1,$ the sequence $\bm{x}_{k}$ is updated as

$\begin{gathered}\bm{x}_{k}=\frac{B_{k-1}}{B_{k}}\Big{(}\bm{x}_{k-1}-\frac{1}{L}\nabla
f(\bm{x}_{k-1})\Big{)}+\frac{b_{k}}{B_{k}}\bm{v}_{k},\end{gathered}$ (2.5)

where $\bm{v}_{k}$ is defined recursively via
$\bm{v}_{k}=\bm{v}_{k-1}-\frac{b_{k-1}}{L}\nabla f(\bm{x}_{k-1})$ with
$\bm{v}_{0}=\bm{x}_{0}$. If ${b_{k}}^{2}\leq B_{k}$ and
$a_{k-1}\leq\frac{B_{k-1}}{2L},$ then
$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\frac{L}{2}\big{(}\|\bm{x}^{*}-\bm{v}_{k}\|^{2}-\|\bm{x}^{*}-\bm{v}_{k+1}\|^{2}\big{)},$
$\forall k\geq 1,$ where $\mathcal{C}_{k}$ is defined by Eq. (2.3).

###### Proof.

Given $k\geq 1,$ by definition of $\mathcal{C}_{k},$ we have

$\mathcal{C}_{k}-\mathcal{C}_{k-1}=a_{k-1}\|\nabla
f(\bm{x}_{k-1})\|^{2}+B_{k}f(\bm{x}_{k})-B_{k-1}f(\bm{x}_{k-1})-b_{k}f(\bm{x}^{*}).$
(2.6)

Since $f(\bm{x}^{*})$ is not known to the algorithm and we are trying to bound
$\mathcal{C}_{k}-\mathcal{C}_{k-1}$ above, it appears natural to use Eq. (1.3)
to bound $f(\bm{x}^{*})$ below. In particular, we have:

$f(\bm{x}^{*})\geq f(\bm{x}_{k})+\left\langle\nabla
f(\bm{x}_{k}),\bm{x}^{*}-\bm{x}_{k}\right\rangle+\frac{1}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}.$ (2.7)

On the other hand, the difference $f(\bm{x}_{k})-f(\bm{x}_{k-1})$ can be
bounded above using, again, Eq. (1.3), as follows.

$\displaystyle f(\bm{x}_{k})-f(\bm{x}_{k-1})\leq$
$\displaystyle\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{x}_{k-1}+\frac{1}{L}\nabla
f(\bm{x}_{k-1})\right\rangle$ (2.8) $\displaystyle-\frac{1}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}-\frac{1}{2L}\|\nabla f(\bm{x}_{k-1})\|^{2}.$

Combining Eq. (2.7) and Eq. (2.8) with Eq. (2.6), we have:

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq$
$\displaystyle-\frac{B_{k}}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}+\Big{(}a_{k-1}-\frac{B_{k-1}}{2L}\Big{)}\|\nabla
f(\bm{x}_{k-1})\|^{2}$ (2.9) $\displaystyle+B_{k-1}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{x}_{k-1}+\frac{1}{L}\nabla
f(\bm{x}_{k-1})\right\rangle+b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{x}^{*}\right\rangle.$

Now, if $b_{k}$ were zero (constant $B_{k}$), we could simply set
$\bm{x}_{k}=\bm{x}_{k-1}-\frac{1}{L}\nabla f(\bm{x}_{k-1}),$ and we would be
recovering gradient descent and its analysis from the previous subsection. Of
course, the goal here is to get a different trade off, where $B_{k}$ is
strictly increasing.

To get a useful bound on $\mathcal{C}_{k}-\mathcal{C}_{k-1},$ we need to be
able to bound or otherwise control the term $b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{x}^{*}\right\rangle.$ Fortunately, such a term
frequently appears in the mirror-descent-type analysis, and it can be bounded
using standard arguments by defining

$\displaystyle\bm{v}_{k+1}$
$\displaystyle=\operatorname*{argmin}_{\bm{u}\in\mathbb{R}^{d}}\Big{\\{}b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{u}-\bm{v}_{k}\right\rangle+\frac{L}{2}\|\bm{u}-\bm{v}_{k}\|^{2}\Big{\\}}$
$\displaystyle=\bm{v}_{k}-\frac{b_{k}}{L}\nabla f(\bm{x}_{k}).$

Then, we have:

$\displaystyle b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{x}^{*}\right\rangle=\;$ $\displaystyle
b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{v}_{k+1}\right\rangle+L\left\langle\bm{v}_{k}-\bm{v}_{k+1},\bm{v}_{k+1}-\bm{x}^{*}\right\rangle$
$\displaystyle=\;$ $\displaystyle b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{v}_{k}\right\rangle+\frac{{b_{k}}^{2}}{L}\|\nabla
f(\bm{x}_{k})\|^{2}$
$\displaystyle+\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k}\|^{2}-\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k+1}\|^{2}-\frac{L}{2}\|\bm{v}_{k+1}-\bm{v}_{k}\|^{2}$
$\displaystyle=\;$ $\displaystyle b_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{v}_{k}\right\rangle+\frac{{b_{k}}^{2}}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}$
$\displaystyle+\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k}\|^{2}-\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k+1}\|^{2},$

where we have repeatedly used $\bm{v}_{k+1}=\bm{v}_{k}-\frac{b_{k}}{L}\nabla
f(\bm{x}_{k}).$ Combining with Eq. (2.9), we have

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\;$
$\displaystyle\frac{{b_{k}}^{2}-B_{k}}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}+\Big{(}a_{k-1}-\frac{B_{k-1}}{2L}\Big{)}\|\nabla
f(\bm{x}_{k-1})\|^{2}$
$\displaystyle+\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k}\|^{2}-\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k+1}\|^{2}$
$\displaystyle+\left\langle\nabla
f(\bm{x}_{k}),B_{k}\bm{x}_{k}-B_{k-1}\Big{(}\bm{x}_{k-1}-\frac{1}{L}\nabla
f(\bm{x}_{k-1})\Big{)}-b_{k}\bm{v}_{k}\right\rangle.$

To obtain
$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k}\|^{2}-\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{k+1}\|^{2},$
it remains to choose ${b_{k}}^{2}\leq B_{k},$ $a_{k-1}\leq\frac{B_{k-1}}{2L}$,
and $\bm{x}_{k}=\frac{B_{k-1}}{B_{k}}\big{(}\bm{x}_{k-1}-\frac{1}{L}\nabla
f(\bm{x}_{k-1})\big{)}+\frac{b_{k}}{B_{k}}\bm{v}_{k}.$ ∎

We can now use Lemma 2.2 to argue about convergence of Nesterov FGM from Eq.
(2.5). Interestingly, the result from Lemma 2.2 suffices to argue about both
convergence in function value and in norm of the gradient. The resulting
bounds are tight, up to a small absolute constant, due to numerical results
from [27].

######  Theorem 2.3 (Convergence of Fast Gradient Method).

Suppose that the assumptions of Lemma 2.2 hold, where $\bm{v}_{0}=\bm{x}_{0}.$
Then, $\forall k\geq 1$:

$f(\bm{x}_{k})-f(\bm{x}^{*})\leq\frac{2B_{0}(f(\bm{x}_{0})-f(\bm{x}^{*}))+L\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{2B_{k}}$

and

$\sum_{i=0}^{k}\frac{B_{i}}{2L}\|\nabla f(\bm{x}_{i})\|^{2}\leq
B_{0}(f(\bm{x}_{0})-f(\bm{x}^{*}))+\frac{L}{2}\|\bm{x}_{0}-\bm{x}^{*}\|^{2}.$

In particular, if $b_{0}=B_{0},$ ${b_{k}}^{2}=B_{k}$ for $k\geq 1$, and
$a_{k}=\frac{B_{k}}{2L}$, then

$f(\bm{x}_{k})-f(\bm{x}^{*})\leq\frac{4L\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{(k+1)(k+2)}$

and

$\min_{0\leq i\leq k}\|\nabla
f(\bm{x}_{i})\|^{2}\leq\frac{\sum_{i=0}^{k}{B_{i}}\|\nabla
f(\bm{x}_{i})\|^{2}}{\sum_{i=0}^{k}B_{i}}\leq\frac{18L^{2}\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{(k+1)(k+2)(k+3)}.$

###### Proof.

Applying Lemma 2.2 and the definition of $\mathcal{C}_{k},$ we have, $\forall
k\geq 1$:

$\displaystyle\mathcal{C}_{k}$
$\displaystyle\leq\mathcal{C}_{0}+\frac{L}{2}\|\bm{x}^{*}-\bm{v}_{0}\|^{2}-\frac{L}{2}\|\bm{v}_{k+1}-\bm{x}^{*}\|^{2}$
$\displaystyle\leq
B_{0}(f(\bm{x}_{0})-f(\bm{x}^{*}))+\frac{L}{2}\|\bm{x}^{*}-\bm{x}_{0}\|^{2}.$

Equivalently:

$\sum_{i=0}^{k-1}a_{i}\|\nabla
f(\bm{x}_{i})\|^{2}+B_{k}(f(\bm{x}_{k})-f(\bm{x}^{*}))\leq
B_{0}(f(\bm{x}_{0})-f(\bm{x}^{*}))+\frac{L}{2}\|\bm{x}^{*}-\bm{x}_{0}\|^{2}.$

The first part of the theorem is now immediate, as
$\sum_{i=0}^{k-1}a_{i}\|\nabla f(\bm{x}_{i})\|^{2}\geq 0$ and

$B_{k}(f(\bm{x}_{k})-f(\bm{x}^{*}))\geq\frac{B_{k}}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}\geq a_{k}\|\nabla f(\bm{x}_{k})\|^{2}.$

For the second part, we only need to bound the growth of $B_{k}$ when
${b_{k}}^{2}=(B_{k}-B_{k-1})^{2}=B_{k}.$ It is a standard result that this
growth is quadratic and at least as fast the growth resulting from choosing
$b_{k}=\frac{k+1}{2},$ $\forall k.$ Thus,
$B_{k}\geq\sum_{i=0}^{k}\frac{i+1}{2}=\frac{(k+1)(k+2)}{4}$ and
$\sum_{i=0}^{k}B_{i}\geq\frac{(k+1)(k+2)(k+3)}{12}.$ Using that
$f(\bm{x}_{0})-f(\bm{x}^{*})\leq\frac{L}{2}\|\bm{x}_{0}-\bm{x}^{*}\|^{2},$ it
now follows from the first part of the theorem that

$f(\bm{x}_{k})-f(\bm{x}^{*})\leq\frac{4L\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{(k+1)(k+2)}$

and

$\min_{0\leq i\leq k}\|\nabla
f(\bm{x}_{i})\|^{2}\leq\frac{\sum_{i=0}^{k}{B_{i}}\|\nabla
f(\bm{x}_{i})\|^{2}}{\sum_{i=0}^{k}B_{i}}\leq\frac{18L^{2}\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{(k+1)(k+2)(k+3)},$

as claimed. ∎

######  Remark 2.4.

It may not be immediately clear why the bound from Theorem 2.3 improves upon
the bound for gradient descent from Lemma 2.1, as in the former the gradient
is bounded as a function of $\|\bm{x}^{*}-\bm{x}_{0}\|^{2},$ while in the
latter it is bounded as a function of $f(\bm{x}_{0})-f(\bm{x}^{*}).$ Here, one
should note that, using the standard convergence result for the optimality gap
of gradient descent
$f(\bm{x}_{k})-f(\bm{x}^{*})=O\big{(}\frac{L\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{k}\big{)}$
and combining it with the bound from Lemma 2.1, we also have that $\|\nabla
f(\bm{x}_{k})\|^{2}=O\big{(}L(\frac{f(\bm{x}_{\lceil
k/2\rceil})-f(\bm{x}^{*}))}{k}\big{)}=O\big{(}\frac{L^{2}\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{k^{2}}\big{)}.$
Furthermore, this bound is known to be tight [27, Theorem 2], and it also
applies to $\min_{0\leq i\leq k}\|\nabla f(\bm{x}_{i})\|^{2}$, as gradient
descent monotonically decreases the gradient. We also note that the improved
bound for FGM from Theorem 2.3 can only be established for the minimum
gradient norm up to iteration $k;$ as shown numerically in [27], the bound for
the gradient of the last iterate is no better than that of gradient descent,
i.e., $\|\nabla
f(\bm{x}_{k})\|^{2}=\Omega\big{(}\frac{L^{2}\|\bm{x}_{0}-\bm{x}^{*}\|^{2}}{k^{2}}\big{)}$.

####  2.2.2 Optimized Method for the Gradients

The only known method that achieves the optimal convergence bound of the form
$\|\nabla
f(\bm{x}_{k})\|^{2}=O\big{(}\frac{L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{k^{2}}\big{)}$
is the optimized method for the gradients (OGM-G), due to Kim and Fessler
[28]. This method was obtained using the performance estimation framework
(PEP) of Drori and Teboulle [20], which relies on numerical solutions to
semidefinite programs that model the worst case performance of methods on a
given class of problems (such as, e.g., unconstrained problems with smooth
convex objective functions considered here). While this is a very powerful
approach that generally produces tight convergence analysis and worst case
instances as a byproduct, as discussed before, the intuition behind the
methods and their analysis obtained using PEP is not always clear.

In this section, we show that OGM-G naturally arises from a potential function
that fits within the broader framework studied in this paper. In particular,
as mentioned earlier in this section, we can view OGM-G as trading off the
norm of the gradient for a gap w.r.t. an anchor point, which is the last point
constructed by the algorithm. As a consequence of anchoring to the last point,
the algorithm crucially requires fixing the number of iterations in advance to
achieve the optimal convergence bound stated above.

The potential function used for analyzing OGM-G is defined by

$\mathcal{C}_{k}=A_{k}\Big{(}\frac{1}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}+\frac{1}{2L}\|\nabla
f(\bm{x}_{K})\|^{2}+f(\bm{x}_{k})-f(\bm{x}_{K})\Big{)},$ (2.10)

where $K$ is the total number of iterations for which OGM-G is invoked.

Unlike for other algorithms, we will not be able to argue that
$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq E_{k}$ for $E_{k}$ that is either zero
or only contains telescoping terms. Instead, we will settle for a more modest
goal of arguing that, under the appropriate choice of algorithm steps and
growth of the sequence $A_{k},$ we have $\mathcal{C}_{K}\leq\mathcal{C}_{0}.$
Observe that, by the definition of $\mathcal{C}_{k}$, if we can prove that
$A_{K}/A_{0}=\Omega(K^{2}),$ this condition immediately leads to the desired
bound

$\|\nabla
f(\bm{x}_{K})\|^{2}=O\Big{(}\frac{L(f(\bm{x}_{0})-f(\bm{x}_{K}))}{K^{2}}\Big{)}=O\Big{(}\frac{L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{K^{2}}\Big{)}.$

As before, we define $a_{k}=A_{k}-A_{k-1}$ and assume it is strictly positive,
for all $k$ (i.e., $A_{k}$ is strictly increasing). To bound
$\mathcal{C}_{K},$ we start by bounding the change in the potential function
$\mathcal{C}_{k}-\mathcal{C}_{k-1},$ for $k\geq 1,$ in the following lemma.
Observe that the lemma itself is algorithm-independent.

######  Lemma 2.5.

Let $\mathcal{C}_{k}$ be defined by Eq. (2.10), for all
$k\in\\{0,1,\dots,K\\}.$ Define $\bm{y}_{k}=\bm{x}_{k}-\frac{1}{L}\nabla
f(\bm{x}_{k})$ for $k\geq 0,$ and set $\bm{y}_{-1}=\bm{x}_{0}.$ Then, $\forall
1\leq k\leq K:$

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\;$ $\displaystyle
A_{k}\left\langle\nabla f(\bm{x}_{k}),\bm{x}_{k}-\bm{y}_{k-1}\right\rangle-
A_{k-1}\left\langle\nabla
f(\bm{x}_{k-1}),\bm{x}_{k-1}-\bm{y}_{k-2}\right\rangle$
$\displaystyle+\left\langle\nabla
f(\bm{x}_{k-1}),A_{k}\bm{y}_{k-1}-A_{k-1}\bm{y}_{k-2}-a_{k}\bm{y}_{K}\right\rangle.$

###### Proof.

Let $\bm{x},\bm{\hat{x}}$ be any two vectors from $\mathbb{R}^{d},$ and let
$\bm{y}=\bm{x}-\frac{1}{L}\nabla f(\bm{x}).$ Then, Eq. (1.3) can be
equivalently written as:

$f(\bm{\hat{x}})-f(\bm{x})\leq\left\langle\nabla
f(\bm{\hat{x}}),\bm{\hat{x}}-\bm{y}\right\rangle-\frac{1}{2L}\|\nabla
f(\bm{\hat{x}})\|^{2}-\frac{1}{2L}\|\nabla f(\bm{x})\|^{2}.$ (2.11)

From the definition of $\mathcal{C}_{k}$ in Eq. (2.10), we have

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}=\;$
$\displaystyle\frac{A_{k}}{2L}\|\nabla
f(\bm{x}_{k})\|^{2}-\frac{A_{k-1}}{2L}\|\nabla
f(\bm{x}_{k-1})\|^{2}+\frac{a_{k}}{2L}\|\nabla f(\bm{x}_{K})\|^{2}$
$\displaystyle+A_{k}(f(\bm{x}_{k})-f(\bm{x}_{k-1}))+a_{k}(f(\bm{x}_{k-1})-f(\bm{x}_{K})).$

Applying Eq. (2.11) to $f(\bm{x}_{k})-f(\bm{x}_{k-1})$ and
$f(\bm{x}_{k-1})-f(\bm{x}_{K})$, we further have

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\;$
$\displaystyle-\frac{A_{k}}{L}\|\nabla
f(\bm{x}_{k-1})\|^{2}+A_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{y}_{k-1}\right\rangle$
$\displaystyle+a_{k}\left\langle\nabla
f(\bm{x}_{k-1}),\bm{x}_{k-1}-\bm{y}_{K}\right\rangle$ $\displaystyle=\;$
$\displaystyle A_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{y}_{k-1}\right\rangle+A_{k}\left\langle\nabla
f(\bm{x}_{k-1}),\bm{y}_{k-1}-\bm{y}_{K}\right\rangle$ $\displaystyle-
A_{k-1}\left\langle\nabla
f(\bm{x}_{k-1}),\bm{x}_{k-1}-\bm{y}_{K}\right\rangle$ $\displaystyle=\;$
$\displaystyle A_{k}\left\langle\nabla
f(\bm{x}_{k}),\bm{x}_{k}-\bm{y}_{k-1}\right\rangle-A_{k-1}\left\langle\nabla
f(\bm{x}_{k-1}),\bm{x}_{k-1}-\bm{y}_{k-2}\right\rangle$
$\displaystyle+\left\langle\nabla
f(\bm{x}_{k-1}),A_{k}\bm{y}_{k-1},-A_{k-1}\bm{y}_{k-2}-a_{k}\bm{y}_{K}\right\rangle,$

as claimed. ∎

The following lemma provides the restrictions on the step sizes of the
algorithm that are needed to ensure that $\mathcal{C}_{K}\leq\mathcal{C}_{0}.$
Here, we assume that each point $\bm{x}_{k}$ can be expressed as the sum of
the initial point $\bm{x}_{0}$ and some linear combination of the gradients
evaluated at points $\bm{x}_{i}$ for $0\leq i\leq k-1.$ Note that most of the
standard first-order algorithms can be expressed in this form.

######  Lemma 2.6.

Let $\mathcal{C}_{k}$ be defined by Eq. (2.10) for $k\in\\{0,\dots,K\\}$ and
assume that points $\bm{x}_{k}$ can be expressed as
$\bm{x}_{k}=\bm{x}_{0}-\frac{1}{L}\sum_{i=0}^{k-1}\beta_{i,k}\nabla
f(\bm{x}_{i}),$ where $\beta_{i,k}$ are some real scalars. Define
$\beta_{k,k}=1,$ so that $\bm{y}_{k}=\bm{x}_{k}-\frac{1}{L}\nabla
f(\bm{x}_{k})=\bm{x}_{0}-\frac{1}{L}\sum_{i=0}^{k}\beta_{i,k}\nabla
f(\bm{x}_{i})$ and set $\bm{y}_{-1}=\bm{x}_{0}.$ If the following two
conditions are satisfied for all $0\leq j<k\leq K-1$:

$\displaystyle\beta_{k,K-1}+\frac{a_{k+1}}{A_{K}}\leq\frac{A_{k+1}}{a_{k+1}},$
(2.12) $\displaystyle
A_{k+1}\beta_{j,k}=A_{k}\beta_{j,k-1}+a_{k+1}\Big{(}\beta_{j,K-1}+\frac{a_{j+1}}{A_{K}}\Big{)}+a_{j+1}\Big{(}\beta_{k,K-1}+\frac{a_{k+1}}{A_{K}}\Big{)}$
(2.13)

and if

$\bm{x}_{K}=\bm{y}_{K-1}-\frac{1}{LA_{K}}\sum_{k=0}^{K-1}a_{k+1}\nabla
f(\bm{x}_{k}),$ (2.14)

then $\mathcal{C}_{K}\leq\mathcal{C}_{0}.$ Further, the largest growth of
$\frac{A_{K}}{A_{0}}$ for which both of these conditions can be satisfied is
$O(K^{2}).$

###### Proof.

Telescoping the inequality from Lemma 2.5, we have:

$\displaystyle\mathcal{C}_{K}-\mathcal{C}_{0}\leq\;$ $\displaystyle
A_{K}\left\langle\nabla f(\bm{x}_{K}),\bm{x}_{K}-\bm{y}_{K-1}\right\rangle$
$\displaystyle+\sum_{k=0}^{K-1}\left\langle\nabla
f(\bm{x}_{k}),A_{k+1}\bm{y}_{k}-A_{k}\bm{y}_{k-1}-a_{k+1}\bm{y}_{K}\right\rangle.$

Observe that $\nabla f(\bm{x}_{K})$ only appears in the first term and as part
of $\bm{y}_{K}=\bm{x}_{K}-\frac{1}{L}\nabla f(\bm{x}_{K}).$ Thus, grouping the
terms that multiply $\nabla f(\bm{x}_{K}),$ we can equivalently write

$\displaystyle\mathcal{C}_{K}-\mathcal{C}_{0}\leq\;$
$\displaystyle\left\langle\nabla
f(\bm{x}_{K}),A_{K}(\bm{x}_{K}-\bm{y}_{K-1})+\frac{1}{L}\sum_{k=0}^{K-1}a_{k+1}\nabla
f(\bm{x}_{k})\right\rangle$ $\displaystyle+\sum_{k=0}^{K-1}\left\langle\nabla
f(\bm{x}_{k}),A_{k+1}\bm{y}_{k}-A_{k}\bm{y}_{k-1}-a_{k+1}\bm{x}_{K}\right\rangle.$

The choice of $\bm{x}_{K}$ from Eq. (2.14) ensures that the first term on the
right-hand side is zero (and this is how it was chosen). The rest of the terms
can be expressed as a function of gradients up to the $(K-1)^{\mathrm{th}}$
one. To simplify the notation, let us define
$\bm{g}_{K-1}=\frac{1}{L}\sum_{k=0}^{K-1}a_{k+1}\nabla f(\bm{x}_{k}).$ Then,
we have

$\displaystyle\mathcal{C}_{K}-\mathcal{C}_{0}\leq\sum_{k=0}^{K-1}\left\langle\nabla
f(\bm{x}_{k}),A_{k+1}\bm{y}_{k}-A_{k}\bm{y}_{k-1}-a_{k+1}\Big{(}\bm{y}_{K-1}-\frac{\bm{g}_{K-1}}{A_{K}}\Big{)}\right\rangle.$
(2.15)

Observe that, as
$\bm{y}_{k}=\bm{x}_{0}-\frac{1}{L}\sum_{i=0}^{k}\beta_{i,k}\nabla
f(\bm{x}_{i})$ by the lemma assumptions, the expression on the right-hand side
can be written as a linear combination of inner products between gradients, as
follows.

$\displaystyle\mathcal{C}_{K}-\mathcal{C}_{0}\leq\frac{1}{L}\sum_{j=0}^{K-1}\sum_{k=j}^{K-1}P_{j,k}\left\langle\nabla
f(\bm{x}_{j}),{\nabla f(\bm{x}_{k})}\right\rangle,$

where, by Eq. (2.15), we have that, for all $0\leq j<k\leq K-1:$

$\displaystyle P_{k,k}$
$\displaystyle=-A_{k+1}\beta_{k,k}+a_{k+1}\Big{(}\beta_{k,K-1}+\frac{a_{k+1}}{{A_{K}}}\Big{)},$
$\displaystyle P_{j,k}$
$\displaystyle=-A_{k+1}\beta_{j,k}+A_{k}\beta_{j,k-1}+a_{k+1}\Big{(}\beta_{j,K-1}+\frac{a_{j+1}}{A_{K}}\Big{)}+a_{j+1}\Big{(}\beta_{k,K-1}+\frac{a_{k+1}}{A_{K}}\Big{)}.$

As, by assumption, $\beta_{k,k}=1,$ conditions in Eqs. (2.12) and (2.13) are
equivalent to $P_{k,k}\leq 0$ and $P_{j,k}=0$, for all $0\leq j<k\leq K-1.$ By
construction, these conditions are sufficient for guaranteeing
$\mathcal{C}_{k}-\mathcal{C}_{0}\leq 0,$ completing the first part of the
proof.

Observe that, given a sequence of positive numbers $\\{a_{k}\\}_{k\geq 0}$ and
$A_{k}=\sum_{j=0}^{k}a_{j},$ all coefficients $\beta_{j,k}$ are uniquely
determined by Eq. (2.13) (as $\beta_{k,k}=1$ by assumption, and the remaining
coefficients can be computed by recursively applying Eq. (2.13)). Thus, the
role of the condition from Eq. (2.12) is to limit the growth of the sequence
$\\{A_{k}\\}_{k\geq 0}.$ Starting with $\beta_{k,k}=1,$ $\forall k$ (which
holds by assumption), it is possible to argue by induction that
$\beta_{j,k}\geq 0,$ $\forall j,k$ (the proof is omitted for brevity). Thus
the condition from Eq. (2.12) implies that
$\frac{a_{k+1}}{A_{K}}\leq\frac{A_{k+1}}{a_{k+1}}.$ Equivalently, $\forall
k\leq K-1$:

$\frac{{a_{k+1}}^{2}}{A_{k+1}}\leq A_{K}.$ (2.16)

For any fixed $A_{K},$ Eq. (2.16) implies that $\frac{A_{k}}{A_{0}}$ cannot
grow faster than quadratically with $k,$ for $k\leq K-1.$ It remains to argue
that the sequence does not make a big jump from $A_{K-1}$ to $A_{K}.$ This
follows by using again Eq. (2.12) for $k=K-1$ and recalling that
$\beta_{K-1,K-1}=1.$ We then have

$1+\frac{a_{K}}{A_{K}}\leq\frac{A_{K}}{a_{K}}.$

Solving for $\frac{a_{K}}{A_{K}},$ it follows that
$\frac{a_{K}}{A_{K}}\leq\frac{-1+\sqrt{5}}{2}<0.62,$ and, thus,
$\frac{A_{K}}{A_{K-1}}\leq\frac{1}{1-0.62}<3,$ completing the proof that
$\frac{A_{K}}{A_{0}}=O(K^{2}).$ ∎

That $\frac{A_{K}}{A_{0}}=O(K^{2})$ is not surprising – if it were not true,
by the discussion from the beginning of this subsection, we would be able to
obtain an algorithm that converges at rate faster than $1/K^{2},$ which is
impossible, due to the existing lower bounds [13]. This result was rather
included to highlight the role of the conditions from Eqs. (2.12) and (2.13)
in Lemma 2.6: the first condition limits the growth of $\\{A_{k}\\}_{k\geq
0},$ whereas the second determines the step sizes $\beta_{j,k}$ in the
algorithm, given the sequence $\\{A_{k}\\}_{k\geq 0}$.

What remains to be shown is that there is a choice of step sizes $\beta_{j,k}$
that guarantees $\frac{A_{K}}{A_{0}}=\Theta(K^{2}),$ and thus leads to an
algorithm with the optimal convergence rate. This choice is obtained when the
inequality from Eq. (2.12) is satisfied with equality. It is possible to argue
that this choice is also the one that leads to the fastest growth of
$\frac{A_{K}}{A_{0}};$ however, this direction is not pursued here as it
unnecessarily complicates the analysis. Further, when Eq. (2.12) is satisfied
with equality, Eq. (2.13) can be further simplified, and it leads to the
algorithm description that does not necessitate storing all of the gradients,
but only a constant number of $d$-dimensional vectors. However, similar to the
algorithm description in [28], the entire sequence $\\{A_{k}\\}_{k=0}^{K}$
needs to be pre-computed and stored, which appears to be unavoidable. The
algorithm and its convergence rate are summarized in the following theorem.

######  Theorem 2.7 (Convergence of Optimized Gradient Method).

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be an $L$-smooth function and let
$\bm{x}_{0}\in\mathbb{R}^{d}$ be an arbitrary initial point. Let $K\geq 1.$
Consider the following algorithm. Let
$\bm{v}=\bm{x}_{0}-\frac{A_{1}}{a_{1}L}\nabla f(\bm{x}_{0})$,
$\bm{g}_{0}=a_{1}\nabla f(\bm{x}_{0}).$ For $k=1$ to $K-1,$

$\begin{gathered}\bm{y}_{k-1}=\bm{x}_{k-1}-\frac{1}{L}\nabla
f(\bm{x}_{k-1}),\\\
\bm{x}_{k}=\frac{A_{k}}{A_{k+1}}\bm{y}_{k-1}+\frac{a_{k+1}}{A_{k+1}}\bm{v}_{k-1}-\frac{1}{a_{k+1}}\bm{g}_{k-1},\\\
\bm{v}_{k}=\bm{v}_{k-1}-\frac{1}{L}\frac{A_{k+1}}{a_{k+1}}\nabla
f(\bm{x}_{k}),\;\bm{g}_{k}=\bm{g}_{k-1}+a_{k+1}\nabla
f(\bm{x}_{k}),\end{gathered}$ (2.17)

where the sequence $\\{A_{k}\\}_{k=0}^{K}$ is recursively defined by the
following

$\begin{cases}A_{k}=1,&\text{ if }k=K,\\\
A_{k}=A_{k+1}\big{[}1+\frac{1}{2}A_{k+1}-\frac{1}{2}\sqrt{A_{k+1}(4+A_{k+1})}\big{]},&\text{
if }0\leq k\leq K-1,\end{cases}$ (2.18)

and $a_{k+1}=A_{k+1}-A_{k},$ for $0\leq k\leq K-1.$

If $\bm{x}_{K}$ is defined by

$\bm{x}_{K}=\bm{y}_{K-1}-\frac{1}{A_{K}L}\bm{g}_{K-1},$

then

$\|\nabla
f(\bm{x}_{K})\|^{2}\leq\frac{16L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{(K+2)^{2}},$

where
$\bm{x}^{*}\in\operatorname*{argmin}_{\bm{x}\in\mathbb{R}^{d}}f(\bm{x}).$

###### Proof.

The proof strategy is as follows. We first argue that the algorithm from the
theorem statement satisfies $\mathcal{C}_{K}\leq\mathcal{C}_{0},$ where
$\mathcal{C}_{k}$ is defined by Eq. (2.10). This is done by showing that we
can apply Lemma 2.6. Then, by the definition of $\mathcal{C}_{k},$
$\mathcal{C}_{K}\leq\mathcal{C}_{0}$ is equivalent to

$\|\nabla f(\bm{x}_{K})\|^{2}\leq
2L\frac{A_{0}}{A_{K}}\Big{(}f(\bm{x}_{0})-f(\bm{x}_{K})+\frac{1}{2L}\|\nabla
f(\bm{x}_{0})\|^{2}\Big{)}.$

As $f(\bm{x}_{K})\geq f(\bm{x}^{*})$ and $\frac{1}{2L}\|\nabla
f(\bm{x}_{0})\|^{2}\leq f(\bm{x}_{0})-f(\bm{x}^{*}),$ what then remains to be
argued is that $\frac{A_{0}}{A_{K}}=O(\frac{1}{K^{2}}).$

To apply Lemma 2.6, observe first that the definition of $\bm{x}_{K}$ from the
theorem statement is the same as the definition of $\bm{x}_{K}$ in Lemma 2.6.
For $k\leq K-1,$ let us define
$\bm{x}_{k}=\bm{x}_{0}-\frac{1}{L}\sum_{j=0}^{k-1}\beta_{j,k}\nabla
f(\bm{x}_{j}),$ $\beta_{k,k}=1,$ and
$\bm{y}_{k}=\bm{x}_{k}-\frac{\beta_{k,k}}{L}\nabla f(\bm{x}_{k})$ as in Lemma
2.6 and show that when both conditions from Lemma 2.6 stated in Eqs. (2.12)
and Eq. (2.13) are satisfied with equality, we recover the algorithm from the
theorem statement, and thus the two sequences of points are equivalent, and so
we can conclude that $\mathcal{C}_{K}\leq\mathcal{C}_{0}.$

When Eq. (2.12) holds with equality, we have that

$\beta_{k,K-1}+\frac{a_{k+1}}{A_{K}}=\frac{A_{k+1}}{a_{k+1}}.$ (2.19)

Plugging it into Eq. (2.13), we have

$A_{k+1}\beta_{j,k}=A_{k}\beta_{j,k-1}+a_{k+1}\frac{A_{j+1}}{a_{j+1}}+a_{j+1}\frac{A_{k+1}}{a_{k+1}}.$
(2.20)

Thus, it follows that

$\displaystyle A_{k+1}\bm{x}_{k}-A_{k}\bm{y}_{k-1}$
$\displaystyle=a_{k+1}\bm{x}_{0}-\frac{a_{k+1}}{L}\sum_{j=0}^{k-1}\frac{A_{j+1}}{a_{j+1}}\nabla
f(\bm{x}_{j})-\frac{a_{j+1}}{L}\sum_{j=0}^{k-1}a_{j+1}\nabla f(\bm{x}_{j})$
$\displaystyle=a_{k+1}\bm{v}_{k-1}-\frac{A_{k+1}}{a_{k+1}}\bm{g}_{k-1},$

which is the same as the definition of $\bm{x}_{k}$ from Eq. (2.17).

It remains to show that the conditions from Lemma 2.6 imply the recursive
definition of the sequence $\\{A_{k}\\}_{k\geq 0}$ and that
$\frac{A_{K}}{A_{0}}\geq\frac{4}{(K+2)^{2}}.$ This is established by Lemma A.1
in the appendix. ∎

######  Remark 2.8.

While OGM-G provides the optimal convergence guarantee for norm of the
gradient, its convergence rate for the optimality gap is not known. Thus, it
does not immediately imply a bound on norm of the gradient in terms of
$\|\bm{x}^{*}-\bm{x}_{0}\|^{2}.$ However, as observed in [43], it is possible
to obtain a bound of $\|\nabla
f(\bm{x}_{K})\|^{2}=O\big{(}\frac{L^{2}\|\bm{x}^{*}-\bm{x}_{0}\|^{2}}{K^{4}}\big{)}$
from OGM-G, by running Nesterov FGM for $\lfloor K/2\rfloor$ iterations,
followed by $\lceil K/2\rceil$ iterations of OGM-G.

###  2.3 Discussion

Gradient descent is perhaps the simplest method that can be used for
minimizing the gradient norm. We also conjecture that it is, in a certain
sense, optimal.

######  Conjecture 1.

For any $K>0$ and any method that constructs its iterates as
$\bm{x}_{k}=\bm{x}_{0}-\sum_{i=0}^{k-1}\beta_{i,k}\nabla f(\bm{x}_{i}),$ where
$\bm{x}_{0}\in\mathbb{R}^{d}$ is the initial point, $f$ is a convex function
accessed via a gradient oracle, and coefficients $\beta_{i,k}\in\mathbb{R}$
can depend on $L>0,i,k$ but are otherwise chosen independently of $K$ or the
input function $f,$ there exists an $L$-smooth convex input function $f$ and
an absolute constant $C>0$ such that

$\|\nabla f(\bm{x}_{K})\|^{2}\geq C\frac{L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{K}.$

The basis for this conjecture is the numerical evidence from [27, 28], which
seems to suggest that fixing the total number of iterations $K$ and choosing
the coefficients $\beta_{i,k}$ as a function $K$ is crucial to obtaining the
optimal bound $\|\nabla
f(\bm{x}_{K})\|^{2}=O\Big{(}\frac{L(f(\bm{x}_{0})-f(\bm{x}^{*}))}{K^{2}}\Big{)}$.
We note that the lower bound from Conjecture 1 can be proved under a stricter
condition on coefficients $\beta_{i,k}$ that essentially forces them to be
constant (independent of $i$ and $k$), using the techniques of Arjevani and
Shamir [3]. However, such a lower bound is weak as it not only excludes the
optimal algorithm from [28] (which is desired) but also all variants of
Nesterov FGM considered in [27].

##  3 Small Gradients in Min-Max Optimization

In this section, we consider the problem of making the gradients small in
convex-concave min-max optimization, under the assumption that the operator
$F$ corresponding to the gradient of the objective is cocoercive (see Section
1.2). Similarly as in the case of convex optimization, the potential functions
we consider trade off a notion of an optimality gap with the norm of $F.$
Further, the inequality corresponding to the cocoercivity assumption suffices
to carry out the analysis of standard methods considered here; namely, the
gradient descent-ascent method and Halpern iteration. We also show (in Section
3.3) that these two methods are the best we can hope for when considering
broad classes of methods that capture most of the standard optimization
methods.

###  3.1 Krasnosel’skiı-Mann/Gradient Descent-Ascent

Perhaps the simplest potential function that can be considered for min-max
optimization is

$\mathcal{C}_{k}=A_{k}\|F(\bm{u}_{k})\|^{2}+B_{k}\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}^{*}\right\rangle,$ (3.1)

which can be seen as a counterpart to the potential function used for gradient
descent in the previous section. The method that is suitable for the analysis
with this potential function is also the counterpart of gradient descent for
min-max optimization—gradient descent-ascent (GDA), stated as

$\bm{u}_{k+1}=\bm{u}_{k}-\eta_{k}F(\bm{u}_{k}),$

where $\eta_{k}\in(0,\frac{2}{L}).$ This method is also equivalent to the
well-known Krasnosel’skiı-Mann iteration for finding fixed points of
nonexpansive (1-Lipschitz) operators. In particular, given a nonexpansive
operator $T:\mathbb{R}^{d}\to\mathbb{R}^{d},$ the Krasnosel’skiı-Mann
iteration updates the iterates as

$\bm{u}_{k+1}=(1-\alpha_{k})\bm{u}_{k}+\alpha_{k}T(\bm{u}_{k}),$

where $\alpha_{k}\in(0,1).$ It is a standard fact that $F$ is
$\frac{1}{L}$-cocoercive if and only if $T(\cdot)=\cdot-\frac{2}{L}F(\cdot)$
is nonexpansive (see, e.g., [9, Proposition 4.1]). Thus, if we apply the
Krasnosel’skiı-Mann iteration to $T(\cdot)=\cdot-\frac{2}{L}F(\cdot)$, we have

$\bm{u}_{k+1}=\bm{u}_{k}-\frac{2\alpha_{k}}{L}F(\bm{u}_{k}),$

which is precisely GDA with $\eta_{k}=\frac{2\alpha_{k}}{L}.$

For simplicity, in the following we analyze GDA with the step size
$\eta_{k}=\eta=\frac{1}{L},$ which is the optimal step size for this method.
The analysis however extends to any step sizes $\eta_{k}\in(0,\frac{2}{L})$ in
a straightforward manner. The convergence result is summarized in the
following lemma.

######  Lemma 3.1 (Convergence of Gradient Descent-Ascent).

Let $F:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be a $\frac{1}{L}$-cocoercive
operator, $\bm{u}_{0}\in\mathbb{R}^{d}$ be an arbitrary initial point, and let
$\bm{u}_{k+1}=\bm{u}_{k}-\frac{1}{L}F(\bm{u}_{k})$ for $k\geq 0.$ Then,
$\forall k\geq 1:$

$\|F(\bm{u}_{k})\|\leq\frac{L\|\bm{u}_{0}-\bm{u}^{*}\|}{\sqrt{k/2+1}},$

where $\bm{u}^{*}$ is such that $F(\bm{u}^{*})=\textbf{0}.$

###### Proof.

The proof relies on showing that the potential function $\mathcal{C}_{k}$
satisfies $\mathcal{C}_{k}\leq\mathcal{C}_{k-1}+E_{k},$ where $E_{k}$ only
contains terms that telescope, for suitably chosen sequences of positive
numbers $\\{A_{k}\\}_{k\geq 0}$ and $\\{B_{k}\\}_{k\geq 0}.$

Let us start with bounding $\mathcal{C}_{0}.$ As
$\bm{u}_{1}=\bm{u}_{0}-\frac{1}{L}F(\bm{u}_{0}),$ we have

$\displaystyle\mathcal{C}_{0}$
$\displaystyle=A_{0}\|F(\bm{u}_{0})\|^{2}+B_{0}\left\langle
F(\bm{u}_{0}),\bm{u}_{0}-\bm{u}^{*}\right\rangle$
$\displaystyle=A_{0}\|F(\bm{u}_{0})\|^{2}+B_{0}L\left\langle\bm{u}_{0}-\bm{u}_{1},\bm{u}_{0}-\bm{u}^{*}\right\rangle$
$\displaystyle=A_{0}\|F(\bm{u}_{0})\|^{2}+\frac{B_{0}L}{2}\big{(}\|\bm{u}_{0}-\bm{u}^{*}\|^{2}-\|\bm{u}_{1}-\bm{u}^{*}\|^{2}+\|\bm{u}_{0}-\bm{u}_{1}\|^{2}\big{)}$
$\displaystyle=\Big{(}A_{0}+\frac{B_{0}}{2L}\Big{)}\|F(\bm{u}_{0})\|^{2}+\frac{B_{0}L}{2}\big{(}\|\bm{u}_{0}-\bm{u}^{*}\|^{2}-\|\bm{u}_{1}-\bm{u}^{*}\|^{2}\big{)}.$

Eq. (1.7) implies $\|F(\bm{u}_{0})\|^{2}\leq
L^{2}\|\bm{u}_{0}-\bm{u}^{*}\|^{2},$ and, thus, we have

$\mathcal{C}_{0}=\frac{A_{0}L^{2}+2B_{0}L}{2}\|\bm{u}_{0}-\bm{u}^{*}\|^{2}-\frac{B_{0}L}{2}\|\bm{u}_{1}-\bm{u}^{*}\|^{2}.$
(3.2)

Now let us consider the change in the potential function
$\mathcal{C}_{k}-\mathcal{C}_{k-1}.$ Note first that, by Eq. (1.7),
$\left\langle
F(\bm{u}_{k-1}),\bm{u}_{k-1}-\bm{u}^{*}\right\rangle\geq\frac{1}{L}\|F(\bm{u}_{k-1})\|^{2}.$
Thus:

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}=\;$ $\displaystyle
A_{k}\|F(\bm{u}_{k})\|^{2}-A_{k-1}\|F(\bm{u}_{k-1})\|^{2}+B_{k}\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}^{*}\right\rangle$ $\displaystyle-
B_{k-1}\left\langle F(\bm{u}_{k-1}),\bm{u}_{k-1}-\bm{u}^{*}\right\rangle$
$\displaystyle\leq\;$ $\displaystyle
A_{k}\|F(\bm{u}_{k})\|^{2}-\Big{(}A_{k-1}+\frac{B_{k-1}}{L}\Big{)}\|F(\bm{u}_{k-1})\|^{2}+B_{k}\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}^{*}\right\rangle.$

Using that $F(\bm{u}_{k})=L(\bm{u}_{k}-\bm{u}_{k+1}),$ we have that
$\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}^{*}\right\rangle=\frac{1}{2L}\|F(\bm{u}_{k})\|^{2}+\frac{L}{2}\|\bm{u}_{k}-\bm{u}^{*}\|^{2}-\frac{L}{2}\|\bm{u}_{k+1}-\bm{u}^{*}\|^{2},$
which leads to

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\;$
$\displaystyle\Big{(}A_{k}+\frac{B_{k}}{2L}\Big{)}\|F(\bm{u}_{k})\|^{2}-\Big{(}A_{k-1}+\frac{B_{k-1}}{L}\Big{)}\|F(\bm{u}_{k-1})\|^{2}$
$\displaystyle+\frac{B_{k}L}{2}\|\bm{u}_{k}-\bm{u}^{*}\|^{2}-\frac{B_{k}L}{2}\|\bm{u}_{k+1}-\bm{u}^{*}\|^{2}.$

On the other hand, by Eq. (1.6) and
$\bm{u}_{k}=\bm{u}_{k-1}-\frac{1}{L}F(\bm{u}_{k-1})$, we have that
$\|F(\bm{u}_{k})\|^{2}\leq\left\langle
F(\bm{u}_{k}),F(\bm{u}_{k-1})\right\rangle,$ and, consequently,
$\|F(\bm{u}_{k})\|\leq\|F(\bm{u}_{k-1})\|.$ Thus, for
$\mathcal{C}_{k}-\mathcal{C}_{k-1}$ to contain only telescoping terms, it
suffices that $A_{k}+\frac{B_{k}}{2L}-A_{k-1}-\frac{B_{k-1}}{L}\leq 0$ and
that $\\{B_{k}\\}_{k\geq 0}$ is non-increasing. In particular, taking
$B_{k}=1$ and $A_{k+1}=A_{k}+\frac{1}{2L}=A_{0}+\frac{k+1}{2L}$ for all $k\geq
0,$ we have

$\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq\frac{L}{2}\|\bm{u}_{k}-\bm{u}^{*}\|^{2}-\frac{L}{2}\|\bm{u}_{k+1}-\bm{u}^{*}\|^{2}.$
(3.3)

Telescoping Eq. (3.3) and combining with Eq. (3.2), we then get

$\mathcal{C}_{k}\leq\frac{A_{0}L^{2}+2L}{2}\|\bm{u}_{0}-\bm{u}^{*}\|^{2}-\frac{L}{2}\|\bm{u}_{k+1}-\bm{u}^{*}\|^{2}\leq\frac{A_{0}L^{2}+2L}{2}\|\bm{u}_{0}-\bm{u}^{*}\|^{2}.$

Taking $A_{0}=0$ and observing that, by Eq. (1.7),
$\mathcal{C}_{k}\geq\big{(}A_{k}+\frac{B_{k}}{L}\big{)}\|F(\bm{u}_{k})\|^{2}=\frac{k+2}{2L}\|F(\bm{u}_{k})\|^{2},$
we finally get

$\|F(\bm{u}_{k})\|^{2}\leq\frac{2L^{2}\|\bm{u}_{0}-\bm{u}^{*}\|^{2}}{k+2}.$

It remains to take the square-root on both sides of the last inequality. ∎

###  3.2 Halpern Iteration

It seems reasonable now to ask whether it is possible to obtain faster rates
than for GDA by considering a different potential function that trades off the
gradient/operator norm for a notion of an optimality gap w.r.t. an anchor
point, similar to how we obtained faster rates for convex optimization. It
turns out that the answer is “yes,” using the initial point $\bm{u}_{0}$ as
the anchor. The resulting potential function is

$\mathcal{C}_{k}=A_{k}\|F(\bm{u}_{k})\|^{2}+B_{k}\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}_{0}\right\rangle$

and it corresponds to the well-known Halpern iteration

$\bm{u}_{k+1}=\lambda_{k+1}\bm{u}_{0}+(1-\lambda_{k+1})T(\bm{u}_{k}),$ (3.4)

where, similarly as in the case of GDA, $T(\cdot)=\cdot-\frac{2}{L}F(\cdot)$
is a nonexpansive operator. We note that a similar potential function was used
in [15] to analyze the convergence of Halpern iteration.

Here we show that the potential function
$\mathcal{C}_{k}=A_{k}\|F(\bm{u}_{k})\|^{2}+B_{k}\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}_{0}\right\rangle$ in fact leads to the Halpern
iteration as a natural algorithm that guarantees that $\mathcal{C}_{k}$ is
non-increasing. The main convergence result is summarized in the following
lemma, whose proof reveals how the chosen potential function leads to the
Halpern iteration.

######  Lemma 3.2 (Convergence of Halpern Iteration).

Let $F:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be a $\frac{1}{L}$-cocoercive
operator, $\bm{u}_{0}\in\mathbb{R}^{d}$ be an arbitrary initial point, and,
for $k\geq 0,$ let

$\bm{u}_{k+1}=\frac{1}{k+1}\bm{u}_{0}+\frac{k}{k+1}\Big{(}\bm{u}_{k}-\frac{2}{L}F(\bm{u}_{k})\Big{)}.$

Then, $\forall k\geq 1,$ we have

$\|F(\bm{u}_{k})\|\leq\frac{L\|\bm{u}_{0}-\bm{u}^{*}\|}{k+1},$

where $\bm{u}^{*}$ satisfies $F(\bm{u}^{*})=\textbf{0}.$

###### Proof.

The claim trivially holds if $\|F(\bm{u}_{k})\|=0,$ so assume throughout that
$\|F(\bm{u}_{k})\|\neq 0.$

Consider bounding $\mathcal{C}_{k}-\mathcal{C}_{k-1}$ above by zero. To do so,
we can only rely on cocoercivity of $F$ from Eq. (1.6). Applying Eq. (1.6)
with $\bm{u}=\bm{u}_{k}$ and $\bm{v}=\bm{u}_{k-1}$ and rearranging the terms,
we have

$\displaystyle\frac{1}{L}\|F(\bm{u}_{k})\|^{2}\leq$ $\displaystyle\left\langle
F(\bm{u}_{k}),\bm{u}_{k}-\bm{u}_{k-1}+\frac{2}{L}F(\bm{u}_{k-1})\right\rangle$
(3.5) $\displaystyle-\left\langle
F(\bm{u}_{k-1}),\bm{u}_{k}-\bm{u}_{k-1}\right\rangle-\frac{1}{L}\|F(\bm{u}_{k-1})\|^{2}.$

Combining Eq. (3.5) with the definition of $\mathcal{C}_{k}$ and grouping
appropriate terms, we have

$\displaystyle\mathcal{C}_{k}-\mathcal{C}_{k-1}\leq$
$\displaystyle\left\langle
F(\bm{u}_{k}),A_{k}L\Big{(}\bm{u}_{k}-\bm{u}_{k-1}+\frac{2}{L}F(\bm{u}_{k-1})\Big{)}+B_{k}(\bm{u}_{k}-\bm{u}_{0})\right\rangle$
(3.6) $\displaystyle-\left\langle
F(\bm{u}_{k-1}),A_{k}L(\bm{u}_{k}-\bm{u}_{k-1})+B_{k-1}(\bm{u}_{k-1}-\bm{u}_{0})\right\rangle$
$\displaystyle-\frac{A_{k}+A_{k-1}}{L}\|F(\bm{u}_{k-1})\|^{2}.$

For $\bm{u}_{k}$ to be explicitly defined, it cannot depend on
$F(\bm{u}_{k})$. Thus, the only direct way to make the first line of the
right-hand side of Eq. (3.6) non-positive is to set

$A_{k}L\Big{(}\bm{u}_{k}-\bm{u}_{k-1}+\frac{2}{L}F(\bm{u}_{k-1}))\Big{)}+B_{k}(\bm{u}_{k}-\bm{u}_{0})=0.$
(3.7)

For the remaining terms, it suffices that

$-\left\langle
F(\bm{u}_{k-1}),A_{k}L(\bm{u}_{k}-\bm{u}_{k-1})+B_{k-1}(\bm{u}_{k-1}-\bm{u}_{0})\right\rangle-({A_{k}+A_{k-1}})\|F(\bm{u}_{k-1})\|^{2}\leq
0.$ (3.8)

Rearranging Eq. (3.7) gives the Halpern algorithm from Eq. (3.4) with
$\lambda_{k}=\frac{B_{k}}{A_{k}L+B_{k}},$ i.e.,

$\bm{u}_{k}=\frac{B_{k}}{A_{k}L+B_{k}}\bm{u}_{0}+\frac{A_{k}L}{A_{k}L+B_{k}}\Big{(}\bm{u}_{k-1}-\frac{2}{L}F(\bm{u}_{k-1})\Big{)}.$
(3.9)

The other condition (from Eq. (3.8)) effectively constrains the growth of
$A_{k}$ compared to $B_{k},$ which is expected, as otherwise we would be able
to prove an arbitrarily fast convergence rate for Halpern iteration, which is
impossible, due to existing lower bounds (see, e.g. [15]).

Combining Eq. (3.7) and Eq. (3.8), we have

$\displaystyle-\left\langle
F(\bm{u}_{k-1}),A_{k}L\bm{u}_{k}-B_{k-1}\bm{u}_{0}-(A_{k}L-B_{k-1})\bm{u}_{k-1}\right\rangle\leq(A_{k}+A_{k-1})\|F(\bm{u}_{k-1})\|^{2}.$

Now, to be able to guarantee that the last inequality is satisfied and
consistent with Eq. (3.9), it is required that

$\frac{B_{k-1}}{A_{k}L}=\frac{B_{k}}{A_{k}L+B_{k}}\quad\text{ and
}\quad\frac{2A_{k}}{A_{k}L+B_{k}}\leq\frac{A_{k}+A_{k-1}}{A_{k}L}.$ (3.10)

In particular, when $B_{k}=k+1$ and $A_{k}=\frac{k(k+1)}{L},$ both conditions
from Eq. (3.10) are satisfied with equality.

Hence, for $B_{k}=k+1,$ $A_{k}=\frac{k(k+1)}{L},$ and
$\lambda_{k}=\frac{B_{k}}{A_{k}L+B_{k}}=\frac{1}{k+1},$ we have that
$\mathcal{C}_{k}\leq\mathcal{C}_{0}.$ By definition, and as $A_{0}=0,$ we have
that $\mathcal{C}_{0}=0$. Thus, $\mathcal{C}_{k}\leq 0,$ $\forall k\geq 1,$
and it follows that

$\displaystyle\|F(\bm{u}_{k})\|^{2}$
$\displaystyle\leq\frac{B_{k}}{A_{k}}\left\langle
F(\bm{u}_{k}),\bm{u}_{0}-\bm{u}_{k}\right\rangle$
$\displaystyle=\frac{L}{k}\big{(}\left\langle
F(\bm{u}_{k}),\bm{u}^{*}-\bm{u}_{k}\right\rangle+\left\langle
F(\bm{u}_{k}),\bm{u}_{0}-\bm{u}^{*}\right\rangle\big{)}$
$\displaystyle\leq\frac{L}{k}\Big{(}-\frac{1}{L}\|F(\bm{u}_{k})\|^{2}+\|F(\bm{u}_{k})\|\|\bm{u}_{0}-\bm{u}^{*}\|\Big{)},$

where the last inequality is by Eq. (1.7) and Cauchy-Schwarz. To complete the
proof, it remains to rearrange the last inequality and divide both sides by
$\|F(\bm{u}_{k})\|.$ ∎

###  3.3 Lower Bounds for Cocoercive Operators

In this section, we provide a lower bound that applies to the class of
algorithms that construct their iterates as the sum of an initial point and a
linear combination of the cocoercive operator
$F:\mathbb{R}^{d}\to\mathbb{R}^{d}$ evaluated at any of the points seen up to
the current iteration. In particular, given a $\frac{1}{L}$-cocoercive
operator $F:\mathbb{R}^{d}\to\mathbb{R}^{d},$ an algorithm’s iterate
$\bm{u}_{k}$ at iteration $k$ can be expressed as

$\bm{u}_{k}=\bm{u}_{0}-\sum_{i=0}^{k-1}\beta_{i,k}F(\bm{u}_{i}),$ (3.11)

where $\beta_{i,k}$ are real coefficients that can depend on $L$ but are
otherwise independent of $F$. To state the lower bound, we use
$\mathcal{F}_{L,D}$ to denote the class of problems with
$\frac{1}{L}$-cocoercive operators $F$ that satisfy
$\|\bm{u}^{*}-\bm{u}_{0}\|\leq D,$ where $\bm{u}_{0}\in\mathbb{R}^{d}$ is an
arbitrary initial point and $\bm{u}^{*}$ is such that
$F(\bm{u}^{*})=\textbf{0}.$ We assume w.l.o.g. that $d$ is even.

To derive the lower bound, we use the framework developed in [2, 3]. To make
use of this framework, which relies on the use of Chebyshev polynomials, it is
necessary to construct hard instances corresponding to linear operators
$F(\bm{u})=\bm{A}\bm{u}+\bm{b},$ where $\bm{A}\in\mathbb{R}^{d\times d}$ and
$\bm{b}\in\mathbb{R}^{d}.$ We note that such an approach was also used in [22]
for the class of monotone Lipschitz operators. However, here we aim to provide
a lower bound for the more restricted class of cocoercive operators, which
necessitates a separate construction. In particular, the monotone operator
from the lower bound instance used in [22] is not cocoercive as it corresponds
to a bilinear function; in fact, it satisfies $\left\langle
F(\bm{u})-F(\bm{v}),\bm{u}-\bm{v}\right\rangle=0,$
$\forall\bm{u},\bm{v}\in\mathbb{R}^{d}.$

Before delving into the technical details of our lower bound, we first provide
definitions and supporting claims from [2] that are needed for stating and
proving it. A useful definition is that of 1-SCLI algorithms, which allows
abstracting algorithms of the form from Eq. (3.11) through the lens of
Chebyshev polynomials. Here, we adopt the terminology from [22], which
somewhat blurs the lines between various definitions (of stationary,
oblivious, $p$-SCLI) algorithm types from [3, 2], but provides perhaps the
simplest way of stating the results.

######  Definition 3.3 (1-SCLI Algorithms).

An optimization algorithm $\mathcal{A}$ acting on the class of linear
operators $F:\mathbb{R}^{d}\to\mathbb{R}^{d}$ of the form
$F(\bm{u})=\bm{A}\bm{u}+\bm{b}$, where $\bm{A}\in\mathbb{R}^{d\times d},$
$\bm{b}\in\mathbb{R}^{d},$ is said to be $1$-stationary canonical linear
iterative ($1$-SCLI) over $\mathbb{R}^{d}$ if, given an initial point
$\bm{u}_{0}\in\mathbb{R}^{d}$, there exist mappings
$C_{0}(\mathbf{A}),N(\mathbf{A}):\mathbb{R}^{d\times d}\to\mathbb{R}^{d\times
d}$ such that for all $k\geq 1$ the iterates of $\mathcal{A}$ can be expressed
as

$\bm{u}_{k}=C_{0}(\bm{A})\bm{u}_{k-1}+N(\bm{A})\bm{b}.$

Observe here that Definition 3.3 imposes no restrictions on what kind of
mappings $C_{0}$ and $N$ can be. In particular, they can be polynomials of an
arbitrary degree. This is important because choosing polynomials of degree $K$
would allow us to emulate arbitrary algorithms of the form from Eq. (3.11) run
over $K$ iterations, as $F$ is assumed to be linear (this observation is
typically used in the analysis of the classical conjugate gradient method;
see, e.g., [45, Chapter 5]). On the other hand, restricting the degree of the
polynomials would restrict the adaptivity of coefficients $\beta_{i,k}$, as
$C_{0},N$ remain fixed for all $k.$ In this context, both GDA and Halpern
iteration (when restricted to be run over a fixed number $K$ of iterations)
can be viewed as 1-SCLI algorithms, with the following crucial difference. For
GDA with a fixed step size $\eta$, we have

$\bm{u}_{k}=(\bm{I}-\eta\bm{A})\bm{u}_{k-1}+\eta\bm{b},$

i.e., $C_{0}$ is of degree one and $N$ is of degree zero. On the other hand,
for Halpern iteration,

$\displaystyle\bm{u}_{k}$
$\displaystyle=\lambda_{k}\bm{u}_{0}+(1-\lambda_{k})\Big{(}\bm{I}-\frac{2}{L}\bm{A}\Big{)}\bm{u}_{k-1}+(1-\lambda_{k})\bm{b}.$
(3.12)

By recursively applying Eq. (3.12) and rolling it down to zero, we get that
$\bm{u}_{k}$ can be expressed as
$\bm{u}_{k}=C_{0}(\bm{A})\bm{u}_{0}+N(\bm{A})\bm{b}$ using $C_{0}$ that is a
polynomial of degree $k$ and $N$ that is a polynomial of degree $k-1.$ In
other words, we can view $k$ iterations of Halpern’s algorithm as one
iteration of a 1-SCLI algorithm, using polynomial maps $C_{0}$ and $N$ of
suitably large degrees. This is crucial for understanding the statement of the
lower bound, which will effectively tell us that GDA is iteration complexity-
optimal among all algorithms of the form from Eq. (3.11) that choose steps
sizes $\beta_{i,k}$ independently of $k,$ while Halpern iteration is iteration
complexity-optimal over all algorithms that are allowed to adapt
$\beta_{i,k}$’s to $k.$

In the following, we further restrict our attention to operators $F$
corresponding to full-rank matrices $\bm{A}.$ This is convenient because the
optimal solution $\bm{u}^{*}$ for which $F(\bm{u}^{*})=\textbf{0}$ can be
expressed in closed form as $\bm{u}^{*}=-\bm{A}^{-1}\bm{b}.$ This allows us to
relate the polynomials $C_{0}$ and $N$ under a minimal (and standard [3, 2,
22]) assumption that the 1-SCLI algorithms we consider are _consistent_ (or
convergent). We note here that the consistency condition is not necessary; it
is rather the case that the proof relies on the relationship between $C_{0}$
and $N$ from Eq. (3.13), for which the natural consistency condition suffices.

######  Definition 3.4 (Consistency).

A 1-SCLI algorithm $\mathcal{A}$ is said to be consistent w.r.t. a full-rank
matrix $\bm{A}$ if for any $\bm{b}\in\mathbb{R}^{d}$ we have that $\bm{u}_{k}$
converges to $\bm{u}^{*}=-\bm{A}^{-1}\bm{b}$. A 1-SCLI algorithm is said to be
consistent if it is consistent w.r.t. any full-rank matrix $\bm{A}.$

The relationship between $C_{0}$ and $N$ for consistent algorithms is
characterized by the following lemma.

######  Lemma 3.5 (Consistency of 1-SCLI Algorithms [2]).

If a 1-SCLI algorithm is consistent w.r.t. $\bm{A}$, then

$C_{0}(\bm{A})=\bm{I}+N(\bm{A})\bm{A}.$ (3.13)

Finally, the following auxiliary lemma will be useful when proving our lower
bound.

######  Lemma 3.6 ([22, Lemma 13]).

Let $L>0,$ let $p$ and $k$ be arbitrary but fixed non-negative integers, and
let $r(y)$ be a polynomial with real-valued coefficients of degree at most
$p$, such that $r(0)=1$. Then:

$\sup_{y\in(0,L]}y|r(y)|^{k}\geq\sup_{y\in[L/(20p^{2}k),L]}y|r(y)|^{k}>\frac{L}{40p^{2}k}.$
(3.14)

We are now ready to state and prove our lower bound.

######  Theorem 3.7.

Let $p,K$ be any two positive integer numbers, and let $L,D>0.$ Then, for any
consistent 1-SCLI algorithm $\mathcal{A}$ acting on instances from
$\mathcal{F}_{L,D}$, initialized at $\bm{u}_{0}=\textbf{0}$ and for which
$N(\bm{A})$ is a matrix polynomial of degree at most $p-1$,

$\sup_{F\in\mathcal{F}_{L,D}}\|F(\bm{u}_{K})\|\geq\frac{LD}{4p\sqrt{5K}}.$

###### Proof.

Similar to [22], we start by showing that

$\bm{u}_{k}=(C_{0}(\bm{A})^{k}-\bm{I})\bm{A}^{-1}\bm{b},$ (3.15)

for all $k\geq 0$. This claim follows by induction on $k$. The base case $k=0$
is immediate. For the inductive step, suppose that Eq. (3.15) holds for some
$k-1\geq 0.$ Then by the definition of 1-SCLI algorithms and the consistency
of $\mathcal{A}$ (Definitions 3.3 and 3.4):

$\displaystyle\bm{u}_{k}$
$\displaystyle=C_{0}(\bm{A})\bm{u}_{k-1}+N(\bm{A})\bm{b}$
$\displaystyle=C_{0}(\bm{A})(C_{0}(\bm{A})^{k-1}-\bm{I})\bm{A}^{-1}\bm{b}+(C_{0}(\bm{A})-\bm{I})\bm{A}^{-1}\bm{b}$
$\displaystyle=(C_{0}(\bm{A})^{k}-\bm{I})\bm{A}^{-1}\bm{b}.$

Therefore, $F(\bm{u}_{k})$ can be expressed as

$F(\bm{u}_{k})=\bm{A}\bm{u}_{k}+\bm{b}=C_{0}(\bm{A})^{k}\bm{b}.$ (3.16)

Let us now specify the “hard instance.” Consider
$F(\bm{u})=\bm{A}\bm{u}+\bm{b},$ where $\bm{A}$ can be expressed as
$\bm{A}=\big{[}\vbox{\Let@\restore@math@cr\default@tag\halign{\hfil$\m@th\scriptstyle#$&$\m@th\scriptstyle{}#$\hfil\cr\eta\bm{I}\>\alpha\bm{I}\\\
-\alpha\bm{I}\>\eta\bm{I}\crcr}}\big{]}$ for some
$\eta,\alpha\in\mathbb{R}_{+}.$ (Observe that such an $F$ can be obtained from
the convex-concave objective
$\phi(\bm{x},\bm{y})=\frac{1}{2}\eta\bm{x}^{T}\bm{x}-\frac{1}{2}\eta\bm{y}^{T}\bm{y}+\alpha\bm{x}^{T}\bm{y}+\bm{b}_{1}^{T}\bm{x}-\bm{b}_{2}^{T}\bm{y},$
where $\bm{x},\bm{y},\bm{b}_{1},\bm{b}_{2}\in\mathbb{R}^{{d}/{2}}$,
$\bm{b}=[{\bm{b}_{1}}^{T}{\bm{b}_{2}}^{T}]^{T}$.)

Let us now argue that for suitably chosen $\eta,\alpha,$ we have that $F$ is
$\frac{1}{L}$-cocoercive. Let $\bm{u}=[\bm{x}^{T}\,\bm{y}^{T}]^{T}$,
$\bar{\bm{u}}=[\bm{\bar{x}}^{T}\,\bm{\bar{y}}^{T}]^{T}$ be an arbitrary pair
of vectors from $\mathbb{R}^{d},$ where
$\bm{x},\bm{y},\bm{\bar{x}},\bm{\bar{y}}\in\mathbb{R}^{d/2}.$ Then

$\left\langle
F(\bm{u})-F(\bar{\bm{u}}),\bm{u}-\bar{\bm{u}}\right\rangle=\eta\|\bm{u}-\bar{\bm{u}}\|^{2}$

and

$\|F(\bm{u})-F(\bar{\bm{u}})\|^{2}=(\eta^{2}+\alpha^{2})\|\bm{u}-\bar{\bm{u}}\|^{2}.$

Hence, for $\eta^{2}+\alpha^{2}\leq L\eta,$ we have $\left\langle
F(\bm{u})-F(\bar{\bm{u}}),\bm{u}-\bar{\bm{u}}\right\rangle\geq\frac{1}{L}\|F(\bm{u})-F(\bar{\bm{u}})\|^{2},$
i.e., $F$ is $\frac{1}{L}$-cocoercive.

To complete the proof, it remains to show that

$\sup_{F\in\mathcal{F}_{L,D}}{\|F(\bm{u}_{K})\|}\geq\frac{LD}{p\sqrt{80K}}.$

To do so, observe that by Eq. (3.16), $\bm{u}_{0}=\textbf{0},$ and
$\bm{u}^{*}=-\bm{A}^{-1}\bm{b},$ we have

$\sup_{F\in\mathcal{F}_{L,D}}\frac{\|F(\bm{u}_{K})\|^{2}}{\|\bm{u}^{*}-\bm{u}_{0}\|^{2}}\geq\sup_{\begin{subarray}{c}\eta\in[0,L],\\\
\alpha\in[0,\sqrt{L\eta-\eta^{2}}]\end{subarray}}\frac{\|C_{0}(\bm{A})^{K}\bm{b}\|^{2}}{\|\bm{A}^{-1}\bm{b}\|^{2}},$

where
$\bm{A}=\big{[}\vbox{\Let@\restore@math@cr\default@tag\halign{\hfil$\m@th\scriptstyle#$&$\m@th\scriptstyle{}#$\hfil\cr\eta\bm{I}\>\alpha\bm{I}\\\
-\alpha\bm{I}\>\eta\bm{I}\crcr}}\big{]}.$ Observe that the characteristic
polynomial of
$\bm{A}=\big{[}\vbox{\Let@\restore@math@cr\default@tag\halign{\hfil$\m@th\scriptstyle#$&$\m@th\scriptstyle{}#$\hfil\cr\eta\bm{I}\>\alpha\bm{I}\\\
-\alpha\bm{I}\>\eta\bm{I}\crcr}}\big{]}$ is:

$\mathrm{det}(\lambda\bm{I}-\mathbf{A})=((\lambda-\eta)^{2}+\alpha^{2})^{{d}/{2}}.$

Hence, $\bm{A}$ has eigenvalues: $\lambda_{1}=\eta+\alpha
i,\,\lambda_{2}=\eta-\alpha i.$ These conjugate eigenvalues have the same
magnitude: $\sqrt{\eta^{2}+\alpha^{2}}$. Accordingly, $\mathbf{A}^{-1}$ has
eigenvalues:
$\lambda_{1}^{\prime}=\frac{1}{\lambda_{1}},\quad\lambda_{2}^{\prime}=\frac{1}{\lambda_{2}}$,
which are also conjugate and equal in magnitude. On the other hand, since
$C_{0}(\bm{A})=\bm{I}+N(\bm{A})\bm{A}$, and, by assumption, $N(\bm{A})$ is a
matrix polynomial of degree at most $p-1$ for some $p\in\mathbb{N}$ with real
coefficients, $C_{0}(\bm{A})$ is a polynomial of $\bm{A}$ with
$C_{0}(\textbf{0}_{d\times d})=\bm{I}$. Therefore, it can be expressed as:

$C_{0}(\bm{A})=\bm{I}+r_{1}\bm{A}+r_{2}\mathbf{A}^{2}+\dots+r_{p}\bm{A}^{p},$

for some real-valued $r_{1},r_{2},r_{3},\dots,r_{p}$. We denote the polynomial
on complex field with the same real-valued coefficients as:
$c_{0}(y)=1+r_{1}y+r_{2}y^{2}+\dots+r_{p}y^{p}$. Then, by the spectral mapping
theorem, the eigenvalues of $C_{0}(\bm{A})$ are: $c_{0}(\lambda_{1})$ and
$c_{0}(\lambda_{2})$, which are again conjugate and have equal norms.
Therefore, we have:

$\displaystyle\sup_{\begin{subarray}{c}\eta\in[0,L]\\\
\alpha\in[0,\sqrt{L\eta-\eta^{2}}]\end{subarray}}\frac{\left\lVert
C_{0}(\mathbf{A})^{K}\bm{b}\right\rVert^{2}}{\left\lVert\mathbf{A}^{-1}\bm{b}\right\rVert^{2}}$
$\displaystyle=\sup_{\begin{subarray}{c}\eta\in[0,L]\\\
\alpha\in[0,\sqrt{L\eta-\eta^{2}}]\end{subarray}}\frac{|c_{0}(\lambda_{1})|^{2K}\left\lVert\bm{b}\right\rVert^{2}}{\frac{1}{|\lambda_{1}|^{2}}\left\lVert\bm{b}\right\rVert^{2}}$
$\displaystyle=\sup_{\begin{subarray}{c}\eta\in[0,L]\\\
\alpha\in[0,\sqrt{L\eta-\eta^{2}}]\end{subarray}}(\eta^{2}+\alpha^{2})|c_{0}(\eta+\alpha
i)|^{2K}.$

To derive the stated lower bound by applying Lemma 3.6, we need to convert the
above expression into a similar form: $\sup_{y\in(0,L]}y|r(y)|^{k}$. Here, we
can observe the difference between the problem we are considering and the
problem discussed in [22]. In [22], the eigenvalues are purely imaginary: $\nu
i$ and $-\nu i$. As a result, the above expression can be written as:
$\sup_{\nu\in(0,L]}\nu^{2}|c_{0}(\nu i)|^{2K}$. By taking the real part of
this term, we get a smaller value
$\sup_{\nu\in(0,L]}\nu^{2}|1-r_{2}\nu^{2}+r_{4}\nu^{4}-\dots+(-1)^{p^{\prime}}r_{2p^{\prime}}\nu^{2p^{\prime}}|^{2K}$,
where $p^{\prime}=\lfloor p/2\rfloor$. Thus, substituting $\nu^{2}$ with $y$,
we get the equation that fits the inequality from Lemma 3.6. However, the same
strategy cannot be applied here since the real part of
$(\eta^{2}+\alpha^{2})|c_{0}(\eta+\alpha i)|^{2K}$ is tangled up with $\alpha$
and $\eta$, hence making it impossible to get an equation of the form
$y|r(y)|^{k}$ by simply taking its real part.

Nevertheless, since we have the extra freedom of choosing $\alpha$, we can
select $\alpha$ carefully to make the real part and imaginary part of
$|c_{0}(\eta+\alpha i)|^{2K}$ separable, while keeping the constant
$\eta^{2}+\alpha^{2}$ large enough. In particular, this can be achieved for:

$\alpha^{2}=L\eta-\eta^{2}.$

Observe that, as long as $\eta\leq L,$ we have
$\alpha\in[0,\sqrt{L\eta-\eta^{2}}],$ as required in the bound above. It
follows that:

$\displaystyle\sup_{\begin{subarray}{c}\eta\in[0,L]\\\
\alpha\in[0,\sqrt{L\eta-\eta^{2}}]\end{subarray}}(\eta^{2}+\alpha^{2})|c_{0}(\eta+\alpha
i)|^{2K}$ $\displaystyle\hskip
72.26999pt\geq\sup_{\eta\in[0,L]}L\eta|c_{0}(\eta+\alpha i)|^{2K}$
$\displaystyle\hskip 72.26999pt=\sup_{\eta\in[0,L]}L\eta|1+r_{1}(\eta+\alpha
i)+\dots+r_{p}(\eta+\alpha i)^{p}|^{2K}.$

Observe that the factor $\alpha$ in the real terms of $(\eta+\alpha i)^{j}$
has only even order, therefore, $\mathrm{Re}(c_{0}(\eta+\alpha i))$ is a
polynomial of $\eta$ and $\alpha^{2}$. Since $\alpha^{2}=L\eta-\eta^{2}$, it
is actually a polynomial of $\eta$ exclusively with real-valued coefficients
of degree at most $p$, which we denote as:
$c^{\prime}_{0}(\eta)=1+r^{\prime}_{1}\eta+r^{\prime}_{2}\eta^{2}+\dots+r^{\prime}_{p}\eta^{p}$.
Therefore, we get:

$\displaystyle\sup_{\eta\in[0,L]}L\eta|c_{0}(\eta+\alpha i)|^{2K}$
$\displaystyle\geq\sup_{\eta\in(0,L]}L\eta|\mathrm{Re}(c_{0}(\eta+\alpha
i))|^{2K}$
$\displaystyle=\sup_{\eta\in(0,L]}L\eta|c_{0}^{\prime}(\eta)|^{2K}.$

By Lemma 3.6 and $\|\bm{A}^{-1}\bm{b}\|=D$, we now have:

$\displaystyle\sup_{F\in\mathcal{F}_{L,D}}\frac{\|F(\bm{u}_{K})\|^{2}}{\|\bm{u}^{*}-\bm{u}_{0}\|^{2}}=\sup_{F\in\mathcal{F}_{L,D}}\frac{\|F(\bm{u}_{K})\|^{2}}{D^{2}}\geq\sup_{\eta\in(0,L]}L\eta|c_{0}^{\prime}(\eta)|^{2K}\geq\frac{L^{2}}{80p^{2}K},$

and the claimed lower bound follows after rearranging the last inequality. ∎

The implications of Theorem 3.7 are as follows. Among all algorithms that
update their iterates as in Eq. (3.11) and use constant (independent of the
iteration count) step sizes $\beta_{i,k},$ GDA is iteration complexity-optimal
for minimizing the norm of a cocoercive operator. This means that other
standard methods such as the extragradient/mirror-prox [29, 39] method, dual
extrapolation [40], or the method of Popov [47], which fall into the same
category, cannot attain a convergence rate for minimizing $\|F(\cdot)\|$ that
is faster than $1/\sqrt{k}.$ Thus, choosing step sizes $\beta_{i,k}$ that
depend on the iteration count is essential for achieving the faster $1/k$ rate
of Halpern’s algorithm. Furthermore, this rate is unimprovable for any of the
typical iterative methods that take the form from Eq. (3.11).

##  4 Conclusion and Future Work

We presented a general and unifying potential function-based framework for
analyzing the convergence of first-order algorithms under the gradient norm
criterion in the settings of convex and min-max optimization. The framework is
intuitive in that it provides an interpretation of the mechanism driving the
convergence as a trade-off between reducing the norm of the gradient and
reducing some notion of an optimality gap.

Many interesting questions for future work remain. In particular, our
framework is primarily applicable to Euclidean setups. Thus, it is an
intriguing question whether it is possible to generalize it to other normed
spaces. We note that beyond the Euclidean setups, the only results with near-
optimal convergence for $\ell_{p}$-normed spaces in the setting of convex
optimization are those for $\ell_{\infty}$ (where an $\ell_{\infty}$ variant
of gradient descent is optimal) and the very recent results for $p\in[1,2]$
that are based on a regularization trick [16]. In a different direction, as
conjectured in Section 2, it appears that fixing either the number of
iterations or the accuracy of the problem in advance is crucial for achieving
near optimal rates in the case of convex objectives, even in Euclidean setups.
Proving such a lower bound would be very interesting, as it would likely
require completely new mathematical techniques. Finally, very little is known
about the convergence in gradient norm in convex-concave min-max optimization
setups, both from the aspect of algorithms and the lower bounds. In
particular, we are not aware of any lower bounds outside of the Euclidean
setup considered here, while, similar as in the case of convex optimization,
the only near-optimal algorithm is based on a regularization trick and applies
only to $p\in[1,2]$ [52].

## References

  * [1] Z. Allen-Zhu and L. Orecchia.  Linear coupling: An ultimate unification of gradient and mirror descent.  In Proc. ITCS’17, 2017.
  * [2] Y. Arjevani, S. Shalev-Shwartz, and O. Shamir.  On lower and upper bounds in smooth and strongly convex optimization.  The Journal of Machine Learning Research, 17(1):4303–4353, 2016\.
  * [3] Y. Arjevani and O. Shamir.  On the iteration complexity of oblivious first-order optimization algorithms.  In Proc. ICML’16, pages 908–916, 2016.
  * [4] H. Attouch and F. Alvarez.  The heavy ball with friction dynamical system for convex constrained minimization problems.  In Optimization, pages 25–35. Springer, 2000.
  * [5] H. Attouch, J. Bolte, and B. F. Svaiter.  Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods.  Mathematical Programming, 137(1):91–129, 2013.
  * [6] H. Attouch, Z. Chbani, J. Fadili, and H. Riahi.  First-order optimization algorithms via inertial systems with Hessian driven damping.  Mathematical Programming, pages 1–43, 2020.
  * [7] H. Attouch, Z. Chbani, and H. Riahi.  Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha\leq 3$.  ESAIM: Control, Optimisation and Calculus of Variations, 25:2, 2019\.
  * [8] H. Attouch, X. Goudou, and P. Redont.  The heavy ball with friction method, I. the continuous dynamical system: global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system.  Communications in Contemporary Mathematics, 2(1):1–34, 2000.
  * [9] H. H. Bauschke and P. L. Combettes.  Convex analysis and monotone operator theory in Hilbert spaces, volume 408.  Springer, 2011.
  * [10] M. Betancourt, M. I. Jordan, and A. C. Wilson.  On symplectic optimization.  arXiv preprint arXiv:1802.03653, 2018.
  * [11] J. Bolte, A. Daniilidis, O. Ley, and L. Mazet.  Characterizations of łojasiewicz inequalities: subgradient flows, talweg, convexity.  Transactions of the American Mathematical Society, 362(6):3319–3363, 2010.
  * [12] S. Bubeck, Y. T. Lee, and M. Singh.  A geometric alternative to Nesterov’s accelerated gradient descent.  arXiv preprint, arXiv:1506.08187, 2015.
  * [13] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford.  Lower bounds for finding stationary points i.  Mathematical Programming, pages 1–50, 2019.
  * [14] E. De Klerk, F. Glineur, and A. B. Taylor.  Worst-case convergence analysis of inexact gradient and newton methods through semidefinite programming performance estimation.  SIAM Journal on Optimization, 30(3):2053–2082, 2020.
  * [15] J. Diakonikolas.  Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.  In Proc. COLT’2020, 2020.
  * [16] J. Diakonikolas and C. Guzmán.  Complementary composite minimization, small gradients in general norms, and applications to regression problems.  arXiv preprint, arXiv:2101.11041, 2021.
  * [17] J. Diakonikolas and M. I. Jordan.  Generalized momentum-based methods: A Hamiltonian perspective.  SIAM Journal on Optimization, 2021.  To appear.
  * [18] J. Diakonikolas and L. Orecchia.  Accelerated extra-gradient descent: A novel, accelerated first-order method.  In Proc. ITCS’18, 2018.
  * [19] J. Diakonikolas and L. Orecchia.  The approximate duality gap technique: A unified theory of first-order methods.  SIAM Journal on Optimization, 29(1):660–689, 2019.
  * [20] Y. Drori and M. Teboulle.  Performance of first-order methods for smooth convex minimization: a novel approach.  Mathematical Programming, 145(1-2):451–482, 2014.
  * [21] D. Drusvyatskiy, M. Fazel, and S. Roy.  An optimal first order method based on optimal quadratic averaging.  SIAM J. Optimiz., 28(1):251–271, 2018.
  * [22] N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar.  Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.  In Proc. COLT’20, 2020.
  * [23] B. Halpern.  Fixed points of nonexpanding maps.  Bulletin of the American Mathematical Society, 73(6):957–961, 1967\.
  * [24] B. Hu and L. Lessard.  Control interpretations for first-order optimization methods.  In Proc. IEEE ACC’17, 2017.
  * [25] M. Ito and M. Fukuda.  Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach.  arXiv preprint arXiv:1912.12004, 2019.
  * [26] D. Kim.  Accelerated proximal point method and forward method for monotone inclusions.  arXiv preprint arXiv:1905.05149, 2019.
  * [27] D. Kim and J. A. Fessler.  Generalizing the optimized gradient method for smooth convex minimization.  SIAM Journal on Optimization, 28(2):1920–1950, 2018.
  * [28] D. Kim and J. A. Fessler.  Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions.  Journal of Optimization Theory and Applications, pages 1–28, 2020\.
  * [29] G. Korpelevich.  Extragradient method for finding saddle points and other problems.  Matekon, 13(4):35–49, 1977.
  * [30] M. Krasnosel’skiı.  Two remarks on the method of successive approximations, uspehi mat.  Nauk, 10:123–127, 1955.
  * [31] W. Krichene, A. Bayen, and P. L. Bartlett.  Accelerated mirror descent in continuous and discrete time.  In Proc. NIPS’15, 2015.
  * [32] L. Lessard, B. Recht, and A. Packard.  Analysis and design of optimization algorithms via integral quadratic constraints.  SIAM Journal on Optimization, 26(1):57–95, 2016.
  * [33] F. Lieder.  On the convergence rate of the halpern-iteration.  Optimization Letters, pages 1–14, 2020.
  * [34] H. Lin, J. Mairal, and Z. Harchaoui.  A universal catalyst for first-order optimization.  In Proc. NIPS’15, 2015.
  * [35] Q. Lin and L. Xiao.  An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization.  In Proc. ICML’14, 2014.
  * [36] S. Lojasiewicz.  Une propriété topologique des sous-ensembles analytiques réels.  Les équations aux dérivées partielles, 117:87–89, 1963\.
  * [37] S. Łojasiewicz.  Ensembles semi-analytiques.  IHES notes, 1965.
  * [38] W. R. Mann.  Mean value methods in iteration.  Proceedings of the American Mathematical Society, 4(3):506–510, 1953.
  * [39] A. Nemirovski.  Prox-method with rate of convergence $O(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.  SIAM Journal on Optimization, 15(1):229–251, 2004.
  * [40] Y. Nesterov.  Dual extrapolation and its applications to solving variational inequalities and related problems.  Mathematical Programming, 109(2):319–344, 2007.
  * [41] Y. Nesterov.  How to make the gradients small.  Optima. Mathematical Optimization Society Newsletter, (88):10–11, 2012.
  * [42] Y. Nesterov.  Gradient methods for minimizing composite functions.  Mathematical Programming, (140(1)):125–161, 2013.
  * [43] Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky.  Primal–dual accelerated gradient methods with small-dimensional relaxation oracle.  Optimization Methods and Software, pages 1–38, 2020.
  * [44] Y. E. Nesterov.  A method for solving the convex programming problem with convergence rate ${O}(1/k^{2})$.  Doklady Akademii Nauk, 269(3):543–547, 1983.
  * [45] J. Nocedal and S. Wright.  Numerical optimization.  Springer Science & Business Media, 2006.
  * [46] Y. Ouyang and Y. Xu.  Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.  Mathematical Programming, Aug 2019.
  * [47] L. D. Popov.  A modification of the Arrow-Hurwicz method for search of saddle points.  Mathematical notes of the Academy of Sciences of the USSR, 28(5):845–848, Nov 1980.
  * [48] S. Sabach and S. Shtern.  A first order method for solving convex bilevel optimization problems.  SIAM Journal on Optimization, 27(2):640–660, 2017.
  * [49] D. Scieur, V. Roulet, F. Bach, and A. D’Aspremont.  Integration methods and accelerated optimization algorithms.  In Proc. NIPS’17, 2017.
  * [50] B. Shi, S. S. Du, M. I. Jordan, and W. J. Su.  Understanding the acceleration phenomenon via high-resolution differential equations.  arXiv preprint, arXiv:1810.08907, 2018.
  * [51] C. Song, Y. Jiang, and Y. Ma.  Unified acceleration of high-order algorithms under general Hölder continuity.  SIAM Journal on Optimization, 2021.  To appear.
  * [52] C. Song, Z. Zhou, Y. Zhou, Y. Jiang, and Y. Ma.  Optimistic dual extrapolation for coherent non-monotone variational inequalities.  Proc. NeurIPS’20, 2020.
  * [53] W. Su, S. Boyd, and E. J. Candes.  A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights.  J. Mach. Learn. Res., 17(153):1–43, 2016.
  * [54] A. B. Taylor, J. M. Hendrickx, and F. Glineur.  Exact worst-case performance of first-order methods for composite convex optimization.  SIAM Journal on Optimization, 27(3):1283–1313, 2017.
  * [55] P. Tseng.  On accelerated proximal gradient methods for convex-concave optimization, 2008.
  * [56] A. Wibisono, A. C. Wilson, and M. I. Jordan.  A variational perspective on accelerated methods in optimization.  In Proceedings of the National Academy of Sciences, 2016.
  * [57] A. C. Wilson, B. Recht, and M. I. Jordan.  A Lyapunov analysis of momentum methods in optimization.  arXiv preprint, arXiv:1611.02635, 2016.
  * [58] C. Zalinescu.  Convex analysis in general vector spaces.  World scientific, 2002.
  * [59] J. Zhang, A. Mokhtari, S. Sra, and A. Jadbabaie.  Direct Runge-Kutta discretization achieves acceleration.  In Proc. NeurIPS’18, 2018.

##  Appendix A Sequence Growth for the Optimized Gradient Method

This section provides a technical lemma used in the proof of Theorem 2.7.

######  Lemma A.1.

Let $\\{\beta_{i,k}\\}_{i\leq k}$, $\\{a_{k}\\}_{k\geq 0},$
$\\{A_{k}\\}_{k\geq 0}$ be the sequences of real numbers that for
$k\in\\{0,\dots,K\\}$ satisfy $\beta_{k,k}=1,$ $A_{k}=\sum_{i=0}^{k}a_{i},$
and

$\displaystyle\beta_{k,K-1}+\frac{a_{k+1}}{A_{K}}=\frac{A_{k+1}}{a_{k+1}},$
(A.1) $\displaystyle
A_{k+1}\beta_{j,k}=A_{k}\beta_{j,k-1}+a_{k+1}\Big{(}\beta_{j,K-1}+\frac{a_{j+1}}{A_{K}}\Big{)}+a_{j+1}\Big{(}\beta_{k,K-1}+\frac{a_{k+1}}{A_{K}}\Big{)}.$
(A.2)

Then the sequence $\\{A_{k}\\}_{k\geq 0}$ can be chosen as

$\begin{cases}A_{k}=1,&\text{ if }k=K;\\\
A_{k}=A_{k+1}\big{[}1+\frac{1}{2}A_{k+1}-\frac{1}{2}\sqrt{A_{k+1}(4+A_{k+1})}\big{]},&\text{
if }0\leq k\leq K-1\end{cases}$ (A.3)

and $\frac{A_{K}}{A_{0}}\geq\frac{(K+2)^{2}}{4}.$

###### Proof.

First, we show that the sequence $\\{A_{k}\\}^{K}_{k=0}$ with $A_{K}=1$ and
that satisfies Eq. (A.1) and Eq. (A.2) has the following recursive
relationship between two successive terms:

$\frac{1}{A_{k-1}}=\frac{1}{A_{k}}+\frac{A_{k}}{a_{k}}$ (A.4)

which is equivalent to:

$\frac{A_{k-1}A_{k}}{a_{k}}=\frac{a_{k}}{A_{k}}.$ (A.5)

Solving for $A_{k-1},$ this relationship leads to Eq. (A.3). We prove the
recursive relationship by induction on $k$. First, for the base case $k=K$,
setting $k=K-1$ in Eq. (2.19), we have:
$\beta_{K-1,K-1}=\frac{A_{K}}{a_{K}}-\frac{a_{K}}{A_{K}}.$ Since we have set
$A_{K}=1$ and $\beta_{K-1,K-1}=1$, it follows that:

$\frac{a_{K}}{A_{K}}=\frac{A_{K}-a_{K}}{a_{K}}=\frac{A_{K-1}}{a_{K}}=\frac{A_{K}A_{K-1}}{a_{K}}$

which coincides with Eq. (A.5).

Now assume that Eq. (A.4) (equivalently, Eq. (A.5)) holds for
$k=K,K-1,\dots,n+1$, and consider $k=n$. Setting $k=n$, $j=n-1$ in Eq. (2.20),
we have:

$A_{n+1}\beta_{n-1,n}=A_{n}\beta_{n-1,n-1}+a_{n+1}\frac{A_{n}}{a_{n}}+a_{n}\frac{A_{n+1}}{a_{n+1}}$

Hence:

$A_{n+1}\beta_{n-1,n}=A_{n}+a_{n+1}\frac{A_{n}}{a_{n}}+a_{n}\frac{A_{n+1}}{a_{n+1}}$
(A.6)

It turns out that we can express $A_{n+1}\beta_{n-1,n}$ using $A_{k}$ for $k$
ranging from $n+1$ to $K$. Let $k=\ell$, $\ell=n+1,n+2,\cdots,K-1$ and $j=n-1$
in Eq. (2.20); then, we get:

$A_{\ell}\beta_{n-1,l-1}=A_{\ell+1}\beta_{n-1,\ell}-a_{\ell+1}\frac{A_{n}}{a_{n}}-a_{n}\frac{A_{\ell+1}}{a_{\ell+1}}.$

This is a recursive relation between $A_{\ell}\beta_{n-1,\ell-1}$ and
$A_{\ell+1}\beta_{n-1,\ell}$. Applying this relation recursively from
$\ell=n+1$ to $\ell=K-1$, we get:

$\displaystyle A_{n+1}\beta_{n-1,n}$
$\displaystyle=A_{K}\beta_{n-1,K-1}-\frac{A_{n}}{a_{n}}(a_{n+2}+\cdots+a_{K})-a_{n}\big{(}\frac{A_{n+2}}{a_{n+2}}+\cdots+\frac{A_{K}}{a_{K}}\big{)}$
$\displaystyle=A_{K}\big{(}\frac{A_{n}}{a_{n}}-\frac{a_{n}}{A_{K}}\big{)}-\frac{A_{n}}{a_{n}}\sum_{\ell=n+1}^{K-1}(A_{\ell+1}-A_{\ell})-a_{n}\sum_{\ell=n+1}^{K-1}\big{(}\frac{1}{A_{\ell}}-\frac{1}{A_{\ell+1}}\big{)}$
$\displaystyle=A_{K}\big{(}\frac{A_{n}}{a_{n}}-\frac{a_{n}}{A_{K}}\big{)}-\frac{A_{n}}{a_{n}}(A_{K}-A_{n+1})-a_{n}\big{(}\frac{1}{A_{n+1}}-\frac{1}{A_{K}}\big{)}$
$\displaystyle=\frac{A_{n}A_{n+1}}{a_{n}}-\frac{a_{n}}{A_{n+1}}.$

The second equation is valid due to our inductive hypothesis for
$k=n+2,n+3,\dots,K$. To derive the last equation, we use that $A_{K}=1$, by
the lemma assumption. Plugging the above equation into Eq. (A.6), we get:

$\frac{A_{n}A_{n+1}}{a_{n}}=A_{n}\frac{a_{n}+a_{n+1}}{a_{n}}+a_{n}\big{(}\frac{A_{n+1}}{a_{n+1}}+\frac{1}{A_{n+1}}\big{)}.$

Using the assumption that
$\frac{1}{A_{n}}=\frac{1}{A_{n+1}}+\frac{A_{n+1}}{a_{n+1}}$, we obtain Eq.
(A.5) for $k=n$, completing the inductive argument.

The recursive relationship between $A_{k}$ and $A_{k+1}$ from Eq. (2.18) be
equivalently written as

$\frac{1}{A_{k}}=\frac{1}{4}\Big{(}2+\frac{4}{A_{k+1}}+2\sqrt{1+\frac{4}{A_{k+1}}}\Big{)}$

Denote $D_{n}=\frac{1}{A_{K-n}}$ for $n\in\\{0,\dots,K\\}.$ Then

$D_{n}=\frac{1}{2}+D_{n-1}+\sqrt{D_{n-1}+\frac{1}{4}}.$ (A.7)

We prove by induction that:

$D_{n}\geq\frac{(n+2)^{2}}{4}.$ (A.8)

As $D_{0}=\frac{1}{A_{K}}=1,$ $D_{0}=\frac{(0+2)^{2}}{4}$ holds by definition.
Now suppose it also for some $n=j$, $0\leq j\leq K-1$. Then:

$\displaystyle D_{j+1}$
$\displaystyle=\frac{1}{2}+D_{j}+\sqrt{D_{j}+\frac{1}{4}}$
$\displaystyle\geq\frac{1}{2}+\frac{1}{4}(j+2+1-1)^{2}+\frac{1}{2}\sqrt{(j+2)^{2}}$
$\displaystyle=\frac{1}{2}+\frac{1}{4}(j+3)^{2}-\frac{1}{2}(j+3)+\frac{1}{4}+\frac{1}{2}(j+2)$
$\displaystyle>\frac{1}{4}(j+3)^{2}$

Thus, $D_{K}=\frac{1}{A_{0}}=\frac{A_{K}}{A_{0}}\geq\frac{(K+2)^{2}}{4},$ as
claimed. ∎