A Semismooth Newton Algorithm for High-Dimensional Nonconvex Sparse Learning
A Semismooth Newton Algorithm for High-Dimensional Nonconvex Sparse Learning
复制标题
高维非凸稀疏学习的半光滑牛顿算法
DOI：
10.1109/tnnls.2019.2935001
复制
发表时间：
2018-02
影响因子：
10.4
通讯作者：
Yang Qinglong
中科院分区：
文献类型：
--
作者：
Shi Yueyong;Huang Jian;Jiao Yuling;Yang Qinglong
光滑剪切绝对偏差（SCAD）和极小极大凹罚（MCP）-罚回归模型是两种重要的、广泛使用的非凸稀疏学习工具，它们可以同时处理变量选择和参数估计，因此在各个领域有潜在的应用，如高通量生物医学研究中的生物数据挖掘。从理论上讲，这两个模型即使在高维环境中也具有预言属性，其中预测变量的<inline-formula><tex-math notation="LaTeX">数量p$</tex-math></inline-formula>可能远远大于观测值的<inline-formula><tex-math notation="LaTeX">数量n$</tex-math></inline-formula>。然而，在数值上，由于其非凸性和非光滑性，开发快速和稳定的算法是相当具有挑战性的。在这篇文章中，我们开发了一个快速算法SCAD和MCP惩罚学习问题。首先，我们证明了这两个模型的全局极小是非光滑方程的根。然后，半光滑牛顿（SSN）算法求解方程组。我们证明了SSN算法局部和超线性收敛到Karush-Kuhn-Tucker（KKT）点。计算复杂度分析表明，SSN算法每次迭代的代价为<inline-formula><tex-math notation="LaTeX">O（np）$</tex-math></inline-formula>。结合热启动技术，SSN算法可以是非常有效和准确的。仿真研究和一个真实的数据例子表明，我们的SSN算法，具有可比的解决方案的精度与坐标下降（CD）和凸（DC）的差异近端牛顿算法，是更有效的计算。
The smoothly clipped absolute deviation (SCAD) and the minimax concave penalty (MCP)-penalized regression models are two important and widely used nonconvex sparse learning tools that can handle variable selection and parameter estimation simultaneously and thus have potential applications in various fields, such as mining biological data in high-throughput biomedical studies. Theoretically, these two models enjoy the oracle property even in the high-dimensional settings, where the number of predictors <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> may be much larger than the number of observations <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. However, numerically, it is quite challenging to develop fast and stable algorithms due to their nonconvexity and nonsmoothness. In this article, we develop a fast algorithm for SCAD- and MCP-penalized learning problems. First, we show that the global minimizers of both models are roots of the nonsmooth equations. Then, a semismooth Newton (SSN) algorithm is employed to solve the equations. We prove that the SSN algorithm converges locally and superlinearly to the Karush–Kuhn–Tucker (KKT) points. The computational complexity analysis shows that the cost of the SSN algorithm per iteration is <inline-formula> <tex-math notation="LaTeX">$O(np)$ </tex-math></inline-formula>. Combined with the warm-start technique, the SSN algorithm can be very efficient and accurate. Simulation studies and a real data example suggest that our SSN algorithm, with comparable solution accuracy with the coordinate descent (CD) and the difference of convex (DC) proximal Newton algorithms, is more computationally efficient.
登录
查看更多内容
DOI：
--
发表时间：
2014-03
期刊：
ArXiv
影响因子：
--
作者：
Yuling Jiao;Bangti Jin;Xiliang Lu
通讯作者：
Yuling Jiao;Bangti Jin;Xiliang Lu
DOI：
--
发表时间：
2019-01
期刊：
arXiv: Computer Vision and Pattern Recognition
影响因子：
--
作者：
Rongrong Ma;Jianyu Miao;Lingfeng Niu;Peng Zhang
通讯作者：
Rongrong Ma;Jianyu Miao;Lingfeng Niu;Peng Zhang
DOI：
--
发表时间：
2017-06
期刊：
ArXiv
影响因子：
--
作者：
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
影响因子：
2.1
作者：
Becker, Stephen;Bobin, Jerome;Candes, Emmanuel J.
通讯作者：
Candes, Emmanuel J.
影响因子：
4.5
作者：
Zhang, Cun-Hui
通讯作者：
Zhang, Cun-Hui