348. Linear Convergence of the Proximal Point Algorithm Beyond Convexity
Invited abstract in session WC-9: Generalized convexity and monotonicity 4, stream Generalized convexity and monotonicity.
Wednesday, 14:00-16:00Room: B100/8013
Authors (first author is the speaker)
| 1. | Felipe Lara
|
| Universidad de Tarapacá |
Abstract
We study the fundamental properties of proximal operators for nonsmooth (strongly) quasar-convex functions [1], and we apply them to the proximal point algorithm (PPA). Our analysis focuses on minimizing strongly quasar-convex functions, where the solution is unique. We establish that the sequence generated by PPA is a minimizing sequence and converges linearly under strong quasar-convexity. Additionally, we provide a complexity analysis, proving that PPA achieves an \(\mathcal{O}(\ln(1/\varepsilon))\) convergence rate for both the iterates and the function values. Finally, and if the time allow us, numerical examples will be also presented.
References:
1-. O. Hinder, A. Sidford, N. Sohoni, Near-optimal methods for minimizing star-convex functions and beyond. Proc. 33th Conf. on Lear. Theory, 125, 1894--1938, (2020).
2-. Y.E. Nesterov, B.T. Polyak, Cubic regularization of Newton method and its global performance, Math. Programm., 108, 177--205, (2006).
Keywords
- Global optimization
- First-order optimization
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers