Curvature-Dependent Lower Bounds for Frank-Wolfe

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.