Error bounds, quadratic growth, and linear convergence of proximal methods

Introduction

Under favorable conditions, many fundamental optimization algorithms converge linearly: the distance of the iterates to the optimal solution set (the “error”) is bounded by a decreasing geometric sequence. Classical optimization literature highlights how quadratic growth properties of the objective function, typically guaranteed through second-order optimality conditions, ensure such linear convergence. Central examples traditionally include the method of steepest descent for smooth minimization [5, Theorem 3.4] and, more abstractly, the proximal point method for nonsmooth convex problems [41, Theorem 2, Proposition 7].

More recent techniques, originally highlighted in the work of Luo and Tseng , postulate that the step length at each iteration of the algorithm linearly bounds the error. Such “error bounds” are commonly used in the analysis of first-order methods for strongly convex functions, popular in modern applications such as machine learning and high-dimensional statistics, including in particular the proximal gradient method and its variants; see for example Nesterov and Beck-Teboulle . Convergence analysis based only on the error bound property is appealingly simple even without strong convexity, but the underlying assumption on the optimization problem is opaque at least at first sight.

Some recent developments have focused on linear convergence guarantees based on more intuitive, geometric properties, akin to the classical quadratic growth condition. An interesting example is . Our aim here is to take a thorough and systematic approach, that is generalizable to problems with more complex structure. Our aim is to show, in several interesting contemporary optimization frameworks, the equivalence between, on the one hand, the intuitive notion of quadratic growth of the objective function away from the set of minimizers, and on the other hand, the powerful analytic tool furnished by an error bound. Rockafellar already foreshadowed this possibility with his original analysis of the proximal point method . We extend that relationship here to the proximal gradient method for problems

with $g$ convex and $f$ convex and smooth, and more generally to the prox-linear algorithm (a variant of Gauss-Newton) for convex-composite problems

where $g$ is a extended-real-valued closed convex function, $h$ is a finite-valued convex function, and $c$ is a smooth mapping. Acceleration strategies for the prox-linear algorithm have recently appeared in . In parallel, we show how the error bound property quickly yields linear convergence guarantees. In essence, our analysis depends on viewing these two methods as approximations of the original proximal point algorithm – a perspective of an independent interest. Our assumptions are mild: we rely primarily on a natural strict complementarity condition. In particular, we simplify and extend some of the novel convergence guarantees established in the recent preprint for the prox-gradient method.While finalizing a first version of this work, the authors became aware of a concurrent, independent and nicely complementary approach , based on a related calculus of Kurdyka-Łojasiewicz exponents.

The iterative algorithms we consider assign a “gradient-like” step to each potential iterate, as in the analysis of proximal methods in [34, Section 2.1.5]; the step length is zero at stationary points and otherwise serves as a surrogate measure of optimality. For steepest descent, the step is simply a multiple of the negative gradient, for the proximal point method it is determined by a subdifferential relationship, while the prox-gradient and prox-linear methods combine the two. In the language of variational analysis, the existence of an error bound is exactly “metric subregularity” of the gradient-like mapping; see Dontchev-Rockafellar . We will show that subregularity of the gradient-like mapping is equivalent to subregularity of the subdifferential of the objective function itself, thereby allowing us to call on extensive literature relating the quadratic growth of a function to metric subregularity of its subdifferential . Given the generality of these techniques, we expect that the approach we describe here, rooted in understanding linear convergence through quadratic growth, should extend broadly. We note, in particular, some parallel developments influenced by the first version of this work , in the recent manuscript .

When analyzing the prox-linear algorithm, we encounter a surprise. The error bound condition yields a linear convergence rate that is an order of magnitude worse than the natural rate for the prox-gradient method in the convex setting. The difficulty is that in the nonconvex case, the “linearizations” used by the method do not lower-bound the objective function. Nonetheless, we show that the method does converge with the natural rate if the objective function satisfies the stronger condition of quadratic growth that is uniform with respect to tilt-perturbations – a property equivalent to the well-studied notions of tilt-stability and strong metric regularity of the subdifferential . Concretely, these notions reduce to strong second-order sufficient conditions in nonlinear programming , whenever the active gradients are linearly independent.

An important byproduct of our analysis, worthy of independent interest, relates the step-lengths taken by the prox-linear method to near-stationarity of the objective function at the iterates. Therefore, short step-lengths can be used to terminate the scheme, with explicit guarantees on the quality of the final solution.

We end by studying to what extent the tools we have developed generalize to composite optimization where the outer function $h$ may be neither convex nor continuous – an arena of growing recent interest (e.g. ). While considerably more technical, key ingredients of our analysis extend to this very general setting.

The outline of the manuscript is as follows. Section 2 briefly records some elementary preliminaries. Section 3 contains a detailed analysis of linear convergence of the prox-gradient method for convex functions through the lens of error bounds and quadratic growth. In section 4, we show that quadratic growth holds in concrete applications under a mild condition of dual strict complementarity; our analysis aims to illuminate and extend some of the results in by dispensing with strong convexity of component functions. Section 5 is dedicated to the local linear convergence of the prox-linear algorithm for minimizing compositions of convex functions with smooth mappings. Section 6 explains how a uniform notion of quadratic growth implies linear convergence of the prox-linear method with the natural rate. Section 7 explains the resulting consequences for the prox-gradient method when the smooth component is not convex. The final section 8 shows the equivalence between the error bound property of the prox-linear map and subdifferential subregularity when both the component functions $g$ and $h$ may be infinite-valued and non-convex.

Preliminaries

Unless otherwise stated, we follow the terminology and notation of . Throughout ${\bf R}^{n}$ will denote an $n$-dimensional Euclidean space with inner-product $\langle\cdot,\cdot\rangle$ and corresponding norm $\|\cdot\|$. The closed unit ball will be written as ${\bf B}$, while the open ball of radius $r$ around a point $x$ will be denoted by $B_{r}(x)$. For any set $Q\subset{\bf R}^{n}$, we define the distance function

The functions we consider will take values in the extended real line $\overline{{\bf R}}:={\bf R}\cup\{\pm\infty\}$. The domain and the epigraph of a function $f\colon{\bf R}^{n}\to\overline{{\bf R}}$ are defined by

respectively. We say that $f$ is closed if the inequality $\operatornamewithlimits{liminf}_{x\to\bar{x}}f(x)\geq f(\bar{x})$ holds for any point $\bar{x}\in{\bf R}^{n}$. The symbol $[f\leq\nu]:=\{x:f(x)\leq\nu\}$ will denote the $\nu$-sublevel set of $f$. For any set $Q\subset{\bf R}^{n}$, the indicator function $\delta_{Q}\colon{\bf R}^{n}\to\overline{\bf R}$ evaluates to zero on $Q$ and to $+\infty$ elsewhere.

