论文标题
势头如何帮助弗兰克·沃尔夫（Frank Wolfe）？
How Does Momentum Help Frank Wolfe?
论文作者
论文摘要
我们揭示了Frank Wolfe（FW）型算法与加速梯度方法（AGM）中动量之间的连接。在负面，这些连接说明了为什么动量不太可能对FW型算法有效。另一方面，此链接背后的令人鼓舞的信息是，势头对FW在一类问题上很有用。特别是，我们证明了FW的动量变体，即我们加速了弗兰克·沃尔夫（AFW），以更快的速度$ \ tilde {\ cal o}（\ frac {1} {1} {k^2} {k^2}）$在某些约束集上，尽管同样的$ {\ cal o}（\ cal o}（\ cal frac）（\ frac）（\ frac）（\ frac）（\ frac）= 1}。鉴于AFW可能以几乎没有额外的费用加速，因此它是FW的竞争替代品。基准的机器学习任务的数值实验进一步验证了我们的理论发现。
We unveil the connections between Frank Wolfe (FW) type algorithms and the momentum in Accelerated Gradient Methods (AGM). On the negative side, these connections illustrate why momentum is unlikely to be effective for FW type algorithms. The encouraging message behind this link, on the other hand, is that momentum is useful for FW on a class of problems. In particular, we prove that a momentum variant of FW, that we term accelerated Frank Wolfe (AFW), converges with a faster rate $\tilde{\cal O}(\frac{1}{k^2})$ on certain constraint sets despite the same ${\cal O}(\frac{1}{k})$ rate as FW on general cases. Given the possible acceleration of AFW at almost no extra cost, it is thus a competitive alternative to FW. Numerical experiments on benchmarked machine learning tasks further validate our theoretical findings.
