ItsOPT: An inexact two-level smoothing framework for nonconvex optimization via high-order Moreau envelope
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916649017278464 |
|---|---|
| author | Kabgani, Alireza Ahookhosh, Masoud |
| author_facet | Kabgani, Alireza Ahookhosh, Masoud |
| contents | This paper introduces ItsOPT, an inexact two-level smoothing optimization framework designed to find first-order critical points of nonsmooth and nonconvex functions. The framework involves two levels of methodologies: at the upper level, a zero-, first-, or second-order method will be tailored to minimize a smooth approximation; at the lower level, the high-order proximal auxiliary problems will be solved inexactly, generating an inexact oracle for the smooth function. As a smoothing technique, we here introduce the high-order Moreau envelope (HOME) and study its fundamental features under standard assumptions. Next, introducing a boosted high-order proximal-point algorithm (Boosted HiPPA) at the upper level using the inexact oracle from the lower level leads to an instance of ItsOPT. Global convergence rates are established under the Kurdyka-Łojasiewicz (KL) property of the cost and envelope functions, along with some reasonable conditions for the accuracy of the proximal terms. surprisingly, for any KL exponent $θ\in (0,1)$ of the original cost, setting the regularization order $p=\frac{1}{1-θ}$ ensures that Boosted HiPPA converges linearly to a proximal fixed point, which is the first algorithm with this property for KL functions. Preliminary numerical experiments on a robust low-rank matrix recovery problem indicate a promising performance of the proposed algorithm, validating our theoretical foundations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19928 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | ItsOPT: An inexact two-level smoothing framework for nonconvex optimization via high-order Moreau envelope Kabgani, Alireza Ahookhosh, Masoud Optimization and Control 90C26, 90C25, 90C06, 65K05, 49J52, 49J53 This paper introduces ItsOPT, an inexact two-level smoothing optimization framework designed to find first-order critical points of nonsmooth and nonconvex functions. The framework involves two levels of methodologies: at the upper level, a zero-, first-, or second-order method will be tailored to minimize a smooth approximation; at the lower level, the high-order proximal auxiliary problems will be solved inexactly, generating an inexact oracle for the smooth function. As a smoothing technique, we here introduce the high-order Moreau envelope (HOME) and study its fundamental features under standard assumptions. Next, introducing a boosted high-order proximal-point algorithm (Boosted HiPPA) at the upper level using the inexact oracle from the lower level leads to an instance of ItsOPT. Global convergence rates are established under the Kurdyka-Łojasiewicz (KL) property of the cost and envelope functions, along with some reasonable conditions for the accuracy of the proximal terms. surprisingly, for any KL exponent $θ\in (0,1)$ of the original cost, setting the regularization order $p=\frac{1}{1-θ}$ ensures that Boosted HiPPA converges linearly to a proximal fixed point, which is the first algorithm with this property for KL functions. Preliminary numerical experiments on a robust low-rank matrix recovery problem indicate a promising performance of the proposed algorithm, validating our theoretical foundations. |
| title | ItsOPT: An inexact two-level smoothing framework for nonconvex optimization via high-order Moreau envelope |
| topic | Optimization and Control 90C26, 90C25, 90C06, 65K05, 49J52, 49J53 |
| url | https://arxiv.org/abs/2410.19928 |