Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
share
In this paper, we propose approximate Frank-Wolfe (FW) algorithms to solve convex optimization problems over graph-structured support sets where the linear minimization oracle (LMO) cannot be efficiently obtained in general. We first demonstrate that two popular approximation assumptions (additive and multiplicative gap errors), are not valid for our problem, in that no cheap gap-approximate LMO oracle exists in general. Instead, a new 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 δ-approximate DMO converges as 𝒪(L / δ t + (1-δ)(δ^-1 + δ^-2)) in general, and as 𝒪(L/(δ^2(t+2))) over a δ-relaxation of the constraint set. Additionally, when the objective is μ-strongly convex and the solution is unique, a variant of FW converges to 𝒪(L^2log(t)/(μδ^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.
READ FULL TEXT