# Variants of the A-HPE and large-step A-HPE algorithms for strongly convex
problems with applications to accelerated high-order tensor methods

M. Marques Alves  Departamento de Matemática, Universidade Federal de Santa
Catarina, Florianópolis, Brazil, 88040-900 (maicon.alves@ufsc.br). The work of
this author was partially supported by CNPq grants no. 304692/2017-4.

###### Abstract

For solving strongly convex optimization problems, we propose and study the
global convergence of variants of the accelerated hybrid proximal
extragradient (A-HPE) and large-step A-HPE algorithms of Monteiro and Svaiter
[21]. We prove _linear_ and the _superlinear_
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ global rates
for the proposed variants of the A-HPE and large-step A-HPE methods,
respectively. The parameter $p\geq 2$ appears in the (high-order) large-step
condition of the new large-step A-HPE algorithm. We apply our results to high-
order tensor methods, obtaining a new inexact (relative-error) tensor method
for (smooth) strongly convex optimization with iteration-complexity
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$. In particular,
for $p=2$, we obtain an inexact proximal-Newton algorithm with fast global
$\mathcal{O}\left(k^{\,-k/3}\right)$ convergence rate.

2000 Mathematics Subject Classification: 90C60, 90C25, 47H05, 65K10.

Key words: Convex optimization, strongly convex, accelerated methods,
proximal-point algorithm, large-step, high-order tensor methods, superlinear
convergence, proximal-Newton method.

##  1 Introduction

The _proximal-point method_ [17, 28] is one of the most popular algorithms for
solving nonsmooth convex optimization problems. For the general problem of
minimizing a convex function $h(\cdot)$, its _exact_ version can be described
by the iteration

$\displaystyle
x^{k+1}=\mbox{arg}\min_{x}\,\left\\{h(x)+\dfrac{1}{2\lambda}\|{x-x^{k}}\|^{2}\right\\},\qquad
k\geq 0,$ (1)

where $\lambda=\lambda_{k+1}>0$ and $x^{k}$ is the current iterate. Motivated
by the fact that in many cases the computation of $x^{k+1}$ is numerically
expensive, several authors have proposed _inexact_ versions of (1). Among
them, inexact proximal-point methods based on _relative-error_ criterion for
the subproblems are currently quite popular. For the more abstract setting of
solving inclusions for maximal monotone operators, this approach was initially
developed by Solodov and Svaiter (see, e.g., [29, 30, 31, 32]), subsequently
studied, from the viewpoint of computational complexity, by Monteiro and
Svaiter (see, e.g., [19, 18, 20, 21]) and has gained a lot of attention by
different authors and research groups (see, e.g., [4, 5, 10, 14, 16]) with
many applications in optimization algorithms and related topics such as
variational inequalities, saddle-point problems, etc.

The starting point of this contribution is [21], where the relative-error
inexact hybrid proximal extragradient (HPE) method [18, 29] was accelerated
for convex optimization, by using Nesterov’s acceleration [22]. The resulting
accelerated HPE-type algorithms, called A-HPE and large-step A-HPE, were
applied to first- and second-order optimization, with iteration-complexities
$\mathcal{O}\left(1/k^{2}\right)$ and $\mathcal{O}\left(1/k^{7/2}\right)$,
respectively. The A-HPE and/or the large-step A-HPE algorithms were recently
studied also in [3, 5, 6, 11, 14, 16], with applications in high-order
optimization, machine learning and tensor methods.

In this paper, we consider the (unconstrained) convex optimization problem

$\displaystyle\min_{x}\,\left\\{h(x):=f(x)+g(x)\right\\},$ (2)

where $f$ is convex and $g$ is _strongly convex_. For solving (2), we propose
and study the convergence rates of variants of the A-HPE and large-step A-HPE
algorithms. The new algorithms are designed especially for strongly convex
problems, and the resulting global convergence rates are _linear_ and
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ for the
variants of the A-HPE and large-step A-HPE, respectively. (the parameter
$p\geq 2$ appears in the high-order large-step condition (see [14, 16].) We
also apply our study to tensor algorithms for high-order convex optimization,
a topic which has been the object of investigation of several authors (see,
e.g., [6, 7, 13, 14, 16, 24, 25] and references therein). The proposed inexact
(relative-error) $p$-th order tensor algorithm has global _superlinear_
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ convergence
rate. We also mention that, for $p=2$ we obtain, as a by-product of our
approach to high-order optimization, a fast $\mathcal{O}\left(k^{-k/3}\right)$
proximal-Newton method for strongly convex optimization.

The main contributions of this paper can be summarized as follows:

  * (i)

A variant of the A-HPE algorithm for strongly convex objectives (Algorithm 1)
and its iteration-complexity analysis as in Theorems 2.6 and 2.9.

  * (ii)

A large-step A-HPE-type algorithm for strongly convex problems (Algorithm 2)
with a high-order large-step condition and its iteration-complexity (see
Theorem 3.3).

  * (iii)

A new inexact high-order tensor algorithm (Algorithm 3) for strongly convex
problems and its global convergence analysis (see Theorem 4.4). Here and in
item (ii) above we highlight the fast global convergence rate
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$.

  * (iv)

An inexact relative-error forward-backward algorithm for strongly convex
optimization (see Algorithm 4 and Theorem 5.4).

Additionally to the contributions described in (i)–(iv) above, we refer the
reader to the remarks/comments following Algorithms 1, 2, 3 and 4.

Some previous contributions. The A-HPE and forward-backward methods for
strongly convex problems were also recently studied in [5]. Based on the A-HPE
framework, $p$th-order tensor methods with iteration-complexity
$\mathcal{O}\left(1/k^{\frac{3p+1}{2}}\right)$ were studied in [3, 6, 11, 14,
16]. When combined with restart techniques, improved rates for the uniformly-
and/or strongly convex case were also obtained in [3, 11] (see also [15]). We
also mention that local superlinear convergence rates for tensor methods were
obtained in [7]. Tensor and/or second-order schemes were also recently studied
in [8, 9, 12, 13].

General notation. We denote by $\mathcal{H}$ a finite-dimensional real vector
space with inner product $\langle\cdot,\cdot\rangle$ and induced norm
$\|{\cdot}\|=\sqrt{\langle\cdot,\cdot\rangle}$. The _$\varepsilon$
-subdifferential_ and the _subdifferential_ of a convex function
$g:\mathcal{H}\to(-\infty,\infty]$ at $x\in\mathcal{H}$ are defined as
$\partial_{\varepsilon}g(x):=\\{u\in\mathcal{H}\;|\;g(y)\geq g(x)+\langle
u,y-x\rangle-\varepsilon\quad\forall y\in\mathcal{H}\\}$ and $\partial
g(x):=\partial_{0}g(x)$, respectively. For additional details on standard
notations and definitions of convex analysis we refer the reader to the
reference [27]. Recall that $g:\mathcal{H}\to(-\infty,\infty]$ is
$\mu$-strongly convex if $\mu>0$ and, for all $x,y\in\mathcal{H}$,

$\displaystyle g(\lambda x+(1-\lambda)y)\leq\lambda
g(x)+(1-\lambda)g(y)-\dfrac{1}{2}\mu\lambda(1-\lambda)\|{x-y}\|^{2},\qquad\forall\lambda\in[0,1].$
(3)

##  2 A variant of the A-HPE algorithm for strongly convex problems

In this section, we consider the convex optimization problem (2), i.e.,

$\displaystyle\min_{x\in\mathcal{H}}\,\\{h(x):=f(x)+g(x)\\},$

where $f,g:\mathcal{H}\to(-\infty,\infty]$ are proper, closed and convex
functions, $\mbox{dom}\,h\neq\emptyset$, and $g$ is $\mu$-strongly convex, for
some $\mu>0$. We will denote by $x^{*}$ the unique solution of (2).

Next we present the main algorithm of this section for solving (2), whose the
complexity analysis will be presented in Theorems 2.6 and 2.9.

######  Algorithm 1.

A variant of the A-HPE algorithm for solving the (strongly convex) problem (2)
0) Choose $x^{0},y^{0}\in\mathcal{H}$, $\sigma\in[0,1]$, let $A_{0}=0$ and set
$k=0$. 1) Compute $\lambda_{k+1}>0$ and
$(y^{k+1},v^{k+1},\varepsilon_{k+1})\in\mathcal{H}\times\mathcal{H}\times\mathbb{R}_{++}$
such that $\displaystyle\begin{aligned}
&v^{k+1}\in\partial_{\varepsilon_{k+1}}f(y^{k+1})+\partial
g(y^{k+1}),\\\\[8.53581pt]
&\dfrac{\|{\lambda_{k+1}v^{k+1}+y^{k+1}-\widetilde{x}^{k}}\|^{2}}{1+\lambda_{k+1}\,\mu}+2\lambda_{k+1}\varepsilon_{k+1}\leq\sigma^{2}\|{y^{k+1}-\widetilde{x}^{k}}\|^{2},\end{aligned}$
(4) where $\displaystyle\widetilde{x}^{k}=\left(\dfrac{a_{k+1}-\mu
A_{k}\lambda_{k+1}}{A_{k}+a_{k+1}}\right)x^{k}+\left(\dfrac{A_{k}+\mu
A_{k}\lambda_{k+1}}{A_{k}+a_{k+1}}\right)y^{k},$ (5) $\displaystyle
a_{k+1}=\dfrac{(1+2\mu A_{k})\lambda_{k+1}+\sqrt{(1+2\mu
A_{k})^{2}\lambda_{k+1}^{2}+4(1+\mu A_{k})A_{k}\lambda_{k+1}}}{2}.$ (6) 2) Let
$\displaystyle A_{k+1}=A_{k}+a_{k+1},$ (7) $\displaystyle
x^{k+1}=\left(\dfrac{1+\mu A_{k}}{1+\mu A_{k+1}}\right)x^{k}+\left(\dfrac{\mu
a_{k+1}}{1+\mu A_{k+1}}\right)y^{k+1}-\left(\dfrac{a_{k+1}}{1+\mu
A_{k+1}}\right)v^{k+1}.$ (8) 3) Set $k=k+1$ and go to step 1.

Next we make some remarks about Algorithm 1:

  * (i)

By letting $\mu=0$ in Algorithm 1, we obtain a special instance of the A-HPE
algorithm of Monteiro and Svaiter (see [21, Section 3]), whose global
convergence rate is $\mathcal{O}\left(1/k^{2}\right)$ (see [21, Theorem 3.8]).
On the other hand, thanks to the strong-convexity assumption on $g$, in
Theorems 2.6 and 2.9 we obtain _linear convergence_ for Algorithm 1. We will
also study a _high-order_ large-step version of Algorithm 1 (see Algorithm 2
in Section 3), for which _superlinear_
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ global
convergence rates are proved, where $p\geq 2$. Applications of the latter
result to high-order tensor methods for convex optimization will also be
discussed in Section 3.

  * (ii)

Since the cost of computing $\widetilde{x}^{k},a_{k+1},A_{k+1}$ and $x^{k+1}$
as in (5)–(8) is negligible (from a computational viewpoint), it follows that
the computational burden of Algorithm 1 is represented by the computation of
$\lambda_{k+1}>0$ and $(y^{k+1},v^{k+1},\varepsilon_{k+1})$ as in
(LABEL:eq:alg_err). In this regard, note that if $\mbox{prox}_{\lambda
h}:=(\lambda\partial h+I)^{-1}$ of $h$ is computable, for $\lambda>0$, then
$\lambda_{k+1}:=\lambda$ and
$(y^{k+1},v^{k+1},\varepsilon_{k+1}):=\left(\mbox{prox}_{\lambda
h}(\widetilde{x}^{k}),\frac{\widetilde{x}^{k}-y^{k+1}}{\lambda_{k+1}},0\right)$
clearly satisfy the conditions in (LABEL:eq:alg_err) with $\sigma=0$. On the
other hand, in the more general setting of $\sigma>0$, Algorithm 1 can be used
both as a framework for the design and analysis of practical algorithms [21]
and as a _bilevel_ method, in which the inequality in (LABEL:eq:alg_err) is
used as a stopping criterion for some _inner_ algorithm applied to the
regularized inclusion $0\in\lambda\partial h(x)+x-\widetilde{x}^{k}$. In this
case, note that the _error-criterion_ in (LABEL:eq:alg_err) is _relative_ and
controlled by the parameter $\sigma\in(0,1]$.

  * (iii)

We emphasize that the inequality in (LABEL:eq:alg_err) is specially tailored
for strongly convex problems, in the sense that it is more general than the
usual inequality appearing in relative-error HPE-type methods (see, e.g., [1,
10, 18, 20, 29]), which in the context of this paper would read as

$\|{\lambda_{k+1}v^{k+1}+y^{k+1}-\widetilde{x}^{k}}\|^{2}+2\lambda_{k+1}\varepsilon_{k+1}\leq\sigma^{2}\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}.$

  * (iv)

We also mention that Algorithm 1 is closely related to a variant of the A-HPE
for strongly convex objectives presented and studied in [5, Section 5]. In
this paper, by taking an approach similar to the one which was considered in
[21, 23], we obtain global convergence rates for Algorithm 1 in terms of
_function values_ , _sequences_ and _(sub-)gradients_ (see Theorems 2.6 and
2.9 below). In contrast to [5], in this paper we also consider a _large-step_
version of Algorithm 1, namely Algorithm 2, for which the (global) superlinear
$\mathcal{O}\left(k^{-k\,\left(\frac{p-1}{p+1}\right)}\right)$ convergence
rate is proved (see Theorems 3.3 and 4.4 below).

  * (v)

We note that condition (6) yields

