# Restarting Frank-Wolfe: Faster Rates Under H"olderian Error Bounds

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2018.

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

- [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)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Convex mixed-integer optimization with Frank-Wolfe methods](https://mlsanity.com/paper/2208.11010/) (2022)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

Conditional Gradient algorithms (aka Frank-Wolfe algorithms) form a classical set of methods for constrained smooth convex minimization due to their simplicity, the absence of projection steps, and competitive numerical performance. While the vanilla Frank-Wolfe algorithm only ensures a worst-case rate of O(1/ε), various recent results have shown that for strongly convex functions on polytopes, the method can be slightly modified to achieve linear convergence. However, this still leaves a huge gap between sublinear O(1/ε) convergence and linear O(log 1/ε) convergence to reach an ε-approximate solution. Here, we present a new variant of Conditional Gradient algorithms, that can dynamically adapt to the function's geometric properties using restarts and smoothly interpolates between the sublinear and linear regimes. These interpolated convergence rates are obtained when the optimization problem satisfies a new type of error bounds, which we call textitstrong Wolfe primal bounds. They combine geometric information on the constraint set with H"olderian Error Bounds on the objective function.