# Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence

arXiv: https://arxiv.org/abs/2302.08580 · HTML: https://mlsanity.com/paper/2302.08580/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 16 Feb 2023.

## Builds on (most cited first, 7 of 7)

- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [Greedy Quasi-Newton Methods with Explicit Superlinear Convergence](https://mlsanity.com/paper/2002.00657/) (2020)
- [Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods](https://mlsanity.com/paper/2003.13607/) (2020)
- [New Results on Superlinear Convergence of Classical Quasi-Newton Methods](https://mlsanity.com/paper/2004.14866/) (2020)
- [Rates of superlinear convergence for classical quasi-Newton methods](https://mlsanity.com/paper/2003.09174/) (2020)
- [Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood](https://mlsanity.com/paper/2202.10538/) (2022)

## Built on by (most cited first, 11 of 11)

- [Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2602.08232/) (2026)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/2502.11229/) (2025)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024)
- [Incremental Gauss--Newton Methods with Superlinear Convergence Rates](https://mlsanity.com/paper/2407.03195/) (2024)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)

## Abstract (arXiv)

Quasi-Newton algorithms are among the most popular iterative methods for solving unconstrained minimization problems, largely due to their favorable superlinear convergence property. However, existing results for these algorithms are limited as they provide either (i) a global convergence guarantee with an asymptotic superlinear convergence rate, or (ii) a local non-asymptotic superlinear rate for the case that the initial point and the initial Hessian approximation are chosen properly. In particular, no current analysis for quasi-Newton methods guarantees global convergence with an explicit superlinear convergence rate. In this paper, we close this gap and present the first globally convergent quasi-Newton method with an explicit non-asymptotic superlinear convergence rate. Unlike classical quasi-Newton methods, we build our algorithm upon the hybrid proximal extragradient method and propose a novel online learning framework for updating the Hessian approximation matrices. Specifically, guided by the convergence analysis, we formulate the Hessian approximation update as an online convex optimization problem in the space of matrices, and we relate the bounded regret of the online problem to the superlinear convergence of our method.