2023

1]Automatic Control and Systems Engineering Department, National University of
Science and Technology Politehnica Bucharest, Spl. Independentei, 313,
Bucharest, 060042, Romania

2]ICTEAM Institute, Université catholique de Louvain, Louvain-La-Neuve, 1348,
Belgium

3]CORE, Université catholique de Louvain, 1348, Belgium

4]Gheorghe Mihoc-Caius Iacob Institute of Mathematical Statistics and Applied
Mathematics of the Romanian Academy, Bucharest, 610101, Romania

# Proximal gradient methods with inexact oracle of degree $q$ for composite
optimization

Yassine Nabou<EMAIL_ADDRESS>François Glineur
<EMAIL_ADDRESS>Ion Necoara<EMAIL_ADDRESS>[  [  [  [

###### Abstract

We introduce the concept of inexact first-order oracle of degree $q$ for a
possibly nonconvex and nonsmooth function, which naturally appears in the
context of approximate gradient, weak level of smoothness and other
situations. Our definition is less conservative than those found in the
existing literature, and  it can be viewed as an interpolation between fully
exact and the existing inexact first-order oracle definitions. We analyze the
convergence behavior of a (fast) inexact proximal gradient method using such
an oracle for solving (non)convex composite minimization problems. We derive
complexity estimates and study the dependence between the accuracy of the
oracle and the desired accuracy of the gradient or of the objective function.
Our results show that better rates can be obtained both theoretically and in
numerical simulations when $q$ is large.

###### keywords:

Composite problems, inexact first-order oracle, proximal gradient, convergence
analysis.

###### pacs:

[

MSC Classification]90C25, 90C06, 65K05.

##  1 Introduction

Optimization methods based on gradient information are widely used in
applications where high accuracy is not desired, such as machine learning,
data analysis, signal processing and statistics Pol:63 ; Bec:17 ; Bot:10 ;
WaLI:14 . The standard convergence analysis of gradient-based methods requires
the availability of the exact gradient information for the objective function.
However, in many optimization problems, one doesn’t have access to exact
gradients, e.g., the gradient is obtained by solving another optimization
problem. In this case one can use inexact (approximate) gradient information.
In this paper, we consider the following composite optimization problem:

$\displaystyle\min\limits_{x\in\mathbb{E}}f(x):=F(x)+h(x),$ (1)

where $h:\mathbb{E}\to\bar{\mathbb{R}}$ is a simple (i.e., proximal easy)
closed convex function, $F:\mathbb{E}\to\mathbb{R}$ is a general lower
semicontinuous function (possibly nonconvex) and there exist $f_{\infty}$ such
that $f(x)\geq f_{\infty}{\color[rgb]{0,0,0}>-\infty}$ for all
$x\in\text{dom}\,f=\text{dom}\,h$. We assume that we can compute exactly the
proximal operator of $h$, and that we cannot have access to the
(sub)differential of $F$, but can compute an approximation of it at any given
point. Optimization algorithms with inexact first-order oracles are well
studied in literature, see e.g., BoGuRa:16 ; CoDiOr:18 ; Asp:08 ; DeGlNe:13 ;
DvGa:16 ; Dvur:17 ; StDv:19 . For example, DeGlNe:13  considers the case where
$h$ is the indicator function of a convex set $Q$ and $F$ is a convex
function, and introduces the so-called inexact first-order $(\delta,L)$-oracle
for $F$, i.e., for any $y\in Q$ one can compute an inexact oracle consisting
of a pair $(F_{\delta,L}(y),g_{\delta,L}(y))$ such that:

$\displaystyle 0\leq F(x)-\Big{(}F_{\delta,L}(y)+\langle
g_{\delta,L}(y),x-y\rangle\Big{)}\leq\frac{L}{2}\lVert
x-y\rVert^{2}+\delta\quad\forall x\in Q.$ (2)

Then, DeGlNe:13  introduces (fast) inexact first-order methods based on
$g_{\delta,L}(y)$ information and derives asymptotic convergence in function
values of order $\mathcal{O}\left(\frac{1}{k}+\delta\right)$ or
$\mathcal{O}\left(\frac{1}{k^{2}}+k\delta\right)$, respectively. One can
notice that in the nonaccelerated scheme, the objective function accuracy
decreases with $k$ and asymptotically tends to $\delta$, while in the
accelerated scheme, there is error accumulation. Further, Dvur:17  considers
problem (1) with domain of $h$ bounded, and introduces the following inexact
first-order oracle:

$\displaystyle|F(x)-F_{\delta,L}(x)|\leq\delta,\;\;F(x)-F_{\delta,L}(y)-\langle
g_{\delta,L}(y),x-y\rangle\leq\frac{L}{2}\|x-y\|^{2}+\delta.$

Under the assumptions that $F$ is nonconvex and $h$ is convex but with bounded
domain, Dvur:17  derives a sublinear rate in the squared norm of the
generalized gradient mapping of order
$\mathcal{O}\left(\frac{1}{k}+\delta\right)$ for an inexact proximal gradient
method based on $g_{\delta,L}(y)$ information. Note that all previous results
provide convergence rates under the assumption of the boundedness of the
domain of $f$ (or equivalently of $h$). An open question is whether one can
modify the previous definitions of inexact first-order oracle to cover both
the convex and nonconvex settings, in order to be more general and to improve
the convergence results of an algorithm based on this inexact information.
More precisely, can one define a general inexact oracle that bridges the gap
between exact oracle (exact gradient information) and the existing inexact
first-order oracle definitions found in the literature DeGlNe:13 ; Dvur:17 ?
In this paper we answer this question positively for both convex and nonconvex
problems, introducing a suitable definition of inexactness for a first-order
oracle for $F$ involving some degree $0\leq q<2$, which consist in multiplying
the constant $\delta$ in (2) with quantity $\|x-y\|^{q}$ (see Definition 2).
We provide several examples that can fit in our proposed inexact first-order
oracle framework, such as approximate gradient or weak level of smoothness,
and show that, under this new definition of inexactness, we can remove the
boundedness assumption of the domain of $h$. Then, we consider an inexact
proximal gradient algorithm based on this inexact first-order oracle and
provide convergence rates of order
$\mathcal{O}\left(\frac{1}{k}+\delta^{2/(2-q)}\right)$ for $q\in[0,1)$ and
$\mathcal{O}\left(\frac{1}{k}+\frac{\delta}{k^{q/2}}+\frac{\delta^{2}}{k^{q-1}}\right)$
for $q\in[1,2)$ for nonconvex composite problems, and of order
$\mathcal{O}\left(\frac{1}{k}+\frac{\delta}{k^{q/2}}\right)$ for $q\in[0,2)$
for convex composite problems in the form (1). We also derive convergence
rates of order $\mathcal{O}(\frac{1}{k^{2}}+\frac{\delta}{k^{(3q-2)/2}})$ for
a fast inexact proximal gradient algorithm for solving the convex composite
problem (1). Note that our convergence rates are better as $q$ increases. In
particular, for the inexact proximal gradient algorithm the power of $\delta$
in the convergence estimate is higher for $q\in(0,1)$ than for $q=0$, while
for $q\geq 1$ the coefficients of $\delta$ diminishes with $k$. For the fast
inexact proximal gradient method we show that there is no error accumulation
for $q\geq 2/3$. Hence, it is beneficial to consider an inexact first-order
oracle of degree $q>0$, as this allows us to work with less accurate
approximation of the (sub)gradient of $F$ when $q$ is large.

##  2 Notations and preliminaries

In what follows $\mathbb{R}^{n}$ denotes the finite-dimensional Euclidean
space endowed with the standard inner product $\langle s,x\rangle=s^{T}x$ and
the corresponding norm $\|s\|=\langle s,s\rangle^{1/2}$ for any
$s\in\mathbb{R}^{n}$. For a proper lower semicontinuous convex function $h$ we
denote its domain by $\text{dom}\;h=\\{x\in\mathbb{R}^{n}:\;h(x)<\infty\\}$
and its proximal operator as:

$\displaystyle\text{prox}_{\gamma
h}(x):=\operatorname*{arg\,min}_{y\in\text{dom}\;h}h(y)+\frac{1}{2\gamma}\|x-y\|^{2}.$

Next, we provide a few definitions and properties for subdifferential calculus
in the nonconvex settings (see Mor:06 ; RoWe:98  for more details).

######  Definition 1.

(Subdifferential): Let $f:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ be a proper lower
semicontinuous function. For a given $x\in\text{dom}\;f$, the
Fr$\acute{e}$chet subdifferential of $f$ at $x$, written
$\widehat{\partial}f(x)$, is the set of all vectors $g_{x}\in\mathbb{R}^{n}$
satisfying:

$\lim_{x\neq y}\inf\limits_{y\to x}\frac{f(y)-f(x)-\langle
g_{x},y-x\rangle}{\lVert x-y\rVert}\geq 0.$

When $x\notin\text{dom}\;f$, we set $\widehat{\partial}f(x)=\emptyset$. The
limiting-subdifferential, or simply the subdifferential, of $f$ at
$x\in\text{dom}\,f$, written $\partial f(x)$, is defined as Mor:06 :

$\displaystyle\partial f(x):=\left\\{g_{x}\in\mathbb{R}^{n}\\!\\!:\exists
x^{k}\to x,f(x^{k})\to f(x)\;\text{and}\;\exists
g_{x}^{k}\in\widehat{\partial}f(x^{k})\;\;\text{such that}\;\;g_{x}^{k}\to
g_{x}\right\\}.$

Note that we have $\widehat{\partial}f(x)\subseteq\partial f(x)$ for each
$x\in\text{dom}\,f$. For $f(x)=F(x)+h(x)$, if $F$ and $h$ are regular at
$x\in\text{dom}f$, then we have:

$\displaystyle\partial f(x)=\partial F(x)+\partial h(x).$

(see Theorem 6 in Hir:79  for more details). Further, if $f$ is proper, lower
semicontinuous and convex, then RoWe:98 :

$\displaystyle\partial
f(x)=\partial\hat{f}(x)=\\{\lambda\in\mathbb{R}^{n}:f(y)\geq
f(x)+\langle\lambda,y-x\rangle\;\;\forall y\in\mathbb{R}^{n}\\}.$

A function $F:\mathbb{R}^{n}\to\mathbb{R}$ is $L_{F}$-smooth if it is
differentiable and its gradient is $L_{F}$ Lipschitz, i.e., satisfying:

$\displaystyle\|\nabla F(x)-\nabla F(y)\|\leq L_{F}\|x-y\|,\quad\forall
x,y\in\mathbb{R}^{n}.$

It follows immediately that Nes:04 :

$\displaystyle|F(x)-(F(y)+\langle\nabla
F(y),x-y\rangle)|\leq\frac{L_{F}}{2}\|x-y\|^{2},\quad\forall
x,y\in\mathbb{R}^{n}.$ (3)

Finally, let us recall the following classical weighted arithmetic-geometric
mean inequality: if $a,b$ are positive constants and
$0\leq\alpha_{1},\alpha_{2}\leq 1$, such that $\alpha_{1}+\alpha_{2}=1$, then
$a^{\alpha_{1}}b^{\alpha_{2}}\leq\alpha_{1}a+\alpha_{2}b$. We will later use
the following consequence for $\rho>0$, $a=\rho\lVert x-y\rVert^{2}$,
$b=\frac{\delta_{q}^{\frac{2}{2-q}}}{\rho^{\frac{q}{2-q}}}$,
$\alpha_{1}=\frac{q}{2}$ and $\alpha_{2}=\frac{2-q}{2}$:

$\displaystyle{\delta_{q}}\lVert x-y\rVert^{q}\leq\frac{q\rho\lVert
x-y\rVert^{2}}{2}+\frac{(2-q)\delta_{q}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$
(4)

##  3 Inexact first-order oracle of degree $q$

In this section, we introduce our new inexact first-order oracle of degree
$0\leq q<2$ and provide some nontrivial examples that fit into our framework.
Our oracle can deal with general functions (possibly with unbounded domain),
unlike the previous results in DeGlNe:13 ; Dvur:17 , but requires exact zero-
order information.

######  Definition 2.

The function $F$ is equipped with an inexact first-order $(\delta,L)$-oracle
of degree $q\\!\in\\![0,2)$ if for any $y\\!\in\\!\text{dom}f$ one can compute
$g_{\delta,L,q}(y)\in\mathbb{E}^{*}$ such that:

$\displaystyle F(x)\\!-\\!\left(F(y)+\langle
g_{\delta,L,q}(y),x-y\rangle\right)\\!\leq\\!\frac{L}{2}\|x-y\|^{2}+\delta\|x-y\|^{q}\;\;\;\forall
x\\!\in\\!\text{dom}f.$ (5)

To the best of our knowledge this definition of a first-order inexact oracle
is new. The motivation behind this definition is to introduce a versatile
inexact first-order oracle framework that bridges the gap between exact oracle
(exact gradient information, i.e., $q=2$) and the existing inexact first-order
oracle definitions found in the literature (i.e., $q=0$). More specifically,
when $q=2$, Definition 2 aligns with established results for smooth functions
under exact gradient information, while when $q=0$, our definition has been
previously explored in the literature, see DeGlNe:13 ; Dvur:17 . Next, we
provide several examples that satisfy Definition 2 naturally, and then we
provide theoretical results showing the advantages of this new inexact oracle
over the existing ones from the literature.

######  Example 1.

(Smooth function with inexact first-order oracle). Let $F$ be differentiable
and its gradient be Lipschitz continuous with constant $L_{F}$ over
$\text{dom}f$. Assume that for any $x\in\text{dom}\,f$, one can compute
$g_{\Delta,L_{F}}(x)$, an approximation of the gradient $\nabla F(x)$
satisfying:

$\displaystyle\|\nabla F(x)-g_{\Delta,L_{F}}(x)\|\leq\Delta.$ (6)

Then, $F$ is equipped with $(\delta,L)$-oracle of degree $q=1$ as in
Definition 2, with $\delta=\Delta$, $L=L_{F}$, and
$g_{\delta,L,1}(x)=g_{\Delta,L_{F}}(x)$. Indeed, since $F$ is $L_{F}$-smooth,
we get:

$\displaystyle F(y)-F(x)-\langle\nabla F(x),y-x\rangle$
$\displaystyle\leq\frac{L_{F}}{2}\|y-x\|^{2}.$

It follows that:

$\displaystyle F(y)\\!-\\!F(x)\\!-\\!\langle
g_{\Delta,L_{F}}(x),y\\!-\\!x\rangle\\!$
$\displaystyle\leq\frac{L_{F}}{2}\|y\\!-\\!x\|^{2}\\!+\\!\|\nabla
F(x)\\!-\\!g_{\Delta,L_{F}}(x)\|\,\|y\\!-\\!x\|$
$\displaystyle\leq\frac{L_{F}}{2}\|y-x\|^{2}+\Delta\|y-x\|.$

which completes our statement. Finite sum optimization problems appear widely
in machine learning Bot:10  and deal with an objective
$F(x):=\sum_{i=1}^{N}F_{i}(x)$, where $N$ is possibly large. In the stochastic
setting, we sample stochastic derivatives at each iteration in order to form a
mini-batch approximation for the gradient of $F$. If we define:

$\displaystyle g_{S}(x)=\frac{1}{|S|}\sum\limits_{j\in S}\nabla F_{i}(x),$ (7)

where $S$ is a subset of $\\{1,\ldots,N\\}$, then condition (6) holds with
probability at least $1-\Delta$ if the batch size $S$ satisfies
$|S|=\mathcal{O}\left(\frac{\Delta^{2}}{L_{F}^{2}}+\frac{1}{N}\right)^{-1}$
(see Lemma 11 in AgKam:17 ).

######  Remark 1.

This example has been also considered in DeGlNe:13 ; Dvur:17 . However, in
these papers $\delta$ depends on the diameter of the domain of $f$, assumed to
be bounded. Our inexact oracle is more general and doesn’t require boundedness
of the domain of $f$, i.e., in our case $\delta=\Delta$, while in DeGlNe:13 ;
Dvur:17 , $\delta=2\Delta D$, where $D$ is the diameter of the domain of $f$.
Hence, our definition is more natural in this setting.

######  Example 2.

(Computations at shifted points) Let $F$ be differentiable with Lipschitz
continuous gradient with constant $L_{F}$ over $\text{dom}f$. For any
$x\in\text{dom}f$ we assume we can compute the exact value of the gradient,
albeit evaluated at a shifted point $\bar{x}$, different from $x$ and
satisfying $\|x-\bar{x}\|\leq\Delta$. Then, $F$ is equipped with a
$(\delta,L)$-oracle of degree $q=1$ as in Definition 2, with
$g_{\delta,L,1}(x)=\nabla F(\bar{x})$, $L=L_{F}$ and $\delta=L_{F}\Delta$.
Indeed, since $F$ is $L_{F}$ smooth, we have:

$\displaystyle F(y)$ $\displaystyle\leq F(x)+\langle\nabla
F(x),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2},$ $\displaystyle=F(x)+\langle\nabla
F(\bar{x}),y-x\rangle+\langle\nabla F(x)-\nabla
F(\bar{x}),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2},$ $\displaystyle\leq
F(x)+\langle\nabla
F(\bar{x}),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2}+L_{F}\|x-\bar{x}\|\|y-x\|,$

where the second inequality follows from the Cauchy-Schwartz inequality. This
proves our statement.

######  Remark 2.

This example was also considered in DeGlNe:13 ; Dvur:17 , with the
corresponding $(\delta,L)$-oracle having $\delta=L_{F}\Delta^{2}$, $L=2L_{F}$
and $q=0$. Note that our $L$ in Definition 2 is twice smaller than the
corresponding $L$ in DeGlNe:13 ; Dvur:17 .

######  Example 3.

(Accuracy measures for approximate solutions) Let us consider a $F$ that is
$L_{F}$ smooth, given by:

$\displaystyle F(x)=\max_{u\in U}\psi(x,u):=\max_{u\in U}G(u)+\langle
Au,x\rangle,$

where $A:\mathbb{E}\to\mathbb{E}^{*}$ is a linear operator and $G(\cdot)$ is a
differentiable strongly concave function with concavity parameter $\kappa>0$.
Under these assumptions, the maximization problem $\max_{u\in U}\psi(x,u)$ has
only one optimal solution $u^{*}(x)$ for a given $x$. Moreover, $F$ is convex
and smooth with Lipschitz continuous gradient $\nabla
F(x)=\nabla_{x}\psi(x,u^{*}(x))=Au^{*}(x)$ having Lipschitz constant
$L_{F}=\frac{1}{\kappa}\|A\|^{2}$ DeGlNe:13 . Suppose that for any
$x\in\text{dom}f$, one can compute $u_{x}$ an approximate minimizer of
$\psi(x,u)$ such that $\|u^{*}(x)-u_{x}\|\leq\Delta$. Then, $F$ is equipped
with $(\delta,L)$-oracle of degree $q=1$ with $\delta=\Delta\|A\|$, $L=L_{F}$
and $g_{\delta,L,1}(x)=Au_{x}$. Indeed, since $F$ has Lipschitz-continuous
gradient, we have:

$\displaystyle F(y)$ $\displaystyle\leq F(x)+\langle\nabla
F(x),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2},$
$\displaystyle=F(x)+\langle\nabla_{x}\psi(x,u^{*}(x)),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2},$
$\displaystyle=F(x)+\langle Au^{*}(x),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2},$
$\displaystyle=F(x)+\langle Au_{x},y-x\rangle+\langle
A(u^{*}(x)-u_{x}),y-x\rangle+\frac{L_{F}}{2}\|y-x\|^{2},$ $\displaystyle\leq
F(x)+\langle
Au_{x},y-x\rangle+\|A\|\|u^{*}(x)-u_{x}\|\|y-x\|+\frac{L_{F}}{2}\|y-x\|^{2},$
$\displaystyle\leq F(x)+\langle
Au_{x},y-x\rangle+\Delta\|A\|\|y-x\|+\frac{L_{F}}{2}\|y-x\|^{2}.$

