Frank-Wolfe algorithm for star-convex functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911072762462208 |
|---|---|
| author | Millan, R. Diaz Ferreira, Orizon Pereira Ugon, Julien |
| author_facet | Millan, R. Diaz Ferreira, Orizon Pereira Ugon, Julien |
| contents | 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 \emph{star-convex functions}, which retain essential geometric properties despite the lack of convexity. We establish iteration-complexity bounds of $\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17272 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Frank-Wolfe algorithm for star-convex functions Millan, R. Diaz Ferreira, Orizon Pereira Ugon, Julien Optimization and Control 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 \emph{star-convex functions}, which retain essential geometric properties despite the lack of convexity. We establish iteration-complexity bounds of $\mathcal{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. |
| title | Frank-Wolfe algorithm for star-convex functions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.17272 |