Please use this identifier to cite or link to this item: https://doi.org/10.1109/TPAMI.2011.177
Title: Sparse algorithms are not stable: A no-free-lunch theorem
Authors: Xu, H. 
Caramanis, C.
Mannor, S.
Keywords: Lasso
regularization
sparsity
Stability
Issue Date: 2012
Citation: Xu, H., Caramanis, C., Mannor, S. (2012). Sparse algorithms are not stable: A no-free-lunch theorem. IEEE Transactions on Pattern Analysis and Machine Intelligence 34 (1) : 187-193. ScholarBank@NUS Repository. https://doi.org/10.1109/TPAMI.2011.177
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.
Source Title: IEEE Transactions on Pattern Analysis and Machine Intelligence
URI: http://scholarbank.nus.edu.sg/handle/10635/85653
ISSN: 01628828
DOI: 10.1109/TPAMI.2011.177
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.