Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse

We study how curvature estimated from gradient differences can accelerate proximal-extragradient quasi-Newton methods. Existing global guarantees for QNPE, A-QNPE, and OL-OQN learn Hessian approximations online and incur dimension dependence through regret bounds. We introduce certified curvature reuse: one finite-difference probe per iteration refreshes a group of Hessian columns, while a path-length certificate controls the error of stale columns and determines the step. Each iteration uses at most three gradient queries and one regularized linear solve (or trust-region step), without a gradient line search or an inner oracle-querying loop. In the convex and strongly convex settings, bisection on stored scalar quantities selects a near-maximal certified stepsize; in the nonconvex setting, a uniform certificate gives an explicit learning rate. With other problem parameters fixed, the convex method attains O(min⁻²,dk⁻³\) in a single run, with no logarithmic factor or additive dimension term, matching accelerated gradient descent (AGD) for k d and improving on A-QNPE thereafter. In the strongly convex setting with condition number $κ$, a single run matches AGD's (1-Θ(κ-1/2))ᵏ rate for k dlogκ and achieves a superlinear upper envelope, eventually scaling as (1+k²/B²)⁻ᵏ with B= O(dκ), improving on QNPE. In the nonconvex setting, the method finds an ε-stationary point in O(min1/3ε-3/2,ε-7/4\) gradient queries, improving on OL-OQN's O(d1/4ε-13/8). For sparse Hessians, d is replaced by an effective dimension χ≤ d. We also compare our bounds with lazy-Hessian, double-loop, and cutting-plane methods.