Hence, our statement follows.

######  Remark 3.

This example was also considered in DeGlNe:13  with the corresponding
$(\delta,L)-$ oracle having $\delta=\Delta$, $L=2L_{F}$ and $q=0$, while in
our case, we have $\delta=\Delta\|A\|$, $L=L_{F}$ and $q=1$.

######  Example 4.

(Weak level of smoothness) Let $F$ be a proper lower semicontinuous function
with the subdifferential $\partial F(x)$ nonempty for all $x\in\text{dom}f$.
Assume that $F$ satisfies the following Hölder condition with
$H_{\nu}<\infty$:

$\displaystyle\lVert g(x)-g(y)\rVert\leq H_{\nu}\lVert y-x\rVert^{\nu},$ (8)

for all $g(x)\in\partial F(x)$, $g(y)\in\partial F(y)$, where
$x,y\in\text{dom}\,f$ and $\nu\in[0,1]$. Then, $F$ is equipped with
$(\delta,L)$-oracle of degree $q$ as in Definition 2, with
$g_{\delta,L,q}(x)\in\partial F(x)$, for any arbitrary degree $0\leq q<1+\nu$
and any accuracy $\delta>0$, and a constant $L$ depending on $\delta$ given
by:

$L(\delta)=\frac{1+\nu-q}{2-q}\left(\frac{H_{\nu}}{1+\nu}\right)^{\frac{2-q}{1+\nu-q}}\left(\frac{1-\nu}{\delta(2-q)}\right)^{\frac{1-\nu}{1+\nu-q}}.$