$\displaystyle\dfrac{(1+\mu
A_{k})A_{k+1}\lambda_{k+1}}{a_{k+1}^{2}}+\dfrac{\mu
A_{k}\lambda_{k+1}}{a_{k+1}}=1.$ (9)

Indeed, substitution of $A_{k+1}$ by $A_{k}+a_{k+1}$ (see (7)) and some simple
algebra give that (9) is equivalent to

$\displaystyle a_{k+1}^{2}-(1+2\mu A_{k})\lambda_{k+1}a_{k+1}-(1+\mu
A_{k})A_{k}\lambda_{k+1}=0.$ (10)

Note now that $a_{k+1}$ as in (6) is exactly the largest root of the quadratic
equation in (10).

  * (vi)

Using (7) and the fact that $A_{0}=0$ (see step 0) we obtain
$A_{1}=A_{0}+a_{1}=a_{1}$. On the other hand, direct substitution of $A_{0}=0$
in (6) with $k=0$ yields $a_{1}=\lambda_{1}$. As a consequence, we conclude
that

$\displaystyle A_{1}=a_{1}=\lambda_{1}.$ (11)

In what follows in this section, we will analyze convergence rates of
Algorithm 1. To this end, we first define $\gamma_{k}(\cdot)$ and
$\Gamma_{k}(\cdot)$ as, for all $x\in\mathcal{H}$,

$\displaystyle\gamma_{k}(x)=h(y^{k})+\langle
v^{k},x-y^{k}\rangle-\varepsilon_{k}+\dfrac{\mu}{2}\|{x-y^{k}}\|^{2}\qquad(k\geq
1)$ (12)

and

$\displaystyle\Gamma_{0}(x)=0\;\;\mbox{and},\;\mbox{for}\;k\geq
1,\;\;\Gamma_{k}(x)=\sum_{j=1}^{k}\,\dfrac{a_{j}}{A_{k}}\gamma_{j}(x).$ (13)

Note that

$\displaystyle\nabla\gamma_{k}(x)=v^{k}+\mu(x-y^{k})\;\;\mbox{and}\;\;\nabla^{2}\gamma_{k}(x)=\mu
I$ (14)

and observe that $A_{k}$ ($k=0,1,\dots$) as in Algorithm 1 satisfies

$\displaystyle A_{0}=0\;\;\mbox{and},\;\mbox{for}\;k\geq
1,\;\;A_{k}=\sum_{j=1}^{k}\,a_{j}.$ (15)

From (13)–(15) we obtain, for $k\geq 1$,

$\displaystyle\nabla^{2}\Gamma_{k}(x)=\mu I,\qquad x\in\mathcal{H}.$ (16)

Note also that the following holds trivially from (13) and (15): for all
$k\geq 0$,

$\displaystyle A_{k+1}\Gamma_{k+1}=A_{k}\Gamma_{k}+a_{k+1}\gamma_{k+1}.$ (17)

Define also, for all $k\geq 0$,

$\displaystyle\beta_{k}=\inf_{x\in\mathcal{H}}\left\\{A_{k}\Gamma_{k}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}\right\\}.$
(18)

Note that $\beta_{0}=0$.

The following three technical lemmas will be useful to prove the first result
on the iteration-complexity of Algorithm 1, namely Proposition 2.4 below.

######  Lemma 2.1.

Let $\gamma_{k}(\cdot)$ and $\Gamma_{k}(\cdot)$ be as in (12) and (13),
respectively. The following holds:

  * _(a)_

For all $k\geq 1$, we have $\gamma_{k}(x)\leq h(x),\quad\forall
x\in\mathcal{H}$.

  * _(b)_

For all $k\geq 0$, we have
$x^{k}=\arg\min_{x\in\mathcal{H}}\\{A_{k}\Gamma_{k}(x)+\frac{1}{2}\|{x-x^{0}}\|^{2}\\}$.

###### Proof.

(a) In view of the inclusion in (LABEL:eq:alg_err) we have, for all $k\geq 1$,
$v^{k}=r^{k}+s^{k}$, where $r^{k}\in\partial_{\varepsilon_{k}}f(y^{k})$ and
$s^{k}\in\partial g(y^{k})$. Using the assumption that $g$ is $\mu$-strongly
convex and the definition of the $\varepsilon$-subdifferential of $f$ we
obtain, for all $x\in\mathcal{H}$,

$\displaystyle f(x)\geq f(y^{k})+\langle
r^{k},x-y^{k}\rangle-\varepsilon_{k},$ $\displaystyle g(x)\geq
g(y^{k})+\langle s^{k},x-y^{k}\rangle+\dfrac{\mu}{2}\|{x-y^{k}}\|^{2},$

which in turn combined with the definition of $h(\cdot)$ in (2), the fact that
$v^{k}=r^{k}+s^{k}$ and (12) yields the desired result.

(b) Let us proceed by induction on $k\geq 0$. The result is trivially true for
$k=0$ (since $A_{0}\Gamma_{0}=0$). Assume now that it is true for some $k\geq
0$, i.e., assume that
$x^{k}=\arg\min_{x}\\{A_{k}\Gamma_{k}(x)+\frac{1}{2}\|{x-x^{0}}\|^{2}\\}$.
Using the latter identity, (16)–(18) and Taylor’s theorem we find

$\displaystyle A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}$
$\displaystyle=A_{k}\Gamma_{k}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}+a_{k+1}\gamma_{k+1}(x)$
$\displaystyle=\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x).$ (19)

From the definition of $\gamma_{k+1}(\cdot)$ (see (12)) and some simple
calculus one can check that $x^{k+1}$ as in (8) is exactly the (unique)
minimizer of $x\mapsto\left(\frac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x)$. Hence, from this
fact and (19) we obtain that
$x^{k+1}=\arg\min_{x\in\mathcal{H}}\\{A_{k+1}\Gamma_{k+1}(x)+\frac{1}{2}\|{x-x^{0}}\|^{2}\\}$,
completing the induction argument. ∎

######  Lemma 2.2.

Consider the sequences evolved by _Algorithm 1_. The following holds for all
$x\in\mathcal{H}$:

  * _(a)_

For all $k\geq 0$,

$\displaystyle
A_{k}\Gamma_{k}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}=\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}.$

  * _(b)_

For all $k\geq 0$,

$\displaystyle
A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}=\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x).$

  * _(c)_

For all $k\geq 0$,

$\displaystyle
A_{k}h(y^{k})+A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}\geq\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x)+A_{k}\gamma_{k+1}(y^{k}).$

###### Proof.

(a) First note that the result is trivial for $k=0$, since $\beta_{0}=A_{0}=0$
and $\Gamma_{0}=0$. Now note that in view of (16) we obtain, for $k\geq 1$,

$\nabla^{2}\left(A_{k}\Gamma_{k}(\cdot)+\dfrac{1}{2}\|{\cdot-x^{0}}\|^{2}\right)(x)=1+\mu
A_{k}.$

Using the latter identity, Lemma 2.1(b), (18) and Taylor’s theorem we find

$\displaystyle A_{k}\Gamma_{k}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}$
$\displaystyle=\underbrace{A_{k}\Gamma_{k}(x^{k})+\dfrac{1}{2}\|{x^{k}-x^{0}}\|^{2}}_{\beta_{k}}+\dfrac{1}{2}\langle(1+\mu
A_{k})(x-x^{k}),x-x^{k}\rangle$ $\displaystyle=\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}.$

(b) From (17) and item (a), we obtain, for all $k\geq 0$,

$\displaystyle A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}$
$\displaystyle=A_{k}\Gamma_{k}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}+a_{k+1}\gamma_{k+1}(x)$
$\displaystyle=\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x).$

(c) From (b) and Lemma 2.1(a) with $k=k+1$ and $x=y^{k}$,

$\displaystyle
A_{k}h(y^{k})+A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}$
$\displaystyle=\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x)+A_{k}h(y^{k})$
$\displaystyle\geq\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x)+A_{k}\gamma_{k+1}(y^{k}).$

∎

######  Lemma 2.3.

Consider the sequences evolved by _Algorithm 1_. The following holds:

  * _(a)_

For all $k\geq 0$ and $x\in\mathcal{H}$,

$\displaystyle
a_{k+1}\gamma_{k+1}(x)+A_{k}\gamma_{k+1}(y^{k})=A_{k+1}\gamma_{k+1}(\widetilde{x})+\left(\dfrac{\mu\,a_{k+1}A_{k}}{2A_{k+1}}\right)\|{x-y^{k}}\|^{2},$

where

$\displaystyle\widetilde{x}:=\dfrac{a_{k+1}}{A_{k+1}}x+\dfrac{A_{k}}{A_{k+1}}y^{k}.$
(20)

  * _(b)_

For all $k\geq 0$ and $x\in\mathcal{H}$,

$\displaystyle
A_{k}h(y^{k})+A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}\geq\beta_{k}+A_{k+1}\Big{[}\gamma_{k+1}(\widetilde{x})+\Delta_{k}\Big{]},$

where, for all $k\geq 0$, $\widetilde{x}$ is as in (20) and

$\displaystyle\Delta_{k}:=\left(\dfrac{(1+\mu
A_{k})A_{k+1}}{2a_{k+1}^{2}}\right)\|{\widetilde{x}-z^{k}}\|^{2}+\left(\dfrac{\mu
A_{k}}{2a_{k+1}}\right)\|{\widetilde{x}-y^{k}}\|^{2},$ (21) $\displaystyle
z^{k}:=\dfrac{a_{k+1}}{A_{k+1}}x^{k}+\dfrac{A_{k}}{A_{k+1}}y^{k}.$ (22)

  * _(c)_

For all $k\geq 0$,

$\displaystyle\Delta_{k}$
$\displaystyle=\dfrac{1}{2\lambda_{k+1}}\left[\|{\widetilde{x}-\widetilde{x}^{k}}\|^{2}+\left(\dfrac{\mu(1+\mu
A_{k})\lambda_{k+1}^{2}A_{k}}{a_{k+1}A_{k+1}}\right)\|{x^{k}-y^{k}}\|^{2}\right],$
(23)

where $\widetilde{x}$ is as in (20).

  * _(d)_

For all $k\geq 0$ and $x\in\mathcal{H}$,

$\displaystyle
A_{k}h(y^{k})+A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}\geq\beta_{k}+A_{k+1}h(y^{k+1})$
$\displaystyle+\left(\dfrac{1-\sigma^{2}}{2}\right)\left(\dfrac{A_{k+1}}{\lambda_{k+1}}\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}\right)$
$\displaystyle+\left(\dfrac{\mu(1+\mu
A_{k})\lambda_{k+1}A_{k}}{2a_{k+1}}\right)\|{x^{k}-y^{k}}\|^{2}.$

###### Proof.

(a) First recall that (see (12))

$\displaystyle\gamma_{k+1}(x)=\underbrace{h(y^{k+1})+\langle
v^{k+1},x-y^{k+1}\rangle-\varepsilon_{k+1}}_{\ell_{k+1}(x)}+\dfrac{\mu}{2}\|{x-y^{k+1}}\|^{2},\qquad\forall
x\in\mathcal{H}.$ (24)

Let $p=\frac{a_{k+1}}{A_{k+1}}$, $q=\frac{A_{k}}{A_{k+1}}$ and note that
$p,q\geq 0$, $p+q=1$ and $\widetilde{x}=px+qy^{k}$. Since $\ell_{k+1}(\cdot)$
is affine, we find

$\displaystyle\ell_{k+1}(\widetilde{x})=\ell_{k+1}(px+qy^{k})$
$\displaystyle=p\ell_{k+1}(x)+q\ell_{k+1}(y^{k})$
$\displaystyle=\dfrac{1}{A_{k+1}}\left[a_{k+1}\ell_{k+1}(x)+A_{k}\ell_{k+1}(y^{k})\right].$
(25)

On the other hand, using the well-know identity
$\|{pz+qw}\|^{2}=p\|{z}\|^{2}+q\|{w}\|^{2}-pq\|{z-w}\|^{2}$, for all
$z,w\in\mathcal{H}$, we also find

$\displaystyle\|{\widetilde{x}-y^{k+1}}\|^{2}$
$\displaystyle=\|{p(x-y^{k+1})+q(y^{k}-y^{k+1})}\|^{2}$
$\displaystyle=p\|{x-y^{k+1}}\|^{2}+q\|{y^{k}-y^{k+1}}\|^{2}-pq\|{x-y^{k}}\|^{2}$
$\displaystyle=\dfrac{1}{A_{k+1}}\left[a_{k+1}\|{x-y^{k+1}}\|^{2}+A_{k}\|{y^{k}-y^{k+1}}\|^{2}-\left(\dfrac{a_{k+1}A_{k}}{A_{k+1}}\right)\|{x-y^{k}}\|^{2}\right].$
(26)

Combining (24)–(26), we then obtain

$\displaystyle\gamma_{k+1}(\widetilde{x})$
$\displaystyle=\ell_{k+1}(\widetilde{x})+\dfrac{\mu}{2}\left\|\widetilde{x}-y^{k+1}\right\|^{2}$
$\displaystyle=\dfrac{1}{A_{k+1}}\left[a_{k+1}\left(\ell_{k+1}(x)+\dfrac{\mu}{2}\|{x-y^{k+1}}\|^{2}\right)+A_{k}\left(\ell_{k+1}(y^{k})+\dfrac{\mu}{2}\|{y^{k}-y^{k+1}}\|^{2}\right)-\left(\dfrac{\mu
a_{k+1}A_{k}}{2A_{k+1}}\right)\|{x-y^{k}}\|^{2}\right]$
$\displaystyle=\dfrac{1}{A_{k+1}}\left[a_{k+1}\gamma_{k+1}(x)+A_{k}\gamma_{k+1}(y^{k})-\left(\dfrac{\mu
a_{k+1}A_{k}}{2A_{k+1}}\right)\|{x-y^{k}}\|^{2}\right],$

