Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions

Abstract

We consider the problem of minimizing a function, which is the sum of a linear function and a composition of a strongly convex function with a linear transformation, over a compact polyhedral set. Jaggi and Lacoste-Julien [14] showed that the conditional gradient method with away steps employed on the aforementioned problem without the additional linear term has linear rate of convergence, depending on the so-called pyramidal width of the feasible set. We revisit this result and provide a variant of the algorithm and an analysis that is based on simple duality arguments, as well as corresponding error bounds. This new analysis (a) enables the incorporation of the additional linear term, (b) does not require a linear-oracle that outputs an extreme point of the linear mapping of the feasible set and (c) depends on a new constant, termed "the vertex-facet distance constant", which is explicitly expressed in terms of the problem's parameters and the geometry of the feasible set. This constant replaces the pyramidal width, which is difficult to evaluate.

References in corpus (1)

• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization

Cited by in corpus (5)

• Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• Linear Convergence of the Proximal Incremental Aggregated Gradient Method under Quadratic Growth Condition
• On the von Neumann and Frank-Wolfe Algorithms with Away Steps
• A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming