Subspace Newton method for the l₀-regularized optimization

Sparse optimization has seen an evolutionary advance in the past decade with extensive applications ranging from image and signal processing, statistics to machine learning. As a tractable approach, regularization is frequently used, leading to a regularized optimization where l0 norm or its continuous approximations that characterize the sparsity are punished in its objective. From the continuity of approximations to the discreteness of l0 norm, the most challenging model is the l0-regularized optimization. To conquer its hardness, numerous numerically effective methods have been proposed. However, most of them only enjoy that the (sub)sequence converges to a stationary point from the deterministic optimization perspective or the distance between each iterate and any given sparse reference point is bounded by an error bound in the sense of probability. We design a method SNL0: subspace Newton method for the l0-regularized optimization, and prove that its generated sequence converges to a stationary point globally under the strong smoothness condition. In addition, it is also quadratic convergent with the help of locally strong convexity, well explaining that our method, as a second order method, is able to converge very fast. Moreover, a novel mechanism to effectively update the penalty parameter is created, which allows us to get rid of the tedious parameter tuning task that is suffered by most regularized optimization methods