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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.