# Stability and Risk Bounds of Iterative Hard Thresholding

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 75 references that are in the map.
- First posted on arXiv 17 Mar 2022.

## Builds on (most cited first, 22 of 22)

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Orthogonal Statistical Learning](https://mlsanity.com/paper/1901.09036/) (2019)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Optimization for deep learning: theory and algorithms](https://mlsanity.com/paper/1912.08957/) (2019)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [High-dimensional classification by sparse logistic regression](https://mlsanity.com/paper/1706.08344/) (2017)
- [A Tight Bound of Hard Thresholding](https://mlsanity.com/paper/1605.01656/) (2016)
- [Training Skinny Deep Neural Networks with Iterative Hard Thresholding Methods](https://mlsanity.com/paper/1607.05423/) (2016)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)
- [Meta-Learning with Network Pruning](https://mlsanity.com/paper/2007.03219/) (2020)
- [Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations](https://mlsanity.com/paper/1608.01234/) (2016)
- [Best Subset Binary Prediction](https://mlsanity.com/paper/1610.02738/) (2016)
- [Smoothing fast iterative hard thresholding algorithm for ℓ0 regularized nonsmooth convex regression problem](https://mlsanity.com/paper/2104.13107/) (2021)

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

- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [WeightLoRA: Keep Only Necessary Adapters](https://mlsanity.com/paper/2506.02724/) (2025)
- [Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithms](https://mlsanity.com/paper/2206.03834/) (2022)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)

## Abstract (arXiv)

In this paper, we analyze the generalization performance of the Iterative Hard Thresholding (IHT) algorithm widely used for sparse recovery problems. The parameter estimation and sparsity recovery consistency of IHT has long been known in compressed sensing. From the perspective of statistical learning, another fundamental question is how well the IHT estimation would predict on unseen data. This paper makes progress towards answering this open question by introducing a novel sparse generalization theory for IHT under the notion of algorithmic stability. Our theory reveals that: 1) under natural conditions on the empirical risk function over n samples of dimension p, IHT with sparsity level k enjoys an tilde O(n-1/2√klog(n)log(p)) rate of convergence in sparse excess risk; 2) a tighter tilde O(n-1/2√log(n)) bound can be established by imposing an additional iteration stability condition on a hypothetical IHT procedure invoked to the population risk; and 3) a fast rate of order tilde Oleft(n-1k(log3(n)+log(p))right) can be derived for strongly convex risk function under proper strong-signal conditions. The results have been substantialized to sparse linear regression and sparse logistic regression models to demonstrate the applicability of our theory. Preliminary numerical evidence is provided to confirm our theoretical predictions.