The Fenchel conjugate of a convex function $f\colon{\bf R}^{n}\to\overline{\bf R}$ is the closed convex function $f^{\star}\colon{\bf R}^{n}\to\overline{{\bf R}}$ defined by

The subdifferential of a convex function $f$ at a point $x$, denoted by $\partial f(x)$, is the set consisting of all vectors $v\in{\bf R}^{n}$ satisfying $f(z)\geq f(x)+\langle v,z-x\rangle$ for all $z\in{\bf R}^{n}$. For any function $f\colon{\bf R}^{n}\to\overline{{\bf R}}$ and a real number $t>0$, we define the Moreau envelope

The proximal map $x\mapsto{\rm prox}_{tg}(x)$ is always 1-Lipschitz continuous.

A set-valued mapping $F\colon{\bf R}^{n}\rightrightarrows{\bf R}^{m}$ is a mapping assigning to each point $x\in{\bf R}^{n}$ the subset $F(x)$ of ${\bf R}^{m}$. The graph of such a mapping is the set

The inverse map $F^{-1}\colon{\bf R}^{m}\rightrightarrows{\bf R}^{n}$ is defined by setting $F^{-1}(y)=\{x:y\in F(x)\}$. Every mapping $F\colon{\bf R}^{n}\rightrightarrows{\bf R}^{n}$ obeys the identity [43, Lemma 12.14]:

Note that for any convex function $g$ and a real $t>0$, equality ${\rm prox}_{tg}=(I+t\partial g)^{-1}$ holds.

Linear convergence of the prox-gradient method

To motivate the discussion, consider the optimization problem

where $g\colon{\bf R}^{n}\to\overline{{\bf R}}$ is a closed convex function and $f\colon{\bf R}^{n}\to{\bf R}$ is a convex $C^{1}$-smooth function with a $\beta$-Lipschitz continuous gradient:

The proximal gradient method is the recurrence

where the constant $t>0$ is appropriately chosen. More succinctly, the method simply iterates the steps

In order to see the parallel between the proximal gradient method and classical gradient descent for smooth minimization, it is convenient to rewrite the recurrence yet again as $x_{k+1}=x_{k}-t\mathcal{G}_{t}(x_{k})$ where

is the prox-gradient mapping. In particular, equality $\mathcal{G}_{t}(x)=0$ holds if and only if $x$ is optimal for $\varphi$.

Let $S$ be the set of minimizers of $\varphi$ and let $\varphi^{*}$ be the minimal value of $\varphi$. Supposing now $t\leq\beta^{-1}$, the following two inequalities are standard [34, Theorem 2.2.7, Corollary 2.2.1] and [7, Lemma 2.3]:

Here $x^{*}$ denotes an arbitrary element of $S$. Hence equation (3.3) immediately implies

Defining $\gamma_{k}:=\frac{\|x^{*}-x_{k}\|}{\|\mathcal{G}_{t}(x_{k})\|}$ and using inequality (3.2), along with some trivial algebraic manipulations, yields the geometric decrease guarantee

Hence if the quantities $\gamma_{k}$ are bounded for all large $k$, asymptotic Q-linear convergence in function values is assured. This observation motivates the following definition, originating in .

Given real numbers $\gamma,\nu>0$, we say that the error bound condition holds with parameters $(\gamma,\nu)$ if the inequality

Suppose the error bound condition holds with parameters $(\gamma,\nu)$. Then the proximal gradient method with $t\leq\beta^{-1}$ satisfies $\varphi(x_{k})-\varphi^{*}\leq\epsilon$ after at most

Moreover, if the iterates $x_{k}$ have some limit point $x^{*}$, then there exists an index $r$ such that the inequality

holds for all $k\geq 1$, where we set $C:=\frac{2}{\beta(1-\sqrt{1-(2\beta\gamma)^{-1}})^{2}}$.

From the the standard sublinear estimate $\varphi(x_{k})-\varphi^{*}\leq\frac{\beta\cdot{\rm dist}^{2}(x_{0},S)}{2k}$ (see e.g. [7, Theorem 3.1]), we deduce that after $k\leq\frac{\beta}{2\nu}{\rm dist}^{2}(x_{0},S)$ iterations the inequality $\varphi(x_{k})-\varphi^{*}\leq\nu$ holds. The second summand in inequality (3.5) is then immediate from the linear rate (3.4) and the fact that the values $\varphi(x_{k})$ decrease monotonically.

Now suppose that $x^{*}$ is a limit point of $x_{k}$. Note that if an iterate $x_{r}$ lies in the set $[\varphi\leq\varphi^{*}+\nu]$, then we have

where we set $D:=\frac{\sqrt{2}}{\sqrt{\beta}(1-\sqrt{1-(2\beta\gamma)^{-1}})}$. Squaring both sides, the result follows. ∎

Convergence guarantees of Theorem 3.2 are expressed in terms of the error bound parameters $(\gamma,\nu)$ – quantities not stated in terms of the initial data of the problem, $f$ and $g$. Indeed, the error bound condition is a property of the prox-gradient mapping $\mathcal{G}_{t}(x)$, a nontrivial object to understand. In contrast, in the current work we will show that the error bound condition is simply equivalent to the objective function $\varphi$ growing quadratically away from its minimizing set $S$ – a familiar, transparent, and largely classical property in nonsmooth optimization.

To gain some intuition, consider the simplest case $g=0$. Then the prox-gradient method reduces to gradient descent $x_{k+1}=x_{k}-t\nabla f(x_{k})$. Suppose now that $f$ grows quadratically (globally) away from its minimizing set, meaning there is a real number $\alpha>0$ such that

Notice this property is weaker than strong convexity even for $C^{1}$-smooth functions; e.g $f(x)=(\max\{|x|-1,0\})^{2}$. Then convexity implies

Thus the error bound condition holds with parameters $(\gamma,\nu)=(\frac{2}{\alpha},\infty)$, and the complexity bound of Theorem 3.2 becomes $k\leq\frac{4\beta}{\alpha}\ln\left(\frac{\varphi(x_{0})-\varphi^{*}}{\epsilon}\right)$. This is the familiar linear rate of gradient descent (up to a constant).