which is clearly equivalent to the desired identity.

(b) First note that in view of (20) and (22) we have
$\widetilde{x}-z^{k}=\frac{a_{k+1}}{A_{k+1}}(x-x^{k})$ and, analogously, we
also have tilde $x-y^{k}=\frac{a_{k+1}}{A_{k+1}}(x-y^{k})$. Hence,

$\displaystyle\|{x-x^{k}}\|^{2}=\dfrac{A_{k+1}^{2}}{a_{k+1}^{2}}\|{\widetilde{x}-z^{k}}\|^{2}\;\;\;\mbox{and}\;\;\;\|{x-y^{k}}\|^{2}=\dfrac{A_{k+1}^{2}}{a_{k+1}^{2}}\|{\widetilde{x}-y^{k}}\|^{2}.$
(27)

Using Lemma 2.2(c) and item (a) we find

$\displaystyle
A_{k}h(y^{k})+A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}$
$\displaystyle\geq\beta_{k}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+a_{k+1}\gamma_{k+1}(x)+A_{k}\gamma_{k+1}(y^{k})$
$\displaystyle=\beta_{k}+A_{k+1}\gamma_{k+1}(\widetilde{x})$
$\displaystyle\hskip 28.45274pt+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}+\left(\dfrac{\mu\,a_{k+1}A_{k}}{2A_{k+1}}\right)\|{x-y^{k}}\|^{2},$

which in turn combined with (27) and (21) finishes the proof of item (b).

(c) First let $p=\frac{(1+\mu A_{k})A_{k+1}\lambda_{k+1}}{a_{k+1}^{2}}$,
$q=\dfrac{\mu A_{k}\lambda_{k+1}}{a_{k+1}}$ and note that $p,q\geq 0$ and, in
view of (9), $p+q=1$. From (21) and the above definitions of $p$ and $q$, we
obtain

$\displaystyle\Delta_{k}$ $\displaystyle=\left(\dfrac{(1+\mu
A_{k})A_{k+1}}{2a_{k+1}^{2}}\right)\|{\widetilde{x}-z^{k}}\|^{2}+\left(\dfrac{\mu
A_{k}}{2a_{k+1}}\right)\|{\widetilde{x}-y^{k}}\|^{2}$
$\displaystyle=\dfrac{1}{2\lambda_{k+1}}\left[p\|{\widetilde{x}-z^{k}}\|^{2}+q\|{\widetilde{x}-y^{k}}\|^{2}\right]$
$\displaystyle=\dfrac{1}{2\lambda_{k+1}}\left[\|{\widetilde{x}-(pz^{k}+qy^{k})}\|^{2}+pq\|{y^{k}-z^{k}}\|^{2}\right],$
(28)

where we also used the well-known identity
$p\|{z}\|^{2}+q\|{w}\|^{2}=\|{pz+qw}\|^{2}+pq\|{z-w}\|^{2}$, for
$z,w\in\mathcal{H}$.

Using (22), the definitions of $p,q$, the fact that $p+q=1$, (5) and (7), and
some simple computations, we find

$\displaystyle pz^{k}+qy^{k}$
$\displaystyle=(1-q)\left(\dfrac{a_{k+1}}{A_{k+1}}x^{k}+\dfrac{A_{k}}{A_{k+1}}y^{k}\right)+qy^{k}$
$\displaystyle=(1-q)\dfrac{a_{k+1}}{A_{k+1}}x^{k}+\left(\dfrac{A_{k}}{A_{k+1}}+q\left(1-\dfrac{A_{k}}{A_{k+1}}\right)\right)y^{k}$
$\displaystyle=(1-q)\dfrac{a_{k+1}}{A_{k+1}}x^{k}+\left(\dfrac{A_{k}}{A_{k+1}}+q\dfrac{a_{k+1}}{A_{k+1}}\right)y^{k}$
$\displaystyle=\left(1-\dfrac{\mu
A_{k}\lambda_{k+1}}{a_{k+1}}\right)\dfrac{a_{k+1}}{A_{k+1}}x^{k}+\left(\dfrac{A_{k}}{A_{k+1}}+\left(\dfrac{\mu
A_{k}\lambda_{k+1}}{a_{k+1}}\right)\dfrac{a_{k+1}}{A_{k+1}}\right)y^{k}$
$\displaystyle=\left(\dfrac{a_{k+1}-\mu
A_{k}\lambda_{k+1}}{A_{k+1}}\right)x^{k}+\left(\dfrac{A_{k}+\mu
A_{k}\lambda_{k+1}}{A_{k+1}}\right)y^{k}$ $\displaystyle=\widetilde{x}^{k}.$
(29)

On the other hand, using again (22) and the definitions of $p,q$, we also
obtain

$\displaystyle pq\|{y^{k}-z^{k}}\|^{2}$ $\displaystyle=\left(\frac{(1+\mu
A_{k})A_{k+1}\lambda_{k+1}}{a_{k+1}^{2}}\right)\left(\dfrac{\mu
A_{k}\lambda_{k+1}}{a_{k+1}}\right)\dfrac{a_{k+1}^{2}}{A_{k+1}^{2}}\|{x^{k}-y^{k}}\|^{2}$
$\displaystyle=\left(\dfrac{\mu(1+\mu
A_{k})\lambda_{k+1}^{2}A_{k}}{a_{k+1}A_{k+1}}\right)\|{x^{k}-y^{k}}\|^{2}.$
(30)

The desired result now follows directly from (28), (29) and (30).

(d) From items (b) and (c),

$\displaystyle
A_{k}h(y^{k})+A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}\geq\beta_{k}$
$\displaystyle+A_{k+1}\Big{[}\gamma_{k+1}(\widetilde{x})+\dfrac{1}{2\lambda_{k+1}}\|{\widetilde{x}-\widetilde{x}^{k}}\|^{2}\Big{]}$
$\displaystyle+\left(\dfrac{\mu(1+\mu
A_{k})\lambda_{k+1}A_{k}}{2a_{k+1}}\right)\|{x^{k}-y^{k}}\|^{2}.$ (31)

From (12),

$\displaystyle\gamma_{k+1}(\widetilde{x})+\dfrac{1}{2\lambda_{k+1}}\|{\widetilde{x}-\widetilde{x}^{k}}\|^{2}$
$\displaystyle=h(y^{k+1})$ $\displaystyle\hskip 19.91684pt+\underbrace{\langle
v^{k+1},\widetilde{x}-y^{k+1}\rangle+\dfrac{\mu}{2}\|{\widetilde{x}-y^{k+1}}\|^{2}-\varepsilon_{k+1}+\dfrac{1}{2\lambda_{k+1}}\|{\widetilde{x}-\widetilde{x}^{k}}\|^{2}}_{=:q_{k+1}(\widetilde{x})}.$
(32)

On the other hand, from Lemma A.2(c) applied to $q_{k+1}(\cdot)$ and
(LABEL:eq:alg_err),

$\displaystyle
q_{k+1}(\widetilde{x})\geq\left(\dfrac{1-\sigma^{2}}{2\lambda_{k+1}}\right)\|{y^{k+1}-\widetilde{x}^{k}}\|^{2},$

which in turn combined with (32) gives

$\displaystyle\gamma_{k+1}(\widetilde{x})+\dfrac{1}{2\lambda_{k+1}}\|{\widetilde{x}-\widetilde{x}^{k}}\|^{2}\geq
h(y^{k+1})+\left(\dfrac{1-\sigma^{2}}{2\lambda_{k+1}}\right)\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}.$

The desired result now follows by the substitution of the latter inequality in
(2). ∎

Next is our first result on the iteration-complexity of Algorithm 1. Item (b)
follows trivially from item (a), which will be derived from Lemmas 2.1, 2.2
and 2.3. The main results on the iteration-complexity of Algorithm 1 will then
be presented in Theorem 2.6 below.

######  Proposition 2.4.

Consider the sequences evolved by _Algorithm 1_, let $x^{*}$ denote the
(unique) solution of (2) and let

$\displaystyle d_{0}:=\|{x^{*}-x^{0}}\|.$ (33)

The following holds:

  * _(a)_

For all $k\geq 1$ and $x\in\mathcal{H}$,

$\displaystyle
A_{k}\left[h(y^{k})-h(x)\right]+\left(\dfrac{1-\sigma^{2}}{2}\right)\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}$
$\displaystyle\hskip 28.45274pt+\sum_{j=1}^{k}\,\left(\dfrac{\mu(1+\mu
A_{j-1})\lambda_{j}A_{j-1}}{2a_{j}}\right)\|{x^{j-1}-y^{j-1}}\|^{2}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}\leq\dfrac{1}{2}\|{x-x^{0}}\|^{2}.$

  * _(b)_

If $\sigma<1$, for all $k\geq 1$,

$\displaystyle\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}\leq\dfrac{d_{0}^{2}}{1-\sigma^{2}},\qquad\forall
k\geq 1.$ (34)

###### Proof.

(a) From Lemma 2.3(d) and the definition of $\beta_{k+1}$ – see (18) – we
obtain, for all $k\geq 0$,

$\displaystyle A_{k}h(y^{k})+\beta_{k+1}\geq\beta_{k}+A_{k+1}h(y^{k+1})$
$\displaystyle+\left(\dfrac{1-\sigma^{2}}{2}\right)\left(\dfrac{A_{k+1}}{\lambda_{k+1}}\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}\right)$
$\displaystyle+\left(\dfrac{\mu(1+\mu
A_{k})\lambda_{k+1}A_{k}}{2a_{k+1}}\right)\|{x^{k}-y^{k}}\|^{2},$

and so, for all $k\geq 0$,

$\displaystyle\underbrace{\sum_{j=0}^{k}\,\left[\beta_{j+1}-\beta_{j}\right]}_{\beta_{k+1}-\beta_{0}}\geq\underbrace{\sum_{j=0}^{k}\,\left[A_{j+1}h(y^{j+1})-A_{j}h(y^{j})\right]}_{A_{k+1}h(y^{k+1})-A_{0}h(y^{0})}$
$\displaystyle+\left(\dfrac{1-\sigma^{2}}{2}\right)\sum_{j=0}^{k}\,\dfrac{A_{j+1}}{\lambda_{j+1}}\|{y^{j+1}-\widetilde{x}^{j}}\|^{2}$
$\displaystyle+\sum_{j=0}^{k}\,\left(\dfrac{\mu(1+\mu
A_{j})\lambda_{j+1}A_{j}}{2a_{j+1}}\right)\|{x^{j}-y^{j}}\|^{2},$

which, since $\beta_{0}=A_{0}=0$, yields, for all $k\geq 0$,

$\displaystyle\beta_{k+1}\geq
A_{k+1}h(y^{k+1})+\left(\dfrac{1-\sigma^{2}}{2}\right)\sum_{j=1}^{k+1}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}+\sum_{j=1}^{k+1}\,\left(\dfrac{\mu(1+\mu
A_{j-1})\lambda_{j}A_{j-1}}{2a_{j}}\right)\|{x^{j-1}-y^{j-1}}\|^{2}.$

By adding $\left(\frac{1+\mu A_{k+1}}{2}\right)\|{x-x^{k+1}}\|^{2}$ in both
sides of the latter inequality, we obtain, for all $k\geq 0$,

$\displaystyle\beta_{k+1}+\left(\dfrac{1+\mu
A_{k+1}}{2}\right)\|{x-x^{k+1}}\|^{2}$ $\displaystyle\geq
A_{k+1}h(y^{k+1})+\left(\dfrac{1-\sigma^{2}}{2}\right)\sum_{j=1}^{k+1}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}$
$\displaystyle+\sum_{j=1}^{k+1}\,\left(\dfrac{\mu(1+\mu
A_{j-1})\lambda_{j}A_{j-1}}{2a_{j}}\right)\|{x^{j-1}-y^{j-1}}\|^{2}$
$\displaystyle+\left(\dfrac{1+\mu A_{k+1}}{2}\right)\|{x-x^{k+1}}\|^{2}.$

Using Lemma 2.2(a) we then find, for all $k\geq 0$,

$\displaystyle A_{k+1}\Gamma_{k+1}(x)+\dfrac{1}{2}\|{x-x^{0}}\|^{2}$
$\displaystyle\geq
A_{k+1}h(y^{k+1})+\left(\dfrac{1-\sigma^{2}}{2}\right)\sum_{j=1}^{k+1}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}$
$\displaystyle+\sum_{j=1}^{k+1}\,\left(\dfrac{\mu(1+\mu
A_{j-1})\lambda_{j}A_{j-1}}{2a_{j}}\right)\|{x^{j-1}-y^{j-1}}\|^{2}$
$\displaystyle+\left(\dfrac{1+\mu A_{k+1}}{2}\right)\|{x-x^{k+1}}\|^{2}.$ (35)

Note now that from (13) and Lemma 2.1(a) we obtain, for all $k\geq 0$,

$A_{k+1}\Gamma_{k+1}(x)=\sum_{j=1}^{k+1}\,a_{j}\gamma_{j}(x)\leq A_{k+1}h(x),$

which combined with (2) yields, for all $k\geq 1$,

