# Affine invariant convergence rates of the conditional gradient method

Javier F. Peña Tepper School of Business, Carnegie Mellon University, USA,
<EMAIL_ADDRESS>
###### Abstract

We show that the conditional gradient method for the convex composite problem

$\min_{x}\\{f(x)+\Psi(x)\\}$

generates primal and dual iterates with a duality gap converging to zero
provided a suitable growth property holds and the algorithm makes a judicious
choice of stepsizes. The rate of convergence of the duality gap to zero ranges
from sublinear to linear depending on the degree of the growth property. The
growth property and convergence results depend on the pair $(f,\Psi)$ in an
affine invariant and norm-independent fashion.

##  1 Introduction

We consider the conditional gradient method for the composite minimization
problem

$\min_{x}\\{f(x)+\Psi(x)\\}$

where $f:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$ and
$\Psi:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$ are closed
convex functions, $f$ is differentiable, and there is an available oracle for
the mapping

$g\mapsto\operatorname*{arg\,min}\\{\left\langle g,y\right\rangle+\Psi(y)\\}.$

The traditional format of the conditional gradient method (also known as the
Frank-Wolfe algorithm) as discussed in [5, 10] corresponds to the case when
$\Psi$ is the indicator function of a compact convex set in
${\mathbb{R}}^{n}$. Some of the most attractive features of the conditional
gradient method are its affine invariance, norm-independence, and lack of
reliance on any projection mapping. These features stand in stark contrast to
those of most other first-order methods. It is therefore natural to seek
convergence results for the conditional gradient method that are affine
invariant and norm-independent as any otherwise convergence result would
typically be loose due to dependence on spurious factors.

We show that the conditional gradient method generates primal and dual
iterates with a duality gap converging to zero provided a suitable growth
property holds (see (10)) and the algorithm makes a judicious choice of
stepsizes (see (9) and (16)). The rate of convergence of the duality gap to
zero ranges from sublinear to linear (see Theorem 1 and Theorem 2) depending
on the degree of the growth property. The growth property and convergence
results depend on the pair $(f,\Psi)$ in an affine invariant and norm-
independent fashion. In fact, our main developments do not rely on any norms
at all.

Our work is inspired by recent developments of Nesterov [19], Ghadimi [8], and
Kerdreux et al [12]. Under the assumption that the domain of $\Psi$ is
bounded, Nesterov [19] established a ${\mathcal{O}}(1/k^{\nu})$ convergence
rate for the conditional gradient method when $\nabla f$ is $\nu$-Hölder
continuous. Nesterov [19] also showed the stronger convergence rate
${\mathcal{O}}(1/k^{2\nu})$ under the additional assumption that $\Psi$ is
strongly convex. Ghadimi [8] showed an even stronger linear rate of
convergence when $\nabla f$ is Lipschitz continuous and $\Psi$ is strongly
convex for a judicious choice of stepsizes. On the other hand, Kerdreux et al.
[12] considered the case when $\nabla f$ is Lipschitz continuous and $\Psi$ is
the indicator function of a uniformly convex set. Kerdreux et al. [12] showed
that the convergence rate ranges from sublinear to linear depending on the
degree of uniform convexity of the set. The results in [8, 12, 19] are all
norm-dependent since they rely on Hölder continuity and uniform convexity. The
norm-dependence of the results in [8, 12, 19] in turn implies that they are
not affine invariant when the norms are not affine invariant, which is
typically the case.

The affine invariance and norm-independence properties of the conditional
gradient method suggest that there should be an affine invariant and norm-
independent approach to obtain the sublinear to linear spectrum of convergence
rates. The central contribution of this paper is to show that this is indeed
the case. To that end, we establish general convergence results (Theorem 1 and
Theorem 2) provided a growth property (10) holds and the stepsizes are
judiciously chosen. The growth property (10) can be seen as an extension of
the curvature constant proposed by Jaggi [10]. It also has a flavor similar to
that of the relative smoothness and relative continuity properties in the
context of Bregman proximal methods as discussed in [2, 17, 18, 22, 23, 24].
Our main convergence results (Theorem 1 and Theorem 2), obtained via the
growth property (10), are stated in terms of the duality gap between the
primal and dual iterates that the algorithm generates. We also develop
parallel results (Theorem 3 and Theorem 4) on the suboptimality gap via a
relaxation (40) of the growth property (10).

Aside from its natural compatibility with the properties of the conditional
gradient method, the affine invariance and norm independence of our approach
yields convergence results that are sharper and more general than previous
approaches that do not have these two fundamental properties. More precisely,
as we detail in Section 3, Section 4, and Section 5, our convergence results
not only subsume some of the norm-dependent convergence results in [6, 8, 12,
19, 25] but are also at least as sharp as these previous norm-dependent
results for any choice of norms. Put differently, the affine invariance and
norm-independence of our main convergence results automatically circumvent any
possible spurious overhead due to a particular choice of norms or affine
scaling. It is also noteworthy that our main results (Theorem 1, Theorem 2,
Theorem 3, and Theorem 4) rely only on straightforward stepsize procedures
that are adaptive to the typically unknown parameters associated to the growth
or weak growth properties. This stands in sharp contrast to some of the
algorithmic schemes in [6, 8, 12, 19, 25] that rely on knowledge of specific
parameters like Lipschitz continuity constants.

This article is related to a number of papers in the rich and increasingly
growing literature on the conditional gradient method. Our primal-dual
approach, with emphasis on bounding the duality gap for the conditional
gradient iterates, is similar in spirit to the approaches used by Bach [1],
Freund and Grigas [5], and Jaggi [10]. Like all of [1, 5, 10], our main
results provide upper bounds on the duality gap between the (primal)
conditional gradient iterates and some canonical dual iterates that the
algorithm also generates. However, our central goal and main results are
fundamentally different from those in [1, 5, 10]. Bach [1] focuses primarily
on the equivalence between the conditional gradient and mirror descent
algorithms. All of the convergence results in [1, 5, 10] are of order
${\mathcal{O}}(1/k)$ or some minor variations. By contrast, our main focus is
the spectrum of convergence rates of the conditional gradient method ranging
from sublinear to linear. The latter goal is also pursued in the recent
articles [8, 12, 19, 25] albeit in a norm-dependent fashion. The articles [13,
21] also establish a spectrum of convergence rates ranging from sublinear to
linear but for more elaborate variants of the conditional gradient method that
include various types of search directions, restart procedures, and/or are
restricted to specific types of domains. As we detail in Section 3, Section 4,
and Section 5, our affine invariant and norm independent results subsume,
sharpen, and extend most of the norm-dependent results previously derived in
[6, 8, 12, 19, 25]. Our developments, driven by affine-invariance, are in the
same spirit as those of Kerdreux et al. [14]. However, the approach in [14]
applies only to the case when $\Psi$ is the indicator function of a strongly
convex set and focuses on an affine-invariant directional smoothness property
that ensures linear convergence. By contrast, our work applies to general
$\Psi$ and relies on the growth property (10) that leads to convergence rates
covering the entire range from sublinear to linear.

The remaining sections of the paper are organized as follows. Section 2
presents our main developments, namely the affine invariant and norm-
independent growth property (10) and convergence results for the conditional
gradient method. For ease of exposition, we include two convergence results.
First, Theorem 1 relies on the assumption that the stepsizes are chosen via
the exact line-search (9). Theorem 2 shows that the convergence rates in
Theorem 1 continue to hold, albeit with some more complicated constants, for
the more flexible and easily implementable choice of stepsizes (16). Section 3
details some classes of problems that satisfy the growth property (10). As a
byproduct, we recover, sharpen, and extend some of the norm-dependent
convergence rates established in [8, 12, 19]. Section 4 presents developments
parallel to those in Section 2 but for the suboptimality gap by relying on the
weak version (40) of the growth property (10). Section 5 presents a more
flexible and general local growth property that in turn yields local
convergence results for the conditional gradient method.

##  2 Growth property and affine invariant convergence

Consider the composite minimization problem

$\min_{x}\\{f(x)+\Psi(x)\\}$ (1)

where both $f:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$ and
$\Psi:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$ are closed
convex functions. Algorithm 1 describes the conditional gradient algorithm for
(1). The algorithm relies on the following assumptions about (1):

  * A1.

The function $f$ is differentiable on ${\mathrm{dom}}(\Psi)$.

  * A2.

A point in the following set of minimizers exists and is computable for all
$x\in{\mathrm{dom}}(f)$

$\operatorname*{arg\,min}_{s}\\{\left\langle\nabla
f(x),s\right\rangle+\Psi(s)\\}.$ (2)

The format of problem (1) is the same as that considered in [19, 8]. The
traditional format of the conditional gradient method, as discussed in [5,
10], corresponds to the special case when $\Psi$ is the indicator function
$\Psi=\delta_{C}$ of some closed convex set $C\subseteq{\mathbb{R}}^{n}$. A
fundamental difference between the conditional gradient method and other
popular first-order methods for (1), like proximal gradient or more general
Bregman proximal gradient methods, is the reliance on the linear oracle (2) as
opposed to the reliance on a proximal mapping for the function $\Psi$. This
fundamental difference has two profound implications. First, the conditional
gradient method is preferable for a problem of the form (1) where the proximal
mapping for $\Psi$ is unavailable or prohibitively expensive but the linear
oracle (2) is available. This is the case in a large class of problems in data
science such as those discussed in [5, 7, 8, 9, 10, 26]. In addition to the
popular setting where $\Psi$ is the indicator function of a closed convex set,
the articles [7, 8, 9, 26] also discuss important data science problems where
$\Psi$ is not an indicator function but a more involved regularization term.
Second, the reliance on the linear oracle (2) as opposed to the reliance on
proximal mappings endows the conditional gradient method with the affine
invariance and norm-independence properties that play a central role in this
article.

Our main developments (Theorem 1 and Theorem 2) concern the behavior of the
gap between the primal iterates $x_{k},\;k=0,1,\dots$ generated by Algorithm 1
and the dual iterates $g_{k}:=\nabla f(x_{k}),\;k=0,1,\dots$ that Algorithm 1
also generates for the Fenchel dual of (1), namely

$\max_{u}\\{-f^{*}(u)-\Psi^{*}(-u)\\}.$ (3)

