Uncorrelated Lasso

Sibao Chen, Chris H. Q. Ding, Bin Luo, Ying XieAAAI 2013 · DOI

Introduction

In high-dimensional data analysis, such as genomics or finance, the number of predictors ($p$) often significantly exceeds the number of observations ($n$). Identifying a compact, discriminative subset of features is critical for model interpretability and performance. While the standard Lasso method effectively enforces sparsity through an $l_1$-penalty, it often fails to account for correlations between predictors, leading to the arbitrary selection of redundant variables. Conversely, the Elastic Net tends to select entire groups of correlated variables, which can lead to inefficient, over-parameterized models.

This paper introduces Uncorrelated Lasso (ULasso), a novel approach presented at AAAI 2013. ULasso addresses these limitations by simultaneously enforcing sparsity and decorrelation, ensuring that the selected features are not only predictive but also non-redundant.

Methodology

ULasso extends the classic least-squares objective function by incorporating two distinct penalties:

  1. Sparsity Penalty ($\lambda_1\|\beta\|_1$): The standard $l_1$-norm penalty used in Lasso to shrink coefficients and perform variable selection.
  2. Decorrelation Penalty ($\lambda_2\beta^\top C\beta$): A new quadratic term where $C$ is defined as the Hadamard product (element-wise square) of the correlation matrix ($C = R \odot R$).

By using the square of the correlation coefficients ($r_{kl}^2$), the penalty treats strong positive and strong negative correlations equally as indicators of redundancy. This forces the model to prioritize a set of predictors that are highly correlated with the response variable but minimally correlated with each other.

The authors developed an iterative algorithm to solve this objective function, alternating between updating a diagonal weighting matrix and the regression coefficients. They mathematically proved that this algorithm converges to a unique global optimum, ensuring robust performance.

Experimental Results

The performance of ULasso was evaluated on two benchmark bioinformatics datasets: the Colon Cancer dataset (2,000 genes, 62 samples) and the Leukemia dataset (7,129 genes, 72 samples).

Colon Cancer Dataset

On the Colon Cancer dataset, ULasso achieved a Leave-One-Out Cross-Validation (LOOCV) accuracy of 93.55% using only 12 genes. As shown in the comparison below, this significantly outperforms standard Lasso, Elastic Net, and even high-dimensional Support Vector Machines (SVM).

Comparison of classification methods on the Colon Cancer dataset.

Leukemia Dataset

In the Leukemia dataset experiments, ULasso demonstrated exceptional generalization. On the test set, it achieved 100% accuracy using 22 genes. In contrast, both Lasso and Elastic Net reached approximately 91% accuracy with a similar number of features.

Performance comparison on the Leukemia dataset, showing ULasso achieving perfect test accuracy.

Discussion and Key Insights

The core advantage of ULasso lies in its information efficiency. By penalizing redundancy, the model avoids wasting "model real estate" on variables that provide overlapping information. This is particularly valuable in biological contexts where multiple genes may belong to the same pathway; ULasso identifies the most representative signal from each independent pathway.

Furthermore, ULasso acts as a generalization of existing methods: it reverts to standard Lasso when $\lambda_2 = 0$ and behaves similarly to Elastic Net when predictors are already uncorrelated. The algorithm is also computationally efficient, typically converging in fewer than 20 iterations.

Conclusion

Uncorrelated Lasso provides a powerful framework for feature selection in "small $n$, large $p$" scenarios. By integrating a decorrelation penalty, it identifies more informative and less redundant feature subsets than traditional regularization methods. Future work may involve optimizing the calculation of the $p \times p$ correlation matrix for ultra-high-dimensional datasets and exploring non-linear extensions to capture more complex variable interactions.

Summary updated

BibTeX
@inproceedings{chen2013uncorrelated,
  author = {Sibao Chen and Chris H. Q. Ding and Bin Luo and Ying Xie},
  title = {{Uncorrelated Lasso}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8576},
}
Figure