Sparse algorithms are not stable: A no-free-lunch theorem

Abstract

We consider two desired properties of learning algorithms: sparsity and algorithmic stability. Both properties are believed to lead to good generalization ability. We show that these two properties are fundamentally at odds with each other: A sparse algorithm cannot be stable and vice versa. Thus, one has to trade off sparsity and stability in designing a learning algorithm. In particular, our general result implies that l1-regularized regression (Lasso) cannot be stable, while l2-regularized regression is known to have strong stability properties and is therefore not sparse. © 2012 IEEE.