Our goal is to elucidate the quantitative relationship between quadratic growth and the error bound condition in full generality. The strategy we follow is very natural; we will interpret the proximal gradient method as an approximation to the true proximal point algorithm $y_{k+1}={\rm prox}_{t\varphi}(y_{k})$ on the function $\varphi=f+g$, and show a linear relationship between the corresponding step sizes (Theorem 3.5). This will allows us to ignore the linearization appearing in the definition of the proximal gradient method and focus on the relationship between quadratic growth of $\varphi$, properties of the mapping ${\rm prox}_{t\varphi}$, and of the subdifferential $\partial\varphi$ (Theorems 3.3 and 3.4). We believe this interpretation of the proximal gradient method is of interest in its own right.

The following is a central result we will need. It establishes a relationship between quadratic growth properties and a “global error bound property” of the function $x\mapsto d(0,\partial\varphi(x))$. Variants of this result have appeared in [1, Theorem 3.3], [4, Theorem 6.1], [15, Theorem 4.3], [19, Theorem 3.1], and .

Consider a closed convex function $h\colon{\bf R}^{n}\to\overline{{\bf R}}$ with minimal value $h^{*}$ and let $S$ be its set of minimizers. Consider the conditions

If condition (3.6) holds, then so does condition (3.7) with $L=2\alpha^{-1}$. Conversely, condition (3.7) implies condition (3.6) with any $\alpha\in(0,\frac{1}{L}]$.

The proof of the implication $\eqref{eqn:quad_growth}\Rightarrow\eqref{eqn:reg_growth}$ is identical to the proof of the analogous implication in [1, Theorem 3.3]; the proof of the implication $\eqref{eqn:reg_growth}\Rightarrow\eqref{eqn:quad_growth}$ is the same as that of [15, Theorem 4.3],[19, Theorem 3.1]. Hence we omit the arguments.

Given the equality ${\rm prox}_{th}=(I+t\partial h)^{-1}$, it is clear that the subdifferential error bound condition (3.7) is related to an analogous property of the proximal mapping. This is the content of the following elementary result.

Consider a closed convex function $h\colon{\bf R}^{n}\to\overline{{\bf R}}$ with minimal value $h^{*}$ and let $S$ be its set of minimizers. Consider the conditions

If condition (3.8) holds, then so does condition (3.9) with $\widehat{L}=L+t$. Conversely, condition (3.9) implies condition (3.8) with $L=\widehat{L}$.

Suppose condition (3.8) holds and consider a point $x\in[h\leq h^{*}+\nu]$. Then clearly the inequality $h({\rm prox}_{th}(x))\leq h(x)\leq h^{*}+\nu$ holds. Taking into account the inclusion $t^{-1}(x-{\rm prox}_{th}(x))\in\partial h({\rm prox}_{th}(x))$, we obtain

as claimed. Conversely suppose condition (3.9) holds and fix a point $x\in[h\leq h^{*}+\nu]$. Then for any subgradient $v\in\partial h(x)$, equality ${\rm prox}_{th}(x+tv)=x$ holds. Hence, we obtain

where we have used the fact that the proximal mapping is 1-Lipschitz continuous. Since the subgradient $v\in\partial h(x)$ is arbitrary, the result follows. ∎

The final step is to relate the step sizes taken by the proximal gradient and the proximal point methods. The ensuing arguments are best stated in terms of monotone operators. To this end, observe that our running problem (3.1) is equivalent to solving the inclusion

More generally, consider monotone operators $F\colon{\bf R}^{n}\to{\bf R}^{n}$ and $G\colon{\bf R}^{n}\rightrightarrows{\bf R}$, meaning that $F$ and $G$ satisfy the inequalities $\langle v_{1}-v_{2},x_{1}-x_{2}\rangle\geq 0$ and $\langle F(x_{1})-F(x_{2}),x_{1}-x_{2}\rangle\geq 0$ for all $x_{i}\in{\bf R}^{n}$ and $v_{i}\in G(x_{i})$ with $i=1,2$. We now further assume that $G$ is maximal monotone, meaning that the graph ${\rm gph}\,G$ is not a proper subset of the graph of any other monotone operator. Along with the operator $G$ and a real $t>0$, we associate the resolvent

The mapping ${\rm prox}_{tG}\colon{\bf R}^{n}\to{\bf R}^{n}$ is then single-valued and nonexpansive ($1$-Lipschitz continuous [43, Theorem 12.12]). We aim to solve the inclusion

Equivalently we may write $x_{k+1}=x_{k}-t\mathcal{G}_{t}(x_{k})$ where $\mathcal{G}_{t}(x)$ is the prox-gradient mapping

Setting $F=\nabla f$, $G:=\partial g$, $\Phi:=\partial\varphi$ recovers the proximal gradient method for the problem (3.1).

The following key result shows that the step lengths of the Forward-Backward algorithm and those taken by the proximal point algorithm $z_{k+1}={\rm prox}_{t\Phi}(z_{k})$ are proportional.

Consider two maximal monotone operators $G\colon{\bf R}^{n}\rightrightarrows{\bf R}^{n}$ and $\Phi\colon{\bf R}^{n}\rightrightarrows{\bf R}^{n}$, with the difference $F:=\Phi-G$ that is single-valued. Then the inequality

Supposing that $F$ is in addition $\beta$-Lipschitz continuous, the inequalities hold:

Fix a point $x\in{\bf R}^{n}$ and a vector $v\in\Phi(x)$. Then clearly the inclusion

or equivalently $x={\rm prox}_{tG}((x-tF(x))+tv).$ Since the proximal mapping is nonexpansive, we deduce

Letting $v$ be the minimal norm element of $\Phi(x)$, we deduce the claimed inequality $\|\mathcal{G}_{t}(x)\|\leq{\rm dist}\left(0;\Phi(x)\right)$.

Now suppose that $F$ is $\beta$-Lipschitz continuous. Consider a point $x\in{\bf R}^{n}$ and define $z:=\mathcal{G}_{t}(x)$. Observe the chain of equivalences:

Define now the vector $w=F(x-tz)-F(x)$ and note $\|w\|\leq\beta t\|z\|$. Hence taking into account that resolvents are nonexpansive, we obtain

The two inequalities in (3.11) follow immediately. ∎

We now arrive at the main result of this section.

Consider a closed, convex function $g\colon{\bf R}^{n}\to\overline{{\bf R}}$ and a $C^{1}$-smooth convex function $f\colon{\bf R}^{n}\to{\bf R}$ with $\beta$-Lipschitz continuous gradient. Suppose that the function $\varphi:=f+g$ has a nonempty set $S$ of minimizers and consider the following conditions:

Then property (3.12) implies property (3.13) with $\gamma=(2\alpha^{-1}+t)(1+\beta t)$. Conversely, condition (3.13) implies condition (3.12) with any $\alpha\in(0,\gamma^{-1})$.

