Efficiency of minimizing compositions of convex functions and smooth maps

Introduction

In this work, we consider the class of composite optimization problems

where $g\colon{\bf R}^{d}\to{\bf R}\cup\{\infty\}$ and $h\colon{\bf R}^{m}\to{\bf R}$ are closed convex functions and $c\colon{\bf R}^{d}\to{\bf R}^{m}$ is a smooth map. Regularized nonlinear least squares [55, Section 10.3] and exact penalty formulations of nonlinear programs [55, Section 17.2] are classical examples, while notable contemporary instances include robust phase retrieval and matrix factorization problems such as NMF . The setting where $c$ maps to the real line and $h$ is the identity function,

is now commonplace in large-scale optimization. In this work, we use the term additive composite minimization for (1.2) to distinguish it from the more general composite class (1.1).

The proximal gradient algorithm, investigated by Beck-Teboulle and Nesterov [54, Section 3], is a popular first-order method for additive composite minimization. Much of the current paper will center around the prox-linear method, which is a direct extension of the prox-gradient algorithm to the entire problem class (1.1). In each iteration, the prox-linear method linearizes the smooth map $c(\cdot)$ and solves the proximal subproblem:

for an appropriately chosen parameter $t>0$. The underlying assumption here is that the strongly convex proximal subproblems (1.3) can be solved efficiently. This is indeed reasonable in some circumstances. For example, one may have available specialized methods for the proximal subproblems, or interior-point points methods may be available for moderate dimensions $d$ and $m$, or it may be that case that computing an accurate estimate of $\nabla c(x)$ is already the bottleneck (see e.g. Example 3.5). The prox-linear method was recently investigated in , though the ideas behind the algorithm and of its trust-region variants are much older . The scheme (1.3) reduces to the popular prox-gradient algorithm for additive composite minimization, while for nonlinear least squares, the algorithm is closely related to the Gauss-Newton algorithm [55, Section 10].

Our work focuses on global efficiency estimates of numerical methods. Therefore, in line with standard assumptions in the literature, we assume that $h$ is $L$-Lipschitz and the Jacobian map $\nabla c$ is $\beta$-Lipschitz. As in the analysis of the prox-gradient method in Nesterov , it is convenient to measure the progress of the prox-linear method in terms of the scaled steps, called the prox-gradients:

A short argument shows that with the optimal choice $t=(L\beta)^{-1}$, the prox-linear algorithm will find a point $x$ satisfying $\|\mathcal{G}_{\frac{1}{L\beta}}(x)\|\leq\varepsilon$ after at most $\mathcal{O}(\frac{L\beta}{\varepsilon^{2}}(F(x_{0})-\inf F))$ iterations; see e.g. . We mention in passing that iterate convergence under the KŁ-inequality was recently shown in , while local linear/quadratic rates under appropriate regularity conditions were proved in . The contributions of our work are as follows.

(Prox-gradient and the Moreau envelope) The size of the prox-gradient $\|\mathcal{G}_{t}(x_{k})\|$ plays a basic role in this work. In particular, all convergence rates are stated in terms of this quantity. Consequently, it is important to understand precisely what this quantity entails about the quality of the point $x_{k}$ (or $x_{k+1}$). For additive composite problems (1.2), the situation is clear. Indeed, the proximal gradient method generates iterates satisfying $F^{\prime}(x_{k+1};u)\geq-2\|\mathcal{G}_{\frac{1}{\beta}}(x_{k})\|$ for all unit vectors $u$, where $F^{\prime}(x;u)$ is the directional derivative of $F$ at $x$ in direction $u$ [54, Corollary 1]. Therefore, a small prox-gradient $\|\mathcal{G}_{\frac{1}{\beta}}(x_{k})\|$ guarantees that $x_{k+1}$ is nearly stationary for the problem, since the derivative of $F$ at $x_{k+1}$ in any unit direction is nearly nonnegative. For the general composite class (1.1), such a conclusion is decisively false: the prox-linear method will typically generate an iterate sequence along which $F$ is differentiable with gradient norms $\|\nabla F(x_{k})\|$ uniformly bounded away from zero, in spite of the norms $\|\mathcal{G}_{\frac{1}{L\beta}}(x_{k})\|$ tending to zero.See the beginning of Section 4 for a simple example of this type of behavior. Therefore, one must justify the focus on the norm $\|\mathcal{G}_{\frac{1}{L\beta}}(x_{k})\|$ by other means. To this end, our first contribution is Theorem 4.5, where we prove that $\|\mathcal{G}_{\frac{1}{L\beta}}(x)\|$ is proportional to the norm of the true gradient of the Moreau envelope of $F$ — a well studied smooth approximation of $F$ having identical stationary points. An immediate consequence is that even though $x$ might not be nearly stationary for $F$, a small prox-gradient $\|\mathcal{G}_{\frac{1}{L\beta}}(x)\|$ guarantees that $x$ is near some point $\hat{x}$ (the proximal point), which is nearly stationary for $F$. In this sense, a small prox-gradient $\|\mathcal{G}_{\frac{1}{L\beta}}(x)\|$ is informative about the quality of $x$. We note that an earlier version of this conclusion based on a more indirect argument, appeared in [23, Theorem 5.3], and was used to derive linear/quadratic rates of convergence for the prox-linear method under suitable regularity conditions.

(Inexactness and first-order methods) For the general composite class (1.1), coping with inexactness in the proximal subproblem solves (1.3) is unavoidable. We perform an inexact analysis of the prox-linear method based on two natural models of inexactness: $(i)$ near-optimality in function value and $(ii)$ near-stationarity in the dual. Based on the inexact analysis, it is routine to derive overall efficiency estimates for the prox-linear method, where the proximal subproblems are themselves solved by first-order algorithms. Unfortunately, the efficiency estimates we can prove for such direct methods appear to either be unsatisfactory or the algorithms themselves appear not to be very practical (Appendix C). Instead, we present algorithms based on a smoothing technique.

(Complexity of first-order methods through smoothing) Smoothing is a common technique in nonsmooth optimization. The seminal paper of Nesterov , in particular, derives convergence guarantees for algorithms based on infimal convolution smoothing in structured convex optimization. In the context of the composite class (1.1), smoothing is indeed appealing. In the simplest case, one replaces the function $h$ by a smooth approximation and solves the resulting smooth problem instead.

We advocate running an inexact prox-linear method on the smooth approximation, with the proximal subproblems approximately solved by fast-gradient methods. To state the resulting complexity bounds, let us suppose that there is a finite upper bound on the operator norms $\|\nabla c(x)\|_{\textrm{op}}$ over all $x$ in the domain of $g$, and denote it by $\displaystyle\|\nabla c\|$.It is sufficient for the inequality $\|\nabla c\|\geq\|\nabla c(x_{k})\|_{\textrm{op}}$ to hold just along the iterate sequence $x_{k}$ generated by the method; in particular, $\|\nabla c\|$ does not need to be specified when initializing the algorithm. We prove that the outlined scheme requires at most

