Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
From MaRDI portal
Publication:6330260
arXiv1912.00858MaRDI QIDQ6330260
Author name not available (Why is that?)
Publication date: 2 December 2019
Abstract: 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.
This page was built for publication: Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330260)
