# Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit

arXiv: https://arxiv.org/abs/1901.02763 · HTML: https://mlsanity.com/paper/1901.02763/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jan 2019.

## Built on by (most cited first, 9 of 9)

- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information](https://mlsanity.com/paper/2408.17163/) (2024)
- [Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique](https://mlsanity.com/paper/2308.00251/) (2023)
- [Convergence of the mini-batch SIHT algorithm](https://mlsanity.com/paper/2209.14536/) (2022)
- [Sparse Decentralized Federated Learning](https://mlsanity.com/paper/2308.16671/) (2023)
- [skscope: Fast Sparsity-Constrained Optimization in Python](https://mlsanity.com/paper/2403.18540/) (2024)
- [MKL-L0/1-SVM](https://mlsanity.com/paper/2308.12016/) (2023)
- [Sparsity-Constraint Optimization via Splicing Iteration](https://mlsanity.com/paper/2406.12017/) (2024)
- [Local Duality for Sparse Support Vector Machines](https://mlsanity.com/paper/2601.20170/) (2026)

## Abstract (arXiv)

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.