# Optimal first-order methods for convex functions
with a quadratic upper bound

Baptiste Goujaud
CMAP, École Polytechnique,
Institut Polytechnique de Paris
<EMAIL_ADDRESS>&Adrien Taylor
INRIA, École Normale Supérieure,
CNRS, PSL Research University, Paris
<EMAIL_ADDRESS>&Aymeric Dieuleveut
CMAP, École Polytechnique,
Institut Polytechnique de Paris
<EMAIL_ADDRESS>
###### Abstract

We analyze worst-case convergence guarantees of first-order optimization
methods over a function class extending that of smooth and convex functions.
This class contains convex functions that admit a simple quadratic upper
bound. Its study is motivated by its stability under minor perturbations. We
provide a thorough analysis of first-order methods, including worst-case
convergence guarantees for several methods, and demonstrate that some of them
achieve the optimal worst-case guarantee over the class. We support our
analysis by numerical validation of worst-case guarantees using performance
estimation problems. A few observations can be drawn from this analysis,
particularly regarding the optimality (resp. and adaptivity) of the heavy-ball
method (resp. heavy-ball with line-search). Finally, we show how our analysis
can be leveraged to obtain convergence guarantees over more complex classes of
functions. Overall, this study brings insights on the choice of function
classes over which standard first-order methods have working worst-case
guarantees.

##  1 Introduction

In this paper, we consider the problem of minimizing a convex (closed proper)
function

$f_{\star}\triangleq\min_{x\in\mathbb{R}^{d}}f(x),$ (1)

where $f:\mathbb{R}^{d}\to\mathbb{R}$ is assumed to have a non-empty set of
global minimizers denoted by $\mathcal{X}_{\star}$ (which is necessarily
convex). Convergence properties of first-order optimization are typically
analyzed through worst-case analyses under the _black-box_ model [39]. In this
formalism, nontrivial guarantees are obtained by assuming the function to be
minimized to satisfy certain regularity conditions. In particular, it is
common to assume Lipschitz continuity of the gradients of $f$ (also often
referred to as smoothness of $f$) as well as (strong) convexity of $f$. First-
order methods and their analyses for minimizing such functions in the black-
box model occupied a great deal of attention, see, e.g., [39, 45, 41].

Due to the practical success of first-order methods in large-scale
applications, and particularly when aiming for only low to medium accuracy
solutions (Bottou and Bousquet [7] motivate this goal for machine learning), a
few trends emerged in the first-order optimization literature. Among them, a
particular focus concerned the question of understanding minimal working
assumptions under which one could design efficient first-order methods. In
other words, many authors looked for weaker/alternate versions to the standard
smoothness and strong convexity-type assumptions, still allowing to obtain
suitable working guarantees for standard first-order methods.

Relaxations of strong convexity-type assumptions. Convexity alone is not
sufficient to a priori guarantee “fast” convergence of usual first-order
methods. On the other hand, strong convexity allows to obtain faster
(geometric) rates but is a very strong condition. Therefore, many authors
studied conditions in between convexity and strong convexity, aiming to obtain
faster rates under relatively generic assumptions. In particular, different
authors considered the restricted secant inequality [55, 22], the error bound
[35], Łojasiewicz-type inequalities [44], and many more [25, 29, 33, 19, 36,
24, 1]. Relations between these assumptions were treated at length in [5, 54].
Among those, one of the weakest relaxation is the so-called (lower) quadratic
growth, see [6, 26, 3]. Recently, those notions turned out to be useful, e.g.
for studying proximal gradient methods, see [10, 16, 15, 43, 53, 9]. In the
rest of the paper, we focus on (non strongly) convex functions.

Relaxations of smoothness-type assumptions. Generalization of smoothness
assumptions were less investigated in the literature. Still, a few such
relaxations have emerged, including the relative smoothness, see [4, 34, 11,
23], restricted smoothness [2] and restricted Lipschitz-continuous gradient
[55]. In this work, we consider instead the set of convex functions satisfying
the (upper) quadratic growth condition, as follows.

###### Definition 1.1

A function $f$ is $L$-quadratically upper bounded (denoted
$L$-$\operatorname{QG}^{+}$) if for all $x\in\mathbb{R}^{d}$:

$f(x)-f_{\star}\leq\frac{L}{2}d(x,\mathcal{X}_{\star})^{2},$

where
$d(x,\mathcal{X}_{\star})=\min_{x_{\star}\in\mathcal{X}_{\star}}\|x-x_{\star}\|_{2}$.
We denote the set of such functions by $\operatorname{QG}^{+}(L)$, and by
$\operatorname{QG}^{+}$ when $L$ is left unspecified.

This assumption is weaker than smoothness. First, any $L$-smooth function
(i.e. with $L$-Lipschitz gradient) also belongs to $\operatorname{QG}^{+}(L)$.
On the other hand,

  1. 1.

some functions do belong to $\operatorname{QG}^{+}$ while not being smooth for
any value of $L$. In particular $\operatorname{QG}^{+}$ contains all Lipschitz
non-smooth convex functions which are twice differentiable at all their
optimal points. Let us mention a few rules for obtaining (not necessarily
smooth) $\operatorname{QG}^{+}$ functions: (i) any function that can be
written as $x\mapsto h(x^{\top}Mx)$, where $h$ is convex Lipschitz continuous
and $M$ is a positive semidefinite matrix, or (ii) $x\mapsto h(N(x))$, where
$h$ is convex and smooth (or $\operatorname{QG}^{+}$) and $N$ is a norm (e.g.
$N=\|\cdot\|_{2}$, $N=\|\cdot\|_{1}$ or $N=\|\cdot\|_{\infty}$).

  2. 2.

Some functions belong to $\operatorname{QG}^{+}(L_{Q})$ while being smooth
only for some $L_{S}\gg L_{Q}$ (see e.g., Eq.(3) and Proposition 4.6 in [21].)
Consequently, even though the worst case convergence rate over the class of
$\operatorname{QG}^{+}(L)$ functions cannot improve on the rate for $L$-smooth
functions, it is possible for a given smooth function that the guarantee
provided by the rate on the $\operatorname{QG}^{+}$ class is actually better
than the one resulting from the rate as a smooth function.

More generally, the later example is related to _condition continuity_ ,
introduced by Guille-Escuret et al. [21, Definition 4.9]. Condition continuity
is a property of function classes, defined by the fact that a minor
modification of the gradient of the function, at any point away from the
optimum, cannot strongly affect the class parameter $L$. This is a desirable
property for first-order methods for which the output typically continuously
depends on the gradients of the functions minimized: if the function is
slightly perturbed away from the optimum, the tuning and convergence
guarantees of the algorithm should not be affected. The
$\operatorname{QG}^{+}$ class satisfies condition continuity, while the class
of smooth convex functions does not: a minor perturbation of an $L$-smooth
function (thus $L$-$\operatorname{QG}^{+}$) can be
$L_{Q}$-$\operatorname{QG}^{+}$ and $L_{S}$-smooth, with $L_{S}\gg L_{Q}$.
This also motivates studying $\operatorname{QG}^{+}$.

Contributions and organization of the paper. The rest of the paper is
organized in two main sections. First, in Section 2, we analyze a few first-
order methods, namely the subgradient method and the heavy-ball method with
and without a line-search. We provide worst-case complexity bounds on the
convergence rates as well as corresponding lower complexity bounds. We also
provide a lower complexity bound for minimizing convex functions in
$\operatorname{QG}^{+}$ via first-order methods. Finally, we provide
interpolation/extensions results for this class of problems, which allows
exploring/deriving all previous results in a principled way (using performance
estimation problems [14, 51]). We summarize those results in Table 1, together
with precise references to the corresponding statements. Secondly, we review
the main consequences of our analysis in Section 3. More specifically, we
underline the facts that (a) the heavy-ball Algorithm 2 and 3 are optimal on
this class of functions, furthermore, (b) Algorithm 3 is adaptive: it achieves
the optimal convergence rate for both Lipschitz-continuous functions and
$\operatorname{QG}^{+}$ functions without requiring knowledge of any class
parameter. Then, we describe how our theory can be exploited for automatically
obtaining convergence rates for different classes of functions. Lastly (in
Appendix G), we discuss results that can be obtained when restricting the
class to functions satisfying additional assumptions (a relaxation of strong-
convexity).

Table 1:  Summary of the worst-case guarantees obtaining after $n$ iterations
of a few different first-order methods on the class of convex
$L$-$\operatorname{QG}^{+}$ functions, which are obtained in Section 2 and
Appendix A. Two main methods are studied, namely the (sub)gradient and the
heavy-ball methods. Some guarantees concern the worst-case function value
accuracy at the last iterate. The term “average” in the third column refers to
the function value on the Polyak-Rupert averaged iterate. All the provided
bounds are proportional to $R^{2}=d(x_{0},\mathcal{X}_{\star})^{2}$, where
$x_{0}$ denotes the starting point of the methods.

Method | Step-sizes $(\gamma_{t})_{0\leq t\leq n-1}$ | Iterate | Upper bound | Lower bound
---|---|---|---|---
Subgradient (Sec. 2.1) | $\frac{1}{L}$ | (Alg. 1) | Average | $\frac{L}{2}\frac{R^{2}}{n+1}$ | (Th. 2.1) | $\frac{L}{2}\frac{R^{2}}{n+1}$ | (Rem. A.1)
$\gamma_{t}$ | (Alg. 1) | Last | $\times$ |  | $\frac{LR^{2}}{2}L\gamma_{n-1}$ | (Th. 2.2)
$\sim\frac{1}{2L\sqrt{t}}$ | (Alg. 6) | Last | $\sim\frac{LR^{2}}{4\sqrt{n}}$ | (Conj. A.3) | $\sim\frac{LR^{2}}{4\sqrt{n}}$ | (Th. 2.2)
Heavy-ball (Sec. 2.3) | $\frac{1}{L}\frac{1}{t+2}$ | (Alg. 2) | Last | $\frac{L}{2}\frac{R^{2}}{n+1}$ | (Th. 3.3) | $\frac{L}{2}\frac{R^{2}}{n+1}$ |
line-search | (Alg. 3) | Last | $\frac{L}{2}\frac{R^{2}}{n+1}$ | (Th. 3.3) | $\frac{L}{2}\frac{R^{2}}{n+1}$ |
First-order (Sec. 2.2) | Any |  | Any | - |  | $\frac{L}{2}\frac{R^{2}}{n+1}$ | (Th. 2.3)

Notation and background results. For problem (1), the set
$\mathcal{X}_{\star}$ of minimizers of $f$ is closed and convex ($f$ is proper
closed and convex by assumption). Therefore, there exists a unique projection
$\pi_{\mathcal{X_{\star}}}$ onto $\mathcal{X}_{\star}$, verifying:
$\|x-\pi_{\mathcal{X_{\star}}}(x)\|_{2}=d(x,\mathcal{X}_{\star}).$ We use the
classical $\partial f$ for denoting the subdifferential of the function $f$.
Namely, the subdifferential of $f$ at $x\in\mathbb{R}^{d}$ is the set of all
subgradients of $f$ at $x$: $\partial f(x)=\\{g|\forall
y\in\mathbb{R}^{d},f(y)\geq f(x)+\left<g|y-x\right>\\}.$ Note that
$0\in\partial f(x)\Leftrightarrow x\in\mathcal{X}_{\star}$; moreover, if
$f\in\operatorname{QG}^{+}$, then for all $x\in\mathcal{X}_{\star}$, $\partial
f(x)=\\{0\\}$.

##  2 A few worst-case guarantees for minimizing $\operatorname{QG}^{+}$
convex functions

In this section, we provide the main technical results of this paper,
summarized in Table 1. In Section 2.1, we study the behavior of a
_(sub)gradient_ method on convex $\operatorname{QG}^{+}$ functions. A lower
complexity bound on the convergence of any first-order method is provided in
Section 2.2. In Section 2.3, we introduce the heavy-ball method under
consideration and prove its worst-case optimality. Finally, we discuss how
interpolation conditions were used for obtaining these results in Section 2.4.

###  2.1 (Sub)gradient method on $\operatorname{QG}^{+}$ convex functions

Algorithm 1 Subgradient method

Input: $x_{0}$, $(\gamma_{t})_{0\leq t\leq n}$

for  _$k=1\ldots n$_ do

Query $g_{k-1}\in\partial f(x_{k-1})$; $x_{k}\leftarrow
x_{k-1}-\gamma_{k-1}g_{k-1}$

Output: $(x_{t})_{0\leq t\leq n}$

In this subsection, we consider Algorithm 1: the subgradient method, for $n$
iterations and a sequence of step-sizes $(\gamma_{t})_{0\leq t\leq n-1}$. The
following result provides a convergence guarantee for the averaged function
value accuracy throughout the iterative procedure.

