# Curvature-Dependent Lower Bounds for Frank-Wolfe

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2026.

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

- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)
- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

The Frank-Wolfe algorithm achieves a convergence rate of O(1/T) for smooth convex optimization over compact convex domains, accelerating to O(1/T2) when both the objective and the feasible set are strongly convex. This acceleration extends beyond strong convexity: Kerdreux et al. (2021a) proved rates of O(T-p/(p-1)) over p-uniformly convex feasible sets, a class that interpolates between strongly convex sets and more general curved domains such as ℓp balls. In this work, we establish a matching Omega(T-p/(p-1)) lower bound for every p≥ 3 under exact line search or short steps, and extend the lower bound to objectives satisfying a H"olderian error bound. The proofs analyze the dynamics of Frank-Wolfe iterates on simple instances and hence are not limited to the high-dimensional setting, unlike information-theoretic lower bounds.