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:
- 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.
- 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.
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.
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