Id: arxiv/2602.04378 Url: https://arxiv.org/abs/2602.04378 Tags: math.OC Score: 0 Title: Lower Bounds for Frank-Wolfe on Strongly Convex Sets Domain: math.OC Source: arxiv Authors: Jannis Halbey, Daniel Deza, Max Zimmer, Christophe Roux, Bartolomeo Stellato, Sebastian Pokutta Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-04 Page: https://delphi.science/r/arxiv/2602.04378 We present a constructive lower bound of $Ω(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 uniformly faster than $\mathcal{O}(1/\sqrt{\varepsilon})$, i.e., irrespective of the position of the optimizer. To investigate this…