Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit
Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Shenglong Zhou;N. Xiu;H. Qi
中科院分区：
文献类型：
--
作者：
Shenglong Zhou;N. Xiu;H. Qi
基于硬阈值原理的算法已经得到了很好的研究，在压缩感知和更一般的稀疏约束优化中具有合理的理论保证。在现有的经验研究中广泛观察到，当使用限制性牛顿步骤（作为去偏步骤）时，硬阈值算法倾向于在显著低的迭代次数中满足停止条件，并且非常有效。因此，由此获得的牛顿硬阈值算法要求更强的理论保证比他们简单的硬阈值对应。本文提供了一个理论上的理由，使用限制牛顿步骤。我们建立了稀疏约束优化的理论和算法-牛顿硬约束追踪算法（NHTP）。我们的主要结果表明，NHTP是二次收敛的限制强凸性和光滑的标准假设下。在一个较弱的假设条件下，证明了算法的全局收敛性.在压缩感知的特殊情况下，NHTP有效地减少了一些现有的硬阈值算法与牛顿步骤。因此，我们的快速收敛结果证明了为什么这些算法比没有牛顿步骤的性能更好。在压缩感知和稀疏逻辑回归中，NHTP的效率在合成和真实的数据上都得到了证明。
Algorithms based on the hard thresholding principle have been well studied with sounding theoretical guarantees in the compressed sensing and more general sparsity-constrained optimization. It is widely observed in existing empirical studies that when a restricted Newton step was used (as the debiasing step), the hard-thresholding algorithms tend to meet halting conditions in a significantly low number of iterations and are very efficient. Hence, the thus obtained Newton hard-thresholding algorithms call for stronger theoretical guarantees than for their simple hard-thresholding counterparts. This paper provides a theoretical justification for the use of the restricted Newton step. We build our theory and algorithm, Newton Hard-Thresholding Pursuit (NHTP), for the sparsity-constrained optimization. Our main result shows that NHTP is quadratically convergent under the standard assumption of restricted strong convexity and smoothness. We also establish its global convergence to a stationary point under a weaker assumption. In the special case of the compressive sensing, NHTP effectively reduces to some of the existing hard-thresholding algorithms with a Newton step. Consequently, our fast convergence result justifies why those algorithms perform better than without the Newton step. The efficiency of NHTP was demonstrated on both synthetic and real data in compressed sensing and sparse logistic regression.