Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Hiroaki Yamada;M. Yamada
中科院分区：
文献类型：
--
作者：
Hiroaki Yamada;M. Yamada
最近引入的一种名为“安全筛选”的稀疏优化问题技术允许我们在优化的早期阶段识别不相关的变量。本文首先提出了一个基于fenchell - rockafellar对偶的灵活安全筛选框架，然后利用该框架导出了一个范数正则化最小二乘的强安全筛选规则。我们称所提出的范数正则化最小二乘筛选规则为“动态Sasvi”，因为它可以解释为Sasvi的泛化。与原始的Sasvi不同，它不需要更强正则化问题的精确解；因此，它在实践中是安全的。理论和实验结果表明，与其他筛选规则相比，我们的筛选规则可以消除更多的特征，提高求解器的速度。
A recently introduced technique for a sparse optimization problem called"safe screening"allows us to identify irrelevant variables in the early stage of optimization. In this paper, we first propose a flexible framework for safe screening based on the Fenchel-Rockafellar duality and then derive a strong safe screening rule for norm-regularized least squares by the framework. We call the proposed screening rule for norm-regularized least squares"dynamic Sasvi"because it can be interpreted as a generalization of Sasvi. Unlike the original Sasvi, it does not require the exact solution of a more strongly regularized problem; hence, it works safely in practice. We show that our screening rule can eliminate more features and increase the speed of the solver in comparison with other screening rules both theoretically and experimentally.