Here $f^{*}$ and $\Psi^{*}$ denote the conjugates of $f$ and $\Psi$
respectively. We will rely on the observation that for $g\in{\mathbb{R}}^{n}$,
the set $\operatorname*{arg\,min}_{y}\\{\left\langle
g,y\right\rangle+\Psi(y)\\}$ is precisely the subdifferential
$\partial\Psi^{*}(-g)$. We will also rely on the observation that the
closedness of $f$ and $\Psi$ together with Assumptions A1 and A2 imply that
${\mathrm{dom}}(\Psi)\subseteq{\mathrm{dom}}(f)$ and
${\mathrm{dom}}(f^{*})\subseteq-{\mathrm{dom}}(\Psi^{*})$.

Algorithm 1 Conditional gradient algorithm

1: input: $(f,\Psi)$, $x_{0}\in{\mathrm{dom}}(\Psi)$

2: for $k=0,1,2,\dots$ do

3: pick $s_{k}\in\operatorname*{arg\,min}_{y}\\{\left\langle\nabla
f(x_{k}),y\right\rangle+\Psi(y)\\}$ and $\theta_{k}\in[0,1]$

4: let $x_{k+1}:=(1-\theta_{k})x_{k}+\theta_{k}s_{k}$

5: end for

Starting from a current iterate $x$, Algorithm 1 updates $x$ to
$x_{+}:=x+\theta(s-x)$ where $s\in\partial\Psi^{*}(-g)$ for $g=\nabla f(x)$,
and $\theta\in[0,1]$. The choice of $g=\nabla f(x)$ and
$s\in\partial\Psi^{*}(-g)$ yields the identity

$f(x)+f^{*}(g)+\Psi(s)+\Psi^{*}(-g)=\left\langle g,x-s\right\rangle,$

which can be equivalently stated as the Wolfe gap:

$f(x)+\Psi(x)+f^{*}(g)+\Psi^{*}(-g)=\left\langle
g,x-s\right\rangle+\Psi(x)-\Psi(s)$ (4)

or as

$f(s)+\Psi(s)+f^{*}(g)+\Psi^{*}(-g)=f(s)-f(x)-\left\langle
g,s-x\right\rangle=D_{f}(s,x),$ (5)

where $D_{f}$ denotes the Bregman distance of $f$, that is, the function

$D_{f}(y,x)=f(y)-f(x)-\left\langle\nabla f(x),y-x\right\rangle.$

In the special case when $\Psi$ is the indicator function of a closed convex
set $C\subseteq{\mathbb{R}}^{n}$, the Wolfe gap (4) has the simpler and
popular expression

$f(x)+\Psi(x)+f^{*}(g)+\Psi^{*}(-g)=\left\langle g,x-s\right\rangle.$

Our main developments are stated in terms of the functions ${\mathsf{gap}}$
and ${\mathcal{D}}$ described next. Define the duality gap function
${\mathsf{gap}}:{\mathrm{dom}}(\Psi)\times{\mathrm{dom}}(f^{*})\rightarrow{\mathbb{R}}$
as follows

${\mathsf{gap}}(x,u):=f(x)+\Psi(x)+f^{*}(u)+\Psi^{*}(-u).$ (6)

Define
${\mathcal{D}}:{\mathrm{dom}}(\Psi)\times{\mathrm{dom}}(\Psi)\times[0,1]\rightarrow{\mathbb{R}}$
as follows

$\displaystyle{\mathcal{D}}(x,s,\theta):=D_{f}(x+\theta(s-x),x)+\Psi(x+\theta(s-x))-(1-\theta)\Psi(x)-\theta\Psi(s).$
(7)

The following proposition establishes a fundamental gap reduction identity
connecting ${\mathsf{gap}}$ and ${\mathcal{D}}$.

######  Proposition 1.

Suppose $x\in{\mathrm{dom}}(\Psi),g=\nabla f(x),$ and
$s\in\partial\Psi^{*}(-g)$ Then for $\theta\in[0,1]$ we have

${\mathsf{gap}}(x+\theta(s-x),g)=(1-\theta){\mathsf{gap}}(x,g)+{\mathcal{D}}(x,s,\theta).$
(8)

###### Proof.

Adding (4) times $(1-\theta)$ and (5) times $\theta$ we get

$(1-\theta)(f+\Psi)(x)+\theta(f+\Psi)(s)+f^{*}(g)+\Psi^{*}(-g)=(1-\theta){\mathsf{gap}}(x,g)+\theta
D_{f}(s,x)$

Thus

$\displaystyle{\mathsf{gap}}(x+\theta(s-x),g)$
$\displaystyle=(f+\Psi)(x+\theta(s-x))+f^{*}(g)+\Psi^{*}(-g)$
$\displaystyle=(1-\theta){\mathsf{gap}}(x,g)+\theta
D_{f}(s,x)+(f+\Psi)(x+\theta(s-x))-(1-\theta)(f+\Psi)(x)-\theta(f+\Psi)(s).$

To finish, observe that

$\displaystyle\theta
D_{f}(s,x)+(f+\Psi)(x+\theta(s-x))-(1-\theta)(f+\Psi)(x)-\theta(f+\Psi)(s)$
$\displaystyle=D_{f}(x+\theta(s-x),x)+\Psi(x+\theta(s-x))-(1-\theta)\Psi(x)-\theta\Psi(s)$
$\displaystyle={\mathcal{D}}(x,s,\theta).$

∎

Theorem 1 below shows that Algorithm 1 generates primal and dual iterates
whose duality gap converges to zero provided the growth property (10) below
holds and Algorithm 1 makes a judicious choice of stepsizes at each iteration.
For a cleaner statement, Theorem 1 assumes that Algorithm 1 chooses the
stepsize $\theta_{k}$ via the following line-search procedure

$\theta_{k}:=\operatorname*{arg\,min}_{\theta\in[0,1]}\left\\{(1-\theta){\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta)\right\\}.$
(9)

As Theorem 2 shows, the main conclusions in Theorem 1 continue to hold, albeit
with more complicated constants, for a more flexible procedure to choose the
stepsize.

The gap reduction identity (8) in Proposition 1 implies that (9) can also be
equivalently stated as

$\theta_{k}=\operatorname*{arg\,min}_{\theta\in[0,1]}(f+\Psi)(x_{k}+\theta(s_{k}-x_{k})).$

We prefer (9) because of its direct connection with the gap reduction identity
(8).

Theorem 1 hinges on the following growth property connecting the functions
${\mathcal{D}}$ and ${\mathsf{gap}}$. Suppose $q>1$ and $r\in[0,1]$. We shall
say that the pair $({\mathcal{D}},{\mathsf{gap}})$ satisfies the
$(q,r)$-growth property if there exists a finite constant $M>0$ such that for
all $x\in{\mathrm{dom}}(\Psi),\,g:=\nabla f(x),$ and
$s\in\partial\Psi^{*}(-g)$

${\mathcal{D}}(x,s,\theta)\leq\frac{M\theta^{q}}{q}\cdot{{\mathsf{gap}}}(x,g)^{r}\text{
for all }\theta\in[0,1].$ (10)

As we detail in Section 3 below, the $(q,r)$-growth property (10) can be seen
as a generalization the curvature constant defined by Jaggi [10]. The growth
property (10) also has a flavor similar to that of the relative smoothness and
relative continuity properties in the context of Bregman proximal methods as
discussed in [2, 17, 18, 22, 23, 24].

The crux of Theorem 1 is to combine the gap reduction identity (8), the growth
property (10), and the following technical lemma due to Borwein, Li, and Yao
[4, Lemma 4.1].

######  Lemma 1.

Suppose $p>0$ and $\beta_{k},\delta_{k}\geq 0$ are such that
$\beta_{k+1}\leq\beta_{k}(1-\delta_{k}\beta_{k}^{p})\text{ for }k=0,1,\dots.$
Then

$\beta_{k}\leq\left(\beta_{0}^{-p}+p\cdot\sum_{i=0}^{k-1}\delta_{i}\right)^{-\frac{1}{p}}.$

Our two central results, namely Theorem 1 and Theorem 2, concern the sequence
${\mathsf{gap}}_{k},\;k=0,1,\dots$ of best duality gaps defined as follows.
For $k=0,1,\dots$ let

${\mathsf{gap}}_{k}:=\min_{i=0,1,\dots,k}{\mathsf{gap}}(x_{k},g_{i})$ (11)

where $g_{i}=\nabla f(x_{i})$ for $i=0,1,\dots$.

######  Theorem 1.

Suppose Algorithm 1 chooses $\theta_{k}\in[0,1]$ via (9) and $q>1$ and
$r\in[0,1]$ are such that $({\mathcal{D}},{\mathsf{gap}})$ satisfy the
$(q,r)$-growth property (10) for some finite $M>0$. Then for $k=0,1,\dots$

${\mathsf{gap}}_{k+1}\leq{\mathsf{gap}}_{k}\left(1-\frac{q-1}{q}\cdot\min\left\\{1,\left(\frac{{\mathsf{gap}}_{k}^{1-r}}{M}\right)^{\frac{1}{q-1}}\right\\}\right).$
(12)

When $r=1$ we have linear convergence

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\left(1-\frac{q-1}{q}\cdot\min\left\\{1,\frac{1}{M^{\frac{1}{q-1}}}\right\\}\right)^{k}.$
(13)

When $r\in[0,1)$ we have an initial linear convergence regime

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\left(1-\frac{q-1}{q}\right)^{k},\;k=0,1,2,\dots,k_{0}$
(14)

where $k_{0}$ is the smallest $k$ such that ${\mathsf{gap}}_{k}^{1-r}\leq M$.
Then for $k\geq k_{0}$ we have a sublinear convergence regime

${\mathsf{gap}}_{k}\leq\left({\mathsf{gap}}_{k_{0}}^{\frac{r-1}{q-1}}+\frac{1-r}{q}\cdot\frac{1}{M^{\frac{1}{q-1}}}\cdot(k-k_{0})\right)^{\frac{q-1}{r-1}}.$
(15)

###### Proof.

Identity (8) in Proposition 1 implies that

${\mathsf{gap}}(x_{k+1},g_{k})=(1-\theta_{k}){\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta_{k}).$

Thus (11), the stepsize choice (9), and growth property (10) imply that