Indeed, we have from Hölder condition Nes:04 :

$\displaystyle F(x)-F(y)-\langle
g(y),x-y\rangle\leq\frac{H_{\nu}}{1+\nu}\lVert x-y\rVert^{1+\nu}.$

For any given $\delta>0$, we compute $L(\delta)$ such that the following
inequality holds:

$\displaystyle\frac{H_{\nu}}{1+\nu}\lVert
x-y\rVert^{1+\nu}\leq\frac{L(\delta)}{2}\lVert x-y\rVert^{2}+\delta\lVert
x-y\rVert^{q}.$

Denote $r=\lVert x-y\rVert$ and let $\lambda\in(0,1)$. Using the weighted
arithmetic-geometric mean inequality with $\alpha_{1}=\lambda$ and
$\alpha_{2}=1-\lambda$, we have:

$\displaystyle\frac{L(\delta)r^{2}}{2}+\delta r^{q}$
$\displaystyle=\lambda\frac{L(\delta)}{2\lambda}r^{2}+(1-\lambda)\frac{\delta}{1-\lambda}r^{q}$
$\displaystyle\geq\left(\frac{L(\delta)}{2\lambda}r^{2}\right)^{\lambda}\left(\frac{\delta}{1\\!-\\!\lambda}r^{q}\right)^{1\\!-\\!\lambda}\\!=\\!\left(\frac{L(\delta)}{2\lambda}\right)^{\lambda}\left(\frac{\delta}{1\\!-\\!\lambda}\right)^{1\\!-\\!\lambda}\\!\\!r^{2\lambda+q(1\\!-\\!\lambda)}.$

Thus
$\frac{H_{\nu}}{1+\nu}=\left(\frac{L(\delta)}{2\lambda}\right)^{\lambda}\left(\frac{\delta}{1-\lambda}\right)^{1-\lambda}$
and $1+\nu=2\lambda+q(1-\lambda)$. It follows that
$\lambda=\frac{1+\nu-q}{2-q}$, $1-\lambda=\frac{1-\nu}{2-q}$ and
$\frac{1}{\lambda}-1=\frac{1-\nu}{1+\nu-q}$. Hence, for a given positive
$\delta$ one may choose:

$\displaystyle
L(\delta)\\!=\\!2\lambda\left(\frac{H_{\nu}}{1\\!+\\!\nu}\right)^{\frac{1}{\lambda}}\left(\frac{1\\!-\\!\lambda}{\delta}\right)^{\frac{1}{\lambda}\\!-\\!1}\\!=\\!\frac{1\\!+\\!\nu\\!-\\!q}{2\\!-\\!q}\left(\frac{H_{\nu}}{1\\!+\\!\nu}\right)^{\frac{2\\!-\\!q}{1\\!+\\!\nu\\!-\\!q}}\left(\frac{1\\!-\\!\nu}{\delta(2\\!-\\!q)}\right)^{\frac{1\\!-\\!\nu}{1\\!+\\!\nu\\!-\\!q}},$

and this is our statement.  Note that if $\nu>0$, then we have $\partial
F(x)=\\{\nabla F(x)\\}$ for all $x$ and thus $F$ is differentiable. Indeed,
letting $y=x$ in (8) we get: $g(x)=\bar{g}(x)$. This implies that the set
$\partial F(x)$ has a single element, thus $F$ is differentiable. This example
covers large classes of functions. Indeed, when $\nu=1$, we get functions with
Lipschitz-continuous subgradient. For $\nu<1$, we get a weaker level of
smoothness. In particular, when $\nu=0$, we obtain functions whose
subgradients have bounded variation. Clearly, the latter class includes
functions whose subgradients are uniformly bounded by $M$ (just take
$H_{0}=2M$). It also covers functions smoothed by local averaging and
Moreau–Yosida regularization (see DeGlNe:13  for more details). We believe
that the readers may find other examples that satisfy our Definition 2 of an
inexact first-order oracle of degree $q$.

##  4 Inexact proximal gradient method

In this section, we introduce an inexact proximal gradient method based on the
previous inexact oracle definition for solving (non)convex composite
minimization problems (1). We derive complexity estimates for this algorithm
and study the dependence between the accuracy of the oracle and the desired
accuracy of the gradient or of the objective function. Hence, we consider the
following Inexact Proximal Gradient Method (I-PGM).

Algorithm 1 Inexact proximal gradient method (I-PGM)

  1. 1.

Given $x_{0}\in\text{dom}\;h$ and $0\leq q<2$.

  2. For $k\geq 0$ do:

  3. 2.

Choose $\delta_{k}$, $L_{k}$ and $\alpha_{k}$. Obtain
$g_{\delta_{k},L_{k},q}(x_{k})$.

  4. 3.

Compute
$x_{k+1}=\text{prox}_{\alpha_{k}h}\left(x_{k}-\alpha_{k}g_{\delta_{k},L_{k},q}(x_{k})\right)$.

Note that Algorithm 1 is an inexact proximal gradient method, where the
inexactness comes from the approximate computation of the (sub)gradient of
$F$, denoted $g_{\delta_{k},L_{k},q}(x_{k})$. In the next sections we analyze
the convergence behavior of this algorithm when
$g_{\delta_{k},L_{k},q}(x_{k})$ satisfies Definition 2.

###  4.1 Nonconvex convergence analysis

In this section we consider a nonconvex function $F$ that admits an inexact
first-order $(\delta,L)$-oracle of degree $q$ as in Definition 2. Using this
definition and inequality (4), for all $\rho>0$ we get the following upper
bound:

