Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization

Xiao–Tong Yuan, Ping Li, Tong Zhang

2014 · 75 citations · 23 references

Concepts

Abstract

Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse so-lutions of underdetermined linear systems. This method has been shown to have strong theoreti-cal guarantees and impressive numerical perfor-mance. In this paper, we generalize HTP from compressed sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard truncation step with or without debiasing. We prove that our method enjoys the strong guarantees analogous to HTP in terms of rate of convergence and parameter estimation accuracy. Numerical evi-dences show that our method is superior to the state-of-the-art greedy selection methods when applied to learning tasks of sparse logistic regres-sion and sparse support vector machines. 1.

References

23