2013 · 891 citations · 41 references
Frank‑Wolfe (conditional gradient) algorithms are widely used for constrained convex optimization, and this work builds on a simple duality‑gap certificate framework. The authors provide stronger, more general primal‑dual convergence results for Frank‑Wolfe‑type algorithms and introduce a new general framework for convex optimization over matrix factorizations with low‑rank updates. Their analysis remains valid with approximate subproblems or inexact gradients, achieves worst‑case optimal sparsity, and applies to matrix‑factorization settings where each Frank‑Wolfe step is a low‑rank update. The framework un.
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.
41