Suppose condition (3.12) holds. Then for any $x\in[\varphi\leq\varphi^{*}+\nu]$, we deduce

This establishes (3.13) with $\gamma=(2\alpha^{-1}+t)(1+\beta t)$. Conversely suppose (3.13) holds. Then for any $x\in[\varphi\leq\varphi^{*}+\nu]$ we deduce using Theorem 3.5 the inequality ${\rm dist}(x,S)\leq\gamma\|\mathcal{G}_{t}(x)\|\leq\gamma\cdot{\rm dist}(0,\partial\varphi(x))$. An application of Theorem 3.3 completes the proof. ∎

The following convergence result is now immediate from Theorem 3.2 and Corollary 3.6. Notice that the complexity bound matches (up to a constant) the linear rate of convergence of the proximal gradient method when applied to strongly convex functions.

Consider a closed, convex function $g\colon{\bf R}^{n}\to\overline{{\bf R}}$ and a $C^{1}$-smooth function $f\colon{\bf R}^{n}\to{\bf R}$ with $\beta$-Lipschitz continuous gradient. Suppose that the function $\varphi:=f+g$ has a nonempty set $S$ of minimizers and that the quadratic growth condition holds:

Then the proximal gradient method with $t\leq\beta^{-1}$ satisfies $\varphi(x_{k})-\varphi^{*}\leq\epsilon$ after at most

Quadratic growth in structured optimization

Recently, the authors of proved that the error bound condition holds under very mild assumptions, thereby explaining asymptotic linear convergence of the proximal gradient method often observed in practice. In this section, we aim to use the equivalence between the error bound condition and quadratic growth, established in Theorem 3.6, to streamline and illuminate the arguments in , while also extending their results to a wider setting. To this end, consider the problem

where $f\colon{\bf R}^{m}\to{\bf R}$ is convex and $C^{1}$-smooth, $g\colon{\bf R}^{n}\to\overline{{\bf R}}$ is closed and convex, and $A\colon{\bf R}^{n}\to{\bf R}^{m}$ is a linear mapping. We assume that $g$ is proper, meaning that its domain is nonempty. Consider now the Fenchel dual problem

By [40, Corollary 31.2.1(a)], the optimal values of the primal (4.1) and of the dual (4.2) are equal, and the dual optimal value is attained. To make progress, we assume that the dual problem (4.2) admits a strictly feasible point:

(dual nondegeneracy) $\quad 0\in A^{T}(\textrm{ri}\,\textrm{dom}\,f^{\star})+\textrm{ri}\,\textrm{dom}\,g^{\star}$,

Then by [40, Corollary 31.2.1(b)], the optimal value of the primal (4.1) is also attained. From the Kuhn-Tucker conditions [40, p. 333], any optimal solution of the dual coincides with $\nabla f(Ax)$ for any primal optimal solution $x$. In particular, the dual has a unique optimal solution and we will denote it by $\bar{y}$. Clearly, the inclusion $0\in\partial\Psi(\bar{y})$ holds. We now assume the mildly stronger property:

(dual strict complementarity) $\quad 0\in\textrm{ri}\,\partial\Psi(\bar{y})$.

Taken together, these two standard conditions (dual nondegeneracy and dual strict complementarity) immediately imply

where the last equality follows for example from [40, Theorem 6.6].

Let $S$ be the solution set of the primal problem (4.1). To elucidate the impact of the inclusion (4.3) on error bounds, recall that we must estimate the distance ${\rm dist}(x,S)$ for an arbitrary point $x$. To this end, the Kuhn-Tucker conditions again directly imply that $S$ admits the description

The inclusion (4.3), combined with [40, Theorem 6.7], guarantees that the relative interiors of the two sets $\partial g^{\star}(-A^{T}\bar{y})$ and $A^{-1}\partial f^{\star}(\bar{y})$ meet and hence by for any compact set $\mathcal{X}\subset{\bf R}^{n}$ there exists a constant $\kappa\geq 0$ satisfyingThis follows by applying [6, Corollary 4.5] first to the two sets $\partial g^{\star}(-A^{T}\bar{y})$ and $A^{-1}\partial f^{\star}(\bar{y})$, and then to the range of $A$ and $\partial f^{\star}(\bar{y})$.

This type of an inequality is often called linear regularity; see for example [6, Corollary 4.5]. The final assumption we need to deduce quadratic growth of $\varphi$, not surprisingly, is a quadratic growth condition on the individual functions $f$ and $g$ after tilt perturbations.

A closed convex function $h\colon{\bf R}^{n}\to\overline{{\bf R}}$ is firmly convex relative to a vector $v\in{\bf R}^{n}$ if the tilted function $h_{v}(x):=h(x)-\langle v,x\rangle$ satisfies the quadratic growth condition: for any compact set $\mathcal{X}\subset{\bf R}^{n}$ there is a constant $\alpha$ satisfying

We say that $h$ is firmly convex if $h$ is firmly convex relative to any vector $v\in{\bf R}^{n}$.

Note that not all convex functions are firmly convex; for example $f(x)=x^{4}$ is not firmly convex at $x=0$ relative to $v=0$. We are now ready to prove the main theorem of this section; note that unlike in , we do not require strong convexity of the function $f$. This generalization is convenient since it allows to capture “robust” formulations where $f$ is a translate of the Huber penalty or its asymmetric extensions.

Consider a closed, convex function $g\colon{\bf R}^{n}\to\overline{{\bf R}}$ and a $C^{1}$-smooth convex function $f\colon{\bf R}^{m}\to{\bf R}$. Suppose that the sum $\varphi(x):=f(Ax)+g(x)$ has a nonempty set $S$ of minimizer and let $\bar{y}$ be the optimal solution of the dual problem (4.2). Suppose the conditions hold:

(Compactness) The solution set $S$ is bounded.

(Dual nondegeneracy and strict complementarity) Assumptions 1 and 2.

(Quadratic growth of components) The functions $f$ and $g$ are firmly convex relative to $\bar{y}$ and $-A^{T}\bar{y}$, respectively.

Then the error bound condition holds with some parameters $(\gamma,\nu)$.

Since $S$ is compact, all sublevel sets of $\varphi$ are compact. Choose a number $\nu>0$ and set $\mathcal{X}:=[\varphi\leq\varphi^{*}+\nu]$ and $\mathcal{Y}=A(\mathcal{X})$. Let $\bar{x}\in S$ be arbitrary and note the equality $\bar{y}=\nabla f(A\bar{x})$. Then observing that $A\bar{x}$ minimizes $f(\cdot)-\langle\bar{y},\cdot\rangle$ and $\bar{x}$ minimizes $g(\cdot)+\langle A^{T}\bar{y},\cdot\rangle$, property (3) (Quadratic growth of components) guarantees that there exist constants $c,\alpha\geq 0$ such that