evaluations of $c(x)$, matrix vector products $\nabla c(x)v$, $\nabla c(x)^{T}w$, and proximal operations of $g$ and $h$ to find a point $x$ satisfying $\|\mathcal{G}_{\frac{1}{L\beta}}(x)\|\leq\varepsilon$. To the best of our knowledge, this is the best known complexity bound for the problem class (1.1) among first-order methods. Here, the symbol $\widetilde{\mathcal{O}}$ hides logarithmic terms.If a good estimate on the gap $F(x_{0})-\inf F$ is known, the logarithmic terms can be eliminated by a different technique, described in Appendix C.

(Complexity of finite-sum problems) Common large-scale problems in machine learning and high dimensional statistics lead to minimizing an average of a large number of functions. Consequently, we consider the finite-sum extension of the composite problem class,

where now each $h_{i}$ is $L$-Lipschitz and each $c_{i}$ is $C^{1}$-smooth with $\beta$-Lipschitz gradient. Clearly, the finite-sum problem is itself an instance of (1.1) under the identification $h(z_{i},\ldots,z_{m}):=\frac{1}{m}\sum_{i=1}^{m}h_{i}(z_{i})$ and $c(x):=(c_{1}(x),\ldots,c_{m}(x))$. In this structured context, however, the complexity of an algorithm is best measured in terms of the number of individual evaluations $c_{i}(x)$ and $\nabla c_{i}(x)$, dot-product evaluations $\nabla c_{i}(x)^{T}v$, and proximal operations ${\rm prox}_{th_{i}}$ and ${\rm prox}_{tg}$ the algorithm needs to find a point $x$ satisfying $\|\mathcal{G}_{\frac{1}{{L}{\beta}}}(x)\|\leq\varepsilon$. A routine computation shows that the efficiency estimate (1.4) of the basic inexact prox-linear method described above leads to the complexity

where abusing notation, we use ${\|\nabla c\|}$ to now denote an upper bound on $\|\nabla c_{i}(x)\|$ over all $i=1,\ldots,m$ and $x\in\operatorname*{dom\,}g$. We show that a better complexity in expectation is possible by incorporating (accelerated)-incremental methods for the proximal subproblems. The resulting randomized algorithm will generate a point $x$ satisfying

basic operations. Notice that the coefficient of $1/\varepsilon^{3}$ scales at worst as $\sqrt{m}$ — a significant improvement over (1.5). We note that a different complementary approach, generalizing stochastic subgradient methods, has been recently pursued by Duchi-Ruan .

(Acceleration) The final contribution of the paper concerns acceleration of the (exact) prox-linear method. For additive composite problems, with $c$ in addition convex, the prox-gradient method is suboptimal from the viewpoint of computational complexity . Accelerated gradient methods, beginning with Nesterov and extended by Beck-Teboulle achieve a superior rate in terms of function values. Later, Nesterov in [49, Page 11, item 2] showed that essentially the same accelerated schemes also achieve a superior rate of $\mathcal{O}((\frac{\beta}{\varepsilon})^{2/3})$ in terms of stationarity, and even a faster rate is possible by first regularizing the problem [49, Page 11, item 3].The short paper only considered smooth unconstrained minimization; however, a minor modification of the proof technique extends to the convex additive composite setting. Consequently, desirable would be an algorithm that automatically accelerates in presence of convexity, while performing no worse than the prox-gradient method on nonconvex instances. In the recent manuscript , Ghadimi and Lan described such a scheme for additive composite problems. Similar acceleration techniques have also been used for exact penalty formulations of nonlinear programs (1.1) with numerical success, but without formal justification; the paper is a good example.

In this work, we extend the accelerated algorithm of Ghadimi-Lan for additive composite problems to the entire problem class (1.1), with inexact subproblem solves. Assuming the diameter $M:=\operatorname*{diam}(\operatorname*{dom\,}g)$ is finite, the scheme comes equipped with the guarantee

where the constants $0\leq c_{1}\leq c_{2}\leq 1$ quantify “convexity-like behavior” of the composition. The inexact analysis of the proposed accelerated method based on functional errors is inspired by and shares many features with the seminal papers for convex additive composite problems (1.2).

The outline of the manuscript is as follows. Section 2 records basic notation that we use throughout the paper. In Section 3, we introduce the composite problem class, first-order stationarity, and the basic prox-linear method. Section 4 discusses weak-convexity of the composite function and the relationship of the prox-gradient with the gradient of the Moreau envelope. Section 5 analyzes inexact prox-linear methods based on two models of inexactness: near-minimality and dual near-stationarity. In Section 6, we derive efficiency estimates of first-order methods for the composite problem class, based on a smoothing strategy. Section 7 extends the aforementioned results to problems where one seeks to minimize a finite average of composite functions. The final Section 8 discusses an inertial prox-linear algorithm that is adaptive to convexity.

Notation

The notation we follow is standard. Throughout, we consider a Euclidean space, denoted by ${\bf R}^{d}$, with an inner product $\langle\cdot,\cdot\rangle$ and the induced norm $\|\cdot\|$. Given a linear map $A\colon{\bf R}^{d}\to{\bf R}^{l}$, the adjoint $A^{*}\colon{\bf R}^{l}\to{\bf R}^{d}$ is the unique linear map satisfying

The operator norm of $A$, defined as $\displaystyle\|A\|_{\rm op}:=\max_{\|u\|\leq 1}\|Au\|$, coincides with the maximal singular value of $A$ and satisfies $\|A\|_{\textrm{op}}=\|A^{*}\|_{\textrm{op}}$. For any map $F\colon{\bf R}^{d}\to{\bf R}^{m}$, we set

In particular, we say that $F$ is $L$-Lipschitz continuous, for some real $L\geq 0$, if the inequality $\operatorname*{lip\,}(F)\leq L$ holds. Given a set $Q$ in ${\bf R}^{d}$, the distance and projection of a point $x$ onto $Q$ are given by

respectively. The extended-real-line is the set $\overline{{\bf R}}:={\bf R}\cup\{\pm\infty\}$. The domain and the epigraph of any function $f\colon{\bf R}^{d}\to\overline{\bf R}$ are the sets

respectively. We say that $f$ is closed if its epigraph, $\textrm{epi}\,f$, is a closed set. Throughout, we will assume that all functions that we encounter are proper, meaning they have nonempty domains and never take on the value $-\infty$. The indicator function of a set $Q\subseteq{\bf R}^{d}$, denoted by $\delta_{Q}$, is defined to be zero on $Q$ and $+\infty$ off it.

Given a convex function $f\colon{\bf R}^{d}\to\overline{{\bf R}}$, a vector $v$ is called a subgradient of $f$ at a point $x\in\operatorname*{dom\,}f$ if the inequality

