Efficient Lasso training from a geometrical perspective

The Lasso (L1-penalized regression) has drawn great interests in machine learning and statistics due to its robustness and high accuracy. A variety of methods have been proposed for solving the Lasso. But for large scale problems, the presence of L1 norm constraint significantly impedes the efficiency. Inspired by recent theoretical and practical contributions on the close relation between Lasso and SVMs, we reformulate the Lasso as a problem of finding the nearest point in a polytope to the origin, which circumvents the L1 norm constraint. This problem can be solved efficiently from a geometric perspective using the Wolfe׳s method. Comparing with least angle regression (LARS), which is a conventional method to solve Lasso, the proposed algorithm is advantageous in both efficiency and numerical stability. Experimental results show that the proposed approach is competitive with other state-of-the-art Lasso solvers on large scale problems.