Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension
Abstract
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 ≥ Clog(2+T), and a prescribed Hessian budget h ≥ 1 with h+1 ≤ aT, every randomized algorithm requires Ω(min{Td1/3, T3/2/√(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 C3, 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.
Related
- Logarithmic Hessian estimates for non-uniformly elliptic equations in non-divergence form
- Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata
- Alternative proof of the gradient estimate for complex Hessian equations
- Gradient Estimates for Hessian Equations with Measure Data
- Gradient potential estimates for k-Hessian equations
BibTeX
@misc{wu2026gradienthessian,
title = {{Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension}},
author = {Wendao Wu and Haihan Zhang and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22208},
eprint = {2610.22208},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22208},
}
RIS
TY - UNPB
TI - Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension
AU - Wendao Wu
AU - Haihan Zhang
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.22208
UR - https://arxiv.org/abs/2610.22208
AB - 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 ≥ Clog(2+T), and a prescribed Hessian budget h ≥ 1 with h+1 ≤ aT, every randomized algorithm requires Ω(min{Td^1/3, T^3/2/√(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.
ER -