text: The objectives of this technical report is to provide additional results on the generalized conditional gradient methods introduced by [BLM05]. Indeed , when the objective function is smooth, we provide a novel certificate of optimality and we show that the algorithm has a linear convergence rate. Applications of this algorithm are also discussed.
  @cite_7: We provide stronger and more general primal-dual convergence results for Frank-Wolfe-type algorithms (a.k.a. conditional gradient) for constrained convex optimization, enabled by a simple framework of duality gap certificates. Our analysis also holds if the linear subproblems are only solved approximately (as well as if the gradients are inexact), and is proven to be worst-case optimal in the sparsity of the obtained solutions. On the application side, this allows us to unify a large variety of existing sparse greedy methods, in particular for optimization over convex hulls of an atomic set, even if those sets can only be approximated, including sparse (or structured sparse) vectors or matrices, low-rank matrices, permutation matrices, or max-norm bounded matrices. We present a new general framework for convex optimization over matrix factorizations, where every Frank-Wolfe iteration will consist of a low-rank update, and discuss the broad application areas of this approach.
summary: Here, we propose to take advantage of the composite structure of the objective function and of an efficient solver of that partially linearized problem. Note that a result similar to Lemma , denoted as the surrogate duality gap in @cite_7 , exists for the conditional gradient: @math Using the convexity of @math one can see that @math This means that the bound expressed in Lemma is at least as good that the one provided by the classical CG. In addition when @math is strictly convex, our bond is strictly better which suggests that our approach provides a better control of the convergence along the iterations.