Many machine learning problems lack strong convexity properties. Fortunately, recent studies have revealed that first-order algorithms also enjoy linear convergences under various weaker regularity conditions. While the relationship among different conditions for convex and smooth functions is well understood, it is not the case for the nonsmooth setting. In this paper, we go beyond convexity and smoothness, and clarify the connections among common regularity conditions (including strong convexity, restricted secant inequality, subdifferential error bound, Polyak-Łojasiewic inequality, and quadratic growth) in the class of weakly convex functions.
In addition, we present a simple and modular proof for the linear convergence of the proximal point method (PPM)  for convex (possibly nonsmooth) optimization using these regularity conditions. The linear convergence also holds when the subproblems of PPM are solved inexactly with a proper control of inexactness.

Error bound, Polyak-Łojasiewic inequality, quadratic growth, proximal point method.

§ INTRODUCTION

Machine learning has shown impressive performance on a wide range of applications. Behind these successes, (sub)gradient-based methods and their variants are the workhorse algorithms. Many studies have investigated the theoretical foundations of these first-order iterative algorithms. For smooth and/or convex cases, (sub)gradient methods are most well-understood [Nesterov, 2018]. It is well-known that the basic gradient descent algorithm achieves linear convergence for minimizing smooth and strongly convex functions.
However, strong convexity is a very strong assumption, and many fundamental models in machine learning lack this good property [Agarwal et al., 2010].

Alternative regularity conditions that are weaker than strong convexity have been revealed in the past.
For example,
gradient descent also converges linearly under Polyak-Lojasiewic inequality or Restricted secant inequality [Polyak, 1963, Zhang and Yin, 2013, Karimi et al., 2016, Guille-Escuret et al., 2022].
These two conditions can even hold for nonconvex functions.
The classical bundle method converges linearly under quadratic growth for smooth convex functions [Díaz and Grimmer, 2023]. This linear convergence result has recently been extended for general semidefinite optimization (a very broad class of conic programs) in [Ding and Grimmer, 2023, Liao et al., 2023].
While smooth and convex (but not strongly convex) problems cover a variety of applications, modern machine learning practice routinely deals with problems lacking both qualities (e.g., training nonsmooth and nonconvex deep networks). Recent studies have further identified one amenable problem
classes: weakly convex [Davis and Drusvyatskiy, 2019]. The class of problems includes all convex functions, $L$-smooth functions, certain compositions of convex functions with smooth functions, and many cost functions in modern machine learning [Drusvyatskiy and Davis, 2020, Atenas et al., 2023].

For nonsmooth problems, it is known that subdifferential error bound (or metrically subregular) or error bound for proximal gradient mapping is sufficient to ensure linear convergence of proximal algorithms [Ye et al., 2021, Drusvyatskiy and Lewis, 2018]. Very recently, [Atenas et al., 2023] also uses error bound properties to establish linear convergence for proximal-type methods.

While a range of weaker conditions ensure linear convergence of many first-order algorithms, their relationship remains unclear, especially in the class of weakly convex functions. Recently, it has been revealed that some regularity conditions (such as PL, error bound, and quadratic growth) are equivalent  [Drusvyatskiy and Lewis, 2018, Drusvyatskiy et al., 2021, Bolte et al., 2017, Karimi et al., 2016, Ye et al., 2021, Zhu et al., 2023]. However, many existing results require smooth and/or convex settings; we postpone a detailed discussion of these results in <ref> after introducing relevant notation and our main results. In this paper, we have two main contributions: 1) we first clarify the relationship among common regularity conditions in the class of weakly convex functions (<ref>); 2) we present a simple and modular proof for linear convergence of the classical proximal point method (PPM) [Rockafellar, 1976]  under these regularity conditions (<ref>). These linear convergence results hold for inexact PPM when controlling stopping criteria properly (<ref>). We remark that our convergence results require weaker conditions with simpler proofs. We expect their applications to sparse and large-scale conic optimization [Zheng et al., 2021].

The rest of this paper is structured as follows. <ref> presents a motivation and revisits linear convergence of gradient descent. <ref> presents the relationship among different regularity conditions. <ref> focus on the (inexact) PPM and establishes the sublinear and linear convergences. <ref> presents three numerical experiments, and <ref> concludes this paper. Some extra discussions and technical proofs are provided in <ref>.

We use $\RR^n$ to denote $n$-dimensional Euclidean space and $\overline{\RR}$ to denote the extended real line, i.e., $\overline{\RR}:= \RR \cup \{\pm\infty\}$. The notations $\innerproduct{\cdot}{\cdot}$ and $\|\cdot\|$ stand for standard inner product and $\ell_2$ norm in $\RR^n.$ For a closed set $S \subseteq \RR^n$, the distance of a point $x\in \RR^n$ to $S$ is defined as $\Dist(x,S) := \min_{y \in S} \|x - y\|$ and the projection of $x$ onto $S$ is denoted as $\Pi_{S}(x) = \argmin_{y\in S}\|x - y\|$. The symbol $[f \leq \nu ]:= \{x \in \RR^n \mid f(x) \leq \nu \}$ denotes the $\nu$-sublevel set of $f$.

§ MOTIVATION: LINEAR CONVERGENCE OF GRADIENT DESCENT ALGORITHMS

To motivate our discussion, consider a smooth convex optimization $\min_x \, f(x)$,
where $f: \RR^n \to {\RR}$ is a convex and $L$-smooth function, i.e., its gradient is $L$-Lipschitz  satisfying
\|\nabla f(x) - \nabla f(y)\| \leq L \|x  - y \|,\; \forall x,$ $ y \in \RR^n.
Let $S := \argmin\, f(x)$ be the set of optimal solutions. Assume $S \neq \emptyset$ and denote $f^\star = \min_x f(x)$. The standard gradient descent (GD) follows the update

\begin{equation} \label{eq:GD_iterates}
\xknext = \xk - t_k \nabla f(\xk),
\end{equation}

where $t_k >0$ is the step size. A textbook result says that when choosing a constant step size $t_k = \frac{1}{L}$,  the GD iterates converge to $f^\star$ with a sublinear rate (precisely, $f(x_k) -f^\star \leq L\Dist^2 (x_0, S)/(2k)$); see e.g., . If the function $f(x)$ is strongly convex, GD achieves a global linear convergence <cit.>.

However, the assumption of strongly convexity is too strong. It is known that some alternative weaker assumptions are already sufficient for linear convergences. We here introduce two notions: restricted secant inequality (RSI) [Zhang and Yin, 2013], and Polyak-Lojasiewicz (PL) inequality [Polyak, 1963].
A smooth function $f(x)$ satisfies RSI if there exists $\mu > 0$ such that

\begin{equation}
\begin{aligned}
\label{eq:RSI-smooth}
\innerproduct{\nabla f(x)}{x - \Pi_{S}(x)} \geq \mu \|x - \Pi_{S}(x) \|^2 = \mu \cdot \Dist^2(x,S),\; \forall x \in \RR^n,
\end{aligned}
\end{equation}

and it satisfies the PL inequality if there exists $\beta > 0$ such that

\begin{equation}
\begin{aligned}
\label{eq:PL-smooth}
\frac{1}{2}\|\nabla f(x)\|^2 \geq \beta ( f(x) - f^\star), \; \forall x \in \RR^n.
\end{aligned}
\end{equation}

Note that both RSI <ref> and PL <ref> imply that any stationary point of $f(x)$ is a global minimum. However, they do not imply the uniqueness of stationary points or convexity of the function. One can think that RSI <ref> (resp. PL <ref>) requires that the gradient $\nabla f(x)$ grows faster than that of quadratic functions when moving away from the solution set $S$ (resp. the optimal value $f^\star$). Linear convergence
of GD under the PL inequality was first proved in [Polyak, 1963], and linear convergence under RSI was discussed in  and . We summarize a simple version below.

Consider $\min_x \, f(x),$ where $f$ is $L$-smooth (possibly nonconvex) function.
Suppose its solution set $S$ is nonempty. If RSI <ref> holds with $\mu > 0$ and PL inequality <ref> holds with $\beta > 0$, then the GD algorithm <ref> with a constant stepsize $t_k = \frac{\mu}{L^2}$ has a global linear convergence rate for iterates and function values, i.e.,

\begin{align}
\Dist(\xknext,S) &\leq \omega_1 \cdot  \Dist(\xk,S), \quad \text{where} \quad  \omega_1 = \sqrt{1-\mu^2/L^2} \in (0,1),  \label{eq:linear-convergence-GD-iterates} \\
f(\xknext) -f^\star & \leq \omega_2 \cdot (f(\xk) -f^\star),\quad \text{where}  \quad
\omega_2 = (L^3 - 2\mu L \beta + \mu^2 \beta)/L^3 \in (0,1).  \label{eq:linear-convergence-GD-costs}
\end{align}

Thanks to RSI <ref> and PL inequality <ref>, the proof of <ref> is very elegant and only takes a few lines. We provide a simple proof and some additional discussions in <ref>. In particular, the RSI <ref> leads to a quick proof of <ref>, and the PL <ref> allows for a simple proof of <ref>. Indeed, it is known that for $L$-smooth convex functions, the two conditions RSI <ref> and PL <ref> are equivalent (cf. ). Some recent studies, such as [Bolte et al., 2017, Necoara et al., 2019, Zhang, 2017], have explored the relationships among different regularity conditions for linear convergences. A nice summary appeared in , but it only works in the context of $L$-smooth
functions. In this paper, we aim to characterize the relationships among different regularity conditions for nonsmooth and nonconvex functions (<ref>), and apply them to derive simple and clean proofs for linear convergences of (inexact) proximal point methods for convex (possibly nonsmooth) optimization (<ref>).

§ RELATIONSHIPS BETWEEN REGULARITY CONDITIONS

In this section, we move away from convex and smooth functions and expand our view to the class of weakly convex (potentially nonsmooth) functions. A function $f: \RR^n \to \overline{\RR}$ is called $\rho$-weakly convex if the function $f(x) + \frac{\rho}{2}\|x\|^2$ is convex. The class of weakly convex functions is very rich: it includes all convex functions, $L$-smooth functions, certain compositions of convex functions with smooth functions, and many cost functions in modern machine learning applications; we refer interested readers to [Drusvyatskiy and Davis, 2020, Atenas et al., 2023] for more details.

Let $f(x):\RR^n \to \overline{\RR}$ be a proper, closed, $\rho$-weakly convex function. For this function class, gradients may not always exist. We define the Fréchet subdifferential (see e.g., ):

\fpartial f(x) = \left \{ s \in \RR^n \mid \liminf_{y \to x }  \frac{ f(y) - f(x) -  \innerproduct{s}{y-x}}{\|y-x\|} \geq 0 \right\}.

If $f(x)$ is convex, Fréchet subdifferential $\fpartial f(x)$ is the same as the usual convex subdifferential $\fpartial f(x) = \partial f(x) =  \{s \in \RR^n \mid f(y) \geq f(x) + \innerproduct{s}{y-x}, \forall y \in \RR^n \}$; if $f(x)$ is smooth, Fréchet subdifferential reduces to the usual gradient, i.e., $ \fpartial f(x) = \{\nabla f(x)\}$.

Let the optimal solution set of $f(x)$ be $S = \argmin_x f(x)$, and we assume $S \neq \emptyset$. Let $\nu > 0$ and consider the following five regularity conditions:

* Strongly Convexity (SC): there exists a positive constant $\mus > 0$ such that

\begin{equation} \label{eq:SC}
f(x) + \langle g, y - x \rangle + \mus \cdot
\|y - x\|^2\leq f(y), \quad \forall x, y \in [f \leq f^\star + \nu] \; \text{and}\;\; g \in \fpartial f(x).
\tag{SC}
\end{equation}

