A Relative Inexact Proximal Gradient Method With an Explicit Linesearch

In this paper, our focus is on addressing nonsmooth convex optimization problems characterized by the following formulation:

where $\mathbbm{E}$ represents a finite-dimensional Euclidean space. The function $g:\mathbbm{E}\to\overline{\mathbbm{R}}:=\mathbbm{R}\cup\{+\infty\}$ is a nonsmooth, proper, and lower semicontinuous convex function. The function $f:\mathbbm{E}\to\mathbbm{R}$ is a continuously differentiable and convex function. Throughout the paper, we denote the optimal value and solution set of problem (1) by $F_{*}$ and $S_{*}$, respectively. From now on, we assume that $S_{*}\neq\emptyset$.

Proximal gradient methods effectively solve optimization problems such as in (1). The main step in the proximal gradient method involves evaluating the proximal operator ${\bf prox}_{g}:\mathbbm{E}\to{\bf dom\,}g:=\{x\in\mathbbm{E}\mid g(x)<+\infty\}$ defined by:

where the norm, $\|\cdot\|$, is induced by the inner product of $\mathbbm{E}$, $\langle\cdot,\cdot\rangle$, as $\|\cdot\|:=\sqrt{\langle\cdot,\cdot\rangle}$. The proximal operator is well-known as a full-domain, firmly nonexpansive operator. These useful properties, together with the descent property of the gradient step, establish the foundation for the convergence and complexity for proximal gradient iterations.

Proximal Gradient Method (PGM) Let $x_{0}\in{\bf dom\,}g$. Compute $\gamma_{k}>0$ and $$\bar{x}_{k}:={\bf prox}_{\gamma_{k}g}\left(x_{k}-\gamma_{k}\nabla f(x_{k})\right).$$ (3) Choose $\beta_{k}\in(0,1]$ and compute $$x_{k+1}:=x_{k}+\beta_{k}(\bar{x}_{k}-x_{k}).$$ (4)

The coefficients $\gamma_{k}$ and $\beta_{k}$, referred to as stepsizes, can be determined based on backtracking linesearch procedures. Such strategies are essential whenever the global $L$-Lipschitz continuity of $f$ fails or even when computing an acceptable upper bound for $L$ is challenging. This situation is often encountered in numerous applications; for instance, in inverse problems based on Banach norms Bredies:2009 ; Schuster:2012 or Bregman distances such as the Kullback-Leibler divergence Salzo:2014 ; Bonettini:2012 ; BelloCruz:2016a . Moreover, even when $L$ is known, linesearches may allow for longer steps toward the solution by using local information at every iteration.

There are several possible choices for these stepsizes, each impacting the algorithm’s performance in different ways; see, for instance, Salzo:2017a ; BelloCruz:2016a ; BelloCruz:2016c ; Bello-Cruz:2021 . It is important to note that in order to compute the stepsize $\gamma_{k}$ using a backtracking linesearch at each iteration $k$, the proximal operator may need to be evaluated multiple times within the procedure. Conversely, the stepsize $\beta_{k}$ can be selected by evaluating the proximal operator only once per iteration. In this context, we will refer to explicit linesearch to describe a backtracking procedure that determines $\beta_{k}$ after setting $\gamma_{k}$ as a constant for all $k$. These explicit strategies are particularly advantageous, especially in cases where evaluating the proximal operator is challenging. The function $g$ is often complex enough that the corresponding proximal operator lacks an analytical solution. In such cases, an ad-hoc algorithm should be employed to evaluate the proximal operator inexactly. For instance, consider $\mathbb{E}=\mathbbm{R}^{n}$, and let $g:\mathbbm{R}^{n}\to\mathbbm{R}$ be defined as

with $\lambda>0$, a form encountered in sparse regression problems with grouping, as discussed in Zhong:2012 . Similarly, in the context of matrix factorization, consider $\mathbb{E}=\mathbbm{R}^{n\times m}$ for the CUR-like factorization optimization problem Barre:2022 ; JMLR:v12:mairal11a , where the goal is to approximate a matrix $W\in\mathbbm{R}^{m\times n}$ with $X\in\mathbbm{R}^{n\times m}$ having sparse rows and columns. In this case, $g:\mathbbm{R}^{n\times m}\to\mathbbm{R}$ is given by

which will be considered in the numerical illustrations of this paper. For further examples and discussions, see BelloCruz:2017a ; Bello-Cruz:2023 ; Salzo:2012 ; Villa:2013 ; Schmidt:2011 ; Jiang:2012 ; Millan:2019 ; Barre:2022 . Of course, there are rare cases when the exact analytical solution of the proximal operator is available, such as when $g:\mathbbm{R}^{n}\to\mathbbm{R}$ as $g(x)=\|x\|_{1}$ or the indicator function of a simple convex and closed set, see, for instance, Beck:2009 ; Combettes:2005 .

