Curvature-Dependent Lower Bounds for Frank-Wolfe
The Frank-Wolfe algorithm achieves a convergence rate of $\mathcal{O}(1/T)$ for smooth convex optimization over compact convex domains, accelerating to $\mathcal{O}(1/T^2)$ when both the objective and the feasible set are strongly convex. This acceleration extends beyond strong convexity: Kerdreux et al. (2021a) proved rates of $\mathcal{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 $\ell_p$ balls. In this work, we establish a matching $Ω(T^{-p/(p-1)})$ lower bound for every $p\ge 3$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.10595
curl -X POST /api/v1/records/arxiv/2605.10595/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.10595/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'