Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization

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.

arXiv comment7 pages, 3 figures, Appeared at the Data Science Meets Optimization Workshop (DSO) at IJCAI'19

References in corpus (8)

• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• Direct Acceleration of SAGA using Sampled Negative Momentum
• Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• ASVRG: Accelerated Proximal SVRG
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints