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
Source: 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.

SCOPUSTM   
Citations

53
checked on Feb 13, 2018

WEB OF SCIENCETM
Citations

37
checked on Jan 15, 2018

Page view(s)

10
checked on Feb 18, 2018

Google ScholarTM

Check

Altmetric


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