Accelerating Frank-Wolfe via Averaging Step Directions
The Frank-Wolfe method is a popular method in sparse constrained
optimization, due to its fast per-iteration complexity. However, the tradeoff
is that its worst case global convergence is comparatively slow, and
importantly, is fundamentally slower than its flow rate--that is to say, the
convergence rate is throttled by discretization error. In this work, we
consider a modified Frank-Wolfe where the step direction is a simple weighted
average of past oracle calls. This method requires very little memory and
computational overhead, and provably decays this discretization error term.
Numerically, we show that this method improves the convergence rate over
several problems, especially after the sparse manifold has been detected.
Theoretically, we show the method has an overall global convergence rate of
$O(1/k^p)$, where $0< p < 1$; after manifold identification, this rate speeds
to $O(1/k^{3p/2})$. We also observe that the method achieves this accelerated
rate from a very early stage, suggesting a promising mode of acceleration for
this family of methods.