Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets
This work provides improved convergence guarantees for projection-free optimization, which is incremental but addresses a known bottleneck in constrained optimization for machine learning and related fields.
The paper tackles optimization over strongly convex constraint sets using Frank-Wolfe methods, showing that a variant without line search achieves faster convergence and that with line search, it converges to global optima for quasi-convex functions and to stationary points for non-convex functions at a rate of O(1/t).
We revisit the Frank-Wolfe (FW) optimization under strongly convex constraint sets. We provide a faster convergence rate for FW without line search, showing that a previously overlooked variant of FW is indeed faster than the standard variant. With line search, we show that FW can converge to the global optimum, even for smooth functions that are not convex, but are quasi-convex and locally-Lipschitz. We also show that, for the general case of (smooth) non-convex functions, FW with line search converges with high probability to a stationary point at a rate of $O\left(\frac{1}{t}\right)$, as long as the constraint set is strongly convex -- one of the fastest convergence rates in non-convex optimization.