$\displaystyle\dfrac{1}{2}\|{x-x^{0}}\|^{2}$ $\displaystyle\geq
A_{k}\left[h(y^{k})-h(x)\right]+\left(\dfrac{1-\sigma^{2}}{2}\right)\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}$
$\displaystyle\hskip 28.45274pt+\sum_{j=1}^{k}\,\left(\dfrac{\mu(1+\mu
A_{j-1})\lambda_{j}A_{j-1}}{2a_{j}}\right)\|{x^{j-1}-y^{j-1}}\|^{2}+\left(\dfrac{1+\mu
A_{k}}{2}\right)\|{x-x^{k}}\|^{2}.$

(b) This follows trivially from item (a) and (33). ∎

######  Lemma 2.5.

For all $k\geq 0$,

$\displaystyle\left(1-\sigma\sqrt{1+\lambda_{k+1}\mu}\right)\|{y^{k+1}-\widetilde{x}^{k}}\|\leq\|{\lambda_{k+1}v^{k+1}}\|\leq\left(1+\sigma\sqrt{1+\lambda_{k+1}\mu}\right)\|{y^{k+1}-\widetilde{x}^{k}}\|.$
(36)

###### Proof.

The proof follows from the inequality in (LABEL:eq:alg_err), the fact that
$\varepsilon_{k+1}\geq 0$ and a simple argument based on the triangle
inequality. ∎

Since, under mild regularity assumptions on $f$ and $g$, problem (2) is
equivalent to the inclusion

$\displaystyle 0\in\partial f(x)+\partial g(x),$ (37)

it is natural to attempt to evaluate the residuals produced by Algorithm 1 in
the light of (37), and this is exactly what Theorem 2.6(b) is about. Note that
if we set $v^{k+1}=0$ and $\varepsilon_{k+1}=0$ in (38), then it follows that
$x:=y^{k+1}$ satisfies the inclusion (37).

As we mentioned before, Theorem 2.6 below is our main result on the iteration-
complexity of Algorithm 1.

######  Theorem 2.6 (Convergence rates for Algorithm 1).

Consider the sequences evolved by _Algorithm 1_, let $x^{*}$ be the (unique)
solution of (2) and let $d_{0}$ be as in (33). Then, the following holds:

  * _(a)_

For all $k\geq 1$,

$\displaystyle
h(y^{k})-h(x^{*})\leq\dfrac{d_{0}^{2}}{2A_{k}},\qquad\|{x^{*}-y^{k}}\|^{2}\leq\dfrac{d_{0}^{2}}{\mu
A_{k}},\qquad\|{x^{*}-x^{k}}\|^{2}\leq\dfrac{d_{0}^{2}}{1+\mu A_{k}}.$

  * _(b)_

For all $k\geq 1$,

$\displaystyle\begin{cases}&v^{k+1}\in\partial_{\varepsilon_{k+1}}f(y^{k+1})+\partial
g(y^{k+1}),\\\\[5.69054pt]
&\|{v^{k+1}}\|^{2}\leq\left(\dfrac{1+\sigma\sqrt{1+\mu\lambda_{k+1}}}{6^{-1/2}\lambda_{k+1}}\right)^{2}\dfrac{d_{0}^{2}}{\mu
A_{k}},\\\\[17.07164pt]
&\varepsilon_{k+1}\leq\left(\dfrac{3\sigma^{2}}{\lambda_{k+1}}\right)\dfrac{d_{0}^{2}}{\mu
A_{k}}.\end{cases}$ (38)

###### Proof.

(a) Note that the bounds on $h(y^{k})-h(x^{*})$ and $\|{x^{*}-x^{k}}\|^{2}$
follow directly from Proposition 2.4(a) with $x=x^{*}$ and (33). Now, since
$h(\cdot)$ is $\mu$-strongly convex and $0\in\partial h(x^{*})$, one can use
the inequality (see, e.g., [28, Proposition 6(c)]) $h(x)\geq
h(x^{*})+\frac{\mu}{2}\|{x-x^{*}}\|^{2}$, for all $x\in\mathcal{H}$, with
$x=y^{k}$ and the bound on $h(y^{k})-h(x^{*})$ to conclude that
$\|{y^{k}-x^{*}}\|^{2}\leq\frac{2}{\mu}\left(h(y^{k})-h(x^{*})\right)\leq\frac{d_{0}^{2}}{\mu
A_{k}}$.

(b) First, note that the inclusion in (38) follows from the inclusion in
(LABEL:eq:alg_err). Since we will use the second inequality in (36) to prove
the inequality for $\|{v^{k+1}}\|^{2}$, it follows that we first have to bound
the term $\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}$. To this end, note that from
the second inequality in item (a) with $k=k+1$ and the fact that $A_{k+1}\geq
A_{k}$,

$\displaystyle\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}$ $\displaystyle\leq
2\left(\|{x^{*}-y^{k+1}}\|^{2}+\|{\widetilde{x}^{k}-x^{*}}\|^{2}\right)$
$\displaystyle\leq 2\left(\dfrac{d_{0}^{2}}{\mu
A_{k}}+\|{\widetilde{x}^{k}-x^{*}}\|^{2}\right).$ (39)

We now have to bound the second term in (2). Since, from (5),
$\widetilde{x}^{k}$ is a convex combination of $x^{k}$ and $y^{k}$, it follows
that

$\displaystyle\|{\widetilde{x}^{k}-x^{*}}\|^{2}$
$\displaystyle\leq\|{x^{*}-x^{k}}\|^{2}+\|{x^{*}-y^{k}}\|^{2}$
$\displaystyle\leq\dfrac{d_{0}^{2}}{1+\mu A_{k}}+\dfrac{d_{0}^{2}}{\mu A_{k}}$
$\displaystyle\leq\dfrac{2d_{0}^{2}}{\mu A_{k}},$ (40)

where in the second inequality we used the second and third inequalities in
item (a). Now using (2) and (2), we find

$\displaystyle\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}\leq 6\dfrac{d_{0}^{2}}{\mu
A_{k}}.$ (41)

To finish the proof of (b), note that using (41), we obtain the desired bounds
on $\|{v^{k+1}}\|^{2}$ and $\varepsilon_{k+1}$ as a consequence of the second
inequality in (36) and the fact that
$2\lambda_{k+1}\varepsilon_{k+1}\leq\sigma^{2}\|{y^{k+1}-\widetilde{x}^{k}}\|^{2}$
(see (LABEL:eq:alg_err)), respectively. ∎

Next result is motivated by the fact that the rate of convergence of Algorithm
1 presented in Theorem 2.6 is given in terms of the sequence $\\{A_{k}\\}$. We
also mention that the proof of Lemma 2.7 follows the same outline of an
argument given in p. 13 of [5].

######  Lemma 2.7.

The following holds:

  * _(a)_

For all $k\geq 1$,

$\displaystyle
A_{k+1}\geq\lambda_{1}\prod_{j=2}^{k+1}\left(\dfrac{1}{1-\sqrt{\dfrac{\mu\lambda_{j}}{1+\mu\lambda_{j}}}}\right).$
(42)

  * _(b)_

For all $k\geq 1$,

$\displaystyle
A_{k+1}\geq\lambda_{1}\prod_{j=2}^{k+1}\left(1+2\mu\lambda_{j}\right).$ (43)

###### Proof.

(a) From (6),

$\displaystyle a_{k+1}$ $\displaystyle=\dfrac{(1+2\mu
A_{k})\lambda_{k+1}+\sqrt{(1+2\mu A_{k})^{2}\lambda_{k+1}^{2}+4(1+\mu
A_{k})A_{k}\lambda_{k+1}}}{2}$ $\displaystyle\geq\dfrac{(2\mu
A_{k})\lambda_{k+1}+\sqrt{(2\mu A_{k})^{2}\lambda_{k+1}^{2}+4(\mu
A_{k})A_{k}\lambda_{k+1}}}{2}$ $\displaystyle=\dfrac{(2\mu
A_{k})\lambda_{k+1}+2A_{k}\sqrt{\mu^{2}\lambda_{k+1}^{2}+\mu\lambda_{k+1}}}{2}$
$\displaystyle=A_{k}\left[\mu\lambda_{k+1}+\sqrt{\mu\lambda_{k+1}(1+\mu\lambda_{k+1})}\right].$

Hence, from (7),

$\displaystyle A_{k+1}$ $\displaystyle=A_{k}+a_{k+1}$ $\displaystyle\geq
A_{k}+A_{k}\left[\mu\lambda_{k+1}+\sqrt{\mu\lambda_{k+1}(1+\mu\lambda_{k+1})}\right]$
$\displaystyle=A_{k}\left[1+\mu\lambda_{k+1}+\sqrt{\mu\lambda_{k+1}(1+\mu\lambda_{k+1})}\right]$
(44)
$\displaystyle=A_{k}\left(\dfrac{1}{1-\sqrt{\dfrac{\mu\lambda_{k+1}}{1+\mu\lambda_{k+1}}}}\right),$
(45)

where in the last equality we used the identity
$1/\left(1-\sqrt{\frac{x}{1+x}}\right)=1+x+\sqrt{x(1+x)}$ with
$x=\mu\lambda_{k+1}$. Note now that (42) follows directly from (45) and the
fact that $A_{1}=\lambda_{1}$ – see (11).

(b) Using (44), the fact that
$\sqrt{\mu\lambda_{k+1}(1+\mu\lambda_{k+1})}\geq\mu\lambda_{k+1}$ and a
similar reasoning to the proof of item (a), we obtain that (43) holds for all
$k\geq 1$. ∎

Next is a corollary of Lemma 2.7(a) for the special case that the sequence
$\\{\lambda_{k}\\}$ is bounded away from zero. Lemma 2.7(b) will be useful
later in Section 3.

######  Corollary 2.8.

Assume that $\lambda_{k}\geq\underline{\lambda}>0$, for all $k\geq 1$, and
define $\alpha\in(0,1)$ as

$\displaystyle\alpha:=\sqrt{\dfrac{\mu\underline{\lambda}}{1+\mu\underline{\lambda}}}.$
(46)

Then, for all $k\geq 1$,

$\displaystyle
A_{k}\geq\underline{\lambda}\left(\dfrac{1}{1-\alpha}\right)^{k-1}.$ (47)

###### Proof.

Using the fact that the scalar function $(0,\infty)\ni t\mapsto\frac{\mu
t}{1+\mu t}\in(0,1)$ is increasing, the assumption
$\lambda_{k}\geq\underline{\lambda}>0$, for all $k\geq 1$, and (46), we find

$\displaystyle\dfrac{1}{1-\sqrt{\dfrac{\mu\lambda_{j}}{1+\mu\lambda_{j}}}}\geq\dfrac{1}{1-\alpha},\qquad\forall
j\geq 1.$

Hence, from Lemma 2.7(a) and the assumption
$\lambda_{k}\geq\underline{\lambda}$ with $k=1$ we obtain
$A_{k+1}\geq\underline{\lambda}\left(\dfrac{1}{1-\alpha}\right)^{k}$, for all
$k\geq 1$, which is clearly equivalent to
$A_{k}\geq\underline{\lambda}\left(\dfrac{1}{1-\alpha}\right)^{k-1}$ for all
$k\geq 2$. To finish the proof of (47), note that the latter inequality holds
trivially for $k=1$ (because $A_{1}=\lambda_{1}$ and
$\lambda_{1}\geq\underline{\lambda}$). ∎

Next we present convergence rate results for Algorithm 1 under the assumption
that $\\{\lambda_{k}\\}$ is bounded away from zero.

######  Theorem 2.9 (Convergence rates for Algorithm 1 with
$\\{\lambda_{k}\\}$ bounded below).

Consider the sequences evolved by _Algorithm 1_ and assume that
$\lambda_{k}\geq\underline{\lambda}>0$ for all $k\geq 1$. Let $x^{*}$ be the
(unique) solution of (2), let $d_{0}$ be as in (33) and let $\alpha\in(0,1)$
be as in (46). The following holds:

  * _(a)_

For all $k\geq 1$,

$\displaystyle
h(y^{k})-h(x^{*})\leq\dfrac{d_{0}^{2}}{2\underline{\lambda}}(1-\alpha)^{k-1},$
$\displaystyle\max\left\\{\|{x^{*}-y^{k}}\|,\|{x^{*}-x^{k}}\|\right\\}\leq\dfrac{d_{0}}{\sqrt{\mu\underline{\lambda}}}(1-\alpha)^{(k-1)/2}.$

  * _(b)_

For all $k\geq 1$,

$\displaystyle\begin{cases}&v^{k+1}\in\partial_{\varepsilon_{k+1}}f(y^{k+1})+\partial
g(y^{k+1}),\\\\[8.53581pt]
&\|{v^{k+1}}\|\leq\left(\dfrac{1+\sigma\sqrt{1+\mu\underline{\lambda}}}{6^{-1/2}\mu^{1/2}\underline{\lambda}^{3/2}}\right)d_{0}\,(1-\alpha)^{(k-1)/2},\\\\[17.07164pt]
&\varepsilon_{k+1}\leq\left(\dfrac{3\sigma^{2}d_{0}^{2}}{\mu\underline{\lambda}^{2}}\right)(1-\alpha)^{k-1}.\end{cases}$

###### Proof.

(a) This follows from Theorem 2.6(a) and Corollary 2.8.

(b) The result follows from Theorem 2.6(b), Corollary 2.8, the assumption
$\lambda_{k}\geq\underline{\lambda}$ and the fact that, for $t>0$, the scalar
function $t\mapsto\frac{1+\sigma\sqrt{1+\mu t}}{t}$ is nonincreasing. ∎

##  3 A (high-order) large-step A-HPE algorithm for strongly convex problems

In this section, we also consider problem (2), i.e.,
$\min_{x\in\mathcal{H}}\left\\{h(x):=f(x)+g(x)\right\\}$, where the same
assumptions as in Section 2 are assumed to hold on $h$, $f$ and $g$.

