Lower Bounds for Frank-Wolfe on Strongly Convex Sets

We present a constructive lower bound of $\Omega(1/\sqrt{\varepsilon})$ for Frank-Wolfe (FW) when both the objective and the constraint set are smooth and strongly convex, showing that the known uniform $\mathcal{O}(1/\sqrt{\varepsilon})$ guarantees in this regime are tight. It is known that under additional assumptions on the position of the optimizer, FW can converge linearly. However, it remained unclear whether strong convexity of the set can yield rates \emph{uniformly} faster than $\mathcal{O}(1/\sqrt{\varepsilon})$, i.e., irrespective of the position of the optimizer. To investigate this question, we focus on a simple yet representative problem class: minimizing a strongly convex quadratic over the Euclidean unit ball, with the optimizer on the boundary. We analyze the dynamics of FW for this problem in detail and develop a novel computational approach to construct worst-case FW trajectories, which is of independent interest. Guided by these constructions, we develop an analytical proof establishing the lower bound.

Many machine learning and engineering tasks boil down to finding the best option inside limits—for example, improving a model while keeping its parameters within a budget. A popular tool for such problems is the Frank–Wolfe method, which avoids expensive “projection” steps and is widely used in areas like matrix completion, optimal transport, and compressing large language models. When the feasible region is nicely curved (strongly convex), Frank–Wolfe is known to reach a target accuracy faster than in the worst general case. It was unclear whether that guarantee could be improved further for all instances, or whether the best known rate was already as good as it gets. We focused on a simple but representative case—finding the closest point on a ball when the answer lies on the boundary—and built a new numerical procedure to construct long, worst-case solution paths. Guided by those constructions, we proved that Frank–Wolfe cannot uniformly beat the known rate in this setting. This settles a long-standing open question and shows that where the optimum sits on the boundary genuinely matters for speed. The result helps researchers know when faster convergence is realistic and when the standard guarantees are already tight.