Convergence rates of regularized quasi-Newton methods without strong convexity

Shida Wang, Jalal Fadili, Peter OchsarXiv 2025 · DOI · arXiv

TL;DR

This paper provides the first non-asymptotic, explicit super-linear convergence rates for regularized proximal Symmetric Rank-1 (SR1) quasi-Newton methods. By replacing the traditional requirement for "strong convexity" with the much broader Kurdyka-Łojasiewicz (KŁ) property, the authors show these methods can solve non-smooth and even non-convex optimization problems with high efficiency.

What Problem Does This Paper Address?

Quasi-Newton methods (like BFGS or SR1) are the workhorses of optimization. They achieve "super-linear" convergence—faster than standard gradient descent—by approximating second-order (Hessian) information using only first-order (gradient) data.

However, the theoretical guarantees for this speed usually come with two major strings attached:

  1. Strong Convexity: The objective function must have a minimum "bowl-like" curvature everywhere. This excludes many modern problems in machine learning and signal processing.
  2. Asymptotic Analysis: Most proofs only describe what happens as the number of iterations $k$ approaches infinity. They don't tell you exactly how much the error drops at iteration 10, 50, or 100.

Furthermore, many existing methods rely on complex "globalization" strategies like line searches or trust regions to ensure they don't diverge. The authors aim to provide a simpler, regularized framework with explicit, non-asymptotic rates that work for a much wider class of functions.

Methods

The authors focus on two primary algorithms:

  • Cubic SR1 PQN (Proximal Quasi-Newton): This method uses cubic regularization—adding a term proportional to the cube of the step size—to stabilize the algorithm. This is particularly useful for non-convex problems.
  • Grad SR1 PQN: A more computationally tractable version for convex problems that uses gradient-based regularization.

The breakthrough in their analysis is the use of the Kurdyka-Łojasiewicz (KŁ) property. Instead of requiring the function to be globally "curved" (strongly convex), the KŁ property describes how the function's geometry relates to its gradient near critical points. Since most functions used in practice (like semi-algebraic functions) satisfy KŁ, this analysis is much more widely applicable.

Crucially, their approach does not require:

  • Line search or trust region strategies.
  • The "Dennis-Moré condition" (a standard but hard-to-verify assumption about Hessian approximation accuracy).
  • Strong convexity.

Datasets

The authors evaluated their algorithms on three distinct types of problems:

  1. Synthetic Quadratic Function: A convex quadratic problem with a "non-trivial kernel," meaning it is convex but specifically not strongly convex.
  2. Mushroom Dataset (UCI Machine Learning Repository): Used for a logistic regression problem with convex regularization ($m=8124$ samples, $n=117$ features).
  3. Image Deblurring: A non-smooth, non-convex optimization problem where a blurry, noisy image is reconstructed using a log-based non-convex regularizer.

Key Insights and Ideas

  • KŁ is the Real Driver: The paper reveals that the KŁ inequality is the fundamental property that enables fast quasi-Newton convergence. Strong convexity is just a special, restrictive case of KŁ.
  • Bypassing Dennis-Moré: Traditionally, you had to prove your Hessian approximation was "getting better" to show super-linear speed. This paper shows that with proper regularization, you can achieve these rates without that assumption.
  • Explicit "Super-Linearity": They don't just say the rate is "fast"; they provide an explicit upper bound. For a common class of KŁ functions, they prove a convergence rate of order: $$\left(\frac{C}{(k-k_0)^{1/2}}\right)^{(k-k_0)/2}$$ This formula gives engineers a concrete way to estimate remaining work at any step $k$.

  • SR1's Redemption: While BFGS is often more popular, the authors show that the Symmetric Rank-1 (SR1) update is exceptionally powerful when paired with cubic or gradient regularization.

Key Results

  • Superior Speed: In the logistic regression experiments, both Cubic and Grad SR1 PQN significantly outperformed first-order methods like Nesterov Accelerated Gradient (NAG) and Heavy Ball (HB) in both the number of iterations and total wall-clock time.
  • High Accuracy in Non-Convex Settings: On the non-convex image deblurring task, Cubic SR1 PQN reached much higher accuracy (lower gradient norms) than first-order methods, which tended to oscillate or get stuck due to the sharp local minima of the non-convex function.
  • Theoretical First: This is the first work to present non-asymptotic super-linear rates for regularized proximal SR1 methods on non-convex, non-smooth objectives.

Limitations and Future Work

  • Sub-problem Cost: While the overall iteration count is lower, each individual step (the "proximal mapping") involves solving a sub-problem with cubic terms. For non-smooth cases, this can be computationally expensive. The authors note that more efficient sub-problem solvers are a key area for future research.
  • Parameter Tuning: The algorithms require estimates of Lipschitz constants ($L$ and $L_H$). While the paper provides a theoretical framework, in practice, these parameters often need to be tuned or estimated heuristically.
  • Generalization to BFGS: The current explicit rates are tailored to SR1; extending this specific KŁ-based non-asymptotic analysis to the BFGS update remains an open challenge.

Summary updated

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 $ϕ$ 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.
BibTeX
@misc{wang2025convergence,
  author = {Shida Wang and Jalal Fadili and Peter Ochs},
  title = {{Convergence rates of regularized quasi-Newton methods without strong convexity}},
  year = {2025},
  eprint = {2506.00521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.00521},
  howpublished = {arXiv},
}
Figure