Min Tao (corresponding author)
Mathematics Subject Classification (2020) 90C26 · 65K05 · 90C30
Introduction
Sparse optimization models often combine a smooth loss with a regularizer that is nonsmooth in the full space. However, many sparsity-promoting regularizers yield a twice continuously differentiable objective when restricted to a fixed support. We combine full-space proximal-gradient steps with cubic-regularized Newton steps on a selected coordinate subspace. A central question is whether the selected coordinate set eventually coincides with the support of the limit point when the usual nondegeneracy condition fails. We prove that finite support identification still holds under a suitable thresholding rule determined by the positive power-type KL exponent of the objective at the limit.
In this paper, we consider composite problems of the form
min x ∈ R n F ( x ) : = g ( x ) + h ( x ) , (1) \min_{x\in\mathbb{R}^{n}} F(x) := g(x) + h(x), \tag*{(1)} x ∈ R n min F ( x ) := g ( x ) + h ( x ) , (1)
where g : R n → R ‾ : = R ∪ { + ∞ } g:\mathbb{R}^{n}\to\overline{\mathbb{R}}:=\mathbb{R}\cup\{+\infty\} g : R n → R := R ∪ { + ∞ } is a proper, lower semicontinuous (l.s.c.), possibly nonconvex and nonsmooth function that is prox-bounded with threshold λ g > 0 \lambda_g>0 λ g > 0 and whose proximal mapping Prox γ g \operatorname{Prox}_{\gamma g} Prox γ g can be computed efficiently for 0 < γ < λ g 0<\gamma<\lambda_g 0 < γ < λ g . We use the following standing assumptions.
Assumption 1.1 (i) For every nonzero x ∈ dom F \mathbf{x}\in\operatorname{dom}F x ∈ dom F , let
M x = { z ∈ R n : supp ( z ) = supp ( x ) } . \mathcal{M}_{\mathbf{x}}=\{\mathbf{z}\in\mathbb{R}^{n}:\operatorname{supp}(\mathbf{z})=\operatorname{supp}(\mathbf{x})\}. M x = { z ∈ R n : supp ( z ) = supp ( x )} .
The restriction of F F F to M x \mathcal{M}_{\mathbf{x}} M x is finite-valued and twice continuously differentiable in a relative neighborhood of x \mathbf{x} x . For every nonempty S ⊆ supp ( x ) S\subseteq\operatorname{supp}(\mathbf{x}) S ⊆ supp ( x ) , let ∇ S F \nabla_S F ∇ S F and ∇ S 2 F \nabla_S^2 F ∇ S 2 F denote the corresponding coordinate gradient and principal Hessian of this restriction, respectively. The mapping ∇ S 2 F \nabla_S^2F ∇ S 2 F is strictly continuous at x \mathbf{x} x relative to M x \mathcal{M}_{\mathbf{x}} M x , with the constant lip M x ∇ S 2 F ( x ) \operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2F(\mathbf{x}) lip M x ∇ S 2 F ( x ) ; see Definition 2.4.
(ii) h : R n → R h:\mathbb{R}^{n}\to\mathbb{R} h : R n → R is continuously differentiable with an L L L -Lipschitz continuous gradient for some L ≥ 0 L\geq0 L ≥ 0 .
(iii) The objective function is bounded below, i.e., F ‾ : = inf x ∈ R n F ( x ) > − ∞ \underline{F}:=\inf_{\mathbf{x}\in\mathbb{R}^{n}}F(\mathbf{x})>-\infty F := inf x ∈ R n F ( x ) > − ∞ .
The following two models illustrate that the local smoothness condition in Assumption 1.1(i) can be readily satisfied.
(a) Sparse recovery. For A ∈ R m × n A\in\mathbb{R}^{m\times n} A ∈ R m × n , b ∈ R m \mathbf{b}\in\mathbb{R}^{m} b ∈ R m , and λ > 0 \lambda>0 λ > 0 , consider problem (1.1) with h ( x ) = 1 2 ∥ A x − b ∥ 2 2 h(\mathbf{x})=\frac{1}{2}\lVert A\mathbf{x}-\mathbf{b}\rVert_2^2 h ( x ) = 2 1 ∥ A x − b ∥ 2 2 .
(i) L 1 / L 2 L_1/L_2 L 1 / L 2 regularization. Let g ( x ) = λ ∥ x ∥ 1 / ∥ x ∥ 2 g(\mathbf{x})=\lambda\lVert\mathbf{x}\rVert_1/\lVert\mathbf{x}\rVert_2 g ( x ) = λ ∥ x ∥ 1 / ∥ x ∥ 2 ; see Tao [38 ] . We define ∥ 0 ∥ 1 / ∥ 0 ∥ 2 = 1 \lVert\mathbf{0}\rVert_1/\lVert\mathbf{0}\rVert_2=1 ∥ 0 ∥ 1 / ∥ 0 ∥ 2 = 1 to make g g g lower semicontinuous at the origin. For x ≠ 0 \mathbf{x}\ne\mathbf{0} x = 0 and ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}) ∅ = S ⊆ supp ( x ) , its restricted Hessian satisfies
lip M x ∇ S 2 F ( x ) ≤ 36 λ ∥ x ∥ 0 ∥ x ∥ 2 3 . \operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2F(\mathbf{x})\leq\frac{36\lambda\sqrt{\lVert\mathbf{x}\rVert_0}}{\lVert\mathbf{x}\rVert_2^3}. lip M x ∇ S 2 F ( x ) ≤ ∥ x ∥ 2 3 36 λ ∥ x ∥ 0 .
(ii) L p p L_p^p L p p regularization. Let g ( x ) = λ ∥ x ∥ p p g(\mathbf{x})=\lambda\|\mathbf{x}\|_p^p g ( x ) = λ ∥ x ∥ p p , 0 < p < 1 0<p<1 0 < p < 1 ; see [46 ] . For x ≠ 0 \mathbf{x}\ne\mathbf{0} x = 0 and ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}) ∅ = S ⊆ supp ( x ) , its restricted Hessian satisfies
lip M x ∇ S 2 F ( x ) ≤ λ p ( 1 − p ) ( 2 − p ) ( min i ∈ S ∣ x i ∣ ) 3 − p . \operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2 F(\mathbf{x})\le\frac{\lambda p(1-p)(2-p)}{(\min_{i\in S}|x_i|)^{3-p}}. lip M x ∇ S 2 F ( x ) ≤ ( min i ∈ S ∣ x i ∣ ) 3 − p λ p ( 1 − p ) ( 2 − p ) .
(b) L 1 − μ L 2 L_1-\mu L_2 L 1 − μ L 2 -regularized logistic regression. Let the rows of A ∈ R m × n A\in\mathbb{R}^{m\times n} A ∈ R m × n be a i T \mathbf{a}_i^\mathsf{T} a i T , and let b i ∈ { − 1 , 1 } b_i\in\{-1,1\} b i ∈ { − 1 , 1 } . For λ > 0 \lambda>0 λ > 0 and 0 < μ ≤ 1 0<\mu\le1 0 < μ ≤ 1 , consider [35 ]
min ( z , u ) ∈ R n × R λ ( ∥ z ∥ 1 − μ ∥ z ∥ 2 ) + 1 m ∑ i = 1 m log ( 1 + e − b i ( a i T z + u ) ) . (2) \min_{(\mathbf{z},u)\in\mathbb{R}^n\times\mathbb{R}} \lambda(\|\mathbf{z}\|_1-\mu\|\mathbf{z}\|_2)+\frac{1}{m}\sum_{i=1}^{m}\log(1+e^{-b_i(\mathbf{a}_i^\mathsf{T}\mathbf{z}+u)}). \tag*{(2)} ( z , u ) ∈ R n × R min λ ( ∥ z ∥ 1 − μ ∥ z ∥ 2 ) + m 1 i = 1 ∑ m log ( 1 + e − b i ( a i T z + u ) ) . (2)
Here u u u is an unpenalized intercept. Set x = ( z , u ) \mathbf{x}=(\mathbf{z},u) x = ( z , u ) , take the regularization term as g g g , and take the logistic loss as h h h . For z ≠ 0 \mathbf{z}\ne\mathbf{0} z = 0 , write S z = supp ( z ) S_z=\operatorname{supp}(\mathbf{z}) S z = supp ( z ) . For ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}) ∅ = S ⊆ supp ( x ) ,
lip ∇ S 2 F ( x ) ≤ { M log + 2 λ μ 3 ∥ z ∥ 2 2 , z ≠ 0 , 1 6 3 , z = 0 , u ≠ 0. \operatorname{lip}\nabla_S^2F(\mathbf{x})\le
\begin{cases}
M_{\log}+\dfrac{2\lambda\mu}{\sqrt{3}\|\mathbf{z}\|_2^2}, & \mathbf{z}\ne\mathbf{0},\\
\dfrac{1}{6\sqrt{3}}, & \mathbf{z}=\mathbf{0},u\ne0.
\end{cases} lip ∇ S 2 F ( x ) ≤ ⎩ ⎨ ⎧ M l o g + 3 ∥ z ∥ 2 2 2 λ μ , 6 3 1 , z = 0 , z = 0 , u = 0.
M log = 1 6 3 m ∑ i = 1 m ( ∥ a i , S z ∥ 2 2 + 1 ) 3 / 2 . M_{\log}=\frac{1}{6\sqrt{3}m}\sum_{i=1}^{m}(\|\mathbf{a}_{i,S_z}\|_2^2+1)^{3/2}. M l o g = 6 3 m 1 i = 1 ∑ m ( ∥ a i , S z ∥ 2 2 + 1 ) 3/2 .
Table 1 lists several commonly used sparsity-promoting regularizers that satisfy Assumption 1.1(i).
Table 1. Examples of regularization functions g g g for x ≠ 0 \mathbf{x}\ne\mathbf{0} x = 0 and ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}) ∅ = S ⊆ supp ( x ) .
Related Work and Motivation
Proximal-gradient methods combine a gradient evaluation of h h h with a proximal evaluation of g g g , without requiring prior knowledge of the relevant support [4 ] . To accelerate these methods, Themelis, Stella, and Patrinos [42 ] propose ZeroFPR, which uses quasi-Newton corrections based on the forward–backward residual and a nonmonotone line search. For sparse composite problems, an alternative is to exploit the local smoothness of the objective on a fixed support. This approach leads to hybrid methods that combine first-order updates with second-order steps on selected subspaces.
Several algorithms use this structure. For L p p L_p^p L p p regularization, 0 < p < 1 0 < p < 1 0 < p < 1 , HpgSRN uses signed-support identification and nonzero-magnitude checks before taking subspace regularized Newton steps [45 ] . IReNA combines reweighted L 1 L_1 L 1 updates with inexact subspace Newton steps for separable concave penalties, imposing additional gradient restrictions beyond power penalties [44 ] . FaRSA-Group combines group proximal-gradient and conjugate-gradient-based subspace Newton steps, with analysis under strong convexity and a strict dual margin on inactive groups [14 ] . For L 1 / L 2 L_1/L_2 L 1 / L 2 minimization, HAFAM combines A D M M p \mathrm{ADMM}_p ADMM p or A D M M p + \mathrm{ADMM}_p^+ ADMM p + with globalized semismooth Newton steps, using a relative-interior condition for identification [41 ] . Optimality-based coordinate selection is also used in reduced-space methods for L 1 L_1 L 1 -regularized convex problems [13 ] .
A key question in selecting the subspaces is whether the chosen coordinates eventually coincide with the limiting support. Finite identification is commonly established through partial smoothness and nondegeneracy [23 , 26 ] . Related results concern active constraints under partial smoothness and prox-regularity [17 ] , proximal linearized methods [24 ] , and connections with Newton-type acceleration [25 ] . For forward–backward methods, Liang, Fadili, and Peyré [28 ] establish finite active-manifold identification and local linear convergence, while Nutini, Schmidt, and Hare [34 ] derive identification-complexity bounds for proximal-gradient methods.
This connection between identification and acceleration also underlies manifold-based methods. For convex partly smooth regularizers, ISQA+ combines successive quadratic approximation with semismooth Newton or Riemannian quasi-Newton steps [22 ] . ManAcc combines proximal-gradient and Riemannian Newton-type steps for potentially nonconvex partly smooth regularizers [3 ] . Both use a relative-interior condition to establish identification, so these guarantees do not cover limits at which that condition fails. Identification without nondegeneracy is nevertheless possible for particular penalties: Tao and Zhang [40 ] establish identification-complexity bounds for L 0 L_0 L 0 and L p L_p L p regularization. This motivates the study of support-selection rules that avoid nondegeneracy in the composite setting considered here.
Besides selecting a suitable subspace, the second-order method should also handle the potential nonconvexity of the resulting model. Cubic regularization offers a natural way to address this challenge. Under suitable smoothness assumptions and inexact subproblem-solution criteria, cubic-regularized Newton methods for smooth nonconvex optimization achieve an O ( ε − 3 / 2 ) \mathcal{O}(\varepsilon^{-3/2}) O ( ε − 3/2 ) iteration bound for a gradient tolerance ε \varepsilon ε and a curvature tolerance proportional to ε \sqrt{\varepsilon} ε [11 , 12 , 33 ] . Cubic Newton steps on random coordinate subspaces have also been studied by Zhao, Doikov, and Lucchi [50 ] . These results motivate combining cubic regularization with a coordinate-selection rule designed to identify the limiting support.
We pursue this combination through full-space proximal-gradient steps and inexact cubic-regularized Newton steps on a threshold-selected coordinate subspace. Rather than requiring the proximal iterates themselves to identify the limiting support, we seek finite identification of the selected coordinate set through a threshold guided by the Kurdyka–Łojasiewicz property. The resulting questions are whether identification can be established without nondegeneracy and under what assumptions the hybrid method admits whole-sequence convergence and post-identification complexity bounds.
Main results
We propose the Hybrid Proximal-Gradient and Subspace Cubic-Newton (HPG-SCN) method and its adaptive variant (AHPG-SCN). At iteration k k k , a proximal-gradient step produces x k x^k x k , and the method selects the coordinates
S k : = { i : ∣ x i k ∣ ≥ ε k } . S^k := \{i : |x_i^k| \geq\varepsilon_k\}. S k := { i : ∣ x i k ∣ ≥ ε k } .
It then computes an inexact cubic-regularized Newton direction on this coordinate subspace and uses backtracking on the original objective to accept a step. Our main results are as follows.
We establish sufficient decrease and a relative-error estimate for the composite iteration. If the iterates are bounded and the objective has the Kurdyka–Łojasiewicz (KL) property, the iterate sequence has finite length and converges to a first-order stationary point. A threshold rule guided by the KL exponent ensures finite support identification without a nondegeneracy assumption. A residual-based logarithmic threshold gives the same conclusion when the KL exponent is unknown.
Under an additional continuity assumption on the restricted Hessian, the line search eventually accepts full cubic steps. With bounded cubic regularization parameters and damping chosen for the target tolerances, Theorem 6.5 gives an explicit outer-iteration count after support identification and entry into the full-step regime.
We develop AHPG-SCN, which adaptively updates the cubic regularization parameter by comparing actual and predicted reductions. Numerical experiments investigate support identification without nondegeneracy and compare HPG-SCN and AHPG-SCN with several existing methods, demonstrating the computational efficiency of the proposed algorithms.
Organization. Section 2 introduces notation and preliminary results. Section 3 presents HPG-SCN and the Lanczos solver for the cubic subproblem. Section 4 gives the global convergence analysis. Section 5 analyzes finite support identification for the power and logarithmic thresholds. Section 6 studies restricted second-order stationarity and bounds the outer-iteration count in the full-step regime. Section 7 introduces AHPG-SCN and reports the numerical experiments. Section 8 summarizes the results. Appendices A and B give bounds for the local restricted Hessian Lipschitz modulus and sufficient conditions for boundedness, respectively.
Preliminaries
Vector norms are Euclidean and matrix norms are spectral unless stated otherwise. We write N = { 0 , 1 , 2 , … } \mathbb{N}=\{0,1,2,\ldots\} N = { 0 , 1 , 2 , … } and [ m ] = { 1 , … , m } [m]=\{1,\ldots,m\} [ m ] = { 1 , … , m } for a positive integer m m m . For any r > 0 r>0 r > 0 , let B ( x ˉ , r ) : = { x : ∥ x − x ˉ ∥ ≤ r } \mathcal{B}(\bar{x},r):=\{x:\lVert x-\bar{x}\rVert\le r\} B ( x ˉ , r ) := { x : ∥ x − x ˉ ∥ ≤ r } . For an extended-real-valued function f : R n → ( − ∞ , + ∞ ] f:\mathbb{R}^{n}\to(-\infty,+\infty] f : R n → ( − ∞ , + ∞ ] , define dom f : = { x : f ( x ) < + ∞ } \operatorname{dom}f:=\{x:f(x)<+\infty\} dom f := { x : f ( x ) < + ∞ } . The function is proper if dom f ≠ ∅ \operatorname{dom}f\ne\varnothing dom f = ∅ . It is lower semicontinuous if f ( x ˉ ) ≤ lim inf x → x ˉ f ( x ) f(\bar{x})\le\liminf_{x\to\bar{x}}f(x) f ( x ˉ ) ≤ lim inf x → x ˉ f ( x ) for every x ˉ ∈ R n \bar{x}\in\mathbb{R}^{n} x ˉ ∈ R n . The symbol # ( D ) \#(D) # ( D ) denotes the cardinality of D D D . λ min ( ⋅ ) \lambda_{\min}(\cdot) λ m i n ( ⋅ ) denotes the smallest eigenvalue, and ker ( ⋅ ) \operatorname{ker}(\cdot) ker ( ⋅ ) denotes the null space. S n × n \mathbb{S}^{n\times n} S n × n denotes the set of n × n n\times n n × n symmetric matrices. For a proper, lower-semicontinuous function f f f , the proximal mapping with parameter α > 0 \alpha>0 α > 0 is defined by
prox α f ( z ) = arg min x ∈ R n ( f ( x ) + 1 2 α ∥ x − z ∥ 2 ) . \operatorname{prox}_{\alpha f}(z)=\mathop{\operatorname{arg\,min}}_{x\in\mathbb{R}^{n}}\left(f(x)+\frac{1}{2\alpha}\lVert x-z\rVert^{2}\right). prox α f ( z ) = arg min x ∈ R n ( f ( x ) + 2 α 1 ∥ x − z ∥ 2 ) .
Definition 2.1 Let f : R n → R ‾ f:\mathbb{R}^{n}\to\overline{\mathbb{R}} f : R n → R be a proper lower semicontinuous function, and let x ∈ dom f x\in\operatorname{dom}f x ∈ dom f .
(a) A vector v v v is a regular (Fréchet) subgradient of f f f at x x x , written v ∈ ∂ ^ f ( x ) v\in\widehat{\partial}f(x) v ∈ ∂ f ( x ) , if f ( y ) ≥ f ( x ) + ⟨ v , y − x ⟩ + o ( ∥ y − x ∥ ) f(y)\ge f(x)+\langle v,y-x\rangle+o(\lVert y-x\rVert) f ( y ) ≥ f ( x ) + ⟨ v , y − x ⟩ + o (∥ y − x ∥) . The little-o relation is understood as y → x y\to x y → x .
(b) A vector v v v belongs to the limiting subdifferential ∂ f ( x ) \partial f(x) ∂ f ( x ) if there exist sequences x k → x x_k\to x x k → x and v k → v v_k\to v v k → v such that x k ∈ dom f x_k\in\operatorname{dom}f x k ∈ dom f , v k ∈ ∂ ^ f ( x k ) v_k\in\widehat{\partial}f(x_k) v k ∈ ∂ f ( x k ) , and f ( x k ) → f ( x ) f(x_k)\to f(x) f ( x k ) → f ( x ) .
We say x ∈ dom f x\in\operatorname{dom}f x ∈ dom f is a first-order stationary point of f f f if 0 ∈ ∂ f ( x ) 0\in\partial f(x) 0 ∈ ∂ f ( x ) . We use the KL property and exponent as in Attouch and Bolte [1 ] , and strict continuity as in Rockafellar and Wets [36, Definition 9.1].
Definition 2.2 A proper function f : R n → R ‾ f:\mathbb{R}^{n}\to\overline{\mathbb{R}} f : R n → R is said to satisfy the Kurdyka-Lojasiewicz (KL) property at a point x ˉ ∈ dom ∂ f \bar{x}\in\operatorname{dom}\partial f x ˉ ∈ dom ∂ f if there exist a constant η ∈ ( 0 , + ∞ ] \eta\in(0,+\infty] η ∈ ( 0 , + ∞ ] , an open neighborhood U U U of x ˉ \bar{x} x ˉ , and a concave and continuous function φ : [ 0 , η ) → [ 0 , + ∞ ) \varphi:[0,\eta)\to[0,+\infty) φ : [ 0 , η ) → [ 0 , + ∞ ) with the properties
(i) φ ( 0 ) = 0 \varphi(0)=0 φ ( 0 ) = 0 ;
(ii) φ \varphi φ is continuously differentiable on ( 0 , η ) (0,\eta) ( 0 , η ) and φ ′ ( ⋅ ) > 0 \varphi'(\cdot)>0 φ ′ ( ⋅ ) > 0 on ( 0 , η ) (0,\eta) ( 0 , η ) ;
(iii) for every x ∈ U x\in U x ∈ U with f ( x ˉ ) < f ( x ) < f ( x ˉ ) + η f(\bar{x})<f(x)<f(\bar{x})+\eta f ( x ˉ ) < f ( x ) < f ( x ˉ ) + η , it holds
φ ′ ( f ( x ) − f ( x ˉ ) ) dist ( 0 , ∂ f ( x ) ) ≥ 1. \varphi'(f(x)-f(\bar{x}))\operatorname{dist}(0,\partial f(x))\ge1. φ ′ ( f ( x ) − f ( x ˉ )) dist ( 0 , ∂ f ( x )) ≥ 1.
The class of so-called desingularization functions ϕ : [ 0 , η ) → [ 0 , + ∞ ) \phi: [0,\eta) \to[0,+\infty) ϕ : [ 0 , η ) → [ 0 , + ∞ ) fulfilling (i)–(iii) is denoted by Φ η \Phi_{\eta} Φ η .
Definition 2.3 Let f : R n → ( − ∞ , + ∞ ] f:\mathbb{R}^{n}\to(-\infty,+\infty] f : R n → ( − ∞ , + ∞ ] be proper and lower semicontinuous, and let x ˉ ∈ dom ( ∂ f ) \bar{x}\in\operatorname{dom}(\partial f) x ˉ ∈ dom ( ∂ f ) be a point satisfying 0 ∈ ∂ f ( x ˉ ) 0\in\partial f(\bar{x}) 0 ∈ ∂ f ( x ˉ ) . We say that f f f satisfies the KL property at x ˉ \bar{x} x ˉ with exponent θ ∈ [ 0 , 1 ) \theta\in[0,1) θ ∈ [ 0 , 1 ) if there exist constants ξ > 0 \xi>0 ξ > 0 , ϵ > 0 \epsilon>0 ϵ > 0 and ν > 0 \nu>0 ν > 0 such that
dist ( 0 , ∂ f ( x ) ) ≥ ν ( f ( x ) − f ( x ˉ ) ) θ , \operatorname{dist}(0,\partial f(x))\geq\nu\bigl(f(x)-f(\bar{x})\bigr)^{\theta}, dist ( 0 , ∂ f ( x )) ≥ ν ( f ( x ) − f ( x ˉ ) ) θ , whenever ∥ x − x ˉ ∥ < ϵ \lVert x-\bar{x}\rVert<\epsilon ∥ x − x ˉ ∥ < ϵ and 0 < f ( x ) − f ( x ˉ ) < ξ 0<f(x)-f(\bar{x})<\xi 0 < f ( x ) − f ( x ˉ ) < ξ .
Definition 2.4 Let F : D ⊆ R n → R m × s F:D\subseteq\mathbb{R}^{n}\to\mathbb{R}^{m\times s} F : D ⊆ R n → R m × s be a single-valued mapping, and let X ⊆ D X\subseteq D X ⊆ D . We say that F F F is strictly continuous at x ˉ \bar{x} x ˉ relative to X X X if x ˉ ∈ X \bar{x}\in X x ˉ ∈ X and the quantity
lip X F ( x ˉ ) : = lim sup x , x ′ → x ˉ x , x ′ ∈ X , x ≠ x ′ ∥ F ( x ′ ) − F ( x ) ∥ ∥ x − x ′ ∥ \operatorname{lip}_{X}F(\bar{x}):=\limsup_{\substack{x,x'\to\bar{x}\\x,x'\in X,\ x\ne x'}}\frac{\lVert F(x')-F(x)\rVert}{\lVert x-x'\rVert} lip X F ( x ˉ ) := x , x ′ → x ˉ x , x ′ ∈ X , x = x ′ lim sup ∥ x − x ′ ∥ ∥ F ( x ′ ) − F ( x )∥ is finite. This quantity is also called the Lipschitz constant of F F F at x ˉ \bar{x} x ˉ relative to X X X .
Throughout the paper, we use lip M ∇ 2 F ( x ) \operatorname{lip}_{\mathcal{M}}\nabla^{2}F(x) lip M ∇ 2 F ( x ) to denote the Lipschitz constant of ∇ 2 F \nabla^{2}F ∇ 2 F at x x x relative to M \mathcal{M} M . When no ambiguity arises, we write lip ∇ 2 F ( x ) \operatorname{lip}\nabla^{2}F(x) lip ∇ 2 F ( x ) . Proposition 2.5 states the global optimality conditions for the cubic subproblem. For a proof, see Nesterov and Polyak [33 Proposition 1] and Jia et al. [19 ] .
Proposition 2.5 Let H ^ ∈ S n × n \widehat{H}\in\mathbb{S}^{n\times n} H ∈ S n × n , g ∈ R n g\in\mathbb{R}^{n} g ∈ R n , and σ > 0 \sigma>0 σ > 0 . Consider the following cubic-regularized Newton problem:
min d ∈ R n { ⟨ g , d ⟩ + 1 2 ⟨ H ^ d , d ⟩ + σ 6 ∥ d ∥ 3 } . (3) \min_{d\in\mathbb{R}^{n}}\left\{\langle g,d\rangle+\frac{1}{2}\langle\widehat{H}d,d\rangle+\frac{\sigma}{6}\lVert d\rVert^{3}\right\}. \tag*{(3)} d ∈ R n min { ⟨ g , d ⟩ + 2 1 ⟨ H d , d ⟩ + 6 σ ∥ d ∥ 3 } . (3) Let λ 1 \lambda_{1} λ 1 denote the smallest eigenvalue of H ^ \widehat{H} H . Then there exists λ ⋆ ≥ 0 \lambda^{\star}\geq0 λ ⋆ ≥ 0 such that every global minimizer d ⋆ d^{\star} d ⋆ satisfies
( H ^ + λ ⋆ I ) d ⋆ = − g , H ^ + λ ⋆ I ⪰ 0 , λ ⋆ = σ 2 ∥ d ⋆ ∥ . (4) (\widehat{H}+\lambda^{\star}I)d^{\star}=-g,\qquad\widehat{H}+\lambda^{\star}I\succeq0,\qquad\lambda^{\star}=\frac{\sigma}{2}\lVert d^{\star}\rVert. \tag*{(4)} ( H + λ ⋆ I ) d ⋆ = − g , H + λ ⋆ I ⪰ 0 , λ ⋆ = 2 σ ∥ d ⋆ ∥ . (4) Moreover, for any unit eigenvector v 1 v_{1} v 1 associated with λ 1 \lambda_{1} λ 1 , the following expression gives a global minimizer d ⋆ d^{\star} d ⋆ of (2.1):
d ⋆ = { − ( H ^ + λ ⋆ I ) − 1 g , if λ ⋆ > − λ 1 , − ( H ^ + λ ⋆ I ) † g + α v 1 , if λ ⋆ = − λ 1 , d^{\star}=
\begin{cases}
-(\widehat{H}+\lambda^{\star}I)^{-1}g, & \text{if }\lambda^{\star}>-\lambda_{1},\\
-(\widehat{H}+\lambda^{\star}I)^{\dagger}g+\alpha v_{1}, & \text{if }\lambda^{\star}=-\lambda_{1},
\end{cases} d ⋆ = { − ( H + λ ⋆ I ) − 1 g , − ( H + λ ⋆ I ) † g + α v 1 , if λ ⋆ > − λ 1 , if λ ⋆ = − λ 1 , where, in the second case, α ∈ R \alpha\in\mathbb{R} α ∈ R satisfies
∥ − ( H ^ + λ ⋆ I ) † g + α v 1 ∥ = 2 λ ⋆ σ . \left\lVert-(\widehat{H}+\lambda^{\star}I)^{\dagger}g+\alpha v_{1}\right\rVert=\frac{2\lambda^{\star}}{\sigma}. − ( H + λ ⋆ I ) † g + α v 1 = σ 2 λ ⋆ . Here, ( ⋅ ) † (\cdot)^{\dagger} ( ⋅ ) † denotes the Moore–Penrose pseudoinverse.
The Hybrid Subspace Cubic-Newton Method
Algorithm 1 combines a full-space proximal-gradient step with an inexact cubic-regularized Newton step on a selected coordinate subspace. At each iteration, the proximal-gradient step generates x k x^k x k from y k − 1 y^{k-1} y k − 1 . The subspace step then updates selected coordinates to obtain y k y^k y k . Both steps employ line searches to ensure sufficient decrease in the original objective function F F F .
The proximal-gradient line search starts from
α k , 0 = { min { ∥ y k − 1 − y k − 2 ∥ ∥ ∇ h ( y k − 1 ) − ∇ h ( y k − 2 ) ∥ , α ˉ } , if k ≥ 2 and ∇ h ( y k − 1 ) ≠ ∇ h ( y k − 2 ) , α 0 , otherwise , (5) \alpha_{k,0} =
\begin{cases}
\min\left\{\dfrac{\lVert y^{k-1}-y^{k-2}\rVert}{\lVert\nabla h(y^{k-1})-\nabla h(y^{k-2})\rVert},\bar{\alpha}\right\}, & \text{if } k\ge2\text{ and }\nabla h(y^{k-1})\ne\nabla h(y^{k-2}),\\
\alpha_0, & \text{otherwise},
\end{cases} \tag*{(5)} α k , 0 = ⎩ ⎨ ⎧ min { ∥ ∇ h ( y k − 1 ) − ∇ h ( y k − 2 )∥ ∥ y k − 1 − y k − 2 ∥ , α ˉ } , α 0 , if k ≥ 2 and ∇ h ( y k − 1 ) = ∇ h ( y k − 2 ) , otherwise , (5)
where 0 < α 0 < α ˉ < λ g 0<\alpha_0<\bar{\alpha}<\lambda_g 0 < α 0 < α ˉ < λ g . The trial stepsize is reduced by a factor q 1 ∈ ( 0 , 1 ) q_1\in(0,1) q 1 ∈ ( 0 , 1 ) until the proximal-gradient point satisfies the prescribed decrease condition. For positive trial stepsizes, the bound α k , l k ≤ α ˉ < λ g \alpha_{k,l_k}\le\bar{\alpha}<\lambda_g α k , l k ≤ α ˉ < λ g ensures that the proximal subproblems are well-defined. At the accepted point x k x^k x k , we select the coordinates
S k : = { i : ∣ x i k ∣ ≥ ϵ k } , n k : = ♯ ( S k ) . S^k:=\{i:|x_i^k|\ge\epsilon_k\},\qquad n_k:=\sharp(S^k). S k := { i : ∣ x i k ∣ ≥ ϵ k } , n k := ♯ ( S k ) .
where the thresholds ϵ k \epsilon_k ϵ k are chosen according to the rules in § 6 . When S k ≠ ∅ S^k\ne\varnothing S k = ∅ , Assumption 1.1(i) ensures that the restriction of F F F to the affine slice through x k x^k x k , with all coordinates outside S k S^k S k fixed, is twice continuously differentiable near x k x^k x k . We denote its gradient and Hessian at x k x^k x k by
g k : = ∇ S k F ( x k ) , H k : = ∇ S k 2 F ( x k ) . g^k:=\nabla_{S^k}F(x^k),\qquad H^k:=\nabla^2_{S^k}F(x^k). g k := ∇ S k F ( x k ) , H k := ∇ S k 2 F ( x k ) .
The subspace step d k ∈ R n k d^k\in\mathbb{R}^{n_k} d k ∈ R n k is an approximate solution of the cubic-regularized Newton subproblem
min d ∈ R n k { ⟨ g k , d ⟩ + 1 2 ⟨ ( H k + η I ) d , d ⟩ + σ k 6 ∥ d ∥ 3 } . (6) \min_{d\in\mathbb{R}^{n_k}}\left\{\langle g^k,d\rangle+\frac{1}{2}\langle(H^k+\eta I)d,d\rangle+\frac{\sigma_k}{6}\lVert d\rVert^3\right\}. \tag*{(6)} d ∈ R n k min { ⟨ g k , d ⟩ + 2 1 ⟨( H k + η I ) d , d ⟩ + 6 σ k ∥ d ∥ 3 } . (6)
Here, η > 0 \eta>0 η > 0 provides quadratic regularization, and σ k \sigma_k σ k is chosen using a bound on the local variation of the restricted Hessian, as specified in Algorithm 1.
To specify the required accuracy of the subspace step, define the first-order residual
r k : = g k + ( H k + η I ) d k + σ k 2 ∥ d k ∥ d k . r^k:=g^k+(H^k+\eta I)d^k+\frac{\sigma_k}{2}\lVert d^k\rVert d^k. r k := g k + ( H k + η I ) d k + 2 σ k ∥ d k ∥ d k .
We require d k d^k d k to satisfy
⟨ r k , d k ⟩ ≤ 0 , (7) \langle r^k,d^k\rangle\le0, \tag*{(7)} ⟨ r k , d k ⟩ ≤ 0 , (7)
⟨ ( H k + η I + σ k 2 ∥ d k ∥ I ) d k , d k ⟩ ≥ 0 , (8) \left\langle\left(H^k+\eta I+\frac{\sigma_k}{2}\lVert d^k\rVert I\right)d^k,d^k\right\rangle\ge0, \tag*{(8)} ⟨ ( H k + η I + 2 σ k ∥ d k ∥ I ) d k , d k ⟩ ≥ 0 , (8)
∥ r k ∥ ≤ κ g ∥ d k ∥ 2 , (9) \lVert r^k\rVert\le\kappa_g\lVert d^k\rVert^2, \tag*{(9)} ∥ r k ∥ ≤ κ g ∥ d k ∥ 2 , (9)
H k + η I + σ k 2 ∥ d k ∥ I ⪰ − κ H ∥ d k ∥ I , (10) H^k+\eta I+\frac{\sigma_k}{2}\lVert d^k\rVert I\succeq-\kappa_H\lVert d^k\rVert I, \tag*{(10)} H k + η I + 2 σ k ∥ d k ∥ I ⪰ − κ H ∥ d k ∥ I , (10)
where κ g , κ H ≥ 0 \kappa_g,\kappa_H\ge0 κ g , κ H ≥ 0 .
A global minimizer of (6) satisfies (3.3a)–(3.3d), with equality in (7) ; see [11 , 12 ] . Condition (9) bounds the first-order residual by the squared step norm, as in inexact regularization methods [5 ] . Condition (10) controls the negative curvature of the shifted Hessian. Conditions (3.3a)–(3.3b) are used to establish sufficient decrease in § 4 , whereas (3.3c)–(3.3d) are needed for the local complexity analysis in § 7 .
A backtracking line search along d k \mathbf{d}^{k} d k then determines y k \mathbf{y}^{k} y k , with all coordinates outside S k S^{k} S k fixed. The acceptance condition contains both quadratic and cubic decrease terms. If S k = ∅ S^{k} = \varnothing S k = ∅ , we set y k = x k \mathbf{y}^{k} = \mathbf{x}^{k} y k = x k . The complete method is given below.
Solving the Cubic Subproblem via a Restarted Lanczos Algorithm
Methods for solving cubic-regularization subproblems include Lanczos methods [11 , 19 ] , gradient descent [10 ] , first-order methods applied to convex reformulations [20 , 21 ] , generalized eigenvalue methods [29 ] , and methods based on approximate secular equations [15 ] . We use the symmetric Lanczos process in Jia et al. [19 Algorithm 1] , with the orthogonal continuation after exact breakdown described at the end of their § 4.1 . Their pseudocode stops at breakdown. If the target dimension has not been reached, we retain the existing basis Q i Q_i Q i and choose a unit vector q i + 1 ∈ ker ( Q i T ) \mathbf{q}_{i+1} \in\operatorname{ker}(Q_i^{\mathsf{T}}) q i + 1 ∈ ker ( Q i T ) to start a new Lanczos block. This is distinct from their nested restarting method in § 5 : we increase the target dimension until (3.3a)–(3.3d) hold.
For a symmetric A ∈ R N × N A \in\mathbb{R}^{N \times N} A ∈ R N × N , a unit vector q \mathbf{q} q , and 1 ≤ r ≤ N 1 \le r \le N 1 ≤ r ≤ N , let [ Q r , T r ] = Lanczos ( A , q , r ) [Q_r, T_r] = \operatorname{Lanczos}(A, \mathbf{q}, r) [ Q r , T r ] = Lanczos ( A , q , r ) denote this process continued until r r r basis vectors have been generated, i.e.,
Q r T Q r = I , T r = Q r T A Q r , Q_r^{\mathsf{T}} Q_r = I,\qquad T_r = Q_r^{\mathsf{T}} A Q_r, Q r T Q r = I , T r = Q r T A Q r ,
where T r T_r T r is symmetric and tridiagonal, with zero off-diagonal entries at block boundaries. Applying this procedure to A = H k + η I A = H^{k} + \eta I A = H k + η I and using d = Q r u \mathbf{d} = Q_r \mathbf{u} d = Q r u gives the reduced cubic problem
min u ∈ R r { ⟨ Q r T g k , u ⟩ + 1 2 u T T r u + σ k 6 ∥ u ∥ 3 } . (11) \min_{\mathbf{u}\in\mathbb{R}^{r}} \left\{ \langle Q_r^{\mathsf{T}}\mathbf{g}^{k},\mathbf{u}\rangle+ \frac{1}{2}\mathbf{u}^{\mathsf{T}}T_r\mathbf{u} + \frac{\sigma_k}{6}\lVert\mathbf{u}\rVert^{3} \right\}. \tag*{(11)} u ∈ R r min { ⟨ Q r T g k , u ⟩ + 2 1 u T T r u + 6 σ k ∥ u ∥ 3 } . (11)
Since ∥ Q r u ∥ = ∥ u ∥ \lVert Q_r\mathbf{u}\rVert= \lVert\mathbf{u}\rVert ∥ Q r u ∥ = ∥ u ∥ , this is precisely the restriction of (6) to Range ( Q r ) \operatorname{Range}(Q_r) Range ( Q r ) . Its objective is continuous and coercive, so a global minimizer exists.
Algorithm 2 solves the reduced problem and increases its dimension until the resulting step satisfies (3.3a)–(3.3d). The additional 1 in the dimension update ensures a strict increase before reaching n k n_k n k , even when s = 1 s = 1 s = 1 .
Theorem 3.1 In exact arithmetic, the Lanczos process described above generates r r r orthonormal vectors for every 1 ≤ r ≤ n k 1 \le r \le n_k 1 ≤ r ≤ n k . If every reduced cubic problem is solved globally, Algorithm 2 terminates after finitely many inner iterations.
Proof. Within each Lanczos block, the recurrence generates orthonormal vectors until breakdown. At breakdown, the accumulated subspace is invariant under
Algorithm 1 Hybrid proximal-gradient and subspace cubic-Newton method (HPG-SCN) for (1.1)
Require: x 0 = y 0 ∈ dom F x^0 = y^0 \in\operatorname{dom} F x 0 = y 0 ∈ dom F , 0 < α 0 < α ‾ < λ g 0 < \alpha_0 < \overline{\alpha} < \lambda_g 0 < α 0 < α < λ g , c , c 1 > 0 c, c_1 > 0 c , c 1 > 0 , η > 0 \eta> 0 η > 0 , q , q 1 ∈ ( 0 , 1 ) q, q_1 \in(0,1) q , q 1 ∈ ( 0 , 1 ) , ω > 1 \omega> 1 ω > 1 , ε k > 0 \varepsilon_k > 0 ε k > 0 , κ g , κ H ≥ 0 \kappa_g, \kappa_H \ge0 κ g , κ H ≥ 0 , MaxIt.
for k = 1 , 2 , … , M a x I t k = 1, 2, \ldots, \mathrm{MaxIt} k = 1 , 2 , … , MaxIt do
Proximal-gradient step.
Set α k , 0 \alpha_{k,0} α k , 0 according to (3.1).
for l k = 0 , 1 , 2 , … l_k = 0, 1, 2, \ldots l k = 0 , 1 , 2 , … do
Compute
x k , l k ∈ Prox α k , l k g ( y k − 1 − α k , l k ∇ h ( y k − 1 ) ) . x^{k,l_k} \in\operatorname{Prox}_{\alpha_{k,l_k} g}\left(y^{k-1} - \alpha_{k,l_k}\nabla h(y^{k-1})\right). x k , l k ∈ Prox α k , l k g ( y k − 1 − α k , l k ∇ h ( y k − 1 ) ) .
if F ( x k , l k ) ≤ F ( y k − 1 ) − c 1 ∥ x k , l k − y k − 1 ∥ 2 F(x^{k,l_k}) \le F(y^{k-1}) - c_1\lVert x^{k,l_k} - y^{k-1}\rVert^2 F ( x k , l k ) ≤ F ( y k − 1 ) − c 1 ∥ x k , l k − y k − 1 ∥ 2 then
Set x k = x k , l k x^k = x^{k,l_k} x k = x k , l k and α k = α k , l k \alpha_k = \alpha_{k,l_k} α k = α k , l k ; break .
else
Set α k , l k + 1 = q 1 α k , l k \alpha_{k,l_k+1} = q_1\alpha_{k,l_k} α k , l k + 1 = q 1 α k , l k .
end if
end for
Coordinate selection.
Set S k : = { i : ∣ x i k ∣ ≥ ε k } S^k := \{i : |x_i^k| \ge\varepsilon_k\} S k := { i : ∣ x i k ∣ ≥ ε k } and n k : = # ( S k ) n_k := \#(S^k) n k := # ( S k ) .
if S k ≠ ∅ S^k \ne\varnothing S k = ∅ then
Subspace cubic-Newton step.
Compute g k = ∇ S k F ( x k ) g^k = \nabla_{S^k} F(x^k) g k = ∇ S k F ( x k ) and H k = ∇ S k 2 F ( x k ) H^k = \nabla^2_{S^k} F(x^k) H k = ∇ S k 2 F ( x k ) .
Choose M ( x k ) > 0 M(x^k) > 0 M ( x k ) > 0 such that
M ( x k ) ≥ ω lip M x k ∇ S k 2 F ( x k ) . M(x^k) \ge\omega\operatorname{lip}_{M_{x^k}}\nabla^2_{S^k} F(x^k). M ( x k ) ≥ ω lip M x k ∇ S k 2 F ( x k ) .
Choose σ k ≥ 2 ( M ( x k ) + c ) / 3 \sigma_k \ge2(M(x^k) + c)/3 σ k ≥ 2 ( M ( x k ) + c ) /3 .
Compute an approximate solution d k d^k d k of (3.2) satisfying (3.3a)–(3.3d).
Backtracking line search.
Set β k , 0 = 1 \beta_{k,0} = 1 β k , 0 = 1 .
for j k = 0 , 1 , 2 , … j_k = 0, 1, 2, \ldots j k = 0 , 1 , 2 , … do
Define
y S k k , j k = x S k k + β k , j k d k , y ( S k ) c k , j k = x ( S k ) c k . y_{S^k}^{k,j_k} = x_{S^k}^k + \beta_{k,j_k}d^k,\qquad y_{(S^k)^c}^{k,j_k} = x_{(S^k)^c}^k. y S k k , j k = x S k k + β k , j k d k , y ( S k ) c k , j k = x ( S k ) c k .
if F ( y k , j k ) ≤ F ( x k ) − η 4 ∥ y k , j k − x k ∥ 2 − c 6 ∥ y k , j k − x k ∥ 3 F(y^{k,j_k}) \le F(x^k) - \frac{\eta}{4}\lVert y^{k,j_k} - x^k\rVert^2 - \frac{c}{6}\lVert y^{k,j_k} - x^k\rVert^3 F ( y k , j k ) ≤ F ( x k ) − 4 η ∥ y k , j k − x k ∥ 2 − 6 c ∥ y k , j k − x k ∥ 3 then
Set y k = y k , j k y^k = y^{k,j_k} y k = y k , j k and β k = β k , j k \beta_k = \beta_{k,j_k} β k = β k , j k ; break .
else
Set β k , j k + 1 = q β k , j k \beta_{k,j_k+1} = q\beta_{k,j_k} β k , j k + 1 = q β k , j k .
end if
end for
else
Set y k = x k y^k = x^k y k = x k .
end if
if the termination criterion is satisfied then
break .
end if
end for
Output: y k y^k y k .
Algorithm 2 A Lanczos method for solving (3.2)
Require: Integers n k ≥ 1 n_k \ge1 n k ≥ 1 and 1 ≤ r k , 0 ≤ n k 1 \le r_{k,0} \le n_k 1 ≤ r k , 0 ≤ n k , s ≥ 1 s \ge1 s ≥ 1 , g k ∈ R n k \boldsymbol{g}^k \in\mathbb{R}^{n_k} g k ∈ R n k , a symmetric H k ∈ R n k × n k H^k \in\mathbb{R}^{n_k \times n_k} H k ∈ R n k × n k , η , σ k > 0 \eta,\sigma_k > 0 η , σ k > 0 , and κ g , κ H ≥ 0 \kappa_g,\kappa_H \ge0 κ g , κ H ≥ 0 .
if g k ≠ 0 \boldsymbol{g}^k \ne0 g k = 0 then
Set q k = g k / ∥ g k ∥ \boldsymbol{q}^k = \boldsymbol{g}^k/\lVert\boldsymbol{g}^k\rVert q k = g k / ∥ g k ∥ .
else
Choose any unit vector q k ∈ R n k \boldsymbol{q}^k \in\mathbb{R}^{n_k} q k ∈ R n k .
end if
for j = 1 , 2 , … j = 1,2,\ldots j = 1 , 2 , … do
Set r k , j = min { ⌈ s r k , j − 1 ⌉ + 1 , n k } r_{k,j} = \min\{\lceil s r_{k,j-1}\rceil+ 1,n_k\} r k , j = min {⌈ s r k , j − 1 ⌉ + 1 , n k } .
Compute [ Q k , j , T k , j ] = Lanczos ( H k + η I , q k , r k , j ) [Q_{k,j},T_{k,j}] = \operatorname{Lanczos}(H^k+\eta I,\boldsymbol{q}^k,r_{k,j}) [ Q k , j , T k , j ] = Lanczos ( H k + η I , q k , r k , j ) .
Compute a global minimizer u k , j \boldsymbol{u}^{k,j} u k , j of (3.4) with ( r , Q r , T r ) = ( r k , j , Q k , j , T k , j ) (r,Q_r,T_r)=(r_{k,j},Q_{k,j},T_{k,j}) ( r , Q r , T r ) = ( r k , j , Q k , j , T k , j ) .
Set d k , j = Q k , j u k , j \boldsymbol{d}^{k,j}=Q_{k,j}\boldsymbol{u}^{k,j} d k , j = Q k , j u k , j and compute
r k , j = g k + ( H k + η I ) d k , j + σ k 2 ∥ d k , j ∥ d k , j . \boldsymbol{r}^{k,j}=\boldsymbol{g}^k+(H^k+\eta I)\boldsymbol{d}^{k,j}+\frac{\sigma_k}{2}\lVert\boldsymbol{d}^{k,j}\rVert\boldsymbol{d}^{k,j}. r k , j = g k + ( H k + η I ) d k , j + 2 σ k ∥ d k , j ∥ d k , j .
if conditions (3.3a)–(3.3d) hold for d k , j \boldsymbol{d}^{k,j} d k , j then
Set d k = d k , j \boldsymbol{d}^k=\boldsymbol{d}^{k,j} d k = d k , j .
return d k \boldsymbol{d}^k d k .
end if
end for
the symmetric matrix H k + η I H^k+\eta I H k + η I , so its orthogonal complement is also invariant. A unit vector in this complement exists whenever fewer than r ≤ n k r \le n_k r ≤ n k vectors have been generated, and starting a new block from it preserves orthogonality. Since s ≥ 1 s \ge1 s ≥ 1 , the dimension update reaches n k n_k n k after finitely many inner iterations unless a step is accepted earlier. At full dimension, Q k , j Q_{k,j} Q k , j is square and orthogonal, so the reduced problem is equivalent to (3.2). Its global minimizer has zero residual and satisfies (2.2); hence, all four acceptance conditions hold. □ \square □
Remark 3.2 An exact global minimizer of the reduced problem automatically satisfies (3.3a) and (3.3b). Let λ k , j : = σ k 2 ∥ d k , j ∥ \lambda_{k,j}:=\frac{\sigma_k}{2}\lVert\boldsymbol{d}^{k,j}\rVert λ k , j := 2 σ k ∥ d k , j ∥ , Proposition 2.5 gives
Q k , j T r k , j = 0 , T k , j + λ k , j I ⪰ 0. Q_{k,j}^{\mathsf{T}}\boldsymbol{r}^{k,j}=0,\qquad T_{k,j}+\lambda_{k,j}I\succeq0. Q k , j T r k , j = 0 , T k , j + λ k , j I ⪰ 0.
Since d k , j = Q k , j u k , j \boldsymbol{d}^{k,j}=Q_{k,j}\boldsymbol{u}^{k,j} d k , j = Q k , j u k , j , it follows that
⟨ r k , j , d k , j ⟩ = 0 , \langle\boldsymbol{r}^{k,j},\boldsymbol{d}^{k,j}\rangle=0, ⟨ r k , j , d k , j ⟩ = 0 ,
and
( d k , j ) T ( H k + η I + λ k , j I ) d k , j = ( u k , j ) T ( T k , j + λ k , j I ) u k , j ≥ 0. (\boldsymbol{d}^{k,j})^{\mathsf{T}}(H^k+\eta I+\lambda_{k,j}I)\boldsymbol{d}^{k,j}=(\boldsymbol{u}^{k,j})^{\mathsf{T}}(T_{k,j}+\lambda_{k,j}I)\boldsymbol{u}^{k,j}\ge0. ( d k , j ) T ( H k + η I + λ k , j I ) d k , j = ( u k , j ) T ( T k , j + λ k , j I ) u k , j ≥ 0.
Thus, only (3.3c) and (3.3d) require separate verification. Condition (3.3c) is checked using the full residual. A numerical certificate for (3.3d) can be obtained from a lower bound ℓ k ≤ λ min ( H k + η I ) \ell_k\le\lambda_{\min}(H^k+\eta I) ℓ k ≤ λ m i n ( H k + η I ) satisfying ℓ k + ( σ k / 2 + κ H ) ∥ d k , j ∥ ≥ 0 \ell_k+(\sigma_k/2+\kappa_H)\lVert\boldsymbol{d}^{k,j}\rVert\ge0 ℓ k + ( σ k /2 + κ H ) ∥ d k , j ∥ ≥ 0 .
Convergence Analysis
In this section, we establish the global convergence result of Algorithm 1.
Descent Property
We first show that the line search for the proximal-gradient step terminates after finitely many trials.
Theorem 4.1 Assume that F F F defined in (1) satisfies Assumption 1.1 and α k , 0 \alpha_{k,0} α k , 0 is chosen according to (5) . Then, the procedure of finding the smallest l k ∈ { 0 , 1 , 2 , … } l_k \in\{0,1,2,\ldots\} l k ∈ { 0 , 1 , 2 , … } such that
F ( x k , l k ) ≤ F ( y k − 1 ) − c 1 ∥ x k , l k − y k − 1 ∥ 2 (12) F(x^{k,l_k}) \leq F(y^{k-1}) - c_1\lVert x^{k,l_k} - y^{k-1}\rVert^2 \tag*{(12)} F ( x k , l k ) ≤ F ( y k − 1 ) − c 1 ∥ x k , l k − y k − 1 ∥ 2 (12) terminates after finitely many trials. Consequently, the proximal-gradient step in Algorithm 1 is well-defined. Moreover, the accepted step sizes satisfy 0 < α ‾ ≤ α k ≤ α ‾ 0 < \underline{\alpha} \leq\alpha_k \leq\overline{\alpha} 0 < α ≤ α k ≤ α (k ≥ 1 k \geq1 k ≥ 1 ) with α ‾ : = min { α 0 , q 1 L + 2 c 1 } > 0 \underline{\alpha} := \min\left\{\alpha_0,\frac{q_1}{L+2c_1}\right\} > 0 α := min { α 0 , L + 2 c 1 q 1 } > 0 .
Proof. By the bound 0 < α k , l k ≤ α k , 0 ≤ α ‾ < λ g 0 < \alpha_{k,l_k} \leq\alpha_{k,0} \leq\overline{\alpha} < \lambda_g 0 < α k , l k ≤ α k , 0 ≤ α < λ g and the definition of x k , l k x^{k,l_k} x k , l k , we have
g ( x k , l k ) + 1 2 α k , l k ∥ x k , l k − y k − 1 + α k , l k ∇ h ( y k − 1 ) ∥ 2 ≤ g ( y k − 1 ) + α k , l k 2 ∥ ∇ h ( y k − 1 ) ∥ 2 . g(x^{k,l_k}) + \frac{1}{2\alpha_{k,l_k}}\left\lVert x^{k,l_k} - y^{k-1} + \alpha_{k,l_k}\nabla h(y^{k-1})\right\rVert^2
\leq g(y^{k-1}) + \frac{\alpha_{k,l_k}}{2}\lVert\nabla h(y^{k-1})\rVert^2. g ( x k , l k ) + 2 α k , l k 1 x k , l k − y k − 1 + α k , l k ∇ h ( y k − 1 ) 2 ≤ g ( y k − 1 ) + 2 α k , l k ∥ ∇ h ( y k − 1 ) ∥ 2 .
Moreover, since ∇ h \nabla h ∇ h is L L L -Lipschitz continuous, the descent lemma gives
h ( x k , l k ) ≤ h ( y k − 1 ) + ⟨ ∇ h ( y k − 1 ) , x k , l k − y k − 1 ⟩ + L 2 ∥ x k , l k − y k − 1 ∥ 2 . h(x^{k,l_k}) \leq h(y^{k-1}) + \left\langle\nabla h(y^{k-1}),x^{k,l_k}-y^{k-1}\right\rangle+ \frac{L}{2}\lVert x^{k,l_k}-y^{k-1}\rVert^2. h ( x k , l k ) ≤ h ( y k − 1 ) + ⟨ ∇ h ( y k − 1 ) , x k , l k − y k − 1 ⟩ + 2 L ∥ x k , l k − y k − 1 ∥ 2 .
Combining the above two inequalities, we obtain
F ( x k , l k ) ≤ F ( y k − 1 ) − ( 1 2 α k , l k − L 2 ) ∥ x k , l k − y k − 1 ∥ 2 . F(x^{k,l_k}) \leq F(y^{k-1}) - \left(\frac{1}{2\alpha_{k,l_k}}-\frac{L}{2}\right)\lVert x^{k,l_k}-y^{k-1}\rVert^2. F ( x k , l k ) ≤ F ( y k − 1 ) − ( 2 α k , l k 1 − 2 L ) ∥ x k , l k − y k − 1 ∥ 2 .
Since α k , l k = q 1 l k α k , 0 \alpha_{k,l_k}=q_1^{l_k}\alpha_{k,0} α k , l k = q 1 l k α k , 0 and 0 < q 1 < 1 0<q_1<1 0 < q 1 < 1 , there exists a smallest finite index l ^ k \widehat{l}_k l k such that α k , l ^ k ≤ 1 / ( L + 2 c 1 ) \alpha_{k,\widehat{l}_k}\leq1/(L+2c_1) α k , l k ≤ 1/ ( L + 2 c 1 ) . Therefore, (12) holds for l k = l ^ k l_k=\widehat{l}_k l k = l k , and the proximal-gradient backtracking procedure terminates after finitely many trials. If l k = 0 l_k=0 l k = 0 , then α k = α k , 0 \alpha_k=\alpha_{k,0} α k = α k , 0 . By (5) , the initial trial is either α 0 \alpha_0 α 0 or, when the gradient difference is nonzero, at least min { 1 / L , α ‾ } \min\{1/L,\overline{\alpha}\} min { 1/ L , α } . In the latter case L > 0 L>0 L > 0 , and this minimum is at least α ‾ \underline{\alpha} α . If l k > 0 l_k>0 l k > 0 , the preceding trial was rejected, so α k , l k − 1 > 1 / ( L + 2 c 1 ) \alpha_{k,l_k-1}>1/(L+2c_1) α k , l k − 1 > 1/ ( L + 2 c 1 ) . Thus α k = q 1 α k , l k − 1 > q 1 / ( L + 2 c 1 ) ≥ α ‾ \alpha_k=q_1\alpha_{k,l_k-1}>q_1/(L+2c_1)\geq\underline{\alpha} α k = q 1 α k , l k − 1 > q 1 / ( L + 2 c 1 ) ≥ α . □ \square □
We next establish a descent estimate for subspace updates. The classical estimate in [33 Lemma 1] does not directly apply to our setting. The following lemma adapts it to restricted derivatives and subspace directions, with an additional term accounting for the Hessian variation error.
Lemma 4.2 Let x , d ∈ R n x,d\in\mathbb{R}^n x , d ∈ R n and M : = { z ∈ R n : supp ( z ) = supp ( x ) } \mathcal{M}:=\{z\in\mathbb{R}^n:\operatorname{supp}(z)=\operatorname{supp}(x)\} M := { z ∈ R n : supp ( z ) = supp ( x )} . Suppose supp ( d ) ⊆ supp ( x ) \operatorname{supp}(d)\subseteq\operatorname{supp}(x) supp ( d ) ⊆ supp ( x ) and supp ( x + t d ) = supp ( x ) \operatorname{supp}(x+td)=\operatorname{supp}(x) supp ( x + t d ) = supp ( x ) for all t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . Assume that the restriction of F F F to M \mathcal{M} M is finite and twice continuously differentiable in a relative neighborhood of the segment { x + t d : 0 ≤ t ≤ 1 } \{x+td:0\leq t\leq1\} { x + t d : 0 ≤ t ≤ 1 } . Assume S \mathcal{S} S is an
index set satisfying supp ( d ) ⊆ S ⊆ supp ( x ) \operatorname{supp}(\mathbf{d}) \subseteq S \subseteq\operatorname{supp}(\mathbf{x}) supp ( d ) ⊆ S ⊆ supp ( x ) and there exist constants M ≥ 0 M \ge0 M ≥ 0 and a ≥ 0 a \ge0 a ≥ 0 such that for all t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] , the function F F F satisfies
∥ ∇ S 2 F ( x + t d ) − ∇ S 2 F ( x ) ∥ ≤ M t ∥ d ∥ + a . (13) \left\lVert\nabla_S^2 F(\mathbf{x}+t\mathbf{d})-\nabla_S^2 F(\mathbf{x})\right\rVert\le M t\lVert\mathbf{d}\rVert+ a. \tag*{(13)} ∇ S 2 F ( x + t d ) − ∇ S 2 F ( x ) ≤ M t ∥ d ∥ + a . (13)
Then, for all t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] , it holds that
∥ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S ∥ ≤ a t ∥ d ∥ + M 2 t 2 ∥ d ∥ 2 , (14) \left\lVert\nabla_S F(\mathbf{x}+t\mathbf{d})-\nabla_S F(\mathbf{x})-t\nabla_S^2 F(\mathbf{x})\mathbf{d}_S\right\rVert\le a t\lVert\mathbf{d}\rVert+\frac{M}{2}t^2\lVert\mathbf{d}\rVert^2, \tag*{(14)} ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S ≤ a t ∥ d ∥ + 2 M t 2 ∥ d ∥ 2 , (14)
where d S ∈ R ♯ ( S ) \mathbf{d}_S \in\mathbb{R}^{\sharp(S)} d S ∈ R ♯ ( S ) denotes the subvector of d \mathbf{d} d consisting of the components indexed by S S S .
Moreover,
F ( x + d ) ≤ F ( x ) + ⟨ ∇ S F ( x ) , d S ⟩ + 1 2 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + a 2 ∥ d ∥ 2 + M 6 ∥ d ∥ 3 . (15) F(\mathbf{x}+\mathbf{d}) \le F(\mathbf{x})+\langle\nabla_S F(\mathbf{x}),\mathbf{d}_S\rangle+\frac{1}{2}\langle\nabla_S^2 F(\mathbf{x})\mathbf{d}_S,\mathbf{d}_S\rangle+\frac{a}{2}\lVert\mathbf{d}\rVert^2+\frac{M}{6}\lVert\mathbf{d}\rVert^3. \tag*{(15)} F ( x + d ) ≤ F ( x ) + ⟨ ∇ S F ( x ) , d S ⟩ + 2 1 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + 2 a ∥ d ∥ 2 + 6 M ∥ d ∥ 3 . (15)
Proof For t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] , define ψ ( t ) : = ∇ S F ( x + t d ) ∈ R ♯ ( S ) \psi(t):=\nabla_S F(\mathbf{x}+t\mathbf{d})\in\mathbb{R}^{\sharp(S)} ψ ( t ) := ∇ S F ( x + t d ) ∈ R ♯ ( S ) . Since supp ( x + t d ) = supp ( x ) \operatorname{supp}(\mathbf{x}+t\mathbf{d})=\operatorname{supp}(\mathbf{x}) supp ( x + t d ) = supp ( x ) for all t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , supp ( d ) ⊆ S ⊆ supp ( x ) \operatorname{supp}(\mathbf{d})\subseteq S\subseteq\operatorname{supp}(\mathbf{x}) supp ( d ) ⊆ S ⊆ supp ( x ) and (4.2) holds for t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , ψ \psi ψ is differentiable on [ 0 , 1 ] [0,1] [ 0 , 1 ] , with
ψ ′ ( t ) = ∇ S 2 F ( x + t d ) d S , t ∈ [ 0 , 1 ] . \psi'(t)=\nabla_S^2F(\mathbf{x}+t\mathbf{d})\mathbf{d}_S,\qquad t\in[0,1]. ψ ′ ( t ) = ∇ S 2 F ( x + t d ) d S , t ∈ [ 0 , 1 ] .
Then, we obtain
ψ ( t ) − ψ ( 0 ) − t ψ ′ ( 0 ) = ∫ 0 t ( ψ ′ ( u ) − ψ ′ ( 0 ) ) d u = ∫ 0 t ( ∇ S 2 F ( x + u d ) − ∇ S 2 F ( x ) ) d S d u . \begin{aligned}
\psi(t)-\psi(0)-t\psi'(0)
&=\int_0^t\left(\psi'(u)-\psi'(0)\right)\,du\\
&=\int_0^t\left(\nabla_S^2F(\mathbf{x}+u\mathbf{d})-\nabla_S^2F(\mathbf{x})\right)\mathbf{d}_S\,du.
\end{aligned} ψ ( t ) − ψ ( 0 ) − t ψ ′ ( 0 ) = ∫ 0 t ( ψ ′ ( u ) − ψ ′ ( 0 ) ) d u = ∫ 0 t ( ∇ S 2 F ( x + u d ) − ∇ S 2 F ( x ) ) d S d u .
Taking norms and using ∥ d S ∥ = ∥ d ∥ \lVert\mathbf{d}_S\rVert=\lVert\mathbf{d}\rVert ∥ d S ∥ = ∥ d ∥ , together with (4.2), yields
∥ ψ ( t ) − ψ ( 0 ) − t ψ ′ ( 0 ) ∥ ≤ ∫ 0 t ∥ ∇ S 2 F ( x + u d ) − ∇ S 2 F ( x ) ∥ ∥ d ∥ d u ≤ ∫ 0 t ( M u ∥ d ∥ + a ) ∥ d ∥ d u = a t ∥ d ∥ + M 2 t 2 ∥ d ∥ 2 , \begin{aligned}
\left\lVert\psi(t)-\psi(0)-t\psi'(0)\right\rVert
&\le\int_0^t\left\lVert\nabla_S^2F(\mathbf{x}+u\mathbf{d})-\nabla_S^2F(\mathbf{x})\right\rVert\lVert\mathbf{d}\rVert\,du\\
&\le\int_0^t\left(Mu\lVert\mathbf{d}\rVert+a\right)\lVert\mathbf{d}\rVert\,du
=a t\lVert\mathbf{d}\rVert+\frac{M}{2}t^2\lVert\mathbf{d}\rVert^2,
\end{aligned} ∥ ψ ( t ) − ψ ( 0 ) − t ψ ′ ( 0 ) ∥ ≤ ∫ 0 t ∇ S 2 F ( x + u d ) − ∇ S 2 F ( x ) ∥ d ∥ d u ≤ ∫ 0 t ( M u ∥ d ∥ + a ) ∥ d ∥ d u = a t ∥ d ∥ + 2 M t 2 ∥ d ∥ 2 ,
which proves (4.3). Next, define ϕ ( t ) = F ( x + t d ) \phi(t)=F(x+td) ϕ ( t ) = F ( x + t d ) . Then, ϕ \phi ϕ is differentiable on [ 0 , 1 ] [0,1] [ 0 , 1 ] and satisfies ϕ ′ ( t ) = ⟨ ∇ S F ( x + t d ) , d S ⟩ \phi'(t)=\langle\nabla_S F(x+td),d_S\rangle ϕ ′ ( t ) = ⟨ ∇ S F ( x + t d ) , d S ⟩ . Consequently,
F ( x + d ) − F ( x ) − ⟨ ∇ S F ( x ) , d S ⟩ = ϕ ( 1 ) − ϕ ( 0 ) − ϕ ′ ( 0 ) = ∫ 0 1 ( ϕ ′ ( t ) − ϕ ′ ( 0 ) ) d t = ∫ 0 1 ⟨ ∇ S F ( x + t d ) − ∇ S F ( x ) , d S ⟩ d t = ∫ 0 1 ⟨ t ∇ S 2 F ( x ) d S , d S ⟩ d t + ∫ 0 1 ⟨ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S , d S ⟩ d t ≤ 1 2 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + ∫ 0 1 ∣ ⟨ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S , d S ⟩ ∣ d t ≤ 1 2 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + ∫ 0 1 ∥ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S ∥ ∥ d S ∥ d t ≤ 1 2 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + ∫ 0 1 ( a t ∥ d ∥ + M 2 t 2 ∥ d ∥ 2 ) ∥ d ∥ d t = 1 2 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + a 2 ∥ d ∥ 2 + M 6 ∥ d ∥ 3 . \begin{aligned}
F(x+d)-F(x)-\langle\nabla_S F(x),d_S\rangle
&=\phi(1)-\phi(0)-\phi'(0)\\
&=\int_0^1(\phi'(t)-\phi'(0))\,dt\\
&=\int_0^1\langle\nabla_S F(x+td)-\nabla_S F(x),d_S\rangle\,dt\\
&=\int_0^1\langle t\nabla_S^2F(x)d_S,d_S\rangle\,dt\\
&\quad+\int_0^1\langle\nabla_SF(x+td)-\nabla_SF(x)-t\nabla_S^2F(x)d_S,d_S\rangle\,dt\\
&\le\frac{1}{2}\langle\nabla_S^2F(x)d_S,d_S\rangle\\
&\quad+\int_0^1\left|\langle\nabla_SF(x+td)-\nabla_SF(x)-t\nabla_S^2F(x)d_S,d_S\rangle\right|\,dt\\
&\le\frac{1}{2}\langle\nabla_S^2F(x)d_S,d_S\rangle\\
&\quad+\int_0^1\|\nabla_SF(x+td)-\nabla_SF(x)-t\nabla_S^2F(x)d_S\|\,\|d_S\|\,dt\\
&\le\frac{1}{2}\langle\nabla_S^2F(x)d_S,d_S\rangle+\int_0^1\left(a\,t\|d\|+\frac{M}{2}t^2\|d\|^2\right)\|d\|\,dt\\
&=\frac{1}{2}\langle\nabla_S^2F(x)d_S,d_S\rangle+\frac{a}{2}\|d\|^2+\frac{M}{6}\|d\|^3.
\end{aligned} F ( x + d ) − F ( x ) − ⟨ ∇ S F ( x ) , d S ⟩ = ϕ ( 1 ) − ϕ ( 0 ) − ϕ ′ ( 0 ) = ∫ 0 1 ( ϕ ′ ( t ) − ϕ ′ ( 0 )) d t = ∫ 0 1 ⟨ ∇ S F ( x + t d ) − ∇ S F ( x ) , d S ⟩ d t = ∫ 0 1 ⟨ t ∇ S 2 F ( x ) d S , d S ⟩ d t + ∫ 0 1 ⟨ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S , d S ⟩ d t ≤ 2 1 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + ∫ 0 1 ⟨ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S , d S ⟩ d t ≤ 2 1 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + ∫ 0 1 ∥ ∇ S F ( x + t d ) − ∇ S F ( x ) − t ∇ S 2 F ( x ) d S ∥ ∥ d S ∥ d t ≤ 2 1 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + ∫ 0 1 ( a t ∥ d ∥ + 2 M t 2 ∥ d ∥ 2 ) ∥ d ∥ d t = 2 1 ⟨ ∇ S 2 F ( x ) d S , d S ⟩ + 2 a ∥ d ∥ 2 + 6 M ∥ d ∥ 3 .
Combining the above estimates establishes (4.4) and completes the proof. □ \square □
The following theorem establishes the finite termination of the line search for β k \beta_k β k and the descent property.
Theorem 4.3 Assume that F F F defined in (1.1) satisfies Assumption 1.1. Assume also that M ( x k ) > 0 M(x^k)>0 M ( x k ) > 0 and
M ( x k ) ≥ ω lip M x k ∇ S 2 F ( x k ) , ω > 1. M(x^k)\ge\omega\operatorname{lip}_{M_{x^k}}\nabla_S^2F(x^k),\qquad\omega>1. M ( x k ) ≥ ω lip M x k ∇ S 2 F ( x k ) , ω > 1. At iteration k k k , suppose that S k ≠ ∅ S^k\ne\varnothing S k = ∅ and c > 0 c>0 c > 0 . Let d k d^k d k be an inexact solution of the cubic subproblem satisfying Conditions (3.3a) and (3.3b). Assume that
σ k ≥ 2 ( M ( x k ) + c ) 3 . (16) \sigma_k\ge\frac{2(M(x^k)+c)}{3}. \tag*{(16)} σ k ≥ 3 2 ( M ( x k ) + c ) . (16) Then, the procedure of finding the smallest j k ∈ N j_k\in\mathbb{N} j k ∈ N such that
F ( y k , j k ) ≤ F ( x k ) − η 2 ∥ y k , j k − x k ∥ 2 − c 6 ∥ y k , j k − x k ∥ 3 (17) F(y^{k,j_k})\le F(x^k)-\frac{\eta}{2}\|y^{k,j_k}-x^k\|^2-\frac{c}{6}\|y^{k,j_k}-x^k\|^3 \tag*{(17)} F ( y k , j k ) ≤ F ( x k ) − 2 η ∥ y k , j k − x k ∥ 2 − 6 c ∥ y k , j k − x k ∥ 3 (17) terminates after finitely many trials.
Proof. Let d ^ k ∈ R n \widehat{d}^k \in\mathbb{R}^n d k ∈ R n be the zero extension of d k d^k d k , so ∥ d ^ k ∥ = ∥ d k ∥ \|\widehat{d}^k\| = \|d^k\| ∥ d k ∥ = ∥ d k ∥ . Since M ( x k ) > lip M x k ∇ S k 2 F ( x k ) M(x^k) > \operatorname{lip}_{\mathcal{M}_{x^k}} \nabla^2_{S^k} F(x^k) M ( x k ) > lip M x k ∇ S k 2 F ( x k ) , strict continuity supplies δ k > 0 \delta_k > 0 δ k > 0 such that
∥ ∇ S k 2 F ( z ) − ∇ S k 2 F ( x k ) ∥ ≤ M ( x k ) ∥ z − x k ∥ for z ∈ B ( x k , δ k ) ∩ M x k . \left\|\nabla^2_{S^k} F(z) - \nabla^2_{S^k} F(x^k)\right\| \le M(x^k)\|z-x^k\| \quad\text{for } z \in\mathcal{B}(x^k,\delta_k) \cap\mathcal{M}_{x^k}. ∇ S k 2 F ( z ) − ∇ S k 2 F ( x k ) ≤ M ( x k ) ∥ z − x k ∥ for z ∈ B ( x k , δ k ) ∩ M x k .
Because S k ⊆ supp ( x k ) S^k \subseteq\operatorname{supp}(x^k) S k ⊆ supp ( x k ) , there is β ^ k ∈ ( 0 , 1 ] \widehat{\beta}_k \in(0,1] β k ∈ ( 0 , 1 ] such that x k + t β d ^ k ∈ B ( x k , δ k ) ∩ M x k x^k+t\beta\widehat{d}^k \in\mathcal{B}(x^k,\delta_k) \cap\mathcal{M}_{x^k} x k + tβ d k ∈ B ( x k , δ k ) ∩ M x k for all t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] and 0 < β ≤ β ^ k 0 < \beta\le\widehat{\beta}_k 0 < β ≤ β k . Lemma 4.2, with a = 0 a=0 a = 0 , therefore gives
F ( x k + β d ^ k ) ≤ F ( x k ) + β ⟨ g k , d k ⟩ + β 2 2 ⟨ H k d k , d k ⟩ + M ( x k ) β 3 6 ∥ d k ∥ 3 . (18) F(x^k+\beta\widehat{d}^k) \le F(x^k)+\beta\langle g^k,d^k\rangle+\frac{\beta^2}{2}\langle H^k d^k,d^k\rangle+\frac{M(x^k)\beta^3}{6}\|d^k\|^3. \tag*{(18)} F ( x k + β d k ) ≤ F ( x k ) + β ⟨ g k , d k ⟩ + 2 β 2 ⟨ H k d k , d k ⟩ + 6 M ( x k ) β 3 ∥ d k ∥ 3 . (18)
Recall that r k = g k + ( H k + η I ) d k + σ k 2 ∥ d k ∥ d k r^k=g^k+(H^k+\eta I)d^k+\frac{\sigma_k}{2}\|d^k\|d^k r k = g k + ( H k + η I ) d k + 2 σ k ∥ d k ∥ d k . By Condition (3.3a) we have ⟨ r k , d k ⟩ ≤ 0 \langle r^k,d^k\rangle\le0 ⟨ r k , d k ⟩ ≤ 0 , and hence
⟨ g k , d k ⟩ ≤ − ⟨ ( H k + η I ) d k , d k ⟩ − σ k 2 ∥ d k ∥ 3 . \langle g^k,d^k\rangle\le-\langle(H^k+\eta I)d^k,d^k\rangle-\frac{\sigma_k}{2}\|d^k\|^3. ⟨ g k , d k ⟩ ≤ − ⟨( H k + η I ) d k , d k ⟩ − 2 σ k ∥ d k ∥ 3 .
Moreover, Condition (3.3b) gives
⟨ H k d k , d k ⟩ ≥ − η ∥ d k ∥ 2 − σ k 2 ∥ d k ∥ 3 . \langle H^k d^k,d^k\rangle\ge-\eta\|d^k\|^2-\frac{\sigma_k}{2}\|d^k\|^3. ⟨ H k d k , d k ⟩ ≥ − η ∥ d k ∥ 2 − 2 σ k ∥ d k ∥ 3 .
Substituting the above two inequalities into (4.7), we obtain
F ( x k + β d ^ k ) ≤ F ( x k ) − η β ∥ d k ∥ 2 − σ k β 2 ∥ d k ∥ 3 + ( − β + β 2 2 ) ⟨ H k d k , d k ⟩ + M ( x k ) β 3 6 ∥ d k ∥ 3 ≤ F ( x k ) − η β 2 2 ∥ d k ∥ 2 − ( σ k β 2 4 − M ( x k ) β 3 6 ) ∥ d k ∥ 3 . \begin{aligned}
F(x^k+\beta\widehat{d}^k)
&\le F(x^k)-\eta\beta\|d^k\|^2-\frac{\sigma_k\beta}{2}\|d^k\|^3 \\
&\quad+\left(-\beta+\frac{\beta^2}{2}\right)\langle H^k d^k,d^k\rangle+\frac{M(x^k)\beta^3}{6}\|d^k\|^3 \\
&\le F(x^k)-\frac{\eta\beta^2}{2}\|d^k\|^2-\left(\frac{\sigma_k\beta^2}{4}-\frac{M(x^k)\beta^3}{6}\right)\|d^k\|^3.
\end{aligned} F ( x k + β d k ) ≤ F ( x k ) − η β ∥ d k ∥ 2 − 2 σ k β ∥ d k ∥ 3 + ( − β + 2 β 2 ) ⟨ H k d k , d k ⟩ + 6 M ( x k ) β 3 ∥ d k ∥ 3 ≤ F ( x k ) − 2 η β 2 ∥ d k ∥ 2 − ( 4 σ k β 2 − 6 M ( x k ) β 3 ) ∥ d k ∥ 3 .
By (4.5) and β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] , we have
σ k β 2 4 − M ( x k ) β 3 6 ≥ β 3 6 ( 3 σ k 2 − M ( x k ) ) ≥ c β 3 6 . \frac{\sigma_k\beta^2}{4}-\frac{M(x^k)\beta^3}{6}\ge\frac{\beta^3}{6}\left(\frac{3\sigma_k}{2}-M(x^k)\right)\ge\frac{c\beta^3}{6}. 4 σ k β 2 − 6 M ( x k ) β 3 ≥ 6 β 3 ( 2 3 σ k − M ( x k ) ) ≥ 6 c β 3 .
Therefore, for every β ∈ ( 0 , β ^ k ] \beta\in(0,\widehat{\beta}_k] β ∈ ( 0 , β k ] , it holds that
F ( x k + β d ^ k ) ≤ F ( x k ) − η β 2 2 ∥ d k ∥ 2 − c β 3 6 ∥ d k ∥ 3 . F(x^k+\beta\widehat{d}^k)\le F(x^k)-\frac{\eta\beta^2}{2}\|d^k\|^2-\frac{c\beta^3}{6}\|d^k\|^3. F ( x k + β d k ) ≤ F ( x k ) − 2 η β 2 ∥ d k ∥ 2 − 6 c β 3 ∥ d k ∥ 3 .
Since y k , j k = x k + β k , j k d ^ k y^{k,j_k}=x^k+\beta_{k,j_k}\widehat{d}^k y k , j k = x k + β k , j k d k and β k , j k + 1 = β k , j k q \beta_{k,j_k+1}=\beta_{k,j_k}q β k , j k + 1 = β k , j k q , there exists a finite j ^ k \widehat{j}_k j k such that (4.6) holds for j k = j ^ k j_k=\widehat{j}_k j k = j k . The test in Algorithm 1 uses the smaller quadratic coefficient η / 4 \eta/4 η /4 , so it also terminates after finitely many trials. ■ \quad\blacksquare ■
The following theorem establishes sufficient decrease at each outer iteration.
Theorem 4.4 Suppose Assumption 1.1 holds. Let the sequences { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be generated by Algorithm 1. Let x 0 = y 0 x^0=y^0 x 0 = y 0 . If σ k \sigma_k σ k satisfies (4.5), then there exists a constant C ~ > 0 \widetilde{C}>0 C > 0 such that the following property holds for k ≥ 1 k\ge1 k ≥ 1 :
F ( x k ) ≤ F ( x k − 1 ) − C ~ ∥ x k − y k − 1 ∥ 2 − C ~ ∥ x k − 1 − y k − 1 ∥ 2 . (19) F(x^k) \le F(x^{k-1})-\widetilde{C}\lVert x^k-y^{k-1}\rVert^2-\widetilde{C}\lVert x^{k-1}-y^{k-1}\rVert^2. \tag*{(19)} F ( x k ) ≤ F ( x k − 1 ) − C ∥ x k − y k − 1 ∥ 2 − C ∥ x k − 1 − y k − 1 ∥ 2 . (19) Consequently,
lim k → ∞ ∥ x k − x k − 1 ∥ = lim k → ∞ ∥ x k − y k − 1 ∥ = lim k → ∞ ∥ x k − 1 − y k − 1 ∥ = 0. (20) \lim_{k\to\infty}\lVert x^k-x^{k-1}\rVert=\lim_{k\to\infty}\lVert x^k-y^{k-1}\rVert=\lim_{k\to\infty}\lVert x^{k-1}-y^{k-1}\rVert=0. \tag*{(20)} k → ∞ lim ∥ x k − x k − 1 ∥ = k → ∞ lim ∥ x k − y k − 1 ∥ = k → ∞ lim ∥ x k − 1 − y k − 1 ∥ = 0. (20) Furthermore, there exists a constant F ^ \widehat{F} F such that lim k → ∞ F ( x k ) = F ^ \lim_{k\to\infty}F(x^k)=\widehat{F} lim k → ∞ F ( x k ) = F .
Proof From Theorem 4.1, we have
F ( x k ) ≤ F ( y k − 1 ) − c 1 ∥ x k − y k − 1 ∥ 2 . (21) F(x^k)\le F(y^{k-1})-c_1\lVert x^k-y^{k-1}\rVert^2. \tag*{(21)} F ( x k ) ≤ F ( y k − 1 ) − c 1 ∥ x k − y k − 1 ∥ 2 . (21)
For k = 1 k=1 k = 1 , inequality (4.10) and x 0 = y 0 x^0=y^0 x 0 = y 0 directly give (4.8). For k ≥ 2 k\ge2 k ≥ 2 , we consider two cases: (a) S k − 1 ≠ ∅ S^{k-1}\ne\emptyset S k − 1 = ∅ and (b) S k − 1 = ∅ S^{k-1}=\emptyset S k − 1 = ∅ .
In case (a), the cubic line search gives F ( y k − 1 ) ≤ F ( x k − 1 ) − η 4 ∥ y k − 1 − x k − 1 ∥ 2 − c 6 ∥ y k − 1 − x k − 1 ∥ 3 F(y^{k-1})\le F(x^{k-1})-\frac{\eta}{4}\lVert y^{k-1}-x^{k-1}\rVert^2-\frac{c}{6}\lVert y^{k-1}-x^{k-1}\rVert^3 F ( y k − 1 ) ≤ F ( x k − 1 ) − 4 η ∥ y k − 1 − x k − 1 ∥ 2 − 6 c ∥ y k − 1 − x k − 1 ∥ 3 . Combining this inequality with (4.10), we obtain
F ( x k ) ≤ F ( x k − 1 ) − c 1 ∥ x k − y k − 1 ∥ 2 − c 6 ∥ x k − 1 − y k − 1 ∥ 3 − η 4 ∥ x k − 1 − y k − 1 ∥ 2 ≤ F ( x k − 1 ) − c 1 ∥ x k − y k − 1 ∥ 2 − η 4 ∥ x k − 1 − y k − 1 ∥ 2 . \begin{aligned}
F(x^k)\le F(x^{k-1})-c_1\lVert x^k-y^{k-1}\rVert^2-\frac{c}{6}\lVert x^{k-1}-y^{k-1}\rVert^3-\frac{\eta}{4}\lVert x^{k-1}-y^{k-1}\rVert^2 \\
&\le F(x^{k-1})-c_1\lVert x^k-y^{k-1}\rVert^2-\frac{\eta}{4}\lVert x^{k-1}-y^{k-1}\rVert^2.
\end{aligned} F ( x k ) ≤ F ( x k − 1 ) − c 1 ∥ x k − y k − 1 ∥ 2 − 6 c ∥ x k − 1 − y k − 1 ∥ 3 − 4 η ∥ x k − 1 − y k − 1 ∥ 2 ≤ F ( x k − 1 ) − c 1 ∥ x k − y k − 1 ∥ 2 − 4 η ∥ x k − 1 − y k − 1 ∥ 2 .
Let C ~ : = min { c 1 , η 4 } \widetilde{C}:=\min\{c_1,\frac{\eta}{4}\} C := min { c 1 , 4 η } . Then (4.8) follows. Case (b). It leads to y k − 1 = x k − 1 y^{k-1}=x^{k-1} y k − 1 = x k − 1 . (4.8) also holds. Rearranging (4.8) and summing the resulting inequalities yields
C ~ ∑ k = 1 ∞ ( ∥ x k − y k − 1 ∥ 2 + ∥ x k − 1 − y k − 1 ∥ 2 ) ≤ F ( x 0 ) − F ^ < ∞ . \widetilde{C}\sum_{k=1}^{\infty}\left(\lVert x^k-y^{k-1}\rVert^2+\lVert x^{k-1}-y^{k-1}\rVert^2\right)\le F(x^0)-\widehat{F}<\infty. C k = 1 ∑ ∞ ( ∥ x k − y k − 1 ∥ 2 + ∥ x k − 1 − y k − 1 ∥ 2 ) ≤ F ( x 0 ) − F < ∞.
Hence, (4.9) holds. Since { F ( x k ) } \{F(x^k)\} { F ( x k )} is nonincreasing and bounded below, there exists a constant F ^ \widehat{F} F such that lim k → ∞ F ( x k ) = F ^ \lim_{k\to\infty}F(x^k)=\widehat{F} lim k → ∞ F ( x k ) = F . □ \square □
Global Convergence
We assume boundedness to prove convergence of the entire sequence.
Assumption 4.5 The sequence { x k } \{x^k\} { x k } generated from Algorithm 1 is bounded.
Coercivity of F F F implies Assumption 4.5. Appendix B gives boundedness conditions for the ratio-regularized least-squares and regularized logistic models.
Lemma 4.6 Suppose that Assumptions 1.1 and 4.5 hold. Let { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be generated from Algorithm 1. Let x 0 = y 0 x^0=y^0 x 0 = y 0 . Let X \mathcal{X} X denote the set of accumulation points of { x k } \{x^k\} { x k } . If σ k \sigma_k σ k satisfies (4.5), then the following assertions hold:
(i) The sequence { y k } \{y^k\} { y k } is bounded and admits the same set of accumulation points X \mathcal{X} X .
(ii) F ( x ‾ ) = F ^ F(\overline{x})=\widehat{F} F ( x ) = F for all x ‾ ∈ X \overline{x}\in\mathcal{X} x ∈ X , where F ^ \widehat{F} F is defined in Theorem 4.4 .
(iii) Every accumulation point x ‾ \overline{x} x of { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } is a critical point of problem (1.1), i.e.,
0 ∈ ∂ g ( x ‾ ) + ∇ h ( x ‾ ) . (22) 0\in\partial g(\overline{x})+\nabla h(\overline{x}). \tag*{(22)} 0 ∈ ∂ g ( x ) + ∇ h ( x ) . (22)
Proof. By (4.9), ∥ x k − y k ∥ → 0 \lVert x^k-y^k\rVert\to0 ∥ x k − y k ∥ → 0 , which implies that { y k } \{y^k\} { y k } is bounded and shares the same accumulation points as { x k } \{x^k\} { x k } . This establishes (i). To prove (ii), let x k j → x ‾ x^{k_j}\to\overline{x} x k j → x be any convergent subsequence. By (4.9), we also have y k j − 1 → x ‾ y^{k_j-1}\to\overline{x} y k j − 1 → x . The lower semicontinuity of F F F then yields F ( x ‾ ) ≤ F ^ < + ∞ F(\overline{x})\le\widehat{F}<+\infty F ( x ) ≤ F < + ∞ . Setting z j : = y k j − 1 − α k j ∇ h ( y k j − 1 ) z^j:=y^{k_j-1}-\alpha_{k_j}\nabla h(y^{k_j-1}) z j := y k j − 1 − α k j ∇ h ( y k j − 1 ) , we have
g ( x k j ) + 1 2 α k j ∥ x k j − z j ∥ 2 ≤ g ( x ‾ ) + 1 2 α k j ∥ x ‾ − z j ∥ 2 . g(x^{k_j})+\frac{1}{2\alpha_{k_j}}\lVert x^{k_j}-z^j\rVert^2\le g(\overline{x})+\frac{1}{2\alpha_{k_j}}\lVert\overline{x}-z^j\rVert^2. g ( x k j ) + 2 α k j 1 ∥ x k j − z j ∥ 2 ≤ g ( x ) + 2 α k j 1 ∥ x − z j ∥ 2 .
Since { z j } \{z^j\} { z j } is bounded,
∥ x k j − z j ∥ 2 − ∥ x ‾ − z j ∥ 2 ≤ ∥ x k j − x ‾ ∥ ( ∥ x k j − z j ∥ + ∥ x ‾ − z j ∥ ) → 0. \lVert x^{k_j}-z^j\rVert^2-\lVert\overline{x}-z^j\rVert^2\le\lVert x^{k_j}-\overline{x}\rVert\bigl(\lVert x^{k_j}-z^j\rVert+\lVert\overline{x}-z^j\rVert\bigr)\to0. ∥ x k j − z j ∥ 2 − ∥ x − z j ∥ 2 ≤ ∥ x k j − x ∥ ( ∥ x k j − z j ∥ + ∥ x − z j ∥ ) → 0.
Since α k j ≥ α > 0 \alpha_{k_j}\ge\alpha>0 α k j ≥ α > 0 , we obtain lim sup j → ∞ g ( x k j ) ≤ g ( x ‾ ) \limsup_{j\to\infty}g(x^{k_j})\le g(\overline{x}) lim sup j → ∞ g ( x k j ) ≤ g ( x ) . By the continuity of h h h , it follows that F ^ ≤ F ( x ‾ ) \widehat{F}\le F(\overline{x}) F ≤ F ( x ) . Consequently, F ( x ‾ ) = F ^ F(\overline{x})=\widehat{F} F ( x ) = F , which completes the proof of (ii). Finally, the proximal optimality condition implies
v k : = y k − 1 − x k α k + ∇ h ( x k ) − ∇ h ( y k − 1 ) ∈ ∂ F ( x k ) , v^k:=\frac{y^{k-1}-x^k}{\alpha_k}+\nabla h(x^k)-\nabla h(y^{k-1})\in\partial F(x^k), v k := α k y k − 1 − x k + ∇ h ( x k ) − ∇ h ( y k − 1 ) ∈ ∂ F ( x k ) ,
∥ v k ∥ ≤ ( α k − 1 + L ) ∥ x k − y k − 1 ∥ . (23) \lVert v^k\rVert\le(\alpha_k^{-1}+L)\lVert x^k-y^{k-1}\rVert. \tag*{(23)} ∥ v k ∥ ≤ ( α k − 1 + L ) ∥ x k − y k − 1 ∥ . (23)
Along the above subsequence, v k j → 0 v^{k_j}\to0 v k j → 0 and F ( x k j ) → F ( x ‾ ) F(x^{k_j})\to F(\overline{x}) F ( x k j ) → F ( x ) . The defining closedness property of the limiting subdifferential gives 0 ∈ ∂ F ( x ‾ ) = ∂ g ( x ‾ ) + ∇ h ( x ‾ ) 0\in\partial F(\overline{x})=\partial g(\overline{x})+\nabla h(\overline{x}) 0 ∈ ∂ F ( x ) = ∂ g ( x ) + ∇ h ( x ) , proving (iii). □ \square □
The following lemma is a direct consequence of (4.12).
Lemma 4.7 Suppose that Assumptions 1.1 and 4.5 hold. Let { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be generated from Algorithm 1. If σ k \sigma_k σ k satisfies (4.5), then the following holds:
dist ( 0 , ∂ F ( x k ) ) ≤ ( 1 α k + L ) ∥ x k − y k − 1 ∥ \operatorname{dist}(0,\partial F(x^k))\le\left(\frac{1}{\alpha_k}+L\right)\lVert x^k-y^{k-1}\rVert dist ( 0 , ∂ F ( x k )) ≤ ( α k 1 + L ) ∥ x k − y k − 1 ∥ ≤ ( 1 α + L ) ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) . (24) \le\left(\frac{1}{\alpha}+L\right)\bigl(\lVert x^k-y^{k-1}\rVert+\lVert x^{k-1}-y^{k-1}\rVert\bigr). \tag*{(24)} ≤ ( α 1 + L ) ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) . (24)
Next, we establish the global convergence of Algorithm 1, following the arguments in [27 Theorem 4] , [7 Theorem 3.4] , and [8 Theorem 6.11] .
Theorem 4.8 Suppose that Assumptions 1.1 and 4.5 hold, and let { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be generated from Algorithm 1. Let x 0 = y 0 x^0=y^0 x 0 = y 0 . Assume that F F F satisfies the Kurdyka–Łojasiewicz (KL) property at every point in dom ( ∂ F ) \operatorname{dom}(\partial F) dom ( ∂ F ) . If σ k \sigma_k σ k satisfies (4.5), then
∑ k = 1 ∞ ∥ x k − x k − 1 ∥ ≤ ∑ k = 1 ∞ ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) < ∞ . \sum_{k=1}^{\infty}\lVert x^k-x^{k-1}\rVert\le\sum_{k=1}^{\infty}\bigl(\lVert x^k-y^{k-1}\rVert+\lVert x^{k-1}-y^{k-1}\rVert\bigr)<\infty. k = 1 ∑ ∞ ∥ x k − x k − 1 ∥ ≤ k = 1 ∑ ∞ ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) < ∞. Consequently, the sequences { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } both converge to the same stationary point x ‾ \overline{x} x satisfying (4.11).
Proof. Define μ k : = F ( x k ) − F ^ ≥ 0 \mu_k := F(x^k) - \widehat{F} \ge0 μ k := F ( x k ) − F ≥ 0 . Lemma 4.6 shows that X ‾ \overline{\mathcal{X}} X is nonempty and compact with F ≡ F ^ F \equiv\widehat{F} F ≡ F on X ‾ \overline{\mathcal{X}} X and dist ( x k , X ‾ ) → 0 \operatorname{dist}(x^k,\overline{\mathcal{X}}) \to0 dist ( x k , X ) → 0 . A finite collection of KL neighborhoods covers the compact set X ‾ \overline{\mathcal{X}} X . Restrict their desingularizing functions to a common interval and let ϕ \phi ϕ be their sum. The functions have positive derivatives, so ϕ ′ \phi' ϕ ′ dominates each individual derivative. For all sufficiently large k k k with μ k − 1 > 0 \mu_{k-1} > 0 μ k − 1 > 0 , the iterate x k − 1 x^{k-1} x k − 1 lies in at least one of these neighborhoods and μ k − 1 \mu_{k-1} μ k − 1 lies in the common interval. Hence
ϕ ′ ( μ k − 1 ) dist ( 0 , ∂ F ( x k − 1 ) ) ≥ 1. (25) \phi'(\mu_{k-1})\operatorname{dist}(0,\partial F(x^{k-1})) \ge1. \tag*{(25)} ϕ ′ ( μ k − 1 ) dist ( 0 , ∂ F ( x k − 1 )) ≥ 1. (25)
If μ K = 0 \mu_K = 0 μ K = 0 for some K K K , (4.8) and monotonicity force x k = y k = x K x^k = y^k = x^K x k = y k = x K for every k ≥ K k \ge K k ≥ K , and the theorem follows immediately. Otherwise every μ k \mu_k μ k is positive. In this case (4.13) and (4.14) ensure that the denominators below are nonzero for all sufficiently large k k k . For such k k k , the concavity of ϕ \phi ϕ gives
ϕ ( μ k − 1 ) − ϕ ( μ k ) ≥ ϕ ′ ( μ k − 1 ) ( μ k − 1 − μ k ) ≥ C ~ ϕ ′ ( μ k − 1 ) ( ∥ x k − y k − 1 ∥ 2 + ∥ x k − 1 − y k − 1 ∥ 2 ) ≥ ∥ x k − y k − 1 ∥ 2 + ∥ x k − 1 − y k − 1 ∥ 2 M ^ ( ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ ) . \begin{aligned}
\phi(\mu_{k-1})-\phi(\mu_k)
&\ge\phi'(\mu_{k-1})(\mu_{k-1}-\mu_k) \\
&\ge\widetilde{C}\phi'(\mu_{k-1})\left(\lVert x^k-y^{k-1}\rVert^2+\lVert x^{k-1}-y^{k-1}\rVert^2\right) \\
&\ge\frac{\lVert x^k-y^{k-1}\rVert^2+\lVert x^{k-1}-y^{k-1}\rVert^2}{\widehat{M}\left(\lVert x^{k-1}-y^{k-2}\rVert+\lVert x^{k-2}-y^{k-2}\rVert\right)}.
\end{aligned} ϕ ( μ k − 1 ) − ϕ ( μ k ) ≥ ϕ ′ ( μ k − 1 ) ( μ k − 1 − μ k ) ≥ C ϕ ′ ( μ k − 1 ) ( ∥ x k − y k − 1 ∥ 2 + ∥ x k − 1 − y k − 1 ∥ 2 ) ≥ M ( ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ ) ∥ x k − y k − 1 ∥ 2 + ∥ x k − 1 − y k − 1 ∥ 2 .
where M ^ = ( 1 / α + L ) / C ~ \widehat{M}=(1/\alpha+L)/\widetilde{C} M = ( 1/ α + L ) / C . Rearranging the above inequality yields
∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ≤ 2 M ^ ( ϕ ( μ k − 1 ) − ϕ ( μ k ) ) ( ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ ) ≤ M ^ ( ϕ ( μ k − 1 ) − ϕ ( μ k ) ) + 1 2 ( ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ ) . \begin{aligned}
\lVert x^k-y^{k-1}\rVert+\lVert x^{k-1}-y^{k-1}\rVert
&\le\sqrt{2\widehat{M}(\phi(\mu_{k-1})-\phi(\mu_k))\left(\lVert x^{k-1}-y^{k-2}\rVert+\lVert x^{k-2}-y^{k-2}\rVert\right)} \\
&\le\widehat{M}(\phi(\mu_{k-1})-\phi(\mu_k))+\frac{1}{2}\left(\lVert x^{k-1}-y^{k-2}\rVert+\lVert x^{k-2}-y^{k-2}\rVert\right).
\end{aligned} ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ≤ 2 M ( ϕ ( μ k − 1 ) − ϕ ( μ k )) ( ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ ) ≤ M ( ϕ ( μ k − 1 ) − ϕ ( μ k )) + 2 1 ( ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ ) .
So,
2 ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) ≤ 2 M ^ ( ϕ ( μ k − 1 ) − ϕ ( μ k ) ) + ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ . (26) 2\left(\lVert x^k-y^{k-1}\rVert+\lVert x^{k-1}-y^{k-1}\rVert\right)
\le2\widehat{M}(\phi(\mu_{k-1})-\phi(\mu_k))+\lVert x^{k-1}-y^{k-2}\rVert+\lVert x^{k-2}-y^{k-2}\rVert. \tag*{(26)} 2 ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) ≤ 2 M ( ϕ ( μ k − 1 ) − ϕ ( μ k )) + ∥ x k − 1 − y k − 2 ∥ + ∥ x k − 2 − y k − 2 ∥ . (26)
Summing (4.15) and using ϕ ≥ 0 \phi\ge0 ϕ ≥ 0 bounds the partial sums uniformly. Hence
∑ k = 1 ∞ ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) < ∞ . \sum_{k=1}^{\infty}\left(\lVert x^k-y^{k-1}\rVert+\lVert x^{k-1}-y^{k-1}\rVert\right)<\infty. k = 1 ∑ ∞ ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) < ∞.
Thus, { x k } \{x^k\} { x k } converges to some x ‾ \overline{x} x satisfying (4.11). Moreover, { y k } \{y^k\} { y k } also converges to x ‾ \overline{x} x .
Theorem 4.9 Suppose that the assumptions in Theorem 4.8 hold. Let { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be the sequences generated from Algorithm 1. Let x 0 = y 0 x^0=y^0 x 0 = y 0 . Assume that F F F satisfies the KL property at the limit point x ‾ \overline{x} x with exponent θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) and desingularizing function ϕ ( s ) = s 1 − θ / [ ν ( 1 − θ ) ] \phi(s)=s^{1-\theta}/[\nu(1-\theta)] ϕ ( s ) = s 1 − θ / [ ν ( 1 − θ )] , where ν > 0 \nu>0 ν > 0 is the constant in Definition 2.3. Then the following statements hold:
(i) For θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , there exists a constant C ^ > 0 \widehat{C} > 0 C > 0 such that, for all sufficiently large k k k ,
∥ x k − x ˉ ∥ ≤ C ^ ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) min ( 1 , 1 − θ θ ) . \|x^k-\bar{x}\| \le\widehat{C}\left(\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\|\right)^{\min\left(1,\frac{1-\theta}{\theta}\right)}. ∥ x k − x ˉ ∥ ≤ C ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) m i n ( 1 , θ 1 − θ ) .
(ii) If θ ∈ ( 0 , 1 2 ] \theta\in\left(0,\frac{1}{2}\right] θ ∈ ( 0 , 2 1 ] , there exist constants C ^ 1 > 0 \widehat{C}_1 > 0 C 1 > 0 and ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) such that, for all sufficiently large k k k ,
∥ x k − x ˉ ∥ ≤ C ^ 1 ρ k . \|x^k-\bar{x}\| \le\widehat{C}_1\rho^k. ∥ x k − x ˉ ∥ ≤ C 1 ρ k .
(iii) If θ ∈ ( 1 2 , 1 ) \theta\in\left(\frac{1}{2},1\right) θ ∈ ( 2 1 , 1 ) , there exists a constant C ^ 2 > 0 \widehat{C}_2 > 0 C 2 > 0 such that, for all sufficiently large k k k ,
∥ x k − x ˉ ∥ ≤ C ^ 2 k − 1 − θ 2 θ − 1 . \|x^k-\bar{x}\| \le\widehat{C}_2 k^{-\frac{1-\theta}{2\theta-1}}. ∥ x k − x ˉ ∥ ≤ C 2 k − 2 θ − 1 1 − θ .
Proof. If the iterates are eventually constant, all conclusions are immediate. Otherwise, restrict to a sufficiently large index range on which the KL inequality at x ˉ \bar{x} x ˉ holds and
s k : = ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ≤ 1. s_k := \|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\| \le1. s k := ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ≤ 1.
(i) Apply the argument for (4.15) on this tail with this ϕ \phi ϕ . Combining (4.13) and (4.14), with k k k replaced by k + 1 k+1 k + 1 , and using ϕ ′ ( μ k ) = ν − 1 μ k − θ \phi'(\mu_k)=\nu^{-1}\mu_k^{-\theta} ϕ ′ ( μ k ) = ν − 1 μ k − θ gives
( 1 α + L ) ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) ≥ dist ( 0 , ∂ F ( x k ) ) ≥ ν μ k θ . (27) \left(\frac{1}{\alpha}+L\right)\left(\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\|\right) \ge\operatorname{dist}(0,\partial F(x^k)) \ge\nu\mu_k^\theta. \tag*{(27)} ( α 1 + L ) ( ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ) ≥ dist ( 0 , ∂ F ( x k )) ≥ ν μ k θ . (27)
Define Δ k : = ∑ p = k + 1 ∞ s p \Delta_k := \sum_{p=k+1}^{\infty}s_p Δ k := ∑ p = k + 1 ∞ s p . Summing (4.15) from p = k + 1 p=k+1 p = k + 1 onward yields
2 Δ k = 2 ∑ p = k + 1 + ∞ ( ∥ x p − y p − 1 ∥ + ∥ x p − 1 − y p − 1 ∥ ) 2\Delta_k = 2\sum_{p=k+1}^{+\infty}\left(\|x^p-y^{p-1}\|+\|x^{p-1}-y^{p-1}\|\right) 2 Δ k = 2 p = k + 1 ∑ + ∞ ( ∥ x p − y p − 1 ∥ + ∥ x p − 1 − y p − 1 ∥ )
≤ 2 M ^ ϕ ( μ k ) + Δ k + ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ . \le2\widehat{M}\phi(\mu_k)+\Delta_k+\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\|. ≤ 2 M ϕ ( μ k ) + Δ k + ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥.
Combining (4.16) with the preceding bound yields
Δ k ≤ 2 M ^ ϕ ( μ k ) + ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ≤ 2 M ^ ν ( 1 − θ ) ( 1 ν ( 1 α + L ) [ ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ] ) 1 − θ θ \begin{aligned}
\Delta_k \le2\widehat{M}\phi(\mu_k)+\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\| \\
&\le\frac{2\widehat{M}}{\nu(1-\theta)}
\left(\frac{1}{\nu}\left(\frac{1}{\alpha}+L\right)
\left[\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\|\right]\right)^{\frac{1-\theta}{\theta}}
\end{aligned} Δ k ≤ 2 M ϕ ( μ k ) + ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ≤ ν ( 1 − θ ) 2 M ( ν 1 ( α 1 + L ) [ ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ] ) θ 1 − θ
+ [ ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ] . (28) \qquad+\left[\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\|\right]. \tag*{(28)} + [ ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ ] . (28)
Let C ^ = 2 M ^ ν ( 1 − θ ) ( ν − 1 ( 1 α + L ) ) 1 − θ θ + 1 \widehat{C}=\frac{2\widehat{M}}{\nu(1-\theta)}\left(\nu^{-1}\left(\frac{1}{\alpha}+L\right)\right)^{\frac{1-\theta}{\theta}}+1 C = ν ( 1 − θ ) 2 M ( ν − 1 ( α 1 + L ) ) θ 1 − θ + 1 . The triangle inequality gives ∥ x k − x ˉ ∥ ≤ ∑ p = k ∞ ∥ x p + 1 − x p ∥ ≤ Δ k \|x^k-\bar{x}\|\le\sum_{p=k}^{\infty}\|x^{p+1}-x^p\|\le\Delta_k ∥ x k − x ˉ ∥ ≤ ∑ p = k ∞ ∥ x p + 1 − x p ∥ ≤ Δ k . Since s k ≤ 1 s_k\le1 s k ≤ 1 , (4.17) implies Δ k ≤ C ^ s k min { 1 , ( 1 − θ ) / θ } \Delta_k\le\widehat{C}s_k^{\min\{1,(1-\theta)/\theta\}} Δ k ≤ C s k m i n { 1 , ( 1 − θ ) / θ } , which proves (i).
(ii) For θ ∈ ( 0 , 1 2 ] \theta\in\left(0,\frac{1}{2}\right] θ ∈ ( 0 , 2 1 ] , it follows from (4.17) that Δ k ≤ C ^ ( Δ k − 1 − Δ k ) \Delta_k\le\widehat{C}(\Delta_{k-1}-\Delta_k) Δ k ≤ C ( Δ k − 1 − Δ k ) . The remainder of the proof proceeds along the same lines as [1 Theorem 2(ii)] .
(iii) From (4.17), we obtain Δ k θ 1 − θ ≤ C ^ θ 1 − θ ( Δ k − 1 − Δ k ) \Delta_k^{\frac{\theta}{1-\theta}}\le\widehat{C}^{\frac{\theta}{1-\theta}}(\Delta_{k-1}-\Delta_k) Δ k 1 − θ θ ≤ C 1 − θ θ ( Δ k − 1 − Δ k ) . The desired result then follows by applying the argument of [1 Theorem 2(iii)] . □ \square □
Finite Identification via Subspace Selection
We specify thresholds ε k \varepsilon_k ε k for selecting the index set S k S^k S k to ensure finite identification. Here, finite identification means that there exists an integer K K K such that S k = S ‾ S^k=\overline{S} S k = S for all k ≥ K k\ge K k ≥ K , where S ‾ \overline{S} S denotes the support of the limit point of the sequence { x k } \{x^k\} { x k } .
Lemma 5.1 Suppose that the thresholds ε k \varepsilon_k ε k in Algorithm 1 are positive and satisfy lim k → ∞ ε k = 0 \lim_{k\to\infty}\varepsilon_k=0 lim k → ∞ ε k = 0 . Let { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be generated from Algorithm 1. Let x 0 = y 0 x^0=y^0 x 0 = y 0 . Suppose the hypotheses of Theorem 4.8 hold. Let x ‾ \overline{x} x be the limit point of { x k } \{x^k\} { x k } , and define S ‾ = supp ( x ‾ ) \overline{S}=\operatorname{supp}(\overline{x}) S = supp ( x ) and n ‾ = ∥ x ‾ ∥ 0 \overline{n}=\|\overline{x}\|_0 n = ∥ x ∥ 0 . Then,
(i) there exists an index K 0 K_0 K 0 such that S ‾ ⊆ S k \overline{S}\subseteq S^k S ⊆ S k , ∀ k ≥ K 0 \forall k\ge K_0 ∀ k ≥ K 0 ;
(ii) for all k ≥ K 0 k\ge K_0 k ≥ K 0 , n ‾ ≤ n k ≤ min { ⌊ ∥ x k − x ‾ ∥ 2 / ε k 2 ⌋ + n ‾ , ∥ x k ∥ 0 } \overline{n}\le n_k\le\min\{\lfloor\|x^k-\overline{x}\|^2/\varepsilon_k^2\rfloor+\overline{n},\|x^k\|_0\} n ≤ n k ≤ min {⌊ ∥ x k − x ∥ 2 / ε k 2 ⌋ + n , ∥ x k ∥ 0 } .
Proof (i) If S ‾ = ∅ \overline{S}=\emptyset S = ∅ , take K 0 = 1 K_0=1 K 0 = 1 . Suppose S ‾ ≠ ∅ \overline{S}\ne\emptyset S = ∅ and denote ρ min : = min { ∣ x ‾ i ∣ : i ∈ S ‾ } > 0 \rho_{\min}:=\min\{|\overline{x}_i|:i\in\overline{S}\}>0 ρ m i n := min { ∣ x i ∣ : i ∈ S } > 0 . Choose a common index K 0 K_0 K 0 such that ε k ≤ ρ min / 2 \varepsilon_k\le\rho_{\min}/2 ε k ≤ ρ m i n /2 and ∥ x k − x ‾ ∥ ≤ ρ min / 2 \|x^k-\overline{x}\|\le\rho_{\min}/2 ∥ x k − x ∥ ≤ ρ m i n /2 when k ≥ K 0 k\ge K_0 k ≥ K 0 . Thus,
∣ x i k ∣ ≥ ∣ x ‾ i ∣ − ∣ x i k − x ‾ i ∣ ≥ ρ min − ∥ x k − x ‾ ∥ ≥ ρ min 2 ≥ ε k , |x_i^k|\ge|\overline{x}_i|-|x_i^k-\overline{x}_i|\ge\rho_{\min}-\|x^k-\overline{x}\|\ge\frac{\rho_{\min}}{2}\ge\varepsilon_k, ∣ x i k ∣ ≥ ∣ x i ∣ − ∣ x i k − x i ∣ ≥ ρ m i n − ∥ x k − x ∥ ≥ 2 ρ m i n ≥ ε k ,
which implies i ∈ S k i\in S^k i ∈ S k . (ii) Let k ≥ K 0 k\ge K_0 k ≥ K 0 . By assumption, ε k > 0 \varepsilon_k>0 ε k > 0 . Let T k : = S k ∖ S ‾ T_k:=S^k\setminus\overline{S} T k := S k ∖ S . Because x ‾ i = 0 \overline{x}_i=0 x i = 0 and ∣ x i k ∣ ≥ ε k |x_i^k|\ge\varepsilon_k ∣ x i k ∣ ≥ ε k for i ∈ T k i\in T_k i ∈ T k ,
∥ x k − x ‾ ∥ 2 ≥ ∑ i ∈ T k ∣ x i k ∣ 2 ≥ # ( T k ) ε k 2 = ( n k − n ‾ ) ε k 2 . \|x^k-\overline{x}\|^2\ge\sum_{i\in T_k}|x_i^k|^2\ge\#(T_k)\varepsilon_k^2=(n_k-\overline{n})\varepsilon_k^2. ∥ x k − x ∥ 2 ≥ i ∈ T k ∑ ∣ x i k ∣ 2 ≥ # ( T k ) ε k 2 = ( n k − n ) ε k 2 .
The assertion follows directly. □ \square □
Theorem 5.2 Suppose that all the assumptions of Theorem 4.8 hold, and let { x k } \{x^k\} { x k } and { y k } \{y^k\} { y k } be generated by Algorithm 1, with x 0 = y 0 x^0=y^0 x 0 = y 0 . Let x ‾ \overline{x} x be its limit and S ‾ : = supp ( x ‾ ) \overline{S}:=\operatorname{supp}(\overline{x}) S := supp ( x ) . Assume that F F F has the KL property at x ‾ \overline{x} x with exponent θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) . Define
s k : = ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ , s_k:=\|x^k-y^{k-1}\|+\|x^{k-1}-y^{k-1}\|, s k := ∥ x k − y k − 1 ∥ + ∥ x k − 1 − y k − 1 ∥ , a k : = max { s k , C a / ( k + 1 ) } > 0 , ν : = min { 1 , ( 1 − θ ) / θ } , (29) a_k:=\max\{s_k,C_a/(k+1)\}>0,\quad\nu:=\min\{1,(1-\theta)/\theta\}, \tag*{(29)} a k := max { s k , C a / ( k + 1 )} > 0 , ν := min { 1 , ( 1 − θ ) / θ } , (29) where C a > 0 C_a>0 C a > 0 . For any C ε > 0 C_\varepsilon>0 C ε > 0 and $0<\gamma<\nu$, take ε k : = C ε a k γ \varepsilon_k:=C_\varepsilon a_k^\gamma ε k := C ε a k γ . Then S k = S ‾ S^k=\overline{S} S k = S for all sufficiently large $k.
Proof We have a k > 0 a_k>0 a k > 0 and a k → 0 a_k\to0 a k → 0 by (20) ; hence ε k > 0 \varepsilon_k>0 ε k > 0 and ε k → 0 \varepsilon_k\to0 ε k → 0 . Lemma 5.1 gives S ‾ ⊆ S k \overline{S}\subseteq S^k S ⊆ S k eventually. By Theorem 4.9 (i), for all sufficiently large k k k , ∥ x k − x ‾ ∥ ≤ C s ν k ≤ C a ν a k ν \|x^k-\overline{x}\|\le C_s\nu_k\le C_a^\nu a_k^\nu ∥ x k − x ∥ ≤ C s ν k ≤ C a ν a k ν . Consequently, the bound in Lemma 5.1 gives
0 ≤ n k − n ‾ ≤ ⌊ C a 2 ν C ε 2 a k 2 ( ν − γ ) ⌋ = 0 0\le n_k-\overline{n}\le\left\lfloor\frac{C_a^{2\nu}}{C_\varepsilon^2}a_k^{2(\nu-\gamma)}\right\rfloor=0 0 ≤ n k − n ≤ ⌊ C ε 2 C a 2 ν a k 2 ( ν − γ ) ⌋ = 0
for all sufficiently large $k, proving the claim. □ \square □
Under the same assumptions, the logarithmic threshold below also ensures finite identification and can be evaluated without knowing θ \theta θ .
ε k : = C ε log ( e + a k − 1 ) q ε , C ε > 0 , q ε > 0 , \varepsilon_k:=\frac{C_\varepsilon}{\log(e+a_k^{-1})^{q_\varepsilon}},\quad C_\varepsilon>0,\quad q_\varepsilon>0, ε k := log ( e + a k − 1 ) q ε C ε , C ε > 0 , q ε > 0 ,
Here a k a_k a k is defined in (5.1). Indeed, ε k > 0 \varepsilon_k>0 ε k > 0 and ε k → 0 \varepsilon_k\to0 ε k → 0 . For ν \nu ν defined in (5.1), we have
∥ x k − x ˉ ∥ ε k ≤ C ^ C a k ν [ log ( e + a k − 1 ) ] q ε ⟶ 0. \frac{\lVert x^k-\bar{x}\rVert}{\varepsilon_k}\leq\frac{\widehat{C}}{C}a_k^\nu\left[\log(e+a_k^{-1})\right]^{q_\varepsilon}\longrightarrow0. ε k ∥ x k − x ˉ ∥ ≤ C C a k ν [ log ( e + a k − 1 ) ] q ε ⟶ 0.
Consequently, the selected set S k S^k S k eventually equals supp ( x ˉ ) \operatorname{supp}(\bar{x}) supp ( x ˉ ) without knowledge of the KL exponent. The floor C a / ( k + 1 ) C_a/(k+1) C a / ( k + 1 ) in a k a_k a k ensures that a k > 0 a_k>0 a k > 0 , and hence ε k > 0 \varepsilon_k>0 ε k > 0 .
Finite Identification without Nondegeneracy: A Degenerate Example
The following example shows that proximal-gradient methods may fail to identify the support of the limit in finitely many iterations when the nondegeneracy condition is absent, even if the objective is partly smooth. In contrast, our proposed ε k \varepsilon_k ε k -based selection strategy can identify the limiting support in finitely many iterations without this condition.
Example 5.3 Consider the problem
min x ∈ R 2 F ( x ) : = ∥ x ∥ 1 + 1 2 ∥ x − b ∥ 2 , b = ( 3 , 1 ) T . \min_{x\in\mathbb{R}^{2}} F(x):=\lVert x\rVert_1+\frac{1}{2}\lVert x-b\rVert^2,\qquad b=(3,1)^{\mathsf{T}}. x ∈ R 2 min F ( x ) := ∥ x ∥ 1 + 2 1 ∥ x − b ∥ 2 , b = ( 3 , 1 ) T . Let g ( x ) : = ∥ x ∥ 1 g(x):=\lVert x\rVert_1 g ( x ) := ∥ x ∥ 1 and h ( x ) : = 1 2 ∥ x − b ∥ 2 h(x):=\frac{1}{2}\lVert x-b\rVert^2 h ( x ) := 2 1 ∥ x − b ∥ 2 . Then ∇ h \nabla h ∇ h is 1-Lipschitz continuous, and the unique minimizer is x ˉ = ( 2 , 0 ) T \bar{x}=(2,0)^{\mathsf{T}} x ˉ = ( 2 , 0 ) T . Moreover, F F F is partly smooth [23 ] at every x ∈ R 2 x\in\mathbb{R}^2 x ∈ R 2 relative to M x : = { z : supp ( z ) = supp ( x ) } \mathcal{M}_x:=\{z:\operatorname{supp}(z)=\operatorname{supp}(x)\} M x := { z : supp ( z ) = supp ( x )} , however, the nondegeneracy condition fails at x ˉ \bar{x} x ˉ since
− ∇ h ( x ˉ ) = ( 1 , 1 ) T ∉ ri ∂ g ( x ˉ ) = { 1 } × ( − 1 , 1 ) . -\nabla h(\bar{x})=(1,1)^{\mathsf{T}}\notin\operatorname{ri}\partial g(\bar{x})=\{1\}\times(-1,1). − ∇ h ( x ˉ ) = ( 1 , 1 ) T ∈ / ri ∂ g ( x ˉ ) = { 1 } × ( − 1 , 1 ) . We first consider the standard PG method. For any α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and x 0 ∈ ( 1 , 3 ) × ( 0 , 1 ) x^0\in(1,3)\times(0,1) x 0 ∈ ( 1 , 3 ) × ( 0 , 1 ) , let r : = 1 − α r:=1-\alpha r := 1 − α . Soft thresholding gives x 1 k − 2 = r ( x 1 k − 1 − 2 ) x_1^k-2=r(x_1^{k-1}-2) x 1 k − 2 = r ( x 1 k − 1 − 2 ) and x 2 k = r x 2 k − 1 x_2^k=rx_2^{k-1} x 2 k = r x 2 k − 1 . Since these updates preserve ( 1 , 3 ) × ( 0 , 1 ) (1,3)\times(0,1) ( 1 , 3 ) × ( 0 , 1 ) , we obtain
x k = Prox α g ( x k − 1 − α ∇ h ( x k − 1 ) ) = ( 2 + r k ( x 1 0 − 2 ) r k x 2 0 ) , k ≥ 1. x^k=\operatorname{Prox}_{\alpha g}\left(x^{k-1}-\alpha\nabla h(x^{k-1})\right)=\begin{pmatrix}2+r^k(x_1^0-2)\\r^kx_2^0\end{pmatrix},\qquad k\geq1. x k = Prox α g ( x k − 1 − α ∇ h ( x k − 1 ) ) = ( 2 + r k ( x 1 0 − 2 ) r k x 2 0 ) , k ≥ 1. Thus, although x k → x ˉ x^k\to\bar{x} x k → x ˉ , we have supp ( x k ) = { 1 , 2 } \operatorname{supp}(x^k)=\{1,2\} supp ( x k ) = { 1 , 2 } for every finite k k k . Hence, PG does not identify the support of the limit in finitely many iterations.
We next apply a thresholding strategy to the PG iterates. Since F F F is strongly convex, it has KL exponent θ = 1 / 2 \theta=1/2 θ = 1/2 at x ˉ \bar{x} x ˉ . Consider a proximal-gradient variant of the power threshold in Theorem 5.2. For any γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) , let
ε k : = ∥ x k − x k − 1 α ∥ γ , S k : = { i ∈ { 1 , 2 } : ∣ x i k ∣ ≥ ε k } , k ≥ 1. \varepsilon_k:=\left\lVert\frac{x^k-x^{k-1}}{\alpha}\right\rVert^\gamma,\qquad S^k:=\{i\in\{1,2\}:|x_i^k|\geq\varepsilon_k\},\qquad k\geq1. ε k := α x k − x k − 1 γ , S k := { i ∈ { 1 , 2 } : ∣ x i k ∣ ≥ ε k } , k ≥ 1. Writing C : = ∥ x 0 − x ˉ ∥ > 0 C:=\lVert x^0-\bar{x}\rVert>0 C := ∥ x 0 − x ˉ ∥ > 0 , we obtain
ε k = C γ r γ ( k − 1 ) > 0 , ∥ x k − x ˉ ∥ 2 ε k 2 = C 2 ( 1 − γ ) r 2 k ( 1 − γ ) + 2 γ ⟶ 0. \varepsilon_k=C^\gamma r^{\gamma(k-1)}>0,\qquad\frac{\lVert x^k-\bar{x}\rVert^2}{\varepsilon_k^2}=C^{2(1-\gamma)}r^{2k(1-\gamma)+2\gamma}\longrightarrow0. ε k = C γ r γ ( k − 1 ) > 0 , ε k 2 ∥ x k − x ˉ ∥ 2 = C 2 ( 1 − γ ) r 2 k ( 1 − γ ) + 2 γ ⟶ 0.
Since ε k > 0 \varepsilon_k > 0 ε k > 0 for every k ≥ 1 k \ge1 k ≥ 1 , no additional positive floor is needed. Moreover, since ∣ x 2 k ∣ ≤ ∥ x k − x ˉ ∥ \lvert x_2^k\rvert\le\lVert x^k-\bar{x}\rVert ∣ x 2 k ∣ ≤ ∥ x k − x ˉ ∥ , ε k → 0 \varepsilon_k \to0 ε k → 0 , and x 1 k → 2 x_1^k \to2 x 1 k → 2 , there exists K K K such that
∣ x 2 k ∣ < ε k < ∣ x 1 k ∣ , S k = { 1 } = supp ( x ˉ ) , k ≥ K . \lvert x_2^k\rvert< \varepsilon_k < \lvert x_1^k\rvert,\qquad S^k=\{1\}=\operatorname{supp}(\bar{x}),\qquad k\ge K. ∣ x 2 k ∣ < ε k < ∣ x 1 k ∣ , S k = { 1 } = supp ( x ˉ ) , k ≥ K .
Thus, the thresholding strategy identifies the limiting support in finitely many iterations, even though the PG iterates do not.
Restricted Local Stationarity
Throughout this section, we assume that the conditions of Theorem 4.8 hold and that there exists an index K 1 ( ≥ K 0 ) K_1(\ge K_0) K 1 ( ≥ K 0 ) such that S k = S ˉ : = supp ( x ˉ ) S^k=\bar{S}:=\operatorname{supp}(\bar{x}) S k = S ˉ := supp ( x ˉ ) for all k ≥ K 1 k\ge K_1 k ≥ K 1 . The latter condition is guaranteed by Theorem 5.2. We restrict the analysis in this section to S ˉ ≠ ∅ \bar{S}\ne\varnothing S ˉ = ∅ . If S ˉ = ∅ \bar{S}=\varnothing S ˉ = ∅ , the assumed identification implies that S k = ∅ S^k=\varnothing S k = ∅ for all sufficiently large k k k . Consequently, y k = x k y^k=x^k y k = x k , and no cubic refinement is performed. For k ≥ K 1 k\ge K_1 k ≥ K 1 , let d ^ k ∈ R n \hat{d}^k\in\mathbb{R}^n d ^ k ∈ R n denote the zero extension of d k d^k d k from S ˉ \bar{S} S ˉ . For k ≥ K 1 k\ge K_1 k ≥ K 1 , we denote
g k = ∇ S ˉ F ( x k ) , H k = ∇ S ˉ 2 F ( x k ) . g^k=\nabla_{\bar{S}}F(x^k),\qquad H^k=\nabla_{\bar{S}}^2F(x^k). g k = ∇ S ˉ F ( x k ) , H k = ∇ S ˉ 2 F ( x k ) .
To proceed, we impose the following additional assumption.
Assumption 6.1 For each x ∈ dom ∂ F x\in\operatorname{dom}\partial F x ∈ dom ∂ F with S = supp ( x ) S=\operatorname{supp}(x) S = supp ( x ) , there exists δ x > 0 \delta_x>0 δ x > 0 such that ∇ S 2 F ( z ) \nabla_S^2F(z) ∇ S 2 F ( z ) is well-defined and continuous on B ( x , δ x ) \mathcal{B}(x,\delta_x) B ( x , δ x ) .
The next theorem proves eventual acceptance of full cubic steps, that is, β k = 1 \beta_k=1 β k = 1 for all sufficiently large k k k .
Theorem 6.2 Under the hypotheses stated at the beginning of this section and Assumption 6.1, the following assertions hold.
(i) The sequences { g k } \{g^k\} { g k } , { H k } \{H^k\} { H k } and { d k } \{d^k\} { d k } are bounded for k ≥ K 1 k\ge K_1 k ≥ K 1 .
(ii) There is a constant β > 0 \beta>0 β > 0 such that β k ≥ β \beta_k\ge\beta β k ≥ β for all sufficiently large k k k .
(iii) d ^ k → 0 \hat{d}^k\to0 d ^ k → 0 .
(iv) There is an index K ^ ≥ K 1 \widehat{K}\ge K_1 K ≥ K 1 such that, for every k ≥ K ^ k\ge\widehat{K} k ≥ K , β k = 1 \beta_k=1 β k = 1 and the following bound holds for all t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ]
∥ ∇ S ˉ 2 F ( x k + t d ^ k ) − ∇ S ˉ 2 F ( x k ) ∥ ≤ η 2 + M ( x ˉ ) t ∥ d k ∥ , (30) \left\lVert\nabla_{\bar{S}}^2F(x^k+t\hat{d}^k)-\nabla_{\bar{S}}^2F(x^k)\right\rVert\le\frac{\eta}{2}+M(\bar{x})t\lVert d^k\rVert, \tag*{(30)} ∇ S ˉ 2 F ( x k + t d ^ k ) − ∇ S ˉ 2 F ( x k ) ≤ 2 η + M ( x ˉ ) t ∥ d k ∥ , (30) where any M ( x ˉ ) ≥ 0 M(\bar{x})\ge0 M ( x ˉ ) ≥ 0 is valid, including M ( x ˉ ) = ( ω + 1 ) lip ∇ S ˉ 2 F ( x ˉ ) / 2 M(\bar{x})=(\omega+1)\operatorname{lip}\nabla_{\bar{S}}^2F(\bar{x})/2 M ( x ˉ ) = ( ω + 1 ) lip ∇ S ˉ 2 F ( x ˉ ) /2 .
Proof. Choose a sufficiently small ball centered at x ˉ \bar{x} x ˉ and contained in B ( x ˉ , δ x ˉ ) \mathcal{B}(\bar{x},\delta_{\bar{x}}) B ( x ˉ , δ x ˉ ) , such that all coordinates in S ˉ \bar{S} S ˉ remain nonzero throughout the ball. By continuity, the restricted Hessian is bounded there by some constant C H > 0 C_H>0 C H > 0 . Since x k → x ˉ x^k\to\bar{x} x k → x ˉ , there exists r > 0 r>0 r > 0 such that, for all sufficiently large k k k , the line segment joining x k x^k x k and x k + r d x^k+r d x k + r d lies in this ball for any unit vector d d d supported on S ˉ \bar{S} S ˉ . For any g k ≠ 0 g^k\ne0 g k = 0 , choosing the direction − g k / ∥ g k ∥ -g^k/\lVert g^k\rVert − g k / ∥ g k ∥ and applying Taylor’s theorem yields
F ≤ F ( x k − r g k ∥ g k ∥ ) ≤ F ( x k ) − r ∥ g k ∥ + C H r 2 2 . F\le F\left(x^k-r\frac{g^k}{\lVert g^k\rVert}\right)\le F(x^k)-r\lVert g^k\rVert+\frac{C_Hr^2}{2}. F ≤ F ( x k − r ∥ g k ∥ g k ) ≤ F ( x k ) − r ∥ g k ∥ + 2 C H r 2 .
where the direction is understood to be extended by zero outside S ˉ \bar{S} S ˉ . Since { F ( x k ) } \{F(x^k)\} { F ( x k )} is bounded above, it follows that { g k } \{g^k\} { g k } is bounded. Enlarging the bound if necessary to cover the finitely many remaining indices, we may choose C g > 0 C_g > 0 C g > 0 such that ∥ g k ∥ ≤ C g \|g^k\| \le C_g ∥ g k ∥ ≤ C g for all k k k . Now, let v k = ∥ d k ∥ v_k = \|d^k\| v k = ∥ d k ∥ . By the definition of the residual r k r^k r k and Condition (3.3a), we obtain
⟨ g k , d k ⟩ + ⟨ H k d k , d k ⟩ + η v k 2 + σ k 2 v k 3 = ⟨ r k , d k ⟩ ≤ 0. \langle g^k,d^k\rangle+ \langle H^k d^k,d^k\rangle+ \eta v_k^2 + \frac{\sigma_k}{2}v_k^3 = \langle r^k,d^k\rangle\le0. ⟨ g k , d k ⟩ + ⟨ H k d k , d k ⟩ + η v k 2 + 2 σ k v k 3 = ⟨ r k , d k ⟩ ≤ 0.
Hence the Cauchy–Schwarz inequality and the bounds ∥ g k ∥ ≤ C g \|g^k\| \le C_g ∥ g k ∥ ≤ C g , ∥ H k ∥ ≤ C H \|H^k\| \le C_H ∥ H k ∥ ≤ C H yield
σ k 2 v k 3 ≤ − ⟨ g k , d k ⟩ − ⟨ H k d k , d k ⟩ − η v k 2 ≤ ∣ ⟨ g k , d k ⟩ ∣ + ∣ ⟨ H k d k , d k ⟩ ∣ ≤ C g v k + C H v k 2 . \begin{aligned}
\frac{\sigma_k}{2}v_k^3 \le-\langle g^k,d^k\rangle- \langle H^k d^k,d^k\rangle- \eta v_k^2 \\
&\le|\langle g^k,d^k\rangle| + |\langle H^k d^k,d^k\rangle| \\
&\le C_gv_k + C_Hv_k^2.
\end{aligned} 2 σ k v k 3 ≤ − ⟨ g k , d k ⟩ − ⟨ H k d k , d k ⟩ − η v k 2 ≤ ∣ ⟨ g k , d k ⟩ ∣ + ∣ ⟨ H k d k , d k ⟩ ∣ ≤ C g v k + C H v k 2 .
Since σ k ≥ 2 c / 3 \sigma_k \ge2c/3 σ k ≥ 2 c /3 , for v k > 0 v_k > 0 v k > 0 the estimate gives c 3 v k 2 ≤ C g + C H v k \frac{c}{3}v_k^2 \le C_g + C_Hv_k 3 c v k 2 ≤ C g + C H v k . Hence, there exists C d > 0 C_d > 0 C d > 0 such that v k ≤ C d v_k \le C_d v k ≤ C d , which also holds trivially when v k = 0 v_k = 0 v k = 0 . This proves (i). By continuity of ∇ S ˉ 2 F \nabla_{\bar{S}}^2F ∇ S ˉ 2 F at x ˉ \bar{x} x ˉ , there exists ρ > 0 \rho> 0 ρ > 0 such that
∥ ∇ S ˉ 2 F ( z ) − ∇ S ˉ 2 F ( w ) ∥ ≤ η / 2 ( z , w ∈ B ( x ˉ , ρ ) ) , \|\nabla_{\bar{S}}^2F(z)-\nabla_{\bar{S}}^2F(w)\| \le\eta/2 \quad(z,w\in\mathcal{B}(\bar{x},\rho)), ∥ ∇ S ˉ 2 F ( z ) − ∇ S ˉ 2 F ( w ) ∥ ≤ η /2 ( z , w ∈ B ( x ˉ , ρ )) ,
and the coordinates indexed by S ˉ \bar{S} S ˉ remain nonzero on this ball. Let β ^ = min { 1 , ρ / ( 2 C d ) } \hat{\beta}=\min\{1,\rho/(2C_d)\} β ^ = min { 1 , ρ / ( 2 C d )} . For all sufficiently large k k k , x k ∈ B ( x ˉ , ρ / 2 ) x^k\in\mathcal{B}(\bar{x},\rho/2) x k ∈ B ( x ˉ , ρ /2 ) , and the segments x k + t β d ^ k x^k+t\beta\hat{d}^k x k + tβ d ^ k , t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , remain in the ball whenever 0 < β ≤ β ^ 0<\beta\le\hat{\beta} 0 < β ≤ β ^ . The complementary coordinates are fixed, so the support is unchanged along each segment. Lemma 4.2 , with a = η / 2 a=\eta/2 a = η /2 and M = 0 M=0 M = 0 , and Conditions (3.3a)–(3.3b) therefore yield
F ( x k + β d ^ k ) ≤ F ( x k ) − η β 2 4 v k 2 − σ k β 2 4 v k 3 ≤ F ( x k ) − η β 2 4 v k 2 − c β 3 6 v k 3 . F(x^k+\beta\hat{d}^k)\le F(x^k)-\frac{\eta\beta^2}{4}v_k^2-\frac{\sigma_k\beta^2}{4}v_k^3\le F(x^k)-\frac{\eta\beta^2}{4}v_k^2-\frac{c\beta^3}{6}v_k^3. F ( x k + β d ^ k ) ≤ F ( x k ) − 4 η β 2 v k 2 − 4 σ k β 2 v k 3 ≤ F ( x k ) − 4 η β 2 v k 2 − 6 c β 3 v k 3 .
Thus every such β \beta β satisfies the line-search test. Backtracking gives β k ≥ q β ^ \beta_k\ge q\hat{\beta} β k ≥ q β ^ , proving (ii). Since ∥ d k ∥ = ∥ x k − y k ∥ / β k ≤ ∥ x k − y k ∥ / β → 0 \|d^k\|=\|x^k-y^k\|/\beta_k\le\|x^k-y^k\|/\beta\to0 ∥ d k ∥ = ∥ x k − y k ∥/ β k ≤ ∥ x k − y k ∥/ β → 0 , assertion (iii) follows. Since d k → 0 d^k\to0 d k → 0 and x k → x ˉ x^k\to\bar{x} x k → x ˉ , the full trial segment lies in the ball for all sufficiently large k k k . The same estimate gives β k = 1 \beta_k=1 β k = 1 , and the Hessian variation is at most η / 2 \eta/2 η /2 throughout the segment. This proves (6.1) for any nonnegative choice of M ( x ˉ ) M(\bar{x}) M ( x ˉ ) .
Definition 6.3 For a twice continuously differentiable function F ~ \widetilde{F} F , a point x \mathbf{x} x is an ( ϵ g , ϵ H ) (\epsilon_g,\epsilon_H) ( ϵ g , ϵ H ) -approximate second-order stationary point if
∥ ∇ F ~ ( x ) ∥ ≤ ϵ g , λ min ( ∇ 2 F ~ ( x ) ) ≥ − ϵ H . (31) \|\nabla\widetilde{F}(\mathbf{x})\|\le\epsilon_g,\qquad\lambda_{\min}(\nabla^2\widetilde{F}(\mathbf{x}))\ge-\sqrt{\epsilon_H}. \tag*{(31)} ∥∇ F ( x ) ∥ ≤ ϵ g , λ m i n ( ∇ 2 F ( x )) ≥ − ϵ H . (31) For the nonsmooth objective in (1.1), replace ∇ F ~ \nabla\widetilde{F} ∇ F and ∇ 2 F ~ \nabla^2\widetilde{F} ∇ 2 F in (31) with ∇ S ˉ F \nabla_{\bar{S}}F ∇ S ˉ F and ∇ S ˉ 2 F \nabla_{\bar{S}}^2F ∇ S ˉ 2 F to define approximate second-order stationarity on S ˉ \bar{S} S ˉ .
Corollary 6.4 Suppose that the hypotheses of Theorem 6.2 hold and sup k σ k = : σ ˉ < ∞ \sup_k \sigma_k =: \bar{\sigma}<\infty sup k σ k =: σ ˉ < ∞ . Then
∇ S ˉ F ( x ˉ ) = 0 , ∇ S ˉ 2 F ( x ˉ ) ⪰ − η I . \nabla_{\bar{S}}F(\bar{x})=0,\qquad\nabla_{\bar{S}}^2F(\bar{x})\succeq-\eta I. ∇ S ˉ F ( x ˉ ) = 0 , ∇ S ˉ 2 F ( x ˉ ) ⪰ − η I .
Proof. Let v k : = ∥ d k ∥ v_k := \lVert d^k\rVert v k := ∥ d k ∥ . By conditions (3.3c) and (3.3d), for all sufficiently large k k k ,
∥ g k ∥ ≤ ( C H + η ) v k + ( σ ˉ 2 + κ g ) v k 2 , H k ⪰ − [ η + ( σ ˉ 2 + κ H ) v k ] I . \lVert g^k\rVert\le(C_H+\eta)v_k+\left(\frac{\bar{\sigma}}{2}+\kappa_g\right)v_k^2,\qquad H^k \succeq-\left[\eta+\left(\frac{\bar{\sigma}}{2}+\kappa_H\right)v_k\right]I. ∥ g k ∥ ≤ ( C H + η ) v k + ( 2 σ ˉ + κ g ) v k 2 , H k ⪰ − [ η + ( 2 σ ˉ + κ H ) v k ] I .
Theorem 6.2(iii) gives v k → 0 v_k\to0 v k → 0 , and hence g k → 0 g^k\to0 g k → 0 . By the continuity of the restricted Hessian, H k → ∇ S ˉ 2 F ( x ˉ ) H^k\to\nabla^2_{\bar{S}}F(\bar{x}) H k → ∇ S ˉ 2 F ( x ˉ ) , which yields the asserted Hessian inequality. To justify the gradient conclusion, fix a unit vector v \mathbf{v} v supported on S ˉ \bar{S} S ˉ . For sufficiently small t > 0 t>0 t > 0 , Taylor’s theorem gives F ( x ˉ + t v ) ≤ F ( x ˉ ) + t ⟨ g k , v S ˉ ⟩ + C H t 2 / 2 F(\bar{x}+t\mathbf{v})\le F(\bar{x})+t\langle g^k,\mathbf{v}_{\bar{S}}\rangle+C_Ht^2/2 F ( x ˉ + t v ) ≤ F ( x ˉ ) + t ⟨ g k , v S ˉ ⟩ + C H t 2 /2 . The global convergence analysis gives F ( x k ) → F ( x ˉ ) F(x^k)\to F(\bar{x}) F ( x k ) → F ( x ˉ ) . Using lower semicontinuity and g k → 0 g^k\to0 g k → 0 , we obtain F ( x ˉ + t v ) ≤ F ( x ˉ ) + C H t 2 / 2 F(\bar{x}+t\mathbf{v})\le F(\bar{x})+C_Ht^2/2 F ( x ˉ + t v ) ≤ F ( x ˉ ) + C H t 2 /2 . Divide by t t t and let t ↓ 0 t\downarrow0 t ↓ 0 . Repeating the argument with − v -\mathbf{v} − v proves ∇ S ˉ F ( x ˉ ) = 0 \nabla_{\bar{S}}F(\bar{x})=0 ∇ S ˉ F ( x ˉ ) = 0 . □
Let g y k = ∇ S ˉ F ( y k ) g_y^k=\nabla_{\bar{S}}F(y^k) g y k = ∇ S ˉ F ( y k ) and H y k = ∇ S ˉ 2 F ( y k ) H_y^k=\nabla_{\bar{S}}^2F(y^k) H y k = ∇ S ˉ 2 F ( y k ) . The following result bounds the number of outer iterations in a fixed run after the selected subspace has stabilized and full steps are accepted.
Theorem 6.5 Suppose that the assumptions of Corollary 6.4 hold. Define
A = M ( x ˉ ) + σ ˉ + 2 κ g , B = 3 2 M ( x ˉ ) + σ ˉ + κ g + κ H . A=M(\bar{x})+\bar{\sigma}+2\kappa_g,\qquad B=\frac{3}{2}M(\bar{x})+\bar{\sigma}+\kappa_g+\kappa_H. A = M ( x ˉ ) + σ ˉ + 2 κ g , B = 2 3 M ( x ˉ ) + σ ˉ + κ g + κ H . Given ε g , ε H > 0 \varepsilon_g,\varepsilon_H>0 ε g , ε H > 0 , suppose that the parameter η \eta η satisfies
0 < η ≤ min { A ε g 3 , A ε H 3 B } . 0<\eta\le\min\left\{\frac{\sqrt{A\varepsilon_g}}{3},\frac{A\sqrt{\varepsilon_H}}{3B}\right\}. 0 < η ≤ min { 3 A ε g , 3 B A ε H } . Let T T T be the first k ≥ K ^ k\ge\widehat{K} k ≥ K for which ∥ g y k ∥ ≤ ε g \lVert g_y^k\rVert\le\varepsilon_g ∥ g y k ∥ ≤ ε g and λ min ( H y k ) ≥ − ε H \lambda_{\min}(H_y^k)\ge-\sqrt{\varepsilon_H} λ m i n ( H y k ) ≥ − ε H . Then T T T is finite and
T − K ^ ≤ ⌈ 6 ( F ( x K ^ ) − F ˉ ) c min { ε g / A , ε H / B 3 } ⌉ . (32) T-\widehat{K}\le\left\lceil\frac{6(F(x^{\widehat{K}})-\bar{F})}{c\min\{\sqrt{\varepsilon_g/A},\sqrt{\varepsilon_H/B^3}\}}\right\rceil. \tag*{(32)} T − K ≤ ⌈ c min { ε g / A , ε H / B 3 } 6 ( F ( x K ) − F ˉ ) ⌉ . (32)
Proof. By Theorems 4.8 and 6.2, we have x k → x ˉ x^k\to\bar{x} x k → x ˉ , d k → 0 d^k\to0 d k → 0 , and β k = 1 \beta_k=1 β k = 1 for all sufficiently large k k k . Recall v k = ∥ d k ∥ v_k=\lVert d^k\rVert v k = ∥ d k ∥ . By (6.1) and conditions (3.3c)–(3.3d), we obtain
∥ g y k ∥ ≤ ( M ( x ˉ ) + σ ˉ 2 + κ g ) v k 2 + 3 η 2 v k , \lVert g_y^k\rVert\le\left(\frac{M(\bar{x})+\bar{\sigma}}{2}+\kappa_g\right)v_k^2+\frac{3\eta}{2}v_k, ∥ g y k ∥ ≤ ( 2 M ( x ˉ ) + σ ˉ + κ g ) v k 2 + 2 3 η v k ,
H y k ⪰ − [ 3 η 2 + ( M ( x ˉ ) + σ ˉ 2 + κ H ) v k ] I . H_y^k\succeq-\left[\frac{3\eta}{2}+\left(M(\bar{x})+\frac{\bar{\sigma}}{2}+\kappa_H\right)v_k\right]I. H y k ⪰ − [ 2 3 η + ( M ( x ˉ ) + 2 σ ˉ + κ H ) v k ] I .
If v k ≤ 3 η / A v_k\le3\eta/A v k ≤ 3 η / A , these estimates imply
∥ g y k ∥ ≤ 9 η 2 A ≤ ε g , H y k ⪰ − 3 η B A I ⪰ − ε H I , \lVert g_y^k\rVert\le\frac{9\eta^2}{A}\le\varepsilon_g,\qquad H_y^k\succeq-\frac{3\eta B}{A}I\succeq-\sqrt{\varepsilon_H}I, ∥ g y k ∥ ≤ A 9 η 2 ≤ ε g , H y k ⪰ − A 3 η B I ⪰ − ε H I ,
which implies y k y^k y k is already an ( ε g , ε H ) (\varepsilon_g,\varepsilon_H) ( ε g , ε H ) -approximate second-order stationary point on S ˉ : = supp ( x ˉ ) \bar{S}:=\operatorname{supp}(\bar{x}) S ˉ := supp ( x ˉ ) . Otherwise η < A v k / 3 \eta<Av_k/3 η < A v k /3 , so
∥ g y k ∥ < A v k 2 , H y k ⪰ − B v k I . \lVert g_y^k\rVert<Av_k^2,\qquad H_y^k\succeq-Bv_kI. ∥ g y k ∥ < A v k 2 , H y k ⪰ − B v k I .
Consequently, every iteration not yet satisfying the target tolerances satisfies v k > δ : = min { ε g / A , ε H / B } v_k > \delta:= \min\{\sqrt{\varepsilon_g}/A,\sqrt{\varepsilon_H}/B\} v k > δ := min { ε g / A , ε H / B } . This follows from the gradient bound if the gradient test fails, and from the Hessian bound if the curvature test fails. Since the full Newton step is accepted for all k ≥ K ^ k \ge\widehat{K} k ≥ K , the subsequent proximal-gradient and subspace cubic Newton steps yield
F ( x k + 1 ) ≤ F ( y k ) ≤ F ( x k ) − c 6 v k 3 < F ( x k ) − c 6 δ 3 . F(x^{k+1}) \le F(y^k) \le F(x^k) - \frac{c}{6}v_k^3 < F(x^k) - \frac{c}{6}\delta^3. F ( x k + 1 ) ≤ F ( y k ) ≤ F ( x k ) − 6 c v k 3 < F ( x k ) − 6 c δ 3 .
Since F F F is bounded below, the target tolerances must be satisfied after finitely many iterations. Summing the above inequality from k = K ^ k = \widehat{K} k = K to T − 1 T - 1 T − 1 yields (6.3). □ \square □
Numerical Results
In this section, we develop an adaptive variant of HPG-SCN (see Algorithm 3), termed AHPG-SCN. The adaptive variant avoids estimating the local Hessian Lipschitz modulus required to prescribe the cubic regularization parameter. Instead, it updates this parameter using the ratio of actual to predicted reduction.
AHPG-SCN takes a cubic step only if 1 ≤ n k ≤ n max 1 \le n_k \le n_{\max} 1 ≤ n k ≤ n m a x .
The ratio ρ k = ( F ( x k ) − F ( y k ) ) / ( F ( x k ) − m k ( β k d k ) ) \rho_k = (F(x^k) - F(y^k))/(F(x^k) - m_k(\beta_k d^k)) ρ k = ( F ( x k ) − F ( y k )) / ( F ( x k ) − m k ( β k d k )) compares actual and predicted reductions [11 ] . The method decreases σ k \sigma_k σ k if ρ k ≥ η 2 \rho_k \ge\eta_2 ρ k ≥ η 2 , and rejects the step and increases σ k \sigma_k σ k if ρ k ≤ η 1 \rho_k \le\eta_1 ρ k ≤ η 1 , subject to the prescribed bounds. For 0 < η 1 < ρ k < η 2 < 1 0 < \eta_1 < \rho_k < \eta_2 < 1 0 < η 1 < ρ k < η 2 < 1 , σ k \sigma_k σ k stays fixed.
The convergence and complexity results proved for HPG-SCN do not automatically apply to AHPG-SCN, and its theoretical convergence analysis is left for future work.
To evaluate the numerical performance of HPG-SCN and AHPG-SCN, we compare them with ZeroFPR, ManAcc, and HpgSRN. The basic algorithmic settings are summarized below, with the parameters of our proposed methods tuned manually.
ZeroFPR. We follow the algorithm and BFGS update given by (5.9) in [42 ] , using the publicly available MATLAB implementation from the ForBES package1 with its default algorithmic parameters.
ManAcc. We follow Algorithms 1 and 3 of [3 ] . Since the authors’ implementation is available in Julia2 , we reimplement the method in MATLAB. We use the truncated Newton variant and retain the original parameter settings. The only modification is the use of the shifted Hessian H k + η I H^k + \eta I H k + η I , with η = 10 − 3 \eta= 10^{-3} η = 1 0 − 3 , to improve numerical stability.
HpgSRN. We follow Algorithm 3.2 of [45 ] , using the authors’ publicly available MATLAB code3 with its default algorithmic parameters.
Algorithm 3 Adaptive hybrid proximal-gradient and subspace cubic-Newton method (AHPG-SCN) for (1.1)
Require: x 0 = y 0 ∈ dom F x^0 = y^0 \in\operatorname{dom} F x 0 = y 0 ∈ dom F , 0 < α 0 < α ‾ < λ g 0 < \alpha_0 < \overline{\alpha} < \lambda_g 0 < α 0 < α < λ g , c c c , c 1 > 0 c_1 > 0 c 1 > 0 , η > 0 \eta> 0 η > 0 , q q q , q 1 ∈ ( 0 , 1 ) q_1 \in(0,1) q 1 ∈ ( 0 , 1 ) , ε k > 0 \varepsilon_k > 0 ε k > 0 , 0 < η 1 < η 2 < 1 0 < \eta_1 < \eta_2 < 1 0 < η 1 < η 2 < 1 , 0 < γ 1 < 1 < γ 2 0 < \gamma_1 < 1 < \gamma_2 0 < γ 1 < 1 < γ 2 , 0 < σ min ≤ σ 1 ≤ σ max 0 < \sigma_{\min} \le\sigma_1 \le\sigma_{\max} 0 < σ m i n ≤ σ 1 ≤ σ m a x , n max > 0 n_{\max} > 0 n m a x > 0 , κ g \kappa_g κ g , κ H ≥ 0 \kappa_H \ge0 κ H ≥ 0 , InnerMaxIt, MaxIt.
for k = 1 , 2 , … , MaxIt k = 1,2,\ldots,\text{MaxIt} k = 1 , 2 , … , MaxIt do
Proximal-gradient step.
Set α k , 0 \alpha_{k,0} α k , 0 according to (3.1).
for l k = 0 , 1 , 2 , … l_k = 0,1,2,\ldots l k = 0 , 1 , 2 , … do
Compute x k , l k ∈ Prox α k , l k ( y k − 1 − α k , l k ∇ h ( y k − 1 ) ) x^{k,l_k} \in\operatorname{Prox}_{\alpha_{k,l_k}}\left(y^{k-1} - \alpha_{k,l_k}\nabla h(y^{k-1})\right) x k , l k ∈ Prox α k , l k ( y k − 1 − α k , l k ∇ h ( y k − 1 ) ) .
if F ( x k , l k ) ≤ F ( y k − 1 ) − c 1 ∥ x k , l k − y k − 1 ∥ 2 F(x^{k,l_k}) \le F(y^{k-1}) - c_1\lVert x^{k,l_k} - y^{k-1}\rVert^2 F ( x k , l k ) ≤ F ( y k − 1 ) − c 1 ∥ x k , l k − y k − 1 ∥ 2 then
Set x k = x k , l k x^k = x^{k,l_k} x k = x k , l k and α k = α k , l k \alpha_k = \alpha_{k,l_k} α k = α k , l k ; break.
else
Set α k , l k + 1 = q 1 α k , l k \alpha_{k,l_k+1} = q_1\alpha_{k,l_k} α k , l k + 1 = q 1 α k , l k .
end if
end for
Coordinate selection.
Set S k : = { i : ∣ x i k ∣ ≥ ε k } S^k := \{i : |x_i^k| \ge\varepsilon_k\} S k := { i : ∣ x i k ∣ ≥ ε k } and n k : = # ( S k ) n_k := \#(S^k) n k := # ( S k ) .
if S k ≠ ∅ S^k \ne\emptyset S k = ∅ and n k ≤ n max n_k \le n_{\max} n k ≤ n m a x then
Subspace cubic-Newton step.
Compute g k = ∇ S k F ( x k ) g^k = \nabla_{S^k}F(x^k) g k = ∇ S k F ( x k ) and H k = ∇ S k 2 F ( x k ) H^k = \nabla^2_{S^k}F(x^k) H k = ∇ S k 2 F ( x k ) .
Compute an approximate solution d k d^k d k of (3.2) satisfying (3.3a)–(3.3d).
Backtracking line search.
Set β k , 0 = 1 \beta_{k,0} = 1 β k , 0 = 1 and Tag = 0 = 0 = 0 .
for j k = 0 , 1 , 2 , … , InnerMaxIt j_k = 0,1,2,\ldots,\text{InnerMaxIt} j k = 0 , 1 , 2 , … , InnerMaxIt do
Define y S k k , j k = x S k k + β k , j k d k y_{S^k}^{k,j_k} = x_{S^k}^k + \beta_{k,j_k}d^k y S k k , j k = x S k k + β k , j k d k , y ( S k ) c k , j k = x ( S k ) c k y_{(S^k)^c}^{k,j_k} = x_{(S^k)^c}^k y ( S k ) c k , j k = x ( S k ) c k .
if F ( y k , j k ) ≤ F ( x k ) − η 2 ∥ y k , j k − x k ∥ 2 − σ k 6 ∥ y k , j k − x k ∥ 3 F(y^{k,j_k}) \le F(x^k) - \frac{\eta}{2}\lVert y^{k,j_k} - x^k\rVert^2 - \frac{\sigma_k}{6}\lVert y^{k,j_k} - x^k\rVert^3 F ( y k , j k ) ≤ F ( x k ) − 2 η ∥ y k , j k − x k ∥ 2 − 6 σ k ∥ y k , j k − x k ∥ 3 then
Set y k = y k , j k y^k = y^{k,j_k} y k = y k , j k , β k = β k , j k \beta_k = \beta_{k,j_k} β k = β k , j k , and Tag = 1 = 1 = 1 ; break.
else
Set β k , j k + 1 = q β k , j k \beta_{k,j_k+1} = q\beta_{k,j_k} β k , j k + 1 = q β k , j k .
end if
end for
if Tag = 1 = 1 = 1 then
Adaptive regularization update.
Define m k ( d ) = F ( x k ) + ⟨ g k , d ⟩ + 1 2 ⟨ ( H k + η I ) d , d ⟩ + σ k 6 ∥ d ∥ 3 m_k(d) = F(x^k) + \langle g^k,d\rangle+ \frac{1}{2}\langle(H^k+\eta I)d,d\rangle+ \frac{\sigma_k}{6}\lVert d\rVert^3 m k ( d ) = F ( x k ) + ⟨ g k , d ⟩ + 2 1 ⟨( H k + η I ) d , d ⟩ + 6 σ k ∥ d ∥ 3 .
if d k = 0 d^k = 0 d k = 0 then
Set y k = x k y^k = x^k y k = x k and σ k + 1 = σ k \sigma_{k+1} = \sigma_k σ k + 1 = σ k .
else
Compute ρ k = ( F ( x k ) − F ( y k ) ) / ( F ( x k ) − m k ( β k d k ) ) \rho_k = (F(x^k)-F(y^k))/(F(x^k)-m_k(\beta_kd^k)) ρ k = ( F ( x k ) − F ( y k )) / ( F ( x k ) − m k ( β k d k )) .
if ρ k ≥ η 2 \rho_k \ge\eta_2 ρ k ≥ η 2 then
Set σ k + 1 = max { σ min , γ 1 σ k } \sigma_{k+1} = \max\{\sigma_{\min},\gamma_1\sigma_k\} σ k + 1 = max { σ m i n , γ 1 σ k } .
else if ρ k ≤ η 1 \rho_k \le\eta_1 ρ k ≤ η 1 then
Set σ k + 1 = min { σ max , γ 2 σ k } \sigma_{k+1} = \min\{\sigma_{\max},\gamma_2\sigma_k\} σ k + 1 = min { σ m a x , γ 2 σ k } and y k = x k y^k = x^k y k = x k .
else
Set σ k + 1 = σ k \sigma_{k+1} = \sigma_k σ k + 1 = σ k .
end if
end if
else
Set σ k + 1 = min { σ max , γ 2 σ k } \sigma_{k+1} = \min\{\sigma_{\max},\gamma_2\sigma_k\} σ k + 1 = min { σ m a x , γ 2 σ k } and y k = x k y^k = x^k y k = x k .
end if
else
Set y k = x k y^k = x^k y k = x k and σ k + 1 = σ k \sigma_{k+1} = \sigma_k σ k + 1 = σ k .
end if
if the termination criterion is satisfied then
break.
end if
end for
Output: y k y^k y k .
HPG-SCN. We set α 0 = 0.95 / L \alpha_0 = 0.95/L α 0 = 0.95/ L , α ˉ = 10 6 \bar{\alpha} = 10^6 α ˉ = 1 0 6 , c = c 1 = 10 − 3 c = c_1 = 10^{-3} c = c 1 = 1 0 − 3 , η = 10 − 10 \eta= 10^{-10} η = 1 0 − 10 , q = q 1 = 0.5 q = q_1 = 0.5 q = q 1 = 0.5 , and κ g = κ H = 10 − 2 \kappa_g = \kappa_H = 10^{-2} κ g = κ H = 1 0 − 2 . The cubic regularization parameter is chosen as σ k = 0.67 ( M ( x k ) + c ) \sigma_k = 0.67(M(x^k) + c) σ k = 0.67 ( M ( x k ) + c ) . The Lanczos solver uses s = 1.5 s = 1.5 s = 1.5 and r k , 0 = ⌈ n k ⌉ r_{k,0} = \lceil\sqrt{n_k}\rceil r k , 0 = ⌈ n k ⌉ . The curvature estimate M ( x k ) M(x^k) M ( x k ) and the threshold parameters C ε C_\varepsilon C ε and q ε q_\varepsilon q ε are specified for each problem.
AHPG-SCN. We use the same settings as HPG-SCN, except that the cubic regularization parameter is updated adaptively. We set η 1 = 0.1 \eta_1 = 0.1 η 1 = 0.1 , η 2 = 0.9 \eta_2 = 0.9 η 2 = 0.9 , γ 1 = 0.5 \gamma_1 = 0.5 γ 1 = 0.5 , γ 2 = 2 \gamma_2 = 2 γ 2 = 2 , σ min = 10 − 3 \sigma_{\min} = 10^{-3} σ m i n = 1 0 − 3 , σ 1 = 1 \sigma_1 = 1 σ 1 = 1 , σ max = 10 3 \sigma_{\max} = 10^3 σ m a x = 1 0 3 , and InnerMaxIt = 50 \text{InnerMaxIt} = 50 InnerMaxIt = 50 . The maximum subspace dimension n max n_{\max} n m a x is specified in each experiment.
These algorithms are selected because they combine proximal-gradient-type steps with second-order or quasi-Newton acceleration. ZeroFPR employs quasi-Newton directions based on the forward–backward envelope, while ManAcc combines proximal-gradient steps with Riemannian Newton-type acceleration on an identified manifold. For the sparse models considered here, the manifold is determined by the current support. HpgSRN combines proximal-gradient steps with subspace regularized Newton steps and is specifically designed for nonconvex L p L_p L p -regularized optimization. As in [45 ] , we define
Res ( x ) : = γ r e s dist ∞ ( x , prox g / γ r e s ( x − γ r e s − 1 ∇ h ( x ) ) ) . \operatorname{Res}(x) := \gamma_{\mathrm{res}} \operatorname{dist}_{\infty}\left(x,\operatorname{prox}_{g/\gamma_{\mathrm{res}}}\left(x-\gamma_{\mathrm{res}}^{-1}\nabla h(x)\right)\right). Res ( x ) := γ res dist ∞ ( x , prox g / γ res ( x − γ res − 1 ∇ h ( x ) ) ) .
where γ r e s = L 0.95 \gamma_{\mathrm{res}} = \frac{L}{0.95} γ res = 0.95 L , and dist ∞ \operatorname{dist}_{\infty} dist ∞ denotes the distance induced by the infinity norm. All solvers use the same stopping rule. A run stops when one of the following holds.
Res ( x ) < 10 − 8 , k ≥ MaxIt , or CPU time > 200 seconds , \operatorname{Res}(x) < 10^{-8}, \quad k \geq\operatorname{MaxIt}, \quad\text{or} \quad\text{CPU time} > 200\text{ seconds}, Res ( x ) < 1 0 − 8 , k ≥ MaxIt , or CPU time > 200 seconds ,
where MaxIt = 10 5 \operatorname{MaxIt} = 10^5 MaxIt = 1 0 5 . We report means over 20 independent trials.
Known KL Exponent
We test the two threshold rules on the following problem.
min x ∈ R n F ( x ) : = ∑ i = 1 n ( log ( 1 + ( x i − b i ) 4 ) − x i ) + ∥ x ∥ 1 , \min_{x\in\mathbb{R}^n} F(x) := \sum_{i=1}^{n}\left(\log\left(1+(x_i-b_i)^4\right)-x_i\right)+\lVert x\rVert_1, x ∈ R n min F ( x ) := i = 1 ∑ n ( log ( 1 + ( x i − b i ) 4 ) − x i ) + ∥ x ∥ 1 ,
where b ∈ { 0 , 1 } n b \in\{0,1\}^n b ∈ { 0 , 1 } n contains both zero and nonzero components. The objective F F F is coercive and admits a unique global solution x ˉ = b \bar{x} = b x ˉ = b , which is also its unique critical point. Taking g ( x ) = ∥ x ∥ 1 g(x) = \lVert x\rVert_1 g ( x ) = ∥ x ∥ 1 and h ( x ) = ∑ i = 1 n ( log ( 1 + ( x i − b i ) 4 ) − x i ) h(x) = \sum_{i=1}^{n}\left(\log\left(1+(x_i-b_i)^4\right)-x_i\right) h ( x ) = ∑ i = 1 n ( log ( 1 + ( x i − b i ) 4 ) − x i ) , we can verify that F F F satisfies Assumption 1.1 with L < 4 L < 4 L < 4 and lip M x ∇ S 2 F ( x ) < 9 \operatorname{lip}_{M_x}\nabla^2_S F(x) < 9 lip M x ∇ S 2 F ( x ) < 9 for any x ≠ 0 x \ne0 x = 0 and ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S \subseteq\operatorname{supp}(x) ∅ = S ⊆ supp ( x ) . Moreover, F F F has the KL property at x ˉ \bar{x} x ˉ with exponent θ = 3 / 4 \theta= 3/4 θ = 3/4 , while the standard nondegeneracy condition − ∇ h ( x ˉ ) ∈ ri ∂ g ( x ˉ ) -\nabla h(\bar{x}) \in\operatorname{ri}\partial g(\bar{x}) − ∇ h ( x ˉ ) ∈ ri ∂ g ( x ˉ ) fails (see Proposition A.4 ). We compare the sets selected by the two HPG-SCN threshold rules with the supports of the proximal-gradient iterates. The proximal-gradient baseline uses the update below with a line search (see Section 10.3.3 of [4 ] ).
x k ∈ arg min x { g ( x ) + 1 2 α k ∥ x − ( x k − 1 − α k ∇ h ( x k − 1 ) ) ∥ 2 } \mathbf{x}^{k} \in\mathop{\arg\min}_{x} \left\{g(x) + \frac{1}{2\alpha_k}\left\|x-\left(x^{k-1}-\alpha_k\nabla h(x^{k-1})\right)\right\|^2\right\} x k ∈ arg min x { g ( x ) + 2 α k 1 x − ( x k − 1 − α k ∇ h ( x k − 1 ) ) 2 }
where α k \alpha_k α k is chosen by the same line-search procedure as in HPG-SCN.
We set n = 50 n=50 n = 50 and construct b \mathbf{b} b by setting its first 10 components to one and the remaining components to zero so that S ‾ = [ 10 ] \overline{S}=[10] S = [ 10 ] . We compare PG with HPG-SCN equipped with two thresholding strategies: (i) the KL-exponent-guided power-type threshold ε k = 0.5 ( max { s k , 10 − 8 / ( k + 1 ) } ) γ \varepsilon_k=0.5(\max\{s_k,10^{-8}/(k+1)\})^\gamma ε k = 0.5 ( max { s k , 1 0 − 8 / ( k + 1 )} ) γ , where s k s_k s k is defined in Theorem 5.2 , with γ = 1 / 6 \gamma=1/6 γ = 1/6 ; and (ii) the adaptive threshold ε k = 2 / log 2 ( e + max { s k , 10 − 8 / ( k + 1 ) } − 1 ) \varepsilon_k=2/\log^2(e+\max\{s_k,10^{-8}/(k+1)\}^{-1}) ε k = 2/ log 2 ( e + max { s k , 1 0 − 8 / ( k + 1 ) } − 1 ) .
For both methods, we set α 0 = 1 / 5 \alpha_0=1/5 α 0 = 1/5 . For HPG-SCN, we choose σ k = 0.67 ( M ( x k ) + c ) \sigma_k=0.67(M(x^k)+c) σ k = 0.67 ( M ( x k ) + c ) with M ( x k ) = 9 M(x^k)=9 M ( x k ) = 9 . The initial point is independently sampled from the uniform distribution on [ − 3 , 3 ] [-3,3] [ − 3 , 3 ] .
We record n k n_k n k for HPG-SCN, ∥ x k ∥ 0 \|x^k\|_0 ∥ x k ∥ 0 for PG (also denoted by n k n_k n k ) and the Jaccard index [31 ] J k = ♯ ( S k ∩ S ) / ♯ ( S k ∪ S ) J_k=\sharp(S^k\cap S)/\sharp(S^k\cup S) J k = ♯ ( S k ∩ S ) /♯ ( S k ∪ S ) , where S k = supp ( x k ) S^k=\operatorname{supp}(x^k) S k = supp ( x k ) for PG. Note that J k = 1 J_k=1 J k = 1 if and only if S k = S S^k=S S k = S .
Figure 1 reports the mean selected-set size and Jaccard index over the first 60 iterations. For both the power-type and logarithmic thresholds, the mean selected-set size reaches 10 and the mean Jaccard index reaches 1. This agrees with the result in Theorem 5.2 and its logarithmic-threshold counterpart, which guarantee that S k = S S^k=S S k = S after finitely many iterations, without requiring nondegeneracy. In contrast, PG retains extra nonzero coordinates, and its support does not identify S ‾ \overline{S} S within the reported iterations.
Figure 1. Averaged n k n_k n k and Jaccard index.
Unknown KL Exponent
Sparse Signal Recovery
We consider the ratio-regularized recovery problem
min x ∈ R n λ ∥ x ∥ 1 ∥ x ∥ 2 + 1 2 ∥ A x − b ∥ 2 2 . \min_{x\in\mathbb{R}^{n}} \lambda\frac{\lVert x\rVert_{1}}{\lVert x\rVert_{2}}+\frac{1}{2}\lVert Ax-b\rVert_{2}^{2}. x ∈ R n min λ ∥ x ∥ 2 ∥ x ∥ 1 + 2 1 ∥ A x − b ∥ 2 2 .
With the convention ∥ 0 ∥ 1 / ∥ 0 ∥ 2 = 1 \lVert0\rVert_{1}/\lVert0\rVert_{2}=1 ∥ 0 ∥ 1 / ∥ 0 ∥ 2 = 1 , the objective is proper, lower semicontinuous, and semialgebraic. It therefore satisfies the KL property [2 Theorem 14] .
We consider two types of sensing matrices. (i) Gaussian matrix (Gauss). The rows of A A A are sampled independently from N ( 0 , Σ ) \mathcal{N}(0,\Sigma) N ( 0 , Σ ) , where Σ = ( 1 − r ) I n + r 1 n 1 n T \Sigma=(1-r)I_n+r\mathbf{1}_n\mathbf{1}_n^{\mathsf{T}} Σ = ( 1 − r ) I n + r 1 n 1 n T . (ii) Oversampled DCT matrix (ODCT). Here A = [ a 1 , a 2 , … , a n ] ∈ R m × n A=[\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_n]\in\mathbb{R}^{m\times n} A = [ a 1 , a 2 , … , a n ] ∈ R m × n with each column
a j : = 1 m cos ( 2 π w j G ) , j = 1 , … , n , \mathbf{a}_j:=\frac{1}{\sqrt{m}}\cos\left(\frac{2\pi wj}{G}\right),\quad j=1,\ldots,n, a j := m 1 cos ( G 2 π w j ) , j = 1 , … , n ,
where w ∈ R m \mathbf{w}\in\mathbb{R}^{m} w ∈ R m is a random vector with entries uniformly distributed on [ 0 , 1 ] [0,1] [ 0 , 1 ] and G ∈ R + G\in\mathbb{R}_{+} G ∈ R + controls the coherence. A larger value of G G G yields a more coherent matrix A A A . We set m = 64 m=64 m = 64 , n = 1024 n=1024 n = 1024 . The ground truth x ∗ \mathbf{x}^{*} x ∗ is K K K -sparse with K ∈ { 2 , 4 , 6 , 8 , 10 } K\in\{2,4,6,8,10\} K ∈ { 2 , 4 , 6 , 8 , 10 } . The support of x ∗ \mathbf{x}^{*} x ∗ is drawn uniformly among the K K K -element subsets of { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } and its nonzero entries are generated by
x ( s u p p ) = sign ( randn ( K , 1 ) ) ⋅ 1 e 2 ⋅ randn ( K , 1 ) . \mathrm{x}(\mathrm{supp})=\operatorname{sign}(\operatorname{randn}(K,1))\cdot1\mathrm{e}2\cdot\operatorname{randn}(K,1). x ( supp ) = sign ( randn ( K , 1 )) ⋅ 1 e 2 ⋅ randn ( K , 1 ) .
The observation vector is given by b = A x ∗ \mathbf{b}=A\mathbf{x}^{*} b = A x ∗ . We consider two sets of configurations. ODCT: G ∈ { 15 , 20 , 25 } G\in\{15,20,25\} G ∈ { 15 , 20 , 25 } , Gaussian: r ∈ { 0.1 , 0.2 , 0.3 } r\in\{0.1,0.2,0.3\} r ∈ { 0.1 , 0.2 , 0.3 } . We denote them by ( O D C T , K , G ) (\mathrm{ODCT},K,G) ( ODCT , K , G ) and ( G a u s s , K , r ) (\mathrm{Gauss},K,r) ( Gauss , K , r ) , respectively.
We set λ = 10 − 2 \lambda=10^{-2} λ = 1 0 − 2 . For HPG-SCN, we set M ( x k ) = 256 λ ∥ x k ∥ 0 ∥ x k ∥ 3 M(\mathbf{x}^{k})=256\lambda\frac{\sqrt{\lVert\mathbf{x}^{k}\rVert_{0}}}{\lVert\mathbf{x}^{k}\rVert^{3}} M ( x k ) = 256 λ ∥ x k ∥ 3 ∥ x k ∥ 0 (Theorem A.1 permits the choice ω = 256 / 36 > 1 \omega=256/36>1 ω = 256/36 > 1 ). For both HPG-SCN and AHPG-SCN we choose the threshold as ϵ k = C ϵ / log ( e + max { s k , 10 − 8 / ( k + 1 ) } ) q ϵ \epsilon_k=C_{\epsilon}/\log(e+\max\{s_k,10^{-8}/(k+1)\})^{q_{\epsilon}} ϵ k = C ϵ / log ( e + max { s k , 1 0 − 8 / ( k + 1 )} ) q ϵ , with C ϵ = 150 C_{\epsilon}=150 C ϵ = 150 and q ϵ = 5.5 q_{\epsilon}=5.5 q ϵ = 5.5 . We also set n max = n n_{\max}=n n m a x = n . All methods are initialized at the same point, obtained by applying ADMM to the ℓ 1 \ell_{1} ℓ 1 -regularized least-squares problem with λ = 10 − 3 \lambda=10^{-3} λ = 1 0 − 3 .
Figure 2 reports the mean CPU times for ODCT (left) and Gaussian (right) sensing matrices. HPG-SCN and AHPG-SCN require substantially less CPU time than ZeroFPR and ManAcc at every plotted value of G G G and r r r . For ODCT, the CPU times of ZeroFPR and ManAcc increase with G G G , whereas those of HPG-SCN and AHPG-SCN remain relatively stable. In particular, when G = 25 G=25 G = 25 , the proposed methods require approximately 2% of the CPU time of ZeroFPR and 3–5% of that of ManAcc. For Gaussian matrices, the proposed methods also maintain low CPU times across different values of r r r . For example, when r = 0.1 r=0.1 r = 0.1 , their CPU times are approximately 4–5% of that of ZeroFPR and 11–13% of that of ManAcc.
Figure 2. Mean CPU times (seconds) by G G G for ODCT (left) and by r r r for Gaussian matrices (right).
Next, we solve the L 1 / 2 1 / 2 L_{1/2}^{1/2} L 1/2 1/2 -regularized least-squares problem.
min x ∈ R n F ( x ) : = 1 2 ∥ A x − b ∥ 2 + λ ∥ x ∥ 1 2 1 2 \min_{x\in\mathbb{R}^{n}} F(\mathbf{x}) := \frac{1}{2}\lVert A\mathbf{x}-\mathbf{b}\rVert^{2}+\lambda\lVert\mathbf{x}\rVert_{\frac{1}{2}}^{\frac{1}{2}} x ∈ R n min F ( x ) := 2 1 ∥ A x − b ∥ 2 + λ ∥ x ∥ 2 1 2 1
The objective function F F F is continuous and semialgebraic and hence satisfies the KL property [2 Theorem 14] . We test this model on four real-world datasets.
winequality-red: The red-wine subset of the Wine Quality dataset, which predicts wine quality from physicochemical measurements. It contains m = 1599 m=1599 m = 1599 observations and n 0 = 11 n_{0}=11 n 0 = 11 input features.4
pyrim: A quantitative structure–activity relationship regression dataset with m = 74 m=74 m = 74 observations and n 0 = 27 n_{0}=27 n 0 = 27 input features.5
airfoil: The Airfoil Self-Noise dataset, which predicts the scaled sound pressure level from aerodynamic measurements. It contains m = 1503 m=1503 m = 1503 observations and n 0 = 5 n_{0}=5 n 0 = 5 input features.6
mpg: An automobile fuel-consumption dataset with m = 392 m=392 m = 392 observations and n 0 = 7 n_{0}=7 n 0 = 7 input features.7
Because the original datasets have more observations than features, following [18 , 45 ] , we expand the feature space using polynomial terms to obtain the expanded dataset A ∈ R m × n A\in\mathbb{R}^{m\times n} A ∈ R m × n with m < n m<n m < n . Table 2 reports the expanded dimensions.
Table 2. Mean results on four real-world datasets. An asterisk (*) indicates that the method reached the 200-second CPU time limit in at least one trial.
In this model, we set λ = 10 − 4 ∥ A T b ∥ ∞ \lambda=10^{-4}\lVert A^{\mathsf{T}}\mathbf{b}\rVert_{\infty} λ = 1 0 − 4 ∥ A T b ∥ ∞ . For HPG-SCN, we set M ( x k ) = 1.1 3 λ 8 ( min j ∈ S k ∣ x j k ∣ ) − 5 / 2 M(\mathbf{x}^{k})=1.1\frac{3\lambda}{8}\left(\min_{j\in S_{k}}|x_{j}^{k}|\right)^{-5/2} M ( x k ) = 1.1 8 3 λ ( min j ∈ S k ∣ x j k ∣ ) − 5/2 (see Theorem A.2 and it permits ω = 1.1 > 1 \omega=1.1>1 ω = 1.1 > 1 ). For both HPG-SCN and AHPG-SCN, the threshold is given by
ϵ k = C ϵ [ log ( e + max { s k , 10 − 8 k + 1 } − 1 ) ] q ϵ \epsilon_k = \frac{C_\epsilon}{\left[\log\left(e+\max\left\{s_k,\frac{10^{-8}}{k+1}\right\}^{-1}\right)\right]^{q_\epsilon}} ϵ k = [ log ( e + max { s k , k + 1 1 0 − 8 } − 1 ) ] q ϵ C ϵ
with q ϵ = 3 q_\epsilon= 3 q ϵ = 3 and C ϵ = 0.3 C_\epsilon= 0.3 C ϵ = 0.3 . We also set n max = n n_{\max} = n n m a x = n . The initial point is drawn from a standard Gaussian distribution independently in each trial.
Table 2 reports the mean objective value (Obj), number of nonzero entries (NNZ), CPU time, and CPU ratio. We define the CPU ratio by
CPU Ratio : = minimum mean CPU time across methods mean CPU time for the method × 100 % . \text{CPU Ratio} := \frac{\text{minimum mean CPU time across methods}}{\text{mean CPU time for the method}} \times100\%. CPU Ratio := mean CPU time for the method minimum mean CPU time across methods × 100%.
As shown in the table, HPG-SCN achieves the lowest mean CPU time on winequality-red, airfoil, and mpg, while AHPG-SCN is the fastest on pyrim. In particular, on winequality-red, HPG-SCN and AHPG-SCN require only 0.69 and 0.83 seconds, respectively, corresponding to approximately 3.1% and 3.7% of the CPU time of HpgSRN, and less than 0.5% of that of ZeroFPR and ManAcc. Both proposed methods also attain competitive objective values across the four datasets.
Logistic Regression
In this section, we use the L 1 − μ L 2 L_1-\mu L_2 L 1 − μ L 2 -regularized logistic regression model from (2) .
min ( z , u ) ∈ R n × R 1 m ∑ i = 1 m log ( 1 + e − b i ( a i T z + u ) ) + λ ( ∥ z ∥ 1 − μ ∥ z ∥ 2 ) \min_{(z,u)\in\mathbb{R}^{n}\times\mathbb{R}} \frac{1}{m}\sum_{i=1}^{m}\log\left(1+e^{-b_i(\mathbf{a}_i^{\mathsf T}z+u)}\right)+\lambda(\lVert z\rVert_1-\mu\lVert z\rVert_2) ( z , u ) ∈ R n × R min m 1 i = 1 ∑ m log ( 1 + e − b i ( a i T z + u ) ) + λ (∥ z ∥ 1 − μ ∥ z ∥ 2 )
The objective function is both continuous and definable on R n + 1 \mathbb{R}^{n+1} R n + 1 and hence satisfies the KL property [2 Theorem 14] .
We first test on synthetic datasets. For the synthetic-data experiments, we set μ ∈ { 0.5 , 1 } \mu\in\{0.5,1\} μ ∈ { 0.5 , 1 } and λ = 3 × 10 − 3 \lambda=3\times10^{-3} λ = 3 × 1 0 − 3 in (2) . Let A ~ = [ A , e ] ∈ R m × ( n + 1 ) \widetilde{A}=[A,e]\in\mathbb{R}^{m\times(n+1)} A = [ A , e ] ∈ R m × ( n + 1 ) , where e ∈ R m e\in\mathbb{R}^{m} e ∈ R m denotes the vector with all entries equal to one. The logistic loss gradient is Lipschitz continuous with constant L = ∥ A ~ ∥ 2 / ( 4 m ) L=\lVert\widetilde{A}\rVert^2/(4m) L = ∥ A ∥ 2 / ( 4 m ) . For HPG-SCN, we take M ( x k ) = 1.1 B k M(\mathbf{x}^k)=1.1B_k M ( x k ) = 1.1 B k (Theorem A.3 permits ω = 1.1 > 1 \omega=1.1>1 ω = 1.1 > 1 ), where S z k = supp ( z k ) S_z^k=\operatorname{supp}(z^k) S z k = supp ( z k ) and
B k = { M log + 2 λ μ / ( 3 ∥ z k ∥ 2 2 ) , z k ≠ 0 , M log ( = 1 / ( 6 3 ) ) , z k = 0 ( u k ≠ 0 ) , B_k=
\begin{cases}
M_{\log}+2\lambda\mu/(\sqrt{3}\lVert z^k\rVert_2^2), & z^k\ne0,\\
M_{\log}\;(=1/(6\sqrt{3})), & z^k=0\;(u^k\ne0),
\end{cases} B k = { M l o g + 2 λ μ / ( 3 ∥ z k ∥ 2 2 ) , M l o g ( = 1/ ( 6 3 )) , z k = 0 , z k = 0 ( u k = 0 ) ,
M log = 1 6 3 m ∑ i = 1 m ( ∥ a i , S z k ∥ 2 2 + 1 ) 3 / 2 . M_{\log}=\frac{1}{6\sqrt{3m}}\sum_{i=1}^{m}\left(\lVert a_{i,S_z^k}\rVert_2^2+1\right)^{3/2}. M l o g = 6 3 m 1 i = 1 ∑ m ( ∥ a i , S z k ∥ 2 2 + 1 ) 3/2 .
For both HPG-SCN and AHPG-SCN, we choose the threshold ϵ k = C ε / log ( e + max { s k , 10 − 8 / ( k + 1 ) } − 1 ) q ε \epsilon_k=C_\varepsilon/\log\left(e+\max\{s_k,10^{-8}/(k+1)\}^{-1}\right)^{q_\varepsilon} ϵ k = C ε / log ( e + max { s k , 1 0 − 8 / ( k + 1 ) } − 1 ) q ε , with C ε = 3 C_\varepsilon=3 C ε = 3 and q ε = 4 q_\varepsilon=4 q ε = 4 . For AHPG-SCN, we set n max = n n_{\max}=n n m a x = n , the number of features.
Table 3 reports the mean CPU times and CPU ratios of the four methods on synthetic datasets with μ ∈ { 0.5 , 1 } \mu\in\{0.5,1\} μ ∈ { 0.5 , 1 } and n ∈ { 400 , 800 , 1200 , 1600 , 2000 } n\in\{400,800,1200,1600,2000\} n ∈ { 400 , 800 , 1200 , 1600 , 2000 } . AHPG-SCN achieves the lowest mean CPU time in all tested configurations. In particular, for μ = 1 \mu=1 μ = 1 and n = 2000 n=2000 n = 2000 , AHPG-SCN requires only 0.148 seconds, less than 1% of the CPU time of ZeroFPR and ManAcc, while HPG-SCN takes 0.223 seconds. Across all configurations, the CPU ratios of HPG-SCN range from 50.16% to 66.37%, whereas those of ZeroFPR and ManAcc remain below 5%.
Table 3. Average CPU time and CPU Ratio for ZeroFPR, ManAcc, HPG-SCN, and AHPG-SCN with different ( μ , n ) (\mu,n) ( μ , n ) .
We next consider two real-world datasets, each with a training set ( A , b ) ∈ R m × n × R m (A,b)\in\mathbb{R}^{m\times n}\times\mathbb{R}^{m} ( A , b ) ∈ R m × n × R m and an evaluation set ( A t e s t , b t e s t ) ∈ R m t e × n × R m t e (A_{\mathrm{test}},b_{\mathrm{test}})\in\mathbb{R}^{m_{\mathrm{te}}\times n}\times\mathbb{R}^{m_{\mathrm{te}}} ( A test , b test ) ∈ R m te × n × R m te .
duke8 : A binary breast-cancer classification dataset with 44 observations in total and n = 7129 n=7129 n = 7129 gene-expression features. We use all 44 observations for both fitting and evaluation (m t e = m = 44 m_{\mathrm{te}}=m=44 m te = m = 44 ), so the reported accuracy is in-sample.
news209 : The original dataset contains documents from 20 newsgroup categories. For binary classification, we retain only the baseball and hockey categories and randomly split them into training and test sets in an 8:2 ratio. Each sample is normalized to have unit 2-norm. The resulting datasets
contain m = 1595 m=1595 m = 1595 training samples and m t e = 398 m_{\mathrm{te}}=398 m te = 398 test samples, with n = 23416 n=23416 n = 23416 features.
We draw the initial point from a standard Gaussian distribution. We compute the classification accuracy (TEAcc) as follows
T E A c c = # { i : sign ( a t e s t , i T z + u ) = b t e s t , i } m t e . \mathrm{TEAcc}=\frac{\#\{i:\operatorname{sign}(a_{\mathrm{test},i}^{\mathsf{T}}z+u)=b_{\mathrm{test},i}\}}{m_{\mathrm{te}}}. TEAcc = m te # { i : sign ( a test , i T z + u ) = b test , i } .
In model (1.2), we set ( μ , λ , C ε , q ε ) = ( 0.5 , 1.5 × 10 − 2 , 8 , 8 ) (\mu,\lambda,C_{\varepsilon},q_{\varepsilon})=(0.5,1.5\times10^{-2},8,8) ( μ , λ , C ε , q ε ) = ( 0.5 , 1.5 × 1 0 − 2 , 8 , 8 ) and ( 1.0 , 1.5 × 10 − 2 , 8 , 8 ) (1.0,1.5\times10^{-2},8,8) ( 1.0 , 1.5 × 1 0 − 2 , 8 , 8 ) for the duke dataset, and ( μ , λ , C ε , q ε ) = ( 0.5 , 1 × 10 − 3 , 30 , 4 ) (\mu,\lambda,C_{\varepsilon},q_{\varepsilon})=(0.5,1\times10^{-3},30,4) ( μ , λ , C ε , q ε ) = ( 0.5 , 1 × 1 0 − 3 , 30 , 4 ) and ( 1.0 , 1 × 10 − 3 , 30 , 4 ) (1.0,1\times10^{-3},30,4) ( 1.0 , 1 × 1 0 − 3 , 30 , 4 ) for the news20 dataset. The remaining algorithmic parameters are chosen as before.
Figure 3 plots the mean stationarity residual against cumulative CPU time for μ = 1 \mu=1 μ = 1 . On duke, HPG-SCN and AHPG-SCN both reduce the residual to the 10 − 8 10^{-8} 1 0 − 8 range in about 0.1 seconds. On news20, the mean residual of AHPG-SCN reaches the 10 − 8 10^{-8} 1 0 − 8 range in under one second, followed by HPG-SCN. ManAcc takes longer, and ZeroFPR reaches the time limit in at least one trial.
Figure 3. Averaged stationarity residual versus cumulative CPU time for duke (left) and news20 (right).
Table 4 reports the TEAcc, CPU times, and CPU ratios for the four methods with μ ∈ { 0.5 , 1 } \mu\in\{0.5,1\} μ ∈ { 0.5 , 1 } . All methods achieve comparable in-sample accuracies on duke. In particular, for μ = 1 \mu=1 μ = 1 , AHPG-SCN achieves an accuracy of 0.99 in only 0.079 seconds, requiring less than 0.1% of the CPU time of ZeroFPR. On news20, HPG-SCN, AHPG-SCN, and ManAcc achieve an accuracy of 0.89, compared with 0.88 for ZeroFPR. For μ = 1 \mu= 1 μ = 1 , AHPG-SCN requires only 0.554 seconds, approximately 15% and 4% of the CPU times of HPG-SCN and ManAcc, respectively, and ZeroFPR reaches the 200-second time limit in at least one trial.
Table 4. Mean classification accuracy, CPU time, and CPU ratio for comparing algorithms. An asterisk (*) indicates that the CPU-time limit of 200 seconds was reached in at least one trial.
Overall, these numerical results demonstrate the computational efficiency of HPG-SCN and AHPG-SCN across different sparse optimization problems.
Conclusions
Under boundedness and the KL property, HPG-SCN converges to a first-order stationary point. The power and logarithmic thresholds both identify the support of the limit in finitely many iterations when a positive power-type KL exponent exists. In the degenerate example in § 6.1 , the selected set stabilizes while the support of the proximal-gradient iterates does not. Under continuity of the restricted Hessian, the line search eventually accepts full cubic steps. With bounded cubic regularization and tolerance-dependent damping, we bound the number of subsequent outer iterations needed to meet the restricted gradient and curvature tolerances. In the sparse recovery and logistic regression tests, the hybrid methods have the lowest mean CPU time in the reported comparisons.
Conflict of interest The authors declare that there is no conflict of interest related to this work.
Bounds for the Local Restricted Hessian Lipschitz Modulus
Theorem A.1 Let F ( x ) = λ ∥ x ∥ 1 / ∥ x ∥ 2 + 1 2 ∥ A x − b ∥ 2 2 F(x)=\lambda\lVert x\rVert_{1}/\lVert x\rVert_{2}+\frac{1}{2}\lVert Ax-b\rVert_{2}^{2} F ( x ) = λ ∥ x ∥ 1 / ∥ x ∥ 2 + 2 1 ∥ A x − b ∥ 2 2 , with λ > 0 \lambda>0 λ > 0 . For x ≠ 0 x\ne0 x = 0 and S = supp ( x ) S=\operatorname{supp}(x) S = supp ( x ) , the local constant relative to the fixed-support manifold satisfies
lip ∇ S 2 F ( x ) ≤ 36 λ ∥ x ∥ 0 ∥ x ∥ 2 3 . \operatorname{lip}\nabla_{S}^{2}F(x)\le\frac{36\lambda\sqrt{\lVert x\rVert_{0}}}{\lVert x\rVert_{2}^{3}}. lip ∇ S 2 F ( x ) ≤ ∥ x ∥ 2 3 36 λ ∥ x ∥ 0 . Proof. Let s = ∣ S ∣ s=|S| s = ∣ S ∣ and consider the restriction of F F F to the active coordinates, using the same notation for the restricted vector. In a sufficiently small neighborhood of x x x , the signs of the nonzero components remain unchanged. Set a = sign ( x ) a=\operatorname{sign}(x) a = sign ( x ) , r = ∥ x ∥ 2 r=\lVert x\rVert_{2} r = ∥ x ∥ 2 , and u = a T x u=a^{\mathsf{T}}x u = a T x . Since the quadratic loss has a constant Hessian, only the regularization term contributes to its variation. For any direction h ∈ R s h\in\mathbb{R}^{s} h ∈ R s , let α = a T h \alpha=a^{\mathsf{T}}h α = a T h and β = x T h \beta=x^{\mathsf{T}}h β = x T h . Differentiating the Hessian of λ u / r \lambda u/r λ u / r yields
D ( ∇ 2 F ) ( x ) [ h ] = 3 λ β r 5 ( a x T + x a T + u I ) − λ r 3 ( a h T + h a T + α I ) D(\nabla^{2}F)(x)[h]=\frac{3\lambda\beta}{r^{5}}\left(ax^{\mathsf{T}}+xa^{\mathsf{T}}+uI\right)-\frac{\lambda}{r^{3}}\left(ah^{\mathsf{T}}+ha^{\mathsf{T}}+\alpha I\right) D ( ∇ 2 F ) ( x ) [ h ] = r 5 3 λ β ( a x T + x a T + u I ) − r 3 λ ( a h T + h a T + α I ) + 3 λ α r 5 x x T + 3 λ u r 5 ( x h T + h x T ) − 15 λ u β r 7 x x T . \qquad+\frac{3\lambda\alpha}{r^{5}}xx^{\mathsf{T}}+\frac{3\lambda u}{r^{5}}\left(xh^{\mathsf{T}}+hx^{\mathsf{T}}\right)-\frac{15\lambda u\beta}{r^{7}}xx^{\mathsf{T}}. + r 5 3 λ α x x T + r 5 3 λ u ( x h T + h x T ) − r 7 15 λ u β x x T . Using ∥ a ∥ 2 = s \lVert a\rVert_{2}=\sqrt{s} ∥ a ∥ 2 = s , ∣ u ∣ ≤ s r |u|\le\sqrt{s}r ∣ u ∣ ≤ s r , ∣ α ∣ ≤ s ∥ h ∥ 2 |\alpha|\le\sqrt{s}\lVert h\rVert_{2} ∣ α ∣ ≤ s ∥ h ∥ 2 , and ∣ β ∣ ≤ r ∥ h ∥ 2 |\beta|\le r\lVert h\rVert_{2} ∣ β ∣ ≤ r ∥ h ∥ 2 , we obtain
∥ D ( ∇ 2 F ) ( x ) [ h ] ∥ ≤ ( 9 + 3 + 3 + 6 + 15 ) λ s r 3 ∥ h ∥ 2 . \left\lVert D(\nabla^{2}F)(x)[h]\right\rVert\le(9+3+3+6+15)\frac{\lambda\sqrt{s}}{r^{3}}\lVert h\rVert_{2}. D ( ∇ 2 F ) ( x ) [ h ] ≤ ( 9 + 3 + 3 + 6 + 15 ) r 3 λ s ∥ h ∥ 2 . Since the restricted function is C 3 C^{3} C 3 , its local Hessian Lipschitz constant equals the operator norm of D ( ∇ 2 F ) ( x ) D(\nabla^{2}F)(x) D ( ∇ 2 F ) ( x ) . The desired bound follows. □ \square □
Theorem A.2 Let
F ( x ) = λ ∥ x ∥ p p + 1 2 ∥ A x − b ∥ 2 2 , F(x)=\lambda\lVert x\rVert_{p}^{p}+\frac{1}{2}\lVert Ax-b\rVert_{2}^{2}, F ( x ) = λ ∥ x ∥ p p + 2 1 ∥ A x − b ∥ 2 2 , where λ > 0 \lambda>0 λ > 0 and 0 < p < 1 0<p<1 0 < p < 1 . For x ≠ 0 x\ne0 x = 0 and S = supp ( x ) S=\operatorname{supp}(x) S = supp ( x ) , the local constant relative to the fixed-support manifold satisfies
lip ∇ S 2 F ( x ) ≤ λ p ( 1 − p ) ( 2 − p ) ( min i ∈ S ∣ x i ∣ ) 3 − p . \operatorname{lip}\nabla_{S}^{2}F(x)\le\frac{\lambda p(1-p)(2-p)}{\left(\min_{i\in S}|x_i|\right)^{3-p}}. lip ∇ S 2 F ( x ) ≤ ( min i ∈ S ∣ x i ∣ ) 3 − p λ p ( 1 − p ) ( 2 − p ) . Proof. Let s = ∣ S ∣ s=|S| s = ∣ S ∣ and consider the restriction of F F F to the active coordinates, using the same notation for the restricted vector. Since the signs of the nonzero components remain unchanged in a sufficiently small neighborhood of x x x , the restricted function is C 3 C^{3} C 3 , with Hessian
∇ 2 F ( x ) = A S T A S + λ p ( p − 1 ) Diag ( ∣ x i ∣ p − 2 ) i ∈ S . \nabla^{2}F(x)=A_{S}^{\mathsf{T}}A_{S}+\lambda p(p-1)\operatorname{Diag}\left(|x_i|^{p-2}\right)_{i\in S}. ∇ 2 F ( x ) = A S T A S + λ p ( p − 1 ) Diag ( ∣ x i ∣ p − 2 ) i ∈ S . For any direction h ∈ R s h\in\mathbb{R}^{s} h ∈ R s , the directional derivative of the Hessian is
D ( ∇ 2 F ) ( x ) [ h ] = λ p ( p − 1 ) ( p − 2 ) Diag ( sign ( x i ) ∣ x i ∣ p − 3 h i ) i ∈ S . D(\nabla^{2}F)(x)[h]=\lambda p(p-1)(p-2)\operatorname{Diag}\left(\operatorname{sign}(x_i)|x_i|^{p-3}h_i\right)_{i\in S}. D ( ∇ 2 F ) ( x ) [ h ] = λ p ( p − 1 ) ( p − 2 ) Diag ( sign ( x i ) ∣ x i ∣ p − 3 h i ) i ∈ S . Using the spectral norm of a diagonal matrix, we obtain
∥ D ( ∇ 2 F ) ( x ) [ h ] ∥ = λ p ( 1 − p ) ( 2 − p ) max i ∈ S ∣ h i ∣ ∣ x i ∣ 3 − p ≤ λ p ( 1 − p ) ( 2 − p ) ( min i ∈ S ∣ x i ∣ ) 3 − p ∥ h ∥ 2 . \left\lVert D(\nabla^{2}F)(x)[h]\right\rVert=\lambda p(1-p)(2-p)\max_{i\in S}\frac{|h_i|}{|x_i|^{3-p}}\le\frac{\lambda p(1-p)(2-p)}{\left(\min_{i\in S}|x_i|\right)^{3-p}}\lVert h\rVert_{2}. D ( ∇ 2 F ) ( x ) [ h ] = λ p ( 1 − p ) ( 2 − p ) i ∈ S max ∣ x i ∣ 3 − p ∣ h i ∣ ≤ ( min i ∈ S ∣ x i ∣ ) 3 − p λ p ( 1 − p ) ( 2 − p ) ∥ h ∥ 2 . Since the restricted function is C 3 C^{3} C 3 , its local Hessian Lipschitz constant equals the operator norm of D ( ∇ 2 F ) ( x ) D(\nabla^{2}F)(x) D ( ∇ 2 F ) ( x ) . The desired bound follows. □ \square □
Theorem A.3 Let
F ( z , u ) = 1 m ∑ i = 1 m log ( 1 + e − b i ( a i T z + u ) ) + λ ( ∥ z ∥ 1 − μ ∥ z ∥ 2 ) , F(z,u)=\frac{1}{m}\sum_{i=1}^{m}\log(1+e^{-b_i(\mathbf{a}_i^{\mathsf{T}}z+u)})+\lambda(\|z\|_1-\mu\|z\|_2), F ( z , u ) = m 1 i = 1 ∑ m log ( 1 + e − b i ( a i T z + u ) ) + λ ( ∥ z ∥ 1 − μ ∥ z ∥ 2 ) , where b i ∈ { ± 1 } b_i\in\{\pm1\} b i ∈ { ± 1 } and λ , μ > 0 \lambda,\mu>0 λ , μ > 0 . For x = ( z , u ) ≠ 0 \mathbf{x}=(z,u)\ne0 x = ( z , u ) = 0 , put S = supp ( x ) S=\operatorname{supp}(\mathbf{x}) S = supp ( x ) and S z = supp ( z ) S_z=\operatorname{supp}(z) S z = supp ( z ) , and define
M log = 1 6 3 ∑ i = 1 m ( ∥ a i , S z ∥ 2 2 + 1 ) 3 / 2 . M_{\log}=\frac{1}{6\sqrt{3}}\sum_{i=1}^{m}(\|\mathbf{a}_{i,S_z}\|_2^2+1)^{3/2}. M l o g = 6 3 1 i = 1 ∑ m ( ∥ a i , S z ∥ 2 2 + 1 ) 3/2 . Then
lip ∇ S 2 F ( x ) ≤ { M log + 2 λ μ 3 ∥ z ∥ 2 2 , z ≠ 0 , M log ( = 1 / ( 6 3 ) ) , z = 0 ( u ≠ 0 ) . \operatorname{lip}\nabla_S^2F(\mathbf{x})\le
\begin{cases}
M_{\log}+\dfrac{2\lambda\mu}{\sqrt{3}\|z\|_2^2}, & z\ne0,\\
M_{\log}\;(=1/(6\sqrt{3})), & z=0\quad(u\ne0).
\end{cases} lip ∇ S 2 F ( x ) ≤ ⎩ ⎨ ⎧ M l o g + 3 ∥ z ∥ 2 2 2 λ μ , M l o g ( = 1/ ( 6 3 )) , z = 0 , z = 0 ( u = 0 ) .
Proof. Let v i = ( a i , 1 ) S \mathbf{v}_i=(\mathbf{a}_i,1)_S v i = ( a i , 1 ) S be the augmented feature vector restricted to the selected coordinates. Thus the intercept entry is included only when u ≠ 0 u\ne0 u = 0 , and ∥ v i ∥ 2 2 ≤ ∥ a i , S z ∥ 2 2 + 1 \|\mathbf{v}_i\|_2^2\le\|\mathbf{a}_{i,S_z}\|_2^2+1 ∥ v i ∥ 2 2 ≤ ∥ a i , S z ∥ 2 2 + 1 . Put θ i = b i ( a i T z + u ) \theta_i=b_i(\mathbf{a}_i^{\mathsf{T}}z+u) θ i = b i ( a i T z + u ) , σ ( t ) = 1 / ( 1 + e − t ) \sigma(t)=1/(1+e^{-t}) σ ( t ) = 1/ ( 1 + e − t ) and w ( t ) = σ ( t ) ( 1 − σ ( t ) ) w(t)=\sigma(t)(1-\sigma(t)) w ( t ) = σ ( t ) ( 1 − σ ( t )) . For a restricted direction h \mathbf{h} h ,
( D ( ∇ S 2 log ( 1 + e − θ i ) ) [ h ] ) = w ′ ( θ i ) b i ( v i T h ) v i v i T . \left(D(\nabla_S^2\log(1+e^{-\theta_i}))[\mathbf{h}]\right)=w'(\theta_i)b_i(\mathbf{v}_i^{\mathsf{T}}\mathbf{h})\mathbf{v}_i\mathbf{v}_i^{\mathsf{T}}. ( D ( ∇ S 2 log ( 1 + e − θ i )) [ h ] ) = w ′ ( θ i ) b i ( v i T h ) v i v i T .
Maximizing ∣ p ( 1 − p ) ( 1 − 2 p ) ∣ |p(1-p)(1-2p)| ∣ p ( 1 − p ) ( 1 − 2 p ) ∣ over p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] gives sup t ∣ w ′ ( t ) ∣ = 1 / ( 6 3 ) \sup_t|w'(t)|=1/(6\sqrt{3}) sup t ∣ w ′ ( t ) ∣ = 1/ ( 6 3 ) . Hence the logistic part has Hessian derivative norm at most M log ∥ h ∥ 2 M_{\log}\|\mathbf{h}\|_2 M l o g ∥ h ∥ 2 .
If z ≠ 0 z\ne0 z = 0 , let r = ∥ z S z ∥ 2 r=\|z_{S_z}\|_2 r = ∥ z S z ∥ 2 , and let p ≠ 0 \mathbf{p}\ne0 p = 0 . Writing β = z S z T p \beta=z_{S_z}^{\mathsf{T}}\mathbf{p} β = z S z T p , direct differentiation gives
D ( ∇ 2 ∥ z S z ∥ 2 ) [ p ] = − β r 3 I + 3 β r 5 z S z z S z T − 1 r 3 ( z S z p T + p z S z T ) = − ∥ p ∥ 2 r 2 B ( t ) , D(\nabla^2\|z_{S_z}\|_2)[\mathbf{p}]
=-\frac{\beta}{r^3}I+\frac{3\beta}{r^5}z_{S_z}z_{S_z}^{\mathsf{T}}-\frac{1}{r^3}(z_{S_z}\mathbf{p}^{\mathsf{T}}+\mathbf{p}z_{S_z}^{\mathsf{T}})
=-\frac{\|\mathbf{p}\|_2}{r^2}B(t), D ( ∇ 2 ∥ z S z ∥ 2 ) [ p ] = − r 3 β I + r 5 3 β z S z z S z T − r 3 1 ( z S z p T + p z S z T ) = − r 2 ∥ p ∥ 2 B ( t ) ,
where
e = z S z r , v = p ∥ p ∥ 2 , t = e T v , B ( t ) = t I − 3 t e e T + e v T + v e T . \mathbf{e}=\frac{z_{S_z}}{r},\qquad\mathbf{v}=\frac{\mathbf{p}}{\|\mathbf{p}\|_2},\qquad t=\mathbf{e}^{\mathsf{T}}\mathbf{v},\qquad B(t)=tI-3t\mathbf{e}\mathbf{e}^{\mathsf{T}}+\mathbf{e}\mathbf{v}^{\mathsf{T}}+\mathbf{v}\mathbf{e}^{\mathsf{T}}. e = r z S z , v = ∥ p ∥ 2 p , t = e T v , B ( t ) = t I − 3 t e e T + e v T + v e T .
To estimate its spectral norm, we only need to compute the eigenvalues of B ( t ) B(t) B ( t ) . When ∣ t ∣ < 1 |t|<1 ∣ t ∣ < 1 , let
q = v − t e 1 − t 2 . \mathbf{q}=\frac{\mathbf{v}-t\mathbf{e}}{\sqrt{1-t^2}}. q = 1 − t 2 v − t e .
Then e \mathbf{e} e and q \mathbf{q} q are orthonormal, and v = t e + 1 − t 2 q \mathbf{v}=t\mathbf{e}+\sqrt{1-t^2}\mathbf{q} v = t e + 1 − t 2 q . Substituting this decomposition into B ( t ) B(t) B ( t ) gives
B ( t ) = t I − t e e T + 1 − t 2 ( e q T + q e T ) . B(t)=tI-t\mathbf{e}\mathbf{e}^{\mathsf{T}}+\sqrt{1-t^2}(\mathbf{e}\mathbf{q}^{\mathsf{T}}+\mathbf{q}\mathbf{e}^{\mathsf{T}}). B ( t ) = t I − t e e T + 1 − t 2 ( e q T + q e T ) .
Since 4 − 3 t 2 ≥ ∣ t ∣ \sqrt{4-3t^2}\ge|t| 4 − 3 t 2 ≥ ∣ t ∣ , we obtain
∥ B ( t ) ∥ = ∣ t ∣ + 4 − 3 t 2 2 ≤ 2 3 , \|B(t)\|=\frac{|t|+\sqrt{4-3t^2}}{2}\le\frac{2}{\sqrt{3}}, ∥ B ( t ) ∥ = 2 ∣ t ∣ + 4 − 3 t 2 ≤ 3 2 ,
with equality when ∣ t ∣ = 1 / 3 |t|=1/\sqrt{3} ∣ t ∣ = 1/ 3 . The cases ∣ t ∣ = 1 |t|=1 ∣ t ∣ = 1 follow directly, and the same bound holds in dimension one. Consequently,
∥ D ( ∇ 2 ∥ z S z ∥ 2 ) [ p ] ∥ ≤ 2 3 r 2 ∥ p ∥ 2 . \|D(\nabla^2\|z_{S_z}\|_2)[\mathbf{p}]\|\le\frac{2}{\sqrt{3}r^2}\|\mathbf{p}\|_2. ∥ D ( ∇ 2 ∥ z S z ∥ 2 ) [ p ] ∥ ≤ 3 r 2 2 ∥ p ∥ 2 .
Since the L 1 L_1 L 1 term is locally linear on a fixed-support neighborhood, it contributes no Hessian variation. Combining this estimate with the bound for the logistic loss yields
lip M x ∇ S 2 F ( x ) ≤ M log + 2 λ μ 3 ∥ z ∥ 2 2 . \operatorname{lip}_{M_{\mathbf{x}}}\nabla_S^2F(\mathbf{x})\le M_{\log}+\frac{2\lambda\mu}{\sqrt{3}\|z\|_2^2}. lip M x ∇ S 2 F ( x ) ≤ M l o g + 3 ∥ z ∥ 2 2 2 λ μ .
If z = 0 z=0 z = 0 and u ≠ 0 u\ne0 u = 0 , then S = { n + 1 } S=\{n+1\} S = { n + 1 } . The regularizer vanishes on this one-dimensional slice, so only the logistic loss contributes to the Hessian variation. Hence,
lip M x ∇ S 2 F ( x ) ≤ M log = 1 6 3 . \operatorname{lip}_{M_{\mathbf{x}}}\nabla_S^2F(\mathbf{x})\le M_{\log}=\frac{1}{6\sqrt{3}}. lip M x ∇ S 2 F ( x ) ≤ M l o g = 6 3 1 .
:::
Proposition A.4 Consider the function
F ( x ) : = ∑ i = 1 n ( log ( 1 + ( x i − b i ) 4 ) − x i ) + ∥ x ∥ 1 , F(\mathbf{x}) := \sum_{i=1}^{n} \left(\log(1+(x_i-b_i)^4)-x_i\right)+\|\mathbf{x}\|_1, F ( x ) := i = 1 ∑ n ( log ( 1 + ( x i − b i ) 4 ) − x i ) + ∥ x ∥ 1 , Here b ∈ { 0 , 1 } n \mathbf{b}\in\{0,1\}^n b ∈ { 0 , 1 } n has both zero and nonzero entries. Set g ( x ) = ∥ x ∥ 1 g(\mathbf{x})=\|\mathbf{x}\|_1 g ( x ) = ∥ x ∥ 1 and h ( x ) = F ( x ) − g ( x ) h(\mathbf{x})=F(\mathbf{x})-g(\mathbf{x}) h ( x ) = F ( x ) − g ( x ) . Then the following hold:
(i) The point x ˉ = b \bar{\mathbf{x}}=\mathbf{b} x ˉ = b is both the unique critical point and the unique global minimizer of F F F . The function F F F is coercive, and the nondegeneracy condition fails at x ˉ \bar{\mathbf{x}} x ˉ .
(ii) The gradient of h h h is globally Lipschitz continuous with constant L < 4 L<4 L < 4 .
(iii) For any 0 ≠ x ∈ R n \mathbf{0}\ne\mathbf{x}\in\mathbb{R}^n 0 = x ∈ R n and ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}) ∅ = S ⊆ supp ( x ) , it holds that lip M x ∇ S 2 F ( x ) < 9 \operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla^2_SF(\mathbf{x})<9 lip M x ∇ S 2 F ( x ) < 9 .
(iv) F F F satisfies the KL property at x ˉ \bar{\mathbf{x}} x ˉ with exact exponent θ = 3 / 4 \theta=3/4 θ = 3/4 .
Proof (i) Let ϕ ( t ) = log ( 1 + t 4 ) \phi(t)=\log(1+t^4) ϕ ( t ) = log ( 1 + t 4 ) . First note that F ( x ) ≥ 0 F(\mathbf{x})\ge0 F ( x ) ≥ 0 and equality holds if and only if x = b \mathbf{x}=\mathbf{b} x = b . Thus, x ˉ = b \bar{\mathbf{x}}=\mathbf{b} x ˉ = b is the unique global minimizer, with F ( x ˉ ) = 0 F(\bar{\mathbf{x}})=0 F ( x ˉ ) = 0 . Coercivity follows from F ( x ) ≥ log ( 1 + ∥ x − b ∥ ∞ 4 ) F(\mathbf{x})\ge\log(1+\|\mathbf{x}-\mathbf{b}\|_\infty^4) F ( x ) ≥ log ( 1 + ∥ x − b ∥ ∞ 4 ) . At x ˉ = b \bar{\mathbf{x}}=\mathbf{b} x ˉ = b , every component of − ∇ h ( x ˉ ) -\nabla h(\bar{\mathbf{x}}) − ∇ h ( x ˉ ) equals 1 1 1 . For each i i i with b i = 0 b_i=0 b i = 0 , the i i i th coordinate of ∂ g ( x ˉ ) \partial g(\bar{\mathbf{x}}) ∂ g ( x ˉ ) ranges over ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) . Thus the nondegeneracy condition fails. To show that x ˉ \bar{\mathbf{x}} x ˉ is also the unique critical point, observe that
∂ i F ( x ) = { { ϕ ′ ( x i − b i ) } , x i > 0 , [ ϕ ′ ( − b i ) − 2 , ϕ ′ ( − b i ) ] , x i = 0 , { ϕ ′ ( x i − b i ) − 2 } , x i < 0. \partial_iF(\mathbf{x})=
\begin{cases}
\{\phi'(x_i-b_i)\}, & x_i>0,\\
[\phi'(-b_i)-2,\phi'(-b_i)], & x_i=0,\\
\{\phi'(x_i-b_i)-2\}, & x_i<0.
\end{cases} ∂ i F ( x ) = ⎩ ⎨ ⎧ { ϕ ′ ( x i − b i )} , [ ϕ ′ ( − b i ) − 2 , ϕ ′ ( − b i )] , { ϕ ′ ( x i − b i ) − 2 } , x i > 0 , x i = 0 , x i < 0.
Since
ϕ ′ ( t ) = 4 t 3 1 + t 4 , \phi'(t)=\frac{4t^3}{1+t^4}, ϕ ′ ( t ) = 1 + t 4 4 t 3 ,
we have ϕ ′ ( t ) = 0 \phi'(t)=0 ϕ ′ ( t ) = 0 if and only if t = 0 t=0 t = 0 . If x i > 0 x_i>0 x i > 0 , the condition 0 ∈ ∂ i F ( x ) 0\in\partial_iF(\mathbf{x}) 0 ∈ ∂ i F ( x ) implies x i = b i = 1 x_i=b_i=1 x i = b i = 1 . If x i < 0 x_i<0 x i < 0 , then ϕ ′ ( x i − b i ) − 2 < 0 \phi'(x_i-b_i)-2<0 ϕ ′ ( x i − b i ) − 2 < 0 , so this condition cannot hold. If x i = 0 x_i=0 x i = 0 , then 0 ∈ ∂ i F ( x ) 0\in\partial_iF(\mathbf{x}) 0 ∈ ∂ i F ( x ) if and only if b i = 0 b_i=0 b i = 0 . Consequently, 0 ∈ ∂ F ( x ) 0\in\partial F(\mathbf{x}) 0 ∈ ∂ F ( x ) if and only if x = b \mathbf{x}=\mathbf{b} x = b , proving (i).
(ii) Next, direct computation gives
ϕ ′ ′ ( t ) = 4 t 2 ( 3 − t 4 ) ( 1 + t 4 ) 2 , ϕ ′ ′ ′ ( t ) = 8 t ( t 8 − 12 t 4 + 3 ) ( 1 + t 4 ) 3 . \phi''(t)=\frac{4t^2(3-t^4)}{(1+t^4)^2},\qquad
\phi'''(t)=\frac{8t(t^8-12t^4+3)}{(1+t^4)^3}. ϕ ′′ ( t ) = ( 1 + t 4 ) 2 4 t 2 ( 3 − t 4 ) , ϕ ′′′ ( t ) = ( 1 + t 4 ) 3 8 t ( t 8 − 12 t 4 + 3 ) .
The nonzero critical points of ϕ ′ ′ \phi'' ϕ ′′ satisfy t 4 = 6 ± 33 t^4=6\pm\sqrt{33} t 4 = 6 ± 33 , while those of ϕ ′ ′ ′ \phi''' ϕ ′′′ satisfy t 4 ∈ { 1 , 15 − 4 14 , 15 + 4 14 } t^4\in\{1,15-4\sqrt{14},15+4\sqrt{14}\} t 4 ∈ { 1 , 15 − 4 14 , 15 + 4 14 } . Evaluating the derivatives at these points yields
sup t ∈ R ∣ ϕ ′ ′ ( t ) ∣ < 4 , sup t ∈ R ∣ ϕ ′ ′ ′ ( t ) ∣ < 9. \sup_{t\in\mathbb{R}}|\phi''(t)|<4,\qquad
\sup_{t\in\mathbb{R}}|\phi'''(t)|<9. t ∈ R sup ∣ ϕ ′′ ( t ) ∣ < 4 , t ∈ R sup ∣ ϕ ′′′ ( t ) ∣ < 9.
Since
∇ 2 h ( x ) = Diag ( ϕ ′ ′ ( x i − b i ) ) i = 1 n , \nabla^2h(\mathbf{x})=\operatorname{Diag}\left(\phi''(x_i-b_i)\right)_{i=1}^n, ∇ 2 h ( x ) = Diag ( ϕ ′′ ( x i − b i ) ) i = 1 n ,
we have
∥ ∇ 2 h ( x ) ∥ ≤ sup t ∈ R ∣ ϕ ′ ′ ( t ) ∣ < 4. \|\nabla^2h(\mathbf{x})\|\le\sup_{t\in\mathbb{R}}|\phi''(t)|<4. ∥ ∇ 2 h ( x ) ∥ ≤ t ∈ R sup ∣ ϕ ′′ ( t ) ∣ < 4.
Thus, ∇ h \nabla h ∇ h is globally Lipschitz continuous with constant L < 4 L<4 L < 4 , proving (ii).
(iii) Fix 0 ≠ x ∈ R n \mathbf{0}\ne\mathbf{x}\in\mathbb{R}^n 0 = x ∈ R n and ∅ ≠ S ⊆ supp ( x ) \varnothing\ne S\subseteq\operatorname{supp}(\mathbf{x}) ∅ = S ⊆ supp ( x ) . Since g g g is locally linear along M x \mathcal{M}_{\mathbf{x}} M x , we have
∇ S 2 F ( z ) = Diag ( ϕ ′ ′ ( z i − b i ) ) i ∈ S \nabla_S^2F(\mathbf{z})=\operatorname{Diag}\left(\phi''(z_i-b_i)\right)_{i\in S} ∇ S 2 F ( z ) = Diag ( ϕ ′′ ( z i − b i ) ) i ∈ S
for z ∈ M x \mathbf{z}\in\mathcal{M}_{\mathbf{x}} z ∈ M x sufficiently close to x \mathbf{x} x . By the mean value theorem, for any such z , w \mathbf{z},\mathbf{w} z , w ,
∥ ∇ S 2 F ( z ) − ∇ S 2 F ( w ) ∥ ≤ sup t ∈ R ∣ ϕ ′ ′ ′ ( t ) ∣ ∥ z − w ∥ ≤ 9 ∥ z − w ∥ . \left\|\nabla_S^2F(\mathbf{z})-\nabla_S^2F(\mathbf{w})\right\|
\le\sup_{t\in\mathbb{R}}|\phi'''(t)|\|\mathbf{z}-\mathbf{w}\|
\le9\|\mathbf{z}-\mathbf{w}\|. ∇ S 2 F ( z ) − ∇ S 2 F ( w ) ≤ t ∈ R sup ∣ ϕ ′′′ ( t ) ∣∥ z − w ∥ ≤ 9∥ z − w ∥.
Hence, lip M x ∇ S 2 F ( x ) ≤ 9 \operatorname{lip}_{\mathcal{M}_{\mathbf{x}}}\nabla_S^2F(\mathbf{x})\le9 lip M x ∇ S 2 F ( x ) ≤ 9 .
(iv) We next show that F F F satisfies the KL inequality with exponent 3 / 4 3/4 3/4 at x ˉ \bar{\mathbf{x}} x ˉ . Choose a neighborhood U U U of x ˉ \bar{\mathbf{x}} x ˉ such that, for every x ∈ U \mathbf{x}\in U x ∈ U , ∣ x i − b i ∣ < 1 |x_i-b_i|<1 ∣ x i − b i ∣ < 1 and F ( x ) < 1 F(\mathbf{x})<1 F ( x ) < 1 . Consider first the case where x i ≥ 0 x_i \ge0 x i ≥ 0 for all i i i . Then
F ( x ) = ∑ i = 1 n ϕ ( x i − b i ) ≤ ∑ i = 1 n ∣ x i − b i ∣ 4 ≤ n ∥ x − b ∥ ∞ 4 . F(x)=\sum_{i=1}^{n}\phi(x_i-b_i)\le\sum_{i=1}^{n}|x_i-b_i|^4\le n\|x-b\|_\infty^4. F ( x ) = i = 1 ∑ n ϕ ( x i − b i ) ≤ i = 1 ∑ n ∣ x i − b i ∣ 4 ≤ n ∥ x − b ∥ ∞ 4 .
For the derivative, we have
∣ ϕ ′ ( t ) ∣ = 4 ∣ t ∣ 3 1 + t 4 ≥ 2 ∣ t ∣ 3 , ∣ t ∣ ≤ 1. |\phi'(t)|=\frac{4|t|^3}{1+t^4}\ge2|t|^3,\qquad|t|\le1. ∣ ϕ ′ ( t ) ∣ = 1 + t 4 4∣ t ∣ 3 ≥ 2∣ t ∣ 3 , ∣ t ∣ ≤ 1.
Any coordinate with x i = 0 x_i=0 x i = 0 has b i = 0 b_i=0 b i = 0 in this neighborhood. If x ≠ b x\ne b x = b , an index attaining ∥ x − b ∥ ∞ \|x-b\|_\infty ∥ x − b ∥ ∞ therefore has x i > 0 x_i>0 x i > 0 , and its partial subdifferential is { ϕ ′ ( x i − b i ) } \{\phi'(x_i-b_i)\} { ϕ ′ ( x i − b i )} . Thus
dist ( 0 , ∂ F ( x ) ) ≥ 2 ∥ x − b ∥ ∞ 3 ≥ 2 n 3 / 4 F ( x ) 3 / 4 . \operatorname{dist}(0,\partial F(x))\ge2\|x-b\|_\infty^3\ge\frac{2}{n^{3/4}}F(x)^{3/4}. dist ( 0 , ∂ F ( x )) ≥ 2∥ x − b ∥ ∞ 3 ≥ n 3/4 2 F ( x ) 3/4 .
Next, suppose that x i < 0 x_i<0 x i < 0 for some i i i . Since x ∈ U x\in U x ∈ U , we must have b i = 0 b_i=0 b i = 0 . Consequently,
∂ i F ( x ) = { 4 x i 3 1 + x i 4 − 2 } , \partial_iF(x)=\left\{\frac{4x_i^3}{1+x_i^4}-2\right\}, ∂ i F ( x ) = { 1 + x i 4 4 x i 3 − 2 } ,
which implies
dist ( 0 , ∂ F ( x ) ) ≥ 2 ≥ 2 n 3 / 4 F ( x ) 3 / 4 . \operatorname{dist}(0,\partial F(x))\ge2\ge\frac{2}{n^{3/4}}F(x)^{3/4}. dist ( 0 , ∂ F ( x )) ≥ 2 ≥ n 3/4 2 F ( x ) 3/4 .
Combining the two cases gives
dist ( 0 , ∂ F ( x ) ) ≥ 2 n 3 / 4 ( F ( x ) − F ( x ‾ ) ) 3 / 4 \operatorname{dist}(0,\partial F(x))\ge\frac{2}{n^{3/4}}\bigl(F(x)-F(\overline{x})\bigr)^{3/4} dist ( 0 , ∂ F ( x )) ≥ n 3/4 2 ( F ( x ) − F ( x ) ) 3/4
for all x ∈ U x\in U x ∈ U . Hence, F F F has the KL property at x ‾ \overline{x} x with exponent 3 / 4 3/4 3/4 .
It remains to show that this exponent is exact. Choose an index j j j with b j = 1 b_j=1 b j = 1 and let x ( t ) = x ‾ + t e j x(t)=\overline{x}+te_j x ( t ) = x + t e j for t > 0 t>0 t > 0 . Then
F ( x ( t ) ) − F ( x ‾ ) = log ( 1 + t 4 ) , dist ( 0 , ∂ F ( x ( t ) ) ) = 4 t 3 1 + t 4 . F(x(t))-F(\overline{x})=\log(1+t^4),\qquad\operatorname{dist}(0,\partial F(x(t)))=\frac{4t^3}{1+t^4}. F ( x ( t )) − F ( x ) = log ( 1 + t 4 ) , dist ( 0 , ∂ F ( x ( t ))) = 1 + t 4 4 t 3 .
For any θ < 3 / 4 \theta<3/4 θ < 3/4 , it follows that
dist ( 0 , ∂ F ( x ( t ) ) ) ( F ( x ( t ) ) − F ( x ‾ ) ) θ = 4 t 3 ( 1 + t 4 ) [ log ( 1 + t 4 ) ] θ → 0 as t ↓ 0. \frac{\operatorname{dist}(0,\partial F(x(t)))}{(F(x(t))-F(\overline{x}))^\theta}
=\frac{4t^3}{(1+t^4)[\log(1+t^4)]^\theta}\to0\quad\text{as }t\downarrow0. ( F ( x ( t )) − F ( x ) ) θ dist ( 0 , ∂ F ( x ( t ))) = ( 1 + t 4 ) [ log ( 1 + t 4 ) ] θ 4 t 3 → 0 as t ↓ 0.
Thus, the KL inequality cannot hold with any exponent θ < 3 / 4 \theta<3/4 θ < 3/4 . Therefore, the exact KL exponent of F F F at x ‾ \overline{x} x is 3 / 4 3/4 3/4 . □
Sufficient Conditions for Boundedness
Lemma B.1 Consider the L 1 / L 2 L_1/L_2 L 1 / L 2 regularized least-squares problem (1.1) with h ( x ) = 1 2 ∥ A x − b ∥ 2 2 h(x)=\frac{1}{2}\|Ax-b\|_2^2 h ( x ) = 2 1 ∥ A x − b ∥ 2 2 . Suppose ker ( A ) ≠ { 0 } \ker(A)\ne\{0\} ker ( A ) = { 0 } and define
ρ A : = min d ∈ ker ( A ) ∖ { 0 } ∥ d ∥ 1 ∥ d ∥ . \rho_A:=\min_{d\in\ker(A)\setminus\{0\}}\frac{\|d\|_1}{\|d\|}. ρ A := d ∈ k e r ( A ) ∖ { 0 } min ∥ d ∥ ∥ d ∥ 1 . If the following condition holds F ( x 0 ) < 1 2 inf x ∈ R n ∥ A x − b ∥ 2 + λ ρ A F(x^0)<\frac{1}{2}\inf_{x\in\mathbb{R}^n}\|Ax-b\|^2+\lambda\rho_A F ( x 0 ) < 2 1 inf x ∈ R n ∥ A x − b ∥ 2 + λ ρ A , then the sequence { x k } \{x^k\} { x k } generated by Algorithm 1 is bounded.
Proof. Let h ∗ : = inf x ∈ R n 1 2 ∥ A x − b ∥ 2 h^* := \inf_{x\in\mathbb{R}^n} \frac{1}{2}\lVert Ax-b\rVert^2 h ∗ := inf x ∈ R n 2 1 ∥ A x − b ∥ 2 . Suppose by contradiction that { x k } \{x^k\} { x k } is unbounded. Then there exists a subsequence, still denoted by { x k } \{x^k\} { x k } for simplicity, such that
lim k → ∞ ∥ x k ∥ = + ∞ . \lim_{k\to\infty}\lVert x^k\rVert=+\infty. k → ∞ lim ∥ x k ∥ = + ∞.
Since { F ( x k ) } \{F(x^k)\} { F ( x k )} is non-increasing and
1 2 ∥ A x k − b ∥ 2 ≤ F ( x k ) ≤ F ( x 0 ) , \frac{1}{2}\lVert Ax^k-b\rVert^2\leq F(x^k)\leq F(x^0), 2 1 ∥ A x k − b ∥ 2 ≤ F ( x k ) ≤ F ( x 0 ) ,
the sequence { A x k } \{Ax^k\} { A x k } is bounded. By taking a further subsequence if necessary, we have
lim k → ∞ x k ∥ x k ∥ 2 = d ˉ with ∥ d ˉ ∥ = 1. \lim_{k\to\infty}\frac{x^k}{\lVert x^k\rVert_2}=\bar{d}\quad\text{with}\quad\lVert\bar{d}\rVert=1. k → ∞ lim ∥ x k ∥ 2 x k = d ˉ with ∥ d ˉ ∥ = 1.
Since { A x k } \{Ax^k\} { A x k } is bounded and lim k → ∞ ∥ x k ∥ = + ∞ \lim_{k\to\infty}\lVert x^k\rVert=+\infty lim k → ∞ ∥ x k ∥ = + ∞ , it follows that A d ˉ = 0 A\bar{d}=0 A d ˉ = 0 . Hence, d ˉ ∈ ker ( A ) \bar{d}\in\ker(A) d ˉ ∈ ker ( A ) and ∥ d ˉ ∥ 1 ≥ ρ A \lVert\bar{d}\rVert_1\geq\rho_A ∥ d ˉ ∥ 1 ≥ ρ A . Therefore,
F ( x 0 ) ≥ lim k → ∞ F ( x k ) ≥ h ∗ + λ ∥ d ˉ ∥ 1 ≥ h ∗ + λ ρ A , F(x^0)\geq\lim_{k\to\infty}F(x^k)\geq h^*+\lambda\lVert\bar{d}\rVert_1\geq h^*+\lambda\rho_A, F ( x 0 ) ≥ k → ∞ lim F ( x k ) ≥ h ∗ + λ ∥ d ˉ ∥ 1 ≥ h ∗ + λ ρ A ,
which contradicts the assumption. Hence, { x k } \{x^k\} { x k } is bounded. □ \square □
Remark B.2 The quantity ρ A \rho_A ρ A is related to null-space quantities used in existence analyses [39 , 47 ] . If ker ( A ) \ker(A) ker ( A ) has the s s s -spherical section property, i.e.,
∥ d ∥ 1 2 ∥ d ∥ 2 2 ≥ m s for every d ∈ ker ( A ) ∖ { 0 } , \frac{\lVert d\rVert_1^2}{\lVert d\rVert_2^2}\geq\frac{m}{s}\quad\text{for every }d\in\ker(A)\setminus\{0\}, ∥ d ∥ 2 2 ∥ d ∥ 1 2 ≥ s m for every d ∈ ker ( A ) ∖ { 0 } ,
then ρ A ≥ m / s \rho_A\geq\sqrt{m/s} ρ A ≥ m / s . Hence the simpler condition F ( x 0 ) < h ∗ + λ m / s F(x^0)<h^*+\lambda\sqrt{m/s} F ( x 0 ) < h ∗ + λ m / s also guarantees boundedness. For matrices with independent standard Gaussian entries and m < n m<n m < n , the null space satisfies this property with high probability for s = c 0 ( log ( n / m ) + 1 ) s=c_0(\log(n/m)+1) s = c 0 ( log ( n / m ) + 1 ) ; see [48 Theorem 3.1] .
Lemma B.3 Consider the L 1 − μ L 2 L_1-\mu L_2 L 1 − μ L 2 regularized logistic regression problem (2) with 0 < μ ≤ 1 0<\mu\leq1 0 < μ ≤ 1 . Suppose
{ ( d , v ) ∈ R n × R : b i ( a i ⊤ d + v ) ≥ 0 , i ∈ [ m ] , ∥ d ∥ 1 − μ ∥ d ∥ = 0 } = { ( 0 , 0 ) } . (33) \left\{(\mathbf{d},v)\in\mathbb{R}^n\times\mathbb{R}:b_i(\mathbf{a}_i^\top\mathbf{d}+v)\geq0,\ i\in[m],\ \lVert\mathbf{d}\rVert_1-\mu\lVert\mathbf{d}\rVert=0\right\}=\{(0,0)\}. \tag*{(33)} { ( d , v ) ∈ R n × R : b i ( a i ⊤ d + v ) ≥ 0 , i ∈ [ m ] , ∥ d ∥ 1 − μ ∥ d ∥ = 0 } = {( 0 , 0 )} . (33) Then the sequence { ( z k , u k ) } \{(z^k,u^k)\} {( z k , u k )} generated by Algorithm 1 is bounded. Moreover, let I + : = { i ∈ [ m ] : b i = 1 } I_+:=\{i\in[m]:b_i=1\} I + := { i ∈ [ m ] : b i = 1 } and I − : = { i ∈ [ m ] : b i = − 1 } I_-:=\{i\in[m]:b_i=-1\} I − := { i ∈ [ m ] : b i = − 1 } .
(i) If 0 < μ < 1 0<\mu<1 0 < μ < 1 , condition (B.1) is equivalent to I + ≠ ∅ I_+\neq\varnothing I + = ∅ and I − ≠ ∅ I_-\neq\varnothing I − = ∅ .
(ii) If μ = 1 \mu=1 μ = 1 , condition (B.1) is equivalent to I + ≠ ∅ I_+\neq\varnothing I + = ∅ and I − ≠ ∅ I_-\neq\varnothing I − = ∅ , together with
min i ∈ I + a i j < max i ∈ I − a i j , min i ∈ I − a i j < max i ∈ I + a i j , ∀ j ∈ [ n ] , \min_{i\in I_+}a_{ij}<\max_{i\in I_-}a_{ij},\qquad\min_{i\in I_-}a_{ij}<\max_{i\in I_+}a_{ij},\qquad\forall j\in[n], i ∈ I + min a ij < i ∈ I − max a ij , i ∈ I − min a ij < i ∈ I + max a ij , ∀ j ∈ [ n ] , where a i j a_{ij} a ij denotes the ( i , j ) (i,j) ( i , j ) -th component of A A A .
Proof. Suppose by contradiction that { ( z k , u k ) } \{(z^k,u^k)\} {( z k , u k )} is unbounded. Then there exists a subsequence, still denoted by { ( z k , u k ) } \{(z^k,u^k)\} {( z k , u k )} for simplicity, such that lim k → ∞ ∥ ( z k , u k ) ∥ = + ∞ \lim_{k\to\infty}\lVert(z^k,u^k)\rVert=+\infty lim k → ∞ ∥( z k , u k )∥ = + ∞ . Since 0 < μ ≤ 1 0<\mu\leq1 0 < μ ≤ 1 , we have ∥ z ∥ 1 − μ ∥ z ∥ ≥ ( 1 − μ ) ∥ z ∥ ≥ 0 \lVert z\rVert_1-\mu\lVert z\rVert\geq(1-\mu)\lVert z\rVert\geq0 ∥ z ∥ 1 − μ ∥ z ∥ ≥ ( 1 − μ ) ∥ z ∥ ≥ 0 . Hence, by the monotonicity of { F ( z k , u k ) } \{F(z^k,u^k)\} { F ( z k , u k )} , we obtain h ( z k , u k ) ≤ F ( z k , u k ) ≤ F ( z 0 , u 0 ) h(z^k,u^k)\leq F(z^k,u^k)\leq F(z^0,u^0) h ( z k , u k ) ≤ F ( z k , u k ) ≤ F ( z 0 , u 0 ) and λ ( ∥ z k ∥ 1 − μ ∥ z k ∥ ) ≤ F ( z 0 , u 0 ) \lambda(\lVert z^k\rVert_1-\mu\lVert z^k\rVert)\leq F(z^0,u^0) λ (∥ z k ∥ 1 − μ ∥ z k ∥) ≤ F ( z 0 , u 0 ) . Let t k : = ∥ ( z k , u k ) ∥ t_k:=\lVert(z^k,u^k)\rVert t k := ∥( z k , u k )∥ , ( d k , v k ) : = ( z k , u k ) / t k (d^k,v^k):=(z^k,u^k)/t_k ( d k , v k ) := ( z k , u k ) / t k . By taking a further subsequence if necessary, we have ( d k , v k ) → ( d ˉ , v ˉ ) (d^k,v^k)\to(\bar{d},\bar{v}) ( d k , v k ) → ( d ˉ , v ˉ ) with ∥ ( d ˉ , v ˉ ) ∥ = 1 \lVert(\bar{d},\bar{v})\rVert=1 ∥( d ˉ , v ˉ )∥ = 1 . We first show that
b i ( a i ⊤ d ˉ + v ˉ ) ≥ 0 , i = 1 , … , m . b_i(\mathbf{a}_i^\top\bar{d}+\bar{v})\geq0,\qquad i=1,\ldots,m. b i ( a i ⊤ d ˉ + v ˉ ) ≥ 0 , i = 1 , … , m .
Suppose otherwise that there exists some i i i such that b i ( a ˉ i ⊤ d ˉ + v ˉ ) < 0 b_i(\bar a_i^\top\bar d+\bar v)<0 b i ( a ˉ i ⊤ d ˉ + v ˉ ) < 0 . Since
lim k → ∞ b i ( a ˉ i ⊤ z k + u k ) t k = lim k → ∞ b i ( a ˉ i ⊤ d k + v k ) = b i ( a ˉ i ⊤ d ˉ + v ˉ ) < 0 , \lim_{k\to\infty}\frac{b_i(\bar a_i^\top z^k+u^k)}{t_k}=\lim_{k\to\infty}b_i(\bar a_i^\top d^k+v^k)=b_i(\bar a_i^\top\bar d+\bar v)<0, k → ∞ lim t k b i ( a ˉ i ⊤ z k + u k ) = k → ∞ lim b i ( a ˉ i ⊤ d k + v k ) = b i ( a ˉ i ⊤ d ˉ + v ˉ ) < 0 ,
we have lim k → ∞ b i ( a ˉ i ⊤ z k + u k ) = − ∞ \lim_{k\to\infty}b_i(\bar a_i^\top z^k+u^k)=-\infty lim k → ∞ b i ( a ˉ i ⊤ z k + u k ) = − ∞ . Consequently, lim k → ∞ log ( 1 + e − b i ( a ˉ i ⊤ z k + u k ) ) = + ∞ \lim_{k\to\infty}\log(1+e^{-b_i(\bar a_i^\top z^k+u^k)})=+\infty lim k → ∞ log ( 1 + e − b i ( a ˉ i ⊤ z k + u k ) ) = + ∞ , which contradicts the boundedness of { h ( z k , u k ) } \{h(z^k,u^k)\} { h ( z k , u k )} .
Moreover, note that λ ( ∥ z k ∥ 1 − μ ∥ z k ∥ 2 ) = λ t k ( ∥ d k ∥ 1 − μ ∥ d k ∥ 2 ) \lambda(\|z^k\|_1-\mu\|z^k\|_2)=\lambda t_k(\|d^k\|_1-\mu\|d^k\|_2) λ ( ∥ z k ∥ 1 − μ ∥ z k ∥ 2 ) = λ t k ( ∥ d k ∥ 1 − μ ∥ d k ∥ 2 ) . Since the left-hand side is bounded and lim k → ∞ t k = + ∞ \lim_{k\to\infty}t_k=+\infty lim k → ∞ t k = + ∞ , we have
lim k → ∞ ∥ d k ∥ 1 − μ ∥ d k ∥ 2 = ∥ d ˉ ∥ 1 − μ ∥ d ˉ ∥ 2 = 0. \lim_{k\to\infty}\|d^k\|_1-\mu\|d^k\|_2=\|\bar d\|_1-\mu\|\bar d\|_2=0. k → ∞ lim ∥ d k ∥ 1 − μ ∥ d k ∥ 2 = ∥ d ˉ ∥ 1 − μ ∥ d ˉ ∥ 2 = 0.
Therefore, by assumption it follows that ( d ˉ , v ˉ ) = ( 0 , 0 ) (\bar d,\bar v)=(0,0) ( d ˉ , v ˉ ) = ( 0 , 0 ) , which contradicts ∥ ( d ˉ , v ˉ ) ∥ 2 = 1 \|(\bar d,\bar v)\|_2=1 ∥ ( d ˉ , v ˉ ) ∥ 2 = 1 . Hence, { ( z k , u k ) } \{(z^k,u^k)\} {( z k , u k )} is bounded.
We next establish the stated equivalences.
(i) Suppose 0 < μ < 1 0<\mu<1 0 < μ < 1 . Since ∥ d ∥ 1 − μ ∥ d ∥ 2 ≥ ( 1 − μ ) ∥ d ∥ 2 \|d\|_1-\mu\|d\|_2\ge(1-\mu)\|d\|_2 ∥ d ∥ 1 − μ ∥ d ∥ 2 ≥ ( 1 − μ ) ∥ d ∥ 2 , condition (B.1) is equivalent to
{ v ∈ R : b i v ≥ 0 , i ∈ [ m ] } = { 0 } , \{v\in\mathbb{R}:b_i v\ge0,\ i\in[m]\}=\{0\}, { v ∈ R : b i v ≥ 0 , i ∈ [ m ]} = { 0 } ,
which is equivalent to I + ≠ ∅ \mathcal{I}_+\ne\varnothing I + = ∅ and I − ≠ ∅ \mathcal{I}_-\ne\varnothing I − = ∅ .
(ii) Suppose μ = 1 \mu=1 μ = 1 . In this case ∥ d ∥ 1 − ∥ d ∥ 2 = 0 \|d\|_1-\|d\|_2=0 ∥ d ∥ 1 − ∥ d ∥ 2 = 0 holds if and only if ∥ d ∥ 0 ≤ 1 \|d\|_0\le1 ∥ d ∥ 0 ≤ 1 . If d = 0 d=0 d = 0 , the argument in (i) shows that v = 0 v=0 v = 0 is the only feasible intercept direction if and only if I + ≠ ∅ \mathcal{I}_+\ne\varnothing I + = ∅ and I − ≠ ∅ \mathcal{I}_-\ne\varnothing I − = ∅ . It remains to consider the case where ∥ d ∥ 0 = 1 \|d\|_0=1 ∥ d ∥ 0 = 1 . Write d = t e j d=te_j d = t e j for some j ∈ [ n ] j\in[n] j ∈ [ n ] and t ≠ 0 t\ne0 t = 0 . Then condition (B.1) holds if and only if for any j ∈ [ n ] j\in[n] j ∈ [ n ] , t ≠ 0 t\ne0 t = 0 and v ∈ R v\in\mathbb{R} v ∈ R , there exists i ∈ [ m ] i\in[m] i ∈ [ m ] such that b i ( t a i j + v ) < 0 b_i(ta_{ij}+v)<0 b i ( t a ij + v ) < 0 , i.e.
min i ∈ I + a i j < max i ∈ I − a i j , min i ∈ I − a i j < max i ∈ I + a i j , ∀ j ∈ [ n ] , \min_{i\in\mathcal{I}_+}a_{ij}<\max_{i\in\mathcal{I}_-}a_{ij},\quad\min_{i\in\mathcal{I}_-}a_{ij}<\max_{i\in\mathcal{I}_+}a_{ij},\quad\forall j\in[n], i ∈ I + min a ij < i ∈ I − max a ij , i ∈ I − min a ij < i ∈ I + max a ij , ∀ j ∈ [ n ] ,
which proves the result.