$\displaystyle{\mathsf{gap}}_{k+1}$
$\displaystyle\leq{\mathsf{gap}}_{k}-\theta_{k}\cdot{\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta_{k})$
$\displaystyle={\mathsf{gap}}_{k}+\min_{\theta\in[0,1]}\left\\{-\theta\cdot{\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},g_{k},\theta)\right\\}$
$\displaystyle\leq{\mathsf{gap}}_{k}+\min_{\theta\in[0,1]}\left\\{-\theta\cdot{\mathsf{gap}}(x_{k},g_{k})+\frac{M\theta^{q}}{q}\cdot{\mathsf{gap}}(x_{k},g_{k})^{r}\right\\}$
$\displaystyle\leq{\mathsf{gap}}_{k}\left(1-\frac{q-1}{q}\cdot\min\left\\{1,\left(\frac{{\mathsf{gap}}_{k}^{1-r}}{M}\right)^{\frac{1}{q-1}}\right\\}\right).$

The last step above follows because the minimum in the second to last step is
attained at

$\hat{\theta}=\min\left\\{1,\left(\frac{{\mathsf{gap}}(x_{k},g_{k})^{1-r}}{M}\right)^{\frac{1}{q-1}}\right\\}\geq\min\left\\{1,\left(\frac{{\mathsf{gap}}_{k}^{1-r}}{M}\right)^{\frac{1}{q-1}}\right\\}.$

Thus
$M\hat{\theta}^{q}\cdot{\mathsf{gap}}(x_{k},g_{k})^{r}\leq\hat{\theta}\cdot{\mathsf{gap}}(x_{k},g_{k})$
and consequently

$\displaystyle{\mathsf{gap}}_{k}$
$\displaystyle+\min_{\theta\in[0,1]}\left\\{-\theta\cdot{\mathsf{gap}}(x_{k},g_{k})+\frac{M\theta^{q}}{q}\cdot{\mathsf{gap}}(x_{k},g_{k})^{r}\right\\}$
$\displaystyle\leq{\mathsf{gap}}_{k}-\hat{\theta}\cdot{\mathsf{gap}}(x_{k},g_{k})+\frac{1}{q}\cdot\hat{\theta}\cdot{\mathsf{gap}}(x_{k},g_{k})$
$\displaystyle\leq{\mathsf{gap}}_{k}\left(1-\frac{q-1}{q}\cdot\hat{\theta}\right)$
$\displaystyle\leq{\mathsf{gap}}_{k}\left(1-\frac{q-1}{q}\cdot\min\left\\{1,\left(\frac{{\mathsf{gap}}_{k}^{1-r}}{M}\right)^{\frac{1}{q-1}}\right\\}\right).$

Therefore (12) is established. Inequality (12) automatically implies (13) when
$r=1$ and also (14) for $k\leq k_{0}$ when $r\in[0,1)$. When $r\in[0,1)$ and
$k\geq k_{0}$ inequality (15) follows from (12) and Lemma 1 applied to
$p:=\frac{1-r}{q-1}$ and
$\beta_{k}:={\mathsf{gap}}_{k},\delta_{k}:=\frac{q-1}{q}\cdot\frac{1}{M^{\frac{1}{q-1}}}$
for $k=k_{0},k_{0}+1,\dots$. ∎

Theorem 1 shows that for fixed $q>1$, the value of $r\in[0,1]$ in the
$(q,r)$-growth property (10) yields a convergence rate for
${\mathsf{gap}}_{k}\rightarrow 0$ somewhere in the spectrum from the sublinear
rate ${\mathcal{O}}(1/k^{q-1})$ when $r=0$ to a linear rate when $r=1$. The
convergence rate increases as $r$ increases to $1$. For fixed $r\in(0,1)$ the
converge rate also increases as the parameter $q>1$ in the $(q,r)$-growth
property (10) increases. Section 3 below elaborates on these observations and
other interesting consequences of Theorem 1.

We next describe a more flexible alternative to (9) to choose the stepsize
$\theta_{k}$. Suppose $c,\rho\in(0,1)$. A simple backtracking procedure can
easily choose $\theta_{k}\in[0,1]$ such that
$\rho\cdot\hat{\theta}_{k}\leq\theta_{k}\leq\hat{\theta}_{k}$ for

$\hat{\theta}_{k}:=\max\left\\{\theta\in[0,1]:(1-\theta){\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta)\leq(1-c\cdot\theta){\mathsf{gap}}(x_{k},g_{k})\right\\}.$
(16)

The inequality in (16) can be seen as an Armijo rule condition for the
function $\varphi:[0,1]\rightarrow{\mathbb{R}}$ defined as
$\varphi(\theta):=(1-\theta){\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta)$.
Indeed, a simple calculation shows that
$\varphi(0)={\mathsf{gap}}(x_{k},g_{k})$ and the right derivative of $\varphi$
at zero satisfies

$\varphi^{\prime}_{+}(0)\leq-{\mathsf{gap}}(x_{k},g_{k})<0.$

Therefore the inequality in (16) can be rewritten in the usual Armijo rule
format [20, Chapter 3]:

$\varphi(\theta)\leq\varphi(0)+\tilde{c}\cdot\theta\cdot\varphi^{\prime}_{+}(0).$

for some $\tilde{c}\leq c$. The Armijo rule condition (16) is evidently easier
to satisfy, and therefore more flexible, than the exact line-search (9) which
corresponds to choosing
$\theta_{k}:=\operatorname*{arg\,min}_{\theta\in[0,1]}\varphi(\theta)$.

A straightforward modification of the proof of Theorem 1 yields the following
result.

######  Theorem 2.

Suppose $c,\rho\in(0,1)$ are such that $c+\rho>1$ and Algorithm 1 chooses
$\theta_{k}\in[0,1]$ so that
$\rho\cdot\hat{\theta}_{k}\leq\theta_{k}\leq\hat{\theta}_{k}$ for
$\hat{\theta}_{k}$ as in (16). Suppose $q>1$ and $r\in[0,1]$ are such that
$({\mathcal{D}},{\mathsf{gap}})$ satisfy the $(q,r)$-growth property (10) for
some finite $M>0$. Then for $k=0,1,\dots$

${\mathsf{gap}}_{k+1}\leq{\mathsf{gap}}_{k}\left(1-(c+\rho-1)\cdot\min\left\\{1,\left(\frac{q(1-c)}{M}\cdot{\mathsf{gap}}_{k}^{1-r}\right)^{\frac{1}{q-1}}\right\\}\right).$
(17)

When $r=1$ we have linear convergence

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\left(1-(c+\rho-1)\cdot\min\left\\{1,\left(\frac{q(1-c)}{M}\right)^{\frac{1}{q-1}}\right\\}\right)^{k}.$
(18)

When $r\in[0,1)$ we have an initial linear convergence regime

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\left(1-(c+\rho-1)\right)^{k},\;k=0,1,2,\dots,k_{0}$
(19)

where $k_{0}$ is the smallest $k$ such that
${\mathsf{gap}}_{k}^{1-r}\leq\frac{M}{q(1-c)}$. Subsequently for $k\geq k_{0}$
we have a sublinear convergence regime

${\mathsf{gap}}_{k}\leq\left({\mathsf{gap}}_{k_{0}}^{\frac{r-1}{q-1}}+\frac{(1-r)(c+\rho-1)}{q-1}\cdot\left(\frac{q(1-c)}{M}\right)^{\frac{1}{q-1}}\cdot(k-k_{0})\right)^{\frac{q-1}{r-1}}.$
(20)

###### Proof.

As noted above, this is a modification of the proof of Theorem 1. Identity (8)
in Proposition 1 yields

${\mathsf{gap}}(x_{k+1},g_{k})=(1-\theta_{k}){\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta_{k}).$

Hence (11) implies that

${\mathsf{gap}}_{k+1}\leq{\mathsf{gap}}_{k}-\theta_{k}\cdot{\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta_{k}).$

Since $\rho\cdot\hat{\theta}_{k}\leq\theta_{k}\leq\hat{\theta}_{k}$ for
$\hat{\theta}_{k}$ as in (16), it follows that

$\displaystyle{\mathsf{gap}}_{k+1}$
$\displaystyle\leq{\mathsf{gap}}_{k}-\rho\cdot\hat{\theta}_{k}\cdot{\mathsf{gap}}(x_{k},g_{k})+{\mathcal{D}}(x_{k},s_{k},\theta_{k})$
$\displaystyle\leq{\mathsf{gap}}_{k}-\rho\cdot\hat{\theta}_{k}\cdot{\mathsf{gap}}(x_{k},g_{k})+(1-c)\cdot\theta_{k}\cdot{\mathsf{gap}}(x_{k},g_{k})$
$\displaystyle\leq{\mathsf{gap}}_{k}-(c+\rho-1)\cdot\hat{\theta}_{k}\cdot{\mathsf{gap}}(x_{k},g_{k})$
$\displaystyle\leq{\mathsf{gap}}_{k}(1-(c+\rho-1)\cdot\hat{\theta}_{k}).$ (21)

The growth property (10) and (11) imply that the minimizer $\hat{\theta}_{k}$
in (16) satisfies

$\displaystyle\hat{\theta}_{k}$
$\displaystyle=\max\left\\{\theta\in[0,1]:{\mathcal{D}}(x_{k},s_{k},\theta)\leq(1-c)\cdot\theta\cdot{\mathsf{gap}}(x_{k},g_{k})\right\\}$
$\displaystyle\geq\max\left\\{\theta\in[0,1]:\frac{M\theta^{q}}{q}{\mathsf{gap}}(x_{k},g_{k})^{r}\leq(1-c)\cdot\theta\cdot{\mathsf{gap}}(x_{k},g_{k})\right\\}$
$\displaystyle=\min\left\\{1,\left(\frac{q(1-c)}{M}\cdot{\mathsf{gap}}(x_{k},g_{k})^{1-r}\right)^{\frac{1}{q-1}}\right\\}$
$\displaystyle\geq\min\left\\{1,\left(\frac{q(1-c)}{M}\cdot{\mathsf{gap}}_{k}^{1-r}\right)^{\frac{1}{q-1}}\right\\}.$
(22)