The set of all subgradients of $f$ at $x$ is denoted by $\partial f(x)$, and is called the subdifferential of $f$ at $x$. For any point $x\notin\operatorname*{dom\,}f$, we set $\partial f(x)$ to be the empty set. With any convex function $f$, we associate the Fenchel conjugate $f^{\star}\colon{\bf R}^{d}\to\overline{\bf R}$, defined by

If $f$ is closed and convex, then equality $f=f^{\star\star}$ holds and we have the equivalence

For any function $f$ and real $\nu>0$, the Moreau envelope and the proximal mapping are defined by

respectively. In particular, the Moreau envelope of an indicator function $\delta_{Q}$ is simply the map $x\mapsto\frac{1}{2{\nu}}{\rm dist}^{2}(x;Q)$ and the proximal mapping of $\delta_{Q}$ is the projection $x\mapsto\operatorname*{proj}(x;Q)$. The following lemma lists well-known regularization properties of the Moreau envelope.

Let $f\colon{\bf R}^{d}\to{\bf R}$ be a closed, convex function. Then $f_{\nu}$ is convex and $C^{1}$-smooth with

If in addition $f$ is $L$-Lipschitz, then the envelope $f_{\nu}(\cdot)$ is $L$-Lipschitz and satisfies

The expression $\nabla f_{\nu}(x)=\nu^{-1}(x-{\rm prox}_{\nu f}(x))=\nu^{-1}\cdot{\rm prox}_{(\nu f)^{*}}(x)$ can be found in [60, Theorem 31.5]. The inequality $\operatorname*{lip\,}(\nabla f_{\nu})\leq\frac{1}{\nu}$ then follows since the proximal mapping of a closed convex function is 1-Lipschitz [60, pp. 340]. The expression (2.3) follows from rewriting $f_{\nu}(x)=(f^{\star}+\frac{\nu}{2}\|\cdot\|^{2})^{\star}(x)=\sup_{z}\,\{\langle x,z\rangle-f^{\star}(z)-\frac{\nu}{2}\|z\|^{2}\}$ (as in e.g. [60, Theorem 16.4]) and noting that the domain of $f^{\star}$ is bounded in norm by $L$. Finally, to see that $f_{\nu}$ is $L$-Lipschitz, observe $\nabla f_{\nu}(x)\in\partial f({\rm prox}_{\nu f}(x))$ for all $x$, and hence $\|\nabla f_{\nu}(x)\|\leq\sup\{\|v\|:y\in{\bf R}^{d},v\in\partial f(y)\}\leq L$. ∎

The composite problem class

This work centers around nonsmooth and nonconvex optimization problems of the form

Throughout, we make the following assumptions on the functional components of the problem:

$g\colon{\bf R}^{d}\to\overline{{\bf R}}$ is a proper, closed, convex function;

$h\colon{\bf R}^{m}\to{\bf R}$ is a convex and $L$-Lipschitz continuous function:

$c\colon{\bf R}^{d}\to{\bf R}^{m}$ is a $C^{1}$-smooth mapping with a $\beta$-Lipschitz continuous Jacobian map:

The values $L$ and $\beta$ will often multiply each other; hence, we define the constant $\mu:=L\beta.$

It is instructive to consider some motivating examples fitting into the framework (3.1).

The most prevalent example of the composite class (3.1) is additive composite minimization. In this case, the map $c$ maps to the real line and $h$ is the identity function:

Such problems appear often in statistical learning and imaging, for example. Numerous algorithms are available, especially when $c$ is convex, such as proximal gradient methods and their accelerated variants . We will often compare and contrast techniques for general composite problems (3.1) with those specialized to this additive composite setting.

The composite problem class also captures nonlinear least squares problems with bound constraints:

Gauss-Newton type algorithm are often the methods of choice for such problems.

Consider a nonlinear optimization problem:

where $f\colon{\bf R}^{d}\to{\bf R}$ and $G\colon{\bf R}^{d}\to{\bf R}^{m}$ are smooth mappings and $\mathcal{K}\subseteq{\bf R}^{m}$ is a closed convex cone. An accompanying penalty formulation – ubiquitous in nonlinear optimization – takes the form

where $\theta_{\mathcal{K}}\colon{\bf R}^{m}\to{\bf R}$ is a nonnegative convex function that is zero only on $\mathcal{K}$ and $\lambda>0$ is a penalty parameter. For example, $\theta_{\mathcal{K}}(y)$ is often the distance of $y$ to the convex cone $\mathcal{K}$ in some norm. This is an example of (3.1) under the identification $c(x)=(f(x),G(x))$ and $h(f,G)=f+\lambda\theta_{\mathcal{K}}(G)$.

Often, one is interested in minimizing an error between a nonlinear process model $G(x)$ and observed data $b$ through a misfit measure $h$. The resulting problem takes the form

where $g$ may be a convex surrogate encouraging prior structural information on $x$, such as the $l_{1}$-norm, squared $l_{2}$-norm, or the indicator of the nonnegative orthant. The misfit $h=\|\cdot\|_{2}$, in particular, appears in nonlinear least squares. The $l_{1}$-norm $h=\|\cdot\|_{1}$ is used in the Least Absolute Deviations (LAD) technique in regression , Kalman smoothing with impulsive disturbances , and for robust phase retrieval .

Another popular class of misfit measures $h$ is a sum $h=\sum_{i}h_{\kappa}(y_{i})$ of Huber functions

The Huber function figures prominently in robust regression , being much less sensitive to outliers than the least squares penalty due to its linear tail growth. The function $h$ thus defined is smooth with $\operatorname*{lip\,}(\nabla h)\sim 1/\kappa$. Hence, in particular, the term $h(b-G(x))$ can be treated as a smooth term reducing to the setting of additive composite minimization (Example 3.1). On the other hand, we will see that because of the poor conditioning of the gradient $\nabla h$, methods that take into account the non-additive composite structure can have better efficiency estimates.

In industrial applications, one is often interested in functions that are available only implicitly. For example, function and derivative evaluations may require execution of an expensive simulation. Such problems often exhibit an underlying composite structure $h(c(x))$. The penalty function $h$ is known (and chosen) explicitly and is simple, whereas the mapping $c(x)$ and the Jacobian $\nabla c(x)$ might only be available through a simulation. Problems of this type are sometimes called grey-box minimization problems, in contrast to black-box minimization. The explicit separation of the hard-to-compute mapping $c$ and the user chosen penalty $h$ can help in designing algorithms. See for example Conn-Scheinberg-Vicente and Wild , and references therein.

2 First-order stationary points for composite problems

Let us now explain the goal of algorithms for the problem class (3.1). Since the optimization problem (3.1) is nonconvex, it is natural to seek points $x$ that are only first-order stationary. One makes this notion precise through subdifferentials (or generalized derivatives), which have a very explicit representation for our problem class. We recall here the relevant definitions, following the monographs of Mordukhovich and Rockafellar-Wets .

