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 that this zig-zagging phenomenon can be viewed as an artifact of discretization, as when the method is viewed as an Euler discretization of a continuous time flow, that flow does not zig-zag. For this reason, we propose multistep Frank-Wolfe variants based on discretizations of the same flow whose truncation errors decay as $O(Delta^p)$, where $p$ is the methods order. We observe speedups using these variants, but at a cost of extra gradient calls per iteration. However, because the multistep methods present better search directions, we show that they are better able to leverage line search and momentum speedups.
Download