Consequently, in practice, the evaluation of the proximal operator is often done inexactly. A basic inexactness criterion is to approximately evaluate the proximal operator using an exogenous sequence of error tolerance which, in general, must be summable in order to guarantee the convergence of the proximal iterations. Such a diminishing sequence is a priori chosen without using any information that may be available along with the iterations. Usually, the restrictive summability condition forces the solution of the proximal subproblem to be increasingly accurate, often more than necessary; see, for instance, Jiang:2012 ; Salzo:2012 ; Aujol:2015 ; Villa:2013 ; Schmidt:2011 . In the past two decades, relative error criteria have been considered as an effective and practical way of controlling the inexactness in solving proximal subproblems of several algorithms, including FISTA, ADMM, augmented Lagrangian, and Douglas-Rachford methods; refer to Eckstein:2013 ; Eckstein:2018 ; Alves:2020 ; Adona:2019 ; Adona:2020 for examples. Relative error criteria are often easy to verify in practice and has the advantage of exploring the available information at a specific iteration, being, therefore, an interesting alternative to the aforementioned exogenous sequences.

In this paper, we propose and analyze an inexact proximal gradient method for solving problem (1). We propose a novel relative inexactness criterion for solving the proximal subproblems which in some sense ressembles the ideas of relative error criteria introduced in Monteiro:2010 ; Solodov:1999a , but adds some new elements in order to control the objective function on the inexact solution. The proposed scheme requires only one inexact solution of the proximal subproblem per iteration, and the stepsizes are computed through a relaxed explicit linesearch procedure that takes into account the residuals obtained in the proximal subproblem and enables the iteration to address non-Lipschitz optimization problems effectively. We show that the sequence generated by our method converges to a solution of problem (1). Moreover, we establish its iteration-complexity in terms of both the function values and the residues associated to an approximate stationary solution. We also present some numerical experiments to illustrate the performance of the proposed method.

The paper is structured as follows: Section 2 presents definitions, basic facts, and auxiliary results. In Section 3, we introduce the inexact proximal gradient method with an explicit linesearch (IPG-ELS) and establish some of its fundamental properties. Section 4 establishes the iteration-complexity bounds of the IPG-ELS method in terms of functional values and a residual associated with the stationary condition for problem (1). Additionally, the full convergence of the sequence generated by the IPG-ELS method is discussed in this section. Some numerical experiments illustrating the behavior of the proposed scheme are reported in Section 5. Finally, concluding remarks are provided in Section 6.

In this section, we present some preliminary material and notations that will be used throughout this paper.

Let $g:\mathbbm{E}\to\overline{\mathbbm{R}}$ be a proper, lower semicontinuous, and convex function. For a given $\varepsilon\geq 0$, the $\varepsilon$-subdifferential of $g$ at $x\in{\bf dom\,}g=\{x\in\mathbbm{E}\mid g(x)<+\infty\}$, denoted by $\partial_{\varepsilon}g(x)$, is defined as

When $x\notin{\bf dom\,}g$, we define $\partial_{\varepsilon}g(x)=\emptyset$. Any element $v\in\partial_{\varepsilon}g(x)$ is called an $\varepsilon$-subgradient. If $\varepsilon=0$, then $\partial_{0}g(x)$ becomes the classical subdifferential of $g$ at $x$, denoted by $\partial g(x)$. It follows immediately from (5) that

We present two useful auxiliary results for $\partial_{\varepsilon}g$. The first one is the closedness of the graph of $\partial_{\varepsilon}g$ and the second is the so-called transportation formula; see Propositions 4.1.1 and 4.2.2 of Hiriart-Urruty:1993 .

We now introduce a concept of approximate stationary solution to problem (1). First, note that $\bar{x}$ is a solution to problem (1) if and only if $0\in\nabla f(\bar{x})+\partial g(\bar{x})$. The concept of approximate stationary solution relaxes this inclusion by introducing a residual $v$ and enlarging $\partial g$ using $\partial_{\varepsilon}g$.

Next, we recall the definition of quasi-Fejér convergence, which is an important and well-known tool for establishing full convergence of gradient and proximal point type methods.

The following result presents the main properties of quasi-Fejér convergent sequences; see Theorem $2.6$ of Bauschke:1996 .

We conclude the section with a basic inequality that will be used in the next sections.

In this section, we introduce the inexact proximal gradient method with an explicit linesearch and establish some basic properties.

Recall that, given $x_{k}\in\mathbbm{E}$, the exact solution of the proximal gradient subproblem (3) with $\gamma_{k}=1$ consists of finding $\bar{x}_{k}$ such that

This proximal subproblem is equivalent to the following monotone inclusion problem:

