An interior-point method for large-scale \(l_1\)-regularized logistic regression. (English) Zbl 1222.62092

Koh, Kwangmoo; Kim, Seung-Jean; Boyd, Stephen

J. Mach. Learn. Res. 8, 1519-1555 (2007).

Summary: Logistic regression with \(l_1\) regularization has been proposed as a promising method for feature selection in classification problems. We describe an efficient interior-point method for solving large-scale \(l_1\)-regularized logistic regression problems. Small problems with up to a thousand or so features and examples can be solved in seconds on a PC; medium sized problems, with tens of thousands of features and examples, can be solved in tens of seconds (assuming some sparsity in the data). A variation on the basic method, that uses a preconditioned conjugate gradient method to compute the search step, can solve very large problems, with a million features and examples (e.g., the 20 Newsgroups data set), in a few minutes, on a PC. Using warm-start techniques, a good approximation of the entire regularization path can be computed much more efficiently than by solving a family of problems independently.

MSC:

62J12	Generalized linear models (logistic models)
65C60	Computational problems in statistics (MSC2010)

Keywords:

feature selection; \(l_1\) regularization; regularization path; interior point methods