###### Theorem 2.1

_(Convergence of Algorithm 1 in average)_ Let $f$ be an
$L$-$\operatorname{QG}^{+}$ convex function. Applying (sub)gradient method on
$f$ with step-size $\gamma\triangleq\frac{1}{L}$ leads to the following
guarantee:

$\frac{1}{n+1}\sum_{k=0}^{n}(f(x_{k})-f_{\star})\leq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}.$
(2)

Sketch of proof. The proof consists in proving that at each step
$f(x_{k})-f_{\star}\leq\frac{L}{2}d(x_{k},\mathcal{X}_{\star})^{2}-\frac{L}{2}d(x_{k+1},\mathcal{X}_{\star})^{2}$
and recognizing a telescopic sum on the right hand side. See Appendix A.
$\hfill\blacksquare$

By convexity of $f$, this result automatically implies a convergence guarantee
for the Polyak-Ruppert (PR) averaging [46, 48],
$\bar{x}_{n}=\frac{1}{n+1}\sum_{k=0}^{n}x_{k}$ with the same convergence rate.
For $L$-smooth convex functions, the same worst-case convergence rate is
achieved by both the PR averaging and the last iterate. It is therefore
natural to wonder if the subgradient method verifies the same convergence
guarantee for the _last iterate_ , on $\operatorname{QG}^{+}$ convex
functions. For $L$-smooth convex functions, Drori and Teboulle [14, Theorem
3.2] provide the following lower bound on the convergence of Algorithm 1: for
any $\gamma_{k}=\gamma\in\left[0,2/L\right]$, there exists a $L$-smooth convex
function and a starting point $x_{0}$ s.t.

$f(x_{n})-f_{\star}\geq\max\left(\frac{L}{2}\frac{1}{1+2nL\gamma},\frac{L}{2}\left(1-L\gamma\right)^{2n}\right)d(x_{0},\mathcal{X}_{\star})^{2}.$
(3)

Drori and Teboulle [14, Theorem 3.1] also provide a corresponding worst-case
guarantee of the form
$f(x_{n})-f_{\star}\leq\frac{L}{2}\frac{1}{1+2nL\gamma}d(x_{0},\mathcal{X}_{\star})^{2}$
for when $\gamma\in(0,\tfrac{1}{L})$, which ensures convergence in function
value accuracy with a constant step-size rule
$\gamma_{k}=\gamma\in(0,\tfrac{1}{L})$ at a rate $O(1/n)$.

Here we provide a stricter lower bound for the convergence of the function
value for the last iterate: contrary to what happens for smooth convex
functions, subgradient methods with constant step-sizes cannot be guaranteed
to converge on $\operatorname{QG}^{+}$ convex functions.

###### Theorem 2.2

_(Lower bound for Algorithm 1 \- final iterate)._ For any sequence
$(\gamma_{i})_{0\leq i\leq n-1}>0$ and any $\varepsilon>0$, there exists an
$L$-$\operatorname{QG}^{+}$ convex function $f$ that verifies, after $n$
iterations of Algorithm 1 with step-sizes $(\gamma_{i})_{0\leq i\leq n-1}$,

$f(x_{n})-f_{\star}\geq\frac{L}{2}L\gamma_{n-1}d(x_{0},\mathcal{X}_{\star})^{2}-\varepsilon.$
(4)

Sketch of proof. The proof consists in finding a function defined on
$\mathbb{R}^{3}$ such that all the iterates except the last one are very close
to each other. As $\operatorname{QG}^{+}$ convex functions might not be
differentiable, subgradients might vary very quickly. Therefore, the last
iterate might be far away from the others, although all the previous iterates
are clustered. A complete proof is provided in Appendix A.
$\hfill\blacksquare$

As a result, it is necessary to enforce $\gamma_{n}\rightarrow 0$ for ensuring
convergence of Algorithm 1 on all problem instances. On the other hand, a
similar lower bound to (3) (using the same Huber function as that used for the
class of smooth convex functions, see [14], or [51, Section 4]) and modifying
$x_{0}$ to account for varying step-sizes (we use
$x_{0}=1+2\sum_{k=0}^{n-1}L\gamma_{k}$), one can obtain:

$f(x_{n})-f_{\star}\geq\frac{L}{2}\frac{1}{1+2\sum_{k=0}^{n-1}L\gamma_{k}}d(x_{0},\mathcal{X}_{\star})^{2}.$
(5)

Consequently the worst-case convergence is slower than $O(1/n)$ as soon as
$\gamma_{k}\rightarrow 0$. Overall, the convergence is provably worse for the
last iterate over the $\operatorname{QG}^{+}(L)$-class than over the class of
$L$-smooth convex functions, even though guarantees match for the PR-averaged
iterate. Actually, the lower bound is at least the maximum of the RHSs of
Equations 4 and 5. In Appendix A, we introduce and analyze Algorithm 6, that
corresponds to Algorithm 1 with a specific sequence of step-sizes such that
Equations 4 and 5 are equal. This results in a decaying sequence of step-sizes
scaling as $O(1/\sqrt{n})$. The next section is devoted to a lower complexity
bound on the convergence in function accuracy for any black-box first-order
method.

###  2.2 First-order lower bound

The next theorem guarantees that no black-box first-order method can beat a
$O(1/n)$ worst-case guarantee in function values uniformly on the set of
$\operatorname{QG}^{+}$ convex functions.

###### Theorem 2.3

_(Lower complexity bound)_ Let $n\in\mathbb{N}$. There exists some
$d\in\mathbb{N}$ and some convex $L$-$\operatorname{QG}^{+}$ function $f$ of
input space $\mathbb{R}^{d}$ such that: for any sequence $(x_{k})_{0\leq k\leq
n}$ satisfying
$x_{k}-x_{0}\in\text{span}\left\\{g_{0},g_{1},g_{2},\dots,g_{k-1}\right\\}$
for all $k\leq n$ with $g_{i}\in\partial f(x_{i})$ ($i=0,\ldots,k-1$), we
have:

$f(x_{n})-f_{\star}\geq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}.$

Sketch of proof. The proof consists in noticing that the function
$x\mapsto\frac{L}{2}\|x\|_{\infty}^{2}$ allows to explore one new dimension
per step and that this new dimension is independent of the way the next point
in the sequence is chosen. Therefore, choosing $d=n+1$ allows to ensure that
there exists one unseen dimension after $n$ iterations. This methodology is
common to prove lower bounds in first-order optimization, see, e.g., [37, 41,
8]. We refer to Appendix B.1 for the complete proof. The above result is also
generalized in Appendix B.2 to account for any sequence generated by a black-
box first-order (possibly without the span assumption as in, e.g., [37,
Chapter 12] for quadratic minimization). $\hfill\blacksquare$

One can conclude from 2.3 that no black-box first-order method can enjoy a
worst-case guarantee better than
$f(x_{n})-f_{\star}\leq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}$
uniformly on all $d\in\mathbb{N}$, all $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$
that is convex and $L$-$\operatorname{QG}^{+}$ and all
$x_{0}\in\mathbb{R}^{d}$. This entails that Algorithm 1, with constant step-
size $1/L$ and PR averaging, is worst-case optimal for decreasing function
values on the class of $\operatorname{QG}^{+}$ and convex functions. In the
next section, we introduce two alternate methods that also achieve this
optimal bound, this time without PR averaging. As we see in the sequel, those
further developments allow achieving this optimal bound without explicitly
using the knowledge of the constant $L$.

###  2.3 Two methods with optimal last iterate guarantee

Algorithm 2 Heavy-ball method for $\operatorname{QG}^{+}$ convex

Input: $x_{0}$, $L$

for  _$k=1\ldots n$_ do

Pick  $g_{k-1}$ from $\partial f(x_{k-1})$
$x_{k}\leftarrow\frac{k}{k+1}x_{k-1}+\frac{1}{k+1}x_{0}-\frac{1}{k+1}\sum_{i=0}^{k-1}\frac{1}{L}g_{i}$

Output: $x_{n}$

In this section, we introduce Algorithm 2 and Algorithm 3 which both achieve
the optimal convergence guarantee for the last iterate (see 2.3). The first of
those two methods explicitly relies on the knowledge of the class parameter
$L$ for performing its updates, whereas the second variant allows avoiding
using any knowledge on $L$. Note that the update rule from Algorithm 2 can
equivalently be expressed as:

$x_{k}\leftarrow
x_{k-1}-\frac{1}{L}\frac{1}{k+1}g_{k-1}+\frac{k-1}{k+1}\left(x_{k-1}-x_{k-2}\right)$
(6)

Algorithm 3 Heavy-ball method with line-search for $\operatorname{QG}^{+}$
convex

Input: $x_{0}$, $v_{0}\leftarrow 0$

for  _$k=1\ldots n$_ do

$y_{k}\leftarrow\frac{k}{k+1}x_{k-1}+\frac{1}{k+1}x_{0}$ Pick
$g_{k-1}\in\partial f(x_{k-1})$ such that $\left<g_{k-1},v_{k-1}\right>=0$.
$v_{k}\leftarrow v_{k-1}+g_{k-1}$
$\alpha_{k}\leftarrow\arg\min_{\alpha}f\left(y_{k}+\alpha v_{k}\right)$
$x_{k}\leftarrow y_{k}+\alpha_{k}v_{k}$

Output: $x_{n}$

where $g_{k-1}\in\partial f(x_{k-1})$. This formulation corresponds to the
heavy-ball method, as defined in [18, Theorem 2] and for which authors
provided a $O(1/n)$ guarantee for $L$-smooth convex functions.

Algorithm 3 takes a similar form, but relies on an exact line-search
procedure, avoiding to use any knowledge on $L$. Both methods share the same
worst-case guarantee, matching the lower bound result from 2.3. The following
theorem provides a necessary condition for an algorithm to share this same
worst-case guarantee.

###### Theorem 2.4

_(Main result: sufficient condition for being worst-case optimal)._ Let
$\mathcal{A}$ be an iterative first-order method that verifies, for all convex
$\operatorname{QG}^{+}(L)$ function $f$, and starting points $x_{0}$,

$\Big{\langle}g_{k},x_{k}-\Big{[}\frac{k}{k+1}x_{k-1}+\frac{1}{k+1}x_{0}-\frac{1}{k+1}\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\Big{]}\Big{\rangle}\leq
0.$ (7)

for some sequence $(g_{i})_{i\in\mathbb{N}}$ of subgradients $g_{i}\in\partial
f(x_{i})$, and where $(x_{i})_{i\in\mathbb{N}}$ are the iterates of
$\mathcal{A}$. Then, the output $x_{n}$ of $\mathcal{A}$ achieves the worst-
case guarantee:

$f(x_{n})-f_{\star}\leq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}.$

Sketch of proof. The proof is based on a Lyapunov analysis; for $k\geq 0$, we
define the sequence
$k(f(x_{k-1})-f_{\star})+\frac{L}{2}\|x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\|^{2}$
and show it is a decreasing. See Appendix C for a complete and detailed proof.
$\hfill\blacksquare$

Inequality (7) is clearly satisfied for Algorithm 2 by ensuring the right hand
side of the inner product being identically $0$. For Algorithm 3, the right
hand side of the inner product in (7) is colinear to the search direction
$\sum_{i=0}^{k-1}g_{i}$. First-order optimality conditions of the exact line-
search procedure enforces the inner product in (7) to be identically $0$. The
next corollary follows.

###### Corollary 2.5

Let $n\in\mathbb{N}$, $d\in\mathbb{N}$, $f$ be a convex
$\operatorname{QG}^{+}$ function, and $x_{0}\in\mathbb{R}^{d}$. Also let
$x_{n}$ be the output of either Algorithm 2 or Algorithm 3, we have:
$f(x_{n})-f_{\star}\leq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}.$

In the next section, we discuss how such worst-case analyses were obtained in
a principled way, through so-called performance estimation problems (PEPs). An
important ingredient to use this methodology is to develop _interpolation_
(a.k.a.  _extension_) results for the convex $\operatorname{QG}^{+}$ class.

###  2.4 Extension/interpolation results for $\operatorname{QG}^{+}$ convex
functions

The problem of interpolating/extending within a class of functions can be
stated as follows. Given a set of triplet $(x_{i},g_{i},f_{i})_{i\in
I}\subset\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}$ for some
$d\in\mathbb{N}$ and some index set $I$, the question of interest is that of
recovering a function $f$ in a prescribed class of convex functions
$\mathcal{F}$ satisfying

$f_{i}=f(x_{i})\text{ and }g_{i}\in\partial f(x_{i})\text{ for all }i\in I.$