Letting $\kappa$ be the constant from (4.4) and setting $y:=Ax$ in (4.5), we deduce

Notice that firm convexity requires a certain inequality to hold on compact sets $\mathcal{X}$, rather than on sublevel sets. In any case, firm convexity is intimately tied to error bounds. For example, analogously to Theorem 3.3, one can show that $h$ is firmly convex relative to $v$ if and only if for any compact set $\mathcal{X}$ there exists a constant $L\geq 0$ satisfying

Indeed this is implicitly shown in the proof of Theorem [1, Theorem 3.3], for example. Moreover, the same argument as in Theorem 3.4 shows that $h$ is firmly convex relative to $v$ if and only if for any compact set $\mathcal{X}$ there exists a constant $\widehat{L}\geq 0$ satisfying

The class of firmly convex functions is large, including for example all strongly convex functions and polyhedral functions. More generally, all convex Piecewise Linear Quadratic (PLQ) functions [43, Section 10.20] are firmly convex, since their subdifferential graphs are finite unions of polyhedra. Indeed, the subclass of affinely composed PLQ penalties [43, Example 11.18] is ubiquitous in optimization. These are functions of the form

where $Z$ is a polyhedron, $B$ is a linear map, and $A$ is a positive-semidefinite matrix. For more details on the PLQ family, see . For example, the elastic net penalty , used for group detection, and the soft-insensitive loss , used for training Support Vector Machines, fall within this class.

Note that the assumptions of dual nondegeneracy and strict complementarity (Assumptions 1 and 2) were only used in the proof Theorem 4.2 to guarantee inequality (4.4). On the other hand, this inequality holds automatically if the subdifferentials $\partial g^{\star}(-A^{T}\bar{y})$ and $\partial f^{\star}(\bar{y})$ are polyhedral—a common situation.

Consider a convex PLQ function $g\colon{\bf R}^{n}\to\overline{{\bf R}}$ and a $C^{1}$-smooth convex function $f\colon{\bf R}^{m}\to{\bf R}$. Suppose that the function $\varphi(x):=f(Ax)+g(x)$ has a nonempty compact set $S$ of minimizers and that either $f$ is strictly convex or $f$ is PLQ. Then the error bound condition holds with some parameters $(\gamma,\nu)$.

Since $g$ is PLQ, the subdifferential $\partial g^{\star}$ at any point is polyhedral. Similarly, if $f$ is PLQ then $\partial f^{\star}$ is polyhedral at any point, while if $f$ is strictly convex, the subdifferential $\partial f^{\star}(\bar{y})$ is a singleton. Thus in all cases the inequality (4.4) holds and the proof proceeds as in Theorem 4.2. ∎

Firm convexity is preserved under separable sums.

Consider a family of functions $f_{i}\colon{\bf R}^{n_{i}}\to\overline{{\bf R}}$ for $i=1,\ldots,m$ with each $f_{i}$ firmly convex relative to some $v_{i}\in{\bf R}^{n_{i}}$. Then the separable function $f:{\bf R}^{n_{1}+\ldots+n_{m}}\to\overline{{\bf R}}$ defined by $f(x)=\sum^{m}_{i=1}f_{i}(x_{i})$ is firmly convex relative to the vector $(v_{1},\ldots,v_{n})$.

The proof is immediate from definitions. ∎

Moreover, firmly convex functions are preserved by the Moreau envelope.

Consider a function $h\colon{\bf R}^{n}\to\overline{{\bf R}}$ that is firmly convex relative to a vector $v$. Then the Moreau envelope $h^{t}$ is itself firmly convex relative to $v$.

Define the tilted functions $h_{v}(x):=h(x)-\langle v,x\rangle$ and $(h^{t})_{v}(x):=h^{t}(x)-\langle v,x\rangle$. Observe

Since firm convexity is invariant under translation of the domain, it is now sufficient to show that $(h_{v})^{t}$ is firmly convex relative to the zero vector. To this end, let $S$ be the set of minimizers of $h_{v}$, or equivalently the set of minimizers of $(h_{v})^{t}$. Since $h$ is firmly convex relative to $v$, for any compact set $\mathcal{Z}\subset{\bf R}^{n}$, there exists a constant $\widehat{L}\geq 0$ so that

we deduce ${\rm dist}(z,S)\leq\widehat{L}\cdot\|\nabla(h_{v})^{t}(z)\|$ for all $z\in\mathcal{Z}$, thereby completing the proof. ∎

In summary, all typical smooth penalties (e.g. square $l_{2}$-norm, logistic loss), polyhedral functions (e.g. $l_{1}$ and $l_{\infty}$-penalties, vapnik, hinge loss, check function, anisotropic total variation penalty), Moreau envelopes of polyhedral functions (e.g. Huber and quantile huber ), and general affinely composed PLQ penalties (e.g. soft-insensitive loss , elastic net ) are firmly convex. Another important example is the nuclear norm .

Prox-linear algorithm

We next step away from convex formulations (3.1), and consider the broad class of nonsmooth and nonconvex optimization problems

where $g\colon{\bf R}^{n}\to\overline{\bf R}$ is a proper closed convex function, $h\colon{\bf R}^{m}\to{\bf R}$ is a finite-valued convex function, and $c\colon{\bf R}^{n}\to{\bf R}^{m}$ is a $C^{1}$-smooth mapping. Since such problems are typically nonconvex, we seek a point $x$ that is only first-order stationary, meaning that the directional derivate of $\varphi$ at $x$ is nonnegative in all directions. The directional derivate of $\varphi$ is exactly the support function of the subdifferential set

and hence stationary of $\varphi$ at $x$ simply amounts to the inclusion $0\in\partial\varphi(x)$.

To specify the algorithm we study, define for any points $x,y\in{\bf R}^{n}$ the linearized function

and for any real $t>0$ consider the quadratic perturbation

Note that the function $\varphi(x;\cdot)$ is always convex, even though $\varphi$ typically is not convex. Let $x^{t}$ be the minimizer of the proximal subproblem

Suppose now that $h$ is $L$-Lipschitz continuous and the Jacobian $\nabla c(x)$ is $\beta$-Lipschitz continuous. It is then immediate that the linearized function $\varphi(x;\cdot)$ is quadratically close to $\varphi$ itself:

In particular, $\varphi_{t}(x;\cdot)$ is a quadratic upper estimator of $\varphi$ for any $t\leq(L\beta)^{-1}$. We now define the prox-gradient mapping in the natural way

