An Efficient Method for Large-Scale l1-Regularized Convex Loss Minimization

Convex loss minimization with lscr₁ regularization has been proposed as a promising method for feature selection in classification (e.g., lscr₁-regularized logistic regression) and regression (e.g., lscr₁-regularized least squares). In this paper we describe an efficient interior-point method for solving large-scale lscr₁-regularized convex loss minimization problems that uses a preconditioned conjugate gradient method to compute the search step. The method can solve very large problems. For example, the method can solve an lscr₁-regularized logistic regression problem with a million features and examples (e.g., the 20 Newsgroups data set), in a few minutes, on a PC.