Convergence rates of regularized quasi-Newton methods without strong convexity

Abstract

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 $\varphi$ 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\ge k_0$. In particular, when $\varphi (t)=c{t}^{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.

arXiv admin note: text overlap with arXiv:2410.11676