Timezone: »

 
Poster
Efficient Stochastic Gradient Hard Thresholding
Pan Zhou · Xiaotong Yuan · Jiashi Feng

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #123
in Thu Poster Session A »

Stochastic gradient hard thresholding methods have recently been shown to work favorably in solving large-scale empirical risk minimization problems under sparsity or rank constraint. Despite the improved iteration complexity over full gradient methods, the gradient evaluation and hard thresholding complexity of the existing stochastic algorithms usually scales linearly with data size, which could still be expensive when data is huge and the hard thresholding step could be as expensive as singular value decomposition in rank-constrained problems. To address these deficiencies, we propose an efficient hybrid stochastic gradient hard thresholding (HSG-HT) method that can be provably shown to have sample-size-independent gradient evaluation and hard thresholding complexity bounds. Specifically, we prove that the stochastic gradient evaluation complexity of HSG-HT scales linearly with inverse of sub-optimality and its hard thresholding complexity scales logarithmically. By applying the heavy ball acceleration technique, we further propose an accelerated variant of HSG-HT which can be shown to have improved factor dependence on restricted condition number. Numerical results confirm our theoretical affirmation and demonstrate the computational efficiency of the proposed methods.

Keywords: Sparsity and Compressed Sensing · Algorithms
[ Paper] 

Author Information

Pan Zhou (National University of Singapore)
Xiaotong Yuan (Nanjing University of Information Science and Technology)
Jiashi Feng (National University of Singapore)

More from the Same Authors