tlars: The T-LARS Algorithm: Early-Terminated Forward Variable Selection

Jasin Machkour, Simon Tien, Daniel P. Palomar, Michael MumaOpenalex Unknown 2022 · DOI · OpenAlex

Abstract: Computes the solution path of the Terminating-LARS (T-LARS) algorithm. The T-LARS algorithm is a major building block of the T-Rex selector (see R package 'TRexSelector'). The package is based on the papers Machkour, Muma, and Palomar (2022) doi:10.48550/arXiv.2110.06048, Efron, Hastie, Johnstone, and Tibshirani (2004) doi:10.1214/009053604000000067, and Tibshirani (1996) doi:10.1111/j.2517-6161.1996.tb02080.x.

Introduction

In modern data science, high-dimensional problems where the number of potential predictors ($p$) far exceeds the number of observations ($n$) are common. Traditional variable selection methods, such as the LASSO or standard Least Angle Regression (LARS), aim to find sparse sets of relevant variables but often struggle with stability and False Discovery Rate (FDR) control, frequently picking up noise variables alongside the true signal.

The tlars package provides a high-performance R interface for the Terminating-LARS (T-LARS) algorithm, a specialized variant of LARS. By integrating "dummy" variables and an early-stopping criterion, it serves as the computational engine for robust variable selection frameworks like the T-Rex selector.

Methodology

The T-LARS algorithm addresses the limitations of standard LARS by introducing a strategic stopping point. Instead of calculating the entire solution path—which becomes increasingly unreliable as more variables are added—T-LARS uses randomly generated noise variables ("dummies") as a benchmark. The algorithm terminates once a specific number of these dummy variables have been included in the model, effectively cutting off the selection process before it descends into overfitting.

Parameters for the T-LARS algorithm implementation, including the early-stopping mechanism.

The package implements this using a mix of R and C++ via Rcpp and RcppArmadillo. The core logic resides in the tlars_cpp class, ensuring heavy linear algebra is executed with C++ efficiency. Key parameters include T_stop, which defines the number of dummies after which the selection process stops, and early_stop, which determines whether to compute the entire path or terminate early.

Implementation and Visualization

The package includes the Gauss_data dataset, a synthetic Gaussian linear model with $n = 50$ and $p = 100$, where only 3 variables are true signals. This provides a benchmark for testing support recovery.

One of the package's strengths is its flexible visualization. The plot.Rcpp_tlars_cpp method provides a clear visual representation of the solution path. It can highlight exactly where real variables enter the model relative to dummy variables, which are marked as 'D' on the plot axis.

Plotting parameters for visualizing the T-LARS solution path, including options to display dummy variables.

Key Insights and Limitations

The most elegant idea in T-LARS is using noise as a "canary in the coal mine." By observing when the algorithm starts selecting known noise, researchers can objectively decide when to stop trusting the selection path. Furthermore, the tlars_model function allows the selection process to be restarted or modified without recomputing from scratch by storing the "state" of the LARS process, which is vital for parallel processing.

However, the effectiveness of the early-stopping rule depends on the quality and generation strategy of the dummy variables. While the backend is efficient C++, extremely high-dimensional matrices (tens of thousands of variables) may still encounter memory limits inherent to the R environment and the Armadillo library. Future work may involve broader integration with machine learning pipelines like caret or tidymodels to make this stopping logic more accessible.

Summary updated

Abstract

Computes the solution path of the Terminating-LARS (T-LARS) algorithm. The T-LARS algorithm is a major building block of the T-Rex selector (see R package 'TRexSelector'). The package is based on the papers Machkour, Muma, and Palomar (2022) &lt;<a href="https://doi.org/10.48550/arXiv.2110.06048" target="_top">doi:10.48550/arXiv.2110.06048</a>&gt;, Efron, Hastie, Johnstone, and Tibshirani (2004) &lt;<a href="https://doi.org/10.1214%2F009053604000000067" target="_top">doi:10.1214/009053604000000067</a>&gt;, and Tibshirani (1996) &lt;<a href="https://doi.org/10.1111%2Fj.2517-6161.1996.tb02080.x" target="_top">doi:10.1111/j.2517-6161.1996.tb02080.x</a>&gt;.
BibTeX
@inproceedings{machkour2022tlars,
  author = {Jasin Machkour and Simon Tien and Daniel P. Palomar and Michael Muma},
  title = {{tlars: The T-LARS Algorithm: Early-Terminated Forward Variable Selection}},
  booktitle = {Openalex Unknown},
  year = {2022},
  doi = {10.32614/cran.package.tlars},
}
Figure