Abstract:In this paper, we propose two second-order methods for solving the \(\ell_1\)-regularized composite optimization problem, which are developed based on two distinct definitions of approximate second-order stationary points. We introduce a hybrid proximal gradient and negative curvature method, as well as an adaptive hybrid proximal gradient-Newton-CG method with negative curvature directions, to find a strong* approximate second-order stationary point and a weak approximate second-order stationary point for \(\ell_1\)-regularized optimization problems, respectively. Comprehensive analyses are provided regarding the iteration complexity, operation complexity (including gradient evaluations and Hessian-vector products), and the local superlinear convergence rates of the first phases of these two methods under specific error bound conditions. We demonstrate that the proximal gradient-Newton-CG method achieves the best-known iteration complexity for attaining the proposed weak approximate second-order stationary point, which is consistent with results for finding an approximate second-order stationary point in unconstrained optimization. Through a toy example, we show that our proposed methods can effectively escape first-order approximate solution. Numerical experiments implemented on the \(\ell_1\)-regularized Student's t-regression problem validate the effectiveness of both methods.
From: Hong Zhu [view email]
[v1]
Tue, 22 Apr 2025 09:56:28 UTC (521 KB)
[v2]
Fri, 9 Jan 2026 15:48:13 UTC (559 KB)
[v3]
Tue, 16 Jun 2026 15:53:15 UTC (543 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。