A globally convergent approximate Newton method for non-convex sparse learning. (June 2022)

• Record Type: Journal Article
• Authors: Ji, Fanfan; Shuai, Hui; Yuan, Xiao-Tong
• Is Part Of: Pattern recognition. Volume 126(2022)
• Publication Date: 2022-06
• Subjects: Sparse learning -- Newton-type method -- Linear models -- Quadratic approximation -- Iterative hard thresholding; 00-01 -- 99-00; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.108560
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We propose a globally convergent approximate Newton (GCAN) method for cardinality-constrained sparse learning of linear model. We analyze theoretically that our method can converge asymptotically. Additionally, the sparse recovery performance under proper condition is also analyzed and we find that our method has a boarder condition to guarantee the sparsity recovery performance. The Hessian matrix and its inverse are unnecessary to access compared to other second-order algorithms, that is to say, our method can be applied to the linear models with complex Hessian matrix (e.g. Softmax regression) or ones without Hessian matrix (e.g. L2-SVMs). We have applied our method to several linear models. The experimental results demonstrate that our proposed algorithm is superior to the first-order algorithms and has a better trade-off between accuracy and efficiency than other methods. Abstract: Newton-type greedy pursuit methods have been shown to work favorably for cardinality-constrained sparse learning problems. The appealing sparsity recovery performance of the existing Newton-type greedy pursuit methods, however, is typically guaranteed within a local neighborhood around the target solution. To address this limitation, we present in this paper a novel approximate Newton pursuit method for sparse learning with linear models. The computation procedure of our method iterates between constructing an inexact Newton-type quadratic majorization to the global empirical risk and solving the quadratic approximation via iterative hard thresholding. Provable global guarantees on mean squared prediction error, which is less understood for prior methods, are provided for our method. Numerical evidence is provided to show the advantages of our approach over the prior methods.