Efficient L1 Regularized Logistic Regression

Su-In Lee, Honglak Lee, Pieter Abbeel, Andrew Y. NgAAAI 2006 · OpenReview

Abstract

L1 regularized logistic regression is a workhorse of machine learning, widely used for classification problems with many features. Solving the underlying convex optimization problem efficiently is challenging, as standard algorithms do not scale well to large datasets. We propose an efficient algorithm, IRLS-LARS, that iteratively approximates the objective function with a quadratic approximation and solves the resulting subproblem using the Least Angle Regression (LARS) algorithm. Our theoretical results guarantee convergence to the global optimum. Experimental results demonstrate that our algorithm significantly outperforms both standard convex optimization solvers and four previously published specialized algorithms.

Introduction

In modern machine learning, classification tasks frequently involve high-dimensional feature spaces with relatively few training examples. L1 regularization (Lasso) is the preferred approach in these scenarios because it encourages sparsity, effectively performing automatic feature selection by driving the weights of irrelevant features to zero.

However, L1 regularized logistic regression is computationally demanding. The L1 penalty introduces non-differentiability at zero, causing standard solvers like Newton’s method or Conjugate Gradient to struggle. Practitioners often resort to smooth approximations or a large number of constraints, both of which can compromise speed or accuracy. This paper introduces IRLS-LARS, a solver designed to handle these discontinuities efficiently while maintaining theoretical guarantees of global optimality.

Methodology

The IRLS-LARS algorithm utilizes a two-level iterative approach to solve the optimization problem:

  1. Outer Loop (IRLS): The algorithm employs the Iteratively Reweighted Least Squares (IRLS) framework. At each step, the complex logistic regression objective is approximated by a simpler quadratic function (a weighted least squares problem) centered at the current parameter estimate.
  2. Inner Loop (LARS): Under L1 regularization, each IRLS step becomes an L1-constrained quadratic optimization problem. The authors solve this using the LARS (Least Angle Regression) algorithm, which is highly efficient for building solution paths incrementally by adding one feature at a time.

To ensure global convergence, the algorithm incorporates a backtracking line search, ensuring the objective function decreases at every iteration. This is supported by a formal proof showing that for objective functions with continuous third derivatives (like logistic regression), the method converges to the global optimum.

Experimental Evaluation

The authors evaluated IRLS-LARS on 12 diverse datasets, including nine UCI repository benchmarks (e.g., Arrhythmia, Spambase), the artificial Madelon dataset, and two high-dimensional gene expression Microarray datasets with up to 3,571 features.

Comparison with Specialized Algorithms

IRLS-LARS was compared against four specialized algorithms: Grafting, SCGIS, GenLasso, and Gl1ce. As shown in Figure 1, IRLS-LARS was the fastest algorithm on 11 out of the 12 test datasets, typically outperforming competitors by a factor of 8x to 10x. The only exception was the Microarray 2 dataset, where the C-based GenLASSO implementation held a slight edge over the MATLAB-based IRLS-LARS.

CPU time comparison of IRLS-LARS against specialized algorithms across various datasets.

Scaling with High Dimensionality

The performance advantage of IRLS-LARS is most evident in high-dimensional settings. When compared to standard convex optimization methods, the speedup can reach several orders of magnitude.

CPU time comparison of IRLS-LARS against standard convex optimization algorithms.

As detailed in the table above, standard methods like Newton's method (NM-epsL1) or Conjugate Gradient (CG-epsL1) often hit time limits or take hundreds of seconds on datasets where IRLS-LARS finishes in less than a second. For instance, on the Microarray 1 dataset, IRLS-LARS is over 7,000 times faster than the Newton-based approach. This demonstrates that the algorithm's focus on "active" features through LARS makes it uniquely suited for high-dimensional data where most features are irrelevant.

Conclusion

IRLS-LARS represents a significant advancement in solving L1 regularized logistic regression by exploiting the mathematical structure of the local quadratic approximation. By leveraging LARS for the inner optimization loop, the method naturally thrives on the sparsity inherent in high-dimensional data. While currently implemented in MATLAB, the algorithm already demonstrates significant leads over optimized C-based competitors, suggesting even greater potential for production-level implementations in low-level languages. Future work may extend this framework to other L1-constrained Generalized Linear Models (GLMs).

Summary updated

Abstract

Efficient L 1 Regularized Logistic Regression Su-In Lee, Honglak Lee, Pieter Abbeel, Andrew Y. Ng L1 regularized logistic regression is now a workhorse of machine learning: it is widely used for many classification problems, particularly ones with many features. L1 regularized logistic regression requires solving a convex optimization problem. However, standard algorithms for solving convex optimization problems do not scale well enough to handle the large datasets encountered in many practical settings. In this paper, we propose an efficient algorithm for L1 regularized logistic regression. Our algorithm iteratively approximates the objective function by a quadratic approximation at the current point. In each iteration, it uses the efficient LARS (Least Angle Regression) algorithm to solve the resulting quadratic optimization problem with the L1 constraints. Our theoretical results show that our algorithm is guaranteed to converge to the global optimum. Our experiments show that our algorithm significantly outperforms standard algorithms for solving convex optimization problems. Moreover, our algorithm outperforms four previously published algorithms that were specifically designed to solve the L1 regularized logistic regression problem. Subjects: 12. Machine Learning and Discovery This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.
BibTeX
@inproceedings{lee2006efficient,
  author = {Su-In Lee and Honglak Lee and Pieter Abbeel and Andrew Y. Ng},
  title = {{Efficient L1 Regularized Logistic Regression}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=H1Eg06eOZB},
}
Figure