Revisiting Frank-Wolfe for Structured Nonconvex Optimization
This provides an incremental improvement for researchers in optimization, offering a more efficient method for nonconvex problems with DC structure.
The paper tackles optimizing structured nonconvex functions using a new projection-free Frank-Wolfe method, achieving a first-order stationary point in O(1/ε²) iterations and, with specific decompositions, reducing gradient oracle calls to O(1/ε).
We introduce a new projection-free (Frank-Wolfe) method for optimizing structured nonconvex functions that are expressed as a difference of two convex functions. This problem class subsumes smooth nonconvex minimization, positioning our method as a promising alternative to the classical Frank-Wolfe algorithm. DC decompositions are not unique; by carefully selecting a decomposition, we can better exploit the problem structure, improve computational efficiency, and adapt to the underlying problem geometry to find better local solutions. We prove that the proposed method achieves a first-order stationary point in $O(1/ε^2)$ iterations, matching the complexity of the standard Frank-Wolfe algorithm for smooth nonconvex minimization in general. Specific decompositions can, for instance, yield a gradient-efficient variant that requires only $O(1/ε)$ calls to the gradient oracle. Finally, we present numerical experiments demonstrating the effectiveness of the proposed method compared to the standard Frank-Wolfe algorithm.