Introduction
Composite optimization provides a natural formulation for problems in which a smooth data-fitting term is combined with a nonsmooth regularizer. Proximal-gradient method gradient methods exploit this structure by separating a gradient step from a proximity step. Nonconvex penalties are of particular interest in sparse approximation, where they induce different sparsity patterns and estimation biases from convex regularizers. Their analysis requires care: the proximity operator can be set-valued, stationary points need not be globally optimal, and guarantees derived from convexity are no longer available [1 , 3 , 5 , 18 ] .
Quasar-convexity offers a different source of structure by controlling a function along segments directed toward a global minimizer. Smooth quasar-convex optimization admits efficient first-order methods [9 , 14 , 24 ] . For nonsmooth functions, the proximal-point analysis in [6 ] establishes global convergence and linear rates under strong quasar-convexity. The proximal comparison inequality relative to the quasar-convex center in [6 Proposition 15] is a starting point for the present work. Proximal quasar-convexity has also been introduced for composite models with convex regularizers and random zeroth-order oracles [8 ] . Our setting differs because the regularizer itself may be nonconvex and its quasar-convex center need not minimize the full composite objective.
The composite analysis in [13 Section 3.3] considers an accelerated proximal-gradient method for a strongly quasar-convex smooth term and a convex nonsmooth term. The composite convergence result is restricted to the quasar-convexity parameter equal to one (κ = 1 \kappa= 1 κ = 1 in our notation) and requires the smooth term to satisfy the extended strong quasar-convexity inequality at a global minimizer of the sum, together with a lower-curvature condition. The location of this reference point is essential, since adding a convex term may displace the minimizer from the original quasar-convex center. In our setting, the smooth term is convex, while the regularizer may be nonconvex and nonsmooth. We retain its own quasar-convex center and derive proximal comparisons valid at arbitrary reference points.
We analyze the splitting iteration
x k + 1 ∈ Prox β k h ( x k − κ β k ∇ g ( x k ) ) , 0 < κ ≤ 1 , x_{k+1} \in\operatorname{Prox}_{\beta_k h}\left(x_k-\kappa\beta_k\nabla g(x_k)\right), \qquad0 < \kappa\le1, x k + 1 ∈ Prox β k h ( x k − κ β k ∇ g ( x k ) ) , 0 < κ ≤ 1 ,
where g g g is convex with a Lipschitz continuous gradient and h h h is proper, lower semicontinuous, and strongly quasar-convex. The factor κ \kappa κ in the gradient step is chosen to match the coefficient arising from the proximal comparison for a strongly quasar-convex regularizer. Both component comparisons then carry the factor 2 κ β k 2\kappa\beta_k 2 κ β k , and their sum yields estimates relative to global minimizers of f = g + h f = g + h f = g + h , which need not coincide with the quasar-convex center of h h h . This choice allows us to exploit the geometry of the regularizer without imposing quasar-convexity on the composite objective. For steps in the descent range, the iteration decreases F k = κ g + h F_k = \kappa g + h F k = κ g + h , so its critical-point convergence concerns this weighted objective. We thus distinguish the objective decreased by the algorithm from the unweighted objective used in the global-minimizer comparisons.
Our first main result combines geometric and asymptotic distance estimates relative to global minimizers of f f f . For every constant step in the descent range, a geometric envelope controls the distance to a ball centered at any such minimizer, with an explicit radius independent of the step size. A common minimizer of g g g and h h h yields global linear convergence for every proximal selection. Our second main result is a comparison at critical points: every critical point u u u of F κ F_{\kappa} F κ lies within an explicit multiple of ∥ ∇ g ( u ) ∥ \lVert\nabla g(u)\rVert ∥ ∇ g ( u )∥ from every global minimizer of f f f . Optimizing the free parameter in the composite inequality recovers this same comparison constant when μ ≤ κ γ / ( 2 − κ ) \mu\leq\kappa\gamma/(2-\kappa) μ ≤ κγ / ( 2 − κ ) , where μ \mu μ and γ \gamma γ denote, respectively, the strong-convexity modulus of g g g and the quasar-convexity modulus of h h h (Assumption (H), Section 3); for larger values of μ \mu μ , the critical-point comparison supplies the stronger asymptotic estimate. An example with a nonconvex regularizer shows that critical points of F κ F_{\kappa} F κ need not be critical for f f f .
For the application h ( x ) = ρ ∥ x ∥ p p h(x)=\rho\lVert x\rVert_p^p h ( x ) = ρ ∥ x ∥ p p , 0 < p < 1 0<p<1 0 < p < 1 , strong quasar-convexity is available only on bounded sets. We recall its sharp modulus on a Euclidean ball and derive the required ball directly from the initial weighted objective value, resolving the confinement requirement without modifying the algorithm. To complete the application, we apply established thresholding and restricted-KL arguments [1 , 27 , 28 ] to verify whole-sequence convergence to a critical point of F κ F_{\kappa} F κ . These properties complement the comparison estimates and do not imply global sparse recovery.
Section 2 presents the preliminaries, and Section 3 develops the proximal comparison inequalities and convergence estimates. Section 4 applies the results to power-regularized least squares, followed by the conclusions in Section 5.
Preliminaries and Basic Definitions
The inner product on R n \mathbb{R}^n R n and the Euclidean norm are denoted by ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ , respectively. The open ball with center at x 0 ∈ R n x_0\in\mathbb{R}^n x 0 ∈ R n and radius ε > 0 \varepsilon>0 ε > 0 is denoted by B ( x 0 , ε ) \mathbb{B}(x_0,\varepsilon) B ( x 0 , ε ) . For r ≥ 0 r\geq0 r ≥ 0 , we write B ( x 0 , r ) : = { x ∈ R n : ∥ x − x 0 ∥ ≤ r } \mathbb{B}(x_0,r):=\{x\in\mathbb{R}^n:\lVert x-x_0\rVert\leq r\} B ( x 0 , r ) := { x ∈ R n : ∥ x − x 0 ∥ ≤ r } for the closed ball, and also use B B B in place of B \mathbb{B} B . We set ( t ) + : = max { t , 0 } (t)_+:=\max\{t,0\} ( t ) + := max { t , 0 } for t ∈ R t\in\mathbb{R} t ∈ R . We write R + : = [ 0 , + ∞ [ \mathbb{R}_+:=[0,+\infty[ R + := [ 0 , + ∞ [ and R + + : = ] 0 , + ∞ [ \mathbb{R}_{++}:=]0,+\infty[ R ++ := ] 0 , + ∞ [ . For a nonempty set K ⊂ R n K\subset\mathbb{R}^n K ⊂ R n , we denote its closure by K ‾ \overline{K} K .
A nonempty set K ⊂ R n K\subset\mathbb{R}^n K ⊂ R n is said to be star-shaped at x 0 ∈ K x_0\in K x 0 ∈ K if, for every x ∈ K x\in K x ∈ K , the segment [ x 0 , x ] ⊂ K [x_0,x]\subset K [ x 0 , x ] ⊂ K .
Given any u , v , w ∈ R n u,v,w\in\mathbb{R}^n u , v , w ∈ R n and any θ ∈ R \theta\in\mathbb{R} θ ∈ R , the following relations hold:
⟨ u − w , v − u ⟩ = 1 2 ∥ w − v ∥ 2 − 1 2 ∥ u − w ∥ 2 − 1 2 ∥ v − u ∥ 2 (1) \langle u-w,v-u\rangle=\frac{1}{2}\lVert w-v\rVert^2-\frac{1}{2}\lVert u-w\rVert^2-\frac{1}{2}\lVert v-u\rVert^2 \tag*{(1)} ⟨ u − w , v − u ⟩ = 2 1 ∥ w − v ∥ 2 − 2 1 ∥ u − w ∥ 2 − 2 1 ∥ v − u ∥ 2 (1)
∥ θ u + ( 1 − θ ) v ∥ 2 = θ ∥ u ∥ 2 + ( 1 − θ ) ∥ v ∥ 2 − θ ( 1 − θ ) ∥ u − v ∥ 2 (2) \lVert\theta u+(1-\theta)v\rVert^2=\theta\lVert u\rVert^2+(1-\theta)\lVert v\rVert^2-\theta(1-\theta)\lVert u-v\rVert^2 \tag*{(2)} ∥ θ u + ( 1 − θ ) v ∥ 2 = θ ∥ u ∥ 2 + ( 1 − θ ) ∥ v ∥ 2 − θ ( 1 − θ ) ∥ u − v ∥ 2 (2)
Given any extended-valued function h : R n → R ‾ h:\mathbb{R}^n\to\overline{\mathbb{R}} h : R n → R , the effective domain of h h h is defined by dom h : = { x ∈ R n : h ( x ) < + ∞ } \operatorname{dom}h:=\{x\in\mathbb{R}^n:h(x)<+\infty\} dom h := { x ∈ R n : h ( x ) < + ∞ } . The function h h h is proper if dom h \operatorname{dom}h dom h is nonempty and h ( x ) > − ∞ h(x)>-\infty h ( x ) > − ∞ for all x ∈ R n x\in\mathbb{R}^n x ∈ R n . The notion of properness is important when dealing with minimization problems.
We denote by S λ ( h ) : = { x ∈ R n : h ( x ) ≤ λ } S_{\lambda}(h):=\{x\in\mathbb{R}^n:h(x)\leq\lambda\} S λ ( h ) := { x ∈ R n : h ( x ) ≤ λ } the sublevel set of h h h at level λ ∈ R \lambda\in\mathbb{R} λ ∈ R , and by argmin R n h \operatorname*{argmin}_{\mathbb{R}^n}h argmin R n h the set of its global minimizers. A function h h h is lower semicontinuous (lsc) at x ‾ ∈ R n \overline{x}\in\mathbb{R}^n x ∈ R n if, for every sequence { x k } k ⊂ R n \{x_k\}_k\subset\mathbb{R}^n { x k } k ⊂ R n with x k → x ‾ x_k\to\overline{x} x k → x , we have h ( x ‾ ) ≤ lim inf k → + ∞ h ( x k ) h(\overline{x})\leq\liminf_{k\to+\infty}h(x_k) h ( x ) ≤ lim inf k → + ∞ h ( x k ) .
A proper function h : R n → R ‾ h : \mathbb{R}^{n} \to\overline{\mathbb{R}} h : R n → R is coercive if
lim ∥ x ∥ → + ∞ h ( x ) = + ∞ , \lim_{\lVert x\rVert\to+\infty} h(x) = +\infty, ∥ x ∥ → + ∞ lim h ( x ) = + ∞ ,
or equivalently, if S λ ( h ) S_{\lambda}(h) S λ ( h ) is bounded for every λ ∈ R \lambda\in\mathbb{R} λ ∈ R .
The following generalized convexity notion has been used in several applications in machine learning because it supports convergence guarantees for gradient methods (see [9 , 12 , 13 , 14 , 24 ] and references therein).
Motivated by [14 Lemma 10] , we define quasar-convexity as follows:
Definition 2.1. Let κ ∈ ] 0 , 1 ] \kappa\in]0,1] κ ∈ ] 0 , 1 ] , γ ≥ 0 \gamma\ge0 γ ≥ 0 , let h : R n → R ‾ h : \mathbb{R}^{n} \to\overline{\mathbb{R}} h : R n → R be proper, and let K ⊂ R n K \subset\mathbb{R}^{n} K ⊂ R n be star-shaped at x ‾ ∈ K ∩ argmin R n h \overline{x} \in K \cap\operatorname{argmin}_{\mathbb{R}^{n}} h x ∈ K ∩ argmin R n h . We say that h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex on K K K with respect to x ‾ \overline{x} x if
h ( λ x ‾ + ( 1 − λ ) x ) ≤ κ λ h ( x ‾ ) + ( 1 − κ λ ) h ( x ) − λ ( 1 − λ 2 − κ ) κ γ 2 ∥ x − x ‾ ∥ 2 h(\lambda\overline{x} + (1-\lambda)x) \le\kappa\lambda h(\overline{x}) + (1-\kappa\lambda)h(x) - \lambda\left(1-\frac{\lambda}{2-\kappa}\right)\frac{\kappa\gamma}{2}\lVert x-\overline{x}\rVert^{2} h ( λ x + ( 1 − λ ) x ) ≤ κλh ( x ) + ( 1 − κλ ) h ( x ) − λ ( 1 − 2 − κ λ ) 2 κγ ∥ x − x ∥ 2 for all λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] and all x ∈ K ∩ dom h x \in K \cap\operatorname{dom} h x ∈ K ∩ dom h . When K = R n K = \mathbb{R}^{n} K = R n , we omit the reference to K K K ; when γ = 0 \gamma= 0 γ = 0 , we say that h h h is κ \kappa κ -quasar-convex.
In particular, K ∩ dom h K \cap\operatorname{dom} h K ∩ dom h is star-shaped at x ‾ \overline{x} x , since the right-hand side is finite for x ∈ K ∩ dom h x \in K \cap\operatorname{dom} h x ∈ K ∩ dom h .
If h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex on K K K with respect to x ‾ \overline{x} x and γ > 0 \gamma> 0 γ > 0 , then x ‾ \overline{x} x is the unique minimizer of h h h on K K K , by the quadratic-growth inequality (5) below; in the global case, argmin R n h = { x ‾ } \operatorname{argmin}_{\mathbb{R}^{n}} h = \{\overline{x}\} argmin R n h = { x } . If γ = 0 \gamma= 0 γ = 0 , then K ∩ argmin R n h K \cap\operatorname{argmin}_{\mathbb{R}^{n}} h K ∩ argmin R n h is star-shaped at x ‾ \overline{x} x (see [14 Observation 3] ). For κ = 1 \kappa= 1 κ = 1 , (strongly) quasar-convex functions are (strongly) star-convex [21 ] . In particular, every (strongly) convex function with modulus γ ≥ 0 \gamma\ge0 γ ≥ 0 that attains its minimum is ( 1 , γ ) (1,\gamma) ( 1 , γ ) -strongly quasar-convex with respect to any of its minimizers.
The relationship between convex/star-convex/quasar-convex notions is summarized below:
strongly convex ⟹ ∗ strongly star-convex ⟹ ∗ strongly quasar-convex ⇓ ⇓ ⇓ convex ⟹ ∗ star-convex ⟹ ∗ quasar-convex \begin{array}{ccccc}
\text{strongly convex} & \overset{*}{\Longrightarrow} & \text{strongly star-convex} & \overset{*}{\Longrightarrow} & \text{strongly quasar-convex} \\
\Downarrow& & \Downarrow& & \Downarrow\\
\text{convex} & \overset{*}{\Longrightarrow} & \text{star-convex} & \overset{*}{\Longrightarrow} & \text{quasar-convex}
\end{array} strongly convex ⇓ convex ⟹ ∗ ⟹ ∗ strongly star-convex ⇓ star-convex ⟹ ∗ ⟹ ∗ strongly quasar-convex ⇓ quasar-convex
where “*” denotes that argmin R n h ≠ ∅ \operatorname{argmin}_{\mathbb{R}^{n}} h \ne\varnothing argmin R n h = ∅ is required. None of the reverse implications holds in general (see [9 , 13 , 14 , 21 ] ).
Remark 2.2. Neither (strong) quasiconvexity nor (strong) quasar-convexity implies the other in general. Indeed, the function in [11 Example 11] is strongly quasiconvex but not quasar-convex, while the function in [6 Example 8] is strongly quasar-convex on a ball in dimension at least two but not quasiconvex. For differentiable functions, sufficient conditions under which strong quasiconvexity implies quasar-convexity are provided in [11 , 17 ] .
A function h : R n → R h : \mathbb{R}^{n} \to\mathbb{R} h : R n → R is said to be L L L -smooth on an open set K ⊂ R n K \subset\mathbb{R}^{n} K ⊂ R n if it is differentiable on K K K and
∥ ∇ h ( x ) − ∇ h ( y ) ∥ ≤ L ∥ x − y ∥ , ∀ x , y ∈ K . (3) \lVert\nabla h(x) - \nabla h(y)\rVert\le L\lVert x-y\rVert,\quad\forall x,y \in K. \tag*{(3)} ∥ ∇ h ( x ) − ∇ h ( y )∥ ≤ L ∥ x − y ∥ , ∀ x , y ∈ K . (3)
For L L L -smooth functions, a fundamental result is the descent lemma: if h h h is L L L -smooth on a convex set K K K , with L ≥ 0 L \ge0 L ≥ 0 , then for every x , y ∈ K x,y \in K x , y ∈ K , we have
h ( y ) ≤ h ( x ) + ⟨ ∇ h ( x ) , y − x ⟩ + L 2 ∥ x − y ∥ 2 . (4) h(y) \le h(x) + \langle\nabla h(x),y-x\rangle+ \frac{L}{2}\lVert x-y\rVert^{2}. \tag*{(4)} h ( y ) ≤ h ( x ) + ⟨ ∇ h ( x ) , y − x ⟩ + 2 L ∥ x − y ∥ 2 . (4)
Also, if h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex with γ > 0 \gamma> 0 γ > 0 , then using h ( x ˉ ) ≤ h ( λ x ˉ + ( 1 − λ ) y ) h(\bar{x}) \le h(\lambda\bar{x} + (1-\lambda)y) h ( x ˉ ) ≤ h ( λ x ˉ + ( 1 − λ ) y ) in Definition 2.1 and letting λ ↑ 1 \lambda\uparrow1 λ ↑ 1 gives
h ( x ˉ ) + κ γ 2 ( 2 − κ ) ∥ y − x ˉ ∥ 2 ≤ h ( y ) , ∀ y ∈ K , (5) h(\bar{x}) + \frac{\kappa\gamma}{2(2-\kappa)}\lVert y-\bar{x}\rVert^{2} \le h(y),\quad\forall y \in K, \tag*{(5)} h ( x ˉ ) + 2 ( 2 − κ ) κγ ∥ y − x ˉ ∥ 2 ≤ h ( y ) , ∀ y ∈ K , (5)
where x ˉ ∈ argmin R n h \bar{x} \in\operatorname*{argmin}_{\mathbb{R}^{n}} h x ˉ ∈ argmin R n h . Thus, strongly quasar-convex functions satisfy a quadratic growth condition with modulus κ γ 2 ( 2 − κ ) > 0 \frac{\kappa\gamma}{2(2-\kappa)} > 0 2 ( 2 − κ ) κγ > 0 .
In the differentiable case, we have the following useful characterization: a differentiable function h : R n → R h:\mathbb{R}^{n} \to\mathbb{R} h : R n → R is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex on R n \mathbb{R}^{n} R n (κ ∈ ] 0 , 1 ] \kappa\in]0,1] κ ∈ ] 0 , 1 ] and γ ≥ 0 \gamma\ge0 γ ≥ 0 ) with respect to x ˉ ∈ argmin R n h \bar{x} \in\operatorname*{argmin}_{\mathbb{R}^{n}} h x ˉ ∈ argmin R n h if and only if (see [14 Lemma 10] )
h ( x ˉ ) ≥ h ( y ) + 1 κ ⟨ ∇ h ( y ) , x ˉ − y ⟩ + γ 2 ∥ y − x ˉ ∥ 2 , ∀ y ∈ R n . (6) h(\bar{x}) \ge h(y) + \frac{1}{\kappa}\langle\nabla h(y),\bar{x}-y\rangle+ \frac{\gamma}{2}\lVert y-\bar{x}\rVert^{2},\quad\forall y \in\mathbb{R}^{n}. \tag*{(6)} h ( x ˉ ) ≥ h ( y ) + κ 1 ⟨ ∇ h ( y ) , x ˉ − y ⟩ + 2 γ ∥ y − x ˉ ∥ 2 , ∀ y ∈ R n . (6)
Hence, quasi-strongly convex functions [20 ] are related to strongly quasar-convex functions. Further properties of differentiable (strongly) quasar-convex functions may be found in [9 , 12 , 13 , 14 , 24 ] , among others.
Let K ⊂ R n K \subset\mathbb{R}^{n} K ⊂ R n be nonempty, closed and convex, let h : R n → R ‾ h:\mathbb{R}^{n} \to\overline{\mathbb{R}} h : R n → R be proper and lsc, and let β > 0 \beta> 0 β > 0 . The proximity operator Prox β h ( K , ⋅ ) : R n ⇉ R n \operatorname{Prox}_{\beta h}(K,\cdot):\mathbb{R}^{n} \rightrightarrows\mathbb{R}^{n} Prox β h ( K , ⋅ ) : R n ⇉ R n of h h h on K K K with parameter β \beta β is defined by
Prox β h ( K , z ) = argmin x ∈ K { h ( x ) + 1 2 β ∥ z − x ∥ 2 } . (7) \operatorname{Prox}_{\beta h}(K,z) = \operatorname*{argmin}_{x \in K}\left\{h(x) + \frac{1}{2\beta}\lVert z-x\rVert^{2}\right\}. \tag*{(7)} Prox β h ( K , z ) = x ∈ K argmin { h ( x ) + 2 β 1 ∥ z − x ∥ 2 } . (7)
When K = R n K = \mathbb{R}^{n} K = R n , we simply write Prox β h ( z ) : = Prox β h ( R n , z ) \operatorname{Prox}_{\beta h}(z) := \operatorname{Prox}_{\beta h}(\mathbb{R}^{n},z) Prox β h ( z ) := Prox β h ( R n , z ) . If h h h is proper, lsc and convex, then Prox β h \operatorname{Prox}_{\beta h} Prox β h is single-valued (see, for instance, [4 Proposition 12.15] ).
For x ∈ dom h x \in\operatorname{dom} h x ∈ dom h , the Fréchet subdifferential is
∂ ^ h ( x ) = { v ∈ R n : lim inf z → x z ≠ x h ( z ) − h ( x ) − ⟨ v , z − x ⟩ ∥ z − x ∥ ≥ 0 } . \widehat{\partial}h(x) = \left\{v \in\mathbb{R}^{n} : \liminf_{\substack{z \to x\\z\ne x}}\frac{h(z)-h(x)-\langle v,z-x\rangle}{\lVert z-x\rVert} \ge0\right\}. ∂ h ( x ) = { v ∈ R n : z → x z = x lim inf ∥ z − x ∥ h ( z ) − h ( x ) − ⟨ v , z − x ⟩ ≥ 0 } .
The limiting subdifferential consists of limits v j → v v_j \to v v j → v with v j ∈ ∂ ^ h ( x j ) v_j \in\widehat{\partial}h(x_j) v j ∈ ∂ h ( x j ) , x j → x x_j \to x x j → x and h ( x j ) → h ( x ) h(x_j) \to h(x) h ( x j ) → h ( x ) .
The following notion extends the classical concept of a stationary point to the possibly nonsmooth setting considered here.
Given a proper lsc function h : R n → R ‾ h:\mathbb{R}^{n} \to\overline{\mathbb{R}} h : R n → R , we denote by ∂ L h ( x ) \partial^{L}h(x) ∂ L h ( x ) its (limiting) subdifferential at x ∈ dom h x \in\operatorname{dom} h x ∈ dom h (see [23 ] for the limiting subdifferential, and [1 ] and the references therein for the general lsc case, which covers functions such as ∣ x ∣ p |x|^{p} ∣ x ∣ p , 0 < p < 1 0 < p < 1 0 < p < 1 , failing to be locally Lipschitz at the origin).
Recall that ∂ L h ( x ) = { ∇ h ( x ) } \partial^{L}h(x)=\{\nabla h(x)\} ∂ L h ( x ) = { ∇ h ( x )} whenever h h h is continuously differentiable near x x x , that the sum rule
∂ L ( ϕ + h ) ( x ) = ∇ ϕ ( x ) + ∂ L h ( x ) \partial^{L}(\phi+h)(x)=\nabla\phi(x)+\partial^{L}h(x) ∂ L ( ϕ + h ) ( x ) = ∇ ϕ ( x ) + ∂ L h ( x )
holds for every ϕ ∈ C 1 ( R n ) \phi\in C^{1}(\mathbb{R}^{n}) ϕ ∈ C 1 ( R n ) and every x ∈ dom h x\in\operatorname{dom}h x ∈ dom h , and that ∂ L h \partial^{L}h ∂ L h has the following closedness property: if x k → x x_{k}\to x x k → x , h ( x k ) → h ( x ) h(x_{k})\to h(x) h ( x k ) → h ( x ) , w k ∈ ∂ L h ( x k ) w_{k}\in\partial^{L}h(x_{k}) w k ∈ ∂ L h ( x k ) and w k → w w_{k}\to w w k → w , then w ∈ ∂ L h ( x ) w\in\partial^{L}h(x) w ∈ ∂ L h ( x ) .
Given κ ∈ ] 0 , 1 ] \kappa\in]0,1] κ ∈ ] 0 , 1 ] , a point x ˉ ∈ R n \bar{x}\in\mathbb{R}^{n} x ˉ ∈ R n is said to be a κ \kappa κ -critical point of f = g + h f=g+h f = g + h if
0 ∈ κ ∇ g ( x ˉ ) + ∂ L h ( x ˉ ) (8) 0\in\kappa\nabla g(\bar{x})+\partial^{L}h(\bar{x}) \tag*{(8)} 0 ∈ κ ∇ g ( x ˉ ) + ∂ L h ( x ˉ ) (8)
that is, x ˉ \bar{x} x ˉ is a critical point, in the sense above, of F κ : = κ g + h F_{\kappa}:=\kappa g+h F κ := κ g + h . When κ = 1 \kappa=1 κ = 1 , (8) reduces to the usual notion of a critical point of f = g + h f=g+h f = g + h .
Definition 2.3 (Kurdyka–Łojasiewicz property). Let σ : R n → R ‾ \sigma:\mathbb{R}^{n}\to\overline{\mathbb{R}} σ : R n → R be proper and lsc, and write
dist ( 0 , ∂ L σ ( u ) ) : = inf { ∥ v ∥ : v ∈ ∂ L σ ( u ) } . \operatorname{dist}(0,\partial^{L}\sigma(u)):=\inf\{\lVert v\rVert:v\in\partial^{L}\sigma(u)\}. dist ( 0 , ∂ L σ ( u )) := inf {∥ v ∥ : v ∈ ∂ L σ ( u )} . (with inf ∅ : = + ∞ \inf\varnothing:=+\infty inf ∅ := + ∞ ). For η ∈ ] 0 , + ∞ ] \eta\in]0,+\infty] η ∈ ] 0 , + ∞ ] , let Φ η \Phi_{\eta} Φ η denote the class of concave functions φ : [ 0 , η [ → [ 0 , + ∞ [ \varphi:[0,\eta[\to[0,+\infty[ φ : [ 0 , η [ → [ 0 , + ∞ [ such that φ ( 0 ) = 0 \varphi(0)=0 φ ( 0 ) = 0 , φ \varphi φ is continuously differentiable on ] 0 , η [ ]0,\eta[ ] 0 , η [ and continuous at 0 0 0 , and φ ′ ( s ) > 0 \varphi'(s)>0 φ ′ ( s ) > 0 for every s ∈ ] 0 , η [ s\in]0,\eta[ s ∈ ] 0 , η [ .
We say that σ \sigma σ has the Kurdyka–Łojasiewicz (KL) property at u ˉ ∈ dom ∂ L σ \bar{u}\in\operatorname{dom}\partial^{L}\sigma u ˉ ∈ dom ∂ L σ if there exist η ∈ ] 0 , + ∞ ] \eta\in]0,+\infty] η ∈ ] 0 , + ∞ ] , a neighborhood U U U of u ˉ \bar{u} u ˉ , and φ ∈ Φ η \varphi\in\Phi_{\eta} φ ∈ Φ η such that
φ ′ ( σ ( u ) − σ ( u ˉ ) ) dist ( 0 , ∂ L σ ( u ) ) ≥ 1 \varphi'(\sigma(u)-\sigma(\bar{u}))\operatorname{dist}(0,\partial^{L}\sigma(u))\geq1 φ ′ ( σ ( u ) − σ ( u ˉ )) dist ( 0 , ∂ L σ ( u )) ≥ 1 for every u ∈ U u\in U u ∈ U with σ ( u ˉ ) < σ ( u ) < σ ( u ˉ ) + η \sigma(\bar{u})<\sigma(u)<\sigma(\bar{u})+\eta σ ( u ˉ ) < σ ( u ) < σ ( u ˉ ) + η . If φ \varphi φ can be taken of the form φ ( s ) = c 1 − θ s 1 − θ \varphi(s)=\frac{c}{1-\theta}s^{1-\theta} φ ( s ) = 1 − θ c s 1 − θ for some c > 0 c>0 c > 0 and θ ∈ [ 0 , 1 [ \theta\in[0,1[ θ ∈ [ 0 , 1 [ , we say that σ \sigma σ satisfies the KL inequality at u ˉ \bar{u} u ˉ with exponent θ \theta θ ; the defining inequality then reduces to
∣ σ ( u ) − σ ( u ˉ ) ∣ θ ≤ c dist ( 0 , ∂ L σ ( u ) ) \lvert\sigma(u)-\sigma(\bar{u})\rvert^{\theta}\leq c\operatorname{dist}(0,\partial^{L}\sigma(u)) ∣ σ ( u ) − σ ( u ˉ ) ∣ θ ≤ c dist ( 0 , ∂ L σ ( u )) for every such u u u . A proper lsc function with the KL property at every point of dom ∂ L σ \operatorname{dom}\partial^{L}\sigma dom ∂ L σ is called a KL function. Real-analytic functions are KL functions, with exponent θ ∈ [ 1 / 2 , 1 [ \theta\in[1/2,1[ θ ∈ [ 1/2 , 1 [ at every point by the Łojasiewicz gradient inequality; see [1 ] and the references therein.
For further background on generalized convexity, proximal point methods and the KL property, we refer to [1 , 2 , 4 , 5 , 7 , 10 , 16 , 18 , 22 ] and references therein.
The Proximal-Gradient Algorithm
Throughout this section, we use the following general assumptions:
(H1) g ∈ C 1 ( R n ) g\in C^{1}(\mathbb{R}^{n}) g ∈ C 1 ( R n ) is μ \mu μ -strongly convex with an L L L -Lipschitz gradient, where L > 0 L>0 L > 0 and 0 ≤ μ ≤ L 0\leq\mu\leq L 0 ≤ μ ≤ L . (H2) h : R n → R ∪ { + ∞ } h : \mathbb{R}^{n} \to\mathbb{R} \cup\{+\infty\} h : R n → R ∪ { + ∞ } is proper, lower semicontinuous, and ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex with respect to x ˉ h ∈ arg min R n h \bar{x}_h \in\arg\min_{\mathbb{R}^{n}} h x ˉ h ∈ arg min R n h , where 0 < κ ≤ 1 0 < \kappa\le1 0 < κ ≤ 1 and γ > 0 \gamma> 0 γ > 0 .
We refer to (H1)–(H2) together as (H). Step-size restrictions and additional conditions are stated in each result. Write
f = g + h , F κ = κ g + h , x ˉ h ∈ arg min h , x ∗ ∈ arg min f . f = g + h,\qquad F_{\kappa} = \kappa g + h,\qquad\bar{x}_h \in\arg\min h,\qquad x^{*} \in\arg\min f. f = g + h , F κ = κ g + h , x ˉ h ∈ arg min h , x ∗ ∈ arg min f .
The quadratic-growth inequality guarantees that x ˉ h \bar{x}_h x ˉ h is unique. Supporting affine minorants of g g g and quadratic growth of h h h make both objectives coercive, so their minimizers exist. The proximal objective is also lower semicontinuous and coercive, hence its set of global minimizers is nonempty and compact. All results hold for every proximal selection. The iteration below is standard proximal gradient for F κ F_{\kappa} F κ ; f f f is the comparison objective. The symbol μ \mu μ denotes the strong-convexity modulus of g g g throughout the paper, while ρ \rho ρ denotes the regularization weight in Section 4.
Algorithm 1 Weighted Proximal-Gradient Algorithm with a Strongly Quasar-Convex Regularizer (PG-SQC)
Step 0. Take x 1 ∈ dom ( h + g ) x_1 \in\operatorname{dom}(h + g) x 1 ∈ dom ( h + g ) , set k = 1 k = 1 k = 1 , and let { β k } k ∈ N ⊂ R + + \{\beta_k\}_{k\in\mathbb{N}} \subset\mathbb{R}_{++} { β k } k ∈ N ⊂ R ++ .
Step 1. Compute
y k = x k − κ β k ∇ g ( x k ) , (9) y_k = x_k - \kappa\beta_k\nabla g(x_k), \tag*{(9)} y k = x k − κ β k ∇ g ( x k ) , (9) x k + 1 ∈ Prox β k h ( y k ) . (10) x_{k+1} \in\operatorname{Prox}_{\beta_k h}(y_k). \tag*{(10)} x k + 1 ∈ Prox β k h ( y k ) . (10) Step 2. If x k + 1 = x k x_{k+1} = x_k x k + 1 = x k , then STOP and return x k x_k x k . Otherwise, set k = k + 1 k = k + 1 k = k + 1 and go to Step 1.
We discuss the stopping criterion below.
Remark 3.1 (Exact stopping criterion). If the stopping condition in Step 2 is satisfied at some iteration, i.e., x k + 1 = x k x_{k+1} = x_k x k + 1 = x k for the step size β k > 0 \beta_k > 0 β k > 0 used there, then x k x_k x k is already a κ \kappa κ -critical point of f = g + h f = g + h f = g + h in the sense of (8). Indeed, proximal optimality of x k + 1 ∈ Prox β k h ( y k ) x_{k+1} \in\operatorname{Prox}_{\beta_k h}(y_k) x k + 1 ∈ Prox β k h ( y k ) gives
0 ∈ ∂ L h ( x k + 1 ) + 1 β k ( x k + 1 − y k ) . 0 \in\partial^{L}h(x_{k+1}) + \frac{1}{\beta_k}(x_{k+1} - y_k). 0 ∈ ∂ L h ( x k + 1 ) + β k 1 ( x k + 1 − y k ) .
Substituting x k + 1 = x k x_{k+1} = x_k x k + 1 = x k and y k = x k − κ β k ∇ g ( x k ) y_k = x_k - \kappa\beta_k\nabla g(x_k) y k = x k − κ β k ∇ g ( x k ) yields
x k − y k β k = κ ∇ g ( x k ) , \frac{x_k-y_k}{\beta_k} = \kappa\nabla g(x_k), β k x k − y k = κ ∇ g ( x k ) ,
hence
0 ∈ κ ∇ g ( x k ) + ∂ L h ( x k ) , 0 \in\kappa\nabla g(x_k) + \partial^{L}h(x_k), 0 ∈ κ ∇ g ( x k ) + ∂ L h ( x k ) ,
which is exactly (8) at x ˉ = x k \bar{x} = x_k x ˉ = x k . Thus, whenever Step 2 is satisfied, the returned iterate is a critical point of F κ F_{\kappa} F κ , regardless of the admissible step-size schedule { β k } k \{\beta_k\}_k { β k } k . This is consistent with the convention, used throughout Sections 3–4, of extending the sequence constantly once the algorithm stops.
As a first result, we present a proximal comparison inequality valid at arbitrary reference points.
Theorem 3.2. Assume ( H 2 ) (H2) ( H 2 ) , let β k > 0 \beta_k > 0 β k > 0 and y k ∈ R n y_k \in\mathbb{R}^n y k ∈ R n , and choose x k + 1 ∈ Prox β k h ( y k ) x_{k+1} \in\operatorname{Prox}_{\beta_k h}(y_k) x k + 1 ∈ Prox β k h ( y k ) . Then, for every δ > 0 \delta> 0 δ > 0 and every x ∈ dom h x \in\operatorname{dom} h x ∈ dom h , we have
2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ y k − x ∥ 2 − ( 1 + β k κ 2 γ 2 + δ ) ∥ x k + 1 − x ∥ 2 + C k ∥ x k + 1 − y k ∥ 2 , (11) \begin{aligned}
2\beta_k\kappa\bigl(h(x_{k+1})-h(x)\bigr)
&\le\|y_k-x\|^2-\left(1+\frac{\beta_k\kappa^2\gamma}{2+\delta}\right)\|x_{k+1}-x\|^2\\
&\quad+C_k\|x_{k+1}-y_k\|^2, \tag*{(11)}
\end{aligned} 2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ y k − x ∥ 2 − ( 1 + 2 + δ β k κ 2 γ ) ∥ x k + 1 − x ∥ 2 + C k ∥ x k + 1 − y k ∥ 2 , (11) where
C k : = ( 2 − κ ) ( 2 + δ − κ ) β k γ κ 2 δ − 1. C_k:=\frac{(2-\kappa)(2+\delta-\kappa)}{\beta_k\gamma\kappa^2\delta}-1. C k := β k γ κ 2 δ ( 2 − κ ) ( 2 + δ − κ ) − 1.
Proof. By proximal optimality, for every z ∈ dom h z \in\operatorname{dom} h z ∈ dom h ,
h ( x k + 1 ) + 1 2 β k ∥ x k + 1 − y k ∥ 2 ≤ h ( z ) + 1 2 β k ∥ z − y k ∥ 2 . (12) h(x_{k+1})+\frac{1}{2\beta_k}\|x_{k+1}-y_k\|^2\le h(z)+\frac{1}{2\beta_k}\|z-y_k\|^2. \tag*{(12)} h ( x k + 1 ) + 2 β k 1 ∥ x k + 1 − y k ∥ 2 ≤ h ( z ) + 2 β k 1 ∥ z − y k ∥ 2 . (12)
Fix t ∈ ] 0 , 1 ] t \in]0,1] t ∈ ] 0 , 1 ] and set z t = ( 1 − t ) x k + 1 + t x ˉ h z_t=(1-t)x_{k+1}+t\bar{x}_h z t = ( 1 − t ) x k + 1 + t x ˉ h . Since h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex, we have
h ( z t ) ≤ h ( x k + 1 ) − κ t ( h ( x k + 1 ) − h ( x ˉ h ) ) − t ( 1 − t 2 − κ ) κ γ 2 ∥ x k + 1 − x ˉ h ∥ 2 . (13) h(z_t)\le h(x_{k+1})-\kappa t\bigl(h(x_{k+1})-h(\bar{x}_h)\bigr)-t\left(1-\frac{t}{2-\kappa}\right)\frac{\kappa\gamma}{2}\|x_{k+1}-\bar{x}_h\|^2. \tag*{(13)} h ( z t ) ≤ h ( x k + 1 ) − κ t ( h ( x k + 1 ) − h ( x ˉ h ) ) − t ( 1 − 2 − κ t ) 2 κγ ∥ x k + 1 − x ˉ h ∥ 2 . (13)
Using (2), we obtain
∥ z t − y k ∥ 2 = t ∥ x ˉ h − y k ∥ 2 + ( 1 − t ) ∥ x k + 1 − y k ∥ 2 − t ( 1 − t ) ∥ x k + 1 − x ˉ h ∥ 2 . (14) \|z_t-y_k\|^2=t\|\bar{x}_h-y_k\|^2+(1-t)\|x_{k+1}-y_k\|^2-t(1-t)\|x_{k+1}-\bar{x}_h\|^2. \tag*{(14)} ∥ z t − y k ∥ 2 = t ∥ x ˉ h − y k ∥ 2 + ( 1 − t ) ∥ x k + 1 − y k ∥ 2 − t ( 1 − t ) ∥ x k + 1 − x ˉ h ∥ 2 . (14)
Taking z = z t z=z_t z = z t in (12), and using (13) and (14), we have
2 t β k κ ( h ( x k + 1 ) − h ( x ˉ h ) ) ≤ t ∥ y k − x ˉ h ∥ 2 − t ∥ x k + 1 − y k ∥ 2 − t ( 1 − t ) ∥ x k + 1 − x ˉ h ∥ 2 − 2 β k t ( 1 − t 2 − κ ) κ γ 2 ∥ x k + 1 − x ˉ h ∥ 2 . \begin{aligned}
2t\beta_k\kappa\bigl(h(x_{k+1})-h(\bar{x}_h)\bigr)
&\le t\|y_k-\bar{x}_h\|^2-t\|x_{k+1}-y_k\|^2-t(1-t)\|x_{k+1}-\bar{x}_h\|^2\\
&\quad-2\beta_k t\left(1-\frac{t}{2-\kappa}\right)\frac{\kappa\gamma}{2}\|x_{k+1}-\bar{x}_h\|^2.
\end{aligned} 2 t β k κ ( h ( x k + 1 ) − h ( x ˉ h ) ) ≤ t ∥ y k − x ˉ h ∥ 2 − t ∥ x k + 1 − y k ∥ 2 − t ( 1 − t ) ∥ x k + 1 − x ˉ h ∥ 2 − 2 β k t ( 1 − 2 − κ t ) 2 κγ ∥ x k + 1 − x ˉ h ∥ 2 .
Dividing by t > 0 t>0 t > 0 and letting t ↓ 0 t\downarrow0 t ↓ 0 yields
2 β k κ ( h ( x k + 1 ) − h ( x ˉ h ) ) ≤ ∥ y k − x ˉ h ∥ 2 − ∥ x k + 1 − y k ∥ 2 − ∥ x k + 1 − x ˉ h ∥ 2 − β k κ γ ∥ x k + 1 − x ˉ h ∥ 2 . 2\beta_k\kappa\bigl(h(x_{k+1})-h(\bar{x}_h)\bigr)\le\|y_k-\bar{x}_h\|^2-\|x_{k+1}-y_k\|^2-\|x_{k+1}-\bar{x}_h\|^2-\beta_k\kappa\gamma\|x_{k+1}-\bar{x}_h\|^2. 2 β k κ ( h ( x k + 1 ) − h ( x ˉ h ) ) ≤ ∥ y k − x ˉ h ∥ 2 − ∥ x k + 1 − y k ∥ 2 − ∥ x k + 1 − x ˉ h ∥ 2 − β k κγ ∥ x k + 1 − x ˉ h ∥ 2 .
Adding and subtracting x x x inside the two squared norms gives
∥ y k − x ˉ h ∥ 2 = ∥ y k − x ∥ 2 + 2 ⟨ y k − x , x − x ˉ h ⟩ + ∥ x − x ˉ h ∥ 2 , \|y_k-\bar{x}_h\|^2=\|y_k-x\|^2+2\langle y_k-x,x-\bar{x}_h\rangle+\|x-\bar{x}_h\|^2, ∥ y k − x ˉ h ∥ 2 = ∥ y k − x ∥ 2 + 2 ⟨ y k − x , x − x ˉ h ⟩ + ∥ x − x ˉ h ∥ 2 ,
∥ x k + 1 − x ˉ h ∥ 2 = ∥ x k + 1 − x ∥ 2 + 2 ⟨ x k + 1 − x , x − x ˉ h ⟩ + ∥ x − x ˉ h ∥ 2 . \|x_{k+1}-\bar{x}_h\|^2=\|x_{k+1}-x\|^2+2\langle x_{k+1}-x,x-\bar{x}_h\rangle+\|x-\bar{x}_h\|^2. ∥ x k + 1 − x ˉ h ∥ 2 = ∥ x k + 1 − x ∥ 2 + 2 ⟨ x k + 1 − x , x − x ˉ h ⟩ + ∥ x − x ˉ h ∥ 2 .
Then:
2 β k κ ( h ( x k + 1 ) − h ( x ˉ h ) ) ≤ ∥ x − y k ∥ 2 − ∥ x k + 1 − x ∥ 2 − ∥ x k + 1 − y k ∥ 2 + 2 ⟨ y k − x k + 1 , x − x ˉ h ⟩ − κ γ β k ∥ x k + 1 − x ˉ h ∥ 2 . (15) \begin{aligned}
2\beta_k\kappa\bigl(h(x_{k+1})-h(\bar{x}_h)\bigr)
&\le\|x-y_k\|^2-\|x_{k+1}-x\|^2-\|x_{k+1}-y_k\|^2\\
&\quad+2\langle y_k-x_{k+1},x-\bar{x}_h\rangle-\kappa\gamma\beta_k\|x_{k+1}-\bar{x}_h\|^2. \tag*{(15)}
\end{aligned} 2 β k κ ( h ( x k + 1 ) − h ( x ˉ h ) ) ≤ ∥ x − y k ∥ 2 − ∥ x k + 1 − x ∥ 2 − ∥ x k + 1 − y k ∥ 2 + 2 ⟨ y k − x k + 1 , x − x ˉ h ⟩ − κγ β k ∥ x k + 1 − x ˉ h ∥ 2 . (15)
By (5), we have
2 β k κ ( h ( x ˉ h ) − h ( x ) ) ≤ − κ 2 γ β k 2 − κ ∥ x − x ˉ h ∥ 2 . (16) 2\beta_k\kappa\bigl(h(\bar{x}_h)-h(x)\bigr)\le-\frac{\kappa^2\gamma\beta_k}{2-\kappa}\lVert x-\bar{x}_h\rVert^2. \tag*{(16)} 2 β k κ ( h ( x ˉ h ) − h ( x ) ) ≤ − 2 − κ κ 2 γ β k ∥ x − x ˉ h ∥ 2 . (16)
Adding (15) and (16) gives
2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ∥ x k + 1 − y k ∥ 2 − ∥ x k + 1 − x ∥ 2 + 2 ⟨ y k − x k + 1 , x − x ˉ h ⟩ − κ γ β k ∥ x k + 1 − x ˉ h ∥ 2 − κ 2 γ β k 2 − κ ∥ x − x ˉ h ∥ 2 . (17) \begin{aligned}
2\beta_k\kappa\bigl(h(x_{k+1})-h(x)\bigr)
&\le\lVert x-y_k\rVert^2-\lVert x_{k+1}-y_k\rVert^2-\lVert x_{k+1}-x\rVert^2\\
&\quad+2\langle y_k-x_{k+1},x-\bar{x}_h\rangle-\kappa\gamma\beta_k\lVert x_{k+1}-\bar{x}_h\rVert^2-\frac{\kappa^2\gamma\beta_k}{2-\kappa}\lVert x-\bar{x}_h\rVert^2. \tag*{(17)}
\end{aligned} 2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ∥ x k + 1 − y k ∥ 2 − ∥ x k + 1 − x ∥ 2 + 2 ⟨ y k − x k + 1 , x − x ˉ h ⟩ − κγ β k ∥ x k + 1 − x ˉ h ∥ 2 − 2 − κ κ 2 γ β k ∥ x − x ˉ h ∥ 2 . (17)
Applying identity (2) with u = x − x ˉ h u=x-\bar{x}_h u = x − x ˉ h , v = x k + 1 − x ˉ h v=x_{k+1}-\bar{x}_h v = x k + 1 − x ˉ h , and any θ ∈ ] 0 , 1 [ \theta\in]0,1[ θ ∈ ] 0 , 1 [ , we obtain
0 ≤ ∥ θ ( x − x ˉ h ) + ( 1 − θ ) ( x k + 1 − x ˉ h ) ∥ 2 = ( 1 − θ ) ∥ x k + 1 − x ˉ h ∥ 2 + θ ∥ x − x ˉ h ∥ 2 − θ ( 1 − θ ) ∥ x k + 1 − x ∥ 2 . \begin{aligned}
0&\le\lVert\theta(x-\bar{x}_h)+(1-\theta)(x_{k+1}-\bar{x}_h)\rVert^2\\
&=(1-\theta)\lVert x_{k+1}-\bar{x}_h\rVert^2+\theta\lVert x-\bar{x}_h\rVert^2-\theta(1-\theta)\lVert x_{k+1}-x\rVert^2.
\end{aligned} 0 ≤ ∥ θ ( x − x ˉ h ) + ( 1 − θ ) ( x k + 1 − x ˉ h ) ∥ 2 = ( 1 − θ ) ∥ x k + 1 − x ˉ h ∥ 2 + θ ∥ x − x ˉ h ∥ 2 − θ ( 1 − θ ) ∥ x k + 1 − x ∥ 2 .
Rearranging terms gives
− ∥ x k + 1 − x ˉ h ∥ 2 ≤ − θ ∥ x k + 1 − x ∥ 2 + θ 1 − θ ∥ x − x ˉ h ∥ 2 . (18) -\lVert x_{k+1}-\bar{x}_h\rVert^2\le-\theta\lVert x_{k+1}-x\rVert^2+\frac{\theta}{1-\theta}\lVert x-\bar{x}_h\rVert^2. \tag*{(18)} − ∥ x k + 1 − x ˉ h ∥ 2 ≤ − θ ∥ x k + 1 − x ∥ 2 + 1 − θ θ ∥ x − x ˉ h ∥ 2 . (18)
Next, for any ε k > 0 \varepsilon_k>0 ε k > 0 , the following inequality holds
2 ⟨ y k − x k + 1 , x − x ˉ h ⟩ ≤ 1 ε k ∥ x k + 1 − y k ∥ 2 + ε k ∥ x − x ˉ h ∥ 2 . (19) 2\langle y_k-x_{k+1},x-\bar{x}_h\rangle\le\frac{1}{\varepsilon_k}\lVert x_{k+1}-y_k\rVert^2+\varepsilon_k\lVert x-\bar{x}_h\rVert^2. \tag*{(19)} 2 ⟨ y k − x k + 1 , x − x ˉ h ⟩ ≤ ε k 1 ∥ x k + 1 − y k ∥ 2 + ε k ∥ x − x ˉ h ∥ 2 . (19)
Substituting (18) and (19) into (17), we obtain
2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ( 1 + β k κ γ θ ) ∥ x k + 1 − x ∥ 2 + ( 1 ε k − 1 ) ∥ x k + 1 − y k ∥ 2 + ( ε k + β k κ γ θ 1 − θ − β k κ 2 γ 2 − κ ) ∥ x − x ˉ h ∥ 2 . \begin{aligned}
2\beta_k\kappa\bigl(h(x_{k+1})-h(x)\bigr)
&\le\lVert x-y_k\rVert^2-(1+\beta_k\kappa\gamma\theta)\lVert x_{k+1}-x\rVert^2\\
&\quad+\left(\frac{1}{\varepsilon_k}-1\right)\lVert x_{k+1}-y_k\rVert^2
+\left(\varepsilon_k+\frac{\beta_k\kappa\gamma\theta}{1-\theta}-\frac{\beta_k\kappa^2\gamma}{2-\kappa}\right)\lVert x-\bar{x}_h\rVert^2.
\end{aligned} 2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ( 1 + β k κγ θ ) ∥ x k + 1 − x ∥ 2 + ( ε k 1 − 1 ) ∥ x k + 1 − y k ∥ 2 + ( ε k + 1 − θ β k κγ θ − 2 − κ β k κ 2 γ ) ∥ x − x ˉ h ∥ 2 .
We now choose
ε k = β k γ ( κ 2 2 − κ − κ θ 1 − θ ) . \varepsilon_k=\beta_k\gamma\left(\frac{\kappa^2}{2-\kappa}-\frac{\kappa\theta}{1-\theta}\right). ε k = β k γ ( 2 − κ κ 2 − 1 − θ κ θ ) .
which cancels the coefficient of ∥ x − x ˉ h ∥ 2 \lVert x-\bar{x}_h\rVert^2 ∥ x − x ˉ h ∥ 2 . The parameter θ \theta θ can be chosen in ] 0 , κ 2 [ ]0,\frac{\kappa}{2}[ ] 0 , 2 κ [ so that ε k > 0 \varepsilon_k>0 ε k > 0 . In particular, for every δ > 0 \delta>0 δ > 0 , the choice θ = κ 2 + δ \theta=\frac{\kappa}{2+\delta} θ = 2 + δ κ satisfies this condition. With this choice of parameters, we obtain
2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ( 1 + β k κ γ θ ) ∥ x k + 1 − x ∥ 2 + ( 1 ε k − 1 ) ∥ x k + 1 − y k ∥ 2 . 2\beta_k\kappa\bigl(h(x_{k+1})-h(x)\bigr)\le\lVert x-y_k\rVert^2-(1+\beta_k\kappa\gamma\theta)\lVert x_{k+1}-x\rVert^2+\left(\frac{1}{\varepsilon_k}-1\right)\lVert x_{k+1}-y_k\rVert^2. 2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ( 1 + β k κγ θ ) ∥ x k + 1 − x ∥ 2 + ( ε k 1 − 1 ) ∥ x k + 1 − y k ∥ 2 .
Substituting θ = κ / ( 2 + δ ) \theta=\kappa/(2+\delta) θ = κ / ( 2 + δ ) and the corresponding value of ε k \varepsilon_k ε k into the above inequality yields (11). □
We next observe that the coefficient C k C_k C k in (11) becomes nonpositive whenever
β k ≥ ( 2 − κ ) ( 2 + δ − κ ) κ 2 γ δ . \beta_k\ge\frac{(2-\kappa)(2+\delta-\kappa)}{\kappa^2\gamma\delta}. β k ≥ κ 2 γ δ ( 2 − κ ) ( 2 + δ − κ ) .
In this case, the last term in (11) can be omitted. For simplicity, we consider δ = 1 \delta=1 δ = 1 , leading to the following corollary.
Corollary 3.3. Under the assumptions of Theorem 3.2 , if
β k ≥ β ′ ≥ ( 2 − κ ) ( 3 − κ ) κ 2 γ > 0 , ∀ k ∈ N , (20) \beta_k \ge\beta' \ge\frac{(2-\kappa)(3-\kappa)}{\kappa^2\gamma} > 0,\quad\forall k \in\mathbb{N}, \tag*{(20)} β k ≥ β ′ ≥ κ 2 γ ( 2 − κ ) ( 3 − κ ) > 0 , ∀ k ∈ N , (20) then
2 β k κ ( h ( x k + 1 ) − h ( x ) ) ≤ ∥ x − y k ∥ 2 − ( 1 + β k κ 2 γ 3 ) ∥ x k + 1 − x ∥ 2 . (21) 2\beta_k\kappa(h(x_{k+1})-h(x)) \le\lVert x-y_k\rVert^2-\left(1+\frac{\beta_k\kappa^2\gamma}{3}\right)\lVert x_{k+1}-x\rVert^2. \tag*{(21)} 2 β k κ ( h ( x k + 1 ) − h ( x )) ≤ ∥ x − y k ∥ 2 − ( 1 + 3 β k κ 2 γ ) ∥ x k + 1 − x ∥ 2 . (21)
Remark 3.4. Condition (20) is sufficient only for dropping the proximal residual in this corollary. It is not imposed in the convergence results below, which retain the residual in Proposition 3.5.
The main consequence of the previous theorem is the following composite inequality.
Proposition 3.5. (Composite Inequality) Assume (H1)–(H2), let f = g + h f=g+h f = g + h , and let { x k } k \{x_k\}_k { x k } k be generated by Algorithm 1. For every δ > 0 \delta>0 δ > 0 and any x ∈ dom f x\in\operatorname{dom} f x ∈ dom f , the following inequality holds:
2 κ β k ( f ( x k + 1 ) − f ( x ) ) ≤ ( 1 − κ β k μ ) ∥ x − x k ∥ 2 − ( 1 + β k κ 2 γ 2 + δ ) ∥ x k + 1 − x ∥ 2 + D k ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 , (22) \begin{aligned}
2\kappa\beta_k(f(x_{k+1})-f(x)) \le{} &(1-\kappa\beta_k\mu)\lVert x-x_k\rVert^2-\left(1+\frac{\beta_k\kappa^2\gamma}{2+\delta}\right)\lVert x_{k+1}-x\rVert^2\\
&+D_k\lVert x_{k+1}-y_k\rVert^2-(1-\kappa\beta_kL)\lVert x_{k+1}-x_k\rVert^2, \tag*{(22)}
\end{aligned} 2 κ β k ( f ( x k + 1 ) − f ( x )) ≤ ( 1 − κ β k μ ) ∥ x − x k ∥ 2 − ( 1 + 2 + δ β k κ 2 γ ) ∥ x k + 1 − x ∥ 2 + D k ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 , (22) where D k : = ( 2 − κ ) ( 2 + δ − κ ) β k γ κ 2 δ D_k:=\frac{(2-\kappa)(2+\delta-\kappa)}{\beta_k\gamma\kappa^2\delta} D k := β k γ κ 2 δ ( 2 − κ ) ( 2 + δ − κ ) .
Proof. By the μ \mu μ -strong convexity of g g g , for all x ∈ dom h x\in\operatorname{dom} h x ∈ dom h , we have
g ( x k ) + ⟨ ∇ g ( x k ) , x − x k ⟩ + μ 2 ∥ x − x k ∥ 2 ≤ g ( x ) . (23) g(x_k)+\langle\nabla g(x_k),x-x_k\rangle+\frac{\mu}{2}\lVert x-x_k\rVert^2\le g(x). \tag*{(23)} g ( x k ) + ⟨ ∇ g ( x k ) , x − x k ⟩ + 2 μ ∥ x − x k ∥ 2 ≤ g ( x ) . (23)
Applying the descent lemma (4) yields
g ( x k + 1 ) ≤ g ( x k ) + ⟨ ∇ g ( x k ) , x k + 1 − x k ⟩ + L 2 ∥ x k + 1 − x k ∥ 2 . (24) g(x_{k+1})\le g(x_k)+\langle\nabla g(x_k),x_{k+1}-x_k\rangle+\frac{L}{2}\lVert x_{k+1}-x_k\rVert^2. \tag*{(24)} g ( x k + 1 ) ≤ g ( x k ) + ⟨ ∇ g ( x k ) , x k + 1 − x k ⟩ + 2 L ∥ x k + 1 − x k ∥ 2 . (24)
Subtracting (23) from (24) , we obtain
g ( x k + 1 ) − g ( x ) ≤ ⟨ ∇ g ( x k ) , x k + 1 − x ⟩ + L 2 ∥ x k + 1 − x k ∥ 2 − μ 2 ∥ x − x k ∥ 2 . (25) g(x_{k+1})-g(x)\le\langle\nabla g(x_k),x_{k+1}-x\rangle+\frac{L}{2}\lVert x_{k+1}-x_k\rVert^2-\frac{\mu}{2}\lVert x-x_k\rVert^2. \tag*{(25)} g ( x k + 1 ) − g ( x ) ≤ ⟨ ∇ g ( x k ) , x k + 1 − x ⟩ + 2 L ∥ x k + 1 − x k ∥ 2 − 2 μ ∥ x − x k ∥ 2 . (25)
Observe that
∥ x − y k ∥ 2 = ∥ x − x k ∥ 2 + 2 ⟨ x − x k , x k − y k ⟩ + ∥ x k − y k ∥ 2 = ∥ x − x k ∥ 2 + 2 β k κ ⟨ x − x k , ∇ g ( x k ) ⟩ + ∥ x k − y k ∥ 2 . (26) \begin{aligned}
\lVert x-y_k\rVert^2&=\lVert x-x_k\rVert^2+2\langle x-x_k,x_k-y_k\rangle+\lVert x_k-y_k\rVert^2\\
&=\lVert x-x_k\rVert^2+2\beta_k\kappa\langle x-x_k,\nabla g(x_k)\rangle+\lVert x_k-y_k\rVert^2. \tag*{(26)}
\end{aligned} ∥ x − y k ∥ 2 = ∥ x − x k ∥ 2 + 2 ⟨ x − x k , x k − y k ⟩ + ∥ x k − y k ∥ 2 = ∥ x − x k ∥ 2 + 2 β k κ ⟨ x − x k , ∇ g ( x k )⟩ + ∥ x k − y k ∥ 2 . (26)
Expanding the inner product and using (25) gives
2 β k κ ⟨ x − x k , ∇ g ( x k ) ⟩ = 2 β k κ ⟨ x − x k + 1 , ∇ g ( x k ) ⟩ + 2 β k κ ⟨ x k + 1 − x k , ∇ g ( x k ) ⟩ ≤ 2 κ β k ( g ( x ) − g ( x k + 1 ) + L 2 ∥ x k + 1 − x k ∥ 2 − μ 2 ∥ x − x k ∥ 2 ) + 2 ⟨ x k + 1 − x k , x k − y k ⟩ . (27) \begin{aligned}
2\beta_k\kappa\langle x-x_k,\nabla g(x_k)\rangle={}&2\beta_k\kappa\langle x-x_{k+1},\nabla g(x_k)\rangle+2\beta_k\kappa\langle x_{k+1}-x_k,\nabla g(x_k)\rangle\\
\le{}&2\kappa\beta_k\left(g(x)-g(x_{k+1})+\frac{L}{2}\lVert x_{k+1}-x_k\rVert^2-\frac{\mu}{2}\lVert x-x_k\rVert^2\right)\\
&+2\langle x_{k+1}-x_k,x_k-y_k\rangle. \tag*{(27)}
\end{aligned} 2 β k κ ⟨ x − x k , ∇ g ( x k )⟩ = ≤ 2 β k κ ⟨ x − x k + 1 , ∇ g ( x k )⟩ + 2 β k κ ⟨ x k + 1 − x k , ∇ g ( x k )⟩ 2 κ β k ( g ( x ) − g ( x k + 1 ) + 2 L ∥ x k + 1 − x k ∥ 2 − 2 μ ∥ x − x k ∥ 2 ) + 2 ⟨ x k + 1 − x k , x k − y k ⟩ . (27)
Using identity (1),
2 ⟨ x k + 1 − x k , x k − y k ⟩ = ∥ x k + 1 − y k ∥ 2 − ∥ x k + 1 − x k ∥ 2 − ∥ y k − x k ∥ 2 2\langle x_{k+1}-x_k,x_k-y_k\rangle=\|x_{k+1}-y_k\|^2-\|x_{k+1}-x_k\|^2-\|y_k-x_k\|^2 2 ⟨ x k + 1 − x k , x k − y k ⟩ = ∥ x k + 1 − y k ∥ 2 − ∥ x k + 1 − x k ∥ 2 − ∥ y k − x k ∥ 2
we obtain
2 β k κ ⟨ x − x k , ∇ g ( x k ) ⟩ ≤ 2 κ β k ( g ( x ) − g ( x k + 1 ) ) − κ β k μ ∥ x − x k ∥ 2 + ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 − ∥ y k − x k ∥ 2 (28) 2\beta_k\kappa\langle x-x_k,\nabla g(x_k)\rangle\le2\kappa\beta_k\bigl(g(x)-g(x_{k+1})\bigr)-\kappa\beta_k\mu\|x-x_k\|^2+\|x_{k+1}-y_k\|^2
-(1-\kappa\beta_kL)\|x_{k+1}-x_k\|^2-\|y_k-x_k\|^2 \tag*{(28)} 2 β k κ ⟨ x − x k , ∇ g ( x k )⟩ ≤ 2 κ β k ( g ( x ) − g ( x k + 1 ) ) − κ β k μ ∥ x − x k ∥ 2 + ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 − ∥ y k − x k ∥ 2 (28)
Substituting (28) into (26) yields
∥ x − y k ∥ 2 ≤ ( 1 − κ β k μ ) ∥ x k − x ∥ 2 + 2 κ β k ( g ( x ) − g ( x k + 1 ) ) + ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 . (29) \|x-y_k\|^2\le(1-\kappa\beta_k\mu)\|x_k-x\|^2+2\kappa\beta_k\bigl(g(x)-g(x_{k+1})\bigr)+\|x_{k+1}-y_k\|^2
-(1-\kappa\beta_kL)\|x_{k+1}-x_k\|^2. \tag*{(29)} ∥ x − y k ∥ 2 ≤ ( 1 − κ β k μ ) ∥ x k − x ∥ 2 + 2 κ β k ( g ( x ) − g ( x k + 1 ) ) + ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 . (29)
Rewriting (29), we get
2 κ β k ( g ( x k + 1 ) − g ( x ) ) ≤ ( 1 − κ β k μ ) ∥ x − x k ∥ 2 − ∥ x − y k ∥ 2 + ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 . (30) 2\kappa\beta_k\bigl(g(x_{k+1})-g(x)\bigr)\le(1-\kappa\beta_k\mu)\|x-x_k\|^2-\|x-y_k\|^2+\|x_{k+1}-y_k\|^2
-(1-\kappa\beta_kL)\|x_{k+1}-x_k\|^2. \tag*{(30)} 2 κ β k ( g ( x k + 1 ) − g ( x ) ) ≤ ( 1 − κ β k μ ) ∥ x − x k ∥ 2 − ∥ x − y k ∥ 2 + ∥ x k + 1 − y k ∥ 2 − ( 1 − κ β k L ) ∥ x k + 1 − x k ∥ 2 . (30)
Adding (30) to (11) from Theorem 3.2 completes the proof.
Convergence Results
Throughout this subsection, { x k } k \{x_k\}_k { x k } k is generated by Algorithm 1 from x 1 ∈ dom h x_1\in\operatorname{dom} h x 1 ∈ dom h . If the algorithm stops, its sequence is extended constantly. The general hypotheses are (H1)–(H2). In particular, quasar-convexity is global and μ ≥ 0 \mu\ge0 μ ≥ 0 denotes the strong-convexity modulus of g g g .
Lemma 3.6. Under (H1)–(H2), for every x ∈ dom h x\in\operatorname{dom} h x ∈ dom h , we have
h ( x ) ≥ h ( x ˉ h ) + κ γ 2 ( 2 − κ ) ∥ x − x ˉ h ∥ 2 . h(x)\ge h(\bar{x}_h)+\frac{\kappa\gamma}{2(2-\kappa)}\|x-\bar{x}_h\|^2. h ( x ) ≥ h ( x ˉ h ) + 2 ( 2 − κ ) κγ ∥ x − x ˉ h ∥ 2 . Consequently, F κ : = κ g + h F_\kappa:=\kappa g+h F κ := κ g + h and f = g + h f=g+h f = g + h are coercive, and in particular have bounded sublevel sets and attain their minima.
Proof. The first claim is (5). Convexity gives g ( x ) ≥ g ( x ˉ h ) + ⟨ ∇ g ( x ˉ h ) , x − x ˉ h ⟩ g(x)\ge g(\bar{x}_h)+\langle\nabla g(\bar{x}_h),x-\bar{x}_h\rangle g ( x ) ≥ g ( x ˉ h ) + ⟨ ∇ g ( x ˉ h ) , x − x ˉ h ⟩ . The quadratic lower bound for h h h dominates this affine term as ∥ x ∥ → + ∞ \|x\|\to+\infty ∥ x ∥ → + ∞ , proving coercivity of both F κ F_\kappa F κ and f f f . Properness and lower semicontinuity then imply that both objectives attain their minima.
Lemma 3.7. Assume (H1)–(H2). For any κ ∈ ] 0 , 1 ] \kappa\in]0,1] κ ∈ ] 0 , 1 ] and 0 < β k ≤ 1 / ( κ L ) 0<\beta_k\le1/(\kappa L) 0 < β k ≤ 1/ ( κ L ) , we have
F κ ( x k + 1 ) ≤ F κ ( x k ) − ( 1 2 β k − κ L 2 ) ∥ x k + 1 − x k ∥ 2 , F κ : = κ g + h . F_\kappa(x_{k+1})\le F_\kappa(x_k)-\left(\frac{1}{2\beta_k}-\frac{\kappa L}{2}\right)\|x_{k+1}-x_k\|^2,\qquad F_\kappa:=\kappa g+h. F κ ( x k + 1 ) ≤ F κ ( x k ) − ( 2 β k 1 − 2 κ L ) ∥ x k + 1 − x k ∥ 2 , F κ := κ g + h .
Proof. By proximal optimality of x k + 1 x_{k+1} x k + 1 with comparison point z = x k z=x_k z = x k , we have
h ( x k + 1 ) + 1 2 β k ∥ x k + 1 − y k ∥ 2 ≤ h ( x k ) + 1 2 β k ∥ x k − y k ∥ 2 . h(x_{k+1})+\frac{1}{2\beta_k}\lVert x_{k+1}-y_k\rVert^2\le h(x_k)+\frac{1}{2\beta_k}\lVert x_k-y_k\rVert^2. h ( x k + 1 ) + 2 β k 1 ∥ x k + 1 − y k ∥ 2 ≤ h ( x k ) + 2 β k 1 ∥ x k − y k ∥ 2 .
Using y k = x k − κ β k ∇ g ( x k ) y_k=x_k-\kappa\beta_k\nabla g(x_k) y k = x k − κ β k ∇ g ( x k ) to expand both squared norms, we cancel the common terms κ 2 β k 2 ∥ ∇ g ( x k ) ∥ 2 \frac{\kappa^2\beta_k}{2}\lVert\nabla g(x_k)\rVert^2 2 κ 2 β k ∥ ∇ g ( x k ) ∥ 2 and obtain
h ( x k + 1 ) ≤ h ( x k ) − κ ⟨ ∇ g ( x k ) , x k + 1 − x k ⟩ − 1 2 β k ∥ x k + 1 − x k ∥ 2 . h(x_{k+1})\le h(x_k)-\kappa\langle\nabla g(x_k),x_{k+1}-x_k\rangle-\frac{1}{2\beta_k}\lVert x_{k+1}-x_k\rVert^2. h ( x k + 1 ) ≤ h ( x k ) − κ ⟨ ∇ g ( x k ) , x k + 1 − x k ⟩ − 2 β k 1 ∥ x k + 1 − x k ∥ 2 .
Adding κ \kappa κ times the descent lemma (4) , namely κ g ( x k + 1 ) ≤ κ g ( x k ) + κ ⟨ ∇ g ( x k ) , x k + 1 − x k ⟩ + κ L 2 ∥ x k + 1 − x k ∥ 2 \kappa g(x_{k+1})\le\kappa g(x_k)+\kappa\langle\nabla g(x_k),x_{k+1}-x_k\rangle+\frac{\kappa L}{2}\lVert x_{k+1}-x_k\rVert^2 κ g ( x k + 1 ) ≤ κ g ( x k ) + κ ⟨ ∇ g ( x k ) , x k + 1 − x k ⟩ + 2 κ L ∥ x k + 1 − x k ∥ 2 , cancels the inner-product terms and proves the claim. □
Lemma 3.8. Assume (H1)–(H2). Let 0 < β k ≡ β < 1 κ L 0<\beta_k\equiv\beta<\frac{1}{\kappa L} 0 < β k ≡ β < κ L 1 . Then, by Lemma 3.7, { F κ ( x k ) } k \{F_\kappa(x_k)\}_k { F κ ( x k ) } k is nonincreasing, and
(a) { x k } k \{x_k\}_k { x k } k is bounded, and consequently M : = sup k ∈ N ∥ ∇ g ( x k ) ∥ < + ∞ M:=\sup_{k\in\mathbb{N}}\lVert\nabla g(x_k)\rVert<+\infty M := sup k ∈ N ∥ ∇ g ( x k )∥ < + ∞ ;
(b) ∑ k = 1 ∞ ∥ x k + 1 − x k ∥ 2 < + ∞ \sum_{k=1}^{\infty}\lVert x_{k+1}-x_k\rVert^2<+\infty ∑ k = 1 ∞ ∥ x k + 1 − x k ∥ 2 < + ∞ . In particular, ∥ x k + 1 − x k ∥ → 0 \lVert x_{k+1}-x_k\rVert\to0 ∥ x k + 1 − x k ∥ → 0 .
Proof. By Lemma 3.7, F κ ( x k + 1 ) ≤ F κ ( x k ) − ( 1 2 β − κ L 2 ) ∥ x k + 1 − x k ∥ 2 F_\kappa(x_{k+1})\le F_\kappa(x_k)-\left(\frac{1}{2\beta}-\frac{\kappa L}{2}\right)\lVert x_{k+1}-x_k\rVert^2 F κ ( x k + 1 ) ≤ F κ ( x k ) − ( 2 β 1 − 2 κ L ) ∥ x k + 1 − x k ∥ 2 , so { F κ ( x k ) } k \{F_\kappa(x_k)\}_k { F κ ( x k ) } k is nonincreasing and F κ ( x k ) ≤ F κ ( x 1 ) F_\kappa(x_k)\le F_\kappa(x_1) F κ ( x k ) ≤ F κ ( x 1 ) for every k k k .
(a): By Lemma 3.6, F κ F_\kappa F κ is coercive, so the sublevel set { x : F κ ( x ) ≤ F κ ( x 1 ) } \{x:F_\kappa(x)\le F_\kappa(x_1)\} { x : F κ ( x ) ≤ F κ ( x 1 )} is bounded. Since { x k } k \{x_k\}_k { x k } k lies in this set, it is bounded, and by continuity of ∇ g \nabla g ∇ g , we have M : = sup k ∥ ∇ g ( x k ) ∥ < + ∞ M:=\sup_k\lVert\nabla g(x_k)\rVert<+\infty M := sup k ∥ ∇ g ( x k )∥ < + ∞ .
(b): Since β < 1 κ L \beta<\frac{1}{\kappa L} β < κ L 1 , c 0 : = 1 2 β − κ L 2 > 0 c_0:=\frac{1}{2\beta}-\frac{\kappa L}{2}>0 c 0 := 2 β 1 − 2 κ L > 0 . Summing the inequality of Lemma 3.7 from k = 1 k=1 k = 1 to K K K gives
c 0 ∑ k = 1 K ∥ x k + 1 − x k ∥ 2 ≤ F κ ( x 1 ) − F κ ( x K + 1 ) ≤ F κ ( x 1 ) − inf R n F κ , c_0\sum_{k=1}^{K}\lVert x_{k+1}-x_k\rVert^2\le F_\kappa(x_1)-F_\kappa(x_{K+1})\le F_\kappa(x_1)-\inf_{\mathbb{R}^n}F_\kappa, c 0 k = 1 ∑ K ∥ x k + 1 − x k ∥ 2 ≤ F κ ( x 1 ) − F κ ( x K + 1 ) ≤ F κ ( x 1 ) − R n inf F κ ,
and the right-hand side is finite since F κ F_\kappa F κ is proper, lsc and coercive. Letting K → + ∞ K\to+\infty K → + ∞ gives ∑ k ∥ x k + 1 − x k ∥ 2 < + ∞ \sum_k\lVert x_{k+1}-x_k\rVert^2<+\infty ∑ k ∥ x k + 1 − x k ∥ 2 < + ∞ , hence ∥ x k + 1 − x k ∥ → 0 \lVert x_{k+1}-x_k\rVert\to0 ∥ x k + 1 − x k ∥ → 0 . □
We now show that every accumulation point of the sequence generated by Algorithm 1 is a κ \kappa κ -critical point of f = g + h f=g+h f = g + h in the sense of (8) , i.e., a critical point of F κ = κ g + h F_\kappa=\kappa g+h F κ = κ g + h .
Lemma 3.9 (Subgradient bound). Assume (H1)–(H2). Let 0 < β k ≡ β < 1 / ( κ L ) 0<\beta_k\equiv\beta<1/(\kappa L) 0 < β k ≡ β < 1/ ( κ L ) . For every k ∈ N k\in\mathbb{N} k ∈ N , define
w k + 1 : = κ ( ∇ g ( x k + 1 ) − ∇ g ( x k ) ) + x k − x k + 1 β . w_{k+1}:=\kappa\bigl(\nabla g(x_{k+1})-\nabla g(x_k)\bigr)+\frac{x_k-x_{k+1}}{\beta}. w k + 1 := κ ( ∇ g ( x k + 1 ) − ∇ g ( x k ) ) + β x k − x k + 1 . Then w k + 1 ∈ κ ∇ g ( x k + 1 ) + ∂ L h ( x k + 1 ) w_{k+1}\in\kappa\nabla g(x_{k+1})+\partial^L h(x_{k+1}) w k + 1 ∈ κ ∇ g ( x k + 1 ) + ∂ L h ( x k + 1 ) and
∥ w k + 1 ∥ ≤ ( κ L + 1 β ) ∥ x k + 1 − x k ∥ , ∀ k ∈ N . \lVert w_{k+1}\rVert\le\left(\kappa L+\frac{1}{\beta}\right)\lVert x_{k+1}-x_k\rVert,\qquad\forall k\in\mathbb{N}. ∥ w k + 1 ∥ ≤ ( κ L + β 1 ) ∥ x k + 1 − x k ∥ , ∀ k ∈ N . In particular, by Lemma 3.8(b), w k + 1 → 0 w_{k+1}\to0 w k + 1 → 0 as k → + ∞ k\to+\infty k → + ∞ .
Proof. By proximal optimality of x k + 1 ∈ Prox β h ( y k ) x_{k+1} \in\operatorname{Prox}_{\beta h}(y_k) x k + 1 ∈ Prox β h ( y k ) and the sum rule for ∂ L h \partial^L h ∂ L h , we have
0 ∈ ∂ L h ( x k + 1 ) + 1 β ( x k + 1 − y k ) ⟺ y k − x k + 1 β ∈ ∂ L h ( x k + 1 ) . 0 \in\partial^L h(x_{k+1})+\frac{1}{\beta}(x_{k+1}-y_k) \Longleftrightarrow\frac{y_k-x_{k+1}}{\beta} \in\partial^L h(x_{k+1}). 0 ∈ ∂ L h ( x k + 1 ) + β 1 ( x k + 1 − y k ) ⟺ β y k − x k + 1 ∈ ∂ L h ( x k + 1 ) .
Since y k = x k − κ β ∇ g ( x k ) y_k=x_k-\kappa\beta\nabla g(x_k) y k = x k − κ β ∇ g ( x k ) ,
y k − x k + 1 β = x k − x k + 1 β − κ ∇ g ( x k ) ∈ ∂ L h ( x k + 1 ) . \frac{y_k-x_{k+1}}{\beta}=\frac{x_k-x_{k+1}}{\beta}-\kappa\nabla g(x_k)\in\partial^L h(x_{k+1}). β y k − x k + 1 = β x k − x k + 1 − κ ∇ g ( x k ) ∈ ∂ L h ( x k + 1 ) .
Adding κ ∇ g ( x k + 1 ) \kappa\nabla g(x_{k+1}) κ ∇ g ( x k + 1 ) to both sides gives
w k + 1 = κ ( ∇ g ( x k + 1 ) − ∇ g ( x k ) ) + x k − x k + 1 β ∈ κ ∇ g ( x k + 1 ) + ∂ L h ( x k + 1 ) . w_{k+1}=\kappa\bigl(\nabla g(x_{k+1})-\nabla g(x_k)\bigr)+\frac{x_k-x_{k+1}}{\beta}\in\kappa\nabla g(x_{k+1})+\partial^L h(x_{k+1}). w k + 1 = κ ( ∇ g ( x k + 1 ) − ∇ g ( x k ) ) + β x k − x k + 1 ∈ κ ∇ g ( x k + 1 ) + ∂ L h ( x k + 1 ) .
By the triangle inequality and the L L L -Lipschitz continuity (3) of ∇ g \nabla g ∇ g , we obtain
∥ w k + 1 ∥ ≤ κ ∥ ∇ g ( x k + 1 ) − ∇ g ( x k ) ∥ + 1 β ∥ x k + 1 − x k ∥ ≤ ( κ L + 1 β ) ∥ x k + 1 − x k ∥ , \lVert w_{k+1}\rVert\leq\kappa\lVert\nabla g(x_{k+1})-\nabla g(x_k)\rVert+\frac{1}{\beta}\lVert x_{k+1}-x_k\rVert\leq\left(\kappa L+\frac{1}{\beta}\right)\lVert x_{k+1}-x_k\rVert, ∥ w k + 1 ∥ ≤ κ ∥ ∇ g ( x k + 1 ) − ∇ g ( x k )∥ + β 1 ∥ x k + 1 − x k ∥ ≤ ( κ L + β 1 ) ∥ x k + 1 − x k ∥ ,
which is the stated bound. The convergence w k + 1 → 0 w_{k+1}\to0 w k + 1 → 0 then follows from ∥ x k + 1 − x k ∥ → 0 \lVert x_{k+1}-x_k\rVert\to0 ∥ x k + 1 − x k ∥ → 0 (Lemma 3.8 (b)).
Theorem 3.10 (Subsequential convergence to critical points). Assume (H1)–(H2). Let 0 < β k ≡ β < 1 / ( κ L ) 0<\beta_k\equiv\beta<1/(\kappa L) 0 < β k ≡ β < 1/ ( κ L ) . Then { x k } k \{x_k\}_k { x k } k admits at least one accumulation point, and every accumulation point x ^ \hat{x} x ^ of { x k } k \{x_k\}_k { x k } k is a κ \kappa κ -critical point of f = g + h f=g+h f = g + h , i.e.,
0 ∈ κ ∇ g ( x ^ ) + ∂ L h ( x ^ ) . 0\in\kappa\nabla g(\hat{x})+\partial^L h(\hat{x}). 0 ∈ κ ∇ g ( x ^ ) + ∂ L h ( x ^ ) .
Proof. By Lemma 3.8 (a), { x k } k \{x_k\}_k { x k } k is bounded, so it admits a convergent subsequence x k j → x ^ x_{k_j}\to\hat{x} x k j → x ^ . By Lemma 3.8 (b), x k j + 1 − x k j → 0 x_{k_j+1}-x_{k_j}\to0 x k j + 1 − x k j → 0 , hence x k j + 1 → x ^ x_{k_j+1}\to\hat{x} x k j + 1 → x ^ as well. First we verify convergence of the function values, which is required for the limiting-subdifferential argument. By Lemma 3.7 , the sequence { F κ ( x k ) } k \{F_\kappa(x_k)\}_k { F κ ( x k ) } k is nonincreasing. By Lemma 3.6 , F κ F_\kappa F κ has a finite minimum, so this sequence is bounded below. Therefore, F κ ( x k ) → ℓ : = inf k ≥ 1 F κ ( x k ) ∈ R F_\kappa(x_k)\to\ell:=\inf_{k\geq1}F_\kappa(x_k)\in\mathbb{R} F κ ( x k ) → ℓ := inf k ≥ 1 F κ ( x k ) ∈ R . Lower semicontinuity gives F κ ( x ^ ) ≤ ℓ F_\kappa(\hat{x})\leq\ell F κ ( x ^ ) ≤ ℓ , so h ( x ^ ) < + ∞ h(\hat{x})<+\infty h ( x ^ ) < + ∞ . Proximal optimality with comparison point x ^ \hat{x} x ^ gives
h ( x k j + 1 ) + 1 2 β ∥ x k j + 1 − y k j ∥ 2 ≤ h ( x ^ ) + 1 2 β ∥ x ^ − y k j ∥ 2 . h(x_{k_j+1})+\frac{1}{2\beta}\lVert x_{k_j+1}-y_{k_j}\rVert^2\leq h(\hat{x})+\frac{1}{2\beta}\lVert\hat{x}-y_{k_j}\rVert^2. h ( x k j + 1 ) + 2 β 1 ∥ x k j + 1 − y k j ∥ 2 ≤ h ( x ^ ) + 2 β 1 ∥ x ^ − y k j ∥ 2 .
Both squared norms converge to κ 2 β 2 ∥ ∇ g ( x ^ ) ∥ 2 \kappa^2\beta^2\lVert\nabla g(\hat{x})\rVert^2 κ 2 β 2 ∥ ∇ g ( x ^ ) ∥ 2 . Together with lower semicontinuity, this proves h ( x k j + 1 ) → h ( x ^ ) h(x_{k_j+1})\to h(\hat{x}) h ( x k j + 1 ) → h ( x ^ ) , and hence F κ ( x ^ ) = ℓ F_\kappa(\hat{x})=\ell F κ ( x ^ ) = ℓ . By Lemma 3.9 , w k j + 1 ∈ κ ∇ g ( x k j + 1 ) + ∂ L h ( x k j + 1 ) w_{k_j+1}\in\kappa\nabla g(x_{k_j+1})+\partial^L h(x_{k_j+1}) w k j + 1 ∈ κ ∇ g ( x k j + 1 ) + ∂ L h ( x k j + 1 ) with w k j + 1 → 0 w_{k_j+1}\to0 w k j + 1 → 0 . Since κ ∇ g ( ⋅ ) \kappa\nabla g(\cdot) κ ∇ g ( ⋅ ) is continuous and the limiting subdifferential is closed along value-convergent sequences, letting j → + ∞ j\to+\infty j → + ∞ yields
0 = lim j → + ∞ w k j + 1 ∈ κ ∇ g ( x ^ ) + ∂ L h ( x ^ ) , 0=\lim_{j\to+\infty}w_{k_j+1}\in\kappa\nabla g(\hat{x})+\partial^L h(\hat{x}), 0 = j → + ∞ lim w k j + 1 ∈ κ ∇ g ( x ^ ) + ∂ L h ( x ^ ) ,
which is (8) .
Remark 3.11. Theorem 3.10 uses γ > 0 \gamma> 0 γ > 0 from (H2) (needed only to guarantee boundedness of { x k } k \{x_k\}_k { x k } k via Lemma 3.8 (a)); it requires no additional condition on μ \mu μ . When κ = 1 \kappa= 1 κ = 1 , (8) is precisely stationarity of f = g + h f = g + h f = g + h itself. For κ < 1 \kappa< 1 κ < 1 , however, a κ \kappa κ -critical point of f f f need not be a critical point of f f f , since the iteration decreases F κ = κ g + h F_\kappa= \kappa g + h F κ = κ g + h . This distinction is illustrated by the nonconvex regularizer in Example 3.17.
Corollary 3.12 (Convergence under the KL property). Under the hypotheses of Theorem 3.10 , if F κ F_\kappa F κ has the Kurdyka–Łojasiewicz (KL) property at every accumulation point, then ∑ k ∥ x k + 1 − x k ∥ < ∞ \sum_k \lVert x_{k+1} - x_k\rVert< \infty ∑ k ∥ x k + 1 − x k ∥ < ∞ and the whole sequence converges to a critical point of F κ F_\kappa F κ .
Proof. Lemma 3.7 , Lemma 3.9 , and the value-convergent subsequence constructed in Theorem 3.10 verify the sufficient-decrease, relative-error and continuity conditions of the standard KL convergence theorem [1 Theorem 2.9] . □
Lemma 3.13 (Radial subgradient inequality). Under (H2), for every u ∈ dom h u \in\operatorname{dom} h u ∈ dom h and v ∈ ∂ L h ( u ) v \in\partial^{L}h(u) v ∈ ∂ L h ( u ) , we have
⟨ v , u − x ˉ h ⟩ ≥ κ ( h ( u ) − h ( x ˉ h ) ) + κ γ 2 ∥ u − x ˉ h ∥ 2 ≥ κ γ 2 − κ ∥ u − x ˉ h ∥ 2 . (31) \langle v, u - \bar{x}_h\rangle\ge\kappa\bigl(h(u) - h(\bar{x}_h)\bigr) + \frac{\kappa\gamma}{2}\lVert u - \bar{x}_h\rVert^2 \ge\frac{\kappa\gamma}{2-\kappa}\lVert u - \bar{x}_h\rVert^2. \tag*{(31)} ⟨ v , u − x ˉ h ⟩ ≥ κ ( h ( u ) − h ( x ˉ h ) ) + 2 κγ ∥ u − x ˉ h ∥ 2 ≥ 2 − κ κγ ∥ u − x ˉ h ∥ 2 . (31)
Proof. If u = x ˉ h u = \bar{x}_h u = x ˉ h , the assertion is immediate. Otherwise, for a Fréchet subgradient, its defining lower estimate along ( 1 − t ) u + t x ˉ h (1-t)u + t\bar{x}_h ( 1 − t ) u + t x ˉ h and the quasar-convex upper estimate give the first inequality after division by t t t and passage to t ↓ 0 t \downarrow0 t ↓ 0 . For a limiting subgradient, pass to the limit along u j → u u_j \to u u j → u , h ( u j ) → h ( u ) h(u_j) \to h(u) h ( u j ) → h ( u ) and Fréchet subgradients v j → v v_j \to v v j → v . The second inequality follows from (5). □
The radial inequality also yields a comparison valid at every critical point of F κ F_\kappa F κ .
Proposition 3.14 (Comparison at critical points). Assume (H1)–(H2). Put
C μ = ( 2 − κ ) + 2 ( 2 − κ ) ( 1 + μ / γ ) κ γ + 2 μ . C_\mu= \frac{(2-\kappa) + \sqrt{2(2-\kappa)(1+\mu/\gamma)}}{\kappa\gamma+ 2\mu}. C μ = κγ + 2 μ ( 2 − κ ) + 2 ( 2 − κ ) ( 1 + μ / γ ) . For every critical point u u u of F κ F_\kappa F κ and every x ∗ ∈ argmin R n f x^* \in\operatorname*{argmin}_{\mathbb{R}^n} f x ∗ ∈ argmin R n f ,
∥ u − x ∗ ∥ ≤ C μ ∥ ∇ g ( u ) ∥ . \lVert u - x^*\rVert\le C_\mu\lVert\nabla g(u)\rVert. ∥ u − x ∗ ∥ ≤ C μ ∥ ∇ g ( u )∥ . Proof. Write z = u − x ∗ z = u - x^* z = u − x ∗ , t = x ∗ − x ˉ h t = x^* - \bar{x}_h t = x ∗ − x ˉ h and p = ∇ g ( u ) p = \nabla g(u) p = ∇ g ( u ) . Since − κ p ∈ ∂ L h ( u ) -\kappa p \in\partial^{L}h(u) − κ p ∈ ∂ L h ( u ) , Lemma 3.13 , quadratic growth at x ∗ x^* x ∗ , and strong convexity of g g g give
0 ≤ f ( u ) − f ( x ∗ ) ≤ − ⟨ p , t ⟩ − γ 2 ∥ z + t ∥ 2 − κ γ 2 ( 2 − κ ) ∥ t ∥ 2 − μ 2 ∥ t ∥ 2 0 \le f(u) - f(x^*) \le-\langle p,t\rangle- \frac{\gamma}{2}\lVert z+t\rVert^2 - \frac{\kappa\gamma}{2(2-\kappa)}\lVert t\rVert^2 - \frac{\mu}{2}\lVert t\rVert^2 0 ≤ f ( u ) − f ( x ∗ ) ≤ − ⟨ p , t ⟩ − 2 γ ∥ z + t ∥ 2 − 2 ( 2 − κ ) κγ ∥ t ∥ 2 − 2 μ ∥ t ∥ 2 = − γ + μ 2 ∥ z ∥ 2 − ⟨ γ z + p , t ⟩ − γ 2 − κ ∥ t ∥ 2 = -\frac{\gamma+\mu}{2}\lVert z\rVert^2 - \langle\gamma z+p,t\rangle- \frac{\gamma}{2-\kappa}\lVert t\rVert^2 = − 2 γ + μ ∥ z ∥ 2 − ⟨ γ z + p , t ⟩ − 2 − κ γ ∥ t ∥ 2 ≤ − γ + μ 2 ∥ z ∥ 2 + 2 − κ 4 γ ∥ γ z + p ∥ 2 . \le-\frac{\gamma+\mu}{2}\lVert z\rVert^2 + \frac{2-\kappa}{4\gamma}\lVert\gamma z+p\rVert^2. ≤ − 2 γ + μ ∥ z ∥ 2 + 4 γ 2 − κ ∥ γ z + p ∥ 2 . Completing the square in t t t gives the last step. Expansion and Cauchy–Schwarz yield ( κ γ + 2 μ ) ∥ z ∥ 2 ≤ 2 ( 2 − κ ) ∥ z ∥ ∥ p ∥ + ( ( 2 − κ ) / γ ) ∥ p ∥ 2 (\kappa\gamma+ 2\mu)\lVert z\rVert^2 \le2(2-\kappa)\lVert z\rVert\lVert p\rVert+ ((2-\kappa)/\gamma)\lVert p\rVert^2 ( κγ + 2 μ ) ∥ z ∥ 2 ≤ 2 ( 2 − κ ) ∥ z ∥ ∥ p ∥ + (( 2 − κ ) / γ ) ∥ p ∥ 2 . The nonnegative root of the associated quadratic equation is C μ ∥ p ∥ C_\mu\lVert p\rVert C μ ∥ p ∥ . □
Theorem 3.15 (Geometric and asymptotic distances to a global minimizer). Assume (H1)–(H2), let 0 < β k ≡ β < 1 / ( κ L ) 0 < \beta_k \equiv\beta< 1/(\kappa L) 0 < β k ≡ β < 1/ ( κ L ) , and fix x ∗ ∈ a r g m i n R n f x^* \in\mathop{\rm argmin}_{\mathbb{R}^n} f x ∗ ∈ argmin R n f . Put
G ∗ = ∥ ∇ g ( x ∗ ) ∥ , M ∞ = lim sup k ∥ ∇ g ( x k ) ∥ , G^* = \|\nabla g(x^*)\|, \qquad M_\infty= \limsup_k \|\nabla g(x_k)\|, G ∗ = ∥∇ g ( x ∗ ) ∥ , M ∞ = k lim sup ∥∇ g ( x k ) ∥ , q = 1 − κ β μ 1 + β κ γ / ( 2 − κ ) ∈ ] 0 , 1 [ , R f = ( 2 − κ ) G ∗ κ γ ( 1 + κ γ + ( 2 − κ ) L γ + ( 2 − κ ) μ ) . q = \frac{1-\kappa\beta\mu}{1+\beta\kappa\gamma/(2-\kappa)} \in]0,1[, \qquad R_f = \frac{(2-\kappa)G^*}{\kappa\gamma}\left(1+\frac{\kappa\gamma+(2-\kappa)L}{\gamma+(2-\kappa)\mu}\right). q = 1 + β κγ / ( 2 − κ ) 1 − κ β μ ∈ ] 0 , 1 [ , R f = κγ ( 2 − κ ) G ∗ ( 1 + γ + ( 2 − κ ) μ κγ + ( 2 − κ ) L ) . Let C μ C_\mu C μ be the constant in Proposition 3.14. Then:
(a) For every k ≥ 1 k \ge1 k ≥ 1 ,
∥ x k − x ∗ ∥ ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ + 2 ( 2 − κ ) G ∗ κ γ ) + ( 1 − q k − 1 ) R f . (32) \|x_k-x^*\| \le q^{k-1}\left(\|x_1-x^*\|+\frac{2(2-\kappa)G^*}{\kappa\gamma}\right)+(1-q^{k-1})R_f. \tag*{(32)} ∥ x k − x ∗ ∥ ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ + κγ 2 ( 2 − κ ) G ∗ ) + ( 1 − q k − 1 ) R f . (32) and consequently
dist ( x k , B ‾ ( x ∗ , R f ) ) ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ + 2 ( 2 − κ ) G ∗ κ γ − R f ) + . (33) \operatorname{dist}(x_k,\overline{B}(x^*,R_f)) \le q^{k-1}\left(\|x_1-x^*\|+\frac{2(2-\kappa)G^*}{\kappa\gamma}-R_f\right)_+. \tag*{(33)} dist ( x k , B ( x ∗ , R f )) ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ + κγ 2 ( 2 − κ ) G ∗ − R f ) + . (33) The radius R f R_f R f is independent of β \beta β .
(b) The asymptotic distance satisfies
lim sup k ∥ x k − x ∗ ∥ ≤ min { R f , C μ M ∞ } . (34) \limsup_k \|x_k-x^*\| \le\min\{R_f,C_\mu M_\infty\}. \tag*{(34)} k lim sup ∥ x k − x ∗ ∥ ≤ min { R f , C μ M ∞ } . (34) If G ∗ = 0 G^*=0 G ∗ = 0 , then R f = 0 R_f=0 R f = 0 and ∥ x k − x ∗ ∥ ≤ q k − 1 ∥ x 1 − x ∗ ∥ \|x_k-x^*\|\le q^{k-1}\|x_1-x^*\| ∥ x k − x ∗ ∥ ≤ q k − 1 ∥ x 1 − x ∗ ∥ ; in particular, the sequence converges globally and linearly to x ∗ x^* x ∗ .
Proof. (a) If u ∈ Prox β h ( y ) u\in\operatorname{Prox}_{\beta h}(y) u ∈ Prox β h ( y ) , proximal optimality and Lemma 3.13 give
⟨ y − x ‾ h , u − x ‾ h ⟩ ≥ ( 1 + β κ γ 2 − κ ) ∥ u − x ‾ h ∥ 2 . \langle y-\overline{x}_h,u-\overline{x}_h\rangle\ge\left(1+\frac{\beta\kappa\gamma}{2-\kappa}\right)\|u-\overline{x}_h\|^2. ⟨ y − x h , u − x h ⟩ ≥ ( 1 + 2 − κ β κγ ) ∥ u − x h ∥ 2 .
By Cauchy–Schwarz,
( 1 + β κ γ 2 − κ ) ∥ u − x ‾ h ∥ ≤ ∥ y − x ‾ h ∥ . \left(1+\frac{\beta\kappa\gamma}{2-\kappa}\right)\|u-\overline{x}_h\|\le\|y-\overline{x}_h\|. ( 1 + 2 − κ β κγ ) ∥ u − x h ∥ ≤ ∥ y − x h ∥.
The gradient map I − κ β ∇ g I-\kappa\beta\nabla g I − κ β ∇ g is ( 1 − κ β μ ) (1-\kappa\beta\mu) ( 1 − κ β μ ) -Lipschitz. Indeed, if μ < L \mu<L μ < L , convex cocoercivity applied to g − μ ∥ ⋅ ∥ 2 / 2 g-\mu\|\cdot\|^2/2 g − μ ∥ ⋅ ∥ 2 /2 , whose quadratic upper model has modulus L − μ L-\mu L − μ , gives, with s = ∇ g ( x ) − ∇ g ( z ) s=\nabla g(x)-\nabla g(z) s = ∇ g ( x ) − ∇ g ( z ) ,
( L + μ ) ⟨ x − z , s ⟩ ≥ ∥ s ∥ 2 + μ L ∥ x − z ∥ 2 . (L+\mu)\langle x-z,s\rangle\ge\|s\|^2+\mu L\|x-z\|^2. ( L + μ ) ⟨ x − z , s ⟩ ≥ ∥ s ∥ 2 + μL ∥ x − z ∥ 2 .
Together with ∥ s ∥ ≥ μ ∥ x − z ∥ \|s\|\ge\mu\|x-z\| ∥ s ∥ ≥ μ ∥ x − z ∥ and κ 2 β 2 − 2 κ β / ( L + μ ) ≤ 0 \kappa^2\beta^2-2\kappa\beta/(L+\mu)\le0 κ 2 β 2 − 2 κ β / ( L + μ ) ≤ 0 , this yields
∥ x − z − κ β s ∥ 2 ≤ ( 1 − 2 κ β μ L L + μ ) ∥ x − z ∥ 2 + ( κ 2 β 2 − 2 κ β L + μ ) ∥ s ∥ 2 ≤ ( 1 − κ β μ ) 2 ∥ x − z ∥ 2 . (35) \begin{aligned}
\|x-z-\kappa\beta s\|^2\le\left(1-\frac{2\kappa\beta\mu L}{L+\mu}\right)\|x-z\|^2+\left(\kappa^2\beta^2-\frac{2\kappa\beta}{L+\mu}\right)\|s\|^2 \\
&\le(1-\kappa\beta\mu)^2\|x-z\|^2. \tag*{(35)}
\end{aligned} ∥ x − z − κ β s ∥ 2 ≤ ( 1 − L + μ 2 κ β μL ) ∥ x − z ∥ 2 + ( κ 2 β 2 − L + μ 2 κ β ) ∥ s ∥ 2 ≤ ( 1 − κ β μ ) 2 ∥ x − z ∥ 2 . (35)
If μ = L \mu=L μ = L , the shifted function is affine and the same conclusion follows directly. Set d k = ∥ x k − x ˉ h ∥ d_k=\lVert x_k-\bar{x}_h\rVert d k = ∥ x k − x ˉ h ∥ . The two preceding estimates imply
d k + 1 ≤ q d k + κ β ∥ ∇ g ( x ˉ h ) ∥ 1 + β κ γ / ( 2 − κ ) . d_{k+1}\le qd_k+\frac{\kappa\beta\lVert\nabla g(\bar{x}_h)\rVert}{1+\beta\kappa\gamma/(2-\kappa)}. d k + 1 ≤ q d k + 1 + β κγ / ( 2 − κ ) κ β ∥ ∇ g ( x ˉ h )∥ .
Iterating this recurrence and using the definition of q q q gives
d k ≤ q k − 1 d 1 + ( 1 − q k − 1 ) ∥ ∇ g ( x ˉ h ) ∥ μ + γ / ( 2 − κ ) . d_k\le q^{k-1}d_1+(1-q^{k-1})\frac{\lVert\nabla g(\bar{x}_h)\rVert}{\mu+\gamma/(2-\kappa)}. d k ≤ q k − 1 d 1 + ( 1 − q k − 1 ) μ + γ / ( 2 − κ ) ∥ ∇ g ( x ˉ h )∥ .
Fermat’s rule at x ∗ x^* x ∗ gives − ∇ g ( x ∗ ) ∈ ∂ L h ( x ∗ ) -\nabla g(x^*)\in\partial Lh(x^*) − ∇ g ( x ∗ ) ∈ ∂ L h ( x ∗ ) . The radial inequality therefore implies
κ γ 2 − κ ∥ x ∗ − x ˉ h ∥ 2 ≤ ⟨ − ∇ g ( x ∗ ) , x ∗ − x ˉ h ⟩ ≤ G ∗ ∥ x ∗ − x ˉ h ∥ , \frac{\kappa\gamma}{2-\kappa}\lVert x^*-\bar{x}_h\rVert^2\le\langle-\nabla g(x^*),x^*-\bar{x}_h\rangle\le G^*\lVert x^*-\bar{x}_h\rVert, 2 − κ κγ ∥ x ∗ − x ˉ h ∥ 2 ≤ ⟨ − ∇ g ( x ∗ ) , x ∗ − x ˉ h ⟩ ≤ G ∗ ∥ x ∗ − x ˉ h ∥ ,
so ∥ x ∗ − x ˉ h ∥ ≤ ( 2 − κ ) G ∗ / ( κ γ ) \lVert x^*-\bar{x}_h\rVert\le(2-\kappa)G^*/(\kappa\gamma) ∥ x ∗ − x ˉ h ∥ ≤ ( 2 − κ ) G ∗ / ( κγ ) . Lipschitz continuity and the definition of R f R_f R f also give
∥ ∇ g ( x ˉ h ) ∥ μ + γ / ( 2 − κ ) ≤ R f − ( 2 − κ ) G ∗ κ γ . \frac{\lVert\nabla g(\bar{x}_h)\rVert}{\mu+\gamma/(2-\kappa)}\le R_f-\frac{(2-\kappa)G^*}{\kappa\gamma}. μ + γ / ( 2 − κ ) ∥ ∇ g ( x ˉ h )∥ ≤ R f − κγ ( 2 − κ ) G ∗ .
Consequently,
∥ x k − x ∗ ∥ ≤ d k + ∥ x ∗ − x ˉ h ∥ ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ + ( 2 − κ ) G ∗ κ γ ) + ( 1 − q k − 1 ) ( R f − ( 2 − κ ) G ∗ κ γ ) + ( 2 − κ ) G ∗ κ γ = q k − 1 ( ∥ x 1 − x ∗ ∥ + 2 ( 2 − κ ) G ∗ κ γ ) + ( 1 − q k − 1 ) R f . \begin{aligned}
\lVert x_k-x^*\rVert&\le d_k+\lVert x^*-\bar{x}_h\rVert\\
&\le q^{k-1}\left(\lVert x_1-x^*\rVert+\frac{(2-\kappa)G^*}{\kappa\gamma}\right)\\
&\quad+(1-q^{k-1})\left(R_f-\frac{(2-\kappa)G^*}{\kappa\gamma}\right)+\frac{(2-\kappa)G^*}{\kappa\gamma}\\
&=q^{k-1}\left(\lVert x_1-x^*\rVert+\frac{2(2-\kappa)G^*}{\kappa\gamma}\right)+(1-q^{k-1})R_f.
\end{aligned} ∥ x k − x ∗ ∥ ≤ d k + ∥ x ∗ − x ˉ h ∥ ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ + κγ ( 2 − κ ) G ∗ ) + ( 1 − q k − 1 ) ( R f − κγ ( 2 − κ ) G ∗ ) + κγ ( 2 − κ ) G ∗ = q k − 1 ( ∥ x 1 − x ∗ ∥ + κγ 2 ( 2 − κ ) G ∗ ) + ( 1 − q k − 1 ) R f .
This proves (32) ; subtracting R f R_f R f and taking positive parts proves (33) . In particular, lim sup k ∥ x k − x ∗ ∥ ≤ R f \limsup_k\lVert x_k-x^*\rVert\le R_f lim sup k ∥ x k − x ∗ ∥ ≤ R f .
(b) Apply Proposition 3.5 at x = x ∗ x=x^* x = x ∗ . Discard the nonnegative objective gap and the nonpositive step term. By Lemma 3.8 , the iterates are bounded and x k + 1 − x k → 0 x_{k+1}-x_k\to0 x k + 1 − x k → 0 ; hence
lim sup k ∥ x k + 1 − y k ∥ 2 = κ 2 β 2 M ∞ 2 . \limsup_k\lVert x_{k+1}-y_k\rVert^2=\kappa^2\beta^2M_\infty^2. k lim sup ∥ x k + 1 − y k ∥ 2 = κ 2 β 2 M ∞ 2 .
Taking upper limits in the composite inequality gives, for every δ > 0 \delta>0 δ > 0 ,
lim sup k ∥ x k − x ∗ ∥ 2 ≤ K δ 2 M ∞ 2 , K δ 2 = ( 2 − κ ) ( 2 + δ − κ ) ( 2 + δ ) κ γ δ [ κ γ + μ ( 2 + δ ) ] . \limsup_k\lVert x_k-x^*\rVert^2\le K_\delta^2M_\infty^2,\qquad K_\delta^2=\frac{(2-\kappa)(2+\delta-\kappa)(2+\delta)}{\kappa\gamma\delta\,[\kappa\gamma+\mu(2+\delta)]}. k lim sup ∥ x k − x ∗ ∥ 2 ≤ K δ 2 M ∞ 2 , K δ 2 = κγ δ [ κγ + μ ( 2 + δ )] ( 2 − κ ) ( 2 + δ − κ ) ( 2 + δ ) .
The definition of C μ C_\mu C μ implies ( κ γ + 2 μ ) C μ 2 = 2 ( 2 − κ ) C μ + ( 2 − κ ) / γ (\kappa\gamma+2\mu)C_\mu^2=2(2-\kappa)C_\mu+(2-\kappa)/\gamma ( κγ + 2 μ ) C μ 2 = 2 ( 2 − κ ) C μ + ( 2 − κ ) / γ . A direct expansion then gives
K δ 2 − C μ 2 = ( ( κ γ C μ − ( 2 − κ ) ) δ − 2 ( 2 − κ ) ) 2 2 κ γ δ [ κ γ + μ ( 2 + δ ) ] . (36) K_\delta^2-C_\mu^2=\frac{\left((\kappa\gamma C_\mu-(2-\kappa))\delta-2(2-\kappa)\right)^2}{2\kappa\gamma\delta\,[\kappa\gamma+\mu(2+\delta)]}. \tag*{(36)} K δ 2 − C μ 2 = 2 κγ δ [ κγ + μ ( 2 + δ )] ( ( κγ C μ − ( 2 − κ )) δ − 2 ( 2 − κ ) ) 2 . (36)
If μ < κ γ / ( 2 − κ ) \mu< \kappa\gamma/(2-\kappa) μ < κγ / ( 2 − κ ) , then κ γ C μ > 2 − κ \kappa\gamma C_\mu> 2-\kappa κγ C μ > 2 − κ and the choice
δ ∗ = 2 ( 2 − κ ) κ γ C μ − ( 2 − κ ) \delta_* = \frac{2(2-\kappa)}{\kappa\gamma C_\mu-(2-\kappa)} δ ∗ = κγ C μ − ( 2 − κ ) 2 ( 2 − κ )
gives K δ ∗ = C μ K_{\delta_*}=C_\mu K δ ∗ = C μ . For μ = 0 \mu=0 μ = 0 , this reduces to δ ∗ = 2 ( 2 − κ ) \delta_*=\sqrt{2(2-\kappa)} δ ∗ = 2 ( 2 − κ ) . At μ = κ γ / ( 2 − κ ) \mu=\kappa\gamma/(2-\kappa) μ = κγ / ( 2 − κ ) , letting δ → + ∞ \delta\to+\infty δ → + ∞ in (35) gives the same bound.
If μ > κ γ / ( 2 − κ ) \mu>\kappa\gamma/(2-\kappa) μ > κγ / ( 2 − κ ) , take a subsequence attaining lim sup k ∥ x k − x ∗ ∥ \limsup_k\|x_k-x^*\| lim sup k ∥ x k − x ∗ ∥ and, by boundedness, a convergent subsequence with limit u u u . Theorem 3.10 makes u u u a critical point of F κ F_\kappa F κ . Proposition 3.14 and continuity of ∇ g \nabla g ∇ g yield
lim sup k ∥ x k − x ∗ ∥ = ∥ u − x ∗ ∥ ≤ C μ ∥ ∇ g ( u ) ∥ ≤ C μ M ∞ . \limsup_k\|x_k-x^*\|=\|u-x^*\|\le C_\mu\|\nabla g(u)\|\le C_\mu M_\infty. k lim sup ∥ x k − x ∗ ∥ = ∥ u − x ∗ ∥ ≤ C μ ∥∇ g ( u ) ∥ ≤ C μ M ∞ .
This establishes the comparison with C μ M ∞ C_\mu M_\infty C μ M ∞ for all μ ≥ 0 \mu\ge0 μ ≥ 0 . Taking the minimum with the bound R f R_f R f from part (a) proves (34). The assertion for G ∗ = 0 G^*=0 G ∗ = 0 follows from part (a).
The geometric rate in part (a) concerns the ball of radius R f R_f R f ; part (b) gives the best of the available asymptotic distance bounds.
Example 3.16 (Comparison of the two bounds). Let h ( x ) = x 2 / 6 h(x)=x^2/6 h ( x ) = x 2 /6 and g a ( x ) = a ( x − 1 ) 2 / 2 g_a(x)=a(x-1)^2/2 g a ( x ) = a ( x − 1 ) 2 /2 , with κ = 1 / 2 \kappa=1/2 κ = 1/2 , γ = β = 1 \gamma=\beta=1 γ = β = 1 , and a ∈ { 1 / 10 , 1 } a\in\{1/10,1\} a ∈ { 1/10 , 1 } . These functions satisfy (H), with μ = L = a \mu=L=a μ = L = a . The iteration is
x k + 1 = 3 4 ( 1 − a 2 ) x k + 3 a 8 , x_{k+1}=\frac{3}{4}\left(1-\frac{a}{2}\right)x_k+\frac{3a}{8}, x k + 1 = 4 3 ( 1 − 2 a ) x k + 8 3 a , so it converges to x ^ = 3 a / ( 2 + 3 a ) \widehat{x}=3a/(2+3a) x = 3 a / ( 2 + 3 a ) , whereas the global minimizer of f f f is x ∗ = 3 a / ( 1 + 3 a ) x^*=3a/(1+3a) x ∗ = 3 a / ( 1 + 3 a ) . Hence
G ∗ = a 1 + 3 a , M ∞ = 2 a 2 + 3 a . G^*=\frac{a}{1+3a},\qquad M_\infty=\frac{2a}{2+3a}. G ∗ = 1 + 3 a a , M ∞ = 2 + 3 a 2 a . Substitution gives the following values:
Table 1.
The ordering reverses between the two choices, so neither bound dominates the other in general.
Example 3.17 (Weighting bias with a nonconvex regularizer). Let g ( x ) = ( x − 3 ) 2 g(x)=(x-3)^2 g ( x ) = ( x − 3 ) 2 , h ( x ) = x 2 − 3 4 x 4 + x 6 h(x)=x^2-\frac{3}{4}x^4+x^6 h ( x ) = x 2 − 4 3 x 4 + x 6 and κ = γ = β = 1 2 \kappa=\gamma=\beta=\frac{1}{2} κ = γ = β = 2 1 . Here, L = μ = 2 L=\mu=2 L = μ = 2 , and 0 < β < 1 / ( κ L ) = 1 0<\beta<1/(\kappa L)=1 0 < β < 1/ ( κ L ) = 1 . Since h ( x ) = x 2 ( ( x 2 − 3 / 4 ) 2 + 7 / 16 ) h(x)=x^2((x^2-3/4)^2+7/16) h ( x ) = x 2 (( x 2 − 3/4 ) 2 + 7/16 ) , its unique minimizer is zero. Moreover, h ′ ′ ( x ) = 30 ( x 2 − 3 / 10 ) 2 − 7 / 10 h''(x)=30(x^2-3/10)^2-7/10 h ′′ ( x ) = 30 ( x 2 − 3/10 ) 2 − 7/10 , so h h h is nonconvex. Nevertheless, it is globally ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex by (6), since
x h ′ ( x ) − κ h ( x ) − κ γ 2 x 2 = x 2 ( 11 2 ( x 2 − 21 / 44 ) 2 + 43 352 ) ≥ 0. xh'(x)-\kappa h(x)-\frac{\kappa\gamma}{2}x^2=x^2\left(\frac{11}{2}(x^2-21/44)^2+\frac{43}{352}\right)\ge0. x h ′ ( x ) − κh ( x ) − 2 κγ x 2 = x 2 ( 2 11 ( x 2 − 21/44 ) 2 + 352 43 ) ≥ 0.
The proximal objective has second derivative at least 13 / 10 13/10 13/10 , so each proximal minimizer is unique. The iteration satisfies
y k = x k + 3 2 , y k = x k + 1 + 1 2 h ′ ( x k + 1 ) . y_k = \frac{x_k+3}{2}, \qquad y_k = x_{k+1} + \frac{1}{2}h'(x_{k+1}). y k = 2 x k + 3 , y k = x k + 1 + 2 1 h ′ ( x k + 1 ) .
The derivative of u ↦ u + 1 2 h ′ ( u ) u \mapsto u + \frac{1}{2}h'(u) u ↦ u + 2 1 h ′ ( u ) is at least 13 / 20 13/20 13/20 ; thus the update is a contraction with factor 10 / 13 10/13 10/13 . Since h ′ ( 1 ) = 2 h'(1)=2 h ′ ( 1 ) = 2 , its fixed point is x ^ = 1 \hat{x}=1 x ^ = 1 , and every initial point gives
∣ x k − 1 ∣ ≤ ( 10 / 13 ) k − 1 ∣ x 1 − 1 ∣ . |x_k-1| \leq(10/13)^{k-1}|x_1-1|. ∣ x k − 1∣ ≤ ( 10/13 ) k − 1 ∣ x 1 − 1∣.
Finally, F κ ′ ′ ≥ 3 / 10 F_\kappa'' \geq3/10 F κ ′′ ≥ 3/10 , so x ^ \hat{x} x ^ is its unique global minimizer, whereas
F κ ′ ( 1 ) = 1 2 ( − 4 ) + 2 = 0 , f ′ ( 1 ) = − 4 + 2 = − 2 ≠ 0. F_\kappa'(1) = \frac{1}{2}(-4)+2=0, \qquad f'(1)=-4+2=-2\ne0. F κ ′ ( 1 ) = 2 1 ( − 4 ) + 2 = 0 , f ′ ( 1 ) = − 4 + 2 = − 2 = 0.
This example separates κ \kappa κ -criticality from ordinary criticality with a nonconvex regularizer satisfying the global hypotheses.
The general results establish critical-point convergence for F κ F_\kappa F κ and quantitative distance estimates relative to global minimizers of f f f ; they do not assert global optimality of the limit under the general hypotheses. The common-minimizer case of Theorem 3.15 ensures global linear convergence to the common global minimizer.
Applications to ℓ p \ell_p ℓ p -Regularized Least Squares (0<p p p <1)
Model, Quasar-Convexity and Confinement
We apply the framework of § 3 to the classical nonconvex sparse recovery problem
min x ∈ R n F ( x ) : = ∥ A x − b ∥ 2 2 + ρ ∥ x ∥ p p (37) \min_{x\in\mathbb{R}^n} F(x):=\lVert Ax-b\rVert_2^2+\rho\lVert x\rVert_p^p \tag*{(37)} x ∈ R n min F ( x ) := ∥ A x − b ∥ 2 2 + ρ ∥ x ∥ p p (37)
where A ∈ R m × n A\in\mathbb{R}^{m\times n} A ∈ R m × n , b ∈ R m b\in\mathbb{R}^m b ∈ R m , 0 < p < 1 0<p<1 0 < p < 1 and ρ > 0 \rho>0 ρ > 0 . This model arises in sparse signal/image recovery, LASSO-type estimation [15 ] , and compressed sensing; the ℓ p \ell_p ℓ p power penalty has been studied as a sparsity-promoting alternative to ℓ 1 \ell_1 ℓ 1 (see [19, 25, 26]).
Set g ( x ) = ∥ A x − b ∥ 2 2 g(x)=\lVert Ax-b\rVert_2^2 g ( x ) = ∥ A x − b ∥ 2 2 and h ( x ) = ρ ∥ x ∥ p p h(x)=\rho\lVert x\rVert_p^p h ( x ) = ρ ∥ x ∥ p p . The quasar-convexity of this penalty on bounded sets was established in [6 Example 8] ; we recall its modulus below before applying Algorithm 1.
Algorithm 1 decreases the weighted objective
F κ = κ g + h = κ ( ∥ A x − b ∥ 2 2 + ρ κ ∥ x ∥ p p ) . F_\kappa=\kappa g+h=\kappa\left(\lVert Ax-b\rVert_2^2+\frac{\rho}{\kappa}\lVert x\rVert_p^p\right). F κ = κ g + h = κ ( ∥ A x − b ∥ 2 2 + κ ρ ∥ x ∥ p p ) .
Thus its effective regularization parameter is ρ / κ \rho/\kappa ρ / κ , while F F F in (36) is the comparison objective. If a prescribed regularization parameter λ \lambda λ is to be used in the objective optimized by the iteration, taking h = κ λ ∥ ⋅ ∥ p p h=\kappa\lambda\lVert\cdot\rVert_p^p h = κλ ∥ ⋅ ∥ p p gives the usual proximal-gradient method for that objective with step κ β \kappa\beta κ β .
Lemma 4.1. If h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex on a star-shaped set K K K with respect to x ˉ h ∈ argmin R n h \bar{x}_h \in\operatorname{argmin}_{\mathbb{R}^n} h x ˉ h ∈ argmin R n h , then for every ρ > 0 \rho> 0 ρ > 0 , ρ h \rho h ρ h is ( κ , ρ γ ) (\kappa,\rho\gamma) ( κ , ρ γ ) -strongly quasar-convex on K K K with respect to the same point x ˉ h \bar{x}_h x ˉ h .
Proof. Multiplying the inequality in Definition 2.1 by ρ > 0 \rho> 0 ρ > 0 preserves its direction. The terms ρ h ( x ˉ h ) \rho h(\bar{x}_h) ρ h ( x ˉ h ) , ρ h ( y ) \rho h(y) ρ h ( y ) and ρ h ( λ x ˉ h + ( 1 − λ ) y ) \rho h(\lambda\bar{x}_h + (1-\lambda)y) ρ h ( λ x ˉ h + ( 1 − λ ) y ) replace their unscaled counterparts, while the last term becomes − λ ( 1 − λ 2 − κ ) κ ( ρ γ ) 2 ∥ y − x ˉ h ∥ 2 -\lambda\left(1-\frac{\lambda}{2-\kappa}\right)\frac{\kappa(\rho\gamma)}{2}\lVert y-\bar{x}_h\rVert^2 − λ ( 1 − 2 − κ λ ) 2 κ ( ρ γ ) ∥ y − x ˉ h ∥ 2 . Since ρ > 0 \rho> 0 ρ > 0 , argmin R n ρ h = argmin R n h \operatorname{argmin}_{\mathbb{R}^n}\rho h=\operatorname{argmin}_{\mathbb{R}^n}h argmin R n ρ h = argmin R n h .
Proposition 4.2. (see [6 Example 8] ) Let 0 < p < 1 0 < p < 1 0 < p < 1 and h ( x ) : = ∥ x ∥ p p = ∑ i = 1 n ∣ x i ∣ p h(x):=\lVert x\rVert_p^p=\sum_{i=1}^{n}|x_i|^p h ( x ) := ∥ x ∥ p p = ∑ i = 1 n ∣ x i ∣ p . Then x ˉ h = 0 ∈ argmin R n h \bar{x}_h=0\in\operatorname{argmin}_{\mathbb{R}^n}h x ˉ h = 0 ∈ argmin R n h , and for every κ ∈ ] 0 , p [ \kappa\in]0,p[ κ ∈ ] 0 , p [ and every R > 0 R>0 R > 0 , h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex with respect to x ˉ h = 0 \bar{x}_h=0 x ˉ h = 0 on K = B ‾ ( 0 , R ) K=\overline{B}(0,R) K = B ( 0 , R ) , with the sharp modulus
γ ( κ , p , R ) = 2 ( p − κ ) κ R p − 2 . \gamma(\kappa,p,R)=\frac{2(p-\kappa)}{\kappa}R^{p-2}. γ ( κ , p , R ) = κ 2 ( p − κ ) R p − 2 .
The stated modulus follows from [6 Example 8] by rescaling the unit ball to radius R R R . Sharpness follows by evaluating the defining inequality at x = ( R , 0 , … , 0 ) x=(R,0,\ldots,0) x = ( R , 0 , … , 0 ) , dividing by λ > 0 \lambda>0 λ > 0 , and letting $\lambda\downarrow 0.
Proposition 4.4 (Explicit confinement). Fix 0 < κ < p < 1 0<\kappa<p<1 0 < κ < p < 1 and a constant step 0 < β < 1 / ( κ L ) 0<\beta<1/(\kappa L) 0 < β < 1/ ( κ L ) , where L = 2 ∥ A ∥ 2 L=2\lVert A\rVert^2 L = 2 ∥ A ∥ 2 and 1 / 0 : = + ∞ 1/0:=+\infty 1/0 := + ∞ . Let { x k } k \{x_k\}_k { x k } k be generated by Algorithm 1 from x 1 ∈ R n x_1\in\mathbb{R}^n x 1 ∈ R n . Set E = F κ ( x 1 ) E=F_\kappa(x_1) E = F κ ( x 1 ) and choose
R > max { ( E / ρ ) 1 / p , ( ∥ b ∥ 2 2 / ρ ) 1 / p } . (38) R>\max\left\{(E/\rho)^{1/p},(\lVert b\rVert_2^2/\rho)^{1/p}\right\}. \tag*{(38)} R > max { ( E / ρ ) 1/ p , (∥ b ∥ 2 2 / ρ ) 1/ p } . (38) All iterates and all global minimizers of either F F F or F κ F_\kappa F κ belong to B ( 0 , R ) B(0,R) B ( 0 , R ) .
Proof. The proximal objective is continuous and coercive, so each proximal subproblem has a global minimizer. Proximal optimality with comparison point x k x_k x k and the descent lemma give
F κ ( x k + 1 ) + 1 − κ β L 2 β ∥ x k + 1 − x k ∥ 2 ≤ F κ ( x k ) . F_\kappa(x_{k+1})+\frac{1-\kappa\beta L}{2\beta}\lVert x_{k+1}-x_k\rVert^2\le F_\kappa(x_k). F κ ( x k + 1 ) + 2 β 1 − κ β L ∥ x k + 1 − x k ∥ 2 ≤ F κ ( x k ) .
Since g , h ≥ 0 g,h\ge0 g , h ≥ 0 and ∥ x ∥ 2 p ≤ ∥ x ∥ p p \lVert x\rVert_2^p\le\lVert x\rVert_p^p ∥ x ∥ 2 p ≤ ∥ x ∥ p p , it follows that ρ ∥ x k ∥ 2 p ≤ E \rho\lVert x_k\rVert_2^p\le E ρ ∥ x k ∥ 2 p ≤ E . Both F F F and F κ F_\kappa F κ are continuous and coercive and therefore attain their minima. If x ∗ ∈ argmin F x^*\in\operatorname{argmin}F x ∗ ∈ argmin F , then ρ ∥ x ∗ ∥ 2 p ≤ F ( x ∗ ) ≤ F ( 0 ) = ∥ b ∥ 2 2 \rho\lVert x^*\rVert_2^p\le F(x^*)\le F(0)=\lVert b\rVert_2^2 ρ ∥ x ∗ ∥ 2 p ≤ F ( x ∗ ) ≤ F ( 0 ) = ∥ b ∥ 2 2 . If z ∗ ∈ argmin F κ z^*\in\operatorname{argmin}F_\kappa z ∗ ∈ argmin F κ , then ρ ∥ z ∗ ∥ 2 p ≤ F κ ( z ∗ ) ≤ F κ ( 0 ) = κ ∥ b ∥ 2 2 ≤ ∥ b ∥ 2 2 \rho\lVert z^*\rVert_2^p\le F_\kappa(z^*)\le F_\kappa(0)=\kappa\lVert b\rVert_2^2\le\lVert b\rVert_2^2 ρ ∥ z ∗ ∥ 2 p ≤ F κ ( z ∗ ) ≤ F κ ( 0 ) = κ ∥ b ∥ 2 2 ≤ ∥ b ∥ 2 2 . The strict choice of R R R proves all assertions.
The smooth part g g g . Take g ( x ) = ∥ A x − b ∥ 2 2 g(x)=\lVert Ax-b\rVert_{2}^{2} g ( x ) = ∥ A x − b ∥ 2 2 . Then g g g is convex and differentiable with ∇ g ( x ) = 2 A T ( A x − b ) \nabla g(x)=2A^{\mathsf{T}}(Ax-b) ∇ g ( x ) = 2 A T ( A x − b ) and ∇ 2 g ( x ) = 2 A T A ⪰ 0 \nabla^{2}g(x)=2A^{\mathsf{T}}A\succeq0 ∇ 2 g ( x ) = 2 A T A ⪰ 0 , hence g g g has L L L -Lipschitz gradient with
L = 2 ∥ A ∥ 2 2 . (39) L=2\lVert A\rVert_{2}^{2}. \tag*{(39)} L = 2 ∥ A ∥ 2 2 . (39)
Its strong-convexity modulus is μ = 2 λ min ( A T A ) ≥ 0 \mu=2\lambda_{\min}(A^{\mathsf{T}}A)\ge0 μ = 2 λ m i n ( A T A ) ≥ 0 , which is positive exactly when A A A has full column rank.
The regularizer h = ρ ∥ ⋅ ∥ p p h=\rho\lVert\cdot\rVert_{p}^{p} h = ρ ∥ ⋅ ∥ p p . By Proposition 4.2 (a formulation on a Euclidean ball of [6 Example 8, Proposition 6(a)] ), x ˉ h = 0 \bar{x}_{h}=0 x ˉ h = 0 , and for every κ ∈ ] 0 , p [ \kappa\in]0,p[ κ ∈ ] 0 , p [ and every R > 0 R>0 R > 0 , ∥ x ∥ p p \lVert x\rVert_{p}^{p} ∥ x ∥ p p is ( κ , γ 0 ) (\kappa,\gamma_{0}) ( κ , γ 0 ) -strongly quasar-convex on K = B ‾ ( 0 , R ) K=\overline{B}(0,R) K = B ( 0 , R ) with
γ 0 ( κ , p , R ) = 2 ( p − κ ) κ R p − 2 . \gamma_{0}(\kappa,p,R)=\frac{2(p-\kappa)}{\kappa}R^{p-2}. γ 0 ( κ , p , R ) = κ 2 ( p − κ ) R p − 2 .
By Lemma 4.1 (scaling), h = ρ ∥ ⋅ ∥ p p h=\rho\lVert\cdot\rVert_{p}^{p} h = ρ ∥ ⋅ ∥ p p is then ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex on K K K with respect to the same x ˉ h = 0 \bar{x}_{h}=0 x ˉ h = 0 , with modulus
γ ( κ , p , R , ρ ) = ρ γ 0 ( κ , p , R ) = 2 ρ ( p − κ ) κ R p − 2 . (40) \gamma(\kappa,p,R,\rho)=\rho\gamma_{0}(\kappa,p,R)=\frac{2\rho(p-\kappa)}{\kappa}R^{p-2}. \tag*{(40)} γ ( κ , p , R , ρ ) = ρ γ 0 ( κ , p , R ) = κ 2 ρ ( p − κ ) R p − 2 . (40)
As noted in [6 Example 8] , for n ≥ 2 n\ge2 n ≥ 2 the penalty h h h is not quasiconvex. The quasar-convex framework of § 3 applies to this penalty on the confinement ball; no quasar-convexity assumption is made on the full objective.
For the remaining convergence results of this section, we use the following application hypotheses, denoted collectively by (A):
(A1) A ∈ R m × n A\in\mathbb{R}^{m\times n} A ∈ R m × n , b ∈ R m b\in\mathbb{R}^{m} b ∈ R m , 0 < p < 1 0<p<1 0 < p < 1 , and ρ > 0 \rho>0 ρ > 0 , with g ( x ) = ∥ A x − b ∥ 2 2 g(x)=\lVert Ax-b\rVert_{2}^{2} g ( x ) = ∥ A x − b ∥ 2 2 , h ( x ) = ρ ∥ x ∥ p p h(x)=\rho\lVert x\rVert_{p}^{p} h ( x ) = ρ ∥ x ∥ p p , F = g + h F=g+h F = g + h , and F κ = κ g + h F_{\kappa}=\kappa g+h F κ = κ g + h . Set L = 2 ∥ A ∥ 2 2 L=2\lVert A\rVert_{2}^{2} L = 2 ∥ A ∥ 2 2 and μ = 2 λ min ( A T A ) ≥ 0 \mu=2\lambda_{\min}(A^{\mathsf{T}}A)\ge0 μ = 2 λ m i n ( A T A ) ≥ 0 . Here ρ \rho ρ is the regularization weight and μ \mu μ is the strong-convexity modulus of g g g .
(A2) Fix 0 < κ < p 0<\kappa<p 0 < κ < p and a constant step 0 < β k ≡ β < 1 / ( κ L ) 0<\beta_{k}\equiv\beta<1/(\kappa L) 0 < β k ≡ β < 1/ ( κ L ) , with 1 / 0 : = + ∞ 1/0:=+\infty 1/0 := + ∞ . The sequence { x k } k \{x_{k}\}_{k} { x k } k is generated by Algorithm 1 from x 1 ∈ R n x_{1}\in\mathbb{R}^{n} x 1 ∈ R n , with arbitrary selections of global proximal minimizers, and is extended constantly if the algorithm stops. Set E = F κ ( x 1 ) E=F_{\kappa}(x_{1}) E = F κ ( x 1 ) .
(A3) Choose R R R satisfying (37) and put K = B ‾ ( 0 , R ) K=\overline{B}(0,R) K = B ( 0 , R ) and γ = 2 ρ ( p − κ ) R p − 2 / κ \gamma=2\rho(p-\kappa)R^{p-2}/\kappa γ = 2 ρ ( p − κ ) R p − 2 / κ , as in (39).
By Proposition 4.2 and Lemma 4.1 , h h h is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly quasar-convex on K K K with respect to 0 0 0 in the sense of Definition 2.1 .
Conditions such as positive restricted curvature or A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 are additional hypotheses only where explicitly stated.
The convergence comparisons retain the proximal residual, so no lower restriction on β \beta β beyond positivity is imposed, and the choice of R R R imposes no further upper bound on β \beta β .
The bounds in Proposition 4.4 place every iterate, accumulation point and global comparison minimizer strictly inside K = B ‾ ( 0 , R ) K=\overline{B}(0,R) K = B ( 0 , R ) . The proximal comparisons use strong quasar-convexity only along segments to zero and quadratic growth at comparison points in K K K , while the radial subgradient inequality remains valid at interior points. Descent gives ∑ k ∥ x k + 1 − x k ∥ 2 < + ∞ \sum_k \lVert x_{k+1}-x_k\rVert^2<+\infty ∑ k ∥ x k + 1 − x k ∥ 2 < + ∞ , and continuity of h h h supplies the value convergence needed for stationarity. Consequently, the proofs of Proposition 3.14 and Theorem 3.15 apply locally to the original unconstrained iteration. When A = 0 A=0 A = 0 , the same arguments apply with L = μ = 0 L=\mu=0 L = μ = 0 ; the gradient map is then the identity, since x − κ β ∇ g ( x ) = x x-\kappa\beta\nabla g(x)=x x − κ β ∇ g ( x ) = x .
Geometric and Asymptotic Distance Estimates
We compare the iterates with global minimizers of F = g + h F=g+h F = g + h , both through a geometric envelope and through asymptotic distance bounds. We bound ∥ ∇ g ( x k ) ∥ \lVert\nabla g(x_k)\rVert ∥ ∇ g ( x k )∥ explicitly using the confinement x k ∈ B ‾ ( 0 , R ) x_k\in\overline{B}(0,R) x k ∈ B ( 0 , R ) :
∥ ∇ g ( x k ) ∥ = 2 ∥ A T ( A x k − b ) ∥ ≤ 2 ∥ A ∥ 2 ( ∥ A ∥ 2 ∥ x k ∥ + ∥ b ∥ 2 ) ≤ 2 ∥ A ∥ 2 ( ∥ A ∥ 2 R + ∥ b ∥ 2 ) = : M . (41) \lVert\nabla g(x_k)\rVert=2\lVert A^{\mathsf T}(Ax_k-b)\rVert\le2\lVert A\rVert_2(\lVert A\rVert_2\lVert x_k\rVert+\lVert b\rVert_2)
\le2\lVert A\rVert_2(\lVert A\rVert_2R+\lVert b\rVert_2)=:M. \tag*{(41)} ∥ ∇ g ( x k )∥ = 2 ∥ A T ( A x k − b )∥ ≤ 2 ∥ A ∥ 2 (∥ A ∥ 2 ∥ x k ∥ + ∥ b ∥ 2 ) ≤ 2 ∥ A ∥ 2 (∥ A ∥ 2 R + ∥ b ∥ 2 ) =: M . (41)
Corollary 4.5. (Explicit distance bounds for power-regularized least squares). Assume ( A 1 ) (A1) ( A 1 ) –( A 3 ) (A3) ( A 3 ) , and fix x ∗ ∈ argmin R n F x^*\in\operatorname*{argmin}_{\mathbb{R}^n}F x ∗ ∈ argmin R n F . Let R f R_f R f and C μ C_\mu C μ be the constants in Theorem 3.15 , with L L L , μ \mu μ and γ \gamma γ as specified in ( A ) (A) ( A ) . Set
q = ( 2 − κ ) ( 1 − κ β μ ) 2 − κ + κ β γ ∈ ( 0 , 1 ) . (42) q=\frac{(2-\kappa)(1-\kappa\beta\mu)}{2-\kappa+\kappa\beta\gamma}\in(0,1). \tag*{(42)} q = 2 − κ + κ β γ ( 2 − κ ) ( 1 − κ β μ ) ∈ ( 0 , 1 ) . (42) Then:
(a) For every k ≥ 1 k\ge1 k ≥ 1 , we have
dist ( x k , B ‾ ( x ∗ , R f ) ) ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ 2 + 4 ( 2 − κ ) κ γ ∥ A T ( A x ∗ − b ) ∥ 2 − R f ) + . (43) \operatorname{dist}(x_k,\overline{B}(x^*,R_f))\le q^{k-1}\left(\lVert x_1-x^*\rVert_2+\frac{4(2-\kappa)}{\kappa\gamma}\lVert A^{\mathsf T}(Ax^*-b)\rVert_2-R_f\right)_+. \tag*{(43)} dist ( x k , B ( x ∗ , R f )) ≤ q k − 1 ( ∥ x 1 − x ∗ ∥ 2 + κγ 4 ( 2 − κ ) ∥ A T ( A x ∗ − b ) ∥ 2 − R f ) + . (43) (b) The asymptotic distance satisfies
lim sup k ∥ x k − x ∗ ∥ 2 ≤ min { R f , 2 C μ lim sup k ∥ A T ( A x k − b ) ∥ 2 } . (44) \limsup_k\lVert x_k-x^*\rVert_2\le\min\left\{R_f,\,2C_\mu\limsup_k\lVert A^{\mathsf T}(Ax_k-b)\rVert_2\right\}. \tag*{(44)} k lim sup ∥ x k − x ∗ ∥ 2 ≤ min { R f , 2 C μ k lim sup ∥ A T ( A x k − b ) ∥ 2 } . (44)
Proof. (a) Proposition 4.4 places every iterate, accumulation point and global comparison minimizer strictly inside K K K , so the proof of Theorem 3.15 applies locally. Since ∇ g ( x ) = 2 A T ( A x − b ) \nabla g(x)=2A^{\mathsf T}(Ax-b) ∇ g ( x ) = 2 A T ( A x − b ) , we have G ∗ = 2 ∥ A T ( A x ∗ − b ) ∥ 2 G^*=2\lVert A^{\mathsf T}(Ax^*-b)\rVert_2 G ∗ = 2 ∥ A T ( A x ∗ − b ) ∥ 2 . Substituting this expression and the values of L L L , μ \mu μ and γ \gamma γ from ( A ) (A) ( A ) into Theorem 3.15 (a) gives q q q and (42).
(b) With M ∞ = 2 lim sup k ∥ A T ( A x k − b ) ∥ 2 M_\infty=2\limsup_k\lVert A^{\mathsf T}(Ax_k-b)\rVert_2 M ∞ = 2 lim sup k ∥ A T ( A x k − b ) ∥ 2 , Theorem 3.15 (b) yields (43). □
Remark 4.6. The bound (40) supplies an explicit estimate of the gradient term in (43) from the confinement radius. The estimates incorporate the strong-convexity modulus μ \mu μ , including when A A A has full column rank. When μ = 0 \mu=0 μ = 0 , the coefficient 2 C μ 2C_\mu 2 C μ reduces to
( 2 − κ ) + 2 ( 2 − κ ) ρ ( p − κ ) R 2 − p . \frac{(2-\kappa)+\sqrt{2(2-\kappa)}}{\rho(p-\kappa)}R^{2-p}. ρ ( p − κ ) ( 2 − κ ) + 2 ( 2 − κ ) R 2 − p .
The same localization of Proposition 3.14 also gives
∥ u − x ∗ ∥ 2 ≤ 2 C μ ∥ A ⊤ ( A u − b ) ∥ 2 \lVert u-x^*\rVert_2 \le2C_\mu\lVert A^\top(Au-b)\rVert_2 ∥ u − x ∗ ∥ 2 ≤ 2 C μ ∥ A ⊤ ( A u − b ) ∥ 2
for every critical point u u u of F κ F_\kappa F κ in B ( 0 , R ) B(0,R) B ( 0 , R ) and every global minimizer x ∗ x^* x ∗ of F F F .
Support Identification and Convergence
We next use the threshold structure of the power penalty to establish convergence of the whole sequence to a critical point of F κ F_\kappa F κ . We write supp ( x ) = { i : x i ≠ 0 } \operatorname{supp}(x)=\{i:x_i\ne0\} supp ( x ) = { i : x i = 0 } . For S ⊂ { 1 , … , n } S\subset\{1,\ldots,n\} S ⊂ { 1 , … , n } , x S x_S x S is the vector of coordinates indexed by S S S and A S A_S A S is the matrix formed by the corresponding columns of A A A .
Theorem 4.7 (Support identification and full-sequence convergence). Under (A1)–(A3), put a β = [ 2 β ρ ( 1 − p ) ] 1 / ( 2 − p ) a_\beta=[2\beta\rho(1-p)]^{1/(2-p)} a β = [ 2 β ρ ( 1 − p ) ] 1/ ( 2 − p ) . Every nonzero coordinate x k , i x_{k,i} x k , i of x k x_k x k , with k ≥ 2 k\ge2 k ≥ 2 , has magnitude at least a β a_\beta a β , that is, ∣ x k , i ∣ ≥ a β |x_{k,i}|\ge a_\beta ∣ x k , i ∣ ≥ a β . The support and coordinate signs therefore become constant after finitely many iterations. Denote the eventual support by S S S . Moreover,
∑ k ∥ x k + 1 − x k ∥ < + ∞ , x k → x ^ , 0 ∈ κ ∇ g ( x ^ ) + ∂ L h ( x ^ ) . \sum_k \lVert x_{k+1}-x_k\rVert< +\infty,\qquad x_k\to\widehat{x},\qquad0\in\kappa\nabla g(\widehat{x})+\partial^L h(\widehat{x}). k ∑ ∥ x k + 1 − x k ∥ < + ∞ , x k → x , 0 ∈ κ ∇ g ( x ) + ∂ L h ( x ) . These conclusions hold for every real p ∈ ] 0 , 1 [ p\in]0,1[ p ∈ ] 0 , 1 [ .
Proof. The proximal problem separates over coordinates. A nonzero scalar minimizer u u u of ρ ∣ v ∣ p + ( v − z ) 2 / ( 2 β ) \rho|v|^p+(v-z)^2/(2\beta) ρ ∣ v ∣ p + ( v − z ) 2 / ( 2 β ) satisfies z = u + β ρ p sign ( u ) ∣ u ∣ p − 1 z=u+\beta\rho p\operatorname{sign}(u)|u|^{p-1} z = u + β ρp sign ( u ) ∣ u ∣ p − 1 . Comparing its value with the value at zero gives
0 ≥ ρ ∣ u ∣ p + u 2 − 2 u z 2 β = ρ ( 1 − p ) ∣ u ∣ p − u 2 2 β . 0\ge\rho|u|^p+\frac{u^2-2uz}{2\beta}=\rho(1-p)|u|^p-\frac{u^2}{2\beta}. 0 ≥ ρ ∣ u ∣ p + 2 β u 2 − 2 u z = ρ ( 1 − p ) ∣ u ∣ p − 2 β u 2 .
hence ∣ u ∣ ≥ a β |u|\ge a_\beta ∣ u ∣ ≥ a β . Since ∥ x k + 1 − x k ∥ → 0 \lVert x_{k+1}-x_k\rVert\to0 ∥ x k + 1 − x k ∥ → 0 , transitions between zero and nonzero coordinates, which produce jumps of magnitude at least a β a_\beta a β , eventually cease; sign changes between nonzero coordinates produce jumps of magnitude at least 2 a β 2a_\beta 2 a β and also cease. If the final support S S S is empty, the sequence is eventually zero. Otherwise, the restricted iterates x k , S x_{k,S} x k , S eventually lie in a compact subset of a fixed sign orthant, with every active coordinate bounded away from zero. On this orthant
Φ S ( u ) = κ ∥ A S u − b ∥ 2 2 + ρ ∑ i ∈ S ∣ u i ∣ p \Phi_S(u)=\kappa\lVert A_Su-b\rVert_2^2+\rho\sum_{i\in S}|u_i|^p Φ S ( u ) = κ ∥ A S u − b ∥ 2 2 + ρ i ∈ S ∑ ∣ u i ∣ p
is real analytic for every real p ∈ ] 0 , 1 [ p\in]0,1[ p ∈ ] 0 , 1 [ . Proximal optimality gives
∥ ∇ Φ S ( x k + 1 , S ) ∥ ≤ ( β − 1 + κ L ) ∥ x k + 1 − x k ∥ . \lVert\nabla\Phi_S(x_{k+1,S})\rVert\le(\beta^{-1}+\kappa L)\lVert x_{k+1}-x_k\rVert. ∥ ∇ Φ S ( x k + 1 , S )∥ ≤ ( β − 1 + κ L ) ∥ x k + 1 − x k ∥ .
Along the identified tail, Φ S ( x k , S ) = F κ ( x k ) \Phi_S(x_{k,S})=F_\kappa(x_k) Φ S ( x k , S ) = F κ ( x k ) ; continuity therefore gives the same limiting objective value at every accumulation point. Sufficient decrease, the relative-gradient estimate and the local analytic gradient inequality then give finite length and convergence by the KL convergence argument [1 Theorem 2.9] . The restricted gradient vanishes at the limit, while ∂ L ( ρ ∣ ⋅ ∣ p ) ( 0 ) = R \partial^L(\rho|\cdot|^p)(0)=\mathbb{R} ∂ L ( ρ ∣ ⋅ ∣ p ) ( 0 ) = R on the complementary coordinates, proving the stated inclusion. The support and restricted-KL mechanisms are consistent with [27 , 28 ] .
Corollary 4.8 (Eventual linear rate). Assume (A1)–(A3). Let S S S and x ^ \widehat{x} x be as in Theorem 4.7 . If S ≠ ∅ S \ne\varnothing S = ∅ and
H S = 2 κ A S T A S − ρ p ( 1 − p ) Diag ( ∣ x ^ i ∣ p − 2 ) i ∈ S ≻ 0 , H_S = 2\kappa A_S^{\mathsf{T}} A_S - \rho p(1-p)\operatorname{Diag}(|\widehat{x}_i|^{p-2})_{i\in S} \succ0, H S = 2 κ A S T A S − ρp ( 1 − p ) Diag ( ∣ x i ∣ p − 2 ) i ∈ S ≻ 0 , then there exist C > 0 C > 0 C > 0 , q ℓ ∈ ] 0 , 1 [ q_{\ell} \in]0,1[ q ℓ ∈ ] 0 , 1 [ and K K K such that ∥ x k − x ^ ∥ ≤ C q ℓ k − K \lVert x_k-\widehat{x}\rVert\le Cq_{\ell}^{k-K} ∥ x k − x ∥ ≤ C q ℓ k − K for all k ≥ K k \ge K k ≥ K .
Proof. Since H S = ∇ 2 Φ S ( x ^ S ) H_S=\nabla^2\Phi_S(\widehat{x}_S) H S = ∇ 2 Φ S ( x S ) is positive definite, Φ S \Phi_S Φ S satisfies the KL inequality of Definition 2.3 with exponent θ = 1 / 2 \theta=1/2 θ = 1/2 at x ^ S \widehat{x}_S x S . Sufficient decrease and the preceding relative-gradient estimate then yield the linear-rate case of the same KL argument. □ \square □
The common-minimizer case can be identified explicitly and gives finite termination.
Lemma 4.9. Under (A1), if A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 , then x ∗ = x h = 0 x^*=x_h=0 x ∗ = x h = 0 is the unique global minimizer of F = g + h F=g+h F = g + h over R n \mathbb{R}^n R n . Conversely, if x ∗ ∈ argmin F x^*\in\operatorname{argmin}F x ∗ ∈ argmin F and ∇ g ( x ∗ ) = 0 \nabla g(x^*)=0 ∇ g ( x ∗ ) = 0 , then x ∗ = 0 x^*=0 x ∗ = 0 and A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 .
Proof. Since A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 , ∇ g ( 0 ) = − 2 A T b = 0 \nabla g(0)=-2A^{\mathsf{T}}b=0 ∇ g ( 0 ) = − 2 A T b = 0 ; as g g g is convex, 0 ∈ argmin R n g 0\in\operatorname{argmin}_{\mathbb{R}^n}g 0 ∈ argmin R n g , i.e., g ( 0 ) = g ∗ = ∥ b ∥ 2 2 g(0)=g^*=\lVert b\rVert_2^2 g ( 0 ) = g ∗ = ∥ b ∥ 2 2 . For every x ≠ 0 x\ne0 x = 0 , g ( x ) ≥ g ∗ = g ( 0 ) g(x)\ge g^*=g(0) g ( x ) ≥ g ∗ = g ( 0 ) and h ( x ) = ρ ∥ x ∥ p p > 0 = h ( 0 ) h(x)=\rho\lVert x\rVert_p^p>0=h(0) h ( x ) = ρ ∥ x ∥ p p > 0 = h ( 0 ) (as p > 0 p>0 p > 0 ), so F ( x ) = g ( x ) + h ( x ) > g ( 0 ) + h ( 0 ) = F ( 0 ) F(x)=g(x)+h(x)>g(0)+h(0)=F(0) F ( x ) = g ( x ) + h ( x ) > g ( 0 ) + h ( 0 ) = F ( 0 ) . Hence 0 is the unique global minimizer of F F F , and since x h = 0 x_h=0 x h = 0 as well, x ∗ = x h = 0 x^*=x_h=0 x ∗ = x h = 0 . For the converse, if x ∗ ∈ argmin F x^*\in\operatorname{argmin}F x ∗ ∈ argmin F and ∇ g ( x ∗ ) = 0 \nabla g(x^*)=0 ∇ g ( x ∗ ) = 0 , then a nonzero coordinate would satisfy the necessary condition ρ p sign ( x i ∗ ) ∣ x i ∗ ∣ p − 1 = 0 \rho p\operatorname{sign}(x_i^*)|x_i^*|^{p-1}=0 ρp sign ( x i ∗ ) ∣ x i ∗ ∣ p − 1 = 0 , a contradiction. Thus x ∗ = 0 x^*=0 x ∗ = 0 and A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 . □ \square □
Corollary 4.10 (Finite termination in the case A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 ). Assume (A1)–(A3). Suppose A T b = 0 A^{\mathsf{T}}b=0 A T b = 0 . Then the algorithm reaches zero in finitely many iterations. More precisely, any k ≥ 2 k\ge2 k ≥ 2 such that
q k − 1 ∥ x 1 ∥ 2 < a β , q^{k-1}\lVert x_1\rVert_2<a_{\beta}, q k − 1 ∥ x 1 ∥ 2 < a β , with q q q from (41) and a β a_{\beta} a β from Theorem 4.7 , satisfies x j = 0 x_j=0 x j = 0 for every j ≥ k j\ge k j ≥ k .
Proof. By Lemma 4.9 , x ∗ = 0 x^*=0 x ∗ = 0 and G ∗ = 0 G^*=0 G ∗ = 0 . Thus R f = 0 R_f=0 R f = 0 , and Corollary 4.5(a) gives ∥ x k ∥ 2 ≤ q k − 1 ∥ x 1 ∥ 2 \lVert x_k\rVert_2\le q^{k-1}\lVert x_1\rVert_2 ∥ x k ∥ 2 ≤ q k − 1 ∥ x 1 ∥ 2 . The nonzero-coordinate gap in Theorem 4.7 therefore forces x k = 0 x_k=0 x k = 0 whenever the stated inequality holds. Since 0 < q < 1 0<q<1 0 < q < 1 and a β > 0 a_{\beta}>0 a β > 0 , such an iteration is reached in finite time. The next proximal subproblem has input zero and unique minimizer zero, so all subsequent iterates remain zero. □ \square □
Conclusions
We developed quantitative proximal-gradient comparisons for a convex smooth term and a possibly nonconvex strongly quasar-convex regularizer. The arbitrary-reference proximal inequality yields optimized composite distance estimates. A radial argument also gives a geometric envelope around every global minimizer of the unweighted objective, with a radius independent of the step size. The critical-point comparison extends the best asymptotic comparison constant to all values of μ ≥ 0 \mu\ge0 μ ≥ 0 , and a common minimizer yields global linear convergence. Critical-point convergence concerns the weighted objective decreased by the iteration, while the distance estimates use global minimizers of the unweighted objective as reference points. The weighting example shows that the two notions of criticality can differ.
For power-regularized least squares, descent provides the ball needed for local strong quasar-convexity. Identification of the support and signs after finitely many iterations, combined with analyticity on the identified support, yields whole-sequence convergence to a critical point of the weighted objective for every real power between zero and one. Positive restricted curvature yields an eventual linear rate. Future work may address inexact proximal solutions and adaptive parameter selection while preserving these comparisons.
Declarations
Availability of Supporting Data
No data sets were generated during the current study.
Author Contributions
All authors contributed equally to the conception, design and implementation of the study and drafted and revised the manuscript.
Conflicts of Interest
There are no conflicts of interest or competing interests related to this manuscript.
Funding
This work has been partially supported by ANID—Chile through Fondecyt Regular 1241040 (Lara).