Consider an arbitrary function $f\colon{\bf R}^{d}\to\overline{\bf R}$ and a point $\bar{x}$ with $f(\bar{x})$ finite. The Fréchet subdifferential of $f$ at $\bar{x}$, denoted $\hat{\partial}f(\bar{x})$, is the set of all vectors $v$ satisfying

Thus the inclusion $v\in\hat{\partial}f(\bar{x})$ holds precisely when the affine function $x\mapsto f(\bar{x})+\langle v,x-\bar{x}\rangle$ underestimates $f$ up to first-order near $\bar{x}$. In general, the limit of Fréchet subgradients $v_{i}\in\hat{\partial}f(x_{i})$, along a sequence $x_{i}\to\bar{x}$, may not be a Fréchet subgradient at the limiting point $\bar{x}$. Hence, one formally enlarges the Fréchet subdifferential and defines the limiting subdifferential of $f$ at $\bar{x}$, denoted $\partial f(\bar{x})$, to consist of all vectors $v$ for which there exist sequences $x_{i}$ and $v_{i}$, satisfying $v_{i}\in\partial f(x_{i})$ and $(x_{i},f(x_{i}),v_{i})\to(\bar{x},f(\bar{x}),v)$. We say that $x$ is stationary for $f$ if the inclusion $0\in\partial f(x)$ holds.

For convex functions $f$, the subdifferentials $\hat{\partial}f(x)$ and $\partial f(x)$ coincide with the subdifferential in the sense of convex analysis (2.1), while for $C^{1}$-smooth functions $f$, they consist only of the gradient $\nabla f(x)$. Similarly, the situation simplifies for the composite problem class (3.1): the two subdifferentials $\hat{\partial}F$ and $\partial F$ coincide and admit an intuitive representation through a chain-rule [61, Theorem 10.6, Corollary 10.9].

For the composite function $F$, defined in (3.1), the Fréchet and limiting subdifferentials coincide and admit the representation

In summary, the algorithms we consider aim to find stationary points of $F$, i.e. those points $x$ satisfying $0\in\partial F(x)$. In “primal terms”, it is worth noting that a point $x$ is stationary for $F$ if and only if the directional derivative of $F$ at $x$ is nonnegative in every direction [61, Proposition 8.32]. More precisely, the equality holds:

where $F^{\prime}(x;v)$ is the directional derivative of $F$ at $x$ in direction $v$ [61, Definition 8.1].

3 The prox-linear method

The basic algorithm we rely on for the composite problem class is the so-called prox-linear method. To motivate this scheme, let us first consider the setting of additive composite minimization (3.2). The most basic algorithm in this setting is the proximal gradient method

Notice that an underlying assumption here is that the proximal map ${\rm prox}_{tg}$ is computable.

Convergence analysis of the prox-gradient algorithm derives from the fact that the function minimized in (3.4) is an upper model of $F$ whenever $t\leq\beta^{-1}$. This majorization viewpoint quickly yields an algorithm for the entire problem class (3.1). The so-called prox-linear algorithm iteratively linearizes the map $c$ and solves a proximal subproblem. To formalize the method, we use the following notation. For any points $z,y\in{\bf R}^{d}$ and a real $t>0$, define

Throughout the manuscript, we will routinely use the following estimate on the error in approximation $|F(z)-F(z;y)|$. We provide a quick proof for completeness.

For all $x,y\in\operatorname*{dom\,}g$, the inequalities hold:

Since $h$ is $L$-Lipschitz, we have |F(z)-F(z;y)|\leq L\big{\|}c(z)-\big{(}c(y)+\nabla c(y)(z-y)\big{)}\big{\|}. The fundamental theorem of calculus, in turn, implies

In particular, Lemma 3.2 implies that $F_{t}(\cdot;y)$ is an upper model for $F$ for any $t\leq\mu^{-1}$, meaning $F_{t}(z;y)\geq F(z)$ for all points $y,z\in\operatorname*{dom\,}g$. The prox-linear method, formalized in Algorithm 1, is then simply the recurrence $x_{k+1}=S_{t}(x_{k}).$ Notice that we are implicitly assuming here that the proximal subproblem (3.6) is solvable. We will discuss the impact of an inexact evaluation of $S_{t}(\cdot)$ in Section 5. Specializing to the additive composite setting (3.2), equality $S_{t}(x)={\rm prox}_{tg}(x-t\nabla c(x))$ holds and the prox-linear method reduces to the familiar prox-gradient iteration (3.4).

The convergence rate of the prox-linear method is best stated in terms of the prox-gradient mapping

Observe that the optimality conditions for the proximal subproblem $\min_{z}F_{t}(z;x)$ read

In particular, it is straightforward to check that with any $t>0$, a point $x$ is stationary for $F$ if and only if equality $\mathcal{G}_{t}(x)=0$ holds. Hence, the norm $\|\mathcal{G}_{t}(x)\|$ serves as a measure of “proximity to stationarity”. In Section 4, we will establish a much more rigorous justification for why the norm $\|\mathcal{G}_{t}(x)\|$ provides a reliable basis for judging the quality of the point $x$. Let us review here the rudimentary convergence guarantees of the method in terms of the prox-gradient, as presented for example in [23, Section 5]. We provide a quick proof for completeness.

Supposing $t\leq\mu^{-1}$, the iterates generated by Algorithm 1 satisfy

where we set $\displaystyle F^{*}:=\lim_{N\to\infty}F(x_{N})$.

Taking into account that $F_{t}(\cdot;x_{k})$ is strongly convex with modulus $1/t$, we obtain

Before continuing the algorithmic development, let us take a closer look at what the measure $\|\mathcal{G}_{t}(x)\|$ tells us about “near-stationarity” of the point $x$. Let us first consider the additive composite setting (3.2), where the impact of the measure $\|\mathcal{G}_{t}(x)\|$ on near-stationarity is well-understood. As discussed on page 1, the prox-linear method reduces to the prox-gradient recurrence

First-order optimality conditions for the proximal subproblem amount to the inclusion

Notice that the right-hand-side is exactly $\partial F(x_{k+1})$. Taking into account that $\nabla c$ is $\beta$-Lipschitz, we deduce

Thus the inequality $\|\mathcal{G}_{\frac{1}{\beta}}(x_{k})\|\leq\varepsilon/2$ indeed guarantees that $x_{k+1}$ is nearly stationary for $F$ in the sense that ${\rm dist}(0;\partial F(x_{k+1}))\leq\varepsilon$. Taking into account (3.3), we deduce the bound on directional derivative $F^{\prime}(x;u)\geq-\varepsilon$ in any unit direction $u$. With this in mind, the guarantee of Proposition 3.3 specialized to the prox-gradient method can be found for example in [54, Theorem 3].

