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

Source: arxiv.org/abs/2610.22208

Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2610.22208 Oct 15, 2026math.OCscore 0

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 $Ω(\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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.22208
curl -X POST /api/v1/records/arxiv/2610.22208/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.22208/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'