Inequality (17) follows by putting together (21) and (22). Inequality (17)
automatically implies (18) when $r=1$ and also (19) for $k\leq k_{0}$ when
$r\in[0,1)$. When $r\in[0,1)$ and $k\geq k_{0}$ inequality (20) follows from
(17) and Lemma 1 applied to $p:=\frac{1-r}{q-1}$ and
$\beta_{k}:={\mathsf{gap}}_{k},\delta_{k}:=(c+\rho-1)\left(\frac{q(1-c)}{M}\right)^{\frac{1}{q-1}}$
for $k=k_{0},k_{0}+1,\dots$. ∎

We note that expression (17) in Theorem 2 is identical to expression (12) in
Theorem 1 for the ideal choice $\rho=1$ and $c=(q-1)/q$. Likewise for (18),
(20) and (13), (15).

To conclude this section, we next discuss the norm-independence and affine
invariance of our developments. The growth property (10) as well as Theorem 1
and Theorem 2 are automatically norm-independent since they do not rely on any
norms. They are also affine invariant as we next detail.

Consider an affine reparametrization of ${\mathbb{R}}^{n}$ of the form
$x:=A\tilde{x}+b$ where $A:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{n}$ is a
linear bijection. Let
$\tilde{f},\tilde{\Psi}:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$
be defined as the corresponding reparametrizations of $f$ and $\Psi$, namely

$\tilde{f}(\tilde{x}):=f(A\tilde{x}+b)\;\text{ and
}\;\tilde{\Psi}(\tilde{x}):=\Psi(A\tilde{x}+b).$

Let $A^{*}:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{n}$ denote the adjoint of
$A$. Some straightforward calculations show that if $x=A\tilde{x}+b$ then

$\nabla\tilde{f}(\tilde{x})=A^{*}\nabla f(x)\text{ and
}\tilde{f}^{*}(A^{*}u)=f^{*}(u)-\left\langle b,u\right\rangle\text{ for all
}u\in{\mathbb{R}}^{n},$

and likewise for $\Psi$ in lieu of $f$. Consequently, if $x=A\tilde{x}+b$ then

$\partial\Psi^{*}(-A^{*}\nabla
f(x))=A\partial\tilde{\Psi}^{*}(-\nabla\tilde{f}(\tilde{x}))+b.$

Hence if $x=A\tilde{x}+b$ then for $g:=\nabla f(x)$ and
$\tilde{g}:=\nabla\tilde{f}(\tilde{x})$ we have $\tilde{g}=A^{*}g$ and
$\partial\Psi^{*}(-g)=A\partial\Psi^{*}(-\tilde{g})+b$. Thus we can assume
that the oracle in Assumption A2 yield respectively $s\in\partial\Psi^{*}(-g)$
and $\tilde{s}\in\partial\tilde{\Psi}^{*}(-\tilde{g})$ that satisfy
$s=A\tilde{s}+b$. The identities
$x=A\tilde{x}+b,\;\tilde{g}=A^{*}g,\;s=A\tilde{s}+b$ in turn imply that

${\mathsf{gap}}(x,g)=\widetilde{{\mathsf{gap}}}(\tilde{x},\tilde{g})$

and

${\mathcal{D}}(x,s,\theta)=\widetilde{{\mathcal{D}}}(\tilde{x},\tilde{s},\theta)\text{
for all }\theta\in[0,1].$

It thus follows that the growth property (10), stepsize selection procedures
(9) and (16), as well as Theorem 1 and Theorem 2 are all affine invariant.

##  3 Growth property in some special cases

The subsections below detail some straightforward consequences of Theorem 1
when the growth property holds for some special values of $(q,r)$. These
special cases recover and sharpen some norm-dependent convergence results
previously derived in [12, 19, 8]. To make the latter connection more precise
and explicit, we show that the growth property (10) holds for various classes
of problems by relying on the concepts of uniform smoothness and uniform
convexity recalled next. A detailed discussion on these concepts is presented
in [11]. Both uniform smoothness and uniform convexity are stated and
formalized in terms of some norm. Thus throughout this section we assume that
${\mathbb{R}}^{n}$ is endowed with a norm $\|\cdot\|$ and let $\|\cdot\|^{*}$
denote its dual norm.

A convex function $f:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$
is uniformly smooth on $C\subseteq{\mathrm{dom}}(f)$ with respect to
$\|\cdot\|$ if there exist constants $q\in(1,2]$ and $L>0$ such that for
$x,y\in C$

$f(x+\theta(y-x))\geq(1-\theta)f(x)+\theta
f(y)-\frac{L}{q}\theta(1-\theta)\|y-x\|^{q}\text{ for all }\theta\in[0,1].$
(23)

It is customary to say that $f$ is $L$-smooth on $C$ when (23) holds with
$q=2$. It is easy to see that (23) holds for $q=\nu+1$ when $\nabla f$ is
$\nu$-Hölder continuous on $C$ with Hölder constant $L$. In particular, $f$ is
$L$-smooth on $C$ when $\nabla f$ is Lipschitz continuous on $C$ with
Lipschitz constant $L$.

As detailed in [11], when $f$ is differentiable, property (23) implies that
for all $x,y\in C$

$D_{f}(y,x)\leq\frac{L}{q}\|y-x\|^{q}.$ (24)

A function $\Psi:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$ is
uniformly convex on $C\subseteq{\mathrm{dom}}(\Psi)$ with respect to
$\|\cdot\|$ if there exist constants $p\geq 2$ and $\mu>0$ such that for all
$x,y\in C$ and $\theta\in[0,1]$

$\Psi(x+\theta(y-x))\leq(1-\theta)\Psi(x)+\theta\Psi(y)-\frac{\mu}{p}\theta(1-\theta)\|y-x\|^{p}\text{
for all }\theta\in[0,1].$ (25)

It is customary to say that $\Psi$ is strongly convex on $C$ when (25) holds
for $p=2$.

Again, as detailed in [11], property (25) implies that for all $x,y\in C$ and
$g\in\partial\Psi(y)$

$\Psi(x)\geq\Psi(y)+\left\langle g,s-y\right\rangle+\frac{\mu}{p}\|x-y\|^{p}.$

In particular, property (25) implies that if $C={\mathrm{dom}}(\Psi)$ and
$s=\operatorname*{arg\,min}_{y}\Psi(y)$ then for all
$x\in{\mathrm{dom}}(\Psi)$

$\Psi(x)-\Psi(s)\geq\frac{\mu}{p}\|x-s\|^{p}.$ (26)

A closed convex set $C\subseteq{\mathbb{R}}^{n}$ is uniformly convex if there
exist constants $p\geq 2$ and $\mu>0$ such that for all $x,y\in C,$
$\theta\in[0,1]$, and $z\in{\mathbb{R}}^{n}$ with $\|z\|\leq 1$

$x+\theta(y-x)+\frac{\mu}{p}\theta(1-\theta)\|y-x\|^{p}z\in C.$ (27)

It is customary to say that $C$ is strongly convex when (27) holds for $p=2.$

Similar to the above implications (23) $\Rightarrow$ (24) and (25)
$\Rightarrow$ (26), property (27) implies that if $g\in{\mathbb{R}}^{n}$ and
$s=\operatorname*{arg\,min}_{y\in C}\left\langle g,y\right\rangle$ then for
all $x\in C$

$\left\langle g,x-s\right\rangle\geq\frac{\mu}{p}\|g\|^{*}\cdot\|x-s\|^{p}.$
(28)

###  3.1 The case $q>1,\;r=0$: sublinear convergence

Suppose the growth property (10) holds for $q>1$ and $r=0,$ that is, for
$x\in{\mathrm{dom}}(\Psi),s\in\partial\Psi^{*}(-\nabla f(x))$

${\mathcal{D}}(x,s,\theta)\leq\frac{M\theta^{q}}{q}\text{ for all
}\theta\in[0,1].$ (29)

In this case ${\mathsf{gap}}_{1}\leq M/q\leq M$ and thus Theorem 1 implies
that

$\displaystyle{\mathsf{gap}}_{k}$
$\displaystyle\leq\left({\mathsf{gap}}_{1}^{-\frac{1}{q-1}}+\frac{1}{q}\cdot\frac{k-1}{M^{\frac{1}{q-1}}}\right)^{-(q-1)}$
$\displaystyle\leq\left(\frac{q^{\frac{1}{q-1}}}{M^{\frac{1}{q-1}}}+\frac{1}{q}\cdot\frac{k-1}{M^{\frac{1}{q-1}}}\right)^{-(q-1)}$
$\displaystyle=M\left(\frac{q}{k-1+q^{\frac{q}{q-1}}}\right)^{q-1}.$ (30)

The case $(q,r)=(2,0)$ is particularly interesting. In this case we get

${\mathsf{gap}}_{k}\leq\frac{2M}{k+3}.$ (31)

This bound applies in the especially important and popular case when $\Psi$ is
the indicator function $\delta_{C}$ of some compact convex set
$C\subseteq{\mathbb{R}}^{n}$ as discussed in [10, 5]. In this case for
$x\in{\mathrm{dom}}(\Psi),s\in\partial\Psi^{*}(-\nabla f(x))$ we have

${\mathcal{D}}(x,s,\theta)=D_{f}(x+\theta(s-x),x)\text{ for all
}\theta\in[0,1]$

and thus (29) holds with $q=2$ and $M$ equal to the following curvature
constant defined by Jaggi [10], provided that it is finite:

$\mathcal{C}_{f}:=\sup_{x,s\in
C\atop\theta\in(0,1]}\frac{2D_{f}(x+\theta(s-x),x)}{\theta^{2}}.$ (32)

Therefore (31) recovers the iconic convergence rate of the conditional
gradient method established in [10]. However, Theorem 1 reveals that the
convergence could be faster as (29) may hold for $M\leq\mathcal{C}_{f}$.

The following proposition describes an important class of problems that
satisfies (29). We rely on the following norm-dependent concept. Suppose
$\|\cdot\|$ is a norm in ${\mathbb{R}}^{n}$ and $C\subseteq{\mathbb{R}}^{n}$
is nonempty and bounded. The diameter of $C$ is

$\mathsf{diam}(C):=\sup_{x,y\in C}\|x-y\|.$

######  Proposition 2.

