Lower Bounds for Frank-Wolfe on Strongly Convex Sets

Jannis Halbey, Daniel Deza, Max Zimmer +3

We present a constructive lower bound of $\hat{I}\text{c◯}(1/\sqrt{\epsilon })$ for Frank-Wolfe (FW) when both the objective and the constraint set are smooth and strongly convex, showing that…