Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms
Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms
复制标题
DOI：
10.1287/opre.2019.1919
复制
发表时间：
2020-09-01
影响因子：
2.7
通讯作者：
Mazumder, Rahul
中科院分区：
文献类型：
--
作者：
Hazimeh, Hussein;Mazumder, Rahul
L-0-正则化最小二乘问题（L-O-Regularized Least Squares Problem）最佳子集）是稀疏统计学习的核心，并在更广泛的统计、机器学习和优化社区中引起了极大的关注。最近的工作表明，现代混合整数优化（MIO）求解器可以用来解决这个问题的小到中等的情况。尽管基于L-0的估计器和通用MIO求解器的有用性，但是当与流行的稀疏学习算法（例如，基于L-1正则化）。在本文中，我们的目标是推动一个家庭的L-0-正则化问题的额外凸处罚的计算前沿。我们提出了一个新的层次的必要的最优性条件，这些问题。我们开发快速算法，基于坐标下降和局部组合优化，保证收敛到满足这些最优性条件的解决方案。从统计学的角度来看，一个有趣的故事出现了。当信号强度高时，我们的组合优化算法在具有挑战性的统计设置中具有优势。当信号较低时，纯L-0受益于额外的凸正则化。我们凭经验证明，我们的基于L-0的估计器家族在各种制度下（例如，不同的信号强度、特征相关性、样本和特征的数量）。我们新的开源稀疏学习工具包L0 Learn（可在CRAN和GitHub上使用）与竞争工具包（如glmnet和ncvreg）相比，速度提高了三倍（p高达10（6））。
The L-0-regularized least squares problem (a.k.a. best subsets) is central to sparse statistical learning and has attracted significant attention across the wider statistics, machine learning, and optimization communities. Recent work has shown that modern mixed integer optimization (MIO) solvers can be used to address small to moderate instances of this problem. In spite of the usefulness of L-0-based estimators and generic MIO solvers, there is a steep computational price to pay when compared with popular sparse learning algorithms (e.g., based on L-1 regularization). In this paper, we aim to push the frontiers of computation for a family of L-0-regularized problems with additional convex penalties. We propose a new hierarchy of necessary optimality conditions for these problems. We develop fast algorithms, based on coordinate descent and local combinatorial optimization, that are guaranteed to converge to solutions satisfying these optimality conditions. Froma statistical viewpoint, an interesting story emerges. When the signal strength is high, our combinatorial optimization algorithms have an edge in challenging statistical settings. When the signal is lower, pure L-0 benefits from additional convex regularization. We empirically demonstrate that our family of L-0-based estimators can outperform the state-of-the-art sparse learning algorithms in terms of a combination of prediction, estimation, and variable selection metrics under various regimes (e.g., different signal strengths, feature correlations, number of samples and features). Our new open-source sparse learning toolkit L0Learn (available on CRAN and GitHub) reaches up to a threefold speedup (with p up to 10(6)) when compared with competing toolkits such as glmnet and ncvreg.