Reference EPFL-ARTICLE-229257 URL: http: arxiv.org abs 0903.4856 Record created on 2017-06-21, modified on 2017-06-21
Instead of using our described generic criss-cross method, another obvious way to avoid degeneracies caused by singular sub-matrices in the objective function is to add a small value @math to each diagonal entry of the original matrix @math ; subsequently, all simple methods for the regular case such as @cite_8 @cite_11 can be used. There are several problems with this approach. First of all, the rank of the objective function matrix is blown up artificially, and the potential of using efficient small-rank-QP methods would be wasted. Secondly, the solution path of the perturbed problem may differ substantially from that of the original problem; in particular, the perturbation may lead to a much higher number of bends and therefore higher tracking cost, and the computed solutions could be far off the real solutions. In contrast, our criss cross method avoids all these issues, since it always solves the original unperturbed problem.
@cite_11 @cite_8
2057682568 2133958955
We consider the generic regularized optimization problem β(λ) = argminβ L(y, Xβ) + λJ(β). Efron, Hastie, Johnstone and Tibshirani [Ann. Statist. 32 (2004) 407-499] have shown that for the LASSO-that is, if L is squared error loss and J(β) = ∥β∥ 1 is the l 1 norm of β-the optimal coefficient path is piecewise linear, that is, ∂β(λ) ∂λ. is piecewise constant. We derive a general characterization of the properties of (loss L, penalty J) pairs which give piecewise linear coefficient paths. Such pairs allow for efficient generation of the full regularized coefficient paths. We investigate the nature of efficient path following algorithms which arise. We use our results to suggest robust versions of the LASSO for regression and classification, and to develop new, efficient algorithms for existing problems in the literature, including Mammen and van de Geer's locally adaptive regression splines. The support vector machine (SVM) is a widely used tool for classification. Many efficient implementations exist for fitting a two-class SVM model. The user has to supply values for the tuning parameters: the regularization cost parameter, and the kernel parameters. It seems a common practice is to use a default value for the cost parameter, often leading to the least restrictive model. In this paper we argue that the choice of the cost parameter can be critical. We then derive an algorithm that can fit the entire path of SVM solutions for every value of the cost parameter, with essentially the same computational cost as fitting one SVM model. We illustrate our algorithm on some examples, and use our representation to give further insight into the range of SVM solutions.