Sparse Algorithms Are Not Stable: A No-Free-Lunch Theorem

作者：Xu Huan^*; Caramanis Constantine; Mannor Shie

来源：IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(1): 187-193.

DOI：10.1109/TPAMI.2011.177

• Stability
• sparsity
• Lasso
• regularization

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 l(1)-regularized regression (Lasso) cannot be stable, while l(2)-regularized regression is known to have strong stability properties and is therefore not sparse.

• 出版日期2012-1