In this paper, we propose approximate Frank-Wolfe (FW) algorithms to solve convex optimization problems over graph-structured support sets where the textit{linear minimization oracle} (LMO) cannot be efficiently obtained in general. We first demonstrate that two popular approximation assumptions (textit{additive} and textit{multiplicative gap errors)}, are not valid for our problem, in that no cheap gap-approximate LMO oracle exists in general. Instead, a new textit{approximate dual maximization oracle} (DMO) is proposed, which approximates the inner product rather than the gap. When the objective is $L$-smooth, we prove that the standard FW method using a $delta$-approximate DMO converges as $mathcal{O}(L / delta t + (1-delta)(delta^{-1} + delta^{-2}))$ in general, and as $mathcal{O}(L/(delta^2(t+2)))$ over a $delta$-relaxation of the constraint set. Additionally, when the objective is $mu$-strongly convex and the solution is unique, a variant of FW converges to $mathcal{O}(L^2log(t)/(mu delta^6 t^2))$ with the same per-iteration complexity. Our empirical results suggest that even these improved bounds are pessimistic, with significant improvement in recovering real-world images with graph-structured sparsity.
Download