论文标题
对广义条件梯度法的安全筛选
Safe Screening for the Generalized Conditional Gradient Method
论文作者
论文摘要
条件梯度方法（CGM）已被广泛用于快速稀疏近似，对于结构化稀疏正规化器的每迭代计算成本较低。我们探讨了广义CGM（GCGM）的稀疏性获得属性，其中约束由基于量规罚款的惩罚函数代替；这可以在不显着增加触电计算的情况下完成，并适用于稀疏性的一般概念。在不假设有界的迭代次数的情况下，我们显示了$ O（1/t）$融合GCGM的功能值和间隙。我们将其与安全的筛选规则相结合，并表明以$ o（1/（tδ^2））$的速率，筛选的支持与解决方案的支撑匹配，其中$δ\ geq 0 $衡量问题与退化的距离有多近。在我们的实验中，我们表明这些修改后的惩罚的GCGM具有类似的特征选择属性与常见惩罚相似，但在选择高参数的选择上可能具有更高的稳定性。
The conditional gradient method (CGM) has been widely used for fast sparse approximation, having a low per iteration computational cost for structured sparse regularizers. We explore the sparsity acquiring properties of a generalized CGM (gCGM), where the constraint is replaced by a penalty function based on a gauge penalty; this can be done without significantly increasing the per-iteration computation, and applies to general notions of sparsity. Without assuming bounded iterates, we show $O(1/t)$ convergence of the function values and gap of gCGM. We couple this with a safe screening rule, and show that at a rate $O(1/(tδ^2))$, the screened support matches the support at the solution, where $δ\geq 0$ measures how close the problem is to being degenerate. In our experiments, we show that the gCGM for these modified penalties have similar feature selection properties as common penalties, but with potentially more stability over the choice of hyperparameter.
