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:
- Strong Convexity: The objective function must have a minimum "bowl-like" curvature everywhere. This excludes many modern problems in machine learning and signal processing.
- 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:
- Synthetic Quadratic Function: A convex quadratic problem with a "non-trivial kernel," meaning it is convex but specifically not strongly convex.
- Mushroom Dataset (UCI Machine Learning Repository): Used for a logistic regression problem with convex regularization ($m=8124$ samples, $n=117$ features).
- 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