A similar problem, often referred to as convex integration, consists in
finding such functions by only specifying some subgradients but no function
values; see [47]; for the case where $\mathcal{F}$ is the class of (closed and
proper) convex functions, this problem was also treated at length in [30].
Motivated by applications to performance estimation problems (see below), this
problem was studied in [51] for the cases where $\mathcal{F}$ is the class of
closed proper (possibly strongly) convex (possibly smooth) functions. In this
case, it is possible to obtain simple necessary and sufficient conditions for
the set $(x_{i},g_{i},f_{i})_{i\in I}$ to be interpolable; we refer to those
conditions as _interpolation conditions_. Such conditions take the form of a
set of inequalities on $(x_{i},g_{i},f_{i})_{i\in I}$, and sometimes allow to
conveniently deal with discrete versions of functions within a certain class
$\mathcal{F}$ (for which we have interpolation conditions at our disposal).
There exists a few classes of functions, typical for the analysis of first-
order methods, for which such conditions exist, see, e.g., [49, Theorem
3.3–3.6, Theorem 3.10]. The next theorem provides interpolation conditions for
the class of convex $\operatorname{QG}^{+}$ functions.

###### Theorem 2.6

_(Interpolation conditions)_ Let $(x_{i},g_{i},f_{i})_{i\in I}$ a family of
elements in $\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}$. Set
$I_{\star}$ the (assumed) non-empty subset of $I$ of the indices of elements
$(x_{i},g_{i},f_{i})$ verifying $g_{i}=0$.

Then, there exists a $\operatorname{QG}^{+}(L)$ and convex function $f$
interpolating those points (i.e. such that $\forall i\in
I,f(x_{i})=f_{i}\text{ and }g_{i}\in\partial f(x_{i})$) if and only if

$\displaystyle\forall i\in I,\forall j\in I,$ $\displaystyle f_{i}\geq
f_{j}+\left<g_{j},x_{i}-x_{j}\right>$ (8) $\displaystyle\forall i\in
I_{\star},\forall j\in I,$ $\displaystyle f_{i}\geq
f_{j}+\left<g_{j},x_{i}-x_{j}\right>+\frac{1}{2L}\|g_{j}\|^{2}.$ (9)

Sketch of proof. The proof is derived in two steps. First we notice that (8)
corresponds to the convexity of the function, and we prove (9) combining the
$2$ inequalities respectively corresponding to convexity and
$L$-$\operatorname{QG}^{+}$ assumptions. Reciprocally, we explicitly build a
$L$-$\operatorname{QG}^{+}$ convex function from (8) and (9). See Appendix E
for a detailed proof. $\hfill\blacksquare$

Application to Performance estimation problems (PEPs). PEPs were introduced by
Drori and Teboulle [14] for developing new analyses of first-order methods;
see also [12, 28] for the first works on this topic. PEPs were later
formalized using the concept of _convex interpolation_ by [51, 49]. PEPs
formulate the search for worst-case guarantees as infinite dimensional
optimization problems over the considered class of functions, e.g.,

$\text{Worst
case}\left(\text{Alg.}~{}\ref{alg:subgrad},n=1,\gamma=\tfrac{1}{L},\text{
convex
}\operatorname{QG}^{+}(L)\right)\triangleq\max_{\footnotesize\shortstack{$f\in\operatorname{QG}^{+}(L)$
\text{ convex } \\\ $x_{1}\in x_{0}-\frac{1}{L}\partial
f(x_{0})$}}\frac{f(x_{1})-f_{\star}}{d(x_{0},\mathcal{X}_{\star})^{2}},$

for the case of 1-step subgradient descent. In order to numerically solve
those problems, it is needed to transform them into a finite dimensional
problem. To that end, interpolation conditions play a crucial role, by
allowing to reduce the optimization over the (infinite dimensional) class of
functions to an optimization over a constrained set of vectors, thus finite
dimensional problem.

Consequently, 2.6 allows us to use the PEP framework to study the class of
$\operatorname{QG}^{+}(L)$ convex functions. Therefore, we obtained and
verified all the results of this work thanks to the different programming
tools that have recently been developed for easing the access to the PEP
framework (see the packages [50, 20]). For each algorithm studied in this
paper, PEPs also provided the associated tight bound. Finally, PEPs also
guided us to prove the lower bound of Theorem 2.3 thanks to the study of the
greedy first-order method (_GFOM_) from [13].

##  3 Discussion and concluding remarks

In this section, we discuss a few takeaways of the results. The messages of
this section include optimality and adaptivity results for heavy-ball with a
line-search, a discussion on the applicability of this functional class beyond
its simple use, as well as a few words on the limitations of considering this
simple class of convex functions.

###  3.1 Optimality of HB algorithm

An ever-recurring question in the field of optimization is the convergence of
HB methods on smooth and strongly convex functions. On the one hand, HB is
optimal (in the sense that it achieves the optimal worst-case guarantee) for
convex quadratic objectives and can then be seen as a variant of Chebyshev
iterative method [17, 31, 52]. Even with a simple (constant) tuning of the
step-size and momentum parameters, it is optimal (i.e., achieving rates
$O(1/n^{2})$ for $L$-smooth convex quadratics, and $(1-O(\sqrt{\mu/L}))^{n}$
if the problem is also $\mu$-strongly convex.).

On the other hand, the method does not generalize well to (non quadratic)
smooth strongly convex functions: Lessard et al. [32, Figure 7] built a
function for which the heavy-ball method, tuned with the same dependence to
$L$ and $\mu$ than for the quadratic case, fails to converge. More generally,
while other sets of hyper-parameters allow to obtain convergence for the class
of smooth and (strongly) convex [18], heavy-ball was never showed to
accelerate w.r.t. the gradient descent method, and the possibility to obtain
such an acceleration remains an open question to the best of our knowledge.
Simultaneously, Nesterov’s accelerated gradient method [40] does achieve such
an acceleration.

In summary, while for quadratic convex problems it has the optimal worst-case
guarantee, heavy-ball is believed not to satisfy this property for smooth and
(strongly) convex functions. Interestingly, 2.5 shows that heavy-ball is
optimal (with rate $O(1/n)$) over the (larger) class $\operatorname{QG}^{+}$
convex.

This observation questions the existence of intermediary classes (smaller than
$\operatorname{QG}^{+}$ convex and containing quadratic functions), over which
heavy-ball would achieve a $O(1/n^{2})$ convergence guarantee. In the next
section, we discuss the adaptivity of the method.

###  3.2 Adaptivity of HB line-search algorithm 3

The search for adaptive and parameter free methods is a major challenge in
optimization as the regularity of the function (both in terms of class and
class-parameter $L$) is often unknown. In the rest of the section, we discuss
the fact that Algorithm 3 provides a parameter-free and adaptive to
$\operatorname{QG}^{+}(L)$ and $M$-Lipshitz functions method. Those results
are summarized in Table 2.

Table 2:  Optimality of the proposed methods over the set of
$\operatorname{QG}^{+}$ convex functions and $M$-Lipschitz convex functions.
ELS: Exact Line-Search.
${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$
indicates optimality among the class and
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
the contrary. All counter examples are given in App. D. $\ {}^{\dagger}$:
constants resulting in optimal convergence rates depend on the class, thus for
example heavy-ball with step-size $\frac{\text{constant}}{(t+2)}$ is not
adaptive as it does not achieve the optimal rate for both classes with the
same constant. $\ {}^{\ddagger}$: up to a $\log$ factor.

Method | Function class | Parameter free
---|---|---
Algorithm | Step-sizes $(\gamma_{t})_{0\leq t\leq n-1}$ | Iterate |  $\operatorname{QG}^{+}(L)$ convex |  $M$-Lipschitz convex |
Subgradient (Alg. 1) | $\text{constant}^{\dagger}$ | Average | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ | (Thm. 2.1) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.1) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
Subgradient (Alg. 6) | $\text{constant}^{\dagger}/\sqrt{t}$ | Average | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (5) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}^{\ddagger}$ |  [41, Sec. 3.2.3] | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
Subgradient (Alg. 7) | ELS | Average | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$
Subgradient (Alg. 7) | ELS | Last | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$
Heavy-ball (Alg. 2) | $\text{constant}^{\dagger}/(t+2)$ | Last | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ | (Cor. 2.5) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ |  [13, , Cor. 3] | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
Heavy-ball (Alg. 3) | ELS | Last | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ | (Cor. 2.5) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ |  [13, , Cor. 4] | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$

Non convergence of the line-search version of Algorithm 1. While the line-
search version of Algorithm 2 (i.e. Algorithm 3) allows to get rid of the
knowledge of $L$ without degrading the convergence guarantee for the latest
iterate, this is not the case for subgradient method. In fact subgradient with
line-search Algorithm 7 does not converge, even when looking at the PR
averaged iterate (see D.2). It thus destroys the guarantee given in Theorem
2.1 for Algorithm 1 with constant step-size $1/L$.

Algorithm 1 is not adaptive to the class of Lipschitz functions. While
Algorithm 1 with averaging and constant step-size $1/L$ is optimal for the
class $\operatorname{QG}^{+}(L)$ convex, for any sequence of constant step-
sizes, neither the average nor the last iterate of Algorithm 1 converge over
the class of $M$-Lipschitz functions (see D.1). On the other hand, to obtain a
nearly (up to a log factor) optimal convergence rate $O(\log(n)/\sqrt{n})$,
one can use $\gamma_{t}=\text{constant}/\sqrt{t}$ for $t\in\\{1,\dots,n\\}$,
but such a sequence degrades the converge for $\operatorname{QG}^{+}$ as
proved by the lower bound 2.2.

Adaptivity of HB line-search (Algorithm 3). While Algorithm 3 requires to
perform exact line-search steps, its first advantage over Algorithm 2 is not
requiring the knowledge of the class parameter $L$. Algorithm 3 is thus
adaptive to the class parameter $L$. This is analogous of _SSEP-based
subgradient method_ presented in Drori and Taylor [13, Corollary 3] and its
line-search version [See 13, Corollary 4] that are both optimal on the class
of Lipschitz continuous and convex functions. The first one requires the
knowledge of the parameter class $M$, the distance of the starting point to
optimum $d(x_{0},\mathcal{X}_{\star})$ as well as the number of performed
steps, while the second one replaces this knowledge by exact line-search
steps. Moreover, we note that _SSEP-based subgradient method_ and Algorithm 2
are very similar to each other. Indeed, their respective update steps can be
written as
$x_{k}\leftarrow\frac{k}{k+1}x_{k-1}+\frac{1}{k+1}x_{0}-\frac{d(x_{0},\mathcal{X}_{\star})}{M\sqrt{N+1}}\frac{1}{k+1}\sum_{i=0}^{k-1}g_{i}$
and
$x_{k}\leftarrow\frac{k}{k+1}x_{k-1}+\frac{1}{k+1}x_{0}-\frac{1}{L}\frac{1}{k+1}\sum_{i=0}^{k-1}g_{i}.$

Remarkably, only the two constants in front of
$\frac{1}{k+1}\sum_{i=0}^{k-1}g_{i}$ differ between the two methods. Thus,
their two line-search versions are identical. We conclude from Corollary 2.5
and Drori and Taylor [13, Corollary 4] that Algorithm 3 is optimal on the
classes of Lipschitz convex functions _and_ on the classes of
$\operatorname{QG}^{+}$ convex functions. One can run this algorithm without
knowing the type of conditions that are verified by the objective function and
still benefit from a guarantee of optimality. This is a significant argument
in favor of Algorithm 3.

###  3.3 Leveraging our analysis to obtain convergence bounds on other classes

One of the major limitations of the $\operatorname{QG}^{+}$ class is that all
functions within the class must be twice differentiable at the set of optimal
points. This typically excludes some Lipschitz functions, as for example
$x\mapsto\|x\|_{1}$ or problems involving Lasso regularization. In this
section, we show that our Section 2 can be leveraged to automatically obtain
rates on more complete classes of functions, that combine the limitations of
the Lipschitz convex and $\operatorname{QG}^{+}$ convex classes.
To introduce these classes, we denote $h$ a generic function defined on
$\mathbb{R}^{+}$ and verifying: $h(0)=0$, $h$ is strictly increasing and $h$
is concave. We consider the class of functions with $h$ relative growth.

###### Definition 3.1

A function $f$ is $h$-relatively upper bounded (denoted
$h$-$\operatorname{RG}^{+}$) if for all $x\in\mathbb{R}^{d}$:

$f(x)-f_{\star}\leq h\left(d(x,\mathcal{X}_{\star})^{2}\right).$

We denote the set of such functions by $\operatorname{RG}^{+}(h)$, and by
$\operatorname{RG}^{+}$ when $h$ is left unspecified.

These classes enable to cover the $\operatorname{QG}^{+}$ classes, the
Lipschitz classes, and more.

###### Remark 3.2

(Examples) These three examples of functions $h$ satisfy the required
assumptions:

  1. 1.

