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

Huan Xu, Shie Mannor, Constantine CaramanisAllerton 2008 · OpenReview

Abstract

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 l1-regularized regression (Lasso) cannot be stable, while l2-regularized regression is known to have strong stability properties.
BibTeX
@inproceedings{xu2008sparse,
  author = {Huan Xu and Shie Mannor and Constantine Caramanis},
  title = {{Sparse algorithms are not stable: A no-free-lunch theorem}},
  booktitle = {Allerton},
  year = {2008},
  url = {https://openreview.net/forum?id=2MCZZJX2Ea},
}

Loading related content...

Figure