The situation is dramatically different for the general composite class (3.1). When $h$ is nonsmooth, the quantity ${\rm dist}(0;\partial F(x_{k+1}))$ will typically not even tend to zero in the limit, in spite of $\|\mathcal{G}_{\frac{1}{\beta}}(x_{k})\|$ tending to zero. For example, the prox-linear algorithm applied to the univariate function $f(x)=|x^{2}-1|$ and initiated at $x>1$, will generate a decreasing sequence $x_{k}\to 1$ with $f^{\prime}(x_{k})\to 2$.Notice $f$ has three stationary points $\{-1,0,1\}$. Fix $y>1$ and observe that $x$ minimizes $f_{t}(\cdot;y)$ if and only if $\tfrac{y-x}{2ty}\in\partial|\cdot|(y^{2}-1+2y(x-y))$. Hence $\tfrac{y-x}{2ty}\cdot(y^{2}-1+2y(x-y))\geq 0$. The inequality $x\leq 1$ would immediately imply a contradiction. Thus the inequality $x_{0}>1$ guarantees $x_{k}>1$ for all $k$. The claim follows.

Thus we must look elsewhere for an interpretation of the quantity $\|\mathcal{G}_{\frac{1}{\mu}}(x_{k})\|$. We will do so by focusing on the Moreau envelope $x\mapsto F_{\frac{1}{2\mu}}(x)$ — a function that serves as a $C^{1}$-smooth approximation of $F$ with the same stationary points. We argue in Theorem 4.5 that the norm of the prox-gradient $\|\mathcal{G}_{\frac{1}{\mu}}(x_{k})\|$ is informative because $\|\mathcal{G}_{\frac{1}{\mu}}(x_{k})\|$ is proportional to the norm of the true gradient of the Moreau envelope $\|\nabla F_{\frac{1}{2\mu}}(x)\|$. Before proving this result, we must first establish some basic properties of the Moreau envelope, which will follow from weak convexity of the composite function $F$; this is the content of the following section.

We will need the following standard definition.

We say that a function $f\colon{\bf R}^{d}\to\overline{{\bf R}}$ is $\rho$-weakly convex on a set $U$ if for any points $x,y\in U$ and $a\in$, the approximate secant inequality holds:

It is well-known that for a locally Lipschitz function $f\colon{\bf R}^{d}\to{\bf R}$, the following are equivalent; see e.g. [17, Theorem 3.1].

(Weak convexity) $f$ is $\rho$-weakly convex on ${\bf R}^{d}$.

(Perturbed convexity) The function $f+\frac{\rho}{2}\|\cdot\|^{2}$ is convex on ${\bf R}^{d}$.

(Quadratic lower-estimators) For any $x,y\in{\bf R}^{d}$ and $v\in\partial f(x)$, the inequality

The function $h\circ c$ is $\rho$-weakly convex on ${\bf R}^{d}$ for some $\rho\in[0,\mu]$.

To simplify notation, set $\Phi:=h\circ c$. Fix two points $x,y\in{\bf R}^{d}$ and a vector $v\in\partial\Phi(x)$. We can write $v=\nabla c(x)^{*}w$ for some vector $w\in\partial h(c(x))$. Taking into account convexity of $h$ and the inequality $\|c(y)-c(x)-\nabla c(x)(y-x)\|\leq\frac{\beta}{2}\|y-x\|^{2}$, we then deduce

Weak convexity of $F$ has an immediate consequence on the Moreau envelope $F_{\nu}$.

Fix $\nu\in(0,1/\mu)$. Then the proximal map ${\rm prox}_{\nu F}(x)$ is well-defined and single-valued, while the Moreau envelope $F_{\nu}$ is $C^{1}$-smooth with gradient

Moreover, stationary points of $F_{\nu}$ and of $F$ coincide.

Fix $\nu\in(0,1/\mu)$. Lemma 4.2 together with [57, Theorem 4.4] immediately imply that ${\rm prox}_{\nu F}(x)$ is well-defined and single-valued, while the Moreau envelope $F_{\nu}$ is $C^{1}$-smooth with gradient given by (4.2). Equation (4.2) then implies that $x$ is stationary for $F_{\nu}$ if and only if $x$ minimizes the function $\varphi(z):=F(z)+\frac{1}{2\nu}\|z-x\|^{2}$. Lemma 4.2 implies that $\varphi$ is strongly convex, and therefore the unique minimizer $z$ of $\varphi$ is characterized by $\nu^{-1}(x-z)\in\partial F(z)$. Hence stationary points of $F_{\nu}$ and of $F$ coincide. ∎

Thus for $\nu\in(0,1/\mu)$, stationary points of $F$ coincide with those of the $C^{1}$-smooth function $F_{\nu}$. More useful would be to understand the impact of $\|\nabla F_{\nu}(x)\|$ being small, but not zero. To this end, observe the following. Lemma 4.3 together with the definition of the Moreau envelope implies that for any $x$, the point $\hat{x}:={\rm prox}_{\nu F}(x)$ satisfies

Thus a small gradient $\|\nabla F_{\nu}(x)\|$ implies that $x$ is near a point $\hat{x}$ that is nearly stationary for $F$.

2 Prox-gradient and the gradient of the Moreau envelope

The final ingredient we need to prove Theorem 4.5 is the following lemma [6, Theorem 2.4.1]; we provide a short proof for completeness.

Consider a closed function $f\colon{\bf R}^{d}\to\overline{\bf R}$ and suppose the inequality $f(x)-\inf f\leq\varepsilon$ holds for some point $x$ and real $\varepsilon>0$. Then for any $\lambda>0$, the inequality holds:

If $f$ is $\alpha$-strongly convex (possibly with $\alpha=0$), then the estimate improves to

Fix a point $\displaystyle y\in\operatornamewithlimits{argmin}_{z}\left\{f(z)+\frac{1}{2\lambda}\|z-x\|^{2}\right\}$. We deduce

Hence we deduce $\lambda^{-1}\|y-x\|\leq\sqrt{\frac{2\varepsilon}{\lambda}}$, as claimed. If $f$ is $\alpha$-strongly convex, then the function $z\mapsto f(z)+\frac{1}{2\lambda}\|z-x\|^{2}$ is $(\alpha+\lambda^{-1})$-strongly convex and therefore

The claimed inequality follows along the same lines. ∎

We can now quantify the precise relationship between the norm of the prox-gradient $\|\mathcal{G}_{t}(x)\|$ and the norm of the true gradient of the Moreau envelope $\|\nabla F_{\frac{t}{1+t\mu}}(x)\|$.

For any point $x$ and real constant $t>0$, the inequality holds:

To simplify notation, throughout the proof set

Notice that $\hat{x}$ is well-defined by Lemma 4.3.

We begin by establishing the first inequality in (4.4). For any point $z$, we successively deduce

where the first and third inequalities follow from (3.5) and the second from strong convexity of $F_{t}(\cdot;x)$.