$\displaystyle F(x)-\Big{(}F(y)+\langle
g_{\delta,L,q}(y),x-y\rangle\Big{)}\leq\frac{L+q\rho}{2}\lVert
x-y\rVert^{2}+\frac{(2-q)\delta^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$ (9)

This inequality will play a key role in our convergence analysis. We define
the gradient mapping at iteration $k$ as
$g_{\delta_{k},L_{k},q}(x_{k})+p_{k+1}$, where $p_{k+1}\in\partial h(x_{k+1})$
such that $g_{k}+p_{k+1}=-\frac{1}{\alpha_{k}}(x_{k+1}-x_{k})$ (i.e.,
$p_{k+1}$ is the subgradient of $h$ at $x_{k+1}$ coming from the optimality
condition of the prox at $x_{k}$). Next we analyze the global convergence of
I-PGM in the norm of the gradient mapping. We have the following theorem:

######  Theorem 1.

Let $F$ be a nonconvex function admitting a $(\delta_{k},L_{k})$-oracle of
degree $q\in[0,2)$ at each iteration $k$, with $\delta_{k}\geq 0$ and
$L_{k}>0$ for all $k\geq 0$. Let $(x_{k})_{k\geq 0}$ be generated by I-PGM and
assume that $\alpha_{k}\leq\frac{1}{L_{k}+q\rho}$, for some arbitrary
parameter $\rho>0$. Then, there exists $p_{k+1}\in\partial h(x_{k+1})$ such
that:

$\displaystyle\sum_{j=0}^{k}\alpha_{j}\lVert
g_{\delta_{j},L_{j},q}(x_{j})+p_{j+1}\rVert^{2}\leq
f(x_{0})-f_{\infty}+\frac{\sum_{j=0}^{k}(2-q)\delta_{j}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$
(10)

Proof: Denote $g_{\delta_{k},L_{k},q}(x_{k})=g_{k}$. From the optimality
conditions of the proximal operator defining $x_{k+1}$, we have:

$\displaystyle g_{k}+p_{k+1}=-\frac{1}{\alpha_{k}}(x_{k+1}-x_{k}).$

Further, from inequality (9), we get:

$\displaystyle F(x_{k+1})\leq F(x_{k})+\langle
g_{k},x_{k+1}-x_{k}\rangle+\frac{L_{k}+q\rho}{2}\lVert
x_{k+1}-x_{k}\rVert^{2}+\frac{(2-q)\delta_{k}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}$
$\displaystyle=F(x_{k})\\!+\\!\langle
g_{k}\\!+\\!p_{k+1},x_{k+1}\\!-\\!x_{k}\rangle\\!-\\!\langle
p_{k+1},x_{k+1}\\!-\\!x_{k}\rangle\\!+\\!\frac{L_{k}+q\rho}{2}\lVert
x_{k+1}\\!-\\!x_{k}\rVert^{2}$
$\displaystyle\quad+\frac{(2-q)\delta_{k}^{\frac{2}{2\\!-\\!q}}}{2\rho^{\frac{q}{2-q}}}$
$\displaystyle\leq
F(x_{k})\\!-\\!\alpha_{k}\left(1-\frac{(L_{k}\\!+\\!q\rho)\alpha_{k}}{2}\right)\|g_{k}\\!+\\!p_{k+1}\|^{2}\\!+\\!h(x_{k})\\!-\\!h(x_{k+1})\\!+\\!\frac{(2\\!-\\!q)\delta_{k}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}$
$\displaystyle\leq
F(x_{k})-\frac{\alpha_{k}}{2}\|g_{k}+p_{k+1}\|^{2}+h(x_{k})-h(x_{k+1})+\frac{(2\\!-\\!q)\delta_{k}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}},$

where the second inequality follows from the convexity of $h$ and
$p_{k+1}\in\partial h(x_{k+1})$, and the last inequality follows from the
definition of $\alpha_{k}$. Hence, we get that:

$\displaystyle f(x_{k+1})\leq f(x_{k})-\frac{\alpha_{k}}{2}\lVert
g_{k}\\!+\\!p_{k+1}\rVert^{2}+\frac{(2-q)\delta_{k}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$

Summing up this inequality from $j=0$ to $j=k$ and using the fact that
$f(x_{k+1})\geq f_{\infty}$, where recall that $f_{\infty}$ denotes a finite
lower bound for the objective function, we get:

$\displaystyle\sum_{j=0}^{k}\frac{\alpha_{j}}{2}\lVert
g_{j}+p_{j+1}\rVert^{2}$ $\displaystyle\leq
f(x_{0})-f(x_{k+1})+\frac{\sum_{j=0}^{k}(2-q)\delta_{j}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}$
$\displaystyle\leq
f(x_{0})-f_{\infty}+\frac{\sum_{j=0}^{k}(2-q)\delta_{j}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$

Hence, our statement follows.

For a particular choice of the algorithm parameters, we can get simpler
convergence estimates.

######  Theorem 2.

Let the assumptions of Theorem 1 hold and consider for all $k\geq 0$:

$L_{k}=L,\;\delta_{k}=\frac{\delta}{(k+1)^{\frac{\beta(2-q)}{2}}},\;\alpha_{k}=\frac{1}{(L+q\rho)(k+1)^{\zeta}},\;\emph{where}\;\beta,\zeta\in[0,1).$

Then, we have:

$\displaystyle\min_{j=0:k}\lVert
g_{j}+p_{j+1}\rVert^{2}\leq\frac{2(L\\!+\\!q\rho)(f(x_{0})\\!-\\!f_{\infty})}{(1\\!-\\!\zeta)(k+1)^{1-\zeta}}\\!+\\!\frac{(2\\!-\\!q)(L\\!+\\!q\rho)\delta^{\frac{2}{2-q}}}{(1-\zeta)(1-\beta)\rho^{\frac{q}{2-q}}(k+1)^{\beta-\zeta}}.$
(11)

Proof:

Taking the minimum in the inequality (10), we get:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2(f(x_{0})-f_{\infty})}{\sum_{j=0}^{k}\alpha_{j}}+\frac{\sum_{j=0}^{k}(2-q)\delta_{j}^{\frac{2}{2-q}}}{\rho^{\frac{q}{2-q}}\sum_{j=0}^{k-1}\alpha_{j}}.$

Further, since we have:

$\displaystyle\sum_{j=0}^{k}\frac{1}{(L+q\rho)(j+1)^{\zeta}}=\sum_{j=1}^{k+1}\frac{1}{(L+q\rho)j^{\zeta}},$

and similarly for $\delta_{j}$, we get:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2(L+q\rho)(f(x_{0})-f_{\infty})}{\sum_{j=1}^{k+1}\frac{1}{j^{\zeta}}}+\frac{(2-q)(L+q\rho)\delta^{\frac{2}{2-q}}\sum_{j=1}^{k+1}\frac{1}{j^{\beta}}}{\rho^{\frac{q}{2-q}}\sum_{j=1}^{k+1}\frac{1}{j^{\zeta}}}.$

Since $0\leq\zeta<1$, then we have for all $k\geq 0$:

$\displaystyle(1-\zeta)(k+1)^{1-\zeta}\leq\frac{(k+2)^{1-\zeta}-1}{1-\zeta}$
$\displaystyle=\int_{1}^{k+2}\frac{1}{u^{\zeta}}du$
$\displaystyle\leq\sum_{j=1}^{k+1}\frac{1}{j^{\zeta}}\leq\int_{1}^{k+1}\left(\frac{1}{u^{\zeta}}\right)du+1\leq\frac{(k+1)^{1-\zeta}}{1-\zeta}.$

It follows that for all $k\geq 0$:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2(L\\!+\\!q\rho)(f(x_{0})\\!-\\!f_{\infty})}{(1\\!-\\!\zeta)(k+1)^{1-\zeta}}+\frac{(2\\!-\\!q)(L\\!+\\!q\rho)\delta^{\frac{2}{2-q}}}{(1-\zeta)(1-\beta)\rho^{\frac{q}{2-q}}(k+1)^{\beta-\zeta}}.$

Hence, our statement follows.

Let us analyze in more details the bound from Theorem 2. For simplicity,
consider the case $q=1$ (see Example 1). Then, we have:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2(L+\rho)(f(x_{0})-f_{\infty})}{(1-\zeta)(k+1)^{1-\zeta}}+\frac{(L+\rho)\delta^{2}}{\rho(1-\zeta)(1-\beta)(k+1)^{\beta-\zeta}}$
$\displaystyle=\frac{2L(f(x_{0})-f_{\infty})}{(1-\zeta)(k+1)^{1-\zeta}}+\frac{2\rho(f(x_{0})-f_{\infty})}{(1-\zeta)(k+1)^{1-\zeta}}$
$\displaystyle\quad+\frac{L\delta^{2}}{\rho(1-\zeta)(1-\beta)(k+1)^{\beta-\zeta}}+\frac{\delta^{2}}{(1-\zeta)(1-\beta)(k+1)^{\beta-\zeta}}.$

Denote $\Delta_{0}:=f(x_{0})-f_{\infty}$. Since parameter $\rho>0$ is a degree
of freedom, minimizing the right hand side of the previous relation w.r.t.
$\rho$ we get an optimal choice
$\rho=\frac{\delta\sqrt{L}}{\sqrt{2\Delta_{0}(1-\beta)}}(k+1)^{\frac{1-\beta}{2}}$.
Hence, replacing this expression for $\rho$ in the last inequality, we get:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2L\Delta_{0}}{(1-\zeta)(k+1)^{1-\zeta}}+\frac{2\delta\sqrt{2L\Delta_{0}}}{((1-\zeta)\sqrt{1-\beta})(k+1)^{\frac{1+\beta}{2}-\zeta}}$
$\displaystyle+\frac{\delta^{2}}{(1-\zeta)(1-\beta)(k+1)^{\beta-\zeta}}.$