For solving (2), we propose and study the iteration-complexity of a variant
(Algorithm 2) of the large-step A-HPE algorithm of Monteiro and Svaiter [21],
with a high-order large-step condition specially tailored for strongly convex
objectives . Applications of this general framework to high-order tensor
methods will be given in Section 4. The main results on convergence rates for
Algorithm 2 are presented in Theorem 3.3 below.

######  Algorithm 2.

A variant of the large-step A-HPE algorithm for (the strongly convex) problem
(2) 0) Choose $x^{0},y^{0}\in\mathcal{H}$, $\sigma\in[0,1)$, $p\geq 2$ and
$\theta>0$; let $A_{0}=0$ and set $k=0$. 1) Compute $\lambda_{k+1}>0$ and
$(y^{k+1},v^{k+1},\varepsilon_{k+1})\in\mathcal{H}\times\mathcal{H}\times\mathbb{R}_{+}$
such that $\displaystyle\begin{aligned}
&v^{k+1}\in\partial_{\varepsilon_{k+1}}f(y^{k+1})+\partial
g(y^{k+1}),\\\\[8.53581pt]
&\dfrac{\|{\lambda_{k+1}v^{k+1}+y^{k+1}-\widetilde{x}^{k}}\|^{2}}{1+\lambda_{k+1}\,\mu}+2\lambda_{k+1}\varepsilon_{k+1}\leq\sigma^{2}\|{y^{k+1}-\widetilde{x}^{k}}\|^{2},\\\\[8.53581pt]
&\lambda_{k+1}\|{y^{k+1}-\widetilde{x}^{k}}\|^{p-1}\geq\theta,\end{aligned}$
(48) where $\displaystyle\widetilde{x}^{k}=\left(\dfrac{a_{k+1}-\mu
A_{k}\lambda_{k+1}}{A_{k}+a_{k+1}}\right)x^{k}+\left(\dfrac{A_{k}+\mu
A_{k}\lambda_{k+1}}{A_{k}+a_{k+1}}\right)y^{k},$ (49) $\displaystyle
a_{k+1}=\dfrac{(1+2\mu A_{k})\lambda_{k+1}+\sqrt{(1+2\mu
A_{k})^{2}\lambda_{k+1}^{2}+4(1+\mu A_{k})A_{k}\lambda_{k+1}}}{2}.$ (50) 2)
Let $\displaystyle A_{k+1}=A_{k}+a_{k+1},$ (51) $\displaystyle
x^{k+1}=\left(\dfrac{1+\mu A_{k}}{1+\mu A_{k+1}}\right)x^{k}+\left(\dfrac{\mu
a_{k+1}}{1+\mu A_{k+1}}\right)y^{k+1}-\left(\dfrac{a_{k+1}}{1+\mu
A_{k+1}}\right)v^{k+1}.$ (52) 3) Set $k=k+1$ and go to step 1.

We now make a few remarks concerning Algorithm 2:

  * (i)

By deleting the third inequality in (LABEL:eq:alg_err2) (the high-order large-
step condition), we see that Algorithm 2 is a special instance of Algorithm 1.
As a consequence, all results proved in Section 2 for Algorithm 1 also hold
for Algorithm 2.

  * (ii)

We mention that Algorithm 2 is a generalization of Algorithm 1 in [16] to
strongly convex objectives. The authors of the latter work proved the global
rates $\mathcal{O}\left(k^{-\frac{3p+1}{2}}\right)$,
$\mathcal{O}\left(k^{-3p}\right)$ and
$\mathcal{O}\left(k^{-\frac{3p+3}{2}}\right)$ for (in the notation of this
paper) function values $h(y^{k+1})-h(x^{*})$ and residuals $\inf_{1\leq i\leq
k+1}\,\|{v^{i}}\|^{2}$ and $\inf_{1\leq i\leq k+1}\,\varepsilon_{i}$,
respectively. (see [16, Theorem 4.3].)

In what follows we will use remark (i) following Algorithm 2 to apply the
results proved for Algorithm 1 in Section 2 to Algorithm 2.

The next two lemmas will be used to prove Theorem 3.3 below.

######  Lemma 3.1.

Consider the sequences evolved by _Algorithm 2_ and let
$d_{0}:=\|{x^{0}-x^{*}}\|$, where $x^{*}$ is the (unique) solution of (2).
Then, for all $k\geq 1$,

$\displaystyle\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}^{\frac{p+1}{p-1}}}\leq\dfrac{d_{0}^{2}}{\theta^{\frac{2}{p-1}}(1-\sigma^{2})}.$
(53)

In particular, for all $k\geq 1$,

$\displaystyle\lambda_{k}\geq Cd_{0}^{-\frac{2(p-1)}{p+1}},\qquad
C:=\lambda_{1}^{\frac{p-1}{p+1}}\theta^{\frac{2}{p+1}}(1-\sigma^{2})^{\frac{p-1}{p+1}}.$
(54)

###### Proof.

Using (34) and third inequality in (LABEL:eq:alg_err2), we obtain

$\displaystyle\left(\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}^{\frac{p+1}{p-1}}}\right)\theta^{\frac{2}{p-1}}\leq\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}^{\frac{p+1}{p-1}}}\left(\lambda_{j}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{p-1}\right)^{\frac{2}{p-1}}=\sum_{j=1}^{k}\,\dfrac{A_{j}}{\lambda_{j}}\|{y^{j}-\widetilde{x}^{\,j-1}}\|^{2}\leq\dfrac{d_{0}^{2}}{1-\sigma^{2}},$

which yields (53). To finish the proof of the lemma, note that (54) follows
directly fom (53) and the fact that $A_{k}\geq\lambda_{1}$ for all $k\geq 1$
(see (7) and (11)). ∎

######  Lemma 3.2.

For all $k\geq 0$,

$\displaystyle A_{k+1}\geq\lambda_{1}\left(1+\dfrac{2\mu
C}{d_{0}^{\frac{2(p-1)}{p+1}}}\,k^{\,\left(\frac{p-1}{p+1}\right)}\right)^{k},$
(55)

where $C>0$ is as in (54).

###### Proof.

First note that from (11) we have $A_{1}=\lambda_{1}$, showing that (55)
trivially holds for $k=0$. Assume now that $k>0$. From Lemma 3.1 we know, in
particular, that

$\displaystyle\sum_{j=2}^{k+1}\,\dfrac{A_{j}}{\lambda_{j}^{\frac{p+1}{p-1}}}\leq\dfrac{d_{0}^{2}}{\theta^{\frac{2}{p-1}}(1-\sigma^{2})}.$

Since $A_{j}=A_{j-1}+a_{j}\geq A_{j-1}\geq\dots\geq A_{1}$, for all $j\geq 2$,
and $A_{1}=\lambda_{1}$, we then obtain

$\displaystyle\sum_{j=2}^{k+1}\,\dfrac{1}{\lambda_{j}^{\frac{p+1}{p-1}}}\leq\dfrac{d_{0}^{2}}{\lambda_{1}\theta^{\frac{2}{p-1}}(1-\sigma^{2})}=:c.$

Now using Lemma A.1 with $c>0$ as above, $q=\frac{p+1}{p-1}$ and
$\lambda_{j}\leftarrow 2\mu\lambda_{j}$, we find

$\displaystyle\prod_{j=2}^{k+1}\left(1+2\mu\lambda_{j}\right)$
$\displaystyle\geq\left(1+\left(\dfrac{(2\mu)^{\frac{p+1}{p-1}}}{c}k\right)^{\frac{p-1}{p+1}}\right)^{k}$
$\displaystyle=\left(1+\dfrac{2\mu}{c^{\frac{p-1}{p+1}}}k^{\frac{p-1}{p+1}}\right)^{k}$
$\displaystyle=\left(1+\left(\dfrac{2\mu\lambda_{1}^{\frac{p-1}{p+1}}\theta^{\frac{2}{p+1}}(1-\sigma^{2})^{\frac{p-1}{p+1}}}{d_{0}^{\frac{2(p-1)}{p+1}}}\right)k^{\frac{p-1}{p+1}}\right)^{k},$

which, in turn, combined with (43) and the definition of $C$ in (54) finishes
the proof of the lemma. ∎

Next is the main result on global convergence rates for Algorithm 2. As we
mentioned before, it provides a global _superlinear_
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ convergence,
where $p-1\geq 1$ is the power in the high-order large-step condition (third
inequality in (LABEL:eq:alg_err2)).

######  Theorem 3.3 (Convergence rates for Algorithm 2).

Consider the sequences evolved by _Algorithm 2_, let $x^{*}$ denote the
(unique) solution of (2) and let $C>0$ be as in (54). Then the following
holds:

  * _(a)_

For all $k\geq 0$,

$\displaystyle
h(y^{k+1})-h(x^{*})\leq\dfrac{d_{0}^{2}}{2\lambda_{1}\left(1+\frac{2\mu
C}{d_{0}^{\frac{2(p-1)}{p+1}}}\,k^{\,\left(\frac{p-1}{p+1}\right)}\right)^{k}}=\mathcal{O}\left(\frac{1}{k^{k\left(\frac{p-1}{p+1}\right)}}\right),$
$\displaystyle\max\left\\{\|{x^{*}-x^{k+1}}\|^{2},\|{x^{*}-y^{k+1}}\|^{2}\right\\}\leq\dfrac{d_{0}^{2}}{\mu\lambda_{1}\left(1+\frac{2\mu
C}{d_{0}^{\frac{2(p-1)}{p+1}}}k^{\,\left(\frac{p-1}{p+1}\right)}\right)^{k}}=\mathcal{O}\left(\frac{1}{k^{k\left(\frac{p-1}{p+1}\right)}}\right).$

  * _(b)_

For all $k\geq 1$,

$\displaystyle\begin{cases}&v^{k+1}\in\partial_{\varepsilon_{k+1}}f(y^{k+1})+\partial
g(y^{k+1}),\\\\[8.53581pt] &\|{v^{k+1}}\|^{2}\leq\left(1+\sigma\sqrt{1+\mu
Cd_{0}^{-\frac{2(p-1)}{p+1}}}\right)^{2}\dfrac{6d_{0}^{\frac{2(3p-1)}{p+1}}}{\mu
C^{2}\lambda_{1}\left(1+\frac{2\mu
C}{d_{0}^{\frac{2(p-1)}{p+1}}}(k-1)^{\,\left(\frac{p-1}{p+1}\right)}\right)^{k-1}}=\mathcal{O}\left(\frac{1}{(k-1)^{(k-1)\left(\frac{p-1}{p+1}\right)}}\right),\\\\[17.07164pt]
&\varepsilon_{k+1}\leq\dfrac{3\sigma^{2}d_{0}^{\frac{4p}{p+1}}}{\mu
C\lambda_{1}\left(1+\frac{2\mu
C}{d_{0}^{\frac{2(p-1)}{p+1}}}(k-1)^{\,\left(\frac{p-1}{p+1}\right)}\right)^{k-1}}=\mathcal{O}\left(\frac{1}{(k-1)^{(k-1)\left(\frac{p-1}{p+1}\right)}}\right).\end{cases}$

###### Proof.

Both items follow from Theorem 2.6 and Lemmas 3.1 and 3.2. To prove the
inequalities in item (b), one also has to use the fact that the scalar
function $t\mapsto\frac{1+\sigma\sqrt{1+\mu t}}{t}$ is nonincreasing as well
as the lower bound on $\lambda_{k}$ given in (54). ∎

##  4 Applications to accelerated high-order tensor methods for strongly
convex objectives

In this section, we consider the problem

$\displaystyle\min_{x\in\mathcal{H}}\,\left\\{h(x):=f(x)+g(x)\right\\},$ (56)

where $f,g:\mathcal{H}\to(-\infty,\infty]$ are proper, closed and convex
functions, $\mbox{dom}\,h\neq\emptyset$, and $g$ is $\mu$-strongly convex on
$\mathcal{H}$ and $p\geq 2$ times continuously differentiable on
$\Omega\supseteq\mbox{Dom}\,(\partial f)$ with $D^{p}g(\cdot)$ being
$L_{p}$-Lipschitz continuous on $\Omega$: $0<L_{p}<+\infty$ and

$\displaystyle\|{D^{p}g(x)-D^{p}g(y)}\|\leq L_{p}\|{x-y}\|,\qquad\forall
x,y\in\Omega.$ (57)

Define

$\displaystyle
g_{x,p}(y):=g(x)+\sum_{k=1}^{p}\,\dfrac{1}{k!}D^{k}g(x)[y-x]^{k}+\dfrac{M}{(p+1)!}\|{y-x}\|^{p+1},\qquad(x,y)\in\Omega\times\mathcal{H},$
(58)

where $M>0$ is such that $M\geq pL_{p}$.

As observed by Nesterov in [26], the function $g_{x,p}(\cdot)$ is convex
whenever $M\geq pL_{p}$ and, moreover,

$\displaystyle\|{\nabla g(y)-\nabla
g_{x,p}(y)}\|\leq\dfrac{L_{p}+M}{p!}\|{y-x}\|^{p},\qquad\forall(x,y)\in\Omega\times\mathcal{H}.$
(59)

At each iteration of the (exact) Proximal-Tensor method for solving (56) one
has to find $y\in\mathcal{H}$ solving an inclusion of the form

$\displaystyle 0\in\lambda\Big{(}\partial f(y)+\nabla g_{z,p}(y)\Big{)}+y-x,$
(60)

where $z=P_{\Omega}(x)$ and $\lambda>0$. Note also that (60) is equivalent to
solving the convex problem

