# Between hard and soft thresholding: optimal iterative thresholding algorithms

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2018.

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

- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [AWP: Activation-Aware Weight Pruning and Quantization with Projected Gradient Descent](https://mlsanity.com/paper/2506.10205/) (2025)
- [Convergence of the mini-batch SIHT algorithm](https://mlsanity.com/paper/2209.14536/) (2022)
- [Slow Kill for Big Data Learning](https://mlsanity.com/paper/2305.01726/) (2023)
- [Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Model](https://mlsanity.com/paper/2106.14630/) (2021)
- [Stochastic Mirror Descent for Large-Scale Sparse Recovery](https://mlsanity.com/paper/2210.12882/) (2022)
- [Feather: An Elegant Solution to Effective DNN Sparsification](https://mlsanity.com/paper/2310.02448/) (2023)
- [Sparsity via Sparse Group k-max Regularization](https://mlsanity.com/paper/2402.08493/) (2024)
- [Understanding Best Subset Selection: A Tale of Two C(omplex)ities](https://mlsanity.com/paper/2301.06259/) (2023)
- [Adaptive Iterative Soft-Thresholding Algorithm with the Median Absolute Deviation](https://mlsanity.com/paper/2507.02084/) (2025)
- [Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation](https://mlsanity.com/paper/2511.18167/) (2025)
- [Auto-Unrolled Proximal Gradient Descent: An AutoML Approach to Interpretable Waveform Optimization](https://mlsanity.com/paper/2603.17478/) (2026)
- [Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization](https://mlsanity.com/paper/2604.03419/) (2026)
- [Online Generalized Sparse Regression: How Does Overparametrization Help?](https://mlsanity.com/paper/2608.17466/) (2026)

## Abstract (arXiv)

Iterative thresholding algorithms seek to optimize a differentiable objective function over a sparsity or rank constraint by alternating between gradient steps that reduce the objective, and thresholding steps that enforce the constraint. This work examines the choice of the thresholding operator, and asks whether it is possible to achieve stronger guarantees than what is possible with hard thresholding. We develop the notion of relative concavity of a thresholding operator, a quantity that characterizes the worst-case convergence performance of any thresholding operator on the target optimization problem. Surprisingly, we find that commonly used thresholding operators, such as hard thresholding and soft thresholding, are suboptimal in terms of worst-case convergence guarantees. Instead, a general class of thresholding operators, lying between hard thresholding and soft thresholding, is shown to be optimal with the strongest possible convergence guarantee among all thresholding operators. Examples of this general class includes ℓq thresholding with appropriate choices of q, and a newly defined em reciprocal thresholding operator. We also investigate the implications of the improved optimization guarantee in the statistical setting of sparse linear regression, and show that this new class of thresholding operators attain the optimal rate for computationally efficient estimators, matching the Lasso.