{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-04","reactions":{}}