$\displaystyle\min_{y\in\mathcal{H}}\,\left\\{f(y)+g_{z,p}(y)+\dfrac{1}{2\lambda}\|{y-x}\|^{2}\right\\}.$
(61)

Next definition introduces a notion of _relative-error_ inexact solution for
(60) (or, equivalently, (61)). It will be used in step 2 (see (66)) of
Algorithm 3, and can be motivated as follows. Note that the inclusion (60) can
be splitted as an inclusion-equation system:

$\displaystyle\begin{cases}u\in\partial f(y),&\\\\[5.69054pt]
\lambda\Big{(}u+\nabla g_{z,p}(y)\Big{)}+y-x=0.\end{cases}$

Definition 4.1 below relaxes the latter conditions by allowing errors in both
the inclusion ($u$ will belong to $\partial_{\varepsilon}f(y)$ instead of
belonging to $\partial f(y)$) and the equation.

######  Definition 4.1.

The triple
$(y,u,\varepsilon)\in\mathcal{H}\times\mathcal{H}\times\mathbb{R}_{+}$ is a
$\hat{\sigma}$-approximate _Tensor solution_ of (60) at
$(x,\lambda)\in\mathcal{H}\times\mathbb{R}_{++}$ if $\hat{\sigma}\geq 0$ and

$\displaystyle
u\in\partial_{\varepsilon}f(y),\qquad\dfrac{\left\|\lambda\Big{(}u+\nabla
g_{z,p}(y)\Big{)}+y-x\right\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\leq\hat{\sigma}^{2}\|{y-x}\|^{2},$
(62)

where $z=P_{\Omega}(x)$.

Note that if $\hat{\sigma}=0$ in (62), then it follows that $\varepsilon=0$,
$u\in\partial f(y)$ and $\lambda\Big{(}u+\nabla g_{z,p}(y)\Big{)}+y-x=0$,
which implies that $y$ is the solution of (60). We also mention that if we set
$\mu=0$ in Definition 4.1 then we recover [14, Definition 2.1] (see also [16,
Definition 1]).

Next proposition shows that $\hat{\sigma}$-approximate solutions of (60)
provide relative-error approximate solutions in the sense of
(LABEL:eq:alg_err2).

######  Proposition 4.2.

Let $(u,y,\varepsilon)$ be a $\hat{\sigma}$-approximate Tensor solution of
(60) at $(x,\lambda)\in\mathcal{H}\times\mathbb{R}_{++}$ _(_ in the sense of
_Definition 4.1_ _)_ and define

$\displaystyle v=u+\nabla
g(y),\qquad\sigma=\dfrac{\lambda(L_{p}+M)\|{y-x}\|^{p-1}}{p!\sqrt{1+\lambda\mu}}+\hat{\sigma}.$
(63)

Then,

$\displaystyle v\in\partial_{\varepsilon}f(y)+\nabla
g(y),\qquad\dfrac{\|{\lambda
v+y-x}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\leq\sigma^{2}\|{y-x}\|^{2}.$
(64)

###### Proof.

Note that the inclusion in (64) follows from the definition of $v$ in (63) and
the inclusion in (62). To prove the inequality in (64), note that from the
definition of $v$ in (63), the triangle inequality and property (59), we find

$\displaystyle\|{\lambda v+y-x}\|^{2}$ $\displaystyle=\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x+\lambda\big{(}\nabla g(y)-\nabla
g_{z,p}(y)\big{)}}\|^{2}$ $\displaystyle\leq\Big{(}\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x}\|+\lambda\|{\nabla g(y)-\nabla
g_{z,p}(y)}\|\Big{)}^{2}$ $\displaystyle\leq\left(\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x}\|+\frac{\lambda(L_{p}+M)}{p!}\|{y-z}\|^{p}\right)^{2}$
$\displaystyle\leq\left(\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x}\|+\frac{\lambda(L_{p}+M)}{p!}\|{y-x}\|^{p}\right)^{2},$

where in the last inequality we also used the fact that
$\|{y-z}\|\leq\|{y-x}\|$. (because
$y\in\mbox{Dom}(\partial_{\varepsilon}f)\subset\overline{\mbox{Dom}(\partial
f)}\subset\Omega$ and $z=P_{\Omega}(x)$.)

Hence,

$\displaystyle\dfrac{\|{\lambda
v+y-x}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon$
$\displaystyle\leq\left(\dfrac{\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x}\|}{\sqrt{1+\lambda\mu}}+\frac{\lambda(L_{p}+M)}{p!\sqrt{1+\lambda\mu}}\|{y-x}\|^{p}\right)^{2}+2\lambda\varepsilon.$

Using now the elementary inequality
$(a+b)^{2}+c\leq\left(b+\sqrt{a^{2}+c}\right)^{2}$ with
$a=\frac{\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x}\|}{\sqrt{1+\lambda\mu}}$,
$b=\lambda(L_{p}+M)\|{y-x}\|^{p}/(p!\sqrt{1+\lambda\mu})$ and
$c=2\lambda\varepsilon$, we find

$\displaystyle\dfrac{\|{\lambda
v+y-x}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon$
$\displaystyle\leq\left(\frac{\lambda(L_{p}+M)}{p!\sqrt{1+\lambda\mu}}\|{y-x}\|^{p}+\sqrt{\dfrac{\|{\lambda\left(u+\nabla
g_{z,p}(y)\right)+y-x}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon}\right)^{2}$
$\displaystyle\leq\left(\frac{\lambda(L_{p}+M)}{p!\sqrt{1+\lambda\mu}}\|{y-x}\|^{p}+\hat{\sigma}\|{y-x}\|\right)^{2}$
$\displaystyle=\left(\frac{\lambda(L_{p}+M)}{p!\sqrt{1+\lambda\mu}}\|{y-x}\|^{p-1}+\hat{\sigma}\right)^{2}\|{y-x}\|^{2}$
$\displaystyle=\sigma^{2}\|{y-x}\|^{2},$

where in the second inequality we used the inequality in (62) and in the
second identity we used the second equality (63). ∎

Next we present our $p$-th order inexact (relative-error) accelerated tensor
algorithm for solving (56).

######  Algorithm 3.

An accelerated inexact high-order tensor method for solving (56) 0) Choose
$x^{0},y^{0}\in\mathcal{H}$ and $p\geq 2$, $\hat{\sigma}\geq 0$,
$0<\sigma_{\ell}<\sigma_{u}<1$ such that
$\displaystyle\sigma:=\sigma_{u}+\hat{\sigma}<1,\qquad\sigma_{\ell}(1+\hat{\sigma})^{p-1}<\sigma_{u}(1-\hat{\sigma})^{p-1};$
(65) let $A_{0}=0$ and set $k=0$.  1) Compute $\lambda_{k+1}>0$ and a
$\hat{\sigma}$-approximate Tensor solution
$(u^{k+1},y^{k+1},\varepsilon_{k+1})$ (in the sense of Definition 4.1) of (60)
at $(\widetilde{x}^{k},\lambda_{k+1})$ satisfying
$\displaystyle\dfrac{p!\,\sigma_{\ell}}{L_{p}+M}\leq\lambda_{k+1}\|{y^{k+1}-\widetilde{x}^{k}}\|^{p-1}\leq\dfrac{p!\,\sigma_{u}\sqrt{1+\lambda_{k+1}\mu}}{L_{p}+M},$
(66) where $\displaystyle\widetilde{x}^{k}=\left(\dfrac{a_{k+1}-\mu
A_{k}\lambda_{k+1}}{A_{k}+a_{k+1}}\right)x^{k}+\left(\dfrac{A_{k}+\mu
A_{k}\lambda_{k+1}}{A_{k}+a_{k+1}}\right)y^{k},$ (67) $\displaystyle
a_{k+1}=\dfrac{(1+2\mu A_{k})\lambda_{k+1}+\sqrt{(1+2\mu
A_{k})^{2}\lambda_{k+1}^{2}+4(1+\mu A_{k})A_{k}\lambda_{k+1}}}{2}.$ (68) 2)
Let $\displaystyle A_{k+1}=A_{k}+a_{k+1},$ (69) $\displaystyle
v^{k+1}=u^{k+1}-\nabla g_{z^{k},p}(y^{k+1})+\nabla g(y^{k+1}),\quad
z^{k}=P_{\Omega}(\widetilde{x}^{k}),$ (70) $\displaystyle
x^{k+1}=\left(\dfrac{1+\mu A_{k}}{1+\mu A_{k+1}}\right)x^{k}+\left(\dfrac{\mu
a_{k+1}}{1+\mu A_{k+1}}\right)y^{k+1}-\left(\dfrac{a_{k+1}}{1+\mu
A_{k+1}}\right)v^{k+1}.$ (71) 3) Set $k=k+1$ and go to step 1.

We now make two remarks concerning Algorithm 3:

  * (i)

Algorithm 3 is a generalization of [16, Algorithm 3] for strongly convex
problems. The latter algorithm, which can be applied to (56) with $f\equiv 0$,
has the global convergence rates $\mathcal{O}\left(k^{-\frac{3p+1}{2}}\right)$
and $\mathcal{O}\left(k^{-3p}\right)$ for (in the notation of this paper)
$g(y^{k})-g(x^{*})$ and $\inf_{1\leq i\leq k}\,\|{\nabla g(y^{i})}\|^{2}$,
respectively (see [16, Theorem 4.13]).

In contrast to this, here we obtained, see Theorem 4.4, the fast global
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ convergence
rate.

  * (ii)

We also mention that a $\hat{\sigma}$-approximate Tensor solution satisfying
(66) can be computed using bisection schemes (see [2, 14, 21]). More
precisely, by defining the curve

$\displaystyle\tau(\lambda)=\frac{a_{k+1}(\lambda)-\mu
A_{k}\lambda}{A_{k}+a_{k+1}(\lambda)},\quad\lambda>0,$

where

$\displaystyle a_{k+1}(\lambda):=\dfrac{(1+2\mu A_{k})\lambda+\sqrt{(1+2\mu
A_{k})^{2}\lambda^{2}+4(1+\mu A_{k})A_{k}\lambda}}{2},$

we find that $\widetilde{x}^{k}$ as in (67) can be written as

$\displaystyle\widetilde{x}^{k}=y^{k}+\tau_{k+1}(x^{k}-y^{k}),$

where $\tau_{k+1}:=\tau(\lambda_{k+1})$. Moreover, it is not difficult to
check that $\tau(\cdot)$ is (smooth) increasing and that $\dot{\tau}(\lambda)$
satisfies

$\dot{\tau}(\lambda)\leq\frac{1}{\lambda}\qquad\forall\lambda>0.$

As a consequence of the above inequality, one can reproduce Lemma 7.13 as in
[21, p. 1121] and pose the “Line search problem” as in [21, p. 1117] (with
$\lambda\|{y_{\lambda}-x(\lambda)}\|$ replaced by
$\lambda\|{y_{\lambda}-x(\lambda)}\|^{p-1}$). The general search procedures
studied in references [2, Section 4] and [14] would also be helpful. The
complexity of the bracketing/bisection procedure depends on a logarithm of the
inverse of the precision (see, e.g., [21, Theorem 7.16]).

######  Proposition 4.3.

_Algorithm 3_ is a special instance of _Algorithm 2_ for solving (56), where

$\displaystyle\theta:=\dfrac{p!\sigma_{\ell}}{L_{p}+M}.$ (72)

###### Proof.

It follows from the definitions of Algorithms 2 and 3 that we only have to
prove that (LABEL:eq:alg_err2) holds. Note that the inclusion and the first
inequality in (LABEL:eq:alg_err2) follow from step 1 of Algorithm 3 – the fact
that $(u^{k+1},y^{k+1},\varepsilon_{k+1})$ is a $\hat{\sigma}$-approximate
Tensor solution of (60)–, the second inequality in (66), the definition of
$\sigma$ in (65) and Proposition 4.2. To finish the proof of the proposition,
note that the last inequality in (LABEL:eq:alg_err2) (the large-step
condition) is a direct consequence of the first inequality in (66) and (72). ∎

Next theorem states the fast global
$\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ convergence
rate for Algorithm 3.

######  Theorem 4.4 (Convergence rates for Algorithm 3).

Consider the sequences generated by _Algorithm 3_, let $\theta>0$ be as in
(72) and let $C>0$ be as in (54), where $d_{0}:=\|{x^{0}-x^{*}}\|$ and $x^{*}$
is the (unique) solution of (56).

Then all the conclusions of _Theorem 3.3_ hold.

###### Proof.

The proof follows from Proposition 4.3 and Theorem 3.3. ∎

Remarks. We now make some remarks concerning Algorithm 3:

  * (i)

Note that if $p=2$ in (57), then it follows that _Algorithm 3_ reduces to an
(accelerated) inexact proximal-Newton-type algorithm with
$\mathcal{O}\left(k^{-k/3}\right)$ global convergence rate (see Theorems 4.4
and 3.3).

  * (ii)

In [12], an accelerated regularized Newton method was proposed for solving
(56) with $p=2$ and $g$ being $\sigma_{q}$-uniformly convex. In the notation
of this paper, Algorithm 1 of [12] (see Theorem 3.3) has global linear

$\mathcal{O}\left(\dfrac{L_{2}d_{0}^{3}}{\left(1+\left(\frac{\mu}{L_{2}}\right)^{1/3}\right)^{2(k-1)}}\right)$

convergence rate for function values.

  * (iii)

In [11], problem (56) was considered with $f\equiv 0$ and $g$ assumed to be
$\sigma_{q}$-uniformly convex. The complexity of an optimal tensor method with
restart ([11, Algorithm 3]) to compute $x$ satisfying
$g(x)-g(x^{*})\leq\varepsilon$ is

