Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

12-2018

Abstract

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 in the quadratic case. Numerical results confirm our theoretical affirmation and demonstrate the computational efficiency of the proposed methods.

Discipline

OS and Networks | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada, December 2-8

First Page

1

Last Page

10

Publisher

NeurIPS

City or Country

Montréal, Canada

Additional URL

https://papers.nips.cc/paper_files/paper/2018/hash/ec5aa0b7846082a2415f0902f0da88f2-Abstract.html

Download

Share

COinS