When $h$ is the linear function $h:z\mapsto\frac{Lz}{2}$, then simply
$\operatorname{RG}^{+}(h)=\operatorname{QG}^{+}(L)$.

  2. 2.

When $h$ is the function $h:z\mapsto M\sqrt{z}$, then simply
$\operatorname{RG}^{+}(h)=\left\\{M\text{-Lipschitz continuous}\right\\}$.

  3. 3.

When $h:z\mapsto M\sqrt{z}+\frac{Lz}{2}$ a broader class containing the
limitations of both previous ones.

In the following, we consider the class of $h$-$\operatorname{RG}^{+}$ and
convex functions. We then propose Algorithm 4, which consists in applying
Algorithm 2 (with the update written as in Equation 6) to the
$\operatorname{QG}^{+}$ convex function $h^{-1}\circ(f-f_{\star})$. We obtain
the following convergence rate.

Algorithm 4 Heavy-ball method for $h$-$\operatorname{RG}^{+}$ convex functions

Input: $x_{0}$, $h$, $f_{\star}$

for  _$k=1\ldots n$_ do

Choose $g_{k-1}$ from $\partial f(x_{k-1})$
$\gamma_{k-1}=\frac{1}{2(k+1)}\frac{1}{h^{\prime}\circ
h^{-1}\left(f(x_{k-1})-f_{\star}\right)}$
$x_{k}\\!\leftarrow\\!x_{k-1}-\gamma_{k-1}g_{k-1}+\frac{k-1}{k+1}\left(x_{k-1}-x_{k-2}\right)$

Output: $x_{n}$

Algorithm 5 Heavy-ball method for Lipschitz continuous convex functions

Input: $x_{0}$, $M$, $f_{\star}$

for  _$k=1\ldots n$_ do

Choose $g_{k-1}$ from $\partial f(x_{k-1})$
$\gamma_{k-1}=\frac{1}{k+1}\frac{f(x_{k-1})-f_{\star}}{M^{2}}$
$x_{k}\\!\leftarrow\\!x_{k-1}-\gamma_{k-1}g_{k-1}+\frac{k-1}{k+1}\left(x_{k-1}-x_{k-2}\right)$

Output: $x_{n}$

###### Theorem 3.3

__Let $f$ an $h-\operatorname{RG}^{+}$ convex function, and $x_{0}$ any
starting point. Then Algorithm 4 verifies $f(x_{n})-f_{\star}\leq
h\left(\frac{d(x_{0},\mathcal{X}_{\star})^{2}}{n+1}\right).$ In the examples
of 3.2, this gives:

  1. 1.

When $h$ is the linear function $h:z\mapsto\frac{Lz}{2}$ ($f$ is
$L$-$\operatorname{QG}^{+}$ convex), then
$f(x_{n})-f_{\star}\leq\frac{L}{2}\frac{d(x_{0},\mathcal{X}_{\star})^{2}}{n+1}$.

  2. 2.

When $h$ is the function $h:z\mapsto M\sqrt{z}$ ($f$ is $M$-Lip. convex), then
$f(x_{n})-f_{\star}\leq M\frac{d(x_{0},\mathcal{X}_{\star})}{\sqrt{n+1}}$.

  3. 3.

When $h$ is the function $h:z\mapsto M\sqrt{z}+\frac{Lz}{2}$, then
$f(x_{n})-f_{\star}\leq
M\frac{d(x_{0},\mathcal{X}_{\star})}{\sqrt{n+1}}+\frac{L}{2}\frac{d(x_{0},\mathcal{X}_{\star})^{2}}{n+1}$.

Sketch of proof. The proof consists in inverting $h$ and applying one of the
results on the $\operatorname{QG}^{+}$ convex functions
$h^{-1}\left(f-f_{\star}\right)$. For a detailed proof, see Appendix F.
$\hfill\blacksquare$

We also observe that for $h:z\mapsto\frac{Lz}{2}$, Algorithm 4 is exactly
Algorithm 2 and we recover the worst-case guarantee provided in Theorem 3.3.
Similarly, when considering $h:z\mapsto M\sqrt{z}$, Algorithm 4 is written as
Algorithm 5 and we recover the worst-case guarantee provided in [13, Cor. 3].
However, in this case the algorithm is different: the latest requires the
knowledge of $d(x_{0},\mathcal{X}_{\star})$, while Algorithm 5 requires the
knowledge of $f_{\star}$. In this sense, the two proposed methods are
complementary.

Finally, we emphasize the fact that in practice, a lot of machine learning
models requires to minimize non-smooth functions that are neither Lipschitz
continuous nor $\operatorname{QG}^{+}$ (e.g. least-square regressions with
lasso penalization of $\text{TV-L}_{2}$ model widely used in computer vision).
These functions can be tackled using the flexible function
$h(z)=M\sqrt{z}+\frac{L}{2}z$ Then, applying 3.3 leads to the guarantee given
in the third point of 3.3 obtained with Algorithm 4 where
$\gamma_{k-1}\leftarrow\frac{1}{k+1}\frac{1}{L}\Big{[}1-1/\sqrt{1+\frac{2L}{M^{2}}(f(x_{k-1})-f_{\star})}\Big{]}$.

Extension with additional constraint. In Appendix G, we provide geometric
convergence guarantees when the functions are also assumed satisfy a
relaxation of strong convexity, $\operatorname{QG}^{-}$.

List of potential applications. The $\operatorname{QG}^{+}$ class, and its
extension to $h-\operatorname{RG}^{+}$ offer a flexibility that allows to
tackle several non-smooth machine learning problems, including for example
RELU activation, $L_{1}$ or TV regularization. As an example, the classical
TV-$L_{2}$ denoising problem, which combines a term with quadratic growth with
a non-smooth (even at the optimum) term, is neither Lipschitz nor smooth, but
belongs to our class $h-\operatorname{RG}^{+}$, with $h:z\mapsto
M\sqrt{z}+\frac{Lz}{2}$ (3.2-3).

Limitations. As specific methods have often been designed for those
applications, our approach does not bring a systematic improvement. Yet, we
believe it paves the way for adaptive methods that could do so. Remark that
our Algorithm 3 is adaptive and optimal for both the class of
$\operatorname{QG}^{+}(L)$ functions, and the class of $M$-Lipschitz
continuous ones. Extending our analysis to obtain an adaptive algorithm for
$h-\operatorname{RG}^{+}$, which is left as an open direction, would allow to
efficiently tackle TV-$L^{2}$ type of problems in a parameter-free way.

#### Conclusion.

In this paper, we thoroughly analyze the class of convex
$\operatorname{QG}^{+}$ functions. This function class relaxes the smoothness
assumption and is motivated by the fact that $\operatorname{QG}^{+}$ satisfies
condition continuity, a desirable property for analyzing first-order methods.
We analyze several such methods, and provide tight worst-case guarantees for
them. Three methods achieve the optimal convergence rate over the class. Our
analysis is supported by the derivation of interpolation conditions allowing
to verify all the results numerically. In particular, we observe that a heavy-
ball algorithm results in acceleration (w.r.t. the subgradient method),
attaining the lower complexity bound for this class, a surprising result with
respect to the smooth case. Moreover, using line-search, we obtain a
parameter-free algorithm which is adaptive to the class parameter in
$\operatorname{QG}^{+}$, and to the function class, as it also achieves the
optimal rate for Lipschitz functions, a strongly desirable property in
practice. Finally, we leverage our results to obtain convergence bounds for
more complex classes of functions, combining the difficulties of the
$\operatorname{QG}^{+}$ and the Lipschitz classes. Overall, this work
participates to the trend of questioning the relevance of the most classical
assumptions used in the analysis of first-order optimization methods. While
our results are not intended to provide a definitive answer to this question,
it goes one step further by providing an in-depth analysis for a more stable
class of functions. Providing a similar analysis while relaxing convexity is a
major open challenge.

## Acknowledgments and Disclosure of Funding

The work of B. Goujaud and A. Dieuleveut is partially supported by
ANR-19-CHIA-0002-01/chaire SCAI, and Hi!Paris. A. Taylor acknowledges support
from the European Research Council (grant SEQUOIA 724063). This work was
partly funded by the French government under management of Agence Nationale de
la Recherche as part of the “Investissements d’avenir” program, reference
ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

