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

We consider two widely used notions in machine learning, namely: sparsity and algorithmic stability. Both notions are deemed desirable in designing algorithms, and are believed to lead to good generalization ability. In this paper, we show that these two notions contradict each other. That is, a sparse algorithm can not be stable and vice versa. Thus, one has to tradeoff sparsity and stability in designing a learning algorithm. In particular, our general result implies that lscr¹-regularized regression (Lasso) cannot be stable, while lscr²-regularized regression is known to have strong stability properties.