Title: Homotopy Parametric Simplex Method for Sparse Learning,
Abstract: High dimensional sparse learning has imposed a great computational challenge
to large scale data analysis. In this paper, we are interested in a broad class
of sparse learning approaches formulated as linear programs parametrized by a
{\em regularization factor}, and solve them by the parametric simplex method
(PSM). Our parametric simplex method offers significant advantages over other
competing methods: (1) PSM naturally obtains the complete solution path for all
values of the regularization parameter; (2) PSM provides a high precision dual
certificate stopping criterion; (3) PSM yields sparse solutions through very
few iterations, and the solution sparsity significantly reduces the
computational cost per iteration. Particularly, we demonstrate the superiority
of PSM over various sparse learning approaches, including Dantzig selector for
sparse linear regression, LAD-Lasso for sparse robust linear regression, CLIME
for sparse precision matrix estimation, sparse differential network estimation,
and sparse Linear Programming Discriminant (LPD) analysis. We then provide
sufficient conditions under which PSM always outputs sparse solutions such that
its computational performance can be significantly boosted. Thorough numerical
experiments are provided to demonstrate the outstanding performance of the PSM
method.