$\displaystyle\mathcal{O}\left(\left(\dfrac{L_{p}}{\sigma_{p+1}}\right)^{\frac{2}{3p+1}}\log_{2}\left(\frac{\Delta_{0}}{\varepsilon}\right)\right),\;q=p+1;\quad$
$\displaystyle\mathcal{O}\left(\left(\dfrac{L_{p}\left(\Delta_{0}\right)^{p+1-q}{q}}{\sigma_{q}^{\frac{p+1}{q}}}\right)^{\frac{2}{3p+1}}+\log_{2}\left(\dfrac{\Delta_{0}}{\varepsilon}\right)\right),\;q<p+1,$

where $\Delta_{0}\geq g(x^{0})-g(x^{*})$. We mention that the upper-bound
$\Delta_{0}$ on $g(x^{0})-g(x^{*})$ is assumed to be known in the
implementation of [11, Algorithm 3].

  * (iv)

In [9], a near-optimal algorithm for solving (56) with $f\equiv 0$ and $\mu=0$
(i.e., with $g$ convex but not strongly convex) was proposed and studied. The
iteration-complexity of Algorithm 2 in [9] to find $x$ satisfying $\|{\nabla
g(x)}\|\leq\varepsilon$ (see [9, Theorem 2]) is

$\mathcal{O}\left(\dfrac{L_{p}^{\frac{2}{3p+1}}}{\varepsilon^{\frac{2(p+1)}{3p+1}}}\Delta_{0}^{\frac{2p}{3p+1}}+\log_{2}\left(\dfrac{2^{\frac{4p-3}{p+1}}\Delta_{0}\left(pL_{p}\right)^{\frac{1}{p}}(p+1)!}{\varepsilon^{\frac{p}{p+1}}}\right),\right)$

where $\Delta_{0}\geq g(x^{0})-g(x^{*})$. Analogously to [11], the upper-bound
$\Delta_{0}$ is assumed to be known while running [9, Algorithm 2].

  * (v)

In [13], tensor methods for solving (56) with $f\equiv 0$ and $g$ being
$p$-times continuously differentiable with $\nu$-Hölder continuous $p$th
derivatives were proposed. The iteration-complexity is
$\mathcal{O}\left(\varepsilon^{-1/(p+\nu-1)}\right)$ and
$\mathcal{O}\left(\varepsilon^{-(p+\nu)/[(p+\nu-1)(p+\nu+1)]}\right)$ for the
non accelerated and accelerated methods, respectively, to find $x$ such that
$\|{\nabla g(x)}\|\leq\varepsilon$.

  * (vi)

In [8], a regularized Newton method with linear convergence rate in function
values for minimizing uniformly convex functions with $\nu$-Hölder continuous
Hessian was proposed and studied. The main result ([8, Theorem 4.1]) gives
that the rate is linear:

$F(x_{k+1})-F^{*}\leq\left(1-\min\left\\{\dfrac{(2+\nu)\left((1+\nu)(2+\nu)\right)^{1/(1+\nu)}\left(\gamma_{f}(\nu)\right)^{\frac{1}{1+\nu}}}{(1+\nu)6^{3/2}\cdot
2^{1/2}\cdot(8+\nu)^{(1-\nu)/(2+2\nu)}},\frac{1}{2}\right\\}\right)\left(F(x_{k})-F^{*}\right),$

where $F$ is the objective function and $F^{*}$ denotes the optimal value.

##  5 Applications to first-order methods for strongly convex problems

Consider the convex optimization problem

$\displaystyle\min_{x\in\mathcal{H}}\,\left\\{h(x):=f(x)+g(x)\right\\},$ (73)

where $f,g:\mathcal{H}\to(-\infty,\infty]$ are proper, closed and convex
functions, $\mbox{dom}\,h\neq\emptyset$, and, additionally, $g$ is _$\mu$
-strongly convex_ on $\mathcal{H}$ and differentiable on
$\Omega\supseteq\mbox{dom}\,f$ with $\nabla g$ being $L$_-Lipschitz continuous
on $\Omega$_

An iteration of the proximal-gradient (forward-backward) method for solving
(73) can be written as follows:

$\displaystyle y=(\lambda\partial f+I)^{-1}\left(x-\lambda\nabla g(z)\right),$
(74)

where $z=P_{\Omega}(x)$ and $\lambda>0$. Using the definition of
$(\lambda\partial f+I)^{-1}$, it is easy to see that (74) is equivalent to
solving the inclusion

$\displaystyle 0\in\lambda\Big{(}\partial f(y)+\nabla g(z)\Big{)}+y-x.$ (75)

Next we define a notion of approximate solution for (75) within a _relative-
error_ criterion.

######  Definition 5.1.

The triple
$(y,u,\varepsilon)\in\mathcal{H}\times\mathcal{H}\times\mathbb{R}_{+}$ is a
$\hat{\sigma}$-approximate Proximal-Gradient (PG) solution of (75) at
$(x,\lambda)\in\mathcal{H}\times\mathbb{R}_{++}$ if $\hat{\sigma}\geq 0$ and

$\displaystyle
u\in\partial_{\varepsilon}f(y),\qquad\dfrac{\|{\lambda\left(u+\nabla
g(z)\right)+y-x}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\leq\hat{\sigma}^{2}\|{y-x}\|^{2},$
(76)

where $z=P_{\Omega}(x)$. We also write

$\displaystyle(y,u,\varepsilon)\approx(\lambda\partial
f+I)^{-1}\left(x-\lambda\nabla g(z)\right)$

to mean that $(y,u,\varepsilon)$ is a $\hat{\sigma}$-approximate PG solution
of (75) at $(x,\lambda)$.

Note that if $\hat{\sigma}=0$ in (76), then it follows that $\varepsilon=0$,
$u\in\partial f(y)$ and $\lambda\left[u+\nabla g(z)\right]+y-x=0$, which
implies that $y$ is the (exact) solution of (75). In particular, in this case,
$y$ satisfies (74).

######  Proposition 5.2.

Let $(u,y,\varepsilon)$ be a $\hat{\sigma}$-approximate PG solution of (75) at
$(x,\lambda)\in\mathcal{H}\times\mathbb{R}_{++}$ as in _Definition 5.1_ and
define

$\displaystyle v=u+\nabla g(y),\qquad\sigma=\dfrac{\lambda
L}{\sqrt{1+\lambda\mu}}+\hat{\sigma}.$ (77)

Then,

$\displaystyle v\in\partial_{\varepsilon}f(y)+\nabla
g(y),\qquad\dfrac{\|{\lambda
v+y-x}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\leq\sigma^{2}\|{y-x}\|^{2}.$
(78)

###### Proof.

The proof follows the same outline of Proposition 4.2’s proof. ∎

For solving (73), we propose the following inexact (relative-error)
accelerated first-order algorithm.

######  Algorithm 4.

An accelerated inexact proximal-gradient algorithm for solving (73) 0) Choose
$x^{0},y^{0}\in\mathcal{H}$ and $\hat{\sigma}\geq 0$, $0<\sigma_{u}\leq 1$
such that $\sigma:=\sigma_{u}+\hat{\sigma}<1$ and let
$\displaystyle\lambda=\dfrac{\sigma_{u}}{\sqrt{\left(\dfrac{\sigma_{u}\mu}{2}\right)^{2}+L^{2}}-\dfrac{\sigma_{u}\mu}{2}}>\dfrac{\sigma_{u}}{L};$
(79) let $A_{0}=0$ and set $k=0$. 1) Compute
$z^{k}=P_{\Omega}(\widetilde{x}^{k})$ and $\displaystyle\begin{aligned}
\qquad(y^{k+1},u^{k+1},\varepsilon_{k+1})\approx(\lambda\partial
f+I)^{-1}\left(\widetilde{x}^{k}-\lambda\nabla g(z^{k})\right),\end{aligned}$
(80) i.e., compute a $\hat{\sigma}$-approximate PG solution
$(u^{k+1},y^{k+1},\varepsilon_{k+1})$ at $(\widetilde{x}^{k},\lambda)$ (in the
sense of Definition 5.1), where
$\displaystyle\widetilde{x}^{k}=\left(\dfrac{a_{k+1}-\mu
A_{k}\lambda}{A_{k}+a_{k+1}}\right)x^{k}+\left(\dfrac{A_{k}+\mu
A_{k}\lambda}{A_{k}+a_{k+1}}\right)y^{k},$ (81) $\displaystyle
a_{k+1}=\dfrac{(1+2\mu A_{k})\lambda+\sqrt{(1+2\mu
A_{k})^{2}\lambda^{2}+4(1+\mu A_{k})A_{k}\lambda}}{2}.$ (82) 2) Let
$\displaystyle A_{k+1}=A_{k}+a_{k+1},$ (83) $\displaystyle
v^{k+1}=u^{k+1}+\nabla g(y^{k+1}),$ (84) $\displaystyle
x^{k+1}=\left(\dfrac{1+\mu A_{k}}{1+\mu A_{k+1}}\right)x^{k}+\left(\dfrac{\mu
a_{k+1}}{1+\mu A_{k+1}}\right)y^{k+1}-\left(\dfrac{a_{k+1}}{1+\mu
A_{k+1}}\right)v^{k+1}.$ (85) 3) Set $k=k+1$ and go to step 1.

We now make the following remark concerning Algorithm 4:

  * (i)

From the definition of $\lambda>0$ in (79) we obtain

$\displaystyle\dfrac{\lambda^{2}L^{2}}{1+\lambda\mu}=\sigma_{u}^{2}.$ (86)

Indeed, it is easy to check that $\lambda>0$ is the largest root of
$L^{2}\lambda^{2}-(\sigma_{u}^{2}\mu)\lambda-\sigma_{u}^{2}=0$, which is
clearly equivalent to (86). Now using (86), we find

$\displaystyle\sigma=\sigma_{u}+\hat{\sigma}=\dfrac{\lambda
L}{\sqrt{1+\lambda\mu}}+\hat{\sigma}.$ (87)

Next proposition shows that Algorithm 4 is a special instance of Algorithm 1
for solving (73).

######  Proposition 5.3.

Consider the sequences evolved by _Algorithm 4_ and let
$\lambda_{k+1}\equiv\lambda$. Then, $\lambda_{k+1}>0$ and the triple
$(y^{k+1},v^{k+1},\varepsilon_{k+1})$ satisfy condition (LABEL:eq:alg_err) in
_Algorithm 1_ with $\sigma=\hat{\sigma}+\sigma_{u}$. As a consequence,
_Algorithm 4_ is a special instance of _Algorithm 1_ for solving (73).

###### Proof.

The proof follows from (80), (87), Proposition 5.2 and the definitions of
Algorithms 1 and 4. ∎

Next we summarize the results on _linear convergence_ rates for Algorithm 4.

######  Theorem 5.4 (Convergence rates for Algorithm 4).

Consider the sequences evolved by _Algorithm 4_ and let
$\sigma=\hat{\sigma}+\sigma_{u}$. Let also $x^{*}$ be the unique solution of
(73), let $d_{0}$ be as in (33) and denote
$\gamma=\sqrt{(1+\sigma_{u})^{-1}\sigma_{u}}$. The following holds:

  * _(a)_

For all $k\geq 1$,

$\displaystyle
h(y^{k})-h(x^{*})\leq\dfrac{Ld_{0}^{2}}{2\sigma_{u}}\left(1-\gamma\sqrt{\dfrac{\mu}{L}}\,\right)^{k-1},$
$\displaystyle\max\left\\{\|{x^{*}-y^{k}}\|,\|{x^{*}-x^{k}}\|\right\\}\leq\sqrt{\dfrac{L}{\sigma_{u}\mu}}\,d_{0}\left(1-\gamma\sqrt{\dfrac{\mu}{L}}\,\right)^{(k-1)/2}.$

  * _(b)_

For all $k\geq 1$,

$\displaystyle\begin{cases}&v^{k+1}\in\partial_{\varepsilon_{k+1}}f(y^{k+1})+\partial
g(y^{k+1}),\\\\[5.69054pt]
&\|{v^{k+1}}\|\leq\dfrac{6d_{0}L^{3/2}}{\mu^{1/2}\sigma_{u}^{3/2}}\left(1+\sigma\sqrt{1+\frac{\sigma_{u}\,\mu}{L}}\,\right)\left(1-\gamma\sqrt{\dfrac{\mu}{L}}\,\right)^{(k-1)/2},\\\\[17.07164pt]
&\varepsilon_{k+1}\leq\dfrac{3\sigma^{2}d_{0}^{2}L^{2}}{\sigma_{u}^{2}\,\mu}\left(1-\gamma\sqrt{\dfrac{\mu}{L}}\,\right)^{k-1}.\end{cases}$

###### Proof.

(a) First note that simple computations using (46) with
$\underline{\lambda}=\lambda$, the inequality in (79), the definition of
$\gamma>0$ and the fact that $L\geq\mu$ show that

$\displaystyle\alpha>\sqrt{(1+\sigma_{u})^{-1}\sigma_{u}}\sqrt{\dfrac{\mu}{L}}=\gamma\sqrt{\dfrac{\mu}{L}},\qquad\lambda>\dfrac{\sigma_{u}}{L},$
(88)

which combined with Proposition 5.3 and Theorem 2.9(a) gives the proof of (a).

(b) The result follows from (88), Proposition 5.3 and Theorem 2.9(b). ∎

## Acknowledgments

The author would like to thank Dr. Benar F. Svaiter for the fruitful
discussions related to the first draft of this work. The author also thank the
three anonymous referees and the associate editor for their comments that
significantly improved the manuscript.