It is easily verified that equality $\mathcal{G}_{t}(x)=0$ holds if and only if $x$ is stationary for $\varphi$. In this section, we consider the well-known prox-linear method (Algorithm 1), recently studied for example in ; see also for interesting variants. The ideas behind the method (and its trust-region versions) go back a long time, e.g. ; see for a historical discussion. We note that Algorithm 1 differs slightly from the one in in the step acceptance criterion.

Note that the prox-gradient method in Section 3 for the problem $\min_{x}f(x)+g(x)$ is an example of Algorithm 1 with the decomposition $c(x)=f(x)$ and $h(r)=r$. In this case, we have $L=1$. Observe also that we do not require $f$ to be convex anymore. Motivated by this observation, we now perform an analysis following the same strategy as for the proximal gradient method; there are important and surprising differences, however, both in the conclusions we make and in the proof techniques. We begin with the following lemma; the proof follows that of [34, Lemma 2.3.2].

For all points $x,y\in{\bf R}^{n}$, the inequality

Noting that the function $\varphi_{t}(x;y):=\varphi(x;y)+\frac{1}{2t}\|y-x\|^{2}$ is strongly convex in the variable $y$, we deduce

establishing (5.3). Inequality (5.4) follows by combining (5.2) and (5.3). Finally, we obtain inequality (5.5) from (5.4) by setting $y=x$. ∎

For simplicity, we assume that the constants $L$ and $\beta$ are known and we set $t\leq\frac{1}{L\beta}$ and $\sigma=\frac{1}{L\beta}$ in Algorithm 1, so that the line search always accepts the initial step. The more general setting with the backtracking line-search is entirely analogous. Observe now that the inequality $\eqref{eqn:descent2}$ yields the functional decrease guarantee

and hence we obtain the global convergence rate

where $\varphi^{*}:=\lim_{k\to\infty}\varphi(x_{k})$. Note moreover the prox-gradients $\mathcal{G}_{t}(x_{k})$ tend to zero, since their norms are square-summable. Thus after $2L\beta(\varphi(x_{1})-\varphi^{*})/\epsilon$ iterations, we can be sure that Algorithm 1 finds a point $x_{k}$ satisfying $\|\mathcal{G}_{t}(x_{k})\|^{2}\leq\epsilon$.

Does a small stepsize $\|\mathcal{G}_{t}(x)\|$ imply that $x$ is “nearly stationary”? This question is fundamental, and speaks directly to reliability of the termination criterion of Algorithm 1. We will see shortly (Theorem 5.3) that the answer is affirmative: if the quantity $\|\mathcal{G}_{t}(x)\|$ is small, then $x$ is close to a point that is nearly stationary for $\varphi$. Our key tool for establishing this result will be Ekeland’s variational principle.

Consider a closed function $f\colon{\bf R}^{n}\to\overline{{\bf R}}$ that is bounded from below. Suppose that for some $\epsilon>0$ and $\bar{x}\in{\bf R}^{n}$, we have $f(\bar{x})\leq\inf f+\epsilon$. Then for any $\rho>0$, there exists a point $\bar{u}$ satisfying

$\displaystyle\{\bar{u}\}=\operatornamewithlimits{argmin}_{u}\,\{f(u)+\rho\|u-\bar{u}\|\}$.

We can now explain the relation of the quantity $\|\mathcal{G}_{t}(x)\|$ to approximate stationarity. Aside from its immediate appeal, this result will play a central role both in the proof of Theorem 5.10 and in section 6.

Consider the convex-composite problem (5.1), where $h$ is $L$-Lipschitz continuous and the Jacobian $\nabla c$ is $\beta$-Lipschitz. Then for any real $t>0$, there exists a point $\hat{x}$ satisfying the properties

(point proximity) $\quad\|x^{t}-\hat{x}\|\leq\|x^{t}-x\|$,

(value proximity) $\quad\varphi(\hat{x})-\varphi(x^{t})\leq\frac{t}{2}(L\beta t+1)\|\mathcal{G}_{t}(x)\|^{2}$,

(near-stationarity) $\quad{\rm dist}\left(0;\partial\varphi(\hat{x})\right)\leq(3L\beta t+2)\|\mathcal{G}_{t}(x)\|$.

Define the function $\zeta(y):=\varphi(y)+\frac{1}{2}(L\beta+t^{-1})\|x-y\|^{2}$ and note that the inequality $\zeta(y)\geq\varphi_{t}(x,y)\geq\varphi_{t}(x,x^{t})$ holds for all $y\in{\bf R}^{n}$. Letting $\zeta^{*}$ be the infimal value of $\zeta$, we have

where the last inequality follows from (5.2). Define the constants $\epsilon:=L\beta\|x^{t}-x\|^{2}$ and $\rho:=L\beta\|x^{t}-x\|$. Applying Ekeland’s variational principle, we obtain a point $\hat{x}$ satisfying the inequalities $\zeta(\hat{x})\leq\zeta(x^{t})$ and $\|x^{t}-\hat{x}\|\leq\epsilon/\rho$, and the inclusion $0\in\partial\zeta(\hat{x})+\rho{\bf B}$. The proximity conditions $(\ref{it:proximity})$ and $(\ref{it:near_func})$ are immediate. To see near-stationarity $(\ref{it:near_stat})$, observe

Following the general outline of the paper and armed with Theorem 5.3, we now turn to linear convergence. To this end, let $\{x_{k}\}$ be a sequence generated by Algorithm 1 and suppose that $x^{*}$ is a limit point of $\{x_{k}\}$. Then inequality (5.4) (with $y=x^{*}$) and lower-semicontinuity of $\varphi$ immediately imply that the values $\varphi(x_{k})$ converge to $\varphi(x^{*})$. A standard argument also shows that $x^{*}$ is a stationary point of $\varphi$. Appealing to inequality (5.4) with $y=x^{*}$, we deduce

Defining $\gamma_{k}:=\max\{1,\|x_{k}-x^{*}\|/\|\mathcal{G}_{t}(x_{k})\|\}$ we deduce

Combining this inequality with (5.6) yields the geometric decay

Hence provided that $\gamma_{k}$ are bounded for all large $k$, the function values asymptotically converge Q-linearly. This motivates the following definition, akin to Definition 3.1.

We say that the error bound condition holds around a point $\bar{x}$ with parameter $\gamma>0$ if there exists a real number $\epsilon>0$ so that the inequality

Hence we arrive at the following convergence guarantee.

