Paperlane

no. 17 · Wednesday 18 November 2026

KL-Guided Support Selection and Subspace Cubic Newton Methods for Sparse Optimization

Zihao Xia, Min Tao and Guojian Yin

math.OC

Abstract

We study sparse composite optimization with a smooth loss and a possibly nonconvex, nonsmooth regularizer. The objective is locally smooth on each fixed support. Our method combines full-space proximal-gradient steps with inexact cubic-regularized Newton steps on a subspace selected by thresholding. If the iterates are bounded and the objective satisfies the Kurdyka–Łojasiewicz (KL) property, the entire sequence converges to a first-order stationary point. A threshold based on the KL exponent ensures that the selected coordinate set coincides with the support of the limit after finitely many iterations, without requiring a nondegeneracy assumption. We also provide a residual-based threshold when such an exponent exists and its value 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 parameters chosen to meet the target tolerances, we bound the number of outer iterations needed to reach restricted approximate second-order stationarity after support identification and entry into the full-step regime. We conduct numerical experiments in two settings: when the KL exponent is known and when it is unknown. In the former case, we use a degenerate problem to demonstrate the effectiveness of the proposed method. In the latter case, we compare the proposed method and its adaptive variant with existing solvers on sparse recovery and logistic regression problems.

fields
Optimization and Control
pdf ↗ page arXiv:2611.22940 ↗