Parametric Simplex Method for Sparse Learning
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 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.
This paper extends simplex algorithm to several sparse learning problem with regularization parameter. The proposed method can collect all the solutions (corresponding to different values of the regularization parameter) in the process of simplex algorithm. It is an efficient way to get the sparse solution path and avoid tuning the regularization parameter. The connection between path Dantzig selector formulation and sensitivity analysis looks interesting to me.
Major comments:
- The method used in this paper seems closely related to the sensitivity analysis of LP. What is the key difference? It looks like just an application of sensitivity analysis.
- The paper mentioned that the number of iterations is linear in the number of nonzero variables empirically. Is there any guarantee for such linear dependency?
Experiment:
- Table 1 is not necessary since PSM never violate the constraints.
- Simplex method is not very efficient for large scale LP. I did not see comparison with interior based approaches or primal dual approaches. Authors are expected to make such comparison to experiments more convincing.
Typo/question:
line 122: z^+, z^- => t^+, t^-
line 291: solutio => solution
line 195: what is the relation between the feasibility condition and the sign of b and c?
line 201: \bar{x}_B and \bar{z}_N are always positive? (otherwise how to always guarantee the feasibility when \lambda is large)
line 207: here we see an upper-bound for \lambda, it contradicts the claim that the feasibility will be guaranteed when \lambda is large enough. In addition, is it possible that \lambda_min > \lambda_max?
line 236: can we guarantee that there is no cycle in such searching?