Convergence rates of regularized quasi-Newton methods without strong convexity
Shida Wang, Jalal Fadili, Peter Ochs · 2025
Read Convergence rates of regularized quasi-Newton methods without strong convexity by Shida Wang, Jalal Fadili, Peter Ochs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00521.txt.
Introduction
Shida Wang, Jalal Fadili, and Peter Ochs prove speed results for a class of optimization methods. Their 2025 paper studies a cubic regularized proximal quasi-Newton method. It solves problems built from a smooth part plus a rough part. Past speed proofs often leaned on a strong curve condition that many problems lack.
They work instead with a broader property named after Kurdyka and Łojasiewicz. After a fixed number of steps, their method shows explicit super-linear speed. A special case tied to a classic inequality makes that speed global. The results are new even for smooth non-convex problems. They need no line search, trust region, or strong assumptions on the method's inner matrices. A gradient variant gets like results for convex cases.
Catalog record
| CREATOR | Shida Wang, Jalal Fadili, Peter Ochs |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00521
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence rates of regularized quasi-Newton methods without strong convexity Shida Wang, Jalal Fadili, Peter Ochs Abstract In this paper, we study convergence rates of the cubic regularized proximal quasi-Newton method (Cubic SR1) 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 k_{0} , Cubic SR1 exhibits non-asymptotic explicit super-linear convergence rates for any k ≥ k 0 k\geq k_{0} . In particular, when φ ( t ) = c t 1 / 2 \varphi(t)=ct^{1/2} , Cubic SR1 PQN has a convergence rate of order ( C ( k − k 0 ) 1 / 2 ) ( k − k 0 ) / 2 \left(\frac{C}{(k-k_{0})^{1/2}}\right)^{(k-k_{0})/2} , where k k is the number of iterations and C > 0 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 (Gradient SR1) 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 Gradient SR1for solving convex problems with the help of the Łojasiewicz inequality instead of strong convexity. 1 Introduction Quasi-Newton methods have been studied extensively over decades due to their fast convergence. They have been developed to approximate the Hessian (second derivative) of the objective [ 18 ] , using solely first-order information. Based on this idea, numerous variants have been developed, including BFGS [ 11 ] , SR1 [ 16 , 10 ] , DFP [ 16 , 22 ] . A striking advantage of quasi-Newton-type methods [ 11 , 12 , 19 , 21 , 24 , 13 ] for minimizing some strongly convex smooth function f is the local super-linear convergence. However, the convergence rates obtained by these works above are asymptotic, i.e., \lim_{k\to\infty}\frac{\|x_{k+1}-x^{*}\|}{\|x_{k}-x^{*}\|}\to 0 or \lim_{k\to\infty}\frac{\|\nabla f(x_{k+1})\|}{\|\nabla f(x_{k})\|}\to 0 . Since an asymptotic statement is about the limit as k\to\infty , we are also interested in a non-asymptotical analysis where the convergence rate is valid for any k or at least for all k\geq k_{0} where k_{0} is some constant. Only a non-asymptotic statement can characterize an explicit upper bound on the error of quasi Newton methods. Recently, on strongly convex problems, many outstanding results [ 45 , 46 , 28 , 52 ] provide non-asymptotic explicit local super-linear convergence rates for classical quasi-Newton schemes including BFGS and SR1. However, the guarantee is their local convergence, meaning that the initial point must be close to the minimum point. To study global rates, [ 44 , 27 ] adopt BFGS with line-search strategies, while [ 51 ] studies SR1 method on a composite problem with solely regularization strategy. In this paper, we would like to generalize the results from [ 51 ] to problems without strong convexity. A possible way is to assume the objective function f has the Kurdyka-Łojasiewicz (KŁ) property [ 6 , 8 , 35 , 42 ] , which can be regarded as a generalization of strong convexity. Based on the KŁ inequality with a special concave function \varphi(t)=ct^{1-\theta} where \theta\in(0,1) , the convergence rates of first-order methods on convex or non-convex problems have been developed [ 53 , 35 , 23 ] . If \varphi is unique for any point x\in\mathrm{dom}\,F , it leads to the gradient-dominated functions studied by Polyak and Nesterov in [ 39 , 31 ] . In this paper, we give non-asymptotic convergence rates by studying cubic- and gradient-regularized quasi-Newton methods from [ 51 ] with the help of the KŁ property. This paper consists of two parts. In the first part, we provide convergence analysis of cubic regularized PQN on non-convex non-smooth problems under general \varphi or \varphi=ct^{1-\theta} of different \theta\in(0,1) . In particular, when \theta\in(0,\frac{1}{2}) , we show an explicit super-linear convergence rate O(\frac{C}{N^{1/2}})^{N/2} for some C after a certain number of iterations. In the second part, we specialize on the convex case and use more tractable gradient regularization, rather than cubic regularization, to achieve similar results. The main contribution of this paper is to reveal that KŁ inequality is the key property for the fast convergence of quasi-Newton methods. It is also worth emphasizing that we do not assume the Dennis-Moré condition in this paper which is, in fact, the characteristic of super-linear convergence and widely assumed by many papers [ 15 , 48 , 13 ] . Furthermore, we have no assumptions on our quasi-Newton metrics. We also do not adopt any line search or trust region strategies to achieve global convergence. 2 Related Works Regularized Newton method. Despite global convergence on convex problem can be obtained while maintaining the local fast convergence [ 17 , 40 ] by using line search or trust region stategies, there are other regularization strategies to achieve the same goal by adding a positive definite matrix to the Hessian (like in the Levenberg–Marquardt method [ 34 , 37 ] ). Thanks to having a positive definite metric, Newton’s methods are stabilized at the cost of loosing the local fast convergence rates. The pioneering work by Nesterov and Polyak [ 39 ] has introduced cubic regularization as another globalization strategy that avoids line search and at the same time shows the standard fast local convergence rates of the pure Newton’s method. This cubic regularization works even on non-convex problems such as star-convex function or gradient dominated functions, namely, one satisfying the condition that for any x\in\mathrm{dom}\,f , f(x)-{\color[rgb]{0,0,0}f^{*}}\leq C\|\nabla f(x)\|^{p} with some C>0 , p>0 . In order to remedy the computational cost of cubic regularization, in [ 38 , 20 ] a gradient regularization strategy was introduced for solving convex problems. It also allows for global convergence with a super-linear rate of convergence for strongly convex problems. Motivated by their works, [ 51 ] proposed two regularized SR1 proximal quasi Newton methods with non-asymptotic super-linear convergence rate on strongly convex problems These works have fundamentally inspired the present paper. We will further study the non-asymptotic convergence rates of two algorithms from [ 51 ] without assuming strong convexity. Quasi-Newton methods. Rodomanov and Nesterov [ 45 ] obtained the first local explicit super-linear convergence rate for greedy quasi-Newton methods. Later, Haishan Ye et al [ 52 ] obtained the first local explicit super-linear convergence rate for the SR1 quasi-Newton method, introducing several fruitful techniques about SR1 scheme. Building on this, [ 51 ] studies the global rates. Both works significantly inspired our development in this paper. However, all results above require the strong convexity of the objective function. Therefore, it is worth looking for non-asymptotic super-linear convergence rates of quasi Newton methods on convex or even non-convex problems. In our paper, we study