Define the function $\zeta(z):=F(z)+\tfrac{\mu+t^{-1}}{2}\|z-x\|^{2}-\frac{1}{2t}\|{\bar{x}}-z\|^{2}$ and notice that $\zeta$ is convex by Lemma 4.2. Inequality (4.5) directly implies

Notice the relation, ${\rm prox}_{t\zeta}({\bar{x}})={\rm prox}_{\frac{tF}{1+t\mu}}(x)=\hat{x}$. Setting $\lambda:=t$ and $\varepsilon:=\mu\|{\bar{x}}-x\|^{2}$ and using Lemma 4.4 (convex case $\alpha=0$) with ${\bar{x}}$ in place of $x$, we conclude

Rearranging and using (4.2) yields the first inequality in (4.4), as claimed.

We next establish the second inequality in (4.4). The argument is in the same spirit as the previous part of the proof. For any point $z$, we successively deduce

where the first inequality follows from (3.5) and the second from $t^{-1}$-strong convexity of $z\mapsto F(z)+\tfrac{\mu+t^{-1}}{2}\|z-x\|^{2}$. Define now the function

Notice that $\Psi$ is strongly convex with parameter $\alpha:=2\mu$. Setting $\varepsilon:=\mu\|\hat{x}-x\|^{2}$ and $\lambda=t$, and applying Lemma 4.4 with $\hat{x}$ in place of $x$, we deduce

To simplify notation, set $\hat{z}:={\rm prox}_{t\Psi}(\hat{x})$. By definition of $\Psi$, equality

and therefore $2\mu(x-\hat{z})\in\partial F_{t}(\hat{z};x)$. Taking into account that $F_{t}(\cdot;x)$ is $t^{-1}$-strongly convex, we deduce

Rearranging and combining the estimate with (4.2), (4.7) yields the second inequality in (4.4). ∎

In the most important setting $t=1/\mu$, Theorem 4.5 reduces to the estimate

A closely related result has recently appeared in [23, Theorem 5.3], with a different proof, and has been extended to a more general class of Taylor-like approximations in . Combining (4.8) and (4.3) we deduce that for any point $x$, there exists a point $\hat{x}$ (namely $\hat{x}={\rm prox}_{F/2\mu}(x))$) satisfying

Thus if $\|\mathcal{G}_{1/\mu}(x)\|$ is small, the point $x$ is “near” some point $\hat{x}$ that is “nearly-stationary” for $F$. Notice that $\hat{x}$ is not computable, since it requires evaluation of ${\rm prox}_{F/2\mu}$. Computing $\hat{x}$ is not the point, however; the sole purpose of $\hat{x}$ is to certify that $x$ is approximately stationary in the sense of (4.9).

Inexact analysis of the prox-linear method

In practice, it is often impossible to solve the proximal subproblems $\min_{z}F_{t}(z;y)$ exactly. In this section, we explain the effect of inexactness in the proximal subproblems (3.6) on the overall performance of the prox-linear algorithm. By “inexactness”, one can mean a variety of concepts. Two most natural ones are that of $(i)$ terminating the subproblems based on near-optimality in function value and $(ii)$ terminating based on “near-stationarity”.

Which of the two criteria is used depends on the algorithms that are available for solving the proximal subproblems. If primal-dual interior-point methods are applicable, then termination based on near-optimality in function value is most appropriate. When the subproblems themselves can only be solved by first-order methods, the situation is less clear. In particular, if near-optimality in function value is the goal, then one must use saddle-point methods. Efficiency estimates of saddle-point algorithms, on the other hand, depend on the diameter of the feasible region, rather than on the quality of the initial iterate (e.g. distance of initial iterate to the optimal solution). Thus saddle-point methods cannot be directly warm-started, that is one cannot easily use iterates from previous prox-linear subproblems to speed up the algorithm for the current subproblem. Moreover, there is a conceptual incompatibility of the prox-linear method with termination based on functional near-optimality. Indeed, the prox-linear method seeks to make the stationarity measure $\|\mathcal{G}_{t}(x)\|$ small, and so it seems more fitting that the proximal subproblems are solved based on near-stationarity themselves. In this section, we consider both termination criteria. The arguments are quick modifications of the proof of Proposition 3.3.

We first consider the effect of solving the proximal subproblems up to a tolerance on function values. Given a tolerance $\varepsilon>0$, we say that a point $x$ is an $\varepsilon$-approximate minimizer of a function $f\colon{\bf R}^{d}\to\overline{\bf R}$ whenever the inequality holds:

Consider now a sequence of tolerances $\varepsilon_{k}\geq 0$ for $k=1,2\ldots,\infty$. Then given a current iterate $x_{k}$, an inexact prox-linear algorithm for minimizing $F$ can simply declare $x_{k+1}$ to be an $\varepsilon_{k+1}$-approximate minimizer of $F_{t}(\cdot;x_{k})$. We record this scheme in Algorithm 2.

Before stating convergence guarantees of the method, we record the following observation stating that the step-size of the inexact prox-linear method $\|x_{k+1}-x_{k}\|$ and the accuracy $\varepsilon_{k}$ jointly control the size of the true prox-gradient $\|\mathcal{G}_{t}(x_{k})\|$. As a consequence, the step-sizes $\|x_{k+1}-x_{k}\|$ generated throughout the algorithm can be used as surrogates for the true stationarity measure $\|\mathcal{G}_{t}(x_{k})\|$.

Suppose $x^{+}$ is an $\varepsilon$-approximate minimizer of $F_{t}(\cdot;x)$. Then the inequality holds:

Let $z^{*}$ be the true minimizer of $F_{t}(\cdot;x)$. We successively deduce

where the first inequality follows from the triangle inequality and the estimate $(a+b)^{2}\leq 2(a^{2}+b^{2})$ for any reals $a,b$, and the second inequality is an immediate consequence of strong convexity of the function $F_{t}(\cdot;x)$. ∎

The inexact prox-linear algorithm comes equipped with the following guarantee.

Supposing $t\leq\mu^{-1}$, the iterates generated by Algorithm 2 satisfy

where we set $\displaystyle F^{*}:=\operatornamewithlimits{liminf}_{k\to\infty}F(x_{k})$.

Let $x_{k}^{*}$ be the exact minimizer of $F_{t}(\cdot;x_{k})$. Note then the equality $\mathcal{G}_{t}(x_{k})=t^{-1}(x_{k}^{*}-x_{k})$. Taking into account that $F_{t}(\cdot;x_{k})$ is strongly convex with modulus $1/t$, we deduce

Then the inequality $t\leq\mu^{-1}$ along with (3.5) implies that $F_{t}(\cdot;x_{k})$ is an upper model of $F(\cdot)$ and therefore

Thus in order to maintain the rate afforded by the exact prox-linear method, it suffices for the errors $\{\varepsilon_{k}\}^{\infty}_{k=1}$ to be summable; e.g. set $\varepsilon_{k}\sim\frac{1}{k^{1+q}}$ with $q>0$.

