Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
复制标题
DOI：
--
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
A. Dedieu;Hussein Hazimeh;R. Mazumder
中科院分区：
文献类型：
--
作者：
A. Dedieu;Hussein Hazimeh;R. Mazumder
我们考虑了一种基于离散优化的方法来学习稀疏分类器，其中结果取决于一小部分特征的线性组合。最近的研究表明，混合整数规划（MIP）可用于解决（最优性）$\ell_0$正则化问题，其规模远远大于统计学和机器学习社区传统上认为可能的规模。尽管它们很有用，但与基于$\ell_1$-正则化和相关的相对成熟的算法相比，基于mip的方法要慢得多。我们的目标是通过开发新的基于mip的$\ell_0$正则化分类算法来弥合这一计算差距。我们提出了两类可扩展算法：一种精确算法，可以在几分钟内处理$p\约50,000$特征，以及近似算法，可以处理$p\约10^6$的实例，其时间可与快速的$\ell_1$算法相媲美。我们的精确算法基于\ textl{完整性生成}的新思想，它通过涉及少量二进制变量的混合整数程序序列来解决原始问题（使用$p$二进制变量）。我们的近似算法是基于坐标下降和局部组合搜索。此外，我们给出了一类$\ell_0$正则化估计的新的估计误差界。对真实数据和合成数据的实验表明，与竞争工具包相比，我们的方法导致模型具有显著改进的统计性能（特别是变量选择）。
We consider a discrete optimization based approach for learning sparse classifiers, where the outcome depends upon a linear combination of a small subset of features. Recent work has shown that mixed integer programming (MIP) can be used to solve (to optimality) $\ell_0$-regularized problems at scales much larger than what was conventionally considered possible in the statistics and machine learning communities. Despite their usefulness, MIP-based approaches are significantly slower compared to relatively mature algorithms based on $\ell_1$-regularization and relatives. We aim to bridge this computational gap by developing new MIP-based algorithms for $\ell_0$-regularized classification. We propose two classes of scalable algorithms: an exact algorithm that can handle $p\approx 50,000$ features in a few minutes, and approximate algorithms that can address instances with $p\approx 10^6$ in times comparable to fast $\ell_1$-based algorithms. Our exact algorithm is based on the novel idea of \textsl{integrality generation}, which solves the original problem (with $p$ binary variables) via a sequence of mixed integer programs that involve a small number of binary variables. Our approximate algorithms are based on coordinate descent and local combinatorial search. In addition, we present new estimation error bounds for a class of $\ell_0$-regularized estimators. Experiments on real and synthetic data demonstrate that our approach leads to models with considerably improved statistical performance (especially, variable selection) when compared to competing toolkits.