This bound is of order
$\mathcal{O}\left(\frac{1}{k^{1-\zeta}}+\frac{\delta}{k^{\frac{1+\beta}{2}-\zeta}}+\frac{\delta^{2}}{k^{\beta-\zeta}}\right)$.
Note that, if $\beta>\zeta$, the gradient mapping $\min_{j=0:k}\lVert
g_{j}+p_{j+1}\rVert^{2}$ converges regardless of the accuracy of the oracle
$\delta$ and the convergence rate is of order
$\mathcal{O}(k^{-\text{min}(1-\zeta,\beta-\zeta)})$ (since we always have
$\frac{1+\beta}{2}-\zeta\geq\beta-\zeta$). Note that this is not the case for
$q=0$, where the convergence rate is of order
$\mathcal{O}\left(\frac{1}{k}+\delta\right)$, see also Dvur:17 . The following
corollary provides a convergence rate for general $q$, but for a particular
choice of the parameters $\zeta$ and $\beta$.

######  Corollary 1.

Let the assumptions of Theorem 2 hold and let assume that $\zeta=\beta=0$.
Then, we have the following convergence rates:

  1. 1.

If $0\leq q<2$ and $\rho=L$, then $\delta_{k}=\delta$,
$\alpha_{k}=\frac{1}{L+qL}$ and

$\displaystyle\min_{j=0:k}\lVert
g_{j}+p_{j+1}\rVert^{2}\leq\frac{2(q+1)L\Delta_{0}}{k+1}+(q+1)(2-q)L^{\frac{2-2q}{2-q}}\delta^{\frac{2}{2-q}}\quad\forall
k\geq 0.$

  2. 2.

If $1\leq q<2$, fixing the number of iterations $k$ and taking
$\rho=\frac{L^{\frac{2-q}{2}}\delta}{(2\Delta_{0})^{\frac{2-q}{2}}}(k+1)^{\frac{2-q}{2}}$,
then $\delta_{j}=\delta$, $\alpha_{j}=\frac{1}{L+q\rho}$ for all $j=0:k$ and

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2L\Delta_{0}}{k+1}\\!+\\!\frac{L^{\frac{2-q}{2}}(2\Delta_{0})^{\frac{q}{2}}\delta\\!+\\!(2-q)\delta
L^{1-\frac{q}{2}}(2\Delta_{0})^{\frac{q}{2}}}{(k+1)^{\frac{q}{2}}}\\!+\\!\frac{q(2-q)\delta^{2}L^{1-q}(2\Delta_{0})^{q-1}}{(k+1)^{q-1}}.$

Proof: Replacing $\zeta=\beta=0$ in inequality (11), we get:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2(L+q\rho)\Delta_{0}}{k+1}+\frac{(2-q)(L+q\rho)\delta^{\frac{2}{2-q}}}{\rho^{\frac{q}{2-q}}}$
$\displaystyle=\frac{2L\Delta_{0}}{k+1}+\frac{2q\rho\Delta_{0}}{k+1}+\frac{(2-q)L\delta^{\frac{2}{2-q}}}{\rho^{\frac{q}{2-q}}}+\frac{q(2-q)\delta^{\frac{2}{2-q}}}{\rho^{\frac{2q-2}{2-q}}}.$

If $0\leq q<2$, then taking $\rho=L$ in the last inequality we get the first
statement. Further, if $1\leq q<2$, minimizing over $\rho$ the second and the
third terms of the right side of the last inequality yields the optimal choice
$\rho=\frac{L^{\frac{2-q}{2}}\delta}{(2\Delta_{0})^{\frac{2-q}{2}}}(k+1)^{\frac{2-q}{2}}$.
Replacing this expression for $\rho$ in the last inequality, we get:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2L\Delta_{0}}{k+1}\\!+\\!\frac{L^{\frac{2-q}{2}}(2\Delta_{0})^{\frac{q}{2}}\delta\\!+\\!(2-q)\delta
L^{1-\frac{q}{2}}(2\Delta_{0})^{\frac{q}{2}}}{(k+1)^{\frac{q}{2}}}\\!+\\!\frac{q(2-q)\delta^{2}L^{1-q}(2\Delta_{0})^{q-1}}{(k+1)^{q-1}},$

and this is the second statement.

######  Remark 4.

Let us analyse in more details this convergence rate for Example 1. For $q=0$,
we have that $\delta=2D\Delta$ and $L=L_{F}$, where $D$ is the diameter of
$\text{dom}f$. Hence, the convergence rate in this case becomes:

$\displaystyle\min_{j=0:k}\lVert
g_{j}+p_{j+1}\rVert^{2}\leq\frac{4L_{F}\Delta_{0}}{k+1}+4DL_{F}\Delta.$

On the other hand, for $q=1$, we have $\delta=\Delta$ and $L=L_{F}$. Thus, we
get the following convergence rate:

$\displaystyle\min_{j=0:k}\lVert
g_{j}+p_{j+1}\rVert^{2}\leq\frac{4L_{F}\Delta_{0}}{k+1}+2\Delta^{2}.$

Hence, if we want to achieve $\min_{j=0:k}\lVert
g_{j}+p_{j+1}\rVert^{2}\leq\epsilon$, for $q=0$ we impose
$4DL_{F}\Delta\leq\epsilon/2$, which implies that one needs to compute an
approximate gradient with accuracy $\Delta=\mathcal{O}(\epsilon)$, while for
$q=1$ we impose $2\Delta^{2}\leq\epsilon/2$, meaning that one only needs to
compute an approximate gradient with accuracy
$\Delta=\mathcal{O}(\epsilon^{1/2})$. Hence, for this example, it is more
natural to use our inexact first-order oracle definition for $q=1$ than for
$q=0$, since it requires less accuracy for approximating the true gradient.

Note that in the second result of Corollary 1, the parameter $\rho$ depends on
the difference $\Delta_{0}=f(x_{0})-f_{\infty}$, and, usually, $f_{\infty}$ is
unknown. In practice, we can approximate $\Delta_{0}$ by using an estimate for
$f_{\infty}$ in place of its exact value. For example, one can consider
$\Delta_{0}^{k}=f(x_{0})-f_{\text{best}}^{k}$, where
$f_{\text{best}}^{k}=\min_{j=0:k}f(x_{j})-\varepsilon_{k}$ for some
$\varepsilon_{k}\geq 0$, see GeBe:99 . Under this setting, the sequence
$\varepsilon_{k}$ and the iterates of I-PGM corresponding to the case of the
second result of Corollary 1 are updated as follows:

Algorithm 2 Adaptive I-PGM algorithm when $f_{\infty}$ is unknown

  1. 1.

Given $\varepsilon_{0}>0$ and $f_{\text{best}}^{0}=f(x_{0})-\varepsilon_{0}$.
For $k\geq 0$ do:

  2. 2.

Compute $x_{k+1}$ by I-PGM with $\Delta_{0}^{k}=f(x_{0})-f_{\text{best}}^{k}$.
While $f(x_{k+1})<f_{\text{best}}^{k}$

    1. (a)

Set $\varepsilon_{k}=2\times\varepsilon_{k}$ and update
$f_{\text{best}}^{k}=\min\limits_{j=0:k}f(x_{j})-\varepsilon_{k}$.

    2. (b)

Re-compute $x_{k+1}$ by I-PGM method.

End While

  3. 3.

Set $\varepsilon_{k+1}=\frac{\varepsilon_{k}}{2}$.

This process is well defined, i.e., the ”while” step finishes in a finite
number of iterations. Indeed, one can observe that if
$\varepsilon_{k}\geq\min_{j=0:k}f(x_{j})-f_{\infty}$ then
$\varepsilon_{k}\geq\min_{j=0:k}f(x_{j})-f(x_{k+1})$, which implies that
$f(x_{k+1})\geq f_{\text{best}}^{k}$. Additionally, we have
$\varepsilon_{k}\leq 2(\min_{j=0:k}f(x_{j})-f_{\infty})$ for all $k\geq 0$.
Hence, we can still derive a convergence rate for the second result of
Corollary 1 using this adaptive process since one can observe that:

$\displaystyle f(x_{0})-f(x_{k+1})$ $\displaystyle\leq
f(x_{0})-f_{\text{best}}^{k}=\Delta_{0}^{k}.$

Additionally, we have the following bound on $\Delta_{0}^{k}$:

$\displaystyle\Delta_{0}^{k}$ $\displaystyle\leq
f(x_{0})-\min\limits_{j=0:k}f(x_{j})+2(\min_{j=0:k}f(x_{j})-f_{\infty})$
$\displaystyle=(f(x_{0})-f_{\infty})+(\min\limits_{j=0:k}f(x_{j})-f_{\infty}).$

Hence, we can replace in (10) the difference $\Delta_{0}=f(x_{0})-f_{\infty}$
with $\Delta_{0}^{k}$ and then the second statement of Corollary 1 remains
valid with $\Delta_{0}^{k}$ instead of $\Delta_{0}$.

