Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914755577380864 |
|---|---|
| author | Latafat, Puya Themelis, Andreas Ahookhosh, Masoud Patrinos, Panagiotis |
| author_facet | Latafat, Puya Themelis, Andreas Ahookhosh, Masoud Patrinos, Panagiotis |
| contents | We introduce two algorithms for nonconvex regularized finite sum minimization, where typical Lipschitz differentiability assumptions are relaxed to the notion of relative smoothness. The first one is a Bregman extension of Finito/MISO, studied for fully nonconvex problems when the sampling is randomized, or under convexity of the nonsmooth term when it is essentially cyclic. The second algorithm is a low-memory variant, in the spirit of SVRG and SARAH, that also allows for fully nonconvex formulations. Our analysis is made remarkably simple by employing a Bregman Moreau envelope as Lyapunov function. In the randomized case, linear convergence is established when the cost function is strongly convex, yet with no convexity requirements on the individual functions in the sum. For the essentially cyclic and low-memory variants, global and linear convergence results are established when the cost function satisfies the Kurdyka-Łojasiewicz property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_10312 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity Latafat, Puya Themelis, Andreas Ahookhosh, Masoud Patrinos, Panagiotis Optimization and Control 90C06, 90C25, 90C26, 49J52, 49J53 We introduce two algorithms for nonconvex regularized finite sum minimization, where typical Lipschitz differentiability assumptions are relaxed to the notion of relative smoothness. The first one is a Bregman extension of Finito/MISO, studied for fully nonconvex problems when the sampling is randomized, or under convexity of the nonsmooth term when it is essentially cyclic. The second algorithm is a low-memory variant, in the spirit of SVRG and SARAH, that also allows for fully nonconvex formulations. Our analysis is made remarkably simple by employing a Bregman Moreau envelope as Lyapunov function. In the randomized case, linear convergence is established when the cost function is strongly convex, yet with no convexity requirements on the individual functions in the sum. For the essentially cyclic and low-memory variants, global and linear convergence results are established when the cost function satisfies the Kurdyka-Łojasiewicz property. |
| title | Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity |
| topic | Optimization and Control 90C06, 90C25, 90C26, 49J52, 49J53 |
| url | https://arxiv.org/abs/2102.10312 |