Flexible block-iterative analysis for the Frank-Wolfe algorithm
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909963468668928 |
|---|---|
| author | Braun, Gábor Halbey, Jannis Pokutta, Sebastian Woodstock, Zev |
| author_facet | Braun, Gábor Halbey, Jannis Pokutta, Sebastian Woodstock, Zev |
| contents | We prove that the block-coordinate Frank-Wolfe (BCFW) algorithm converges with state-of-the-art rates in both convex and nonconvex settings under a very mild "block-iterative" assumption. This appears to be the first result on BCFW addressing the setting of nonconvex objective functions with Lipschitz-continuous gradients and no additional assumptions. This analysis newly allows for (I) progress without activating the most-expensive linear minimization oracle(s), LMO(s), at every iteration, (II) parallelized updates that do not require all LMOs, and therefore (III) deterministic parallel update strategies that take into account the numerical cost of the problem's LMOs. Our results apply for short-step BCFW as well as an adaptive method for convex functions. New relationships between updated coordinates and primal progress are proven, and a favorable speedup is demonstrated using FrankWolfe.jl. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06931 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Flexible block-iterative analysis for the Frank-Wolfe algorithm Braun, Gábor Halbey, Jannis Pokutta, Sebastian Woodstock, Zev Optimization and Control 49M27, 49M37, 65K05, 90C26, 90C30 We prove that the block-coordinate Frank-Wolfe (BCFW) algorithm converges with state-of-the-art rates in both convex and nonconvex settings under a very mild "block-iterative" assumption. This appears to be the first result on BCFW addressing the setting of nonconvex objective functions with Lipschitz-continuous gradients and no additional assumptions. This analysis newly allows for (I) progress without activating the most-expensive linear minimization oracle(s), LMO(s), at every iteration, (II) parallelized updates that do not require all LMOs, and therefore (III) deterministic parallel update strategies that take into account the numerical cost of the problem's LMOs. Our results apply for short-step BCFW as well as an adaptive method for convex functions. New relationships between updated coordinates and primal progress are proven, and a favorable speedup is demonstrated using FrankWolfe.jl. |
| title | Flexible block-iterative analysis for the Frank-Wolfe algorithm |
| topic | Optimization and Control 49M27, 49M37, 65K05, 90C26, 90C30 |
| url | https://arxiv.org/abs/2409.06931 |