Convergence rates of regularized quasi-Newton methods without strong convexity
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909742495956992 |
|---|---|
| author | Wang, Shida Fadili, Jalal Ochs, Peter |
| author_facet | Wang, Shida Fadili, Jalal Ochs, Peter |
| contents | In this paper, we study convergence rates of the cubic regularized proximal quasi-Newton method (\csr) for solving non-smooth additive composite problems that satisfy the so-called Kurdyka-Łojasiewicz (KŁ) property with respect to some desingularization function $ϕ$ rather than strong convexity. After a number of iterations $k_0$, Cubic SR1 PQN exhibits non-asymptotic explicit super-linear convergence rates for any $k\geq k_0$. In particular, when $ϕ(t)=ct^{1/2}$, Cubic SR1 PQN has a convergence rate of order $\left(\frac{C}{(k-k_0)^{1/2}}\right)^{(k-k_0)/2}$, where $k$ is the number of iterations and $C>0$ is a constant. For the special case, i.e. functions which satisfy Łojasiewicz inequality, the rate becomes global and non-asymptotic. This work presents, for the first time, non-asymptotic explicit convergence rates of regularized (proximal) SR1 quasi-Newton methods applied to non-convex non-smooth problems with KŁ property. Actually, the rates are novel even in the smooth non-convex case. Notably, we achieve this without employing line search or trust region strategies, without assuming the Dennis-Moré condition, without any assumptions on quasi-Newton metrics and without assuming strong convexity. Furthermore, for convex problems, we focus on a more tractable gradient regularized quasi-Newton method (Grad SR1 PQN) which can achieve results similar to those obtained with cubic regularization. We also demonstrate, for the first time, the non-asymptotic super-linear convergence rate of Grad SR1 PQN for solving convex problems with the help of the Łojasiewicz inequality instead of strong convexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00521 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence rates of regularized quasi-Newton methods without strong convexity Wang, Shida Fadili, Jalal Ochs, Peter Optimization and Control In this paper, we study convergence rates of the cubic regularized proximal quasi-Newton method (\csr) for solving non-smooth additive composite problems that satisfy the so-called Kurdyka-Łojasiewicz (KŁ) property with respect to some desingularization function $ϕ$ rather than strong convexity. After a number of iterations $k_0$, Cubic SR1 PQN exhibits non-asymptotic explicit super-linear convergence rates for any $k\geq k_0$. In particular, when $ϕ(t)=ct^{1/2}$, Cubic SR1 PQN has a convergence rate of order $\left(\frac{C}{(k-k_0)^{1/2}}\right)^{(k-k_0)/2}$, where $k$ is the number of iterations and $C>0$ is a constant. For the special case, i.e. functions which satisfy Łojasiewicz inequality, the rate becomes global and non-asymptotic. This work presents, for the first time, non-asymptotic explicit convergence rates of regularized (proximal) SR1 quasi-Newton methods applied to non-convex non-smooth problems with KŁ property. Actually, the rates are novel even in the smooth non-convex case. Notably, we achieve this without employing line search or trust region strategies, without assuming the Dennis-Moré condition, without any assumptions on quasi-Newton metrics and without assuming strong convexity. Furthermore, for convex problems, we focus on a more tractable gradient regularized quasi-Newton method (Grad SR1 PQN) which can achieve results similar to those obtained with cubic regularization. We also demonstrate, for the first time, the non-asymptotic super-linear convergence rate of Grad SR1 PQN for solving convex problems with the help of the Łojasiewicz inequality instead of strong convexity. |
| title | Convergence rates of regularized quasi-Newton methods without strong convexity |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2506.00521 |