论文标题
Frank-Wolfe方法具有无限的可行区域，并应用于结构化学习
Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
论文作者
论文摘要
Frank-Wolfe（FW）方法是一种流行的算法，用于解决结构化统计学习中出现的大规模凸优化问题。但是，只有在可行区域有限时才能应用传统的Frank-Wolfe方法，这限制了其实践中的适用性。 $ \ ell_1 $趋势过滤问题和矩阵优化问题与广义核定常约束有关，我们研究了一个凸优化问题的家族，其中无界可行区域是无界线性子空间和有界约束集的直接总和。我们提出了两种新的Frank-Wolfe方法：无界的Frank-Wolfe方法（UFW）和无限制的夫妻Frank-Wolfe方法（UAFW），用于解决此类无界可行区域的凸出优化问题的家庭。我们表明，在适当的规律性条件下，无界的弗兰克 - 沃尔夫方法具有$ O（1/k）$ sublinear的收敛速度，而无限制的客场弗兰克 - 沃尔夫方法具有线性融合率，在可行的区域时，富兰克 - 沃尔夫方法的最著名结果匹配。此外，计算实验表明我们所提出的方法似乎超过了替代求解器。
The Frank-Wolfe (FW) method is a popular algorithm for solving large-scale convex optimization problems appearing in structured statistical learning. However, the traditional Frank-Wolfe method can only be applied when the feasible region is bounded, which limits its applicability in practice. Motivated by two applications in statistical learning, the $\ell_1$ trend filtering problem and matrix optimization problems with generalized nuclear norm constraints, we study a family of convex optimization problems where the unbounded feasible region is the direct sum of an unbounded linear subspace and a bounded constraint set. We propose two new Frank-Wolfe methods: unbounded Frank-Wolfe method (uFW) and unbounded Away-Step Frank-Wolfe method (uAFW), for solving a family of convex optimization problems with this class of unbounded feasible regions. We show that under proper regularity conditions, the unbounded Frank-Wolfe method has a $O(1/k)$ sublinear convergence rate, and unbounded Away-Step Frank-Wolfe method has a linear convergence rate, matching the best-known results for the Frank-Wolfe method when the feasible region is bounded. Furthermore, computational experiments indicate that our proposed methods appear to outperform alternative solvers.