2 Near-stationarity in the subproblems

In the previous section, we considered the effect of solving the proximal subproblems up to an accuracy in functional error. We now consider instead a model of inexactness for the proximal subproblems based on near-stationarity. A first naive attempt would be to consider a point $z$ to be $\varepsilon$-stationary for the proximal subproblem, $\min F_{t}(\cdot;x)$, if it satisfies

This assumption, however, is not reasonable since first-order methods for this problem do not produce such points $z$, unless $h$ is smooth. Instead, let us look at the Fenchel dual problem. To simplify notation, write the target subproblem $\min F_{t}(\cdot;x)$ as

under the identification $G(z)=g(z)+\frac{1}{2t}\|z-x\|^{2}$, $A=-\nabla c(x)$, and $b=c(x)-\nabla c(x)x$. Notice that $G$ is $t^{-1}$-strongly convex and therefore $G^{\star}$ is $C^{1}$-smooth with $t$-Lipschitz gradient. The Fenchel dual problem, after negation, takes the form [61, Example 11.41]:

Thus the dual objective function $\varphi$ is a sum of a smooth convex function $G^{\star}(A^{*}w)-\langle b,w\rangle$ and the simple nonsmooth convex term $h^{\star}$. Later on, when $x$ depends on an iteration counter $k$, we will use the notation $\varphi_{k}$, $G_{k}$, $A_{k}$, $b_{k}$ instead to make precise that these objects depend on $k$.

Typical first-order methods, such as prox-gradient and its accelerated variants can generate a point $w$ for the problem (5.4) satisfying

up to any specified tolerance $\varepsilon>0$. Such schemes in each iteration only require evaluation of the gradient of the smooth function $G^{\star}(A^{*}w)-\langle b,w\rangle$ along with knowledge of a Lipschitz constant of the gradient, and evaluation of the proximal map of $h^{\star}$. For ease of reference, we record these quantities here in terms of the original functional components of the composite problem (3.1). Since the proof is standard, we have placed it in Appendix A.

The following are true for all points $z$ and $w$ and real $t>0$:

Consequently, the gradient map \nabla\Big{(}G^{\star}\circ A^{*}-\langle\cdot,b\rangle\Big{)} is Lipschitz continuous with constant $t\|\nabla c(x)\|^{2}_{\textrm{op}}$ and admits the representation:

Thus, suppose we have found a point $w$ satisfying (5.5). How can we then generate a primal iterate $x^{+}$ at which to form the prox-linear subproblem for the next step? The following lemma provides a simple recipe for doing exactly that. It shows how to generate from $w$ a point that is a true minimizer to a slight perturbation of the proximal subproblem.

Let $\varphi$ be the function defined in (5.4). Fix a point $w\in\operatorname*{dom\,}\varphi$ and a vector $\zeta\in\partial\varphi(w)$. Then the point $\bar{x}:=\nabla G^{\star}(A^{*}w)$ is the true minimizer of the problem

Appealing to the chain rule, $\partial\varphi(w)=A\nabla G^{\star}(A^{*}w)-b+\partial h^{\star}(w)$, we deduce

The relation (2.2) then implies $w\in\partial h(\zeta+b-A\bar{x})$. Applying $A^{*}$ to both sides and rearranging yields

where the last inclusion follows from applying (2.2) to $G$. The right-hand-side is exactly the subdifferential of the objective function in (5.9) evaluated at $\bar{x}$. The result follows. ∎

This lemma directly motivates the following inexact extension of the prox-linear algorithm (Algorithm 3), based on dual near-stationary points.

Algorithm 3 is stated in a way most useful for convergence analysis. On the other hand, it is not very explicit. To crystallize the ideas, let us concretely describe how one can implement step $k$ of the scheme. First, we find a point $w_{k+1}$ that is $\varepsilon_{k+1}$-stationary for the dual problem (5.4). More precisely, we find a pair $(w_{k+1},\zeta_{k+1})$ satisfying $\zeta_{k+1}\in\partial\varphi_{k}(w_{k+1})$ and $\|\zeta_{k+1}\|\leq\varepsilon_{k+1}$. We can achieve this by a proximal gradient method (or its accelerated variants) on the dual problem (5.4). Then combining Lemma 5.4 with equation (5.7), we conclude that we can simply set

We record this more explicit description of Algorithm 3 in Algorithm 4. The reader should keep in mind that even though Algorithm 4 is more explicit, the convergence analysis we present will use the description in Algorithm 3.

Before stating convergence guarantees of the method, we record the following observation stating that the step-size $\|x_{k+1}-x_{k}\|$ and the error $\varepsilon_{k+1}$ jointly control the stationarity measure $\|\mathcal{G}_{t}(x_{k})\|$. In other words, one can use the step-size $\|x_{k+1}-x_{k}\|$, generated throughout the algorithm, as a surrogate for the true stationarity measure $\|\mathcal{G}_{t}(x_{k})\|$.

Suppose $x^{+}$ is a minimizer of the function

for some vector $\zeta$. Then for any real $t>0$, the inequality holds:

Let $z^{*}$ be the true minimizer of $F_{t}(\cdot;x)$. We successively deduce

where the first inequality follows from the triangle inequality and the estimate $(a+b)^{2}\leq 2(a^{2}+b^{2})$ for any reals $a,b$, the second inequality is an immediate consequence of strong convexity of the function $F_{t}(\cdot;x)$, and the third follows from Lipschitz continuity of $h$. ∎

Theorem 5.6 explains the convergence guarantees of the method; c.f. Proposition 3.3.

Supposing $t\leq\mu^{-1}$, the iterates generated by Algorithm 3 satisfy

where we set $\displaystyle F^{*}:=\operatornamewithlimits{liminf}_{k\to\infty}F(x_{k})$.

Since the point $x_{k+1}$ minimizes the $\frac{1}{t}$-strongly convex function in (5.10), we deduce

Summing along the indices $j=0,\ldots,N-1$ yields

In particular, to maintain the same rate in $N$ as the exact prox-linear method in Proposition 3.3, we must be sure that the sequence $\varepsilon_{k}$ is summable. Hence, we can set $\varepsilon_{k}\sim\frac{1}{k^{1+q}}$ for any $q>0$.

Overall complexity for the composite problem class

In light of the results of Section 5, we can now use the inexact prox-linear method to derive efficiency estimates for the composite problem class (3.1), where the proximal subproblems are themselves solved by first-order methods. As is standard, we will assume that the functions $h$ and $g$ are prox-friendly, meaning that ${\rm prox}_{th}$ and ${\rm prox}_{tg}$ can be evaluated. Given a target accuracy $\varepsilon>0$, we aim to determine the number of basic operations – evaluations of $c(x)$, matrix-vector multiplications $\nabla c(x)v$ and $\nabla c(x)^{*}w$, and evaluations of ${\rm prox}_{th}$, ${\rm prox}_{tg}$ – needed to find a point $x$ satisfying $\|{\mathcal{G}}_{t}(x)\|\leq\varepsilon$. To simplify the exposition, we will ignore the cost of the evaluation $c(x)$, as it will typically be dominated by the cost of the matrix-vector products $\nabla c(x)v$ and $\nabla c(x)^{*}w$.

