On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning
On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning
复制标题
DOI：
--
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Xingguo Li;Lin F. Yang;J. Ge;Jarvis D. Haupt;T. Zhang;T. Zhao
中科院分区：
文献类型：
--
作者：
Xingguo Li;Lin F. Yang;J. Ge;Jarvis D. Haupt;T. Zhang;T. Zhao
我们提出了一种 DC 近端牛顿算法来解决高维非凸正则化稀疏学习问题。我们提出的算法将近端牛顿算法与基于凸（DC）编程差异的多级凸松弛相结合，并具有强大的计算和统计保证。具体来说，通过利用稀疏建模结构/假设的复杂表征（即局部受限强凸性和 Hessian 平滑性），我们证明在凸松弛的每个阶段内，我们提出的算法实现（局部）二次收敛，并最终在仅几次凸松弛后获得具有最佳统计特性的稀疏近似局部最优。提供了数值实验来支持我们的理论。
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.