{
  "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\\lesssim 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\\lesssim d\\logκ$ and achieves a superlinear upper envelope, eventually scaling as $(1+k^2/B^2)^{-k}$ with $B=\\tilde O(dκ)$, improving on QNPE. In the nonconvex setting, the method finds an $\\varepsilon$-stationary point in $O(\\min\\{d^{1/3}\\varepsilon^{-3/2},\\varepsilon^{-7/4}\\})$ gradient queries, improving on OL-OQN's $O(d^{1/4}\\varepsilon^{-13/8})$. For sparse Hessians, $d$ is replaced by an effective dimension $χ\\le d$. We also compare our bounds with lazy-Hessian, double-loop, and cutting-plane methods.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.40608",
  "author_total": 2,
  "authors": [
    {
      "name": "Aryan Mokhtari"
    },
    {
      "name": "Francisco Patitucci"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6cg2thfnam9jh.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.40608",
  "fulltext_url": null,
  "id": "6cg2thfnam9jh",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.40608",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.OC"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2610.40608",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-29",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6cg2thfnam9jh.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:36:35Z",
      "native_id": "2610.40608",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.40608"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse",
  "title_text": "Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse",
  "type": "preprint",
  "updated_at": "2026-11-01T12:20:53Z",
  "url": "https://research.draconitic.com/paper/6cg2thfnam9jh",
  "venue": "arXiv",
  "versions": []
}