# Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 24 Jul 2024.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method](https://mlsanity.com/paper/1609.03261/) (2016)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)
- [Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints](https://mlsanity.com/paper/1407.0088/) (2014)
- [Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction](https://mlsanity.com/paper/1605.02711/) (2016)
- [Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization](https://mlsanity.com/paper/1905.03652/) (2019)
- [Approximation Algorithms for Model-Based Compressive Sensing](https://mlsanity.com/paper/1406.1579/) (2014)

## Abstract (arXiv)

Stochastic optimization algorithms are widely used for large-scale data analysis due to their low per-iteration costs, but they often suffer from slow asymptotic convergence caused by inherent variance. Variance-reduced techniques have been therefore used to address this issue in structured sparse models utilizing sparsity-inducing norms or ℓ0-norms. However, these techniques are not directly applicable to complex (non-convex) graph sparsity models, which are essential in applications like disease outbreak monitoring and social network analysis. In this paper, we introduce two stochastic variance-reduced gradient-based methods to solve graph sparsity optimization: GraphSVRG-IHT and GraphSCSG-IHT. We provide a general framework for theoretical analysis, demonstrating that our methods enjoy a linear convergence speed. Extensive experiments validate