On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning
Xingguo Li, Lin Yang, Jason Ge, Jarvis Haupt, Tong Zhang, Tuo Zhao
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 (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.
BibTeX
@inproceedings{NIPS2017_351b3358,
author = {Li, Xingguo and Yang, Lin and Ge, Jason and Haupt, Jarvis and Zhang, Tong and Zhao, Tuo},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/351b33587c5fdd93bd42ef7ac9995a28-Paper.pdf},
volume = {30},
year = {2017}
}