Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

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 nuclear-norm balls. 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 burn-in phase and up to a logarithmic factor, has LOO complexity that scales with r/√ε, where ε is the target accuracy and r is the solution sparsity (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/√ε) sparse projections and LOO calls (independently of both the ambient dimension and the sparsity level 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.