* Restricted Secant Inequality (ESI): there exists a positive constant $\mur > 0$ such that

\begin{equation}
\label{eq:RSI}
\mur \cdot     \Dist^2(x,S) \leq \innerproduct{g}{x- \Pi_{S}(x)} , \quad \forall x \in [f \leq f^\star + \nu] \; \text{and}\;\; g \in \fpartial f(x).
\tag{RSI}
\end{equation}

* Error bound (EB)[Error bound is closely related to metrically subregularity at $x^\star$ for $0$ <cit.>: there exist a constant $a>0$ and a set $\mathcal{U}$ containing $x^\star$ such that $\Dist(x,(\partial f)^{-1}(0)) \leq a \cdot \Dist(0,\partial f(x)), \forall x \in \mathcal{U}$.]:
there exists a constant $\mue >0$ such that

\begin{equation}
\label{eq:EB}
\Dist (x,S) \leq \mue  \cdot  \Dist(0,\fpartial f(x)), \quad \forall x \in [f \leq f^\star + \nu].
\tag{EB}
\end{equation}

* Polyak-Łojasiewic (PL) inequality[To be consistent with the smooth case in [Karimi et al., 2016], we call the property <ref>  Polyak-Łojasiewic, which is usually used for smooth functions. The property <ref> is actually a special case of  Kurdyka-Łojasiewicz inequality $\varphi^\prime (f(x)-f^\star)\Dist(0,\fpartial f(x))\geq 1 $ with  $\varphi (s) = c s^{1/2}$ and $c > 0$.]: there exists a constant $\mup > 0$ such that

\begin{equation}\label{eq:PL}
\mup \cdot (f(x) - f^\star) \leq \Dist^2(0,\fpartial f(x)),\quad \forall x \in [ f \leq f^\star + \nu].
\tag{PL}
\end{equation}

* Quadratic Growth (QG): there exists a constant $\muq > 0$ such that

\begin{equation}
\label{eq:QG}
\muq \cdot \Dist^2(x,S) \leq f(x) - f^\star, \quad \forall x \in [f \leq f^\star + \nu].
\tag{QG}
\end{equation}

All the regularity conditions above are defined over a sublevel set $[f \leq f^\star + \nu]$. If $v = +\infty$, then they are global. In particular, <ref> imposes a quadratic lower bound for every point in the sublevel set.
On the other hand, <ref>, <ref>  and <ref> all require a certain growth of the subdifferential $\fpartial f(x)$ when moving away from its solution set $S$ or optimal value $f^\star$. It is easy to see that <ref>, <ref>  and <ref> all imply that every stationary point $0 \in \fpartial f(x)$ in the sublevel set $[f\leq f^\star + \nu]$ is a global minimum (but they do not imply the uniqueness of stationary points). Finally, <ref> shows that $f(x)$ grows at least quadratically when moving away from the solution set $S$.

Our first technical result summarizes the relationships among the five regularity conditions.

Let $f$ be a proper closed $\rho$-weakly convex function.
The following relationship holds

\begin{equation} \label{eq:relationship-weakly-convex}
\cref{eq:SC}
\rightarrow  \cref{eq:RSI} \rightarrow
\cref{eq:EB}   \equiv \cref{eq:PL} \rightarrow \cref{eq:QG}.
\end{equation}

Furthermore, if any of the following two conditions is satisfied

* $f(x)$ is convex (i.e., $\rho = 0$),

* the <ref> coefficient satisfies $\muq > \frac{\rho}{2}$,

then the following equivalence holds

\begin{equation} \label{eq:relationship-convex}
\cref{eq:RSI}\equiv \cref{eq:EB}   \equiv \cref{eq:PL}  \equiv \cref{eq:QG}.
\end{equation}

<ref> includes  and  as a special case, in which only $L$-smooth functions are considered. It is easy to see that all $L$-smooth functions are also $L$-weakly convex.
Even for smooth functions,  <ref> is more general than  in the sense that 1) we require no Lipschitz constant $L$ for gradients to ensure the equivalency among <ref>, <ref>, and <ref> in the convex case;
2) the condition $\muq > \rho/2$ is new and does not mean that $f(x)$ is convex (see <ref> for an example).

Our proof details for <ref> are presented in <ref>. The proof of <ref> relies heavily on the notion of slope defined in [Drusvyatskiy et al., 2021], Ekeland’s variational principle [Ekeland, 1974], and a technical result in .
Alternative proofs based subgradient flows [Bolte et al., 2017] are also possible. Indeed, one key step in the proof of  is based on gradient flows for smooth functions, which is as a special case of subgradient flows for nonsmooth cases.

The regularity conditions <ref>, <ref> and <ref> have been discussed for different function classes in the literature. For the smooth case, we refer to   for a nice summary. For nonsmooth convex functions, the equivalency between <ref> and <ref> has been recognized in  and , and the equivalency between <ref> and <ref> is established in . Thus, <ref>, <ref>, and <ref> are equivalent for the class of nonsmooth convex functions <cit.>; also see [Zhu et al., 2023] for a recent discussion.
Our <ref> extends these results to $\rho$-weakly convex functions. The most closely related work is [Drusvyatskiy et al., 2021] which focuses on nonsmooth optimization using taylor-like models. Indeed, we specialize the proof in  in our setting and prove the relationship in <ref> directly using the slope technique.
We note that the implication from <ref> to <ref>/<ref> is not true in general. Yet, with one of the two conditions in <ref>, all four regularity conditions <ref>, <ref>,  <ref> and <ref> are equivalent.

We conclude this section with a few simple instances. In principle, all the five properties in <ref> are generalizations of quadratic functions to non-quadratic, nonconvex, and even nonsmooth cases. For illustration, let us first consider the simplest quadratic function $f(x) = x^2$, which is convex and differentiable. It is clear that  $\fpartial f(x) = \{2x\}$ and $S = \{0\}$. It is also immediate to verify that <ref> holds with $0 < \mus \leq 1$, <ref> holds with $0 < \mur \leq  2$, <ref> holds with $\mue  \geq  1/2$, <ref> holds with $0<\mup \leq 4$, and <ref> holds with $0<\muq \leq 1$. Consider another simple convex function $f(x) = x^2, \text{if}~|x|\leq 1,$ and $f(x) =\frac{1}{2}x^4 + \frac{1}{2}$ otherwise. All the five properties hold for this function, but it is not $L$-smooth globally. Let us move away from convex functions, and consider $f(x) = x^2 + 6 \sin^2(x)$. It is clear that this function satisfies <ref> globally, however, there exist suboptimal stationary points and consequently <ref> and <ref> do not hold globally. Thus, the relationship <ref> is strict, and <ref> is more general than the other conditions. Finally, we consider a $\rho$-weakly convex function with a QG constant $\muq > \frac{\rho}{2}$: $f(x) = -x^2+1$ if $-1  <  x < -0.5$, and $f(x) = 3(x+1)^2$ otherwise.
The function is not convex but $2$-weakly convex with the QG constant $\muq = 3 > 2/2 = 1$. In this case, <ref> guarantees that <ref>, <ref> and <ref> also hold (see <ref> and  <ref> for additional details in the appendix).

§ PROXIMAL POINT METHOD FOR CONVEX OPTIMIZATION

In this section, we will utilize the regularity conditions in <ref> to derive fast linear convergence guarantees of the classical proximal point method (PPM) [Rockafellar, 1976] for convex (potentially nonsmooth) optimization. PPM is a conceptually simple algorithm, which has been historically used for guiding algorithm design and analysis, such as proximal bundle methods [Lemarechal et al., 1981], augmented Lagrangian methods [Rockafellar, 1976]. It has recently found increasing applications in modern machine learning; see [Drusvyatskiy, 2017].

§.§ Proximal point method

Consider the optimization problem

\begin{equation}
\label{eq:general-minimization}
f^\star = \min_x \; f(x), \vspace{-1mm}
\end{equation}

where $f: \RR^n \to \overline{\RR}$ is a proper closed convex function.  Note that <ref> is also an abstract model for constrained optimization since given a closed convex set $X$, we can define $\bar{f}(x) = f(x)$ if $x \in X$, otherwise $\bar{f}(x) = \infty$. Let $S = \argmin_x \, f(x)$.
We define the proximal mapping as

\begin{equation} \label{eq:PPM-subproblem}
\text{prox}_{\alpha,f}(x):=\argmin_{x \in \mathbb{R}^n}\; f(x) + \frac{1}{2\alpha} \left\|x - \xk\right\|^2,
\end{equation}

where $\alpha > 0$.
Starting with any initial point $x_0$, the PPM generates a sequence of points as follows

\begin{equation}
\label{eq:PPM}
\xknext =   \mathrm{prox}_{c_k,f}(\xk), \quad k = 0, 1, 2, \ldots
\end{equation}

where $\{c_k\}_{k\geq 0}$ is a sequence of positive real numbers. The quadratic term in <ref> makes the objective function strongly convex and always admits a unique solution. The iterates <ref> are thus well-defined.

The convergence of PPM <ref> for (nonsmooth) convex optimization has been studied since 1970s [Rockafellar, 1976]. The sublinear convergence is relatively easy to establish, and many different assumptions exist for linear convergences of <ref>; see [Rockafellar, 1976, Luque, 1984, Leventhal, 2009, Cui et al., 2016, Drusvyatskiy and Lewis, 2018]. However, as we will highlight later, some assumptions are restrictive and the corresponding proofs are sophisticated and nontransparent. We aim to provide simple and clean proofs under the general regularity conditions in <ref>.

§.§ (Sub)linear convergences of PPM

Under a very general setup, the PPM <ref> converges at a sublinear rate for cost value gaps, and the iterates converge asymptotically, as summarized in <ref>. This result is classical <cit.>, and a new bound with a constant 4 is also available in  using the performance estimation technique.

Let $f\!:\! \RR^n \!\to \! \overline{\RR}$ be a proper closed convex function, and $S\neq \emptyset$. Then, the iterates <ref> with a positive sequence $\{c_k\}_{k\geq 0}$ satisfy

\begin{equation} \label{eq:PPM-sublinear-convergence-cost}
f(\xk) - f^\star \leq  \Dist^2(x_0,S)/(2\textstyle \sum_{t=0}^{k-1}c_t).
\end{equation}

If we further have $\lim_{k \to \infty }\sum_{t=0}^{k-1}c_t = \infty$, the iterates converge to an optimal solution $ \bar{x} $ asymptotically, i.e., $\lim_{k \to \infty} x_k = \bar{x}$, where $\bar{x} \in S$.

The proof of <ref> is immediate from a telescope sum via the following one-step improvement:

\begin{equation}
2c_k( f(\xknext)-  f(x^\star)) \leq   \|\xk - x^\star \|^2 - \|\xknext - x^\star \|^2, \qquad \forall c_k >0, x^\star \in S. \label{eq:PPM-distant-nonincreasing}
\end{equation}

This fact <ref> is not difficult to establish. For completeness, we provide proof details in <ref>. Note that choosing any constant step size $c_k = c > 0$ in <ref> directly implies the common sublinear rate $\mathcal{O}(1/k)$. In <ref>, $f(x)$ does not need to be $L$-smooth, and it can also be nonsmooth. Thus, the guarantees in <ref> are much stronger than those by (sub)gradient methods. This is because the proximal mapping <ref> is a stronger oracle than simple (sub)gradient updates.

Similar to GD in <ref>,
when $f(x)$ satisfies additional regularity conditions, the PPM enjoys linear convergence. Our next main technical result  establishes linear convergences of the PPM under the general regularity conditions in <ref>.