##  Appendix A Some auxiliary results

######  Lemma A.1.

For all $k\geq 1$, the optimal value of the minimization problem, over
$\lambda_{1},\dots,\lambda_{k}>0$,

$\displaystyle\begin{aligned}
&\min\,\prod_{j=1}^{k}\left(1+\lambda_{j}\right)\\\\[5.69054pt]
&\emph{s.t.}\;\;\sum_{j=1}^{k}\dfrac{1}{\lambda_{j}^{q}}\leq c,\end{aligned}$
(89)

where $c>0$ and $q\geq 1$, is given by

$\left(1+\left(\dfrac{k}{c}\right)^{1/q}\right)^{k}.$

###### Proof.

First consider the convex problem

$\displaystyle\begin{aligned}
&\min\,\sum_{j=1}^{k}\,\log(1+e^{t_{j}})\\\\[5.69054pt]
&\mbox{s.t.}\;\;\sum_{j=1}^{k}\dfrac{1}{e^{qt_{j}}}\leq c.\end{aligned}$ (90)

Since the objective and constraint functions in (90) are convex and invariant
under permutations on $(t_{1},\dots,t_{k})$, it follows that one of its
solutions takes the form $(t,\dots,t)$. It is also clear that at any solution
the inequality in (90) must hold as an equality. Hence, $k\frac{1}{e^{qt}}=c$,
i.e., $e^{t}=\left(\frac{k}{c}\right)^{1/q}$. As a consequence, for all
$(t_{1},\dots,t_{k})$ such that $\sum_{j=1}^{k}\frac{1}{e^{qt_{j}}}\leq c$,

$\displaystyle\sum_{j=1}^{k}\,\log(1+e^{t_{j}})\geq
k\log(1+e^{t})=k\log\left(1+\left(\dfrac{k}{c}\right)^{1/q}\right)=\log\left(\left(1+\left(\dfrac{k}{c}\right)^{1/q}\right)^{k}\right).$
(91)

Now let $\lambda_{1},\dots,\lambda_{k}>0$ be such that
$\sum_{j=1}^{k}\frac{1}{\lambda_{j}^{q}}\leq c$ and define
$t_{j}:=\log(\lambda_{j})$, for $j\in\\{1,\dots,k\\}$. Then, since in this
case $\sum_{j=1}^{k}\frac{1}{e^{qt_{j}}}\leq c$, using (91) and some basic
properties of logarithms we find

$\displaystyle\prod_{j=1}^{k}\,(1+\lambda_{j})=\prod_{j=1}^{k}\,(1+e^{t_{j}})$
$\displaystyle=e^{\log\left(\prod_{j=1}^{k}\,(1+e^{t_{j}})\right)}$
$\displaystyle=e^{\sum_{j=1}^{k}\,\log(1+e^{t_{j}})}$ $\displaystyle\geq
e^{\log\left(\left(1+\left(\dfrac{k}{c}\right)^{1/q}\right)^{k}\right)}$
$\displaystyle=\left(1+\left(\dfrac{k}{c}\right)^{1/q}\right)^{k},$

which concludes the proof of the lemma. ∎

######  Lemma A.2.

The following holds for $q(\cdot)$ defined by

$\displaystyle q(x)=\langle
v,x-y\rangle+\frac{\mu}{2}\|{x-y}\|^{2}-\varepsilon+\frac{1}{2\lambda}\|{x-z}\|^{2}\qquad(x\in\mathcal{H})$
(92)

where $v,y,z\in\mathcal{H}$ and $\mu,\varepsilon,\lambda>0$.

  * _(a)_

The (unique) global minimizer of $q(\cdot)$ is given by

$x^{*}=\frac{1}{1+\lambda\mu}z+\frac{\lambda\mu}{1+\lambda\mu}y-\frac{\lambda}{1+\lambda\mu}v.$

  * _(b)_

We have,

$\displaystyle\min_{x}\,q(x)=\dfrac{1}{2\lambda}\left[\|{y-z}\|^{2}-\left(\dfrac{\|{\lambda
v+y-z}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\right)\right].$

  * _(c)_

We have,

$\displaystyle
q(x)=\dfrac{1}{2\lambda}\left[\|{y-z}\|^{2}-\left(\dfrac{\|{\lambda
v+y-z}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\right)\right]+\dfrac{1+\lambda\mu}{2\lambda}\|{x-x^{*}}\|^{2},\qquad\forall
x\in\mathcal{H}.$

###### Proof.

(a) This follows directly from (92) and some simple calculus.

(b) Note first that

$\displaystyle\min_{x}\,q(x)=q(x^{*})$ $\displaystyle=\langle
v,x^{*}-y\rangle+\frac{\mu}{2}\|{x^{*}-y}\|^{2}-\varepsilon+\frac{1}{2\lambda}\|{x^{*}-z}\|^{2}.$
(93)

Using the well-known identity
$a\|{z}\|^{2}+b\|{w}\|^{2}=\frac{1}{a+b}\left[\|{az+bw}\|^{2}+ab\|{z-w}\|^{2}\right]$
with $a=\mu$, $b=1/\lambda$, $z=x^{*}-y$ and $w=x^{*}-z$, and (a) we find

$\displaystyle\mu\|{x^{*}-y}\|^{2}+\frac{1}{\lambda}\|{x^{*}-z}\|^{2}$
$\displaystyle=\dfrac{\lambda}{1+\lambda\mu}\left[\left\|\underbrace{\dfrac{1+\lambda\mu}{\lambda}x^{*}-\mu
y-\dfrac{1}{\lambda}z}_{-v}\right\|^{2}+\dfrac{\mu}{\lambda}\|{z-y}\|^{2}\right]$
$\displaystyle=\dfrac{\lambda}{1+\lambda\mu}\left[\|{v}\|^{2}+\dfrac{\mu}{\lambda}\|{z-y}\|^{2}\right].$
(94)

On the other hand, we also have
$x^{*}-y=\frac{1}{1+\lambda\mu}(z-y)-\frac{\lambda}{1+\lambda\mu}v$, which in
turn gives

$\displaystyle\langle v,x^{*}-y\rangle=\dfrac{1}{1+\lambda\mu}\left[\langle
v,z-y\rangle-\lambda\|{v}\|^{2}\right].$ (95)

Direct use of (93), (A) and (95) yields

$\displaystyle\min_{x}\,q(x)+\varepsilon$
$\displaystyle=\dfrac{1}{1+\lambda\mu}\left[\langle
v,z-y\rangle-\lambda\|{v}\|^{2}\right]+\dfrac{\lambda}{2(1+\lambda\mu)}\left[\|{v}\|^{2}+\dfrac{\mu}{\lambda}\|{z-y}\|^{2}\right]$
$\displaystyle=\dfrac{1}{2\lambda(1+\lambda\mu)}\left[2\langle\lambda
v,z-y\rangle-\|{\lambda v}\|^{2}+\lambda\mu\|{z-y}\|^{2}\right]$
$\displaystyle=\dfrac{1}{2\lambda(1+\lambda\mu)}\left[(1+\lambda\mu)\|{y-z}\|^{2}-\|{\lambda
v+y-z}\|^{2}\right]$
$\displaystyle=\dfrac{1}{2\lambda}\left[\|{y-z}\|^{2}-\dfrac{\|{\lambda
v+y-z}\|^{2}}{1+\lambda\mu}\right],$

which then yields

$\displaystyle\min_{x}\,q(x)$
$\displaystyle=\dfrac{1}{2\lambda}\left[\|{y-z}\|^{2}-\dfrac{\|{\lambda
v+y-z}\|^{2}}{1+\lambda\mu}\right]-\varepsilon$
$\displaystyle=\dfrac{1}{2\lambda}\left[\|{y-z}\|^{2}-\left(\dfrac{\|{\lambda
v+y-z}\|^{2}}{1+\lambda\mu}+2\lambda\varepsilon\right)\right].$

(c) This follows from (b) and Taylor’s theorem applied to $q(\cdot)$. ∎

## References

  * [1] M. M. Alves, R. D. C. Monteiro, and B. F. Svaiter.  Regularized HPE-type methods for solving monotone inclusions with improved pointwise iteration-complexity bounds.  SIAM J. Optim., 26(4):2730–2743, 2016.
  * [2] M. M. Alves, R.D.C. Monteiro, and B.F. Svaiter.  Primal-dual regularized SQP and SQCQP type methods for convex programming and their complexity analysis.  Technical report (optimization-online 4353), Sep 2014.
  * [3] Y. Arjevani, O. Shamir, and R. Shiff.  Oracle complexity of second-order methods for smooth convex optimization.  Math. Program., 178(1-2, Ser. A):327–360, 2019.
  * [4] H. Attouch, M. M. Alves, and B. F. Svaiter.  A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity $\mathcal{O}(1/n^{2})$.  J. Convex Anal., 23(1):139–180, 2016.
  * [5] M. Barré, A. Taylor, and F. Bach.  A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives.  Technical report (arxiv:2106.15536v2 [math.oc]), Jul 2021.
  * [6] S. Bubeck, Q. Jiang, Y. Lee, Y. Yuanzhil, and A. Sidford.  Near-optimal method for highly smooth convex optimization.  Proceedings of Machine Learning Research, 99:1–16, 2019.
  * [7] N. Doikov and Y. Nesterov.  Local convergence of tensor methods.  _Math. Program._ , 2021.
  * [8] N. Doikov and Y. Nesterov.  Minimizing uniformly convex functions by cubic regularization of Newton method.  J. Optim. Theory Appl., 189(1):317–339, 2021.
  * [9] P. Dvurechensky, A. Gasnikov, P. Ostroukhov, C. Uribe, and A. Ivanova.  Near-optimal tensor methods for minimizing the gradient norm of convex function.  Technical report (arxiv:1912.03381v1 [math.oc]), Dec 2019.
  * [10] J. Eckstein and W. Yao.  Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM.  Math. Program., 170(2, Ser. A):417–444, 2018.
  * [11] A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, and C. Uribe.  Optimal tensor methods in smooth convex and uniformly convex optimization.  Proceedings of Machine Learning Research, 99:1–18, 2019.
  * [12] G. N. Grapiglia and Y. Nesterov.  Accelerated regularized Newton methods for minimizing composite convex functions.  SIAM J. Optim., 29(1):77–99, 2019.
  * [13] G. N. Grapiglia and Y. Nesterov.  Tensor methods for finding approximate stationary points of convex functions.  Optim. Methods Softw., pages 1–34, 2020.
  * [14] B. Jiang, H. Wang, and S. Zhang.  An optimal high-order tensor method for convex optimization.  Technical report (arxiv:1812.06557 [math.oc]), Apr 2020.
  * [15] G. Kornowski and O. Shamir.  High-order oracle complexity of smooth and strongly convex optimization.  Technical report (arxiv:2010.06642v2 [math.oc]), Apr 2021.
  * [16] T. Lin and M. I. Jordan.  A control-theoretic perspective on optimal high-order optimization.  Technical report (arxiv:1912.07168v2 [math.oc]), Apr 2021.
  * [17] B. Martinet.  Régularisation d’inéquations variationnelles par approximations successives.  Rev. Française Informat. Recherche Opérationnelle, 4(Ser. R-3):154–158, 1970.
  * [18] R. D. C. Monteiro and B. F. Svaiter.  On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean.  SIAM J. Optim., 20(6):2755–2787, 2010.
  * [19] R. D. C. Monteiro and B. F. Svaiter.  Complexity of variants of Tseng’s modified F-B splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems.  SIAM J. Optim., 21(4):1688–1720, 2011.
  * [20] R. D. C. Monteiro and B. F. Svaiter.  Iteration-Complexity of a Newton Proximal Extragradient Method for Monotone Variational Inequalities and Inclusion Problems.  SIAM J. Optim., 22(3):914–935, 2012.
  * [21] R. D. C. Monteiro and B. F. Svaiter.  An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.  SIAM J. Optim., 23(2):1092–1125, 2013.
  * [22] Y. Nesterov.  Introductory lectures on convex optimization, volume 87 of Applied Optimization.  Kluwer Academic Publishers, Boston, MA, 2004.  A basic course.
  * [23] Y. Nesterov.  Smooth minimization of non-smooth functions.  Math. Program., 103(1, Ser. A):127–152, 2005.
  * [24] Y. Nesterov.  Inexact accelerated high-order proximal-point methods.  Technical report, Feb 2020.
  * [25] Y. Nesterov.  Inexact accelerated high-order proximal-point methods with auxiliary search procedure.  Technical report, Feb 2020.
  * [26] Y. Nesterov.  Implementable tensor methods in unconstrained convex optimization.  Math. Program., 186(1-2, Ser. A):157–183, 2021.
  * [27] R. T. Rockafellar.  Convex Analysis.  Princeton University Press, Princeton, NJ, 1970.
  * [28] R. T. Rockafellar.  Monotone operators and the proximal point algorithm.  SIAM J. Control Optimization, 14(5):877–898, 1976.
  * [29] M. V. Solodov and B. F. Svaiter.  A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator.  Set-Valued Anal., 7(4):323–345, 1999.
  * [30] M. V. Solodov and B. F. Svaiter.  A hybrid projection-proximal point algorithm.  J. Convex Anal., 6(1):59–70, 1999.
  * [31] M. V. Solodov and B. F. Svaiter.  An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions.  Math. Oper. Res., 25(2):214–230, 2000.
  * [32] M. V. Solodov and B. F. Svaiter.  A unified framework for some inexact proximal point algorithms.  Numer. Funct. Anal. Optim., 22(7-8):1013–1035, 2001.