Consider the sequence $x_{k}$ generated by Algorithm 1 with $t\leq(L\beta)^{-1}$, and suppose that $x_{k}$ has some limit point $x^{*}$ around which the error bound condition holds with parameter $\gamma>0$. Define now the fraction

Then for all large $k$, function values converge Q-linearly

while the points $x_{k}$ asymptotically converge R-linearly: there exists an index $r$ such that the inequality

holds for all $k\geq 1$, where we set $C:=\frac{2}{{L\beta(1-\sqrt{1-(1-q)^{-1}})^{2}}}$.

Let $\epsilon,\nu>0$ be as in Definition 5.4. As observed above, the function values $\varphi(x_{k})$ converge to $\varphi(x^{*})$. Hence we may assume all the iterates $x_{k}$ lie in $[\varphi\leq\varphi(x^{*})+\nu]$. We aim now to show that if $x_{r}$ is sufficiently close to $x^{*}$, then all following iterates never leave the ball $B_{\epsilon}(x^{*})$. To this end, let $r$ be an index such that $x_{r}$ lies in $B_{\epsilon}(x^{*})$ and let $k\geq 1$ be the smallest index satisfying $x_{r+k}\notin B_{\epsilon}(x^{*})$. Defining $\zeta:=L\beta(2+L\beta)\gamma^{2}$ and using inequality (5.6), we deduce

Hence if $x_{r}$ lies in the ball $B_{\epsilon/2}(x^{*})$ and is sufficiently close to $x^{*}$ so that the right-hand-side is smaller than $\frac{\epsilon}{2}$, we obtain a contradiction. Thus there exists an index $r$ so that for all $k\geq r$, the iterates $x_{k}$ lie in $B_{\epsilon}(x^{*})$. The claimed Q-Linear rate follows immediately. To obtain the R-linear rate of the iterates, we argue as in the proof of Theorem 3.2:

where $D=\frac{\sqrt{2}}{{\sqrt{L\beta}(1-\sqrt{1-\zeta^{-1}})}}$. Squaring both sides, the result follows. ∎

Theorem 5.5 already marks a point of departure from the convex setting. Gradient descent for an $\alpha$-strongly convex function with $\beta$-Lipschitz gradient converges at the linear rate $1-\alpha/\beta$. Treating this setting as a special case of composite minimization with $g=0$ and $h(t)=t$, Theorem 5.5 guarantees the linear rate only on the order of $1-(\alpha/\beta)^{2}$. The difference is the lack of convexity; the linearizations $\varphi(x;\cdot)$ no longer lower bound the objective function $\varphi$, but only do so up to a quadratic deviation, thereby leading to a worse linear rate of convergence. We put this issue aside for the moment and will revisit it in section 6, where we will show that Algorithm 1 accelerates under a natural uniform quadratic growth condition. The ensuing discussion relating the error bound condition and quadratic growth will drive that analysis as well.

Following the pattern of the current work, we seek to interpret the error bound condition in terms of a natural property of the subdifferential $\partial\varphi$. It is tempting to proceed by showing that the step-lengths of Algorithm 1 are proportional to the step-lengths of the proximal point method $z_{k+1}\in(I+t\partial\varphi)^{-1}(z_{k})$, as in Theorem 3.5. The following theorem attempts to do just that. First, we establish inequality (5.7), showing that the norm $\|\mathcal{G}_{t}(x)\|$ is always bounded by twice the stationarity measure ${\rm dist}\left(0;\partial\varphi(x)\right)$. This is a direct analogue of (3.10), though we arrive at it through a different argument. Second, seeking to imitate the key inequality (3.11), we arrive at the inequality (5.8) below. The difficulty is that in this more general setting, the proportionality constant we need (left-hand-side of (5.8)) tends to $+\infty$ as $t$ tends to $(L\beta)^{-1}$ – the most interesting regime. We will circumvent this difficulty in the proof of our main result (Theorem 5.10) by a separate argument using Theorem 5.3; nonetheless, we believe the proportionality inequality (5.8) is interesting in its own right.

Consider the convex-composite problem (5.1). Then the inequality

Suppose in addition that $h$ is L-Lipschitz continuous and $\nabla c$ is $\beta$-Lipschitz continuous, and set $r:=L\beta$. Then for $t<r^{-1}$ and any point $x^{+}\in(I+t\partial\varphi)^{-1}(x)$ the inequality holds:

Fix a vector $v\in\partial\varphi(x)$. Then there exist vectors $z\in\partial g(x)$ and $w\in\partial h(c(x))$ satisfying $v=z+\nabla c(x)^{*}w$. Convexity yields

Appealing to the inequality $\varphi(x)\geq\varphi(x;x^{t})+\frac{1}{2t}\|x-x^{t}\|^{2}$, we deduce $\|v\|\cdot\|x^{t}-x\|\geq\frac{1}{2t}\|x^{t}-x\|^{2}$, completing the proof of (5.7).

Next, again fix a point $x$ and a subgradient $v=z+\nabla c(x)^{*}w$ for some $z\in\partial g(x)$ and $w\in\partial h(c(x))$. Then for all $y\in{\bf R}^{n}$ we successively deduce

Consider now a point $x^{+}\in(I+t\partial\varphi)^{-1}(x)$. Setting $r:=L\beta$ and replacing $x$ with $x^{+}$ in the above inequality, we deduce

Taking into account the strong convexity inequality $\varphi_{t}(x;x^{+})\geq\varphi_{t}(x;x^{t})+\frac{1}{2t}\|x^{+}-x^{t}\|^{2}$, we deduce

As alluded to prior to the theorem, the inequality (5.8) is meaningless for $t=1/L\beta$ – the most interesting case – since the left-hand-side becomes infinite. This seems unavoidable. In essence, the difficulty is that the base-point $x$ at which the lengths comparison is made remains fixed. To circumvent this difficulty, instead of relying on (5.8), we will prove our main result (Theorem 5.10) by using Theorem 5.3.

Next, we introduce the “natural property” of the subdifferential with which we will equate the error bound.

A set-valued mapping $F\colon{\bf R}^{n}\rightrightarrows{\bf R}^{m}$ is subregular at $(\bar{x},\bar{y})\in{\rm gph}\,F$ with constant $l>0$ if there exists a neighborhood $\mathcal{X}$ of $\bar{x}$ satisfying

Clearly, the error bound property around a stationary point $\bar{x}$ of $\varphi$ with parameter $\gamma$ amounts to subregularity of the prox-gradient mapping $\mathcal{G}_{t}(\cdot)$ at $(\bar{x},0)$ with constant $\gamma$. We aim to show that the error bound property is equivalent to subregularity of the subdifferential $\partial\varphi$ itself – a transparent notion closely tied to quadratic growth . We first record the following elementary lemma; we omit the proof, as it quickly follows from definitions.

