Convergence Rate of Frank-Wolfe for Non-Convex Objectives
This provides a theoretical convergence guarantee for Frank-Wolfe in non-convex optimization, which is incremental as it extends existing results to a different algorithm.
The paper tackles the problem of analyzing the Frank-Wolfe algorithm for non-convex objectives, proving it achieves a stationary point at a rate of O(1/√t) with a Lipschitz continuous gradient, matching rates known for projected gradient methods.
We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of $O(1/\sqrt{t})$ on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).