The $k$-th iteration of the inexact proximal gradient method, which incorporates an explicit linesearch as proposed below, begins by first relaxing the above inclusion. This is achieved by finding an approximate solution $\tilde{x}_{k}$ along with a residual pair $(v_{k},\varepsilon_{k})$ satisfying

and adheres to a specific mixed relative error criterion. This criterion is designed to ensure that the residual pair remains small, while also controlling the functional value of $g$ and the angle between $\nabla f(x_{k})$ and $v_{k}$, in addition to guiding a search direction that involves the intermediate iteration $\tilde{x}_{k}$ and the residual $v_{k}$. If the stopping criterion $\tilde{x}_{k}=x_{k}$ is not satisfied, we use a novel linesearch procedure, designed with the triple $(\tilde{x}_{k},v_{k},\varepsilon_{k})$ in mind, to find a suitable stepsize $\beta_{k}$. This stepsize is used to move from the current point $x_{k}$ towards $y_{k}-x_{k}$ where $y_{k}=\tilde{x}_{k}-v_{k}$, genegenerating the next point $x_{k+1}$.

In the following, we formally describe the proposed method, which combines a relative inexact computation of the proximal subproblem with an explicit linesearch.

Inexact Proximal Gradient Method with an Explicit Linesearch (IPG-ELS) Initialization Step. Let $x_{0}\in{\bf dom\,}g$, $\tau\in(0,1]$, $\theta\in(0,1)$, $\gamma_{1}>1$, $\gamma_{2}\geq 1$, and $\alpha\in[0,1-\tau]$. Set $k=0$. Inexact Proximal Subproblem. Compute a triple $(\tilde{x}_{k},v_{k},\varepsilon_{k})$ satisfying $$\displaystyle v_{k}\in\nabla f(x_{k})+\partial_{\varepsilon_{k}}g(\tilde{x}_{k})+\tilde{x}_{k}-x_{k},$$ (10) $$\displaystyle g(\tilde{x}_{k}-v_{k})-g(\tilde{x}_{k})-\langle\nabla f(x_{k}),v_{k}\rangle+\frac{(1+\gamma_{1})}{2}\|v_{k}\|^{2}+(1+\gamma_{2})\varepsilon_{k}\leq\frac{(1-\tau-\alpha)}{2}\|x_{k}-\tilde{x}_{k}\|^{2};$$ (11) Stopping Criterion. If $\tilde{x}_{k}=x_{k}$, then stop. Linesearch Procedure. Set $\beta=1$ and $y_{k}:=\tilde{x}_{k}-v_{k}$. If $$\dsty f\left(x_{k}+\beta(y_{k}-x_{k})\right)\leq f(x_{k})+\beta\langle\nabla f(x_{k}),y_{k}-x_{k}\rangle+\frac{\beta\tau}{2}\|x_{k}-\tilde{x}_{k}\|^{2}+\frac{\gamma_{1}}{2}\beta\|v_{k}\|^{2}+\beta\gamma_{2}\varepsilon_{k},$$ (12) then set $\beta_{k}=\beta$, $x_{k+1}=x_{k}+\beta_{k}(y_{k}-x_{k})$ and $k:=k+1$, and go to Step 2. Otherwise, set $\beta=\theta\beta$, and verify (12).

We introduce a useful lemma that plays a crucial role in analyzing the stopping criterion of the IPG-ELS method.

Proof It follows from (10) that

Now using (5) together with the fact that $y_{k}=\tilde{x}_{k}-v_{k}$, we have

which is equivalent to

On the other hand, considering the definitions of $\Gamma_{k}$ and $y_{k}$, we observe that (11) is equivalent to

which, combined with (17), yields the desired inequality (16). ∎

The following result demonstrates that the termination criterion of the IPG-ELS method, as specified in Step 3, is satisfied only when a solution to problem (1) is identified.

Proof Assume that the IPG-ELS method stops at the $k$-th iteration. In view of Step 3, we have $\tilde{x}_{k}=x_{k}$. Hence, it follows from (16) that

Since $\gamma_{1}>1$ and $\gamma_{2}\geq 1$, we obtain $v_{k}=0$ and $\varepsilon_{k}=0$. Hence, in view of (10), we get that $0\in\nabla f(x_{k})+\partial g(x_{k}),$ concluding that $x_{k}$ is a solution of problem (1).

Assume now that $x_{k}$ is a solution of problem (1). Thus, $-\nabla f(x_{k})\in\partial g(x_{k}).$ It follows from (10) that $v_{k}+x_{k}-\tilde{x}_{k}-\nabla f(x_{k})\in\partial_{\varepsilon_{k}}g(\tilde{x}_{k})$. So, the $\varepsilon$-monotonicity of $\partial_{\varepsilon}g$ in (6) implies

which is equivalent to

