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.
翻译:最近引入的稀薄优化问题“安全筛选”技术使我们得以在优化的早期阶段确定无关的变量。在本文中,我们首先提出一个基于Fenchel-Rockafellar双重性的安全筛选的灵活框架,然后根据框架为规范正规化的最小方块制定强有力的安全筛选规则。我们称拟议的规范正规化最低方块的筛选规则“Sasvi ”, 因为它可以被解释为对Sasvi的概括化。 与原Sasvi不同的是,它并不要求精确地解决更严格常规化的问题;因此,它在实践中是安全的。我们表明,与理论上和实验上的其他筛选规则相比,我们的筛选规则可以消除更多的特征,提高解决问题者的速度。