# Balancing Gradient and Hessian Queries in Non-Convex Optimization

arXiv: https://arxiv.org/abs/2510.20786 · HTML: https://mlsanity.com/paper/2510.20786/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2025.

## Built on by (most cited first, 3 of 3)

- [Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization](https://mlsanity.com/paper/2606.05438/) (2026)
- [Finding Stationary Points by Comparisons](https://mlsanity.com/paper/2606.27082/) (2026)
- [Near-Optimal Convex Optimization with Lazy Second-Order Oracles](https://mlsanity.com/paper/2610.03222/) (2026)

## Abstract (arXiv)

We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We provide a method that for any twice-differentiable fcolon mathbb Rd rightarrow mathbb R with L2-Lipschitz Hessian, input initial point with Delta-bounded sub-optimality, and sufficiently small ε > 0, outputs an ε-critical point, i.e., a point x such that |nabla f(x)| ≤ ε, using tildeO(L21/4 nH-1/2Deltaε-9/4) queries to a gradient oracle and nH queries to a Hessian oracle for any positive integer nH. As a consequence, we obtain an improved gradient query complexity of tildeO(d1/3L21/2Deltaε-3/2) in the case of bounded dimension and of tildeO(L23/4Delta3/2ε-9/4) in the case where we are allowed only a single Hessian query. We obtain these results through a more general algorithm which can handle approximate Hessian computations and recovers the state-of-the-art bound of computing an ε-critical point with O(L11/2L21/4Deltaε-7/4) gradient queries provided that f also has an L1-Lipschitz gradient.