Exact Recovery of Hard Thresholding Pursuit
Xiaotong Yuan · Ping Li · Tong Zhang

Wed Dec 7th 06:00 -- 09:30 PM @ Area 5+6+7+8 #68 #None
The Hard Thresholding Pursuit (HTP) is a class of truncated gradient descent methods for finding sparse solutions of $\ell_0$-constrained loss minimization problems. The HTP-style methods have been shown to have strong approximation guarantee and impressive numerical performance in high dimensional statistical learning applications. However, the current theoretical treatment of these methods has traditionally been restricted to the analysis of parameter estimation consistency. It remains an open problem to analyze the support recovery performance (a.k.a., sparsistency) of this type of methods for recovering the global minimizer of the original NP-hard problem. In this paper, we bridge this gap by showing, for the first time, that exact recovery of the global sparse minimizer is possible for HTP-style methods under restricted strong condition number bounding conditions. We further show that HTP-style methods are able to recover the support of certain relaxed sparse solutions without assuming bounded restricted strong condition number. Numerical results on simulated data confirms our theoretical predictions.

Author Information

Xiaotong Yuan (Nanjing University of Informat)
Ping Li (Baidu Research USA)
Tong Zhang (Tencent)

More from the Same Authors