.png){kind=icon}
返回
Sparse classification: a scalable discrete optimization perspective
.png){kind=icon}
OA
AI
DOI：10.1007/s10994-021-06085-5.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We formulate the sparse classification problem of n samples with p features as a binary convex optimization problem and propose a outer-approximation algorithm to solve it exactly. For sparse logistic regression and sparse SVM, our algorithm finds optimal solutions for n and p in the 10,000 s within minutes. On synthetic data our algorithm achieves perfect support recovery in the large sample regime. Namely, there exists an n(0) such that the algorithm takes a long time to find an optimal solution and does not recover the correct support for n < n(0), while for n >= n(0), the algorithm quickly detects all the true features, and does not return any false features. In contrast, while Lasso accurately detects all the true features, it persistently returns incorrect features, even as the number of observations increases. Consequently, on numerous real-world experiments, our outer-approximation algorithms returns sparser classifiers while achieving similar predictive accuracy as Lasso. To support our observations, we analyze conditions on the sample size needed to ensure full support recovery in classification. For k-sparse classification, and under some assumptions on the data generating process, we prove that information-theoretic limitations impose n(0) < C(2 + sigma(2)) k log(p - k), for some constant C > 0.
Keyword:
Sparse classification
Binary convex optimization
Support recovery
期刊
IF:
2.9
论文数:
2.7K
被引数:
3.4W
机构
引用论文
Dual coordinate descent methods for logistic regression and maximum entropy modelslogistic回归和最大熵模型的双坐标下降方法.png)
MACHINE LEARNINGOAAI
MACHINE LEARNINGIF2.9
OAAI分享收藏分享收藏
查看更多内容