Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse
Abstract
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{k−2,dk−3}) 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))k rate for k≲ dlogκ and achieves a superlinear upper envelope, eventually scaling as (1+k2/B2)−k with B=Õ(dκ), improving on QNPE. In the nonconvex setting, the method finds an ε-stationary point in O(min{d1/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.
Related
- The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
- Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
- Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds
- Spectral-NFP: Certified Low-Rank Curvature Majorization for Accelerating WMMSE
- Algorithmic Information Dynamics of Learning: A Certified, Differentiable Complexity Controller for Grokking
BibTeX
@misc{mokhtari2026improved,
title = {{Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse}},
author = {Aryan Mokhtari and Francisco Patitucci},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40608},
eprint = {2610.40608},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40608},
}
RIS
TY - UNPB
TI - Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse
AU - Aryan Mokhtari
AU - Francisco Patitucci
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40608
UR - https://arxiv.org/abs/2610.40608
AB - 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{k^−2,dk^−3}) 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))^k rate for k≲ dlogκ and achieves a superlinear upper envelope, eventually scaling as (1+k^2/B^2)^−k with B=Õ(dκ), improving on QNPE. In the nonconvex setting, the method finds an ε-stationary point in O(min{d^1/3ε^−3/2,ε^−7/4}) gradient queries, improving on OL-OQN's O(d^1/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.
ER -