Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908964504993792 |
|---|---|
| author | de Brito, José Lara, Felipe Liu, Di |
| author_facet | de Brito, José Lara, Felipe Liu, Di |
| contents | This work investigates the properties of the proximity operator for quasar-convex functions and establishes the convergence of the proximal point algorithm to a global minimizer with a particular focus on its convergence rate. In particular, we demonstrate: (i) the generated sequence is mi\-ni\-mi\-zing and achieves an $\mathcal{O}(\varepsilon^{-1})$ complexity rate for quasar-convex functions; (ii) under strong quasar-convexity, the sequence converges linearly and attains an $\mathcal{O}(\ln(\varepsilon^{-1}))$ complexity rate. These results extend known convergence rates from the (strongly) convex to the (strongly) quasar-convex setting. To the best of our knowledge, some findings are novel even for the special case of (strongly) star-convex functions. Numerical experiments corroborate our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04375 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case de Brito, José Lara, Felipe Liu, Di Optimization and Control 90C26, 90C30 This work investigates the properties of the proximity operator for quasar-convex functions and establishes the convergence of the proximal point algorithm to a global minimizer with a particular focus on its convergence rate. In particular, we demonstrate: (i) the generated sequence is mi\-ni\-mi\-zing and achieves an $\mathcal{O}(\varepsilon^{-1})$ complexity rate for quasar-convex functions; (ii) under strong quasar-convexity, the sequence converges linearly and attains an $\mathcal{O}(\ln(\varepsilon^{-1}))$ complexity rate. These results extend known convergence rates from the (strongly) convex to the (strongly) quasar-convex setting. To the best of our knowledge, some findings are novel even for the special case of (strongly) star-convex functions. Numerical experiments corroborate our theoretical results. |
| title | Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case |
| topic | Optimization and Control 90C26, 90C30 |
| url | https://arxiv.org/abs/2509.04375 |