Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
This addresses a bottleneck in applying stochastic optimization to complex graph-structured sparsity problems, though it appears incremental as it extends existing methods to this specific constraint.
The authors tackled the problem of optimizing graph-structured sparsity models, which are non-convex and important for applications like disease outbreak and social networks, by proposing a stochastic gradient-based method that achieves linear convergence up to a constant error.
Stochastic optimization algorithms update models with cheap per-iteration costs sequentially, which makes them amenable for large-scale data analysis. Such algorithms have been widely studied for structured sparse models where the sparsity information is very specific, e.g., convex sparsity-inducing norms or $\ell^0$-norm. However, these norms cannot be directly applied to the problem of complex (non-convex) graph-structured sparsity models, which have important application in disease outbreak and social networks, etc. In this paper, we propose a stochastic gradient-based method for solving graph-structured sparsity constraint problems, not restricted to the least square loss. We prove that our algorithm enjoys a linear convergence up to a constant error, which is competitive with the counterparts in the batch learning setting. We conduct extensive experiments to show the efficiency and effectiveness of the proposed algorithms.