Balancing Gradient and Hessian Queries in Non-Convex Optimization

Deeksha Adil Brian Bullins Aaron Sidford Chenyi Zhang ‡ · 2025

Read Balancing Gradient and Hessian Queries in Non-Convex Optimization by Deeksha Adil Brian Bullins Aaron Sidford Chenyi Zhang ‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20786.txt.

Introduction

Deeksha Adil and three co-authors develop optimization methods that trade off gradient queries against Hessian queries when hunting critical points of non convex functions. Gradients give slope, Hessians give curvature, and each costs differently depending on the system, so the best mix matters.

For any smooth function with Lipschitz Hessian, a bounded starting gap. A chosen accuracy, their method reaches an approximate critical point with a stated gradient budget that falls as the Hessian budget grows. The result improves known gradient complexity and makes the exchange rate between first and second order information precise. Such trade offs guide algorithm design when curvature calls are cheap for some variables but costly for others.

Catalog record

CREATORDeeksha Adil Brian Bullins Aaron Sidford Chenyi Zhang ‡
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20786

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Balancing Gradient and Hessian Queries in Non-Convex Optimization Deeksha Adil Brian Bullins Aaron Sidford Chenyi Zhang ‡ Abstract 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 f : ℝ d → ℝ f\colon\mathbb{R}^{d}\rightarrow\mathbb{R} with L 2 L_{2} -Lipschitz Hessian, input initial point with Δ \Delta -bounded sub-optimality, and sufficiently small ϵ > 0 \epsilon>0 , outputs an ϵ \epsilon -critical point, i.e., a point x x such that ‖ ∇ f ​ ( x ) ‖ ≤ ϵ \|\nabla f(x)\|\leq\epsilon , using O ~ ( L 2 1 / 4 n H − 1 / 2 Δ ϵ − 9 / 4 ) \tilde{O}(L_{2}^{1/4}n_{H}^{-1/2}\Delta\epsilon^{-9/4}) queries to a gradient oracle and n H n_{H} queries to a Hessian oracle for any positive integer n H n_{H} . As a consequence, we obtain an improved gradient query complexity of O ~ ( d 1 / 3 L 2 1 / 2 Δ ϵ − 3 / 2 ) \tilde{O}(d^{1/3}L_{2}^{1/2}\Delta\epsilon^{-3/2}) in the case of bounded dimension and of O ~ ( L 2 3 / 4 Δ 3 / 2 ϵ − 9 / 4 ) \tilde{O}(L_{2}^{3/4}\Delta^{3/2}\epsilon^{-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 ϵ \epsilon -critical point with O ( L 1 1 / 2 L 2 1 / 4 Δ ϵ − 7 / 4 ) O(L_{1}^{1/2}L_{2}^{1/4}\Delta\epsilon^{-7/4}) gradient queries provided that f f also has an L 1 L_{1} -Lipschitz gradient. 1 Introduction We consider the problem of computing an \epsilon -critical point of a differentiable function f\colon\mathbb{R}^{d}\rightarrow\mathbb{R} , that is x with \norm{\grad f(x)}\leq\epsilon , given an initial point x^{(0)}\in\mathbb{R}^{d} with bounded function error or sub-optimality, \Delta:=f(x^{(0)})-\inf_{x\in\mathbb{R}^{d}}f(x) . 1 1 1 Throughout the paper we let \norm{\cdot} denote the Euclidean or \ell_{2} norm, and when applied to a square matrix, we let it denote the \ell_{2} -operator norm, i.e., \norm{A}=\sup_{x\in\mathbb{R}^{d}}\norm{Ax}/\norm{x} for all A\in\mathbb{R}^{d\times d} . This critical point computation problem —also referred to as making the gradient norm small [ 2 , 33 ] or finding stationary points [ 1 ] —is a foundational and well-studied optimization problem. It is ubiquitous in machine learning research and has been studied extensively for decades; see e.g., [ 10 , 11 ] for references. Obtaining an \epsilon -critical point is a natural stopping condition for many optimization methods. For general smooth non-convex functions, guarantees of this type—as opposed to reaching a globally optimal point—may be provably established without incurring exponential dimension dependence in the rates [ 10 , 11 ] . Furthermore, there are even instances of non-convex objectives, such as regression tasks with non-convex regularization [ 31 ] and matrix completion [ 21 ] , for which reaching what is known as a second-order critical point [ 1 , 9 , 26 , 27 ] —which generalize \epsilon -critical points—suffices to establish global optimality. In certain foundational settings, optimal query complexities for critical point computation are known. For example, consider the following simple variant of gradient descent, e.g., x^{(t+1)}\leftarrow x^{(t)}-\frac{1}{L_{1}}\nabla f(x^{(t)})=\mathrm{argmin}_{x\in\mathbb{R}^{d}}T^{1}_{x^{(t)}}(x)+\frac{L_{1}}{2}\big\|x^{(t)}-x\big\|^{2} (1) where T^{p}_{x^{(t)}}(x) is the p th-order Taylor approximation of f evaluated at x^{(t)} and f is L_{1} -smooth, i.e., has an L_{1} -Lipschitz gradient where \norm{\grad f(x) - \grad f(y)}\leq L_{1}\norm{x - y} for all x,y\in\mathbb{R}^{d} . Eq. ( 1 ) computes an \epsilon -critical point with at most O(L_{1}\Delta\epsilon^{-2}) iterations [ 32 ] , and it is known that for sufficiently large d , any method (even a randomized one that succeeds with high probability) must compute at least \Omega(L_{1}\Delta\epsilon^{-2}) gradients in the worst case [ 10 ] . More broadly, for f that has L_{p} -Lipschitz p th-order derivatives define a p th-order oracle as one that when queried at a point x returns all partial derivatives of f at x up to order p . It is known that the method x^{(t+1)}\leftarrow\mathrm{argmin}_{x\in\mathbb{R}^{d}}T^{p}_{x^{(t)}}(x)+c_{p}L_{p}\big\|x^{(t)}-x\big\|^{p+1}, for suitable choice of constant c_{p}>0 , solves the problem in O(c_{p}L_{p}^{1/p}\Delta\epsilon^{-(p+1)/p}) queries and iterations [ 7 ] , and these rates are optimal in terms of dimension-independent query complexity [ 10 ] . Unfortunately, the faster rates for critical point computation obtained via higher-order oracles, e.g., p th-order oracles, generally come at a cost. Simply specifying the output of a p th-order oracle at a point involves outputting d^{p} numbers in the worst case, which even for a small constant p can be prohibitively expensive when the problem dimension is large. Correspondingly, there has been extensive research [ 1 , 9 , 10 , 11 , 34 ] on what rates are obtainable given various assumptions on f and access only to a gradient oracle , i.e., an oracle that when queried at x\in\mathbb{R}^{d} outputs \nabla f(x) , the gradient of f at x , and a Hessian oracle , i.e., an oracle that when queried at x\in\mathbb{R}^{d} outputs \nabla^{2}f(x) , the Hessian of f at x . One particularly relevant line of work has shown that with only a gradient oracle for f that has L_{1} -Lipschitz gradient and L_{2} -Lipschitz Hessian, it is possible to obtain a rate of O(L_{1}^{1/2}L_{2}^{1/4}\Delta\epsilon^{-7/4}) if 0<\epsilon\leq\min\{L_{1}^{2}L_{2}^{-1},\Delta^{2/3}L_{2}^{1/3}\} [ 1 , 9 , 29 ] , and [ 11 ] provided an \Omega(L_{1}^{3/7}L_{2}^{2/7}\Delta\epsilon^{-12/7}) lower bound for this setting. In other words, when the Hessian of the function is also Lipschitz continuous, it is possible to improve upon the O(L_{1}\Delta\epsilon^{-2}) query complexity of gradient descent. Meanwhile, if we further allow for querying Hessian information, this rate can be improved to O(L_{2}^{1/2}\Delta\epsilon^{-3/2}) [ 34 ] , which is optimal under this stronger oracle model [ 10 , 12 ] . In this paper, we perform a more fine-grained study of the problem of critical point computation. We ask, what trade-offs are possible between the number of gradient and Hessian computations that are needed to compute \epsilon -critical points for functions with L_{1} -Lipschitz gradients and L_{2} -Lipschitz Hessians? Our main result is an algorithm which offers a new such trade-off, even when the Hessian is computed only approximately. Furthermore, we show that this result generalizes the bounds of [ 29 ] and yields further improvements in dimension-dependent settings. 1.1 Our Results Our main result is a new trade-off in the number of approximate Hessian oracle queries and gradient queries for f needed for \epsilon -critical point computation. Here we define the approximate Hessian oracle we consider and provide our main theorem. Definition 1 (Approximate Hessian Oracle) . We call a procedure a \delta -approximate Hessian oracle for twice differentiable f:\mathbb{R}^{d}\rightarrow\mathbb{R} if when queried at x\in\mathbb{R}^{d} it outputs symmetric H_{x}\in\mathbb{R}^{d\times d} such that \big\|H_{x}-\nabla^{2}f(x)\big\|\leq\delta . Theorem 1 (Main Result) . Let f\colon\mathbb{R}^{d}\mapsto\mathbb{R} have L_{1} -Lipschitz gradient and L_{2} -Lipschitz Hessian. There is an algorithm which given any x^{(0)}\in\mathbb{R}^{d} with \Delta -bounded sub-optimality with respect to f , positive integer n_{H} , and 0<\epsilon\leq\min\{L_{1}^{2}L_{2}^{-1},\Delta^{2/3}L_{2}^{1/3}\} , outputs an \epsilon -critical point of f with at most n_{H} queries to a \delta -approximate Hessian oracle and at most \displaystyle O\left(\frac{\Delta L_{2}^{1/4}c_{\delta}^{1/2}}{\epsilon^{7/4}}\cdot\poly\log\left(\frac{c_{\ell}}{c_{\delta}}\right)\right) queries to a gradient oracle for f , where

Read the complete text