On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions
arXiv:1706.06066
Abstract
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.
arXiv comment36 pages, 5 figures, 1 table, Accepted at NIPS 2017
References in corpus (10)
- Nearly unbiased variable selection under minimax concave penalty
- Simultaneous analysis of Lasso and Dantzig selector
- On the conditions used to prove oracle results for the Lasso
- Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
- The huge Package for High-dimensional Undirected Graph Estimation in R
- Compressed sensing performance bounds under Poisson noise
- Restricted Eigenvalue Conditions on Subgaussian Random Matrices
- Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory
- A Likelihood Ratio Framework for High Dimensional Semiparametric Regression
- On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About Its Nonsmooth Loss Function