# Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 11 Apr 2022.

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

- [AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks](https://mlsanity.com/paper/2106.12379/) (2021)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Between hard and soft thresholding: optimal iterative thresholding algorithms](https://mlsanity.com/paper/1804.08841/) (2018)
- [Sparse Convex Optimization via Adaptively Regularized Hard Thresholding](https://mlsanity.com/paper/2006.14571/) (2020)
- [Greedy Minimization of Weakly Supermodular Set Functions](https://mlsanity.com/paper/1502.06528/) (2015)
- [Local Search Algorithms for Rank-Constrained Convex Optimization](https://mlsanity.com/paper/2101.06262/) (2021)

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

- [Quantized Distributed Training of Large Models with Convergence Guarantees](https://mlsanity.com/paper/2302.02390/) (2023)
- [Gradient Descent Converges Linearly for Logistic Regression on Separable Data](https://mlsanity.com/paper/2306.14381/) (2023)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)
- [The Condition-Number Barrier in Sparse Least Squares](https://mlsanity.com/paper/2608.02588/) (2026)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization](https://mlsanity.com/paper/2402.17902/) (2024)
- [Sparsity-Constraint Optimization via Splicing Iteration](https://mlsanity.com/paper/2406.12017/) (2024)
- [Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation](https://mlsanity.com/paper/2511.18167/) (2025)
- [Curation Leaks: Membership Inference Attacks against Data Curation for Machine Learning](https://mlsanity.com/paper/2603.00811/) (2026)

## Abstract (arXiv)

We propose a simple modification to the iterative hard thresholding (IHT) algorithm, which recovers asymptotically sparser solutions as a function of the condition number. When aiming to minimize a convex function f(x) with condition number kappa subject to x being an s-sparse vector, the standard IHT guarantee is a solution with relaxed sparsity O(skappa2), while our proposed algorithm, regularized IHT, returns a solution with sparsity O(skappa). Our algorithm significantly improves over ARHT which also finds a solution of sparsity O(skappa), as it does not require re-optimization in each iteration (and so is much faster), is deterministic, and does not require knowledge of the optimal solution value f(x^*) or the optimal sparsity level s. Our main technical tool is an adaptive regularization framework, in which the algorithm progressively learns the weights of an ℓ2 regularization term that will allow convergence to sparser solutions. We also apply this framework to low rank optimization, where we achieve a similar improvement of the best known condition number dependence from kappa2 to kappa.