The $(q,0)$-growth property (29) holds if $f$ is $q$-uniformly smooth and
${\mathrm{dom}}(\Psi)$ is bounded. More precisely, the $(q,0)$-growth property
(29) holds for $M=L\cdot\mathsf{diam}({\mathrm{dom}}(\Psi))^{q}$ if there is a
norm $\|\cdot\|$ in ${\mathbb{R}}^{n}$ such that (23) holds for
$x,y\in{\mathrm{dom}}(\Psi)$.

###### Proof.

Suppose (23) holds for some constants $q>1$ and $L>0$. Then (7) and (24) imply
that for all $x,s\in{\mathrm{dom}}(\Psi)$ and $\theta\in[0,1]$

${\mathcal{D}}(x,s,\theta)\leq
D_{f}(x+\theta(s-x),x)\leq\frac{L}{q}\|\theta(s-x)\|^{q}=\frac{L\|s-x\|^{q}}{q}\cdot\theta^{q}.$

Thus (29) holds for $M=L\cdot\mathsf{diam}({\mathrm{dom}}(\Psi))^{q}$. ∎

Proposition 2 and (3.1) readily yield the following norm-dependent convergence
result for a class of problems previously considered in [8, 19]. Suppose
${\mathrm{dom}}(\Psi)$ is bounded and $\nabla f$ is $\nu$-Hölder continuous on
${\mathrm{dom}}(\Psi)$ for some $\nu>0$. In this case $f$ is
$(\nu+1)$-uniformly smooth on ${\mathrm{dom}}(\Psi)$. Thus Proposition 2
implies that the $(q,0)$-growth property (29) holds for $q=\nu+1$ and
$M=L\cdot\mathsf{diam}({\mathrm{dom}}(\Psi))^{1+\nu}$ where $L$ is the Hölder
continuity constant of $\nabla f$. Therefore (3.1) implies that

$\displaystyle{\mathsf{gap}}_{k}$ $\displaystyle\leq
L\cdot\mathsf{diam}({\mathrm{dom}}(\Psi))^{1+\nu}\left(\frac{\nu+1}{k-1+(\nu+1)^{\frac{\nu+1}{\nu}}}\right)^{\nu}$
$\displaystyle\leq
L\cdot\mathsf{diam}({\mathrm{dom}}(\Psi))^{1+\nu}\left(\frac{\nu+1}{k}\right)^{\nu}.$
(33)

Therefore we recover the ${\mathcal{O}}(1/k^{\nu})$ convergence results shown
in [19, Corollary 1] and in [8, Corollary 1] if we ignore some log factor in
[8, Corollary 1 and Equation (2.30)]. The constant in front of $1/k^{\nu}$ in
(3.1) is simpler and sharper than the constants in [19, Corollary 1] and in
[8, Equation (2.30)]. Furthermore, Theorem 1 reveals that the convergence is
generally faster as (29) and (3.1) will typically hold for $M\leq
L\cdot\mathsf{diam}({\mathrm{dom}}(\Psi))^{1+\nu}$.

###  3.2 The case $(q,r)=(2,1)$: linear convergence

Suppose the growth property (10) holds for $(q,r)=(2,1),$ that is, for
$x\in{\mathrm{dom}}(\Psi),s\in\partial\Psi^{*}(-\nabla f(x))$

${\mathcal{D}}(x,s,\theta)\leq\frac{M\theta^{2}}{2}\cdot{{\mathsf{gap}}}(x,g)\text{
for all }\theta\in[0,1].$ (34)

In this case Theorem 1 readily implies that

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\cdot\left(1-\frac{1}{2}\cdot\min\left\\{1,\frac{1}{M}\right\\}\right)^{k}.$
(35)

Proposition 3 below describes some important classes of problems that
satisfies (34). We omit the proof of Proposition 3 as it is a special case of
the more general Proposition 4 in Section 3.3 below.

######  Proposition 3.

Suppose $f$ is $2$-uniformly smooth on ${\mathrm{dom}}(\Psi)$. Then the
$(2,1)$-growth property (34) holds if $\Psi$ is $2$-uniformly convex on
${\mathrm{dom}}(\Psi)$, or if $\Psi=\delta_{C}$ for a $2$-uniformly convex and
closed set $C\subseteq{\mathbb{R}}^{n}$ and $\nabla f$ is bounded away from
zero in $C$. More precisely:

  * (a)

The $(2,1)$-growth property (34) holds for $M=2L/\mu$ if there is a norm
$\|\cdot\|$ in ${\mathbb{R}}^{n}$ such that both (23) and (25) hold for
$p=q=2$ and $x,y\in{\mathrm{dom}}(\Psi)$.

  * (b)

The $(2,1)$-growth property (34) holds for $M=2L/(\ell\mu)$ if
$\Psi=\delta_{C}$ for a closed convex set $C\subseteq{\mathbb{R}}^{n}$, there
is a norm $\|\cdot\|$ in ${\mathbb{R}}^{n}$ such that both (23) and (27) hold
for $p=q=2$ and $x,y\in C$, and

$\ell:=\inf_{x\in C}\|\nabla f(x)\|^{*}>0.$

Proposition 3 and (35) readily yield the following norm-dependent linear
convergence results for two classes of problems previously considered in [8,
14].

First, if $\nabla f$ is Lipschitz continuous on ${\mathrm{dom}}(\Psi)$ and
$\Psi$ is strongly convex then Proposition 3(a) implies that the
$(2,1)$-growth property (34) holds with $M=L/\mu$ where $L$ and $\mu$ are
respectively the Lipschitz continuity constant of $\nabla f$ and the strong
convexity constant of $\Psi$. Therefore (35) implies that

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\cdot\left(1-\frac{1}{2}\cdot\min\left\\{1,\frac{\mu}{2L}\right\\}\right)^{k}.$

Hence we recover the linear convergence result shown in [8, Corollary 1 and
Equation (2.32)] but with a simpler and sharper expression. Furthermore, the
convergence is generally faster as (34) and (35) will typically hold for
$M\leq 2L/\mu$.

Second, if $\Psi=\delta_{C}$, $\nabla f$ is Lipschitz continuous and bounded
away from zero on $C$, and $C\subseteq{\mathbb{R}}^{n}$ is a closed and
strongly set then Proposition 3(b) implies that the $(2,1)$-growth property
(34) holds with $M=2L/(\ell\mu)$ where $L,\mu,$ and $\ell$ are respectively
the Lipschitz continuity constant of $\nabla f$, the strong convexity constant
of $C$ and the lower bound on $\|\nabla f(x)\|^{*}$ on $C$. Therefore (35)
implies that

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\cdot\left(1-\frac{1}{2}\cdot\min\left\\{1,\frac{\ell\mu}{2L}\right\\}\right)^{k}.$

Hence we recover the linear convergence result shown in [14, Theorem 2.2] with
a slightly improved convergence rate. Theorem 1 shows that the convergence
rate is generally better as (34) and (35) typically hold for $M\leq
2L/(\ell\mu)$.

###  3.3 Other values $(q,r)$: sublinear to linear convergence

Suppose the growth property (10) holds for some $q>1,\;r\in(0,1),$ and $M>0$.
We next discuss the spectrum of convergence rates from sublinear to linear
that Theorem 1 yields depending on the values of $(q,r)$. To simplify notation
and exposition, we shall assume that ${\mathsf{gap}}_{0}\leq M$ throughout
this subsection so that we skip the initial linear convergence regime (14) in
Theorem 1. This assumption can be relaxed either at the expense of some
notational overhead to deal with the initial linear convergence regime (14),
or at the expense of artificially increasing the constant $M$.

Suppose ${\mathsf{gap}}_{0}\leq M$. Then for $r\in[0,1)$ Theorem 1 implies
that

${\mathsf{gap}}_{k}\leq\left(\frac{1}{M^{\frac{1-r}{q-1}}}+\frac{1-r}{q}\cdot\frac{k}{M^{\frac{1}{q-1}}}\right)^{\frac{q-1}{r-1}}=M\left(1+\frac{q-1}{q\cdot
M^{\frac{r}{q-1}}}\cdot k\cdot\frac{1-r}{q-1}\right)^{-\frac{q-1}{1-r}}.$ (36)

For $q>1$ fixed, the right-most expression in (36) decreases monotonically
with $r$ from the sublinear rate $M\left(\frac{q}{k+q}\right)^{q-1}$ for $r=0$
to the following asymptotic linear rate for $r\uparrow 1$

$Me^{-\rho k}=M\left(e^{-\rho}\right)^{k},$ (37)

where

$\rho:=\frac{q-1}{q\cdot M^{\frac{1}{q-1}}}\in(0,1).$

Since $e^{-\rho}\approx 1-\rho$ for small $\rho>0$, it follows that the
asymptotic linear rate (37) is approximately the same linear rate given by
Theorem 1 when $r=1$, namely

${\mathsf{gap}}_{k}\leq{\mathsf{gap}}_{0}\left(1-\frac{q-1}{q\cdot
M^{\frac{1}{q-1}}}\right)^{k}.$

The following general version of Proposition 3 describes a broad class of
problems that satisfies the $(q,r)$-growth property for various values of
$(q,r)$ depending on the degree of uniform smoothness and uniform convexity of
$f$ and $\Psi$.

######  Proposition 4.

Suppose $f$ is $q$-uniformly smooth on ${\mathrm{dom}}(\Psi)$. Then the
$(q,r)$-growth property (10) holds for $r=q/p$ if $\Psi$ is $p$-uniformly
convex on ${\mathrm{dom}}(\Psi)$, or if $\Psi=\delta_{C}$ for a $p$-uniformly
convex and closed set $C\subseteq{\mathbb{R}}^{n}$ and $\nabla f$ is bounded
away from zero in $C$. More precisely:

  * (a)

The $(q,r)$-growth property (10) holds for $r=q/p$ and
$M=L\cdot\left(p/\mu\right)^{\frac{q}{p}}$ if there is a norm $\|\cdot\|$ in
${\mathbb{R}}^{n}$ such that both (23) and (25) hold for
$x,y\in{\mathrm{dom}}(\Psi)$.

  * (b)

The $(q,r)$-growth property (10) holds for $r=q/p$ and
$M=L\cdot\left(p/(\ell\mu)\right)^{\frac{q}{p}}$ if $\Psi=\delta_{C}$ for a
closed convex set $C\subseteq{\mathbb{R}}^{n}$, and there is a norm
$\|\cdot\|$ in ${\mathbb{R}}^{n}$ such that both (23) and (27) hold for
$x,y\in C$, and

