Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910025118646272 |
|---|---|
| author | Takahashi, Shota Pokutta, Sebastian Takeda, Akiko |
| author_facet | Takahashi, Shota Pokutta, Sebastian Takeda, Akiko |
| contents | We propose Frank--Wolfe (FW) algorithms with an adaptive Bregman step-size strategy for smooth adaptable (also called: relatively smooth) (weakly-) convex functions. This means that the gradient of the objective function is not necessarily Lipschitz continuous, and we only require the smooth adaptable property. Compared with existing FW algorithms, our assumptions are less restrictive. We establish convergence guarantees in various settings, including convergence rates ranging from sublinear to linear, depending on the assumptions for convex and nonconvex objective functions. Assuming that the objective function is weakly convex and satisfies the local quadratic growth condition, we provide both local sublinear and local linear convergence with respect to the primal gap. We also propose a variant of the away-step FW algorithm using Bregman distances over polytopes. We establish faster global convergence (up to a linear rate) for convex optimization under the Hölder error bound condition and local linear convergence for nonconvex optimization under the local quadratic growth condition. Numerical experiments demonstrate that our proposed FW algorithms outperform existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04330 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions Takahashi, Shota Pokutta, Sebastian Takeda, Akiko Optimization and Control 65K05, 90C06, 90C25, 90C26, 90C30 We propose Frank--Wolfe (FW) algorithms with an adaptive Bregman step-size strategy for smooth adaptable (also called: relatively smooth) (weakly-) convex functions. This means that the gradient of the objective function is not necessarily Lipschitz continuous, and we only require the smooth adaptable property. Compared with existing FW algorithms, our assumptions are less restrictive. We establish convergence guarantees in various settings, including convergence rates ranging from sublinear to linear, depending on the assumptions for convex and nonconvex objective functions. Assuming that the objective function is weakly convex and satisfies the local quadratic growth condition, we provide both local sublinear and local linear convergence with respect to the primal gap. We also propose a variant of the away-step FW algorithm using Bregman distances over polytopes. We establish faster global convergence (up to a linear rate) for convex optimization under the Hölder error bound condition and local linear convergence for nonconvex optimization under the local quadratic growth condition. Numerical experiments demonstrate that our proposed FW algorithms outperform existing methods. |
| title | Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions |
| topic | Optimization and Control 65K05, 90C06, 90C25, 90C26, 90C30 |
| url | https://arxiv.org/abs/2504.04330 |