## References

  * Abbaszadehpeivasti et al. [2022] Hadi Abbaszadehpeivasti, Etienne de Klerk, and Moslem Zamani.  Conditions for linear convergence of the gradient method for non-convex optimization.  _arXiv preprint arXiv:2204.00647_ , 2022.
  * Agarwal et al. [2012] Alekh Agarwal, Sahand N. Negahban, and Martin J. Wainwright.  Fast global convergence of gradient methods for high-dimensional statistical recovery.  _Ann. Statist._ , 40(5):2452–2482, 2012.
  * Anitescu [2000] Mihai Anitescu.  Degenerate nonlinear programming with a quadratic growth condition.  _SIAM Journal on Optimization_ , 10(4):1116–1135, 2000.
  * Bauschke et al. [2017] Heinz H. Bauschke, Jérôme Bolte, and Marc Teboulle.  A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications.  _Mathematics of Operations Research_ , 42(2):330–348, 2017.
  * Bolte et al. [2017] Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W. Suter.  From error bounds to the complexity of first-order descent methods for convex functions.  _Mathematical Programming_ , 165(2):471–507, 2017\.
  * Bonnans and Ioffe [1995] Joseph Frédéric Bonnans and Alexander Ioffe.  Second-order sufficiency and quadratic growth for nonisolated minima.  _Mathematics of Operations Research_ , 20(4):801–817, 1995.
  * Bottou and Bousquet [2007] Léon Bottou and Olivier Bousquet.  The tradeoffs of large scale learning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2007.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Chieu et al. [2021] Nguyen Huy Chieu, Nguyen Thi Quynh Trang, and Ha Anh Tuan.  Quadratic growth and strong metric subregularity of the subdifferential for a class of non-prox-regular functions, 2021.
  * Cui et al. [2017] Ying Cui, Chao Ding, and Xinyuan Zhao.  Quadratic growth conditions for convex matrix optimization problems associated with spectral functions, 2017.
  * Dragomir et al. [2021] Radu-Alexandru Dragomir, Adrien B. Taylor, Alexandre d’Aspremont, and Jérôme Bolte.  Optimal complexity and certification of bregman first-order methods.  _Mathematical Programming_ , pages 1–43, 2021.
  * Drori [2014] Yoel Drori.  _Contributions to the Complexity Analysis of Optimization Algorithms_.  PhD thesis, Tel-Aviv University, 2014.
  * Drori and Taylor [2020] Yoel Drori and Adrien B. Taylor.  Efficient first-order methods for convex minimization: a constructive approach.  _Mathematical Programming_ , 184(1):183–220, 2020\.
  * Drori and Teboulle [2014] Yoel Drori and Marc Teboulle.  Performance of first-order methods for smooth convex minimization: a novel approach.  _Mathematical Programming_ , 145(1):451–482, 2014\.
  * Drusvyatskiy and Ioffe [2015] Dmitriy Drusvyatskiy and Alexander D. Ioffe.  Quadratic growth and critical point stability of semi-algebraic functions.  _Mathematical Programming_ , 153(2):635–653, 2015\.
  * Drusvyatskiy and Lewis [2018] Dmitriy Drusvyatskiy and Adrian S Lewis.  Error bounds, quadratic growth, and linear convergence of proximal methods.  _Mathematics of Operations Research_ , 43(3):919–948, 2018.
  * Flanders and Shortley [1950] Donald A. Flanders and George Shortley.  Numerical determination of fundamental modes.  _Journal of Applied Physics_ , 21(12):1326–1332, 1950.
  * Ghadimi et al. [2015] Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson.  Global convergence of the heavy-ball method for convex optimization.  In _2015 European control conference (ECC)_ , pages 310–315, 2015\.
  * Gong and Ye [2014] Pinghua Gong and Jieping Ye.  Linear convergence of variance-reduced stochastic gradient without strong convexity.  _arXiv:1406.1102_ , 2014.
  * Goujaud et al. [2022] Baptiste Goujaud, Céline Moucer, François Glineur, Julien Hendrickx, Adrien Taylor, and Aymeric Dieuleveut.  PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python.  _preprint arXiv:2201.04040_ , 2022.
  * Guille-Escuret et al. [2021] Charles Guille-Escuret, Baptiste Goujaud, Manuela Girotti, and Ioannis Mitliagkas.  A study of condition numbers for first-order optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1261–1269, 2021.
  * Guille-Escuret et al. [2022] Charles Guille-Escuret, Baptiste Goujaud, Adam Ibrahim, and Ioannis Mitliagkas.  Gradient descent is optimal under lower restricted secant inequality and upper error bound.  _arXiv preprint arXiv:2203.00342_ , 2022.
  * Hanzely et al. [2021] Filip Hanzely, Peter Richtarik, and Lin Xiao.  Accelerated bregman proximal gradient methods for relatively smooth convex optimization.  _Computational Optimization and Applications_ , 79(2):405–440, 2021.
  * Hardt et al. [2018] Moritz Hardt, Tengyu Ma, and Benjamin Recht.  Gradient descent learns linear dynamical systems.  _Journal of Machine Learning Research_ , 19, 2018.
  * Hazan et al. [2015] Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz.  Beyond convexity: Stochastic quasi-convex optimization.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 1594–1602. Curran Associates, Inc., 2015.
  * Ioffe [1994] Alexander Ioffe.  On sensitivity analysis of nonlinear programs in banach spaces: the approach via composite unconstrained optimization.  _SIAM Journal on Optimization_ , 4(1):1–43, 1994\.
  * Iouditski and Nesterov [2014] Anatoli Iouditski and Yuri Nesterov.  Primal-dual subgradient methods for minimizing uniformly convex functions.  _preprint arXiv:1401.1792_ , 2014.
  * Kim and Fessler [2016] Donghwan Kim and Jeffrey A Fessler.  Optimized first-order methods for smooth convex minimization.  _Mathematical programming_ , 159(1):81–107, 2016\.
  * Kurdyka [1998] Krzysztof Kurdyka.  On gradients of functions definable in o-minimal structures.  _Annales de l’institut Fourier_ , 48:769–783, 1998.
  * Lambert et al. [2004] Delphine Lambert, Jean-Pierre Crouzeix, V. Hien Nguyen, and Jean-Jacques Strodiot.  Finite convex integration.  _Journal of Convex Analysis_ , 11(1):131–146, 2004.
  * Lanczos [1952] Cornelius Lanczos.  Solution of systems of linear equations by.  _Journal of research of the National Bureau of Standards_ , 49(1):33, 1952.
  * Lessard et al. [2016] Laurent Lessard, Benjamin Recht, and Andrew Packard.  Analysis and design of optimization methods via integral quadratic constraints.  _SIAM Journal on Optimization_ , 26(1):57–95, 2016.
  * Liu and Wright [2015] Ji Liu and Stephen J. Wright.  Asynchronous stochastic coordinate descent: Parallelism and convergence properties.  _SIAM Journal on Optimization_ , 25(1):351—376, 2015.
  * Lu et al. [2018] Haihao Lu, Robert M. Freund, and Yurii Nesterov.  Relatively-smooth convex optimization by first-order methods, and applications.  _SIAM Journal on Optimization_ , 28(1):333–354, 2018.
  * Luo and Tseng [1993] Zhi-Quan Luo and Paul Tseng.  Error bounds and convergence analysis of feasible descent methods: a general approach.  _Annals of Operations Research_ , 46(1):157–178, 1993.
  * Necoara et al. [2019] Ion Necoara, Yurii Nesterov, and Francois Glineur.  Linear convergence of first order methods for non-strongly convex optimization.  _Mathematical Programming_ , 175(1):69–107, 2019\.
  * Nemirovskii [1994] Arkadi S. Nemirovskii.  Information-based complexity of convex programming.  Lecture notes, 1994.
  * Nemirovskii and Nesterov [1985] Arkadi S. Nemirovskii and Yurii Nesterov.  Optimal methods of smooth convex minimization.  _USSR Computational Mathematics and Mathematical Physics_ , 25(2):21–30, 1985.
  * Nemirovskii and Yudin [1983] Arkadi S. Nemirovskii and David B. Yudin.  Problem complexity and method efficiency in optimization.  _Willey-Interscience, New York_ , 1983.
  * Nesterov [1983] Yurii Nesterov.  A method of solving a convex programming problem with convergence rate ${O}(1/k^{2})$.  _Soviet Mathematics Doklady_ , 27(2):372–376, 1983.
  * Nesterov [2003] Yurii Nesterov.  _Introductory Lectures on Convex Optimization_.  Springer, 2003.
  * Nesterov [2013] Yurii Nesterov.  Gradient methods for minimizing composite functions.  _Mathematical programming_ , 140(1):125–161, 2013\.
  * Peng et al. [2020] Wei Peng, Hui Zhang, Xiaoya Zhang, and Lizhi Cheng.  Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions.  _Journal of Global Optimization_ , 78(1):69–89, 2020.
  * Polyak [1963] Boris T. Polyak.  Gradient methods for the minimisation of functionals.  _USSR Computational Mathematics and Mathematical Physics_ , 3(4):864 – 878, 1963.
  * Polyak [1987] Boris T. Polyak.  _Introduction to optimization_.  Optimization Software New York, 1987.
  * Polyak and Juditsky [1992] Boris T. Polyak and Anatoli B Juditsky.  Acceleration of stochastic approximation by averaging.  _SIAM journal on control and optimization_ , 30(4):838–855, 1992.
  * Rockafellar [1970] Ralph T. Rockafellar.  _Convex Analysis_.  Princeton University Press., 1970.
  * Ruppert [1988] David Ruppert.  Efficient estimations from a slowly convergent robbins-monro process.  Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
  * Taylor et al. [2017a] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur.  Exact worst-case performance of first-order methods for composite convex optimization.  _SIAM Journal on Optimization_ , 27(3):1283–1313, 2017a.
  * Taylor et al. [2017b] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur.  Performance estimation toolbox (PESTO): automated worst-case analysis of first-order optimization methods.  In _56th Annual Conference on Decision and Control (CDC)_ , pages 1278–1283, 2017b.
  * Taylor et al. [2017c] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur.  Smooth strongly convex interpolation and exact worst-case performance of first-order methods.  _Mathematical Programming_ , 161(1-2):307–345, 2017c.
  * Young [1953] David Young.  On richardson’s method for solving linear systems with positive definite matrices.  _Journal of Mathematics and Physics_ , 32(1-4):243–255, 1953.
  * Zhang [2017a] Hui Zhang.  Linear convergence of the proximal incremental aggregated gradient method under quadratic growth condition, 2017a.
  * Zhang [2017b] Hui Zhang.  The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth.  _Optimization Letters_ , 11(4):817–833, 2017b.
  * Zhang and Yin [2013] Hui Zhang and Wotao Yin.  Gradient methods for convex minimization: better rates under weaker conditions.  Cam report, UCLA, 2013.

## Organisation of the appendix

This appendix contains the proofs of the theorems stated in the main core of
the paper. We also state a conjecture and bring some evidence about its
statement. This appendix also contains discussions and extended results.

Appendix A details the results on the subgradient method. Appendix A.1
contains the proof of 2.1, Appendix A.2 contains the proof of 2.2 and Appendix
A.3 contains a conjecture that does not appear in the main core of the paper.
This appendix also contains some evidence supporting this conjecture.

Appendix B contains the proofs for lower bounds on the class
$\operatorname{QG}^{+}$ convex. Appendix B.1 contains the proofs of 2.3
stating the lower bound under the classical assumption that the difference
between the iterates lies into the span of observed gradients. Appendix B.2
extends the latter results without the aforementioned assumption.

Appendix C contains the proof of Theorem 2.4, the main result of the paper,
stating that all first order algorithm verifying a given identity, also enjoys
an upper bound guarantee.

Appendix D contains the proofs of all the claims that figure in Table 2 that
are not already made elsewhere in this work or in others.

Appendix E contains the proof of 2.6, essential to use the PEP framework.

Appendix F contains all the proofs and discussions related to the extended
class of the $\operatorname{RG}^{+}$ convex functions

Finally, Appendix G contains linear convergence result under an additional
assumption similar to the classical quadratic growth assumption. This result
is not presented in the main core in the paper, since it is a bit out of the
scope of the main message. However, we thought it was worth mentioning it
here.

###### Contents

  1. 1 Introduction
  2. 2 A few worst-case guarantees for minimizing $\operatorname{QG}^{+}$ convex functions
  3. 3 Discussion and concluding remarks
  4. A (Sub)gradient method on $\operatorname{QG}^{+}$-convex functions
  5. B First-order lower bound
  6. C Main result: worst-case guarantee of proposed methods
  7. D Summary of convergence results on $\operatorname{QG}^{+}$ convex and Lipschitz convex
  8. E Interpolation results for $\operatorname{QG}^{+}$ convex functions
  9. F Convergence bound on other classes
  10. G Linear convergence guarantees under lower bound assumption

##  Appendix A (Sub)gradient method on $\operatorname{QG}^{+}$-convex
functions

In this appendix, we provide the proof of Theorems 2.1 and 2.2 stating
respectively an upper bound result on the subgradient method with fixed step-
size $1/L$ on the Polyak-Rupert averaged iterate, and a lower bound result on
the subgradient method on the last iterate. Finally, based on this lower
bound, we suggest a specific tuning of the subgradient method for
$\operatorname{QG}^{+}$ convex functions. A conjecture is formulated on the
worst-case bound achieved by this method with the prescribed tuning, as well
as evidence obtained through the PEP framework.

###  A.1 Convergence of subgradient method with fixed step-size at Polyak-
Rupert averaged iterate

In section 2.1, we state the following theorem about a worst-case upper bound
of Algorithm 1 on the class of $\operatorname{QG}^{+}$-convex functions. In
this section, we provide the proof of this theorem.

See 2.1

Proof. Let $k\in[0,n]$. We have

$\displaystyle d(x_{k+1},\mathcal{X}_{\star})^{2}$ $\displaystyle=$
$\displaystyle\|x_{k+1}-\pi_{\mathcal{X}_{\star}}(x_{k+1})\|^{2}$
$\displaystyle\leq$
$\displaystyle\|x_{k+1}-\pi_{\mathcal{X}_{\star}}(x_{k})\|^{2}$
$\displaystyle=$ $\displaystyle\|x_{k}-\gamma
g_{k}-\pi_{\mathcal{X}_{\star}}(x_{k})\|^{2},\qquad\text{ with
}g_{k}\in\partial f(x_{k})$ $\displaystyle=$
$\displaystyle\|x_{k}-\pi_{\mathcal{X}_{\star}}(x_{k})\|^{2}-2\gamma\left<x_{k}-\pi_{\mathcal{X}_{\star}}(x_{k}),g_{k}\right>+\gamma^{2}\|g_{k}\|^{2}$
$\displaystyle\overset{Eq.~{}\eqref{eq:interp_convexity_qg}}{\leq}$
$\displaystyle\|x_{k}-\pi_{\mathcal{X}_{\star}}(x_{k})\|^{2}-2\gamma\left(f(x_{k})-f_{\star}+\frac{1}{2L}\|g_{k}\|^{2}\right)+\gamma^{2}\|g_{k}\|^{2}$
$\displaystyle=$ $\displaystyle
d(x_{k},\mathcal{X}_{\star})^{2}-2\gamma\left(f(x_{k})-f_{\star}\right)-\gamma\left(\frac{1}{L}-\gamma\right)\|g_{k}\|^{2}$
$\displaystyle\overset{\gamma=\frac{1}{L}}{=}$ $\displaystyle
d(x_{k},\mathcal{X}_{\star})^{2}-\frac{2}{L}\left(f(x_{k})-f_{\star}\right)$

By reordering the terms and summing over $k$:

$\sum_{k=0}^{n}(f(x_{k})-f_{\star})\leq\frac{L}{2}d(x_{0},\mathcal{X}_{\star})^{2}$
(10)

which leads to the desired results.

$\hfill\blacksquare$

###### Remark A.1

From Theorem 2.1, we conclude

$\displaystyle\min_{0\leq k\leq n}f(x_{k})-f_{\star}$ $\displaystyle\leq$
$\displaystyle\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}$
$\displaystyle f\left(\frac{1}{n+1}\sum_{k=0}^{n}x_{k}\right)-f_{\star}$
$\displaystyle\overset{\text{(by convexity)}}{\leq}$
$\displaystyle\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}.$

###### Remark A.2

Note that this bound is tight not only for $\operatorname{QG}^{+}$ convex
functions, but also for smooth convex functions.

Indeed, we consider the real Huber function defined as