$\ell:=\inf_{x\in C}\|\nabla f(x)\|^{*}>0.$

###### Proof.

  * (a)

Suppose (23) holds for some constants $q>1$ and $L>0$, and also (25) holds for
some constants $p>1$ and $\mu>0$. Then for all $x\in{\mathrm{dom}}(\Psi)$ and
$g:=\nabla f(x)$ the tilted function $\Psi_{g}:=\Psi+\left\langle
g,\cdot\right\rangle$ is also $p$-uniformly convex on
${\mathrm{dom}}(\Psi_{g})={\mathrm{dom}}(\Psi)$ for the same $p$ and $\mu$.
Consequently (26) implies that
$s:=\operatorname*{arg\,min}_{y}\\{\Psi(y)+\left\langle
g,y\right\rangle\\}=\operatorname*{arg\,min}_{y}\Psi_{g}(y)$ satisfies

${\mathsf{gap}}(x,g)=\Psi(x)+\left\langle
g,x\right\rangle-\Psi(s)-\left\langle
g,s\right\rangle=\Psi_{g}(x)-\Psi_{g}(s)\geq\frac{\mu}{p}\|x-s\|^{p}.$

On the other hand, (7) and (24) imply that

${\mathcal{D}}(x,s,\theta)\leq
D_{f}(x+\theta(s-x),x)\leq\frac{L\theta^{q}}{q}\|s-x\|^{q}.$

It thus follows that (10) holds for $q$ and $r=q/p$ with
$M=L\cdot\left({p}/{\mu}\right)^{\frac{q}{p}}$.

  * (b)

Suppose (23) holds for some constants $q>1$ and $L>0$, (27) holds for some
constants $p\geq 2$ and $\mu>0$, and $\ell:=\inf_{x\in C}\|\nabla
f(x)\|^{*}>0.$ Then (28) implies that for $x\in{\mathrm{dom}}(\Psi),g:=\nabla
f(x)$ and $s=\operatorname*{arg\,min}_{x\in C}\left\langle g,x\right\rangle$
we have

${\mathsf{gap}}(x,g)=\left\langle
g,x-s\right\rangle\geq\frac{\mu}{p}\|g\|^{*}\cdot\|x-s\|^{p}\geq\frac{\ell\mu}{p}\cdot\|x-s\|^{p}.$
(38)

Thus proceeding as in part (a), (24) implies that (10) holds for $q$ and
$r=q/p$ with $M=L\cdot\left({p}/{(\ell\mu)}\right)^{\frac{q}{p}}$

∎

Proposition 4 and Theorem 1 yield the following norm-dependent convergence
results for two classes of problems that extend the two classes discussed in
Section 3.2.

First, suppose $\nabla f$ is $\nu$-Hölder continuous on ${\mathrm{dom}}(\Psi)$
for some $\nu\in(0,1]$ and $\Psi$ is $p$-uniformly convex on
${\mathrm{dom}}(\Psi)$ for some $p\geq 2$. Then Proposition 4 implies that the
$(q,r)$-growth property (10) holds for $q=\nu+1$ and $r=(\nu+1)/p$ with
$M=L\cdot\left(p/\mu\right)^{\frac{q}{p}}$. The case $r=1$, that is, $\nu=1$
and $p=2$ was already discussed in Section 3.2. Hence we focus on the case
$r<1,$ that is, $p>\nu+1$. Under the mild assumption that
${\mathsf{gap}}_{0}\leq M$, inequality (36) implies that

$\displaystyle{\mathsf{gap}}_{k}$
$\displaystyle\leq\left(\frac{1}{M^{\frac{p-\nu-1}{p\nu}}}+\frac{p-\nu-1}{p(\nu+1)}\cdot\frac{k}{M^{\frac{1}{\nu}}}\right)^{\frac{p\nu}{\nu+1-p}}\leq\left(\frac{p(\nu+1)\cdot
M^{\frac{1}{\nu}}}{p-\nu-1}\cdot\frac{1}{k}\right)^{\frac{p\nu}{p-\nu-1}}.$
(39)

The above ${\mathcal{O}}(1/k^{\frac{p\nu}{p-\nu-1}})$ convergence rate is new
for $p>2$ and extends some of the results considered in [8, 19] that only
consider the cases when $p=2$ or when ${\mathrm{dom}}(\Psi)$ is bounded.

Second, if $\Psi=\delta_{C}$, $\nabla f$ is $\nu$-Hölder continuous and
bounded away from zero on $C$, and $C\subseteq{\mathbb{R}}^{n}$ is a closed
and $p$-uniformly set then Proposition 4(b) implies that the $(q,r)$-growth
property (34) holds for $q=\nu+1,r=q/p$ with
$M=L\cdot\left({p}/{(\ell\mu)}\right)^{\frac{q}{p}}$ where $L,\mu,$ and $\ell$
are respectively the Lipschitz continuity constant of $\nabla f$, the strong
convexity constant of $C$ and the lower bound on $\|\nabla f(x)\|^{*}$ on $C$.
Again the case $r=1$, that is, $\nu=1$ and $p=2$ was already discussed in
Section 3.2 and thus we focus on the case $r<1.$ Under the mild assumption
that ${\mathsf{gap}}_{0}\leq M$, inequality (36) again implies (39) albeit for
a different constant $M$. Hence we extend the sublinear convergence result
shown in [12, Theorem 2.2] that considers only the special case $\nu=1$ and
$p>2$. For these values of $\nu$ and $p$ we get

${\mathsf{gap}}_{k}\leq\left(\frac{2Mp}{p-2}\cdot\frac{1}{k}\right)^{\frac{p}{p-2}}$

and thus recover the ${\mathcal{O}}(1/k^{\frac{p}{p-2}})$ sublinear
convergence result in [12, Theorem 2.2] albeit with a slightly simpler and
sharper constant.

##  4 Weak growth property and suboptimality gap

Consider the setting of Section 2. Define the suboptimality gap function
${\mathsf{subopt}}:{\mathrm{dom}}(\Psi)\rightarrow{\mathbb{R}}$ as follows

${\mathsf{subopt}}(x):=f(x)+\Psi(x)-\min_{y}\left\\{f(y)+\Psi(y)\right\\}.$

The weak duality property between (1) and its dual (3) implies that for all
$(x,u)\in{\mathrm{dom}}(\Psi)\times{\mathrm{dom}}(f^{*})$

${\mathsf{gap}}(x,u)\geq{\mathsf{subopt}}(x).$

Therefore any upper bound on the duality gap automatically holds for the
suboptimality gap as well. This section takes this observation further:
Theorem 3 and Theorem 4 provide analogous statements to Theorem 1 and Theorem
2 for the suboptimality gap by relying on the following relaxed version of
(10). Suppose $q>1$ and $r\in[0,1]$. We shall say that the triple
$({\mathcal{D}},{\mathsf{gap}},{\mathsf{subopt}})$ satisfies the $(q,r)$ weak
growth property if there exists a finite constant $M>0$ such that for all
$x\in{\mathrm{dom}}(\Psi),\,g:=\nabla f(x),$ and $s\in\partial\Psi^{*}(-g)$

${\mathcal{D}}(x,s,\theta)\cdot{\mathsf{subopt}}(x)^{1-r}\leq\frac{M\theta^{q}}{q}\cdot{{\mathsf{gap}}}(x,g)\text{
for all }\theta\in[0,1].$ (40)

Since ${\mathsf{gap}}(x,g)\geq{\mathsf{subopt}}(x)\geq 0$, it is immediate
that the weak growth property (40) holds whenever the growth property (10)
holds.

The next two results concern the sequence of suboptimality gaps

${\mathsf{subopt}}_{k}:={\mathsf{subopt}}(x_{k}),\;k=0,1,\dots$

for the iterates generated by Algorithm 1. We omit the proofs of Theorem 3 and
Theorem 4 below as they are word by word extensions of the proofs of Theorem 1
and Theorem 2.

######  Theorem 3.

Suppose Algorithm 1 chooses $\theta_{k}\in[0,1]$ via (9) and $q>1$ and
$r\in[0,1]$ are such that $({\mathcal{D}},{\mathsf{gap}},{\mathsf{subopt}})$
satisfy the $(q,r)$ weak growth property (40) for some finite $M>0$. Then for
$k=0,1,\dots$

${\mathsf{subopt}}_{k+1}\leq{\mathsf{subopt}}_{k}\left(1-\frac{q-1}{q}\cdot\min\left\\{1,\left(\frac{{\mathsf{subopt}}_{k}^{1-r}}{M}\right)^{\frac{1}{q-1}}\right\\}\right).$

When $r=1$ we have linear convergence

${\mathsf{subopt}}_{k}\leq{\mathsf{subopt}}_{0}\left(1-\frac{q-1}{q}\cdot\min\left\\{1,\frac{1}{M^{\frac{1}{q-1}}}\right\\}\right)^{k}.$

When $r\in[0,1)$ we have an initial linear convergence regime

${\mathsf{subopt}}_{k}\leq{\mathsf{subopt}}_{0}\left(1-\frac{q-1}{q}\right)^{k},\;k=0,1,2,\dots,k_{0}$

where $k_{0}$ is the smallest $k$ such that ${\mathsf{subopt}}_{k}^{1-r}\leq
M$. Then for $k\geq k_{0}$ we have a sublinear convergence regime

${\mathsf{subopt}}_{k}\leq\left({\mathsf{subopt}}_{k_{0}}^{\frac{r-1}{q-1}}+\frac{1-r}{q}\cdot\frac{1}{M^{\frac{1}{q-1}}}\cdot(k-k_{0})\right)^{\frac{q-1}{r-1}}.$

######  Theorem 4.

Suppose $c,\rho\in(0,1)$ are such that $c+\rho>1$ and Algorithm 1 chooses
$\theta_{k}\in[0,1]$ so that
$\rho\cdot\hat{\theta}_{k}\leq\theta_{k}\leq\hat{\theta}_{k}$ for
$\hat{\theta}_{k}$ as in (16). Suppose $q>1$ and $r\in[0,1]$ are such that
$({\mathcal{D}},{\mathsf{gap}},{\mathsf{subopt}})$ satisfy the $(q,r)$ weak
growth property (40) for some finite $M>0$. Then for $k=0,1,\dots$

${\mathsf{subopt}}_{k+1}\leq{\mathsf{subopt}}_{k}\left(1-(c+\rho-1)\cdot\min\left\\{1,\left(\frac{q(1-c)}{M}\cdot{\mathsf{subopt}}_{k}^{1-r}\right)^{\frac{1}{q-1}}\right\\}\right).$

When $r=1$ we have linear convergence

${\mathsf{subopt}}_{k}\leq{\mathsf{subopt}}_{0}\left(1-(c+\rho-1)\cdot\min\left\\{1,\left(\frac{q(1-c)}{M}\right)^{\frac{1}{q-1}}\right\\}\right)^{k}.$

When $r\in[0,1)$ we have an initial linear convergence regime

${\mathsf{subopt}}_{k}\leq{\mathsf{subopt}}_{0}\left(1-(c+\rho-1)\right)^{k},\;k=0,1,2,\dots,k_{0}$

where $k_{0}$ is the smallest $k$ such that
${\mathsf{subopt}}_{k}^{1-r}\leq\frac{M}{q(1-c)}$. Subsequently for $k\geq
k_{0}$ we have a sublinear convergence regime

${\mathsf{subopt}}_{k}\leq\left({\mathsf{subopt}}_{k_{0}}^{\frac{r-1}{q-1}}+\frac{(1-r)(c+\rho-1)}{q-1}\cdot\left(\frac{q(1-c)}{M}\right)^{\frac{1}{q-1}}\cdot(k-k_{0})\right)^{\frac{q-1}{r-1}}.$

Proposition 5 below provides a nice complement to Proposition 4(b).
Proposition 5 describes a class of problems that satisfies the weak growth
property similar to that in Proposition 4(b). However, instead of assuming
that $\nabla f$ is bounded away from zero in $C$, Proposition 5 relies on the
following type of Hölderian error bound as in [12, 25]. Suppose
$C\subseteq{\mathbb{R}}^{n}$ is a closed convex set, $f^{\star}:=\min_{x\in
C}f(x)$ is finite, $X^{\star}:=\\{x\in C:f(x)=f^{\star}\\}$ is nonempty.
Suppose ${\mathbb{R}}^{n}$ is endowed with a norm $\|\cdot\|$ and
$\gamma\in[0,1]$. We shall say that $f$ satisfies the $\gamma$-Hölderian error
bound on $C$ if there exists a finite constant $K>0$ such that for all $x\in
C$

$\min_{y\in X^{\star}}\|x-y\|\leq K\cdot(f(x)-f^{\star})^{\gamma}.$ (41)

The Hölderian error bound (41) is known to hold generically when $C$ is a
compact set and $f$ is subanalytic, as established by Łojasiewicz [16], and
further developed by Kurdyka [15] and Bolte et al. [3].

######  Proposition 5.

The $(q,r)$ weak growth property (40) holds for $r=\gamma q/p$ if
$\Psi=\delta_{C}$ for some closed and $p$-uniformly convex set
$C\subseteq{\mathbb{R}}^{n}$, $f$ is $q$-uniformly smooth on $C$, and the
$\gamma$-Hölderian error bound (41) holds for $\gamma\in[0,1]$.

###### Proof.

Suppose (23) holds for some constants $q\in(1,2]$ and $L>0$, (27) holds for
some constants $p\geq 2$ and $\mu>0$, and (41) holds for some constants
$\gamma\in[0,1]$ and $K>0$. Then (28) implies that for all $x\in C$ and
$g:=\nabla f(x)$ we have

${\mathsf{gap}}(x,g)=\left\langle
g,x-s\right\rangle\geq\frac{\mu}{p}\|g\|^{*}\cdot\|x-s\|^{p}.$ (42)

Next, the convexity of $f$, Cauchy-Schwarz inequality, and (41) imply that for
$x^{\star}:=\operatorname*{arg\,min}_{y\in X^{\star}}\|x-y\|$

${\mathsf{subopt}}(x)=f(x)-f(x^{\star})\leq\left\langle
g,x-x^{\star}\right\rangle\leq\|g\|^{*}\cdot\|x-x^{\star}\|\leq
K\cdot\|g\|^{*}\cdot{\mathsf{subopt}}(x)^{\gamma}.$ (43)

From (42) and (43) it follows that

$\|x-s\|^{p}\cdot{\mathsf{subopt}}(x)^{1-\gamma}\leq\frac{pK}{\mu}\cdot{\mathsf{gap}}(x,g).$

The latter inequality, (24), and ${\mathsf{subopt}}(x)\leq{\mathsf{gap}}(x,g)$
imply that

$\displaystyle{\mathcal{D}}(x,s,\theta)\cdot{\mathsf{subopt}}(x)^{1-\frac{\gamma
q}{p}}$
$\displaystyle={\mathcal{D}}_{f}(x+\theta(s-x),x)\cdot{\mathsf{subopt}}(x)^{1-\frac{\gamma
q}{p}}$
$\displaystyle\leq\frac{L}{q}\cdot\theta^{q}\cdot\|s-x\|^{q}\cdot{\mathsf{subopt}}(x)^{\frac{(1-\gamma)q}{p}}\cdot{\mathsf{gap}}(x,g)^{1-\frac{q}{p}}$
$\displaystyle=\frac{L}{q}\cdot\theta^{q}\cdot\left(\|s-x\|^{p}\cdot{\mathsf{subopt}}(x)^{1-\gamma}\right)^{\frac{q}{p}}\cdot{\mathsf{gap}}(x,g)^{1-\frac{q}{p}}$
$\displaystyle\leq
L\cdot\left(\frac{pK}{\mu}\right)^{\frac{q}{p}}\cdot\frac{\theta^{q}}{q}\cdot{\mathsf{gap}}(x,g).$

Therefore (40) holds for $r=\gamma q/p$ and
$M=L\cdot\left(pK/\mu\right)^{q/p}.$ ∎

Proposition 5 and Theorem 3 yield the following norm-dependent convergence
results for a class of problems previously considered in [14, 25].

Suppose $\Psi=\delta_{C}$ for $C\subseteq{\mathbb{R}}^{n}$ closed and
$p$-uniformly convex, $\nabla f$ is $\nu$-Hölder continuous on $C$, and $f$
satisfies the $\gamma$-Hölderian error bound on $C$. Then Proposition 5
implies that the $(q,r)$ weak growth property holds for $q=\nu+1,r=\gamma q/p$
with $M=L\cdot\left(pK/\mu\right)^{q/p}$ where $L,\mu,$ and $K$ are
respectively the Hölder continuity constant of $\nabla f$, the $p$-convexity
constant of $C$, and the $\gamma$-Hölderian error bound constant of $f$ on
$C$.

When $\nu=1,\;p=2,$ and $\gamma=1$ we have $q=2,\;r=1,$ and
$M=\frac{2LK}{\mu}$. Thus Theorem 3 yields the linear convergence rate

${\mathsf{subopt}}_{k}\leq{\mathsf{subopt}}_{0}\left(1-\frac{1}{2}\cdot\min\left\\{1,\frac{\mu}{2LK}\right\\}\right)^{k}.$

We thus recover the linear convergence result in [25, Theorem 1] with a
sharper rate. For all other values of $\nu,p,\gamma$ we have $r=\gamma q/p<1$.
To simplify notation and exposition for this case, assume that
${\mathsf{subopt}}_{0}\leq M$. Thus Theorem 3 yields the sublinear rate

$\displaystyle{\mathsf{subopt}}_{k}$
$\displaystyle\leq\left(\frac{1}{M^{\frac{1-r}{q-1}}}+\frac{1-r}{q}\cdot\frac{k}{M^{\frac{1}{q-1}}}\right)^{\frac{q-1}{r-1}}\leq\left(\frac{(\nu+1)\cdot
M^{\frac{1}{\nu}}}{1-\gamma(\nu+1)/p}\cdot\frac{1}{k}\right)^{\frac{\nu}{1-\gamma(\nu+1)/p}}.$

Hence we extend the sublinear convergence results in [25, Theorem 1] and in
[12, Theorem 2.9]. Both [25] and [12] consider only the special case $\nu=1$.
In this special case we get $r=2\gamma/p$ and thus

${\mathsf{subopt}}_{k}\leq\left(\frac{2M}{1-2\gamma/p}\cdot\frac{1}{k}\right)^{\frac{1}{1-2\gamma/p}}$

In particular, we recover the
${\mathcal{O}}\left(1/k^{\frac{1}{1-\gamma}}\right)$ sublinear convergence
rate in [25, Theorem 1] which only considers the case $p=2$. We also recover
the ${\mathcal{O}}\left(1/k^{\frac{1}{1-2\gamma/p}}\right)$ sublinear
convergence result in [12, Theorem 2.9] which only considers the case
$\gamma\in[0,1/2]$. Like both [12] and [25], we also recover the
${\mathcal{O}}\left(1/k^{2}\right)$ sublinear convergence result in [6,
Theorem 2] which only considers the case $p=2$ and $\gamma=1/2$. In all cases
we get slightly simpler and sharper constants.

##  5 Local growth property

We next describe an extension of the main developments in Section 2 to a local
setting. The same extension applies to the developments in Section 4.

Consider the setting of Section 2. Suppose $q>1$ and $r\in[0,1]$. We shall say
that the pair $({\mathcal{D}},{\mathsf{gap}})$ satisfies the $(q,r)$ local
growth property if there exist constants $\epsilon>0$ and $M>0$ such that for
all $x\in{\mathrm{dom}}(\Psi),\,g:=\nabla f(x),$ and $s:=\partial\Psi^{*}(-g)$
that satisfy ${\mathsf{gap}}(x,g)<\epsilon$ we have

${\mathcal{D}}(x,s,\theta)\leq\frac{M\theta^{q}}{q}\cdot{{\mathsf{gap}}}(x,g)^{r}\text{
for all }\theta\in[0,1].$ (44)