Hence, it follows from (16) that

Since $\gamma_{1}>1$, $\gamma_{2}\geq 1$, $\alpha\geq 0$, and $\tau>0$, we conclude that $x_{k}=\tilde{x}_{k}$ and $v_{k}=0$. Hence, from (11), we also have $\varepsilon_{k}=0$. Therefore, the IPG-ELS method stops at the $k$-th iteration. ∎

In the following, we establish the well-definedness of the linesearch procedure in Step 4 of the IPG-ELS method.

Proof In view of Step 3, we have $x_{k}\neq\tilde{x}_{k}$. Assume, for the sake of contradiction, that the linesearch procedure does not terminate after a finite number of steps. Thus, for all $\beta\in\{1,\theta,\theta^{2},\ldots\}$, we have

or, equivalently,

Given that $f$ is differentiable, the left-hand side of the above inequality approaches zero as $\beta\downarrow 0$, leading to the conclusion that

This implies $x_{k}=\tilde{x}_{k}$ contradicting the assumption that $x_{k}\neq\tilde{x}_{k}$. ∎

The subsequent analysis investigates the linesearch procedure introduced in Step 4 of the IPG-ELS method, assuming that the gradient of the function $f$, $\nabla f$, is Lipschitz continuous. We aim to establish an upper bound for the number of iterations required by the linesearch procedure in Step 4.

Proof Since $\nabla f$ is $L$-Lipschitz continuous, for any $\beta>0$, we have

Hence, if $\beta\leq\tau/(2L)$, we conclude that

using Lemma 2 in the last inequality. Since $\gamma_{1}>1>\tau$ and $\gamma_{2}\geq 0$, we have that (12) holds, thereby proving the first statement of the lemma. The last statement follows from the first one, given that the natural number $\ell$, defined in (19), satisfies $\beta_{\ell}:=\theta^{\ell}\leq\min\{\tau/(2L),1\}$. ∎

This lemma provides a sufficient condition to ensure that the lower bound of the sequence generated by our linesearch is greater than $0$. Specifically, if $\nabla f$ is $L$-Lipschitz, then the step sizes $\beta_{k}$, produced through the line search (12), are guaranteed to be bounded below by a positive constant $\beta>0$, i.e., $\beta_{k}\geq\beta>0$ for all $k\in\mathbb{N}$. Moreover, it is possible to relax the global Lipschitz condition to something local, such as $\nabla f$ being locally Lipschitz continuous around any solution of problem (1), as was done in Proposition 5.4(ii) of BelloCruz:2016a .

In this section, we focus on analyzing the convergence properties of the IPG-ELS method. We establish the convergence and its iteration complexity in terms of functional values and a residual associated with an approximated solution, as defined in Definition 1.

We begin this section by presenting a result that is fundamental for establishing the convergence and the iteration complexity of the IPG-ELS method.

Proof Let $x\in{\bf dom\,}\,g$ and $k\in\mathbb{N}$. In view of the inexact relative inclusion (10), we have $v_{k}+{x}_{k}-\tilde{x}_{k}-\nabla f({x}_{k})\in\partial_{\varepsilon_{k}}g(\tilde{x}_{k})$, and hence the definition of $\partial_{\varepsilon}g$ in (5) implies that

Since $f$ is convex, we have $f(x)-f(x_{k})\geq\langle\nabla f(x_{k}),x-x_{k}\rangle$. Adding the above two inequalities, using $f+g=F$, and simplifying the resulting expression, we obtain

Combining the above inequality with the identity

we have

or, equivalently,

Since $x_{k+1}=x_{k}+\beta_{k}(y_{k}-x_{k})$ and $g$ is convex, we have $g(x_{k+1})-g(x_{k})\leq\beta_{k}(g(y_{k})-g(x_{k}))$. Hence, combining the last two inequalities and the fact that $y_{k}=\tilde{x}_{k}-v_{k}$, we get

or, equivalently,

Now, using the linesearch procedure of Step 4, we obtain

It follows from the above inequality and (11) that

On the other hand, using the identity $x_{k+1}-x=(1-\beta_{k})(x_{k}-x)+\beta_{k}(y_{k}-x)$ and the strong convexity of $\|\cdot\|^{2}$, we have

which implies

Therefore, the proof of (20) follows by combining the latter inequality with (22). The last statement of the proposition follows immediately from (20) with $x=x_{k}$ that

So, $(F(x_{k}))_{k\in\mathbbm{N}}$ is decreasing and convergent because it is bounded from below by $F(x_{*})$. Moreover, the last inequality implies that $\sum_{k=0}^{\infty}\|x^{k}-x^{k+1}\|^{2}<+\infty$. ∎

Next, we establish the convergence rate of the functional values sequence $(F(x_{k}))_{k\in\mathbbm{N}}$.