# Frank-Wolfe algorithm for star-convex functions

arXiv: https://arxiv.org/abs/2507.17272 · HTML: https://mlsanity.com/paper/2507.17272/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2025.

## Built on by (most cited first, 3 of 3)

- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2605.25255/) (2026)

## Abstract (arXiv)

We study the Frank-Wolfe algorithm for minimizing a differentiable function with Lipschitz continuous gradient over a compact convex set. To extend classical complexity bounds to certain non-convex functions, we focus on the class of star-convex functions, which retain essential geometric properties despite the lack of convexity. We establish iteration-complexity bounds of O(1/k) for both the objective values and the duality gap under star-convexity, using diminishing, Armijo-type, and Lipschitz-based stepsize rules. Notably, the diminishing and Armijo strategies do not require prior knowledge of Lipschitz or curvature constants. These results demonstrate that the Frank-Wolfe method preserves optimal complexity guarantees beyond the convex setting.