论文标题
多步弗兰克 - 沃尔夫方法
A Multistep Frank-Wolfe Method
论文作者
论文摘要
Frank-Wolfe算法已经重新获得了其在结构受限的机器学习应用中的使用。但是，Frank-Wolfe算法的一个主要局限性是由于曲折的行为而导致的局部收敛属性缓慢。我们将Frank-Wolfe方法中的曲折现象视为离散化的工件，并提出了多步弗兰克 - 沃尔夫变种，其中截断错误衰减为$ o（δ^p）$，其中$ p $是该方法的顺序。该策略“稳定”了该方法，并允许线路搜索和动力等工具获得更多好处。但是，我们的结果表明，最糟糕的情况是runge-kutta型离散化方案的最坏情况，这取决于$ k $的速率，而香草弗兰克·沃尔夫方法的收敛速度无法改善。尽管如此，我们认为这种分析增加了对优化方法的流动分析知识的越来越多，并且是关于多步方法最终有用性的一个警示故事。
The Frank-Wolfe algorithm has regained much interest in its use in structurally constrained machine learning applications. However, one major limitation of the Frank-Wolfe algorithm is the slow local convergence property due to the zig-zagging behavior. We observe the zig-zagging phenomenon in the Frank-Wolfe method as an artifact of discretization, and propose multistep Frank-Wolfe variants where the truncation errors decay as $O(Δ^p)$, where $p$ is the method's order. This strategy "stabilizes" the method, and allows tools like line search and momentum to have more benefits. However, our results suggest that the worst case convergence rate of Runge-Kutta-type discretization schemes cannot improve upon that of the vanilla Frank-Wolfe method for a rate depending on $k$. Still, we believe that this analysis adds to the growing knowledge of flow analysis for optimization methods, and is a cautionary tale on the ultimate usefulness of multistep methods.
