论文标题
重新访问弗兰克·沃尔夫（Frank-Wolfe
Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
论文作者
论文摘要
近年来，证明经典的Frank-Wolfe算法（又称条件梯度算法）的简单修改，以便在凸和紧凑型多面体上平滑凸的最小化，并以线性速率收敛，假设目标函数具有四倍的生长特性。但是，这些方法的速率明确取决于问题的维度，该维度无法解释其大规模问题的经验成功。在本文中，我们首先证明已经出于非常简单的问题，即使最佳解决方案位于多层的低维脸上，也无法在最坏的情况下避免这种依赖性。然后，我们重新审视沃尔夫（Wolfe）的古典书中已经考虑过的严格互补性假设\ cite {wolfe1970}，并证明在这种情况下，具有外客台面和线路搜索的Frank-Wolfe方法与速率与速度汇总，这仅取决于最佳面部最佳面的尺寸。我们通过证明这意味着最佳噪声解决方案的稀疏性来激发严格的互补性。
In recent years it was proved that simple modifications of the classical Frank-Wolfe algorithm (aka conditional gradient algorithm) for smooth convex minimization over convex and compact polytopes, converge with linear rate, assuming the objective function has the quadratic growth property. However, the rate of these methods depends explicitly on the dimension of the problem which cannot explain their empirical success for large scale problems. In this paper we first demonstrate that already for very simple problems and even when the optimal solution lies on a low-dimensional face of the polytope, such dependence on the dimension cannot be avoided in worst case. We then revisit the addition of a strict complementarity assumption already considered in Wolfe's classical book \cite{Wolfe1970}, and prove that under this condition, the Frank-Wolfe method with away-steps and line-search converges linearly with rate that depends explicitly only on the dimension of the optimal face. We motivate strict complementarity by proving that it implies sparsity-robustness of optimal solutions to noise.
