An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912009170190336 |
|---|---|
| author | Olikier, Guillaume Absil, P. -A. |
| author_facet | Olikier, Guillaume Absil, P. -A. |
| contents | We consider the problem of minimizing a differentiable function with locally Lipschitz continuous gradient over the real determinantal variety, and present a first-order algorithm designed to find stationary points of that problem. This algorithm applies steps of a retraction-free descent method proposed by Schneider and Uschmajew (2015), while taking the numerical rank into account to attempt rank reductions. We prove that this algorithm produces a sequence of iterates the accumulation points of which are stationary, and therefore does not follow the so-called apocalypses described by Levin, Kileel, and Boumal (2022). Moreover, the rank reduction mechanism of this algorithm requires at most one rank reduction attempt per iteration, in contrast with the one of the $\mathrm{P}^2\mathrm{GDR}$ algorithm introduced by Olikier, Gallivan, and Absil (2022) which can require a number of rank reduction attempts equal to the rank of the iterate in the worst-case scenario. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_12051 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration Olikier, Guillaume Absil, P. -A. Optimization and Control Numerical Analysis 14M12, 65K10, 90C26, 90C30, 40A05 We consider the problem of minimizing a differentiable function with locally Lipschitz continuous gradient over the real determinantal variety, and present a first-order algorithm designed to find stationary points of that problem. This algorithm applies steps of a retraction-free descent method proposed by Schneider and Uschmajew (2015), while taking the numerical rank into account to attempt rank reductions. We prove that this algorithm produces a sequence of iterates the accumulation points of which are stationary, and therefore does not follow the so-called apocalypses described by Levin, Kileel, and Boumal (2022). Moreover, the rank reduction mechanism of this algorithm requires at most one rank reduction attempt per iteration, in contrast with the one of the $\mathrm{P}^2\mathrm{GDR}$ algorithm introduced by Olikier, Gallivan, and Absil (2022) which can require a number of rank reduction attempts equal to the rank of the iterate in the worst-case scenario. |
| title | An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration |
| topic | Optimization and Control Numerical Analysis 14M12, 65K10, 90C26, 90C30, 40A05 |
| url | https://arxiv.org/abs/2208.12051 |