Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems

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

This paper, recently published by researchers from Saarland University and ENSICAEN, tackles one of the "Holy Grails" of optimization: achieving the lightning-fast convergence of Newton’s method with the low computational cost of first-order methods, all while ensuring the algorithm works regardless of where you start.

TL;DR

The authors introduce two new regularized proximal quasi-Newton methods (Cubic and Gradient SR1 PQN) that achieve global, non-asymptotic, super-linear convergence for non-smooth composite problems. Unlike traditional quasi-Newton methods, these don't require expensive line searches or "lucky" initializations to be fast.

What Problem Does This Paper Address?

In the world of optimization, we usually face a trade-off. First-order methods (like Gradient Descent) are cheap per iteration but slow to converge. Newton’s method is incredibly fast (super-linear or quadratic convergence) but requires calculating the Hessian (second derivatives), which costs $O(n^3)$—a dealbreaker for large-scale machine learning.

Quasi-Newton methods (like BFGS or SR1) try to bridge this gap by approximating the Hessian using only gradients, bringing the cost down to $O(n^2)$. However, they have two major "catches":

  1. Locality: They usually only achieve super-linear speed when you are already very close to the solution.
  2. Asymptotics: Most proofs only guarantee they eventually become fast, without telling you exactly how many steps it will take.

Furthermore, many real-world problems are "non-smooth" (e.g., using $L_1$ regularization for sparsity), which adds another layer of complexity that standard quasi-Newton methods struggle to handle globally without complex "globalization" strategies like line searches.

Methods

The authors propose two algorithms based on the Symmetric Rank-1 (SR1) update rule:

  1. Cubic SR1 PQN: This method adds a cubic regularization term to the subproblem. Inspired by the work of Nesterov and Polyak, this term penalizes large steps, ensuring global stability without needing a line search.
  2. Grad SR1 PQN: This version uses gradient-based regularization. It’s computationally lighter than the cubic version because the subproblem is easier to solve, often allowing for the use of the Sherman-Morrison-Woodbury formula to speed up matrix inversions.

The Secret Sauce: The authors utilize a novel, simplified Lyapunov-type potential function ($V(G) = \text{tr } G$) to analyze convergence. While previous proofs relied on complex log-determinant functions, this trace-based approach allows them to prove global rates and implement a simple "restarting" strategy to keep the Hessian approximation bounded.

Datasets

The algorithms were evaluated on two standard machine learning benchmarks:

  • Regularized Log-Sum-Exp: A synthetic problem designed to test high-dimensional convex optimization ($m=500, n=200$).
  • Logistic Regression: Performed on the "Mushroom" dataset from the UCI Machine Learning Repository ($m=8124, n=117$). This represents a classic real-world classification task with regularization.

Key Insights and Ideas

  • Globalization without Line Search: By integrating cubic or gradient regularization directly into the proximal quasi-Newton framework, the authors eliminate the need for line searches or trust-region strategies, which are often computationally expensive and finicky to tune.
  • Non-Asymptotic is the New Standard: This paper provides the first explicit formulas for super-linear rates that apply from the very first iteration. For the Cubic version, the rate is roughly $(C/N^{1/2})^{N/2}$.
  • The Power of Simplicity: The move to a trace-based potential function isn't just a mathematical convenience; it enables a practical "restarting" criterion. If the approximate Hessian becomes too "large" (unstable), the algorithm simply resets it, maintaining global convergence guarantees.

Key Results

  • Theoretical Superiority: The paper proves that both methods achieve super-linear convergence rates globally. The Cubic SR1 PQN achieves a rate of $O((C/N^{1/2})^{N/2})$, while the Gradient version is slightly slower at $O((C/N^{1/4})^{N/2})$.
  • Wall-Clock Efficiency: In experiments, Grad SR1 PQN emerged as the "Goldilocks" method. While "Cubic Newton" takes fewer iterations, its iterations are so slow ($O(n^3)$) that Grad SR1 PQN ($O(n^2)$) finishes the task much faster in actual time.
  • Beating First-Order Methods: Both proposed methods significantly outperformed standard Gradient Descent and Heavy Ball methods in terms of the number of iterations required to reach high precision.

Limitations and Future Work

  • Subproblem Complexity: While the Grad SR1 PQN is efficient, the Cubic version still requires solving a non-trivial subproblem (often via bisection), which can be a bottleneck in very high dimensions.
  • Conservative Constants: The authors note that their theoretical constants ($C$) are likely quite conservative; the algorithms often perform much better in practice than the "worst-case" theory predicts.
  • Non-Smooth Subproblems: The authors acknowledge that efficiently solving the proximal subproblem for any non-smooth term remains a challenge. They suggest that future work could integrate "proximal calculus" to make these methods even more general.

Summary updated

Abstract

In this paper, we propose two regularized proximal quasi-Newton methods with symmetric rank-1 update of the metric (SR1 quasi-Newton) to solve non-smooth convex additive composite problems. Both algorithms avoid using line search or other trust region strategies. For each of them, we prove a super-linear convergence rate that is independent of the initialization of the algorithm. The cubic regularized method achieves a rate of order $\left(\frac{C}{N^{1/2}}\right)^{N/2}$, where $N$ is the number of iterations and $C$ is some constant, and the other gradient regularized method shows a rate of the order $\left(\frac{C}{N^{1/4}}\right)^{N/2}$. To the best of our knowledge, these are the first global non-asymptotic super-linear convergence rates for regularized quasi-Newton methods and regularized proximal quasi-Newton methods. The theoretical properties are also demonstrated in two applications from machine learning.
BibTeX
@misc{wang2024global,
  author = {Shida Wang and Jalal Fadili and Peter Ochs},
  title = {{Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems}},
  year = {2024},
  eprint = {2410.11676},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.11676},
}
Figure