To make progress, in this section we also assume that we have available a real value, denoted $\|\nabla c\|$, satisfying

In particular, we assume that the right-hand-side is finite. Strictly speaking, we only need the inequality $\|\nabla c\|\geq\|\nabla c(x_{k})\|_{\textrm{op}}$ to hold along an iterate sequence $x_{k}$ generated by the inexact prox-linear method. This assumption is completely expected: even when $c$ is a linear map, convergence rates of first-order methods for the composite problem (3.1) depend on some norm of the Jacobian $\nabla c$.

The strategy we propose can be succinctly summarized as follows:

(Smoothing+prox-linear+fast-gradient) We will replace $h$ by a smooth approximation (Moreau envelope), with a careful choice of the smoothing parameter. Then we will apply an inexact prox-linear method to the smoothed problem, with the proximal subproblems approximately solved by fast-gradient methods.

The basis for the ensuing analysis is the fast-gradient method of Nesterov for minimizing convex additive composite problems. The following section recalls the scheme and records its efficiency guarantees, for ease of reference.

This section discusses a scheme from that can be applied to any problem of the form

where $f\colon{\bf R}^{d}\to{\bf R}$ is a convex $C^{1}$-smooth function with $L_{f}$-Lipschitz gradient and $p\colon{\bf R}^{d}\to\overline{\bf R}$ is a closed $\alpha$-strongly convex function ($\alpha\geq 0$). The setting $\alpha=0$ signifies that $p$ is just convex.

We record in Algorithm 5 the so-called “fast-gradient method” for such problems [54, Accelerated Method].

The method comes equipped with the following guarantee [54, Theorem 6].

Let $x^{*}$ be a minimizer of $f^{p}$ and suppose $\alpha>0$. Then the iterates $x_{j}$ generated by Algorithm 5 satisfy:

Let us now make a few observations that we will call on shortly. First, each iteration of Algorithm 5 only requires two gradient computations, $\nabla f(y_{j})$ in (6.3) and $\nabla f(x_{j+1})$ in (6.4), and two proximal operations, ${\rm prox}_{p/L_{f}}$ in (6.3) and ${\rm prox}_{p}$ in (6.2).

Secondly, let us translate the estimates in Theorem 6.1 to estimates based on desired accuracy. Namely, simple arithmetic shows that the inequality

holds as soon as the number of iterations $j$ satisfies

Let us now see how we can modify the scheme slightly so that it can find points $x$ with small subgradients. Given a point $x$ consider a single prox-gradient iteration $\hat{x}:={\rm prox}_{\frac{p}{L_{f}}}\left(x-\tfrac{1}{L_{f}}\nabla f(x)\right)$. Then we successively deduce

where the first inequality is (4.1) and the second is the descent guarantee of the prox-gradient method (e.g. [54, Theorem 1]). Thus the inequality $f^{p}(x)-f^{p}(x^{*})\leq\varepsilon^{2}/(8L_{f})$ would immediately imply ${\rm dist}(0;\partial f^{p}(\hat{x}))\leq\varepsilon$. Therefore, let us add an extra prox-gradient step $\hat{x}_{j}:={\rm prox}_{\frac{p}{L_{f}}}\left(x_{j}-\tfrac{1}{L_{f}}\nabla f(x_{j})\right)$ to each iteration of Algorithm 5. Appealing to the linear rate in (6.5), we then deduce that we can be sure of the inequality

as soon as the number of iterations $j$ satisfies

With this modification, each iteration of the scheme requires two gradient evaluations of $f$ and three proximal operations of $p$.

2 Total cost if hℎh is smooth

In this section, we will assume that $h$ is already $C^{1}$-smooth with the gradient having Lipschitz constant $L_{h}$, and calculate the overall cost of the inexact prox-linear method that wraps a linearly convergent method for the proximal subproblems. As we have discussed in Section 5, the proximal subproblems can either be approximately solved by primal methods or by dual methods. The dual methods are better adapted for a global analysis, since the dual problem has a bounded domain; therefore let us look first at that setting.

We consider the near-stationarity model of inexactness as in Section 5.2. Namely, let us compute the total cost of Algorithm 4, when each subproblem $\min_{w}\varphi_{k}(w)$ is approximately minimized by the fast-gradient method (Algorithm 5). In the notation of Section 6.1, we set $f(w)=G_{k}^{\star}(A^{*}_{k}w)-\langle b_{k},w\rangle$ and $p=h^{\star}$. By Lemma 5.3, the function $f$ is $C^{1}$-smooth with gradient having Lipschitz constant $L_{f}:=t\|\nabla c(x_{k})\|^{2}_{\textrm{op}}$. Since $\nabla h$ is assumed to be $L_{h}$-Lipschitz, we deduce that $h^{\star}$ is $\frac{1}{L_{h}}$-strongly convex. Notice moreover that since $h$ is $L$-Lipschitz, any point in $\operatorname*{dom\,}h^{\star}$ is bounded in norm by $L$; hence the diameter of $\operatorname*{dom\,}h^{\star}$ is at most $2L$. Let us now apply Algorithm 5 (with the extra prox-gradient step) to the problem $\min_{w}\varphi_{k}(w)=f(w)+p(w)$. According to the estimate (6.6), we will be able to find the desired point $w_{k+1}$ satisfying ${\rm dist}(0;\partial\varphi_{k}(w_{k+1})))\leq\varepsilon_{k+1}$ after at most

iterations of the fast-gradient method. According to Lemma 5.3, each gradient evaluation $\nabla f$ requires two-matrix vector multiplications and one proximal operation of $g$, while the proximal operation of $p$ amounts to a single proximal operation of $h$. Thus each iteration of Algorithm 5, with the extra prox-gradient step requires $9$ basic operations. Finally to complete step $k$ of Algorithm 5, we must take one extra proximal map of $g$. Hence the number of basic operations needed to complete step $k$ of Algorithm 5 is $9\times$(equation (6.7))$+1$, where we set $t=1/\mu$.

Let us now compute the total cost across the outer iterations $k$. Theorem 5.6 shows that if we set $\varepsilon_{k}=\frac{1}{Lk^{2}}$ in each iteration $k$ of Algorithm 4, then after $N$ outer iterations we are guaranteed

after at most $\mathcal{N}(\varepsilon):=\left\lceil\frac{4\mu(F(x_{0})-F^{*}+8)}{\varepsilon^{2}}\right\rceil$ outer-iterations and therefore after