Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
This work provides accelerated algorithms for optimization problems with sparsity structures, such as polytopes and matrix domains, which is incremental but improves efficiency by reducing dependency on dimension.
The paper tackles the problem of accelerating Frank-Wolfe algorithms for smooth convex optimization over compact convex sets, achieving optimal worst-case first-order oracle complexity and sparsity-dependent linear optimization oracle complexity that scales with solution sparsity rather than ambient dimension.
We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and the unit nuclear-norm ball. A key technical ingredient is a complementarity condition that captures solution sparsity -- face dimension for polytopes and rank for matrices. We present two algorithms: (1) a purely linear optimization oracle (LOO) method for polytopes that has optimal worst-case first-order (FO) oracle complexity and, aside of a finite \emph{burn-in} phase and up to a logarithmic factor, has LOO complexity that scales with $r/\sqrtε$, where $ε$ is the target accuracy and $r$ is the solution sparsity $r$ (independently of the ambient dimension), and (2) a hybrid scheme that combines FW with a sparse projection oracle (e.g., low-rank SVDs for matrix domains with low-rank solutions), which also has optimal FO oracle complexity, and after a finite burn-in phase, only requires $O(1/\sqrtε)$ sparse projections and LOO calls (independently of both the ambient dimension and the rank of optimal solutions). Our results close a gap on how to accelerate recent advancements in linearly-converging FW algorithms for strongly convex optimization, without paying the price of the dimension.