Let $f\!:\! \RR^n \!\to \! \overline{\RR}$ be a proper closed convex function, and $S \neq \emptyset$.
Suppose $f$ satisfies <ref> (or  <ref>, <ref>, <ref>) over the sublevel set $[f \leq f^\star + \nu]$.
Then, for all $k \geq k_0$ steps, the iterates <ref> with a positive sequence $\{c_k\}_{k\geq 0}$ enjoy  linear convergence rates, i.e.,

\begin{align}
f(\xknext) - f^\star & \leq  \omega_k \cdot (f(\xk) - f^\star), \label{eq:cost-gap-linear}\\
\Dist(\xknext,S) & \leq \theta_k \cdot \Dist(\xk,S), \label{eq:iterate-linear}
\end{align}

where the constants are

\begin{equation*}
\omega_k = \frac{2}{2+\mu_{\mathrm{p}} c_k }  < 1, \quad \theta_{k} =\min \left \{ \frac{ 1}{\sqrt{ 2c_k\mu_{\mathrm{q}} +1} } , \frac{1}{\sqrt{\mue^2/c_k^2 + 1}} \right \}< 1, \quad k_0 = \frac{\Dist^2(x^0,S)}{2\nu \min_{k\geq 0}c_k }.
\end{equation*}

The sublinear convergence in <ref> ensures that the iterate $x_k$ reaches $[f\leq f^\star + \nu]$ after at most $k_0$ iterations. Once $\xk$ is within  $[f\leq f^\star + \nu]$, all the properties <ref>, <ref>, <ref>, and <ref> are equivalent by <ref>.
For the analysis below, we assume $\xk \in  [f\leq f^\star + \nu]$.

We next show that <ref> gives a simple proof of <ref>, and <ref> together with <ref> leads to a clean proof of <ref>. Recall that the optimality condition of <ref> directly implies

\begin{equation}
- (\xknext - \xk)/c_k  \in \partial f(\xknext).\label{eq:optimality-condition}
\end{equation}

Then, the following inequalities hold

\begin{align} \label{eq:PL-cost-gap}
f(\xk) - f(\xknext) \overset{(a)}{\geq} \frac{1}{2c_k}\|\xknext - \xk\|^2
\overset{(b)}{\geq} \frac{c_k}{2} \Dist^2(0,\partial f(\xknext))
\overset{(c)}{\geq} c_k \frac{\mup}{2} (f(\xknext) - f^\star),
\end{align}

where $(a)$ applies the fact that $\xk$ is a suboptimal solution to <ref>, $(b)$ comes from the optimality <ref>, and $(c)$ applies <ref>.
Re-arranging and subtracting $f^*$ from both sides of <ref> lead to the desired linear convergence result in <ref>.

We next use <ref> to prove <ref> with coefficient $\theta_k \leq 1/\sqrt{2c_k\mu_{\mathrm{q}} +1}$.
By definition, we have

$$f(\Pi_{S}(\xk)) = f^\star, \quad  \text{and} \quad   \|  \Pi_{S}(\xk) - \xk\|^2 = \Dist^2(\xk,S).$$

Since $f(x) + \frac{1}{2c_k} \|x- \xk\|^2$ is  $1/c_k$ strongly convex, its first-order lower bound at $\xknext$ is

\begin{equation}
\label{eq:first-order-lower-bound}
\begin{aligned}
& f^* +\frac{1}{2c_k} \|  \Pi_{S}(\xk) - \xk\|^2  = f( \Pi_{S}(\xk) )  +\frac{1}{2c_k} \Dist^2(\xk,S) \\
\geq ~&  f(\xknext) + \frac{1}{2c_k} \|\xknext- \xk\|^2 + \langle 0, \Pi_{S}(\xk) -\xknext \rangle + \frac{1}{2c_k} \|\Pi_{S}(\xk) -\xknext \|^2,
\end{aligned}
\end{equation}

where we also applied the fact that  $\xknext$ minimizes <ref> so 0 is a subgradient. From <ref>, we drop the positive term $\|\xknext- \xk\|^2$ and use the fact that $\|\Pi_{S}(\xk) -\xknext \| \geq \Dist(\xknext,S)$, leading to

\begin{equation*}
f^\star -  f(\xknext) +\frac{1}{2c_k} \Dist^2(\xk,S) \geq \frac{1}{2c_k} \Dist^2(\xknext,S).
\end{equation*}

Combining this inequality with <ref> and simple re-arranging leads to the desired linear rate

\begin{equation*}
\Dist^2(\xknext,S) \leq 1/\sqrt{2c_k\muq + 1} \cdot \Dist^2(\xk,S).
\end{equation*}

Simple arguments based on <ref> can establish <ref> with coefficient $\theta_k \leq 1/{\sqrt{\mue^2/c_k^2 + 1}}$. We provide some details in <ref>. This completes the proof.

Two nice features of <ref> are 1) the simplicity of its proofs and 2) the generality of its conditions. Indeed, the proof of <ref> is very simple via <ref>, while the proof of <ref> is also clean via  <ref> and <ref>, which are simpler than typical proofs. In addition, the regularity conditions are weaker than [Rockafellar, 1976, Luque, 1984].
Linear convergence for $\Dist(\xk,S)$ was first established in [Rockafellar, 1976] with one restrictive assumptions:
the inverse of the subdifferential $(\partial f)^{-1}$ is locally Lipschitz at $0$. This assumption in turn implies the optimal solution is unique, i.e., $S$ is a singleton.  The uniqueness assumption is lifted in [Luque, 1984], which allows an unbounded solution set. More recently, this assumption is further relaxed as $\partial f$ being metrically subregular in [Cui et al., 2016, Leventhal, 2009].

It is known that for convex functions, $\partial f$ is metrically subregular if and only if $f(x)$ satisfies quadratic growth (cf. <ref>). Indeed, our proof in <ref> is based on quadratic growth, which is a more intuitive, geometric
property. Our main idea in the proof above is motivated by a recent result for the linear convergence of the spectral bundle method in [Ding and Grimmer, 2023].

§ INEXACT PROXIMAL POINT METHOD (IPPM) AND ITS CONVERGENCES

In <ref>, each subproblem <ref> is solved exactly. This may not be practical since one still needs an iterative solver to solve <ref>, where stopping criteria naturally introduce errors.

We here discuss an inexact version of PPM (iPPM, Rockafellar, 1976) where the subproblem <ref> is solved inexactly. The regularity conditions in <ref> also allow us to establish linear convergences of iPPM.

§.§ iPPM and stopping criteria

We replace the exact update <ref>  with an inexact update

\begin{equation}
\label{eq:PPM-inexact}
\xknext \approx \text{prox}_{c_k,f}(\xk).
\end{equation}

Two classical criteria suggested in Rockafellar's seminal work [Rockafellar, 1976]

\begin{align}
\|\xknext - \text{prox}_{c_k,f}(\xk)\|& \leq \epsilon_k, \quad \textstyle \sum_{k=0}^\infty \epsilon_k < \infty,
\tag{A} \label{eq:criterion A}\\
\|\xknext - \text{prox}_{c_k,f}(\xk)\|& \leq \delta_k \| \xknext - \xk \|, \quad \textstyle \sum_{k=0}^\infty \delta_k < \infty.
\tag{B}
\label{eq:criterion B}
\end{align}

The inexact update <ref> with <ref> or <ref> is called iPPM. The two criteria are not directly implementable as the value of $\text{prox}_{c_k,f}(\xk)$ is unknown.
As discussed in , two implementable alternatives that imply <ref>, respectively, are

\begin{align}
\Dist(0,H_k(\xknext)) &\leq \epsilon_k/c_k, \quad \textstyle \sum_{k=0}^\infty \epsilon_k < \infty,
\tag{$\text{A}^{\prime}$} \label{eq:criterion Ap}\\
\Dist(0,H_k(\xknext))& \leq  (\delta_k/c_k) \|\xknext - \xk\|, \quad \textstyle \sum_{k=0}^\infty \delta_k < \infty,
\tag{$\text{B}^{\prime}$} \label{eq:criterion Bp}
\end{align}

where $H_k(x) = \partial f(x) + (x-\xk)/c_k$ is the subdifferential of $f(x) + \|x-\xk\|^2/(2c_k)$ (since $f(x)$ is convex by assumption).
Note that <ref> only require the inexact update $\xknext$ to stay close enough to  $\text{prox}_{c_k,f}(\xk)$ with respect to the Euclidean distance, but they do not require the inexact update $\xknext$ to be within the domain of $f$, i.e., $f(\xknext)$ might be infinity.
However, the stopping criteria
(<ref>) and
(<ref>) require that $x_{k+1}$ is in the domain of $f$.

§.§ (Sub)linear convergences of iPPM

The seminal work [Rockafellar, 1976] has established the asymptotic convergence of iterates for iPPM under a general setup. We state the results below whose proof is  technically invovled.

Let $f\!:\! \RR^n \!\to \! \overline{\RR}$ be a proper closed convex function. Consider any sequence $\{ \xk \}_{k\geq 0 }$ generated by <ref> under <ref> with a positive sequence $\{c_k\}_{k\geq 0 }$ bounded away from zero. Then, we have 1) the sequence $\{\xk\}_{k\geq 0 }$ is bounded if and only if there exists a solution to $0 \in \partial f(x)$, i.e., $S \neq \emptyset$;
2) if $S \neq \emptyset$, the whole sequence $\{\xk\}_{k\geq 0 }$
converges to an optimal point $x_{\infty} \in S$ asymptotically, i.e., $\lim x_k = x_\infty$.

We next establish a sublinear convergence of iPPM for cost value gaps. Our simple proof is based on the boundedness of the iterates from <ref> and a recent idea in . We provide some details in <ref>.

Let $f\!:\! \RR^n \!\to \! \overline{\RR}$ be a proper closed convex function,  and $S \neq \emptyset$.
The iterates <ref> under <ref> with a positive sequence $\{c_k\}_{k\geq 0}$ bounded away from zero
converges to  $x^\star \in S$ asymptotically, and the cost value gaps converge as

\begin{align*}
\min_{j = 0,\ldots,k}f(x_j) - f^\star \leq \frac{ \Dist^2(x_0,S) + 2D\sum_{j=0}^{k-1} \epsilon_j}{2\sum_{j=0}^{k-1}c_j} ,
\end{align*}

where $D$ is the diameter of iterates $\{\xk\}$ which is bounded.

Note that <ref> can be viewed as the convergence counterpart for iPPM of <ref> with two major differences: 1) <ref> deals with the best iterate,  unlike the last iterate in <ref> (the guarantee for the average $\bar{x}_k = \frac{1}{k} \sum_{j=1}^{k} x_j $ or weighted average
$\Tilde{x}_k = ({\sum_{j=0}^{k-1} c_j x_{j+1}})/({\sum_{j=0}^{k-1} c_j})$
is also straightforward; see <ref> in the appendix); 2) the convergence of cost values in <ref> relies on the boundedness of iterates in <ref> whose proof is technically involved from , while the convergence of iterates of exact PPM is established from the sublinear convergence of cost values in <ref>.

We now introduce our final technical result, which is the counterpart of <ref>.

Let $f\!:\! \RR^n \!\to \! \overline{\RR}$ be a proper closed convex function,  and $S \neq \emptyset$.
Suppose $f$ satisfies <ref> (or <ref>, <ref>) over the sublevel set $[f \leq f^\star + \nu]$. Let $\{\xk\}$ be any sequence generated by iPPM <ref> under <ref> with parameters $\{c_k\}_{k \geq 0}$ bounded away from zero.
There exists a nonnegative $\theta_k < 1$ and a large $\bar{k} >0$ such that for all $k \geq \bar{k}$, we have

\begin{equation}
\label{eq:iPPM-linear-convergence}
\Dist(\xknext,S)  \leq \hat{\theta}_k \Dist(\xk,S),
\hat{\theta}_k = \frac{ \theta_k +2\delta_k}{1-\delta_k}~\text{and}~ \lim_{k \to \infty} \hat{\theta}_k = \theta_k < 1.
\end{equation}

