On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions
This addresses computational and statistical challenges in high-dimensional sparse learning, representing an incremental improvement through integration of existing techniques.
The authors tackled nonconvex regularized sparse learning in high dimensions by proposing a DC proximal Newton algorithm that integrates proximal Newton with multi-stage convex relaxation, achieving local quadratic convergence and obtaining sparse approximate local optima with optimal statistical properties after few convex relaxations.
We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal Newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statistical guarantees. Specifically, by leveraging a sophisticated characterization of sparse modeling structures/assumptions (i.e., local restricted strong convexity and Hessian smoothness), we prove that within each stage of convex relaxation, our proposed algorithm achieves (local) quadratic convergence, and eventually obtains a sparse approximate local optimum with optimal statistical properties after only a few convex relaxations. Numerical experiments are provided to support our theory.