Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization
This work addresses optimization challenges in graph sparsity for applications like disease monitoring and social network analysis, representing an incremental improvement over existing variance-reduced techniques.
The paper tackled the problem of slow convergence in stochastic optimization for complex graph sparsity models by introducing two variance-reduced gradient methods, achieving linear convergence speed as validated in experiments.
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 $\ell_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