# Convergence of the mini-batch SIHT algorithm

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 29 Sep 2022.

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

- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [A Tight Bound of Hard Thresholding](https://mlsanity.com/paper/1605.01656/) (2016)
- [Between hard and soft thresholding: optimal iterative thresholding algorithms](https://mlsanity.com/paper/1804.08841/) (2018)
- [Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints](https://mlsanity.com/paper/1407.0088/) (2014)
- [IHT dies hard: Provable accelerated Iterative Hard Thresholding](https://mlsanity.com/paper/1712.09379/) (2017)
- [Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit](https://mlsanity.com/paper/1901.02763/) (2019)
- [Gradient Properties of Hard Thresholding Operator](https://mlsanity.com/paper/2209.08247/) (2022)
- [Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization](https://mlsanity.com/paper/1703.00119/) (2017)
- [Amenable Sparse Network Investigator](https://mlsanity.com/paper/2202.09284/) (2022)
- [A Lagrange-Newton Algorithm for Sparse Nonlinear Programming](https://mlsanity.com/paper/2004.13257/) (2020)
- [Optimization over Sparse Symmetric Sets via a Nonmonotone Projected Gradient Method](https://mlsanity.com/paper/1509.08581/) (2015)

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

- [The Backpropagation algorithm for a math student](https://mlsanity.com/paper/2301.09977/) (2023)
- [Learning a Sparse Neural Network using IHT](https://mlsanity.com/paper/2404.18414/) (2024)

## Abstract (arXiv)

The Iterative Hard Thresholding (IHT) algorithm has been considered extensively as an effective deterministic algorithm for solving sparse optimizations. The IHT algorithm benefits from the information of the batch (full) gradient at each point and this information is a crucial key for the convergence analysis of the generated sequence. However, this strength becomes a weakness when it comes to machine learning and high dimensional statistical applications because calculating the batch gradient at each iteration is computationally expensive or impractical. Fortunately, in these applications the objective function has a summation structure that can be taken advantage of to approximate the batch gradient by the stochastic mini-batch gradient. In this paper, we study the mini-batch Stochastic IHT (SIHT) algorithm for solving the sparse optimizations. As opposed to previous works where increasing and variable mini-batch size is necessary for derivation, we fix the mini-batch size according to a lower bound that we derive and show our work. To prove stochastic convergence of the objective value function we first establish a critical sparse stochastic gradient descent property. Using this stochastic gradient descent property we show that the sequence generated by the stochastic mini-batch SIHT is a supermartingale sequence and converges with probability one. Unlike previous work we do not assume the function to be a restricted strongly convex. To the best of our knowledge, in the regime of sparse optimization, this is the first time in the literature that it is shown that the sequence of the stochastic function values converges with probability one by fixing the mini-batch size for all steps.