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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.40608
curl -X POST /api/v1/records/arxiv/2610.40608/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.40608/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'