Metraipolis › archive › dc_7434bde97ddb

Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension — arXiv:2610.22208

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.22208
License (as archived)
CC0-1.0
Archived
2026-10-16T10:28:53.976Z
SHA-256 of the archived text
62211f41e147fdb2d0ef17aa5aaa60bf2d0003257581b69ceb6b90b27c936d0f
Stable URL of this page
https://metraipolis.com/documento/dc_7434bde97ddb

How to cite

Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension — arXiv:2610.22208 — arXiv (en), https://arxiv.org/abs/2610.22208 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7434bde97ddb (Metraipolis archive dc_7434bde97ddb, sha256 62211f41e147fdb2d0ef17aa5aaa60bf2d0003257581b69ceb6b90b27c936d0f)
BibTeX
@misc{dc7434bde97ddb,
  title = {Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension — arXiv:2610.22208},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.22208},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7434bde97ddb; sha256 62211f41e147fdb2d0ef17aa5aaa60bf2d0003257581b69ceb6b90b27c936d0f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22208. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We establish matching lower bounds for the tradeoff between gradient and Hessian queries in nonconvex optimization with Lipschitz Hessian. In normalized units, the initial objective gap is at most $T$, the Hessian Lipschitz constant is at most one, and the target gradient norm is one. For sufficiently large $T$, dimension $d \ge C\log(2+T)$, and a prescribed Hessian budget $h \ge 1$ with $h+1 \le aT$, every randomized algorithm requires $\Omega(\min\{Td^{1/3}, T^{3/2}/\sqrt{h+1}\})$ ordinary queries. An ordinary query returns the value and gradient; a Hessian query returns the complete second jet and is charged only to its own budget. Both budgets are worst-case caps. Queries and outputs may be arbitrary real points, and no Hessian-norm bound is imposed. The hard input law consists of fixed, globally $C^3$, coercive functions. The construction combines sequential readouts of a continuous random matrix with localized completion blocks and reliability dimensions that vary across hierarchy levels. Premature disclosures are charged by their expected task cost, while every oracle reply remains the exact jet of the presampled objective. This yields a logarithmic dimension threshold and a depth-independent third-derivative bound. Together with a translation of the NALEN upper bound of Chen, Liu, Luo, and Zhang, the result determines the query tradeoff up to absolute constants throughout the stated range.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.22208 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:49:47.938Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).