# Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2014.

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

- [Hybrid ISTA: Unfolding ISTA With Convergence Guarantees Using Free-Form Deep Neural Networks](https://mlsanity.com/paper/2204.11640/) (2022)
- [WeightLoRA: Keep Only Necessary Adapters](https://mlsanity.com/paper/2506.02724/) (2025)
- [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)
- [Convergence of the mini-batch SIHT algorithm](https://mlsanity.com/paper/2209.14536/) (2022)
- [The Stochastic Proximal Distance Algorithm](https://mlsanity.com/paper/2210.12277/) (2022)
- [Federated Gradient Matching Pursuit](https://mlsanity.com/paper/2302.10755/) (2023)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints](https://mlsanity.com/paper/2304.10123/) (2023)
- [Stochastic Natural Thresholding Algorithms](https://mlsanity.com/paper/2306.04730/) (2023)
- [Hard-Thresholding Meets Evolution Strategies in Reinforcement Learning](https://mlsanity.com/paper/2405.01615/) (2024)
- [Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization](https://mlsanity.com/paper/2407.16968/) (2024)
- [Normalized Iterative Hard Thresholding for Tensor Recovery](https://mlsanity.com/paper/2507.04228/) (2025)

## Abstract (arXiv)

Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and covariance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which align with the theoretical analysis and demonstrate these improvements in several different settings.