$f(x)=\left\\{\begin{array}[]{cc}\frac{L}{2}x^{2}&\text{if }|x|\leq 1\\\
L|x|-\frac{L}{2}&\text{if }|x|\geq 1\end{array}\right.$ (11)

This function is $L$-smooth convex and often used to find lower bounds [See
e.g. 14, 51, 28]. Moreover, starting from $x_{0}=n+1$, GD with
$\gamma=\frac{1}{L}$ leads exactly to $x_{k}=n+1-k$ for all $k\leq n$, hence
$f(x_{k})-f_{\star}=L\left(n+\frac{1}{2}-k\right)$ and
$\sum_{k=0}^{n}(f(x_{k})-f_{\star})=L\sum_{k=0}^{n}n+\frac{1}{2}-k=\frac{L}{2}(n+1)^{2}=\frac{L}{2}d(x_{0},\mathcal{X}_{\star})^{2}$.

###  A.2 Convergence limitation of the subgradient method in last iterate

In this section, we prove Theorem 2.2 stating a lower bound guarantee on the
convergence of the subgradient method. This proof is by far the most technical
of this paper due to the amount of newly introduced notations.

See 2.2

Proof. Let $\eta>0$.

We introduce the following notations:

  * •

$\delta\triangleq\left(\frac{\eta\sqrt{3}}{1+L\gamma_{n-2}}\right)^{1/2}$

  * •

Huber function

$h_{\delta}(x)=\begin{cases}\frac{L}{2}x^{2}&\text{if }x\leq\delta\\\ L\delta
x-\frac{L}{2}\delta^{2}&\text{if }x>\delta\end{cases}$ (12)

  * •

For $i\in[|0,n-1|]$, define
$\xi_{i}\triangleq\delta\left(1+\sum_{k=i}^{n-2}L\gamma_{i}\right)$.

  * •

$\lambda=\frac{L\eta}{(1+L\gamma_{n-2})(1+\eta^{2}+\xi_{0}^{2})}$.

Based on those notations, we define the $3$-dimensional function

$f(x)=\max\left[\frac{L}{2}\left(x^{(1)}-1+|x^{(2)}|\sqrt{3}\right),h_{\delta}\left(x^{(3)}\right),\frac{\lambda}{2}\|x\|_{2}^{2}\right].$
(13)

$f$ is convex as maximum of 3 convex functions.

Moreover, we note that $\mathcal{X}_{\star}=\\{0\\}$ and $f_{\star}=0$.

And each of the three components defining $f$ is smaller that
$\frac{L}{2}\|x\|_{2}^{2}$. Indeed,

$\displaystyle\frac{L}{2}\left(x^{(1)}-1+|x^{(2)}|\sqrt{3}\right)$
$\displaystyle=\frac{L}{2}\left(\left(x^{(1)}\right)^{2}-\left(x^{(1)}-\frac{1}{2}\right)^{2}+\left(x^{(2)}\right)^{2}-\left(x^{(2)}-\frac{\sqrt{3}}{2}\right)^{2}\right)$
$\displaystyle\leq\frac{L}{2}\left(\left(x^{(1)}\right)^{2}+\left(x^{(2)}\right)^{2}\right)$
$\displaystyle\leq\frac{L}{2}\|x\|_{2}^{2}$ (14) $\displaystyle
h_{\delta}\left(x^{(3)}\right)$ $\displaystyle\leq\frac{L}{2}(x^{(3)})^{2}$
$\displaystyle\leq\frac{L}{2}\|x\|_{2}^{2}$ (15) $\displaystyle\lambda$
$\displaystyle\leq\frac{L\eta}{2\eta}=\frac{L}{2}\leq L,\text{ hence
}\frac{\lambda}{2}\|x\|_{2}^{2}\leq\frac{L}{2}\|x\|_{2}^{2}$ (16)

Therefore, $f$ is also $\operatorname{QG}^{+}(L)$.

We choose to start the GD algorithm at
$x_{0}\triangleq\begin{pmatrix}1&\eta&\xi_{0}\end{pmatrix}^{\top}$.

We claim that after $i$ ($0\leq i\leq n-1$) steps of GD,
$x_{i}=\begin{pmatrix}1&\eta&\xi_{i}\end{pmatrix}^{\top}$.

This can be proven by induction. Indeed, by definition, this is true for
$i=0$. We now assume this property is true for some $i<n-1$ and want to prove
it for $i+1$.

From the 3 remarks

$\displaystyle h_{\delta}(\xi_{i})$
$\displaystyle\geq\frac{L}{2}\left(1-1+|\eta|\sqrt{3}\right)$ (17)
$\displaystyle h_{\delta}(\xi_{i})$
$\displaystyle\geq\frac{\lambda}{2}\|x_{i}\|_{2}^{2}$ (18)
$\displaystyle\xi_{i}$ $\displaystyle\geq\delta,$ (19)

we conclude that $\nabla
f(x_{i})=\begin{pmatrix}0&0&L\delta\end{pmatrix}^{\top}$.

Hence
$x_{i+1}=x_{i}-\begin{pmatrix}0&0&L\gamma_{i}\delta\end{pmatrix}^{\top}=\begin{pmatrix}1&\eta&\xi_{i+1}\end{pmatrix}^{\top}$.

Finally, from the 2 remarks

$\displaystyle\frac{L}{2}(1-1+|\eta|\sqrt{3})$ $\displaystyle\geq
h_{\delta}(\xi_{n-1})$ (20) $\displaystyle\frac{L}{2}(1-1+|\eta|\sqrt{3})$
$\displaystyle\geq\frac{\lambda}{2}\|x_{n-1}\|_{2}^{2},$ (21)

we conclude that $\nabla
f(x_{n-1})=\frac{L}{2}\begin{pmatrix}1&\sqrt{3}&0\end{pmatrix}^{\top}$,
leading to
$x_{n}=x_{n-1}-\gamma_{n-1}\frac{L}{2}\begin{pmatrix}1&\sqrt{3}&0\end{pmatrix}^{\top}=\begin{pmatrix}1-\frac{L\gamma_{n-1}}{2}&\eta-\frac{L\gamma_{n-1}\sqrt{3}}{2}&\delta\end{pmatrix}^{\top}$.

We compute the two quantities

$\displaystyle\|x_{0}\|^{2}$ $\displaystyle=1+\eta^{2}+\xi_{0}^{2}$ (22)
$\displaystyle f(x_{n})$
$\displaystyle\geq\frac{L}{2}\left(1-\frac{L\gamma_{n-1}}{2}-1+|\eta-\frac{L\gamma_{n-1}\sqrt{3}}{2}|\sqrt{3}\right)$
$\displaystyle=\frac{L}{2}\left(-\frac{L\gamma_{n-1}}{2}+\left(\frac{L\gamma_{n-1}\sqrt{3}}{2}-\eta\right)\sqrt{3}\right)$
$\displaystyle=\frac{L}{2}\left(L\gamma_{n-1}-\eta\sqrt{3}\right)$ (23)

Finally,

$\displaystyle\frac{f(x_{n})-f_{\star}}{d(x_{0},\mathcal{X}_{\star})^{2}}$
$\displaystyle\geq\frac{L}{2}\frac{L\gamma_{n-1}-\eta\sqrt{3}}{1+\eta^{2}+\xi_{0}^{2}}$
$\displaystyle=\frac{L}{2}\frac{L\gamma_{n-1}-\eta\sqrt{3}}{1+\eta^{2}+\delta^{2}\left(1+\sum_{k=i}^{n-2}L\gamma_{i}\right)^{2}}$
$\displaystyle=\frac{L}{2}\frac{L\gamma_{n-1}-\eta\sqrt{3}}{1+\eta^{2}+\frac{\eta\sqrt{3}}{1+L\gamma_{n-2}}\left(1+\sum_{k=i}^{n-2}L\gamma_{i}\right)^{2}}$
$\displaystyle\underset{\eta\rightarrow
0}{\longrightarrow}\frac{L}{2}L\gamma_{n-1}.$ (24)

Hence, for any $\epsilon>0$, we can find $\eta>0$ sufficiently small such that
$f$ reaches the claim of the Theorem.

$\hfill\blacksquare$

###  A.3 A new tuning prescription

Theorem 2.2 provides a lower bound on the last iterate value of the
subgradient method on the class of $\operatorname{QG}^{+}$ convex functions.
Moreover, a new analysis of the subgradient method on the Huber function (12),
starting at $x_{0}=1+2\sum_{k=0}^{n-1}L\gamma_{k}$ provides another lower
bound.

Combining those 2 results, we know that whatever $(\gamma_{i})_{0\leq i\leq
n-1}>0$ is, there exists $f$ an $L-\operatorname{QG}^{+}$ convex function as
well as a starting point $x_{0}$ such that

$f(x_{n})-f_{\star}\geq\max\left(\frac{L}{2}\frac{1}{1+2\sum_{k=0}^{n-1}L\gamma_{k}},\frac{L}{2}L\gamma_{n-1}\right)d(x_{0},\mathcal{X}_{\star})^{2}.$
(25)

Naturally, we propose the sequence of

Algorithm 6 GD with decreasing step-sizes

Input: $x_{0}$, $L$

$u_{0}=1$

for  _k=1 …n_ do

$u_{k}\leftarrow\frac{u_{k-1}}{2}+\sqrt{\left(\frac{u_{k-1}}{2}\right)^{2}+2}$;
$\gamma_{k-1}\leftarrow\frac{1}{Lu_{k}}$; Pick  $g_{k-1}\in\partial
f(x_{k-1})$; $x_{k}\leftarrow x_{k-1}-\gamma_{k-1}g_{k-1}$

Output: $x_{n}$

$(\gamma_{i})_{0\leq i\leq n-1}>0$ that verifies for all $n$,
$\frac{L}{2}\frac{1}{1+2\sum_{k=0}^{n-1}L\gamma_{k}}=\frac{L}{2}L\gamma_{n-1}$
(for each index $n\geq 1$). This is summarized in Algorithm 6. We note that
$u_{n}\sim 2\sqrt{n}$ and $\gamma_{n-1}\sim\frac{1}{2L\sqrt{n}}$. The lower
bound (25) for this method becomes
$f(x_{n})-f_{\star}\geq\frac{L}{2}L\gamma_{n-1}d(x_{0},\mathcal{X}_{\star})^{2}\sim\frac{L}{4\sqrt{n}}d(x_{0},\mathcal{X}_{\star})^{2}$.
We conjecture that this bound is actually reached by the proposed method 6.

###### Conjecture A.3

_(Convergence of GD with decreasing step-sizes)_ The algorithm 6 verifies the
following lower bound on every $L-\operatorname{QG}^{+}$ convex function $f$:

$f(x_{n})-f_{\star}\leq\frac{L}{2u_{n}}d(x_{0},\mathcal{X}_{\star})^{2}.$ (26)

where $u_{n}$ is the sequence used in 6, defined by

$\displaystyle u_{0}$ $\displaystyle=1$ (27) $\displaystyle u_{k}$
$\displaystyle=\frac{u_{k-1}}{2}+\sqrt{\left(\frac{u_{k-1}}{2}\right)^{2}+2},\quad\text{for
every }k\in\llbracket 1,n\rrbracket.$ (28)

and verifying

$u_{n}\sim 2\sqrt{n}.$ (29)

This conjecture is supported by the Figure 1 that has been built using the PEP
framework. This figure represents the worst-case guarantee of Algorithm 6 as a
function of the number of iterations. The conjecture (red curve) follows
exactly the numerical worst-case guarantee provided by the PEPs (blue curve)
and the equivalent sequence (green curve) is very close to the 2 previous
ones.

Figure 1: Verification of the conjecture using PEPs

##  Appendix B First-order lower bound

In this section, we prove the lower bound of first order methods on
$\operatorname{QG}^{+}$ convex functions.

In the first subsection, we assume that the iterates of the first order
algorithm must stay in the span of the past observed gradients.

In the second subsection, we release this assumption and still prove the same
lower bound. This proof is a bit more technical, hence the reason why we
provide the two proofs.

###  B.1 Proof of Theorem 2.3

The following theorem brings a lower bound over all first order methods
verifying that all the iterates lie into the span of the previously observed
gradients.

See 2.3

Proof. Consider $f(x)\triangleq\frac{L}{2}\|x\|_{\infty}^{2}$ defined on
$\mathbb{R}^{n+1}$ and $x_{0}=\vec{\mathbf{1}}$.

After $k$ steps, the oracle can “choose” to return a vector that lies in the
first $k+1$ dimension of the input space, leading to $f(x_{n})-f_{\star}\geq
f(x_{0})-f_{\star}=\frac{L}{2}=\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}$.
$\hfill\blacksquare$

###### Remark B.1

Note that by considering instead
$x_{0}=\begin{pmatrix}1&1-\varepsilon/n&1-2\varepsilon/n&\ldots&1-\varepsilon\end{pmatrix}^{\top}$,
one ends up with
$f(x_{n})-f_{\star}\geq\frac{L}{2}\frac{1-\varepsilon}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}$
whatever the oracle “chooses” to return.

###  B.2 Lower bound proof without span assumption

In this section we release the span assumption and prove that the previously
shown lower bound still holds. This proof is a bit more technical than the one
of Theorem 2.3 proven in Appendix B.1.

######  Theorem B.2 (Lower bound of first order algorithm without span
assumption)