Consider a set-valued mapping $S\colon{\bf R}^{n}\rightrightarrows{\bf R}^{m}$ and a pair $(\bar{x},0)\in{\rm gph}\,S$. Then if $S$ is subregular at $(\bar{x},0)$ with constant $l$, the mapping $(I+S^{-1})^{-1}$ is subregular at $(\bar{x},0)$ with constant $1+l$. Conversely, if $(I+S^{-1})^{-1}$ is subregular at $(\bar{x},0)$ with constant $\hat{l}$, then $S$ is subregular at $(\bar{x},0)$ with constant $1+\hat{l}$.

The following result analogous to Theorem 3.4 is now immediate.

Consider the convex-composite problem (5.1) and let $\bar{x}$ be a stationary point of $\varphi$. Consider the conditions

the subdifferential $\partial\varphi$ is subregular at $(\bar{x},0)$ with constant $l$.

the mapping $T:=t^{-1}\left(I-(I+t\partial\varphi)^{-1}\right)$ is subregular at $(\bar{x},0)$ with constant $\hat{l}$.

If condition $(\ref{eqn:subreg_sub2})$ holds, then so does condition $(\ref{eqn:subreg_prox2})$ with $\hat{l}=l+t$. Conversely, condition $(\ref{eqn:subreg_prox2})$ implies condition $(\ref{eqn:subreg_sub2})$ with $l=\hat{l}+t$.

Note first the equality $tT=(I+(t\partial\varphi)^{-1})^{-1}$ (equation (2.1)). Suppose that $\partial\varphi$ is $l$-subregular at $(\bar{x},0)$ with constant $l$. Then by Lemma 5.8, the mapping $tT$ is subregular at $(\bar{x},0)$ with constant $1+l/t$, and hence $T$ is subregular at $(\bar{x},0)$ with constant $l+t$, as claimed. The converse argument is analogous. ∎

We are now ready to prove the main result of this section.

Consider the convex-composite problem (5.1), where $h$ is $L$-Lipschitz continuous and the Jacobian $\nabla c$ is $\beta$-Lipschitz. Let $\bar{x}$ be a stationary point of $\varphi$ and consider the conditions:

the subdifferential $\partial\varphi$ is subregular at $(\bar{x},0)$ with constant $l$.

the prox-gradient mapping $\mathcal{G}_{t}(\cdot)$ is subregular at $(\bar{x},0)$ with constant $\hat{l}$.

If condition $(\ref{eqn:subreg_prox3})$ holds, then condition $(\ref{eqn:subreg_sub3})$ holds with $l:=2\hat{l}$. Conversely, if condition $(\ref{eqn:subreg_sub3})$ holds, then condition $(\ref{eqn:subreg_prox3})$ holds with $\hat{l}:=(3L\beta t+2)l+2t$.

Suppose first that the gradient mapping $\mathcal{G}_{t}(x)$ is subregular at $(\bar{x},0)$ with constant $\hat{l}$. Then by Theorems 5.6 and 5.9, we deduce for all $x$ near $\bar{x}$, the inequalities

Conversely, suppose that $\partial\varphi$ is subregular at $(\bar{x},0)$ with constant $l$. Fix a point $x$, and let $\hat{x}$ be the point guaranteed to exist by Theorem 5.3. For the purpose of establishing subregularity of $\mathcal{G}_{t}(\cdot)$, we can suppose the $x$ and $x_{t}$ are arbitrarily close to $\bar{x}$. Then $\hat{x}$ is close to $\bar{x}$, and we deduce

We conclude ${\rm dist}\left(x;(\partial\varphi)^{-1}(0)\right)\leq\left(l(3L\beta+2t^{-1})+2\right)\|x^{t}-x\|$, as claimed. ∎

Thus subregularity of the subdifferential $\partial\varphi$ and the error bound property are identical notions, with a precise relationship between the constants. Subdifferential subregularity at a minimizer, on the other hand, is equivalent to the natural quadratic growth condition when the functions in question are semi-algebraic (or more generally tame) or convex (Theorem 3.3). To the best of our knowledge, it is not yet known if such a relationship persists for all convex-composite functions.

Natural rate of convergence under tilt-stability

As we alluded to in section 5, the linear rate at which Algorithm 1 converges under the error bound condition is an order of magnitude slower than the rate that one would expect. In section 5, we highlighted the equivalence between the error bound condition and subregularity of the subdifferential, and their close relationships to quadratic growth. We will now show that when these properties hold uniformly relative to tilt-perturbations, the algorithm accelerates to the natural rate.

We say that $\bar{x}$ is a stable strong local minimizer with constant $\alpha>0$ of a function $f\colon{\bf R}^{n}\to\overline{{\bf R}}$ if there exists a neighborhood $\mathcal{X}$ of $\bar{x}$ so that for each vector $v$ near the origin, there is a point $x_{v}$ (necessarily unique) in $\mathcal{X}$, with $x_{0}=\bar{x}$, so that in terms of the perturbed functions $f_{v}:=f(\cdot)-\langle v,\cdot\rangle$, the inequality

This type of uniform quadratic growth is known to be equivalent to a number of influential notions, such as tilt-stability and strong metric regularity of the subdifferential . Here, we specialize the discussion to the convex-composite case, though the relationships hold much more generally. The following theorem appears in [19, Theorem 3.7, Proposition 4.5]; some predecessors were proved in .

Consider the convex-composite problem (5.1) and let $x^{*}$ be a local minimizer of $\varphi$. Then the following properties are equivalent.

(uniform quadratic growth) The point $x^{*}$ is a stable strong local minimizer of $\varphi$ with constant $\alpha$.

(local subdifferential convexity) There exists a neighborhood $\mathcal{X}$ of $x^{*}$ so that for any sufficiently small vector $v$, there is a point $x_{v}\in\mathcal{X}\cap(\partial\varphi)^{-1}(v)$ so that the inequality

(tilt-stability) There exists a neighborhood $\mathcal{X}$ of $x^{*}$ so that the mapping

is single-valued and $1/\alpha$-Lipschitz continuous on some neighborhood of the origin.

(strong regularity of the subdifferential) There exist neighborhoods $\mathcal{X}$ of $x^{*}$ and $\mathcal{V}$ of $\bar{v}=0$ so that the restriction $(\partial\varphi)^{-1}\colon\mathcal{V}\rightrightarrows\mathcal{X}$ is a single-valued $1/\alpha$-Lipschitz continuous mapping.