Sparse algorithms are not stable: A no-free-lunch theorem
Lists
Only you see this
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...