Let $\mathcal{A}$ a first-order algorithm. Then, for any $n\geq 0$, there
exists $d$ a positive integer, $f$ a $L-\operatorname{QG}^{+}$ convex function
of input space $\mathbb{R}^{d}$ and a starting point $x_{0}$ such that
$f(x_{n})-f_{\star}\geq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}$.

Proof. Let $\mathcal{E}=\left\\{v\in\mathbb{R}^{n+1}|\forall i\in\llbracket
1,n+1\rrbracket,|v_{i}|=1\right\\}$ the set of the $2^{n+1}$ vectors of
$\mathbb{R}^{n+1}$ which all coordinates are $\pm 1$.

For each $v\in\mathcal{E}$, we introduce
$f_{v}(x)\triangleq\frac{L}{2}\|x-v\|_{\infty}^{2}$ defined on
$\mathbb{R}^{n+1}$.

First note that all those functions are $L-\operatorname{QG}^{+}$ convex. We
will prove that not only there exists a starting point $x_{0}$ and a
$L-\operatorname{QG}^{+}$ convex function such that
$f(x_{n})-f_{\star}\geq\frac{L}{2}\frac{1}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}$,
but also that there exists a starting point $x_{0}$ and a function among the
$f_{v}$ we introduced above such that the latest holds.

To proceed, we need to show that the algorithm $\mathcal{A}$ cannot know the
right $v$ after only $n$ iterations and therefore, cannot guarantee
$f(x_{n})-f_{\star}\leq\frac{L}{2}$. Taking $x_{0}=\vec{0}$,
$\|x_{0}-x_{\star}\|^{2}=n+1$ whatever $x_{\star}$ is (among $\mathcal{E}$),
hence the result.

In order to prove that the algorithm cannot know the solution after $n$
iterations, we keep track of all the remaining possibilities across time.

We denote by $\mathcal{E}_{k}$ the remaining possibilities after $k$ steps of
the algorithm. In particular, $\mathcal{E}_{0}=\mathcal{E}$.

At each step $k$, $\mathcal{A}$ guesses $x_{k}$ based on all the previous
information, summarized in $\mathcal{E}_{k}$, and the oracle provides
$f(x_{k})$ and a sub-gradient $g_{k}\in\partial f(x_{k})$.

Let $v_{k}\in\arg\max_{v\in\mathcal{E}_{k}}\|x_{k}-v_{k}\|_{\infty}$. We
consider the case where the oracle behaves like if the objective function to
minimize was $f_{v_{k}}$. Moreover, in the case where $f_{v_{k}}$ is not
differentiable in $x_{k}$, we ask that the oracle returns a sub-gradient co-
linear to a vector belonging to the canonical basis (which is always
possible).

Considering $i$ such that $g_{k}$ is co-linear to $e_{i}$, we obtain
$\mathcal{E}_{k+1}=\left\\{v\in\mathcal{E}_{k}|\left<v,e_{i}\right>=\left<v_{k},e_{i}\right>\right\\}$,
reducing by half the number of remaining elements at each step (except when
the algorithm badly guesses and receive twice the same direction, in which
case one of the steps is useless).

After $n$ steps, $\mathcal{E}_{n}$ contains 2 elements, and the algorithm
$\mathcal{A}$ must guess based on nothing. Again, we consider the further one
to the last guess as the right solution, and obtain the lower bound provided
by the Theorem.

$\hfill\blacksquare$

##  Appendix C Main result: worst-case guarantee of proposed methods

In this section, we prove Theorem 2.4, the main result of this paper, stating
that all the sequences of iterates verifying a certain property enjoy an upper
bound guarantee corresponding to the lower bound presented in 2.3 and proved
in Appendix B.

See 2.4

Proof. This proof relies on the Lyapunov function

$V_{n}\triangleq
n(f(x_{n-1})-f_{\star})+\frac{L}{2}\left\|x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{n-1}\frac{1}{L}g_{i}\right\|^{2}.$
(30)

For all $k$, we verify

$\displaystyle V_{k+1}-V_{k}$ $\displaystyle=$
$\displaystyle\left[(k+1)(f(x_{k})-f_{\star})+\frac{L}{2}\left\|x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k}\frac{1}{L}g_{i}\right\|^{2}\right]$
$\displaystyle-\left[k(f(x_{k-1})-f_{\star})+\frac{L}{2}\left\|x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\right\|^{2}\right]$
$\displaystyle=$
$\displaystyle(f(x_{k})-f_{\star})+k(f(x_{k})-f(x_{k-1}))+\frac{L}{2}\left[-\frac{2}{L}\left<g_{k},x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\right>+\frac{1}{L^{2}}\|g_{k}\|^{2}\right]$
$\displaystyle=$
$\displaystyle\left(f(x_{k})-f_{\star}+\frac{1}{2L}\|g_{k}\|^{2}\right)+k(f(x_{k})-f(x_{k-1}))-\left<g_{k},x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\right>$
$\displaystyle\overset{(\ref{eq:interp_convexity},~{}\ref{eq:interp_convexity_qg})}{\leq}$
$\displaystyle\left<g_{k},x_{k}-\pi_{\mathcal{X_{\star}}}(x_{0})\right>+k\left<g_{k},x_{k}-x_{k-1}\right>-\left<g_{k},x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\right>$
$\displaystyle=$
$\displaystyle\left<g_{k},x_{k}-\pi_{\mathcal{X_{\star}}}(x_{0})+k(x_{k}-x_{k-1})-\left(x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\right)\right>$
$\displaystyle=$
$\displaystyle\left<g_{k},(k+1)x_{k}-kx_{k-1}-x_{0}+\sum_{i=0}^{k-1}\frac{1}{L}g_{i}\right>$

The assumption therefore concludes

$\forall k,V_{k+1}\leq V_{k}$

Finally,

$(N+1)(f(x_{N})-f_{\star})+\frac{L}{2}\left\|x_{0}-\pi_{\mathcal{X_{\star}}}(x_{0})-\sum_{i=0}^{N}\frac{1}{L}g_{i}\right\|^{2}=V_{n+1}\leq
V_{0}=\frac{L}{2}\|x_{0}-x^{*}\|^{2}.$

Hence,

$f(x_{N})-f_{\star}\leq\frac{L}{2}\frac{1}{N+1}\|x_{0}-x^{*}\|^{2}.$

$\hfill\blacksquare$

##  Appendix D Summary of convergence results on $\operatorname{QG}^{+}$
convex and Lipschitz convex

In this section, we state and prove the 2 results of Table 2 that are not
already proven elsewhere.

