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

arXiv: https://arxiv.org/abs/1504.05002 · HTML: https://mlsanity.com/paper/1504.05002/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2015.

## Built on by (most cited first, 12 of 12)

- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)
- [A Policy Efficient Reduction Approach to Convex Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/2108.12916/) (2021)
- [Frank Wolfe Meets Metric Entropy](https://mlsanity.com/paper/2205.08634/) (2022)
- [Iterative regularization in classification via hinge loss diagonal descent](https://mlsanity.com/paper/2212.12675/) (2022)
- [Learning Massive-scale Partial Correlation Networks in Clinical Multi-omics Studies with HP-ACCORD](https://mlsanity.com/paper/2412.11554/) (2024)
- [Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes](https://mlsanity.com/paper/2505.11259/) (2025)
- [Non-Stationary Online Structured Prediction with Surrogate Losses](https://mlsanity.com/paper/2510.07086/) (2025)

## Abstract (arXiv)

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.