High dimensional sparse learning has imposed a great computational challenge to large scale data analysis. In this paper, we investiage 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). PSM 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, sparse support vector machine for sparse linear classification, and sparse differential network estimation. 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.

The paper by Lustig, Marsten, and Shanno (LMS) gives an excellent presentation of the current state of the art for interior-point methods (as represented by their OB1 code) as it compares to the current state of the art for the simplex method (represented by OSL). The paper is well organized and thoughtful. The results of their experiments clearly indicate that for large problems interior-point methods offer a serious alternative to the simplex method. In these comments, we will try to clarify the relation among some of the algorithms discussed in LMS. In addition, we will compare the implementation strategy described in LMS, which is based on solving the so-called normal equations, to an alternative implementation strategy based on solving the so-called reduced Karush-Kuhn-Tucker (KKT) system. We will show that for many problems the two approaches yield virtually identical results but, for certain classes of challenging problems, the reduced KKT approach yields a much more efficient code. Also, we will argue that the reduced KKT system approach is more easily extended to quadratic and convex optimization problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper describes an implementation of the one-phase primal-dual path-following algorithm for solving linear programming problems. The design is intended to be simple, portable and robust. These design goals are achieved without sacrificing state-of-the-art performance. We give a rather complete description of the algorithm and the implementation. Computational results obtained for the NETLIB suite of problems run on a Silicon Graphics workstation are also presented. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.