Stable Variable Selection for Sparse Linear Regression in a Non-uniqueness Regime

Abstract

This thesis presents a comprehensive investigation of the LASSO method in a non-uniqueness regime and its ability of stable variable selection. We characterize when LASSO may have non-unique solutions through a sufficient and necessary condition, and how these non-unique solutions behave geometrically: all solutions must lie in the same simplex within the same orthant, and they form a polytope structure in which each corner represents the most parsimonious collection of features that does not contain other corners. Leveraging this geometric structure, this work then explores what to do to practically obtain these estimators, by proposing an efficient sampling algorithm that returns uniformly distributed points on the polytope.We present a non-asymptotic analysis of the l_2 coefficient error and feature selection consistency for the non-unique LASSO, by restricting necessary conditions (the eigenvalue condition and mutual incoherence condition) to a certain direction or a subset of features. Our theoretical results show that, under strong assumptions, the non-unique LASSO is as theoretically efficient as the original LASSO. Moreover, when dealing with linearly combined features in a dataset, numerical experiments demonstrate the superior stable variable selection performance of our proposed non-unique LASSO over other existing algorithms, particularly if the proper tuning parameters can be selected.