  Large-scale non-convex sparsity-constrained problems have recently gained
extensive attention. Most existing deterministic optimization methods (e.g.,
GraSP) are not suitable for large-scale and high-dimensional problems, and thus
stochastic optimization methods with hard thresholding (e.g., SVRGHT) become
more attractive. Inspired by GraSP, this paper proposes a new general relaxed
gradient support pursuit (RGraSP) framework, in which the sub-algorithm only
requires to satisfy a slack descent condition. We also design two specific
semi-stochastic gradient hard thresholding algorithms. In particular, our
algorithms have much less hard thresholding operations than SVRGHT, and their
average per-iteration cost is much lower (i.e., O(d) vs. O(d log(d)) for
SVRGHT), which leads to faster convergence. Our experimental results on both
synthetic and real-world datasets show that our algorithms are superior to the
state-of-the-art gradient hard thresholding methods.
