Efficient Gradient Support Pursuit With Less Hard Thresholding for Cardinality-Constrained Learning | JoVE Visualize

Area of Science:

Optimization
Machine Learning
Signal Processing

Background:

Stochastic hard thresholding (HT) optimization methods, such as stochastic variance reduced gradient hard thresholding (SVRGHT), are increasingly used for large-scale sparsity/rank-constrained problems.
Existing methods face challenges with high HT oracle complexities, particularly for high-dimensional data and large matrices.

Purpose of the Study:

To develop a novel framework, Relaxed Gradient Support Pursuit (RGraSP), to address the high computational complexity of existing stochastic HT methods.
To introduce efficient stochastic algorithms based on RGraSP, namely stochastic variance reduced-gradient support pursuit (SVRGSP) and its fast variant (SVRGSP+).
To analyze the theoretical performance and practical efficiency of the proposed algorithms for large-scale optimization problems.

Main Methods:

Introduction of the Relaxed Gradient Support Pursuit (RGraSP) framework, which allows for approximate solutions at each iteration.
Development of stochastic variance reduction-gradient support pursuit (SVRGSP) and its accelerated version (SVRGSP+).
Theoretical analysis of gradient and hard thresholding (HT) oracle complexities, proving convergence properties.
Design of an asynchronous parallel variant for handling very high-dimensional and sparse data.

Main Results:

The proposed algorithms (SVRGSP and SVRGSP+) demonstrate a two-fold reduction in gradient oracle complexity compared to SVRGHT.
HT complexity is reduced by a factor of κ_∧s (restricted condition number) relative to SVRGHT.
Algorithms exhibit fast linear convergence towards an approximately global optimum.
Experimental results on synthetic and real-world datasets confirm superior performance over state-of-the-art gradient HT methods.

Conclusions:

The RGraSP framework and its associated algorithms (SVRGSP, SVRGSP+) offer significant improvements in efficiency and convergence for large-scale sparsity-constrained optimization.
The proposed methods provide a more computationally tractable alternative to existing stochastic HT techniques, especially for high-dimensional and sparse datasets.
The asynchronous parallel variant further enhances scalability for extremely large problems.