Table 2:  Optimality of the proposed methods over the set of
$\operatorname{QG}^{+}$ convex functions and $M$-Lipschitz convex functions.
ELS: Exact Line-Search.
${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$
indicates optimality among the class and
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
the contrary. All counter examples are given in App. D. $\ {}^{\dagger}$:
constants resulting in optimal convergence rates depend on the class, thus for
example heavy-ball with step-size $\frac{\text{constant}}{(t+2)}$ is not
adaptive as it does not achieve the optimal rate for both classes with the
same constant. $\ {}^{\ddagger}$: up to a $\log$ factor.

Method | Function class | Parameter free
---|---|---
Algorithm | Step-sizes $(\gamma_{t})_{0\leq t\leq n-1}$ | Iterate |  $\operatorname{QG}^{+}(L)$ convex |  $M$-Lipschitz convex |
Subgradient (Alg. 1) | $\text{constant}^{\dagger}$ | Average | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ | (Thm. 2.1) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.1) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
Subgradient (Alg. 6) | $\text{constant}^{\dagger}/\sqrt{t}$ | Average | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ |  (5) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}^{\ddagger}$ |  [41, Sec. 3.2.3] | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
Subgradient (Alg. 7) | ELS | Average | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$
Subgradient (Alg. 7) | ELS | Last | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$ | (Thm. D.2) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$
Heavy-ball (Alg. 2) | $\text{constant}^{\dagger}/(t+2)$ | Last | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ | (Cor. 2.5) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ |  [13, , Cor. 3] | ${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$
Heavy-ball (Alg. 3) | ELS | Last | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ | (Cor. 2.5) | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$ |  [13, , Cor. 4] | ${\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\checkmark}$

We first state D.1.

###### Theorem D.1

For any $M>0$ and any $\gamma>0$, the subgradient method 1 with constant step-
size $\gamma$ cannot be guaranteed to converge to optimum on all the
$M$-Lipschitz continuous convex functions, both in last iterate and in Polyak-
Rupert averaged iterate.

Proof. First we note that $f\triangleq z\mapsto M|z|$ is $M$-Lipschitz
continuous and convex. Let $\gamma>0$. We consider $x_{0}=\frac{3}{4}M\gamma$
the starting point of the subgradient method with constant step-size $\gamma$.
We verify that $x_{1}=-\frac{1}{4}M\gamma$ and that the sequence $(x_{t})_{t}$
cycles back to $\frac{3}{4}M\gamma$. Therefore, the sequence itself does not
converge and the sequence of the PR averaged iterates converges to
$\frac{1}{4}M\gamma$, while the optimum value would be 0. $\hfill\blacksquare$

Algorithm 7 Subgradient method with line-search

Input: $x_{0}$, $v_{0}\leftarrow 0$

for  _$k=1\ldots n$_ do

Pick  $g_{k-1}\in\partial f(x_{k-1})$.
$\alpha_{k}\leftarrow\arg\min_{\alpha}f\left(x_{k-1}-\alpha g_{k-1}\right)$
$x_{k}\leftarrow x_{k-1}-\alpha_{k}g_{k-1}$

Output: $x_{n}$

Then, one could wonder whether performing exact line search steps on the
subgradient method (Algorithm 7.) leads to convergence on Lipschitz continuous
convex or $\operatorname{QG}^{+}$ convex function. We now prove Theorem D.2
stating that the subgradient method with exact line search does not converge
for all functions neither of the class of Lipschitz continuous convex
functions nor of the class of $\operatorname{QG}^{+}$ convex functions,
neither in last iterate nor in Polyak-Rupert averaged iterate.

###### Theorem D.2

There exists a $\operatorname{QG}^{+}$ convex function $f_{QG}$ and a
Lipschitz continuous convex function $f_{Lip}$ such that, the iterates
$((x_{n})_{n}^{f_{QG}})_{n}$ and $((x_{n})_{n}^{f_{Lip}})_{n}$ obtained by
Algorithm 7, verify the 2 guarantees

$\displaystyle f(x_{n})-f_{\star}$ $\displaystyle\geq$
$\displaystyle\frac{L}{6}\|x_{0}-x_{\star}\|^{2}.$ (31) $\displaystyle
f(\bar{x_{n}})-f_{\star}$ $\displaystyle\geq$
$\displaystyle\frac{L}{6}\|x_{0}-x_{\star}\|^{2}.$ (32)

where $\bar{x_{n}}$ denotes the Polyak-Rupert averaged iterate obtained from
the sequence $(x_{n})_{n}$.

Proof. Considering $f_{Lip}(z)=M\|x\|_{\infty}$ and
$f_{QG}(z)=\frac{L}{2}\|x\|_{\infty}^{2}$ defined on $\mathbb{R}^{3}$, the
iterates of Algorithm 7 can be cycling between the four points $(1,1,1)$,
$(1,-1,1)$, $(-1,1,1)$ and $(-1,-1,1)$. Therefore, the aforementioned
statement. $\hfill\blacksquare$

##  Appendix E Interpolation results for $\operatorname{QG}^{+}$ convex
functions

The interpolation conditions of a given class represent the key ingredient to
use the PEP framework on this class. Theorem 2.6 provides the interpolation
conditions for the class of $\operatorname{QG}^{+}$ convex functions. In this
section, we recall this result and prove it.

See 2.6

Proof.

We prove the two implications one by one.

  * $\Rightarrow$:

Assume there exists such a convex-$\operatorname{QG}^{+}$ function $f$ that
interpolates $(x_{i},g_{i},f_{i})_{i\in I}$. Equation (8) follows immediately
from convexity. Let’s prove equation (9). Let $i\in I_{\star},\forall j\in I$
and $x\in\mathbb{R}^{d}$. We have:

$f_{j}+\left<g_{j},x-x_{j}\right>\overset{\text{CVX}}{\leq}f(x)\overset{\operatorname{QG}^{+}}{\leq}\min_{z\in\mathbb{R}^{d}}f(z)+\frac{L}{2}d(x,\mathcal{X}_{\star})^{2}\leq
f_{i}+\frac{L}{2}\|x-x_{i}\|^{2}.$

Rewriting the previous equation for $x=x_{i}+\frac{1}{L}g_{j}$ leads to
equation (9).

  * $\Leftarrow$:

Let’s consider equations (8) and (9) are verified. Applying (8) with $j\in
I_{\star}$

$\forall i\in I,\forall j\in I_{\star},f_{i}\geq f_{j}$ (33)

In particular, $\forall i\in I_{\star},\forall j\in I_{\star},f_{i}=f_{j}$.
Hence, let’s introduce $f_{\star}$ the common value of all the $f_{i}$ for
$i\in I_{\star}$. Let’s denote here $\mathcal{X}^{\star}$ the convex hull of
$\left\\{x_{i}\right\\}_{i\in I_{\star}}$. Finally let’s introduce
$\mu\triangleq 2\min_{i\in I\setminus
I_{\star}}\left(\frac{f_{i}-f_{\star}}{d(x_{i},\mathcal{X}^{\star})^{2}}\right)$.

Let’s prove that the following function $f$ is a solution:

$f(x)=\max\left(\max_{j\in
I}\left(f_{j}+\left<g_{j},x-x_{j}\right>\right),f_{\star}+\frac{\mu}{2}d\left(x,\mathcal{X}^{\star}\right)^{2}\right).$
(34)

    * -

$\forall i\in I,f(x_{i})=f_{i}$: For all $i\in I$, equation (8) shows
$\max_{j\in I}\left(f_{j}+\left<g_{j},x_{i}-x_{j}\right>\right)\leq f_{i}$ and
the definition of $\mu$ leads to
$f_{\star}+\frac{\mu}{2}d\left(x_{i},\mathcal{X}^{\star}\right)^{2}\leq
f_{i}$. Hence, for all $i\in I$, $f(x_{i})\leq f_{i}$. Moreover, from equation
(34), $f(x)\geq\left(f_{i}+\left<g_{i},x-x_{i}\right>\right)$, hence
$f(x_{i})\geq f_{i}$. Finally, we conclude $\forall i\in I,f(x_{i})=f_{i}$.

    * -

$\forall i\in I,g_{i}\in\partial f(x_{i})$: $\forall i\in
I,f(x)\geq\left(f_{i}+\left<g_{i},x-x_{i}\right>\right)$, and from the
previous point, we conclude $\forall i\in
I,f(x)\geq\left(f(x_{i})+\left<g_{i},x-x_{i}\right>\right)$. Finally, $\forall
i\in I,g_{i}\in\partial f(x_{i})$.

    * -

$f$ is convex: $f$ is clearly defined as the maximum of convex functions,
hence is convex.

    * -

$f$ is $\operatorname{QG}^{+}$: We aim at proving that $\forall
x\in\mathbb{R}^{d},f(x)\leq
f_{\star}+\frac{L}{2}d\left(x,\mathcal{X}^{\star}\right)^{2}$. Since it is
clear that $\forall
x\in\mathbb{R}^{d},f_{\star}+\frac{\mu}{2}d\left(x,\mathcal{X}^{\star}\right)^{2}\leq
f_{\star}+\frac{L}{2}d\left(x,\mathcal{X}^{\star}\right)^{2}$, it remains to
prove that $\forall x\in\mathbb{R}^{d},\forall j\in
I,f_{j}+\left<g_{j},x-x_{j}\right>\leq
f_{\star}+\frac{L}{2}d\left(x,\mathcal{X}^{\star}\right)^{2}$. The latest is
also equivalent to $\forall x\in\mathbb{R}^{d},\forall j\in I,\forall
x_{\star}\in\mathcal{X}^{\star},f_{j}+\left<g_{j},x-x_{j}\right>\leq
f_{\star}+\frac{L}{2}\|x-x_{\star}\|^{2}$. For $j$ and $x_{\star}$ fixed, this
expression is a quadratic form in $x$, optimized for
$x=x_{\star}+\frac{1}{L}g_{j}$. Hence, we need to show $\forall j\in I,\forall
x_{\star}\in\mathcal{X}^{\star},f_{j}+\left<g_{j},x_{\star}+\frac{1}{L}g_{j}-x_{j}\right>\leq
f_{\star}+\frac{L}{2}\left\|x_{\star}+\frac{1}{L}g_{j}-x_{\star}\right\|^{2}$,
also rewritten $\forall x_{\star}\in\mathcal{X}^{\star},\forall j\in
I,f_{\star}\geq
f_{j}+\left<g_{j},x_{\star}-x_{j}\right>+\frac{1}{2L}\|g_{j}\|^{2}$. Since
$\mathcal{X}^{\star}$ is the convex hull of $\left\\{x_{i}\right\\}_{i\in
I_{\star}}$, the latest is obtained by linear combination (with non-negative
weights) of equation 9 for different values of $i$.

$\hfill\blacksquare$

##  Appendix F Convergence bound on other classes

In this section, we naturally extend the previous results to the class of
$h-\operatorname{RG}^{+}$ (See. 3.1) convex functions.

See 3.3

Proof.

First note that since $h$ is strictly increasing, $h^{-1}$ is well defined.
Furthermore, Definition 3.1 can be expressed as
$h^{-1}\left(f(x)-f_{\star}\right)\leq d(x,\mathcal{X}_{\star})^{2}.$
Therefore, $h^{-1}\left(f-f_{\star}\right)$ is $2-\operatorname{QG}^{+}$. And
we know by definition that $h$ is increasing and concave, then $h^{-1}$ is
increasing and convex. Since $f$ is also convex, so is
$h^{-1}\left(f-f_{\star}\right)$.

We conclude that $h^{-1}\left(f-f_{\star}\right)$ is $2-\operatorname{QG}^{+}$
and convex, and then we know that Algorithm 6 applied on
$h^{-1}\left(f-f_{\star}\right)$ leads to

$h^{-1}\left(f(x_{n})-f_{\star}\right)\leq\frac{d(x_{0},\mathcal{X}_{\star})^{2}}{n+1}.$

It remains to compose the above by $h$ and to notice that Algorithm 6 applied
on $h^{-1}\left(f-f_{\star}\right)$ is exactly Algorithm 4.

$\hfill\blacksquare$

##  Appendix G Linear convergence guarantees under lower bound assumption

In all this section, we assume that $f$ is convex and
$h-\operatorname{RG}^{+}$ for a certain $h$. Moreover, we consider that $f$
verifies the following additional assumption (referred to as “Łojasiewicz
error bound inequality” in [5]) for a given $\kappa\geq 1$:

###### Assumption G.1

For all $x\in\mathbb{R}^{d}$, $f(x)-f_{\star}\geq
h\left(\frac{d(x,\mathcal{X}_{\star})^{2}}{\kappa}\right)$.

###### Remark G.2

When $h$ is the linear function $h:R\mapsto\frac{LR}{2}$, then $f$ is simply
$L-\operatorname{QG}^{+}$ convex as well as $\mu-\operatorname{QG}^{-}$
$\left(\text{where }\mu\triangleq\frac{L}{\kappa}\right)$(See [21] for the
definition of $\operatorname{QG}^{-}$).

We introduce the following algorithm based on the restart idea studied in [38,
42, 27].

Algorithm 8 Heavy-ball with restart

Input: $x_{0}$, $h$, $f_{\star}$

for  _$k=1\ldots n$_ do

Choose $g_{k-1}$ from $\partial f(x_{k-1})$ $l\leftarrow k\text{ mod
}\left\lfloor\kappa e\right\rfloor-1$ (between $1$ and $\left\lfloor\kappa
e\right\rfloor-1$). $x_{k}\leftarrow
x_{k-1}-\frac{1}{2(l+1)}\frac{1}{h^{\prime}\circ
h^{-1}\left(f(x_{k-1})-f_{\star}\right)}g_{k-1}+\frac{l-1}{l+1}\left(x_{k-1}-x_{k-2}\right)$

Output: $x_{n}$

This algorithm comes with the linear convergence rate guarantee

###### Theorem G.3

__Algorithm 8 verifies for every $n$ multiple of $\left\lfloor\kappa
e\right\rfloor-1$:
$d(x_{n},\mathcal{X}_{\star})^{2}\leq\left(1-\frac{1}{\kappa
e}\right)^{n}d(x_{0},\mathcal{X}_{\star})^{2}.$ (35)

Proof.

From Theorem 3.3, running Algorithm 4 leads to the guarantee

$f(x_{n})-f_{\star}\leq
h\left(\frac{d\left(x_{0},\mathcal{X}_{\star}\right)^{2}}{n+1}\right).$ (36)

From the additional assumption (G.1), we can upper bound the left hand size of
the above and write

$h\left(\frac{d(x_{n},\mathcal{X}_{\star})^{2}}{\kappa}\right)\leq
h\left(\frac{d\left(x_{0},\mathcal{X}_{\star}\right)^{2}}{n+1}\right).$

Hence,

$d(x_{n},\mathcal{X}_{\star})^{2}\leq\frac{\kappa}{n+1}d(x_{0},\mathcal{X}_{\star})^{2}.$

The latest is a contraction guarantee. Indeed, for $n$ sufficiently large,
$d(x_{n},\mathcal{X}_{\star})^{2}<d(x_{0},\mathcal{X}_{\star})^{2}$. The
average contraction factor is $\left(\frac{\kappa}{n+1}\right)^{1/n}$ and is
minimized for $n\approx\left\lfloor\kappa e\right\rfloor-1$. Choosing such a
$n$ leads to a contraction factor upper bounded by $1-\frac{1}{\kappa e}$.

This corresponds to the convergence rate obtained by applying
$\left\lfloor\kappa e\right\rfloor-1$ steps of Algorithm 4 and then restarting
it. This is described as Algorithm 8.

$\left\lfloor\kappa e\right\rfloor-1$ steps of Algorithm 4 therefore leads to
a contraction factor of $\frac{\kappa}{\left\lfloor\kappa
e\right\rfloor}\leq\left(1-\frac{1}{\kappa e}\right)^{\left\lfloor\kappa
e\right\rfloor-1}$. Thus applying the same algorithm restarted every
$\left\lfloor\kappa e\right\rfloor-1$ steps leads to a contraction factor of
$\left(1-\frac{1}{\kappa e}\right)^{q\left(\left\lfloor\kappa
e\right\rfloor-1\right)}$ after $q\left(\left\lfloor\kappa
e\right\rfloor-1\right)$ steps.

$\hfill\blacksquare$

###### Corollary G.4

__Algorithm 8 verifies for every $n$, $f(x_{n})-f_{\star}\leq
h\left(e\left(1-\frac{1}{\kappa
e}\right)^{n}d(x_{0},\mathcal{X}_{\star})^{2}\right).$ (37)

Proof.

Consider $n=q\left(\left\lfloor\kappa e\right\rfloor-1\right)+r$, with $0\leq
r<\left\lfloor\kappa e\right\rfloor-1$.

Combining Theorem G.3 applied on $q\left(\left\lfloor\kappa
e\right\rfloor-1\right)$ steps and Theorem 3.3 applied for the latest $r$
steps from starting point $x_{q\left(\left\lfloor\kappa
e\right\rfloor-1\right)}$, we get

$\displaystyle f(x_{n})-f_{\star}$
$\displaystyle\overset{\text{Theorem~{}\ref{thm:hb_restart}}}{\leq}$
$\displaystyle h\left(\frac{d(x_{q\left(\left\lfloor\kappa
e\right\rfloor-1\right)},\mathcal{X}_{\star})^{2}}{r+1}\right)$
$\displaystyle\overset{\text{Theorem~{}\ref{thm:hb_general}}}{\leq}$
$\displaystyle h\left(\frac{\left(1-\frac{1}{\kappa
e}\right)^{q\left(\left\lfloor\kappa
e\right\rfloor-1\right)}d(x_{0},\mathcal{X}_{\star})^{2}}{r+1}\right)$
$\displaystyle\leq$ $\displaystyle h\left(\frac{\left(1-\frac{1}{\kappa
e}\right)^{-r}\left(1-\frac{1}{\kappa
e}\right)^{n}d(x_{0},\mathcal{X}_{\star})^{2}}{r+1}\right)$
$\displaystyle\leq$ $\displaystyle h\left(\frac{e\left(1-\frac{1}{\kappa
e}\right)^{n}d(x_{0},\mathcal{X}_{\star})^{2}}{r+1}\right)$
$\displaystyle\leq$ $\displaystyle h\left(e\left(1-\frac{1}{\kappa
e}\right)^{n}d(x_{0},\mathcal{X}_{\star})^{2}\right)$

$\hfill\blacksquare$

###### Example G.5

_(Logistic regression)_ The logistic objective function is strictly convex and
smooth. But it is not strongly convex. However, its square is still convex,
and $\operatorname{QG}^{+}$ (not necessarily smooth anymore), and is still not
necessarily strongly convex, but is $\operatorname{QG}^{-}$. Therefore,
Theorem G.3 provides a linear convergence guarantee for Algorithm 8.

Note that without strong convexity, the classical theory does not guarantee
linear convergence of Logistic regression without further very specialized
analysis.