It is straightforward to see that local versions of Theorem 1 and Theorem 2
also hold if we replace the growth property (10) with the local growth
property (44) provided
${\mathsf{gap}}_{0}={\mathsf{gap}}(x_{0},g_{0})<\delta$. It is also evident
that the local growth property (44) is less stringent than the growth property
(10). In particular, the natural local version of Proposition 4 holds if the
uniform smoothness and uniform convexity assumptions hold on a neighborhood of
an optimal solution to (1). The following proposition, which is a
straightforward extension of some arguments in [12], describes another class
of problems that satisfy the local growth condition (44). Proposition 6
provides a counterpart to Proposition 4(b) that relaxes the assumption of
$p$-uniform convexity of $C$ and boundedness away from zero of $\nabla f$ on
$C$ to the far less stringent local scaling inequality (45). This relaxed
assumption comes at the expense of downgrading the growth condition for
$r=q/p$ to the local growth condition for $r=q(q-1)/(p(p-1))$. As noted in
[12, Remark 2.6], in the special case when $q=p=2$ there is no downgrade in
the value of $r$. For all other values of $q\in(1,2]$ and $p\geq 2$ the
downgrade factor $(q-1)/(p-1)$ on $r$ is the price we pay for relaxing the
uniform convexity and boundedness assumptions to the less stringent local
scaling assumption.

######  Proposition 6.

Suppose $\Psi=\delta_{C}$ for a closed convex set
$C\subseteq{\mathbb{R}}^{n}$, $x^{\star}\in C$ is a minimizer of (1),
$\nu\in(0,1]$, and $p\geq 2$. Then the local growth property (44) holds for
$q=1+\nu$ and $r=q(q-1)/(p(p-1))$ if $\nabla f$ is $\nu$-Hölder continuous on
$C$ and there exists $\sigma>0$ such that the following local scaling
inequality holds for all $x\in C$

$\left\langle\nabla
f(x^{\star}),x-x^{\star}\right\rangle\geq\sigma\cdot\|x-x^{\star}\|^{p}.$ (45)

###### Proof.

From (45) and the convexity of $f$ it follows that for $x\in C$ and $g=\nabla
f(x)$

${\mathsf{gap}}(x,g)\geq f(x)-f(x^{\star})\geq\left\langle\nabla
f(x^{\star}),x^{\star}-x\right\rangle\geq\sigma\cdot\|x-x^{\star}\|^{p}.$ (46)

In addition, for $s=\operatorname*{arg\,min}_{y\in C}\left\langle
g,y\right\rangle=\operatorname*{arg\,min}_{y\in C}\left\langle\nabla
f(x),y\right\rangle$ the local scaling inequality (45) implies that

$\left\langle\nabla f(x^{\star})-\nabla
f(x),s-x^{\star}\right\rangle\geq\left\langle\nabla
f(x^{\star}),s-x^{\star}\right\rangle\geq\sigma\cdot\|s-x^{\star}\|^{p}.$ (47)

Thus the $\nu$-Hölder continuity of $\nabla f$ and Hölder’s inequality imply
that for some finite Hölder continuity constant $L>0$

$L\|x^{\star}-x\|^{\nu}\cdot\|s-x^{\star}\|\geq\sigma\cdot\|s-x^{\star}\|^{p}.$

Hence $\sigma\cdot\|s-x^{\star}\|^{p-1}\leq L\|x^{\star}-x\|^{\nu}$ and thus
(46) yields

${\mathsf{gap}}(x,g)\geq\sigma\cdot\|x-x^{\star}\|^{p}\geq\sigma\cdot\left(\frac{\sigma}{L}\right)^{\frac{p}{\nu}}\|s-x^{\star}\|^{\frac{p(p-1)}{\nu}}$
(48)

From (46) and (48) it follows that for ${\mathsf{gap}}(x,g)\leq 1$:

$\displaystyle\|s-x\|$ $\displaystyle\leq\|x^{\star}-x\|+\|s-x^{\star}\|$
$\displaystyle\leq\frac{1}{\sigma^{\frac{1}{p}}}\cdot{\mathsf{gap}}(x,g)^{\frac{1}{p}}+\frac{1}{\sigma^{\frac{\nu}{p(p-1)}}}\cdot\left(\frac{L}{\sigma}\right)^{\frac{1}{p-1}}\cdot{\mathsf{gap}}(x,g)^{\frac{\nu}{p(p-1)}}$
$\displaystyle\leq\left(\frac{1}{\sigma^{\frac{1}{p}}}+\frac{1}{\sigma^{\frac{\nu}{p(p-1)}}}\cdot\left(\frac{L}{\sigma}\right)^{\frac{1}{p-1}}\right)\cdot{\mathsf{gap}}(x,g)^{\frac{\nu}{p(p-1)}}.$

Therefore (24) implies that for ${\mathsf{gap}}(x,g)\leq 1$

$\displaystyle{\mathcal{D}}(x,s,\theta)$
$\displaystyle={\mathcal{D}}_{f}(x+\theta(s-x),x)$
$\displaystyle\leq\frac{L\theta^{1+\nu}}{1+\nu}\cdot\|s-x\|^{1+\nu}$
$\displaystyle\leq
L\cdot\left(\frac{1}{\sigma^{\frac{1}{p}}}+\frac{1}{\sigma^{\frac{\nu}{p(p-1)}}}\cdot\left(\frac{L}{\sigma}\right)^{\frac{1}{p-1}}\right)^{1+\nu}\cdot\frac{\theta^{1+\nu}}{1+\nu}\cdot{\mathsf{gap}}(x,g)^{\frac{\nu(1+\nu)}{p(p-1)}}.$

Therefore whenever ${\mathsf{gap}}(x,g)<1$ the local growth property (44)
holds for $q=1+\nu$ and $r=q(q-1)/(p(p-1))$ with

$M=L\cdot\left(\frac{1}{\sigma^{\frac{1}{p}}}+\frac{1}{\sigma^{\frac{\nu}{p(p-1)}}}\cdot\left(\frac{L}{\sigma}\right)^{\frac{1}{p-1}}\right)^{1+\nu}.$

∎

## References

  * [1] F. Bach.  Duality between subgradient and conditional gradient methods.  SIAM Journal on Optimization, 25(1):115–129, 2015.
  * [2] H. Bauschke, J. Bolte, and M. Teboulle.  A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications.  Mathematics of Operations Research, 42(2):330–348, 2016.
  * [3] J. Bolte, A. Daniilidis, and A. Lewis.  The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.  SIAM Journal on Optimization, 17(4):1205–1223, 2007.
  * [4] J. Borwein, G. Li, and L. Yao.  Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets.  SIAM Journal on Optimization, 24(1):498–527, 2014.
  * [5] R. Freund and P. Grigas.  New analysis and results for the Frank–Wolfe method.  Mathematical Programming, 155(1-2):199–230, 2016.
  * [6] D. Garber and E. Hazan.  Faster rates for the Frank-Wolfe method over strongly-convex sets.  In International Conference on Machine Learning, pages 541–549. PMLR, 2015.
  * [7] D. Garber, A. Kaplan, and S. Sabach.  Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems.  Mathematical Programming, 186(1):185–208, 2021.
  * [8] S. Ghadimi.  Conditional gradient type methods for composite nonlinear and stochastic optimization.  Mathematical Programming, 173(1):431–464, 2019.
  * [9] Z. Harchaoui, A. Juditsky, and A. Nemirovski.  Conditional gradient algorithms for norm-regularized smooth convex optimization.  Mathematical Programming, 152(1):75–112, 2015.
  * [10] M. Jaggi.  Revisiting Frank-Wolfe: Projection-free sparse convex optimization.  In ICML, volume 28 of JMLR Proceedings, pages 427–435, 2013\.
  * [11] T. Kerdreux, A. d’Aspremont, and S. Pokutta.  Local and global uniform convexity conditions.  arXiv preprint arXiv:2102.05134, 2021.
  * [12] T. Kerdreux, A. d’Aspremont, and S. Pokutta.  Projection-free optimization on uniformly convex sets.  In International Conference on Artificial Intelligence and Statistics, pages 19–27. PMLR, 2021.
  * [13] T. Kerdreux, A. d’Aspremont, and S. Pokutta.  Restarting Frank–Wolfe: Faster rates under Hölderian error bounds.  Journal of Optimization Theory and Applications, 192(3):799–829, 2022.
  * [14] T. Kerdreux, L. Liu, S. Lacoste-Julien, and D. Scieur.  Affine invariant analysis of Frank-Wolfe on strongly convex sets.  In International Conference on Machine Learning, pages 5398–5408. PMLR, 2021.
  * [15] K. Kurdyka.  On gradients of functions definable in o-minimal structures.  In Annales de l’institut Fourier, volume 48, pages 769–783, 1998\.
  * [16] S. Łojasiewicz.  Ensembles semi-analytiques.  Lectures Notes IHES (Bures-sur-Yvette), 1965.
  * [17] H. Lu.  “Relative continuity” for non-Lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent.  INFORMS Journal on Optimization, 1(4):288–303, 2019.
  * [18] H. Lu, R. Freund, and Y. Nesterov.  Relatively smooth convex optimization by first-order methods, and applications.  SIAM Journal on Optimization, 28(1):333–354, 2018.
  * [19] Y. Nesterov.  Complexity bounds for primal-dual methods minimizing the model of objective function.  Mathematical Programming, 171(1):311–330, 2018.
  * [20] J. Nocedal and S. Wright.  Numerical Optimization, Second Edition.  Springer, 2006.
  * [21] F. Rinaldi and D. Zeffiro.  A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition.  arXiv preprint arXiv:2008.09781, 2020.
  * [22] M. Teboulle.  A simplified view of first order methods for optimization.  Mathematical Programming, pages 1–30, 2018.
  * [23] Q. Van Nguyen.  Variable quasi-Bregman monotone sequences.  Numerical Algorithms, 73(4):1107–1130, 2016.
  * [24] Q. Van Nguyen.  Forward-backward splitting with Bregman distances.  Vietnam Journal of Mathematics, 45(3):519–539, 2017.
  * [25] Y. Xu and T. Yang.  Frank-Wolfe method is automatically adaptive to error bound condition.  arXiv preprint arXiv:1810.04765, 2018.
  * [26] Y. Yu, X. Zhang, and D. Schuurmans.  Generalized conditional gradient for sparse estimation.  Journal of Machine Learning Research, 18:1–46, 2017.