Abstract
Highly optimized toolkit for approximately solving L0-regularized learning problems (a.k.a. best subset selection). The algorithms are based on coordinate descent and local combinatorial search. For more details, check the paper by Hazimeh and Mazumder (2020) doi:10.1287/opre.2019.1919.
Introduction
In high-dimensional statistics, identifying a small subset of relevant predictors from a large pool of candidates is a fundamental challenge. This property, known as sparsity, is traditionally addressed using the Lasso (L1 regularization). While Lasso is computationally efficient due to its convexity, it often suffers from biased estimates and poor selection performance when variables are highly correlated.
The ideal approach is Best Subset Selection, which employs an L0 penalty to directly constrain the number of non-zero coefficients. Historically, L0 optimization was considered computationally intractable for large-scale problems. The L0Learn package bridges this gap by providing highly optimized approximate algorithms that scale to high-dimensional datasets while maintaining the superior statistical properties of L0-based methods.
Methodology
L0Learn implements several key algorithmic innovations to solve the L0-regularized objective efficiently:
Coordinate Descent and Local Search
The core of the package relies on a fast Coordinate Descent (CD) algorithm. To improve the quality of the local optima found by CD, the package incorporates a local combinatorial search (CDPSI). This search mechanism performs variable swaps to explore the solution space more thoroughly, effectively escaping poor local minima that often plague non-convex optimization.
Hybrid Penalties
Recognizing that pure L0 selection can sometimes be unstable, L0Learn supports hybrid penalties, specifically L0L1 (L0 + Lasso) and L0L2 (L0 + Ridge). These combinations allow users to leverage the selection power of L0 while benefiting from the stability and grouping effects of L1 or L2 penalties, which is particularly useful in the presence of multicollinearity.
Pathwise Optimization
The software computes the entire regularization path efficiently. By using "warm starts"—where the solution for a specific sparsity level serves as the initialization for the next—the algorithm significantly reduces the total computation time across a grid of tuning parameters.
Software Implementation
The package is built with a high-performance C++ backend using the RcppArmadillo library. This ensures that the computationally intensive optimization routines are executed with maximum efficiency.
As shown in the package documentation, L0Learn provides a comprehensive suite of functions that mirror the standard R modeling workflow, including fitting, cross-validation, and prediction, making it accessible to practitioners familiar with tools like glmnet.
Data Generation and Benchmarking
To facilitate rigorous testing and benchmarking, L0Learn includes built-in tools for generating synthetic datasets. These tools allow researchers to simulate various scenarios, including standard sparse models and cases with high feature correlation.
The GenSynthetic function, as detailed in the figure above, allows for precise control over the number of samples ($n$), features ($p$), and non-zero coefficients ($k$), as well as the signal-to-noise ratio (SNR).
Results and Discussion
Empirical results demonstrate that L0Learn can handle thousands of features on a standard laptop. The package supports multiple loss functions, including Squared Error for regression and Logistic or Squared Hinge loss for classification. This versatility makes it a robust alternative for practitioners seeking sparser and more interpretable models without the computational overhead of exact Mixed-Integer Programming solvers.
Conclusion
L0Learn democratizes access to Best Subset Selection by providing a scalable, user-friendly toolkit. While the underlying problem remains non-convex and global optimality is not guaranteed, the combination of coordinate descent and local search provides high-quality solutions that often outperform traditional convex relaxations in practical applications. Future work may involve extending the package to support a wider range of generalized linear models, such as Cox regression.
Summary updated