Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2412.19541 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917879964762112 |
|---|---|
| author | An, Qi Wang, Jiao Niu, Zequn Zhang, Nana |
| author_facet | An, Qi Wang, Jiao Niu, Zequn Zhang, Nana |
| contents | In this study, we focus on computing the projection onto the $\ell_p$ quasi-norm ball, which is challenging due to the non-convex and non-Lipschitz nature inherent in the $\ell_p$ quasi-norm with $0<p<1$. We propose a novel localized approximation method that yields a Lipschitz continuous concave surrogate function for the $\ell_p$ quasi-norm with improved approximation quality. Building on this approximation, we enhance the state-of-the-art iterative reweighted algorithm proposed by Yang et al. (J Mach Learn Res 23:1-31, 2022) by constructing tighter subproblems. This improved algorithm solves the $\ell_p$ quasinorm ball projection problem through a series of tractable projections onto the weighted $\ell_1$ norm balls. Convergence analyses and numerical studies demonstrate the global convergence and superior computational efficiency of the proposed method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19541 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Computation of the Non-convex Quasi-norm Ball Projection with Iterative Reweighted Approach An, Qi Wang, Jiao Niu, Zequn Zhang, Nana Optimization and Control In this study, we focus on computing the projection onto the $\ell_p$ quasi-norm ball, which is challenging due to the non-convex and non-Lipschitz nature inherent in the $\ell_p$ quasi-norm with $0<p<1$. We propose a novel localized approximation method that yields a Lipschitz continuous concave surrogate function for the $\ell_p$ quasi-norm with improved approximation quality. Building on this approximation, we enhance the state-of-the-art iterative reweighted algorithm proposed by Yang et al. (J Mach Learn Res 23:1-31, 2022) by constructing tighter subproblems. This improved algorithm solves the $\ell_p$ quasinorm ball projection problem through a series of tractable projections onto the weighted $\ell_1$ norm balls. Convergence analyses and numerical studies demonstrate the global convergence and superior computational efficiency of the proposed method. |
| title | Efficient Computation of the Non-convex Quasi-norm Ball Projection with Iterative Reweighted Approach |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.19541 |