Thanks to <ref>, the asymptotic convergence of $\{\xk \}$ is guaranteed by <ref>. Thus, there exists a $k_1$ such that the iterate enters the QG region, i.e., <ref> holds. <ref> implies

\begin{equation}
\label{eq:inequality-QG-iPPM}
\Dist(\text{prox}_{c_k,f}(\xk),S) \leq  \theta_{k} \Dist(\xk,S),\; \forall k \geq k_1,
\end{equation}

where $\theta_{k} = 1/\sqrt{2c_k \mu_{\mathrm{q}} +1}  < 1$.
On the other hand, thanks to <ref>, there exists a $k_2 > 0$ such that

\begin{equation}
\label{eq:inexact-PPM-distance-error}
(1-\delta_k ) \Dist(\xknext,S) \leq 2\delta_k \Dist(\xk,S) + \Dist(\text{prox}_{c_k,f}(\xk),S), \; \forall k \geq  k_2.
\end{equation}

This inequality <ref> quantifies the quality between the next iterate $\xknext$ and the true proximal point $\text{prox}_{c_k, f}(\xk)$, first appeared in . We provide some details of <ref> in <ref>.
Choosing $k \geq \bar{k} = \max \{k_1,k_2\} $ and combining <ref> with <ref> directly leads to the desired rate <ref>. This completes the proof.

In <ref>, criterion <ref> is to guarantee that the iterates can reach the QG region (cf. the asymptotic convergence from <ref>). If  <ref> holds globally (i.e., $\nu =\infty $),
the same linear convergence result holds with only <ref>. Note that the convergence proof in <ref> is very modular. Indeed, thanks to the regularity conditions (i.e., <ref>) in <ref>, our proof is simpler and less conservative than typical proofs in the literature; see the discussions at the end of <ref>.

§ APPLICATIONS

In this section, we consider three different applications of convex optimization in machine learning and signal processing: linear support vector machine (SVM) ([Zhang and Lin, 2015]), lasso ([Tibshirani, 1996]), and elastic-net ([Zou and Hastie, 2005]) respectively. For each application, we run the PPM on three different data sets. These problems satisfy the regularity conditions in <ref>. The numerical results are shown in <ref>, which confirms the fast linear convergence of the PPM.
The details of the data set and the choices of parameters can be found in <ref>.

Linear convergences of cost value gaps for linear SVM (left), lasso (middle), and elastic-net (right).

§ CONCLUSION

In this paper, we have established the relationship between different favorite regularity conditions under the class of $\rho$-weakly convex functions. This result is beneficial in analysis and design of various first-order algorithm. We have also presented simple and clear proofs for the (inexact) PPM which makes the analysis of the (inexact) PPM more accessible to new readers. We believe these results will facilitate algorithm development in nonsmooth optimization. We are particularly interested in further applications in large-scale conic optimization [Zheng et al., 2021].

This work is supported in part by NSF ECCS-2154650 and in part by NSF CMMI-2320697.

[Agarwal et al., 2010]
Alekh Agarwal, Sahand Negahban, and Martin J Wainwright.
Fast global convergence rates of gradient methods for high-dimensional statistical recovery.
Advances in Neural Information Processing Systems, 23, 2010.

[ApS, 2019]
MOSEK ApS.
MOSEK Optimization Toolbox for MATLAB 10.1.20, 2019.
URL <https://docs.mosek.com/latest/toolbox/index.html>.

[Artacho and Geoffroy, 2008]
FJ Aragón Artacho and Michel H Geoffroy.
Characterization of metric regularity of subdifferentials.
Journal of Convex Analysis, 150 (2):0 365, 2008.

[Atenas et al., 2023]
Felipe Atenas, Claudia Sagastizábal, Paulo JS Silva, and Mikhail Solodov.
A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle methods.
SIAM Journal on Optimization, 330 (1):0 89–115, 2023.