######  Remark 5.

We observe that for $q=0$ we recover the same convergence rate as in Dvur:17 .
However, our result does not require the boundedness of the domain of $f$,
while in Dvur:17  the rate depends explicitly of the diameter of the domain of
$f$. Moreover, for $q>0$ our convergence bounds are better than in Dvur:17 ,
i.e., the coefficients of the terms in $\delta$ are either smaller or even
tend to zero, while in Dvur:17  they are always constant.

Further, let us consider the case of Example 4, where $F$ satisfies the Hölder
condition with constant $\nu\in(0,1]$ and $\beta=\zeta=0$. We have shown that
for any $\delta>0$ this class of functions can be equipped with a
$(\delta,L)$-oracle of degree $q<1+\nu$ with
$L=C(H_{\nu},q)\left(\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu-q}}$ (see
Example 4 for the expression of the constant $C(H_{\nu},q)$). In view of the
first result of Corollary 1, after $k$ iterations, we have:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$
$\displaystyle\leq\frac{2(q+1)\Delta_{0}L}{k+1}+(q+1)(2-q)L^{\frac{2-2q}{2-q}}\delta^{\frac{2}{2-q}}$
$\displaystyle=\frac{C_{1}}{k+1}\left(\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu-q}}+C_{2}\left(\frac{1}{\delta}\right)^{\frac{(1-\nu)(2-2q)}{(1+\nu-q)(2-q)}}\delta^{\frac{2}{2-q}}$
$\displaystyle=\frac{C_{1}}{k+1}\delta^{-\frac{1-\nu}{1+\nu-q}}+C_{2}\delta^{-\frac{(1-\nu)(2-2q)}{(1+\nu-q)(2-q)}+\frac{2}{2-q}}$
$\displaystyle=\frac{C_{1}}{k+1}\delta^{-\frac{1-\nu}{1+\nu-q}}+C_{2}\delta^{\frac{2\nu}{1+\nu-q}},$

where $C_{1}:=2(q+1)\Delta_{0}C(H_{\nu},q)$ and
$C_{2}=(q+1)(2-q)C(H_{\nu},q)^{\frac{2-2q}{2-q}}$. Since in this example we
can choose $\delta$, its optimal value can be computed from the following
equation:

$\displaystyle-\frac{C_{1}(1-\nu)}{(1+\nu-q)}\frac{1}{(k+1)}\delta^{\frac{q-2}{1+\nu-q}}+\frac{2\nu
C_{2}}{1+\nu-q}\delta^{\frac{-1+\nu+q}{1+\nu-q}}=0.$

Hence, we get:

$\displaystyle\delta=C_{3}(k+1)^{-\frac{1+\nu-q}{1+\nu}},$

where $C_{3}=\left(\frac{2\nu
C_{2}}{(1-\nu)C_{1}}\right)^{-\frac{1+\nu-q}{1+\nu}}$. Thus, replacing this
optimal choice of $\delta$ in the last inequality, we get:

$\displaystyle\min_{j=0:k}\lVert g_{j}+p_{j+1}\rVert^{2}$ $\displaystyle\leq
C_{1}C_{3}\left((k+1)^{-\left(1-\frac{1-\nu}{1+\nu}\right)}\right)+C_{2}C_{3}\left((k+1)^{-\frac{2\nu}{1+\nu}}\right)$
$\displaystyle=\frac{C_{3}(C_{1}+C_{2})}{(k+1)^{\frac{2\nu}{1+\nu}}}.$

######  Remark 6.

Note that our convergence rate of order $\mathcal{O}(k^{-\frac{2\nu}{1+\nu}})$
for Algorithm 1 (I-PGM) for nonconvex problems having the first term $F$ with
a Hölder continuous gradient (Example 4) recovers the rate obtained in Dvur:17
under the same settings.

Finally, let us now show that when the gradient mapping is small enough, i.e.,
$\|g_{k}+p_{k+1}\|$ is small, $x_{k+1}$ is a good approximation for a
stationary point of problem (1). Note that any choice
$\alpha_{k}\leq\frac{1}{L+q\rho_{k}}$ yields:

$\displaystyle\|x_{k+1}-x_{k}\|\leq\frac{1}{L}\left\|\frac{1}{\alpha_{k}}(x_{k+1}-x_{k})\right\|=\frac{1}{L}\|g_{k}+p_{k+1}\|.$

Hence, if the gradient mapping is small, then the norm of the difference
$\|x_{k+1}-x_{k}\|$ is also small.

######  Theorem 3.

Let $(x_{k})_{k\geq 0}$ be generated by I-PGM and let $p_{k+1}\in\partial
h(x_{k+1})$. Assume that we are in the case of Example 1. Then, we have:

$\displaystyle\emph{dist}(0,\partial
f(x_{k+1}))\leq\|g_{\Delta,L_{F},q}(x_{k})+p_{k+1}\|+L_{F}\|x_{k+1}-x_{k}\|+\Delta.$

Further, if we are in the case of Example 4, then we have:

$\displaystyle\emph{dist}(0,\partial
f(x_{k+1}))\leq\|g(x_{k})+p_{k+1}\|+H_{\nu}\|x_{k+1}-x_{k}\|^{\nu},\;\;g(x_{k})\in\partial
F(x_{k}).$

Proof: Let us consider Example 1, where $F$ is $L_{F}$ smooth and $h$ is
convex. Since $\nabla F(x_{k+1})+p_{k+1}\in\partial f(x_{k+1})$, then we have:

$\displaystyle\|\nabla F(x_{k+1})+p_{k+1}\|$
$\displaystyle\leq\|g_{\Delta,L_{F},q}(x_{k})+p_{k+1}\|+\|\nabla
F(x_{k})-g_{\Delta,L_{F},q}(x_{k})\|+\|\nabla F(x_{k+1})-\nabla F(x_{k})\|$
$\displaystyle\leq\|g_{\Delta,L_{F},q}(x_{k})+p_{k+1}\|+\Delta+L_{F}\|x_{k+1}-x_{k}\|.$

Further, let us assume that we are in the case of Example 4. Then, we have
$g(x_{k})\in\partial F(x_{k})$. Further, let $g(x_{k+1})\in\partial
F(x_{k+1})$, then we get:

$\displaystyle\|g(x_{k+1})+p_{k+1}\|$
$\displaystyle\leq\|g(x_{k})+p_{k+1}\|+\|g(x_{k+1})-g(x_{k})\|$
$\displaystyle\leq\|g(x_{k})+p_{k+1}\|+H_{\nu}\|x_{k+1}-x_{k}\|^{\nu}.$

This proves our statements.

Thus, for $\|\frac{1}{\alpha_{k}}(x_{k+1}-x_{k})\|=\|g_{k}+p_{k+1}\|$ small,
$x_{k+1}$ is an approximate stationary point of problem (1). Note that our
convergence rates from this section are better as $q$ increases, i.e., the
terms depending on $\delta$ are smaller for $q>0$ than for $q=0$. In
particular, the power of $\delta$ in the convergence estimate is higher for
$q\in(0,1)$ than for $q=0$, while for $q\geq 1$ the coefficients of $\delta$
even diminish with $k$. Hence, it is beneficial to have an inexact first-order
oracle of degree $q>0$, as this allows us to work with less accurate
approximation of the (sub)gradient of the nonconvex function $F$ than for
$q=0$.

###  4.2 Convex convergence analysis

In this section, we analyze the convergence rate of I-PGM for problem (1),
where $F$ is now assumed to be a convex function. By adding extra information
to the oracle (5), we consider the following modification of Definition 2:

######  Definition 3.

Given a convex function $F$, then it is equipped with an inexact first-order
$(\delta,L)$-oracle of degree $0\leq q<2$ if for any $y\in\text{dom}f$ we can
compute a vector $g_{\delta,L,q}(y)$ such that:

$\displaystyle 0\\!\leq\\!F(x)\\!-\\!\left(F(y)\\!+\\!\langle
g_{\delta,L,q}(y),x\\!-\\!y\rangle\right)\\!\leq\\!\frac{L}{2}\|x\\!-\\!y\|^{2}\\!\\!+\\!\delta\|y\\!-\\!x\|^{q}\;\;\;\forall
x\\!\in\\!\text{dom}f.$ (12)

Note that Example 4 satisfies this definition. In (12), the zero-order
information is considered to be exact. This is not the case in DeGlNe:13 ,
which considers the particular choice $q=0$ . Further, the first-order
information $g_{\delta,L,q}$ is a subgradient of $f$ at $y$ in (12), while in
DeGlNe:13  it is a $\delta$-subgradient. However, using this inexact first-
order oracle of degree $q$, I-PGM provides better rates compared to DeGlNe:13
. From (12) and (4), we get:

$\displaystyle 0\leq F(x)\\!-\\!\left(F(y)\\!+\\!\langle
g_{\delta,L,q}(y),x\\!-\\!y\rangle\right)\leq\frac{L\\!+\\!q\rho}{2}\lVert
x\\!-\\!y\rVert^{2}+\frac{(2-q)\delta_{q}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}},$
(13)

