Balancing Gradient and Hessian Queries in Non-Convex Optimization

Deeksha Adil, Brian Bullins, Aaron Sidford, Chenyi Zhang

TL;DR

This paper introduces a new non-convex optimization framework that allows researchers to flexibly trade off between gradient and Hessian computations when searching for stationary points. By leveraging a novel spectral norm transformation and allowing for approximate Hessian queries, the authors achieve state-of-the-art complexity bounds, including an improved dimension-dependent gradient query rate of $\tilde{O}(d^{1/3}\epsilon^{-3/2})$.

What Problem Does This Paper Address?

In non-convex optimization—which underpins much of modern machine learning—the standard goal is to find an $\epsilon$-critical point, a location where the gradient norm is small ($\|\nabla f(x)\| \leq \epsilon$).

To get there, algorithms rely on "oracles" that provide local information about the function:

  • First-order oracles provide gradients. They are cheap to compute but lead to slower convergence rates (like gradient descent's $O(\epsilon^{-2})$).
  • Second-order oracles provide Hessians (matrices of second derivatives). They allow for much faster convergence, but computing and storing a full $d \times d$ Hessian matrix is prohibitively expensive in high dimensions.

Prior work mostly treated these two regimes as distinct choices. This paper tackles a more nuanced question: What fine-grained trade-offs are possible if we can choose exactly how many Hessian queries to make, or if we only have access to a noisy, approximate Hessian?

Methods

The authors develop a multi-layered algorithmic framework to bridge the gap between gradient and Hessian methods:

  1. Spectral Norm Transformation ($\widehat{H} = \phi(H)$): Instead of using the exact Hessian or a standard Euclidean norm, the core algorithm runs Accelerated Gradient Descent (AGD) inside a custom norm induced by a transformed approximate Hessian. They apply a carefully designed piecewise function $\phi$ to the eigenvalues of the approximate Hessian to intentionally introduce spectral gaps, stabilizing the algorithm against matrix perturbations.
  2. Critical-or-Progress Subroutine: This inner loop either successfully finds an $\epsilon$-critical point or guarantees a significant decrease in the function's overall value.
  3. Lazy Hessian Updates & Negative Curvature Descent: The outer algorithm (Algorithm 2) maintains a Hessian estimate lazily, only re-querying the Hessian oracle when the iterates move past a certain distance threshold. If it encounters a direction of significant negative curvature, it takes a direct step along it to rapidly decrease the function value.
  4. Subspace Reduction for Unbounded Smoothness: Standard optimization proofs often assume a globally bounded gradient Lipschitz constant ($L_1$). The authors introduce a reduction technique (Algorithm 3) that splits the space into high- and low-eigenvalue components, effectively removing the algorithm's dependence on a global $L_1$ bound.

Datasets

None used. This paper is entirely theoretical and focuses on proving mathematical complexity bounds.

Key Insights and Ideas

  • Space Warping via Approximate Geometry: Instead of altering step sizes globally, warping the optimization space using a spectrally altered approximate Hessian allows first-order gradient steps to mimic the fast convergence of second-order methods within well-behaved subspaces.
  • The Power of Laziness: You don't need a fresh Hessian at every step. Updating the Hessian only when the algorithm drifts too far from its reference point preserves fast convergence rates while drastically cutting down on expensive oracle queries.
  • Breaking the $d^{1/2}$ Barrier: By approximating the Hessian columns using finite differences of gradients, the authors achieve a dimension dependence of $d^{1/3}$. For dimensions $d \geq 7$, this beats the long-standing state-of-the-art dimension dependence of $d^{1/2}$.

Key Results

The paper provides a smooth trade-off curve: given $nH$ Hessian queries, the algorithm requires at most $\tilde{O}(L_2^{1/4} n_H^{-1/2}\Delta\epsilon^{-9/4})$ gradient queries.

Special cases of this result yield significant improvements over prior literature:

  • Single Hessian Query ($n_H = 1$): Finds an $\epsilon$-critical point using $\tilde{O}(\Delta^{3/2}L_2^{3/4}\epsilon^{-9/4})$ gradient queries, improving upon previous implicit bounds by a factor of $O(\Delta^{1/2}L_2^{1/4}\epsilon^{-3/4})$.
  • Dimension-Dependent Regime: By using finite differences to approximate the Hessian, the method achieves a gradient-only query complexity of $\tilde{O}(d^{1/3}L_2^{1/2}\Delta\epsilon^{-3/2} + d)$.

A comprehensive comparison with prior state-of-the-art methods is illustrated in the table below:

Comparison of gradient query complexities to reach an $\epsilon$-critical point.

Limitations and Future Work

  • Purely Theoretical: The paper does not include empirical evaluations or practical implementations on real-world machine learning tasks.
  • Logarithmic Overhead: The bounds hide substantial polylogarithmic factors (with exponents as high as 18 or 19 in the proofs), which might hurt performance in practical settings unless optimized.
  • Optimality Open Question: While the $d^{1/3}$ dimension dependence is a breakthrough for $d \geq 7$, it remains an open question whether this is the absolute theoretical lower bound for this regime.
  • Smoothness Requirements: The framework strictly requires twice-differentiable functions with Lipschitz Hessians, meaning it cannot be directly applied to non-smooth optimization problems (e.g., functions utilizing ReLU activations) without modification.

Summary updated

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\colon \mathbb R^d \rightarrow \mathbb R$ with $L_2$-Lipschitz Hessian, input initial point with $Δ$-bounded sub-optimality, and sufficiently small $ε> 0$, outputs an $ε$-critical point, i.e., a point $x$ such that $\|\nabla f(x)\| \leq ε$, using $\tilde{O}(L_2^{1/4} n_H^{-1/2}Δε^{-9/4})$ queries to a gradient oracle and $n_H$ queries to a Hessian oracle for any positive integer $n_H$. As a consequence, we obtain an improved gradient query complexity of $\tilde{O}(d^{1/3}L_2^{1/2}Δε^{-3/2})$ in the case of bounded dimension and of $\tilde{O}(L_2^{3/4}Δ^{3/2}ε^{-9/4})$ in the case where we are allowed only a \emph{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(L_1^{1/2}L_2^{1/4}Δε^{-7/4})$ gradient queries provided that $f$ also has an $L_1$-Lipschitz gradient.
BibTeX
@inproceedings{adil2025balancing,
  author = {Deeksha Adil and Brian Bullins and Aaron Sidford and Chenyi Zhang},
  title = {{Balancing Gradient and Hessian Queries in Non-Convex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=r8U08iSppJ},
}
Figure