[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:0 471–507, 2017.

[Bubeck et al., 2015]
Sébastien Bubeck et al.
Convex optimization: Algorithms and complexity.
Foundations and Trends® in Machine Learning, 80 (3-4):0 231–357, 2015.

[Chang and Lin, 2011]
Chih-Chung Chang and Chih-Jen Lin.
Libsvm: a library for support vector machines.
ACM transactions on intelligent systems and technology (TIST), 20 (3):0 1–27, 2011.

[Cui et al., 2016]
Ying Cui, Defeng Sun, and Kim-Chuan Toh.
On the asymptotic superlinear convergence of the augmented lagrangian method for semidefinite programming with multiple solutions.
arXiv preprint arXiv:1610.00875, 2016.

[Davis and Drusvyatskiy, 2019]
Damek Davis and Dmitriy Drusvyatskiy.
Stochastic model-based minimization of weakly convex functions.
SIAM Journal on Optimization, 290 (1):0 207–239, 2019.

[Díaz and Grimmer, 2023]
Mateo Díaz and Benjamin Grimmer.
Optimal convergence rates for the proximal bundle method.
SIAM Journal on Optimization, 330 (2):0 424–454, 2023.

[Ding and Grimmer, 2023]
Lijun Ding and Benjamin Grimmer.
Revisiting spectral bundle methods: Primal-dual (sub) linear convergence rates.
SIAM Journal on Optimization, 330 (2):0 1305–1332, 2023.

[Drusvyatskiy and Davis, 2020]
D Drusvyatskiy and D Davis.
Subgradient methods under weak convexity and tame geometry.
SIAG/OPT Views and News, 28:0 1–10, 2020.

[Drusvyatskiy, 2013]
Dmitriy Drusvyatskiy.
Slope and geometry in variational mathematics.

[Drusvyatskiy, 2017]
Dmitriy Drusvyatskiy.
The proximal point method revisited.
arXiv preprint arXiv:1712.06038, 2017.

[Drusvyatskiy and Lewis, 2018]
Dmitriy Drusvyatskiy and Adrian S Lewis.
Error bounds, quadratic growth, and linear convergence of proximal methods.
Mathematics of Operations Research, 430 (3):0 919–948, 2018.

[Drusvyatskiy et al., 2015]
Dmitriy Drusvyatskiy, Alexander D Ioffe, and Adrian S Lewis.
Curves of descent.
SIAM Journal on Control and Optimization, 530 (1):0 114–138, 2015.

[Drusvyatskiy et al., 2021]
Dmitriy Drusvyatskiy, Alexander D Ioffe, and Adrian S Lewis.
Nonsmooth optimization using taylor-like models: error bounds, convergence, and termination criteria.
Mathematical Programming, 185:0 357–383, 2021.

[Ekeland, 1974]
Ivar Ekeland.
On the variational principle.
Journal of Mathematical Analysis and Applications, 470 (2):0 324–353, 1974.

[Guille-Escuret et al., 2022]
Charles Guille-Escuret, Adam Ibrahim, Baptiste Goujaud, and Ioannis Mitliagkas.
Gradient descent is optimal under lower restricted secant inequality and upper error bound.
Advances in Neural Information Processing Systems, 35:0 24893–24904, 2022.

[Güler, 1991]
Osman Güler.
On the convergence of the proximal point algorithm for convex minimization.
SIAM journal on control and optimization, 290 (2):0 403–419, 1991.

[Ioffe, 2017]
Alexander D Ioffe.
Variational analysis of regular mappings.
Springer Monographs in Mathematics. Springer, Cham, 2017.

[Karimi et al., 2016]
Hamed Karimi, Julie Nutini, and Mark Schmidt.
Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.
In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795–811. Springer, 2016.

[Lemarechal et al., 1981]
Claude Lemarechal, Jean-Jacques Strodiot, and André Bihain.
On a bundle algorithm for nonsmooth optimization.
In Nonlinear programming 4, pages 245–282. Elsevier, 1981.

[Leventhal, 2009]
D Leventhal.
Metric subregularity and the proximal point method.
Journal of Mathematical Analysis and Applications, 3600 (2):0 681–688, 2009.

[Li et al., 2020]
Jiajin Li, Anthony Man-Cho So, and Wing-Kin Ma.
Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth functions.
IEEE Signal Processing Magazine, 370 (5):0 18–31, 2020.

[Liao et al., 2023]
Feng-Yi Liao, Lijun Ding, and Yang Zheng.
An overview and comparison of spectral bundle methods for primal and dual semidefinite programs.
arXiv preprint arXiv:2307.07651, 2023.

[Löfberg, 2004]
J. Löfberg.
Yalmip : A toolbox for modeling and optimization in matlab.
In In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.

[Lu and Yang, 2023]
Haihao Lu and Jinwen Yang.
On a unified and simplified proof for the ergodic convergence rates of ppm, pdhg and admm.
arXiv preprint arXiv:2305.02165, 2023.

[Luque, 1984]
Fernando Javier Luque.
Asymptotic convergence analysis of the proximal point algorithm.
SIAM Journal on Control and Optimization, 220 (2):0 277–293, 1984.

[Necoara et al., 2019]
Ion Necoara, Yu Nesterov, and Francois Glineur.
Linear convergence of first order methods for non-strongly convex optimization.
Mathematical Programming, 175:0 69–107, 2019.

[Nesterov, 2018]
Yurii Nesterov.
Lectures on convex optimization, volume 137.
Springer, 2018.

[Penot, 2013]
Jean-Paul Penot.
Calculus without derivatives, volume 266.
Springer, 2013.

[Polyak, 1963]
Boris T Polyak.
Gradient methods for the minimisation of functionals.
USSR Computational Mathematics and Mathematical Physics, 30 (4):0 864–878, 1963.

[Rockafellar, 1976]
R Tyrrell Rockafellar.
Augmented lagrangians and applications of the proximal point algorithm in convex programming.
Mathematics of operations research, 10 (2):0 97–116, 1976a.

[Rockafellar, 1976]
R Tyrrell Rockafellar.
Monotone operators and the proximal point algorithm.
SIAM journal on control and optimization, 140 (5):0 877–898, 1976b.

[Rockafellar, 2021]
R Tyrrell Rockafellar.
Characterizing firm nonexpansiveness of prox mappings both locally and globally.
Journal of Nonlinear and convex Analysis, 220 (5), 2021.

[Taylor et al., 2017]
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, 270 (3):0 1283–1313, 2017.

[Tibshirani, 1996]
Robert Tibshirani.
Regression shrinkage and selection via the lasso.
Journal of the Royal Statistical Society Series B: Statistical Methodology, 580 (1):0 267–288, 1996.

[Ye et al., 2021]
Jane J Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang.
Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems.
Set-Valued and Variational Analysis, pages 1–35, 2021.

[Zhang, 2017]
Hui Zhang.
The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth.
Optimization Letters, 11:0 817–833, 2017.

[Zhang, 2020]
Hui Zhang.
New analysis of linear convergence of gradient-type methods via unifying error bound conditions.
Mathematical Programming, 1800 (1-2):0 371–416, 2020.

[Zhang and Yin, 2013]
Hui Zhang and Wotao Yin.
Gradient methods for convex minimization: better rates under weaker conditions.
arXiv preprint arXiv:1303.4645, 2013.

[Zhang and Lin, 2015]
Yuchen Zhang and Xiao Lin.
Stochastic primal-dual coordinate method for regularized empirical risk minimization.
In International Conference on Machine Learning, pages 353–361. PMLR, 2015.

[Zheng et al., 2021]
Yang Zheng, Giovanni Fantuzzi, and Antonis Papachristodoulou.
Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization.
Annual Reviews in Control, 52:0 243–279, 2021.

[Zhu et al., 2023]
Daoli Zhu, Lei Zhao, and Shuzhong Zhang.
A unified analysis for the subgradient methods minimizing composite nonconvex, nonsmooth and non-lipschitz functions.
arXiv preprint arXiv:2308.16362, 2023.

[Zou and Hastie, 2005]
Hui Zou and Trevor Hastie.
Regularization and variable selection via the elastic net.
Journal of the Royal Statistical Society Series B: Statistical Methodology, 670 (2):0 301–320, 2005.

§ SUBDIFFERENTIAL CHARACTERIZATION OF WEAKLY CONVEX FUNCTIONS

For self-completeness, we review a useful subdifferential characterization of weakly convex functions. Recall that $\overline{\RR}$ denotes the extended real line, i.e., $\overline{\RR}:= \RR \cup \{\pm \infty\}$.

We say that a function $f: \RR^n \to \overline{\RR}$ is proper if $f(x) < \infty$ for at least one $x \in \RR^n$ and $-\infty < f(x)$ for all $x \in \RR^n.$     We say that a function $f: \RR^n \to \overline{\RR}$ is closed if the epigraph $\text{epi}f :\{ (x,\alpha) \in \RR^n \times \RR \mid f(x)\leq \alpha \}$ is closed.

For a closed function $f:\RR^n \to \overline{\RR}$, we define the Fréchet subdifferential as

\fpartial f(x) = \left \{ s \in \RR^n \mid \liminf_{y \to x }  \frac{ f(y) - f(x) -  \innerproduct{s}{y-x}}{\|y-x\|} \geq 0 \right\}.

A function $f:\RR^n \to \overline{\RR}$ is called $\rho$-weakly convex if $f(x) + \frac{\rho}{2}\|x\|^2$ is convex.

For this class of $\rho$-weakly convex functions, the Fréchet subdifferential always exists for any point $x \in \RR^n$. This is because the Fréchet subdifferential is the same as the Clarke subdifferential for $\rho$-weakly convex functions and the Clarke subdifferential always exists <cit.>.
The class of $\rho$-weakly convex functions also has the following nice characterizations. These characterizations offer favorable properties for  $\rho$-weakly convex functions, which can be viewed as extensions from strongly convex functions.

The following statements are equivalent for any closed function $f(x)$.

* The function $f$ is $\rho$-weakly convex.

* The approximate secant inequality holds:

\begin{equation*}
f(\lambda x + (1-\lambda )y )\leq \lambda f(x) + (1-\lambda) f(y) +\frac{\rho \lambda (1-\lambda)}{2}\|x-y\|^2, \quad \forall x,y \in \RR^n, \lambda \in [0,1].
\end{equation*}

* The subgradient inequality holds:

\begin{equation} \label{eq:subdifferential-inequality-weakly-convex}
f(y) \geq f(x) + \innerproduct{v}{y-x} - \frac{\rho}{2}\|y-x\|^2, \quad \forall x,y \in \RR^n, v \in \fpartial f(x).
\end{equation}

* The subdifferential map is hypomonotone:

\begin{equation*}
\innerproduct{v-w}{x-y} \geq - \rho \|x-y\|^2, \quad \forall x, y \in \RR^n, v \in \fpartial f(x),~ \text{and}~w \in \fpartial f(y).
\end{equation*}

If $f$ is $\mathcal{C}^2$-smooth, then the four properties above are all equivalent to

\begin{equation*}
\nabla^2 f(x)  \succeq -\rho I, \forall x \in \RR^n.
\end{equation*}

The subgradient inequality <ref> is particularly useful in our proof for <ref> in <ref>. We will repeatedly apply <ref> to establish the connection between subdifferential and cost value gap.

§ PROOF OF <REF>

Recall that we say a differentialable function $f:\RR^n \to \RR$ is $L$-smooth if it satisfies

\begin{equation}
\label{eq:L-smooth-definion}
\|\nabla f(x) - \nabla f(y)\| \leq L \|x  - y \|,\;\; \forall x, y \in \RR^n.
\end{equation}

A differentialable $L$-smooth function $f$ also satisfy the following useful inequalities

\begin{equation}
\label{eq:Lispchitz-upper}
f(y) \leq f(x) + \innerproduct{\nabla f(x)}{y-x} +\frac{L}{2}\|y-x\|^2, \;\; \forall x, y \in \RR^n.
\end{equation}

Assume that RSI <ref> holds with constant $\mu > 0$. We first note that $\mu \leq L$. Indeed, this can be seen from the following fact: let $x \in \RR^n, x \notin S$, we have

\begin{align*}
\mu \|x-\Pi_{S}(x)\|^2 & \leq \innerproduct{\nabla f(x)}{x-\Pi_{S}(x)} =\innerproduct{\nabla f(x) - \nabla f(\Pi_{S}(x))}{x-\Pi_{S}(x)}  \\
& \leq L\|x-\Pi_{S}(x)\|^2,
\end{align*}

where the first inequality uses RSI <ref>, and the last inequality applies Cauchy-Schwarz and <ref>.

Recall that for a closed set $S \subseteq \RR^n$, we denote the distance of a point $x\in \RR^n$ to $S$ as $\Dist(x,S) := \min_{y \in S} \|x - y\|$ and the projection of $x$ onto $S$ as $\Pi_{S}(x) = \argmin_{y\in S}\|x - y\|$. In the following, $S$ denotes the set of minimizers of $f(x)$.

We first the following inequality in terms of
the distance to the solution set

\begin{align}
\Dist^2(\xknext,S) & \leq \|\xk - t_k \nabla f(\xk) - \Pi_{S}(\xk)\|^2 \label{eq:iterate-decrease-a} \\
& = \|\xk - \Pi_{S}(\xk)\|^2- 2t_k \innerproduct{\nabla f(\xk)}{\xk - \Pi_{S}(\xk)} + t_k^2\|\nabla f(\xk)\|^2 \label{eq:iterate-decrease-b} \\
& \leq \Dist^2(\xk,S) - 2 t_k \mu \Dist^2(\xk,S) + t_k^2 L^2 \Dist^2(\xk,S)  \label{eq:iterate-decrease-c}\\
& = \left(1- 2 t_k \mu + t_k^2 L^2\right)\Dist^2(\xk,S), \label{eq:iterate-decrease-d}
\end{align}

where <ref> plugs in definition of $\xknext$ and uses the fact $\Dist(\xknext,S) = \|\xknext - \Pi_{S}(\xknext)\| \leq \|\xknext - \Pi_{S}(\xk)\| $, <ref> simply expends the square, and  <ref> uses <ref> to upper bound the inner product term and applies the $L$-smoothness inequality <ref> to $\|\nabla f(\xk)\| = \|\nabla f(\xk) -  \nabla f(\Pi_{S}(\xk)) \| $ $ \leq L \| \xk - \Pi_{S}(\xk) \|$ (noting that $\nabla f(\Pi_{S}(\xk)) = 0$).

On the other hand, suppose the PL property <ref> holds with constant $\beta > 0$.
First, we have

\begin{align*}
f(\xknext) -f(\xk) &\leq  \innerproduct{\nabla f(\xk)}{\xknext-\xk} +\frac{L}{2}\|\xknext-\xk\|^2 \nonumber \\
&=  -t_k\innerproduct{\nabla f(\xk)}{\nabla f(\xk)} + \frac{Lt_k^2}{2}\|\nabla f(\xk)\|^2 \nonumber  \\
& = \left( \frac{-2t_k+Lt_k^2}{2}\right)\|\nabla f(\xk)\|^2.
\end{align*}

where the first inequality applies  <ref>. If the step size $t_k$ is chosen such that $ 0< t_k< \frac{2}{L}$, then $ \frac{-2t_k+Lt_k^2}{2} < 0$.  Then, applying PL <ref> to the above inequality and subtracting $f^*$ from both sides, we arrive at the linear convergence in the cost value gap

\begin{equation}
\label{eq:linear-decrease-cost}
f(\xknext) - f^\star \leq (1+\left(-2t_k+Lt_k^2\right) \beta) (f(\xk) - f^\star).
\end{equation}

To summarize, if we choose the step size $t_k$ such that the constants in <ref> less than one (equivalently, $ 0 \leq 1- 2 t_k \mu + t_k^2 L^2 <1$ and $0< t_k< \frac{2}{L} $), linear convergence for both the distance and the cost value gap is guaranteed.
In particular, choosing $t_k = \frac{\mu}{L^2}$, we have $ 1- 2 t_k \mu + t_k^2 L^2  = 1 - \frac{\mu}{L} < 1 $ and $ t_k \leq \frac{L}{L^2} < \frac{2}{L}$ as $\mu \leq L$, leading to the desired linear convergence:

\begin{equation*}
\begin{aligned}
\Dist^2 (\xknext,S) & \leq (1 -\mu/L)  \Dist^2 (\xk,S),
\\
f(\xknext) - f^\star & \leq \frac{L^3 + (- 2 \mu L + \mu^2) \beta }{L^3} (f(\xk) - f^\star).
\end{aligned}
\end{equation*}

Note that if <ref> holds with $\beta >0$, then $\beta \leq \frac{L^3}{2\mu L - \mu^2}$. Otherwise, the above cost value decrease would contradict with the fact that the cost value gap is always nonnegative.
This choice of step size $t_k = \frac{\mu}{L^2}$ is not new, which was used  in <cit.> or implicitly <cit.>.

Note that <ref>
is consistent with the linear convergence result in <cit.> since the step size $t_k = \frac{1}{L}$ also satisfies $0 < t_k < \frac{2}{L}$. Despite choosing $t_k = \frac{1}{L}$ renders a cleaner reduction constant $(1-\frac{\mu}{L})$ in <cit.>, it is unclear if the distance also converges linearly under this stepsize choice (i.e., it is not guaranteed that $t_k = \frac{1}{L}$ leads to the constant $1- 2 t_k \mu + t_k^2 L^2 = 2 - 2 \frac{\mu}{L}<1$).

§ DETAILS OF <REF>

§.§ Proofs of <ref>

Our proofs are adapted from the techniques in <cit.>. We first start by introducing the necessary ingredients to build up the proofs. We define the notion of slope as <cit.>.

Let $\mathcal{X}$ be a complete metric space with the metric $d(\cdot,\cdot)$. Consider a closed function $f: \mathcal{X} \to \overline{\RR}$ and a point $\bar{x}$ with $f(\bar{x})$ finite. The slope of $f$ at $\bar{x}$ is its maximal instantaneous rate of decrease:

\begin{align*}
|\nabla f|(\bar{x}) := \limsup_{x \to \bar{x}} \frac{ (f(\bar{x})- f(x))^{+}} {d(x,\bar{x})},
\end{align*}

where we use the notation $r^{+} = \max\{0,r\}$.

If the function $f$ is smooth on a Euclidean space, the slope $|\nabla f|(\bar{x})$ is simply the norm of the gradient $\|\nabla f(\bar{x})\|$. If $f(x)$ is convex, the slope $|\nabla f|(\bar{x})$ is equivalent to the length of the minimal norm element in the subdifferential, i.e., $|\nabla f|(\bar{x})=\Dist(0, \partial f(\bar{x}))$. If it is $\rho$-weakly convex, the slope $|\nabla f|(\bar{x})$ is the same as the length of the minimal element in the Fréchet subdifferential, i.e., $|\nabla f|(\bar{x}) = \Dist(0, \fpartial f(\bar{x}))$ (see
[Ioffe, 2017, Drusvyatskiy, 2013] for more details).
We summarize these useful properties into a lemma below:

Consider a closed function $f: \RR^n \to \overline{\RR}$ and a point $\bar{x} \in \RR^n$ with $f(\bar{x})$ finite. The following statements for the slope hold.

* If $f$ is smooth, then $|\nabla f|(\bar{x}) =  \|\nabla f(\bar{x})\|$;

* If $f$ is convex, then $|\nabla f|(\bar{x}) = \Dist(0,\partial f(\bar{x}))$;

* If $f$ is $\rho$-weakly convex, then $|\nabla f|(\bar{x}) = \Dist(0,\fpartial f(\bar{x}))$.

We note that the following inequality holds for any $\bar{x} \in \RR^n$ with a finite function value $f(\bar{x})$ <cit.>

\begin{equation}
\label{eq:slope-Frechet-subdifferential}
|\nabla f|(\bar{x}) \leq \Dist (0,\fpartial f(\bar{x}) ).
\end{equation}

As the slope lacks basic lower-semicontinuity properties, it is important to define the limiting slope

\begin{equation}
\begin{aligned}
\overline{|\nabla f|}(\bar{x}) := \liminf_{x\to \bar{x},  f(x) \to f(\bar{x})} |\nabla f|(x). \label{eq:limit-slope}
\end{aligned}
\end{equation}

The result from <cit.> has shown that

\begin{equation}
\begin{aligned}
\label{eq:limiting-slope-limiting-subdifferential}
\overline{|\nabla f|}(\bar{x}) = \Dist(0,\partial f(\bar{x})),
\end{aligned}
\end{equation}

where $\partial f(\bar{x})$ denotes the limiting subdifferential (defined in Equation 18 [Li et al., 2020]) of $f$ evaluated at $\bar{x}$.
Then we claim that for the class of functions whose Fréchet subdifferential and limiting subdifferential coincide, we have $|\nabla f|(\bar{x}) = \Dist(0,\fpartial (\bar{x})).$
Indeed, suppose $\fpartial f(\bar{x}) = \partial f(\bar{x}) $, using <ref> and <ref>, we have

\begin{equation*}
\overline{|\nabla f|}(\bar{x}) = \Dist(0,\partial f(\bar{x})) =  \Dist(0,\fpartial f(\bar{x})) \geq |\nabla f|(\bar{x}).
\end{equation*}

On the other hand, $\overline{|\nabla f|}(\bar{x}) \leq |\nabla f|(\bar{x})$ always holds true by defintion <ref>. Thus, $ |\nabla f|(\bar{x}) = \Dist(0,\fpartial f (\bar{x}))$.
One sufficient condition for Fréchet subdifferential and limiting subdifferential being the same (i.e., $\fpartial f(\bar{x}) = \partial f(\bar{x})$) is $f$ being subdifferentially regular at $\bar{x}$ <cit.>. For smooth, convex, and weakly convex functions, they are subdifferentially regular at every point <cit.>. Thus, the result follows.

We then introduce a key result from <cit.> that will help us estimate the distance to the optimal solution set.

Let $f: \RR^n \to \overline{\RR}$ be a proper closed function. Suppose for some point $x \in \text{dom}(f)$, there are constants $\alpha < f(x)$ and $r>0, K > 0$ such that $f(x) - \alpha < Kr$ and

\begin{align*}
|\nabla f|(u) \geq r, \qquad  \forall u \in [\alpha < f \leq f(x)] \cap (\Dist(u,x) \leq K).
\end{align*}

Then the sublevel set $[f\leq \alpha]$ is nonempty and $\Dist(x,[f\leq \alpha]) \leq (f(x)-\alpha)/r.$

Note that if $\alpha = f^\star$ in <ref>, we can estimate the distance $\Dist(x, [f= f^\star])$.

Let $f: \RR^n \to \overline{\RR} $ be a proper closed function. Suppose that for some $\epsilon > 0$ and $z \in [f \leq  \inf f + \epsilon]$.
Then for any $\rho > 0$ there exists $y \in \RR^n$ such that

\begin{align}
\Dist(z,y) &\leq \epsilon/\rho, \label{eq:Ekeland-1} \\
f(y)  &\leq f(z), \label{eq:Ekeland-2}\\
f(x) + \rho \cdot \Dist(x,y)  &> f(y), \;\;\forall x \in \RR^n/\{y\}.\label{eq:Ekeland-3}
\end{align}

Note that <ref> means that the distance between $y$ and $z$ is bounded, <ref> tells us that $y$ is also in the sublevel set, and <ref> shows that $y$ uniquely minimizes the function $f(\cdot) + \rho \cdot \Dist(\cdot,y)$. Following from the definition of slope (<ref>), one immediate consequence of <ref> is that the slope of $y$ is also bounded by $\rho$ as

\begin{equation}
\label{eq:bound-slope}
\begin{aligned}
|\nabla f|(y) = \limsup_{x \to y} \frac{ (f(y)- f(x))^{+}} {\Dist(x,y)} \leq \limsup_{x \to y} \frac{ \rho \cdot \Dist(x,y) } {\Dist(x,y)} = \rho.
\end{aligned}
\end{equation}

We are ready to prove the main result in <ref>. In particular, <ref> will play an important role in the proof of $\cref{eq:PL} \Rightarrow \cref{eq:EB} \Rightarrow \cref{eq:QG}$.

Poof of <ref> Recall that $S$ denotes the set of minimizers of $f(x)$, which is non-empty.

* <ref> $\Rightarrow$ <ref>: Suppose $f$ satisfies <ref> with constant $\mus>0$. For any $x \in [f\leq f^\star + \nu]$ and $g \in \partial f(x)$, we let $y = \Pi_{S}(x)$. It follows that

\begin{equation*}
\begin{aligned}
& f(x) + \innerproduct{g}{\Pi_{S}(x)-x} + \mus \cdot \Dist^2(x,S) \leq f(\Pi_{S}(x)) \\
\Longrightarrow ~ & \mus \cdot \Dist^2(x,S) \leq f(\Pi_{S}(x)) - f(x) + \innerproduct{g}{x-\Pi_{S}(x)} \\
&\qquad \qquad \qquad \; \leq \innerproduct{g}{x-\Pi_{S}(x)},
\end{aligned}
\end{equation*}

where the last inequality comes from the fact that $f(\Pi_{S}(x)) - f(x) \leq 0$. This inequality also implies that $\mur \geq \mus$.

* <ref> $\Rightarrow$ <ref>: Suppose $f$ satisfies <ref> with constant $\mur > 0$. Let $x \in [f\leq f^\star + \nu]$ and $g$ be the minimal norm element in $\fpartial f(x)$. Then, by definition of <ref>, we have

\begin{equation*}
\begin{aligned}
\innerproduct{g}{x - \Pi_{S}(x)} \geq \mur \cdot \Dist^2(x,S).
\end{aligned}
\end{equation*}

Applying Cauchy-Schwarz on the left side yields

\begin{equation*}
\begin{aligned}
\Dist(0,\fpartial f (x))  \geq \mur \cdot \Dist(x,S).
\end{aligned}
\end{equation*}

This also implies that $\mue \leq \frac{1}{\mur}$.

* <ref> $\Rightarrow$   <ref>: Suppose $f$ satisfies <ref> with constant $\mue>0$. From the subdifferential property for $\rho$-weakly convex function <ref>, we have

\begin{align*}
f^\star \geq f(x) + \innerproduct{v}{\Pi_{S}(x) - x} - \frac{\rho}{2}\|\Pi_{S}(x) - x\|^2,
\end{align*}

where $v \in \fpartial f(x)$. Choosing $v$ as the minimal norm element of $\fpartial f(x)$, we deduce

\begin{align*}
f(x) - f^\star & \leq \Dist(0,\fpartial f(x))\Dist(x,S) + \frac{\rho}{2}\Dist^2(x,S) \\
& \leq \mue \cdot \Dist^2(0,\fpartial f(x)) + \frac{\rho \mue^2}{2}\Dist^2(0,\fpartial f(x)) \\
& = \left(\frac{2 \mue +\rho \mue^2}{2} \right) \Dist^2(0,\fpartial f(x)).
\end{align*}

Dividing both sides by $(2 \mue +\rho \mue^2)/2$ gets the desired constant.

* <ref> $\Rightarrow$ <ref>: Suppose $f$ satisfies <ref> with constant $\mup > 0$.
As $f$ is $\rho$-weakly convex, applying <ref> on <ref> shows that

\begin{equation} \label{eq:slop-PL-f}
|\nabla f|^2(x) \geq \mup \cdot (f(x) - f^\star), \quad \forall x \in [f\leq f^\star + \nu].
\end{equation}

Let $g(x) = (f(x) - f^\star)^{1/2}$. Note that from <ref> and the chain rule of limiting subdifferential <cit.>, for all $\Bar{x} \in [0<g \leq \sqrt{\nu}]$, we have the following inequalities

\begin{equation*}
\begin{aligned}
|\nabla g|(\bar{x}) & \overset{(a)}{\geq} \overline{|\nabla g|}(\bar{x}) \overset{(b)}{=}  \Dist(0, \partial g(\bar{x})) \overset{(c)}{\geq}  \Dist(0, \frac{1}{2} (f(\bar{x}) - f^\star)^{-1/2} \partial f(\bar{x}))\\
& \overset{(d)}{=} \Dist(0, \frac{1}{2} (f(\bar{x}) - f^\star)^{-1/2} \fpartial f(\bar{x})) = \frac{1}{2} (f(\bar{x}) - f^\star)^{-1/2} \Dist(0,  \fpartial f(\bar{x}))\\
& \overset{(e)}{=} \frac{1}{2} (f(\bar{x}) - f^\star)^{-1/2} |\nabla f|(\bar{x}) \\
&  \overset{(f)}{\geq} \frac{1}{2} (f(\bar{x}) - f^\star)^{-1/2} \cdot \sqrt{\mup}(f(\bar{x})-f^\star)^{1/2} \\
& = \frac{\sqrt{\mup}}{2},
\end{aligned}
\end{equation*}

where $(a)$ follows the definition <ref>, $(b)$ comes from <ref>, $(c)$ uses the fact that $\partial g \subseteq \frac{1}{2} (f(\bar{x}) - f^\star)^{-1/2} \partial f(\bar{x})$ <cit.>, $(d)$ uses the fact that $f$ is weakly convex so it is subdifferentially regular at every point, implying $\fpartial f(\bar{x}) = \partial f(\bar{x})$  <cit.>, $(e)$ uses <ref>, and $(f)$ comes from <ref>.

Fix a point $x \in [ 0 < g \leq \sqrt{\nu}]$.
We choose $K > g(x) \frac{2}{\sqrt{\mup}}$. It is obvious we have

\begin{equation*}
\begin{aligned}
|\nabla g|(u) & \geq   \frac{\sqrt{\mup}}{2 }, \quad \forall u \in [0 < g \leq g(x)] \cap (\Dist(u,x) \leq K),\\
g(x)  & < K \frac{\sqrt{\mup}}{2 }.
\end{aligned}
\end{equation*}

Choosing $r = \frac{\sqrt{\mup}}{2}, \alpha = 0$ in <ref>, we have the following bounds

\begin{equation*}
\begin{aligned}
\Dist(x,S) = \Dist(x,[g\leq 0]) & \leq \frac{2}{\sqrt{\mup}}g(x) = \frac{2}{\sqrt{\mup}}(f(x)-f^\star)^{1/2} \\
& \leq \frac{2}{\mup} |\nabla f|(x) = \frac{2}{\mup} \Dist(0,\fpartial f(x)),\quad \forall x\in [f \leq f^\star + \nu],
\end{aligned}
\end{equation*}

where the first inequality is from <ref>, the second inequality comes from <ref>, and the third inequality applies <ref>.
This completes the proof of <ref> $\Rightarrow$ <ref>.

* <ref> $\Rightarrow$ <ref>:
Suppose $f$ satisfies <ref> with $\mue > 0$. Fixing any $x \in [f^\star<f\leq f^\star + \nu]$, we have $x \in [f^\star<f \leq f^\star + \epsilon]$ with $\epsilon = f(x) - f^\star$. Choosing $\rho = \sqrt{\epsilon/\mue}$, <ref> ensure that there exists a $y$ such that $y \in [f\leq f^\star+ \epsilon]$ and $|\nabla f|(y) \leq \rho$.

\begin{align*}
\mue \rho \geq \mue \cdot |\nabla f|(y)& \overset{(a)}{\geq} \Dist(y,S)\\
&\overset{(b)}{\geq} \Dist(x,S) - \Dist(x,y) \\
&\overset{(c)}{\geq} \Dist(x,S) - \epsilon/\rho,
\end{align*}

where $(a)$ uses <ref> (i.e., we have $|\nabla f|(y) = \Dist(0,\fpartial f(y))$ for weakly convex functions) and <ref>, $(b)$ applies the triangle inequality for a point to a set, and $(c)$ comes from <ref>.
Substituting $\epsilon = f(x) - f^\star$ and $\rho = \sqrt{\frac{\epsilon}{\mue}}$ and rearranging the above inequality yields

\begin{align*}
2\sqrt{\mue} (f(x) - f^\star)^{1/2} \geq \Dist(x,S).
\end{align*}

Squaring both sides completes the proof of <ref> $\Rightarrow$ <ref>.

Summarizing the relationship above leads to the first part of <ref> in <ref>. We now prove the second part in <ref>.

* <ref> with $f$ being convex or $\muq > \frac{\rho}{2}$ $\Rightarrow$ <ref>: We prove the later as the former follows the exact argument by setting $\rho = 0$ (which means that $f$ is convex).

Let $x  \in [f \leq f^\star + \nu]$ and $ g \in \fpartial f(x)$. From the assumption of <ref> and the property of subgradient of weakly convex function in <ref>, we have

\begin{align*}
\muq \cdot \Dist^2(x,S) \leq  f(x) - f^\star & \leq   \innerproduct{g}{x - \Pi_{S}(x)} + \frac{\rho}{2} \Dist^2(x,S).
\end{align*}

Rearranging terms yields

\begin{equation*}
\begin{aligned}
\left (\muq - \frac{\rho}{2} \right)  \cdot \Dist^2(x,S) \leq \innerproduct{g}{x - \Pi_{S}(x)}.
\end{aligned}
\end{equation*}

This completes our proof of <ref>.

§.§ An example of $\rho$-weakly convex function with $\muq > \frac{\rho}{2}$

We give a detailed examination of the example showing that even if <ref> holds with the constant $\muq > \frac{\rho}{2}$, the function is still nonconvex while all the <ref>, <ref>, <ref>, and <ref> all hold true.
Consider the function

\begin{equation*}
\begin{aligned}
f(x) = \begin{cases}
-x^2+1 & \text{if}~ -1  <  x < -0.5, \\
3(x+1)^2 & \text{otherwise}.
\end{cases}
\end{aligned}
\end{equation*}

It can be verified that the function is not convex (due to the part $-1<x<-0.5$) but $2$-weakly convex with a unique minimizer $x^\star = -1$ and $f^\star = 0$. See <ref> for an illustration of these properties. The Fréchet subdifferential can be calculated as

\begin{equation*}
\begin{aligned}
\fpartial f(x) = \begin{cases}
-2x & \text{if}~ -1  <  x < -0.5, \\
6(x+1) & \text{if}~ x < -1~\text{or}~x>-0.5, \\
[0,2]    & \text{if}~x = -1, \\
[1,3]    & \text{if}~x = -0.5.
\end{cases}
\end{aligned}
\end{equation*}

The length of the minimal element is then

\begin{equation*}
\begin{aligned}
\Dist(0,\fpartial f(x)) = \begin{cases}
|2x| & \text{if}~-1<x<-0.5, \\
|6(x+1)| & \text{if}~ x < -1~\text{or}~x>-0.5, \\
0    & \text{if}~x = -1, \\
1    & \text{if}~x = -0.5.
\end{cases}
\end{aligned}
\end{equation*}

One can see that <ref> holds for $0< \muq\leq 3$,  <ref> holds for $\mue \geq 1/2$, and <ref> holds for $0 < \mup \leq  4/3$. These can also be observed in <ref>.

A nonconvex function with $f^\star = 0$ that satisfies the equivalency $\cref{eq:RSI}\equiv \cref{eq:EB} \equiv \cref{eq:PL} \equiv \cref{eq:QG}$. Left: the function $f$ (blue line) is $\rho$-weakly convex (confirmed by the green line), and also satisfies <ref> with $\muq = 2.5$ (confirmed by the red line);  Middle: $f$ satisfies <ref> as the value of $\Dist(0, \fpartial f(x))$ (yellow curve) is lower bounded by $\Dist(x,S)$ (purple curve). Right: $f$ satisfies <ref> as the value of $\Dist^2(0,\fpartial f(x))$ (red curve) is lower bounded by $f(x)$ (blue curve).

§ CONVERGENCE PROOFS OF THE PPM IN <REF>

§.§ Proof for <ref>

One important step to prove the sublinear convergence <ref> is to establish the one-step improvement <ref>. Specifically, from the optimality condition of <ref>, the iterate $\xknext$ satisfies

\begin{equation}  \label{eq:optimality-subproblem}
- 1/c_k(\xknext - \xk) \in \partial f(\xknext).
\end{equation}

By the definition of subdifferential for convex functions, we know

\begin{equation}
\geq f(\xknext) + \left\langle - \frac{1}{c_k}(\xknext - \xk),  x^\star - \xknext \right\rangle .\label{eq:subgradient-inequality}
\end{equation}

On the other hand, we have

\begin{align}
\|\xknext - x^\star \|^2
& = \|\xk  - x^\star \|^2 - \|\xk-\xknext\|^2 + 2 \innerproduct{\xknext - \xk}{\xknext - x^\star} \nonumber\\
& \leq \|\xk - x^\star \|^2 + 2 \innerproduct{\xknext - \xk}{\xknext - x^\star} ,\label{eq:progress-iterate-1}
\end{align}

where the first identity follows from simple algebraic manipulations $\|\xk - x^\star \|^2 = \|\xk - \xknext + \xknext - x^\star \|^2 = \|\xk - \xknext\|^2 - 2 \langle \xknext - \xk, \xknext - x^\star \rangle + \|\xknext - x^\star \|^2$, and the second inequality drops a nonnegative term $\|\xk-\xknext \|^2$.

Combining (<ref>) with (<ref>) leads to

\begin{align}
\|\xknext - x^\star \|^2 \leq \|\xk - x^\star \|^2 - 2 c_k ( f(\xknext)-  f(x^\star))
\label{eq:progress-iterate-appendix}
\end{align}

which is the same as <ref>.
The rest of the proof follows from a standard telescope argument. Let $x^\star$ be a minimizer. Summing <ref> for $t = 0, \ldots, k-1$, we have a telescope sum as follows

\begin{equation*}
\sum_{t=0}^{k-1} c_t (f(\xknext)-  f(x^\star)) \leq \frac{1}{2}\sum_{t=0}^{k-1}(\|x_{t} - x^\star \|^2 - \|x_{t+1} - x^\star \|^2) \leq \frac{1}{2}\|x_{0} - x^\star \|^2. %  \frac{}{2\hat{c}}.
\end{equation*}

Considering the fact that the function values $\{f(\xk)\}_{k\geq0}$ are nonincreasing, we deduce that

\begin{equation*}
(f(\xk)-f(x^\star)) \sum_{t=0}^{k-1}c_t
\leq \sum_{t=0}^{k-1} c_t (f(x_{t+1})-f(x^\star))
\leq \frac{1}{2}\|x_{0} - x^\star \|^2.
\end{equation*}

Dividing both sides by $\sum_{t=0}^{k-1}c_t$ and taking $x^\star$ as the closed point to $x_0$ in $S$ (since $x^\star$ can be any minimizer), we get the desired inequality in <ref>.
Finally, we show that the sequence of iterates $\{\xk\}_{k \geq 0}$ converges to a minimizer. From <ref>, we know $\{\|\xk - x^\star\|\}_{k \geq 0}$ is nonincreasing and the sequence $\{\xk\}_{k \geq 0}$ is bounded.
Hence, the sequence $\{\xk\}_{k\geq 0}$ has at least one accumulation point $\bar{x}$. Due to the convergence of $f(\xk)$, we know that $\bar{x}$ must be a minimizer, i.e., $f(\bar{x}) = f^\star$ and $\bar{x} \in S$.
We let $x^\star = \bar{x}$ in <ref>. This implies that $\|\xk - \bar{x}\|$ is nonincreasing and bounded by an infimum $0$, thus $\lim_{k\to \infty} \|\xk - \bar{x}\| = 0$, i.e., the whole sequence of iterates $x_k$ converge to $\bar{x}$ asymptotically.

§.§ A compelete proof for <ref>

To finish the proof for <ref> with coefficient $\theta_k \leq 1/{\sqrt{\mue^2/c_k^2 + 1}}$. We first review a crucial but standard result about the proximal mapping.

For any $c_k > 0$ in <ref>, the following holds true

\begin{align}
\Dist^2(\xk,S)  \geq \|\xknext - \Pi_{S}(\xk) \|^2 + \|\xk - \xknext\|^2 \label{eq:firmly-nonexpensive}.
\end{align}

As shown in [Rockafellar, 2021], the proximal point operator for a convex function $f:\RR^n \to \overline{\RR}$ with $\alpha > 0$ is firmly nonexpensive, i.e.,

\begin{align}
\|\text{prox}_{\alpha, f}(x)- \text{prox}_{\alpha, f}(y)\|^2 \leq \innerproduct{x-y}{\text{prox}_{\alpha, f}(x)- \text{prox}_{\alpha, f}(y)},
\quad \forall x,y \in \RR^n.
\label{eq:firmly-nonexpensive-general}
\end{align}

For notational convenience, let $P(x):= \text{prox}_{\alpha, f}(x).$ We have

\begin{align*}
\|x  - y\|^2 & = \|P(x) + ( x -P(x) ) -( P(y) + ( y -P(y) ) )\|^2 \\
& = \|P(x) -P(y)+ ( x -P(x) ) - ( y -P(y) ) \|^2 \\
& = \|P(x) -P(y)\|^2 + \|( x -P(x) ) - ( y -P(y) )\|^2 \\
&\quad  + 2\innerproduct{P(x) -P(y)}{( x -P(x) ) - ( y -P(y) )} \\
& \geq \|P(x) -P(y)\|^2 + \|( x -P(x) ) - ( y -P(y) )\|^2,
\end{align*}

where the last inequality comes from the fact that the inner product is nonnegative by <ref>.

Setting $x = \xk $ and $y = \Pi_{S}(\xk)$, we have $\xknext = P(\xk)$, and $y = P(y)$, which leads to the desired result in  <ref>.

With <ref>, it follows that

\begin{align*}
\Dist^2(\xknext,S) & \leq \|\xknext - \Pi_{S}(\xk)\|^2 \\
& \leq \|\xk - \Pi_{S}(\xk)\|^2  - \|\xk - \xknext\|^2 \\
& \leq \Dist^2(\xk,S) - c_k^2\Dist^2(0,\partial f(\xknext)) \\
& \leq \Dist^2(\xk,S) - \frac{c_k^2}{\mue^2} \Dist(\xknext,S),
\end{align*}

where the second inequality is from <ref>, the third inequality comes from <ref>, and the last inequality uses <ref>.
Rearranging terms, we have

\begin{align*}
\Dist^2(\xknext,S) \leq \frac{\mue^2}{c_k^2 + \mue^2} \Dist^2(\xk,S).
\end{align*}

Taking a square root yields the desired result.

§.§ Weakly convex extension

The linear convergence result in <ref> can be extended to the class of $\rho$-weakly convex functions with proper initialization when the regularity conditions in <ref> hold. As shown in  theorem below, the coefficient $\{c_k\}$ is implicitly related to the weakly convex constant $\rho$.

Suppose the function $f$ in <ref> is $\rho$-weakly convex. Let $S$ be the solution set of <ref> and assume $S \neq \emptyset$. Suppose $f$ satisfies
<ref> with $\muq > \frac{\rho}{2} > 0$ over the sublevel set $[f \leq f^\star + \nu]$ with $\nu > 0$. The iterates generated by the PPM <ref> with any positive sequence $\{c_k\}$ satisfying $\frac{1}{c_k} > \rho, \forall k \geq 1$, and initialization $x_0 \in [f\leq f^\star + \nu]$ satisfy <ref> with constants

\begin{equation*}
\begin{aligned}
\omega_k = \frac{2}{2+\mu_{\mathrm{p}} c_k }  < 1\quad \text{and }\quad\min \left \{ \frac{ 1}{\sqrt{ 2c_k\beta +1} } , \frac{1}{\sqrt{\mue^2/c_k^2 + 1}} \right \}< 1,~\text{where}~\beta = \muq - \frac{\rho}{2} > 0.
\end{aligned}
\end{equation*}

The proof of the linear decrease in the cost value gap is identical to that in <ref>. As $\muq > \frac{\rho}{2}$, <ref>, <ref>, and <ref> also hold by <ref>. For the proof of the linear decrease in the distance, the coefficient $\frac{1}{\sqrt{\mue^2/c_k^2 + 1}}$ follows the same argument as in the convex case since $c_k$ is chosen such that $1/c_k > \rho $ so that the function $f(x) + \frac{1}{2c_k}\| x - \xk \|^2 $ is a convex function plus a quadratic term and the proximal mapping is still firmly inexpensive; For the coefficient $\frac{ 1}{\sqrt{ 2c_k\beta +1}}$, the argument is essential the same as the convex case with a small modification that the subproblem is $(\frac{1}{c_k} - \rho)$-strongly convex.

§ CONVERGENCE PROOFS FOR THE INEXACT PPM IN <REF>

§.§ Proofs for <ref>

The optimality condition of <ref> and criteria <ref> implies that there exist $v_k \in \partial f(\xknext)$ and  $\theta_k \in \RR^n$ such that

\begin{align*}
0 =  v_k + \frac{\xknext - \xk +  \theta_k}{c_k},\quad \|\theta_k\| \leq \epsilon_k.
\end{align*}

Following the same argument in <ref>, we can get a similar version of <ref> as

\begin{align*}
\|\xknext - x^\star \|^2 \leq \|\xk - x^\star \|^2  - 2 c_k ( f(\xknext)-  f(x^\star)) + 2\epsilon_k \|x^\star - \xknext\|.
\end{align*}

This improvement holds for all $k \geq 0$. Taking a sum of the above inequality from $0$ to $k-1$, we get

\begin{align*}
&\|\xk - x^\star \|^2 \leq \|x_0 - x^\star\|^2 - 2 \sum_{j = 0}^{k-1} c_j (f(x_{j+1}) - f(x^\star)) +  \sum_{j = 0}^{k-1} 2\epsilon_j \|x^\star -  x_{j+1}\| \nonumber \\
\Longrightarrow~& 2\sum_{j=0}^{k-1} c_j  \min_{j = 0,\ldots,k}f(x_j)
- f(x^\star) \leq 2\sum_{j = 0}^{k-1}c_j (f(x_{j+1}) - f(x^\star))
\leq \|x_0-x^\star\|^2 + 2D\sum_{j=0}^{k-1} \epsilon_j.
\end{align*}

Dividing both sides by $2 \sum_{j=0}^{k-1}c_j$ and letting $x^\star = \Pi_{S}(x^0)$ gets the desired inequality. The convergence of the iterate $\{\xk\}$ and the boundedness of the diameter $D$ is guaranteed by <ref>.

<ref> provides a convergence guarantee for the best iterate as opposed to that for the last iterate in <ref>. The guarantee for the average $\bar{x}_k = \frac{1}{k} \sum_{j=1}^{k} x_j $ or the weighted average $\Tilde{x}_k = \frac{\sum_{j=0}^{k-1} c_j x_{j+1}}{\sum_{j=0}^{k-1} c_j} $ can also be shown using the inequality

\begin{equation*}
f(\bar{x}_k) - f^\star =  f\left(\sum_{j=1}^{k} \frac{1}{k} x_j\right) -
\frac{1}{k}\sum_{j=1}^{k} f^\star \leq \frac{1}{k} \sum_{j=0}^{k-1}   (f(x_{j+1}) - f^\star)
\end{equation*}

\begin{equation*}
f(\Tilde{x}_k) - f^\star
\leq  \frac{1}{\sum_{j=0}^{k-1} c_j}  \sum_{j=0}^{k-1} c_j (f(x_{j+1}) - f^\star).
\end{equation*}

The proof in <ref> borrows some proof idea  from <cit.> with the fact that <ref> implies the existence of $\theta_k \in \RR^n$ such that $\Dist(0,H_k(\xknext)) ={\|\theta_k\|}/{c_k} \leq \epsilon_k$.

§.§ Proofs for <ref>

We here discuss some details for the useful inequality <ref>. Since this inequality plays an important role in the proof of <ref>, we put it into a lemma below.

Let $S$ be the solution set of <ref> and assume $S \neq \emptyset$.
Let $\{\xk\}$ be any sequence generated by the inexact PPM <ref> under <ref> with parameters $\{c_k\}_{k\geq 0}$ bounded away from zero.
Then there exists a $\hat{k}\geq 0$ such that
$\hat{k}$ satisfies $\delta_k < 1,\forall k \geq  \hat{k}$ and

\begin{align}
\label{eq:inexact-PPM-distance-error-app}
(1-\delta_k ) \Dist(\xknext,S) \leq 2\delta_k \Dist(\xk,S) + \Dist(\mathrm{prox}_{c_k ,f}(\xk),S), \; \forall k \geq  \hat{k},
\end{align}

Fix a $x\in \RR^n$. From the update <ref>, we know

\begin{equation*}
\begin{aligned}
& f(\mathrm{prox}_{c_k,f}(x)) + \frac{1}{2c_k}\| \mathrm{prox}_{c_k,f}(x)- x\|^2 \leq f(\Pi_{S}(x)) +  \frac{1}{2c_k}\| \Pi_{S}(x)- x\|^2 \\
\Longrightarrow ~ &  \frac{1}{2c_k}\| \mathrm{prox}_{c_k,f}(x)- x\|^2  \leq f^\star - f(\mathrm{prox}_{c_k,f}(x)) + \frac{1}{2c_k}\| \Pi_{S}(x)- x\|^2 \\
\Longrightarrow ~ & \| \mathrm{prox}_{c_k,f}(x)- x\| \leq \Dist(x,S),
\end{aligned}
\end{equation*}

where the last implication is due to $f^\star - f(\mathrm{prox}_{c_k,f}(x)) \leq 0$. On the other hand, using triangle inequality, the nonexpensiveness of projection onto a convex set, and the above inequality, we have

\begin{align}
\forall x \in \RR^n, ~ \|x - \Pi_{S}(\text{prox}_{c_k,f}(x)) \| &  \leq \|x - \Pi_{S}(x)\| + \| \Pi_{S}(x)-\Pi_{S}(\text{prox}_{c_k,f}(x))\| \nonumber \\
& \leq  \Dist(x,S) + \| x-\text{prox}_{c_k,f}(x)\|  \nonumber \\
& \leq 2 \Dist(x,S).%,\quad \forall x \geq 0.
\label{eq:difference}
\end{align}

\begin{align*}
&~\|\xknext -\Pi_{S}(\text{prox}_{c_k,f}(x)) \| \\
\leq &~\| \xknext  -\text{prox}_{c_k,f}(\xk) \| + \| \text{prox}_{c_k,f}(\xk)- \Pi_{S}(\text{prox}_{c_k,f}(x))\| \\
\leq &~\delta_k \|\xknext - \xk\| + \Dist(\text{prox}_{c_k,f}(\xk),S) \\
\leq &~\delta_k \| \xknext -\Pi_{S}(\text{prox}_{c_k,f}(x))  \| + \delta_k \| \xk -\Pi_{S}(\text{prox}_{c_k,f}(x))  \| + \Dist(\text{prox}_{c_k,f}(\xk),S),
\end{align*}

where the second inequality is from the stopping criterion <ref>. As $\delta_k \to 0$, choosing $\hat{k}$ such that $\delta_k < 1, \forall k \geq \hat{k},$ we have

\begin{align*}
(1-\delta_k )\|\xknext -\Pi_{S}(\text{prox}_{c_k,f}(x)) \| \leq \delta_k \| \xk -\Pi_{S}(\text{prox}_{c_k,f}(x))  \| + \Dist(\text{prox}_{c_k,f}(\xk),S).%\; \forall k \geq \hat{k}.
\end{align*}

Finally, using the fact $\Dist(\xknext,S) \leq \|\xknext -\Pi_{S}(\text{prox}_{c_k,f}(x)) \|$ and <ref> for $x = \xk$ completes the proof.

§ DETAILS OF NUMERICAL EXPERIMENTS

In <ref>, we consider three applications of convex optimization in machine learning and signal processing, including linear support vector machine (SVM) ([Zhang and Lin, 2015]), Lasso ([Tibshirani, 1996]), and Elastic-Net ([Zou and Hastie, 2005]).
The problem formulations are listed as

* Linear SVM:

\begin{equation*}
\begin{aligned}
\min_{x\in \RR^n}\quad  \frac{1}{n} \sum_{i = 1}^n \max \{0,1 - b_i(a_i^\tr x)\} + \frac{\rho}{2} \|x\|^2,
\end{aligned}
\end{equation*}

where $\rho > 0, a_i \in \RR^d, b_i \in \{-1,1\}, i = 1, \ldots, n.$

* Lasso ($\ell_1$-regularization):

\begin{equation*}
\min_{x\in \RR^m}\quad \frac{1}{2} \| y - Ax \|^2 + \lambda \|x\|_{1},
\end{equation*}

where $A \in \RR^{n\times m}, y \in \RR^m ,$ and $ \lambda > 0$.

* Elastic-Net ($\ell_1-\ell_2^2$-regularization):

\begin{equation*}
\min_{x\in \RR^m}\quad  \frac{1}{2}\| y - Ax \|^2 + \lambda \|x\|_{1}+ \frac{\mu}{2}\|x\|^2,
\end{equation*}

where $A \in \RR^{n\times m}, y \in \RR^m ,$ and $ \lambda, \mu > 0$.

For linear SVM, we consider three datasets (“a1a”, “Australian”, “fourclass”) from [Chang and Lin, 2011]. The regularization term is set as $\rho = 1.$ The step size parameter of the PPM is chosen as $c_k = 1$ for all $k\geq 1$. For Lasso, we randomly generate $A \in \RR^{n \times m}$ and $ \hat{x} \in \RR^{m}$ with $s$ elements being zero ($s < m$), then construct the vector $y = A\hat{x}$. We consider problems with three different sizes: $(n=10,m=40,s=5),(n=20,m=50,s=10),$ and $(n=30,m=60,s=15) $. The regularization terms are set as $\rho = 10$. The step size parameter of the PPM is chosen as $c_k = 0.16$ for all $k\geq 1$. For Elastic-Net, we consider the same data in Lasso with the regularization terms $\rho =10$ and $\mu = 1.$

We use the modeling package Yalmip [Löfberg, 2004] to formulate the subproblem <ref> and call the conic solver Mosek [ApS, 2019] to solve it. Our code is available at