for all $\rho>0$. Next, we analyze the convergence rate of I-PGM in the convex
setting. We have the following convergence rate:

######  Corollary 2.

Let $F$ be a convex function admitting a $(\delta,L)$-oracle of degree
$q\in[0,2)$ (see Definition 3). Let $(x_{k})_{k\geq 0}$ be generated by I-PGM
and assume that $\alpha_{k}=\frac{1}{L+q\rho}$, with $\rho>0$. Define
$\hat{x}_{k}=\frac{\sum_{i=0}^{k}x_{i+1}}{k+1}$ and $R=\|x_{0}-x^{*}\|$. Then,
we have:

$\displaystyle
f(\hat{x}_{k})-f^{*}\leq\frac{(L+q\rho)R^{2}}{2k}+\frac{(2-q)\delta^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$
(14)

Proof: Follows from (13) and Theorem 2 in DeGlNe:13 .

Since we have the freedom of choosing $\rho$, let us minimize the right hand
side of (14) over $\rho$. Then, $\rho$ must satisfy
$\frac{qR^{2}}{2k}-\frac{q\delta^{\frac{2}{2-q}}}{2}\rho^{\frac{-2}{2-q}}=0.$
Thus, the optimal choice is $\rho=\frac{\delta}{R^{2-q}}k^{\frac{2-q}{2}}$.
Finally, fixing the number of iterations $k$ and replacing this expression in
equation (14), we get:

$\displaystyle
f(\hat{x}_{k})-f^{*}\leq\frac{LR^{2}}{2k}+\delta\frac{(2+q)R^{q}}{2k^{\frac{q}{2}}}.$

One can notice that our rate in function values is of order
$\mathcal{O}(k^{-1}+\delta k^{-\frac{q}{2}})$, while in DeGlNe:13  the rate is
of order $\mathcal{O}(k^{-1}+\delta)$. Hence, when $q>0$, regardless of the
accuracy of the oracle, our second term diminishes, while in DeGlNe:13  it
remains constant. Hence, our new definition of inexact oracle of degree $q$,
Definition 3, is also beneficial in the convex case when analysing proximal
gradient type methods, i.e., large $q$ yields better rates.

We also consider an extension of the fast inexact projected gradient method
from DeGlNe:13 , where the projection is replaced by a proximal step with
respect to the function $h$ (see Nes:13 ), called FI-PGM. Note that the
inexactness in FI-PGM comes from the approximate computation of the
(sub)gradient of $F$, denoted $g_{\delta_{k},L_{k},q}(x_{k})$, as given in
Definition 3. Let $(\theta_{k})_{k\geq 0}$ be a sequence such that:

$\displaystyle\theta_{0}\in(0,1],\quad\frac{\theta_{k+1}^{2}}{L_{k+1}}\leq
A_{k+1}:=\sum_{i=0}^{k+1}\frac{\theta_{i}}{L_{i}}\;\;\;\forall k\geq 0.$ (15)

Then, the fast inexact proximal gradient method (FI-PGM) is as follows:

Algorithm 3 Fast inexact proximal gradient method (FI-PGM)

  1. 1.

Given $x_{0}\in\text{dom}\;h$, $\theta_{0}\in(0,1]$ and $0\leq q<2$.

  2. For $k\geq 0$ do:

  3. 2.

Choose $\delta_{k}$, $L_{k}$ and $\alpha_{k}$. Obtain
$g_{\delta_{k},L_{k},q}(x_{k})$.

  4. 3.

Compute
$y_{k}=\text{prox}_{\alpha_{k}h}\left(x_{k}-\alpha_{k}g_{\delta_{k},L_{k},q}(x_{k})\right)$.

  5. 4.

Compute
$z_{k}=\operatorname*{arg\,min}\frac{1}{2}\|x-x_{0}\|^{2}+\sum_{i=0}^{k}\frac{\theta_{i}}{L_{i}}\langle
g_{\delta_{k},L_{k},q}(x_{i}),x-x_{i}\rangle+h(x)$.

  6. 5.

Choose $\theta_{k+1}$ satisfying condition (15) and compute
$A_{k+1}=\sum_{i=0}^{k+1}\frac{\theta_{i}}{L_{i}}.$

  7. 6.

Compute $x_{k+1}=\tau_{k}y_{k}+(1-\tau_{k})z_{k}$ using
$\tau_{k}=\frac{\theta_{k+1}}{A_{k+1}L_{k+1}}$.

Using a similar proof as in DeGlNe:13 , we get the following convergence rate
for FI-PGM algorithm:

######  Corollary 3.

Let $F$ satisfy the assumptions of Lemma 2 and $(y_{k})_{k\geq 0}$ be
generated by FI-PGM. Then, for all $\rho>0$, we have the following rate:

$\displaystyle
f(y_{k})-f^{*}\leq\frac{4(L+q\rho)R^{2}}{(k+1)(k+2)}+\frac{(k+3)(2-q)\delta^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}.$
(16)

Proof: The proof follows from (13) and Theorem 4 in DeGlNe:13 . The optimal
$\rho$ in the right hand side of inequality (16) is

$\displaystyle\rho^{*}=\frac{\big{(}(k+1)(k+2)(k+3)\big{)}^{\frac{2-q}{2}}}{(8R^{2})^{\frac{2-q}{2}}}\delta.$

Further, replacing $\rho$ with its optimal value in the inequality (16), we
get

$\displaystyle f(y_{k})-f^{*}$
$\displaystyle\leq\frac{4LR^{2}}{(k+1)(k+2)}+\frac{q8^{\frac{q}{2}}R^{q}(k+3)}{2((k+1)(k+2)(k+3))^{\frac{q}{2}}}\delta$
$\displaystyle+\frac{(2-q)8^{\frac{q}{2}}R^{q}(k+3)}{2((k+1)(k+2)(k+3))^{\frac{q}{2}}}\delta$
$\displaystyle=\frac{4LR^{2}}{(k+1)(k+2)}+\frac{8^{\frac{q}{2}}R^{q}(k+3)}{((k+1)(k+2)(k+3))^{\frac{q}{2}}}\delta.$
$\displaystyle=\mathcal{O}\left(\frac{LR^{2}}{k^{2}}\right)+\mathcal{O}\left(\frac{R^{q}}{k^{\frac{3q}{2}-1}}\delta\right).$

Hence, if $q>\frac{2}{3}$, then FI-PGM doesn’t have error accumulation under
our inexact oracle as the rate is of order $\mathcal{O}\left(k^{-2}+\delta
k^{1-\frac{3q}{2}}\right)$, while in DeGlNe:13  the FI-PGM scheme always
displays error accumulation, as the convergence rate is of order
$\mathcal{O}(k^{-2}+\delta k)$. Therefore, the same conclusion holds as for
I-PGM, i.e., for the FI-PGM scheme in the convex setting it is beneficial to
have an inexact first-order oracle with large degree $q$.

######  Remark 7.

In our Definition 2 we have considered exact zero-order information. However,
it is possible to change this definition considering also inexact zero-order
information for the nonconvex case. More precisely, we can change Definition 2
as follows

$\left\\{\begin{split}&F_{\delta_{0}}(x)-F(x)\leq\delta_{0},\\\
&F(x)\\!-\\!\left(F_{\delta_{0}}(y)+\langle
g_{\delta,L,q}(y),x-y\rangle\right)\\!\leq\\!\frac{L}{2}\|x-y\|^{2}+\delta\|x-y\|^{q}.\end{split}\right.$

With this new definition, the convergence result in Theorem 1 becomes:

$\displaystyle\sum_{j=0}^{k}\alpha_{j}\|g_{\delta_{j},L_{j},q}(x_{j})+p_{j+1}\|^{2}\leq
f(x_{0})-f_{\infty}+\frac{\sum_{j=0}^{k}(2-q)\delta_{j}^{\frac{2}{2-q}}}{2\rho^{\frac{q}{2-q}}}+\sum_{j=0}^{k}\delta_{0}.$

Hence the rate in this case is also influenced by the inexactness of the zero-
order information (i.e., $\delta_{0}$). Note that for the convex case, the
previous extension is not possible in Definition 3 when $q>0$, since we must
have:

$\displaystyle 0\leq F(x)\\!-\\!\left(F_{\delta_{0}}(y)+\langle
g_{\delta,L,q}(y),x-y\rangle\right)\\!\leq\\!\frac{L}{2}\|x-y\|^{2}+\delta\|x-y\|^{q},$

which implies for $x=y$ that $F(x)=F_{\delta_{0}}(x)$. Since we want to have
consistency between Definitions 2 and 3, we have chosen to work with the exact
zero-order information in our previous nonconvex convergence analysis.

##  5 Numerical simulations

In this section, we evaluate the performance of I-PGM for a composite problem
arising in image restoration. Namely, we consider the following nonconvex
optimization problem StThPa:17 :

$\displaystyle\min_{x\in\mathbb{R}^{n}}\sum_{i=1}^{N}\text{log}\left(\left(a_{i}^{T}x-b_{i}\right)^{2}+1\right),$
(17) $\displaystyle\text{s.t.}\;\;\|x\|_{1}\leq R,$

where $R>0$, $b\in\mathbb{R}^{N}$ and $a_{i}\in\mathbb{R}^{n}$, for $i=1:N$.
In image restoration, $b$ represents the noisy blurred image and
$A=(a_{1},\cdots,a_{N})\in{\color[rgb]{0,0,0}\mathbb{R}^{n\times N}}$ is a
blur operator StThPa:17 . This problem fits into our general problem (1), with
$F(x)=\sum_{i=1}^{N}\text{log}\left(\left(a_{i}^{T}x-b_{i}\right)^{2}+1\right)$,
which is a nonconvex function with Lipschitz continuous gradient of constant
$L_{F}:=\sum_{i=1}^{N}\|a_{i}\|^{2}$, and $h(x)$ is the indicator function of
the bounded convex set $\\{x:\|x\|_{1}\leq R\\}$. We generate the inexact
oracle by adding normally distributed random noise $\delta$ to the true
gradient, i.e., $g_{\delta,L,q}(x):=\nabla F(x)+\delta$. This is a particular
case of Example 1. However, for all $x$ and $y$ satisfying $\|x\|\leq R$,
$\|y\|\leq R$, we have the following:

$\displaystyle\delta\|x-y\|$
$\displaystyle=\delta\|x-y\|^{1-q}\|x-y\|^{q}\leq\delta(2R)^{1-q}\|x-y\|^{q}.$

Thus, this example satisfies Definition 2 for all $q\in[0,1]$. We apply I-PGM
for this particular example where we consider three choices for the degree
$q$: $0$, $1/2$ and $1$. Recall that the convergence rate of I-PGM with
constant step size is (see Corollary 1, first statement):

$\displaystyle\min_{j=0:k}\lVert
g_{j}\\!+\\!p_{j+1}\rVert^{2}\leq\frac{2(q\\!+\\!1)L(f(x_{0})\\!-\\!f^{*})}{k+1}+(q\\!+\\!1)(2\\!-\\!q)L^{\frac{2-2q}{2-q}}\delta^{\frac{2}{2-q}}.$
(18)

At each iteration of I-PGM we need to solve the following convex subproblem:

$\displaystyle\min_{x\in\mathbb{R}^{n}}F(x_{k})+\langle
g_{\delta,q}(x_{k}),x-x_{k}\rangle+\frac{L+q\rho}{2}\|x-x_{k}\|^{2},\;\;\text{s.t.}\;\;\|x\|_{1}\leq
R.$

This subproblem has a closed form solution (see e.g., Tib:96 ). We compare
I-PGM with constants step size $\alpha_{k}=\frac{1}{2(L_{F}+q\rho)}$ and
$\rho=L_{F}$ for three choices of $q=0,1/2,1$ and three choices of noise norm
$\|\delta\|\leq 0.1,1,3$, respectively. The results are given in Fig. 1
(dotted lines), where we plot the evolution of the error
$\min_{j=0:k}\|\frac{1}{\alpha_{k}}(x_{j+1}-x_{j})\|^{2}$, which corresponds
to the gradient mapping. In the same figure we also plot the theoretical
bounds (18) for $q=0,1/2,1$ (full lines). Our main figures are Figure 1(a),
(c), and (d), while Figure 1(b) is a subfigure (zoom) of Figure 1(a),
displaying only the first 300 iterations. Moreover, one can see in these main
figures (i.e., Figure 1(a), (c), and (d)) that the behaviour of our algorithm
for $q=1$ is better than for $q=1/2$. Similarly, the behaviour of our
algorithm for $q=1/2$ is better than for $q=0$. One can observe these better
behaviours after 300 iterations when the error $\delta$ is small (see Figure
1(c) and (d)). However, when the error $\delta$ is large, we need to perform a
larger number of iterations before we can observe these behaviours, (see
Figure 1(a) and (b)). This is natural, since large errors on the gradient
approximation must have impact on the convergence speed. Hence, as the degree
$q$ increases or the norm of the noise decreases, better accuracies for the
norm of the gradient mapping can be achieved, which supports our theoretical
findings.

Moreover, from the numerical simulations, one can observe that the gap between
the theoretical and the practical bounds is large in Figure 1(c) and (d). We
believe that this happens because, in the convergence analysis, the
theoretical bounds are derived under worst-case scenarios (i.e., the
convergence analysis must account for the worst case direction generated by
the inexact first-order oracle, while in practical implementations, which
often involve randomness, one usually doesn’t encounter these worst-case
directions). However, the simulations in Figure 1(a) show that the gap between
the theoretical bounds and the practical behavior is not too large. More
precisely, we have generated at each iteration 100 random directions and, in
order to update the new point, we have chosen the worst direction with respect
to the gradient mapping (i.e., the largest) $\|x_{k+1}-x_{k}\|$). The results
are given in Figure 1(a), where one can see that the theoretical and practical
bounds are getting closer for sufficiently large number of iterations.

(a) $\|\delta\|\leq 3$

(b) $\|\delta\|\leq 3$

(c) $\|\delta\|\leq 1$

(d) $\|\delta\|\leq 0.1$

Figure 1: Practical (dotted lines) and theoretical (full lines) performances
of the I-PGM algorithm for different choices of $q$ and $\delta$, and with
$R=4$. Figure (b) represents a zoom of the left corner from Figure (a).

Acknowledgments The research leading to these results has received funding
from: ITN-ETN project TraDE-OPT funded by the European Union’s Horizon 2020
Research and Innovation Programme under the Marie Skolodowska-Curie grant
agreement No. 861137; UEFISCDI PN-III-P4-PCE-2021-0720, under project L2O-MOC,
nr. 70/2022.

Data sharing not applicable to this article as no datasets were generated or
analyzed during the current study.

## References

  * (1) A. Agafonov, D. Kamzolov, P. Dvurechensky, A. Gasnikov, M. Takac, _Inexact Tensor Methods and Their Application to Stochastic Convex Optimization_ , Optimization Methods and Software, doi.org/10.1080/10556788.2023.2261604, 2017.
  * (2) A. Beck, _First-order methods in optimization_ , vol. 25, SIAM, 2017.
  * (3) L. Bogolubsky, G. Gusev, A. Raigorodskii, A. Tikhonov, M. Zhukovskii, P. Dvurechensky, A. Gasnikov, Yu. Nesterov, _Learning supervised PageRank with gradient-based and gradient-free optimization methods_ , 30th Conference on Neural Information Processing Systems, 2016.
  * (4) L. Bottou, _Large-scale machine learning with stochastic gradient descent_ , 19th International Conference on Computational Statistics, 2010.
  * (5) M.B. Cohen, J. Diakonikolas, L. Orecchia, _On Acceleration with Noise-Corrupted Gradients_ , International Conference on Machine Learning, 2018.
  * (6) A. d’Aspremont, _Smooth optimization with approximate gradient_ , SIAM Journal on Optimization, 19(3): 1171–1183, 2008.
  * (7) O. Devolder, F. Glineur, Yu. Nesterov, _First-order methods of smooth convex optimization with inexact oracle_ , Math. Prog., 146: 37–75, 2013.
  * (8) P. Dvurechensky, A. Gasnikov, _Stochastic intermediate gradient method for convex problems with stochastic inexact oracle_ , Journal of Optimization Theory and Applications, 171(1): 121–145, 2016.
  * (9) P. Dvurechensky, _A gradient method with inexact oracle for composite nonconvex optimization_ , Computer Research and Modeling, 14(2), 2022.
  * (10) A. Geary and D.P. Bertsekas, _Incremental subgradient methods for nondifferentiable optimization_ , Conference on Decision and Control, 1999.
  * (11) J-B. Hiriart-Urruty, _New concepts in nondifferentiable programming_ , Memoires de la Societe Mathematique de France, 60: 57–85, 1979.
  * (12) L. Stella, A. Themelis and P. Patrinos, _Forward–backward quasi-Newton methods for nonsmooth optimization problems_ , Computational Optimization and Applications, 67: 443–487, 2017.
  * (13) B. Mordukhovich, _Variational analysis and generalized differentiation: basic theory_ , Springer, 2006.
  * (14) Yu. Nesterov, _Introductory lectures on convex optimization: A basic course_ , Springer, 2004.
  * (15) Yu. Nesterov, _Gradient methods for minimizing composite functions_ Mathematical programming 140.1, 125–161, 2013.
  * (16) B.T. Polyak, _Gradient methods for the minimisation of functionals_ , Computational Mathematics and Mathematical Physics, 3(4): 864–878, 1963.
  * (17) R. Rockafellar and R. Wets, _Variational Analysis_ , Springer, 1998.
  * (18) F.S. Stonyakin, D. Dvinskikh, P. Dvurechensky, A. Kroshnin, O. Kuznetsova, A. Agafonov, A. Gasnikov, A. Tyurin, C.A. Uribe, D. Pasechnyuk, S. Artamonov, _Gradient methods for problems with inexact model of the objective_ , International Conference on Mathematical Optimization Theory and Operations Research, 2019.
  * (19) R. Tibshirani, _Regression shrinkage and selection via the Lasso_ , Journal of the Royal Statistical Society, 58(1): 267–288, 1996.
  * (20) P.W. Wang and C-J. Lin, _Iteration complexity of feasible descent methods for convex optimization_ , Journal of Machine Learning Research, 15(4), 1523–1548, 2014.