Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens

Junbin Qiu, Zhaowei Hong, Renzhe Xu, Yao Shu · 2026

Read Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens by Junbin Qiu, Zhaowei Hong, Renzhe Xu, Yao Shu (2026) 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-2605-30960.txt.

Introduction

Qiu and colleagues recast Hessian guess through single-step policy tuning. Exact Hessian gauging is key for slope-free methods, yet low-variance Hessian gauges in high sizes remain hard. Their view shows match between zeroth-order Hessian gauges and the Hessian of a smoothed goal, joining old gauges as picks. They give ZoVH, a suite of gauges for the full Hessian and its inverse. ZoVH uses an optimal base and query reuse using past queries to enhance speed. Theory confirms fairness and settling, and tests show better truth.

Catalog record

CREATORJunbin Qiu, Zhaowei Hong, Renzhe Xu, Yao Shu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE144816
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30960

Browse the full library · About the Tower of Babel

Full text

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

Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens Junbin Qiu, Zhaowei Hong, Renzhe Xu, Yao Shu Abstract Accurate Zeroth-Order (ZO) Hessian estimation is a cornerstone of derivative-free methods, essential for tasks such as bilevel optimization, Bayesian inference, and uncertainty quantification. However, obtaining a complete suite of low-variance estimators for the Hessian and its inverse in high-dimensional settings remains a significant challenge. To address this, we propose a unified framework that reinterprets ZO Hessian approximation through the lens of single-step Policy Optimization (PO). This perspective establishes a theoretical equivalence between general ZO Hessian estimators and the Hessian of a smoothed PO objective, unifying distinct classical randomized estimators as specific instances of baseline selection. Building on this foundation, we introduce ZoVH, a comprehensive suite of variance-reduced estimators for the full Hessian matrix, its regularized inverse, and the bias-corrected inverse Hessian-gradient product. ZoVH leverages two key techniques: (1) a unique optimal baseline derived to provably minimize variance, and (2) a query reuse strategy that incorporates historical function queries to enhance sample efficiency without inflating costs. Our rigorous theoretical analysis confirms the unbiasedness of the Hessian estimator, validates the variance optimality of our baseline, provides error bounds for the entire ZoVH suite, and establishes convergence guarantees for the resulting curvature-aware ZO algorithm. Extensive empirical results validate our theoretical findings, demonstrating that ZoVH achieves superior estimation accuracy and convergence performance in real-world applications. Code is available at https://github.com/Qjbtiger/ZoVH . 1 Introduction Zeroth-Order (ZO) Hessian approximation for black-box objectives F({\bm{\theta}})\triangleq\mathbb{E}_{\xi}[f({\bm{\theta}};\xi)] , which are accessible solely through noisy function evaluations, represents a fundamental challenge in derivative-free optimization ( 4 ; 3 ; 15 ; 6 ) . Estimating accurate curvature information is crucial for various applications, including derivative-free bilevel optimization ( 1 ; 25 ) , uncertainty quantification ( 8 ) , and curvature-aware fine-tuning of Large Language Models (LLMs) ( 29 ) . While naive finite-difference methods typically necessitate \mathcal{O}(d^{2}) function queries ( 5 ) , randomized rank-one estimators can reduce the query complexity to a constant number of evaluations, independent of the dimension d (e.g., 4 queries for 2SPSA ( 18 ) and 3 for RDSA ( 9 ) ). We provide a discussion of related work about ZO Hessian approximation in Appx. A . Despite its practical significance, ZO Hessian approximation suffers from high variance, particularly in noisy, high-dimensional regimes ( 30 ; 6 ) . While a recent study by ( 14 ) bridged ZO gradient estimation with single-step Policy Optimization (PO) methods to establish a rigorous theoretical foundation and variance reduction techniques, such connections remain unexplored for ZO Hessian approximation. Moreover, prior studies have primarily focused on estimating the Hessian \nabla^{2}F({\bm{\theta}}) itself. In contrast, the estimation of regularized inverse Hessian (\nabla^{2}F({\bm{\theta}})+\lambda{\mathbf{I}}_{d})^{-1} and its product with the gradient (\nabla^{2}F({\bm{\theta}})+\lambda{\mathbf{I}}_{d})^{-1}\nabla F({\bm{\theta}}) are essential for curvature-aware zeroth-order optimization ( 30 ; 29 ) , but have received limited attention. Our first contribution is to demonstrate a unified framework for ZO Hessian approximation from the PO perspective. Within this framework, ZO Hessian approximation is reinterpreted as the Hessian of a smoothed objective \nabla^{2}F_{\mu}({\bm{\theta}}) under a parameterized sampling policy (Sec. 3.1 ). Specifically, for Gaussian sampling, this perspective leads to explicit Hessian identities (Props. 3.2 and 3.3 ) incorporating baseline terms. By selecting different baselines, these identities recover classical Hessian estimators from ( 3 ) as special cases (Sec. 3.2 ). Furthermore, this framework extends naturally to general sampling distributions via importance sampling (Sec. 3.3 ). Building on this foundation, our second contribution is ZoVH, a novel Zeroth-Order Variance-reduced Hessian approximation that minimizes estimator variance through optimal baseline selection and query reuse (Sec. 4 ). ZoVH constructs a Hessian estimator leveraging two techniques: (a) an averaged baseline that provably minimizes variance among all constant baselines (Thm. 4.7 ); and (b) a query reuse strategy that estimates the Hessian from a history buffer of past function queries, increasing the sample size without incurring additional query costs, thereby further reducing variance (Sec. 4.1 ). To assess the efficacy of ZoVH, we provide a comprehensive theoretical analysis in Sec. 4.2 , covering its unbiasedness (Thm. 4.6 ) and bias-variance trade-off (Thm. 4.8 ). We then present an empirical error analysis in Sec. 6.1 , demonstrating that ZoVH achieves significantly lower estimation error compared to classical Hessian estimators across various synthetic functions and neural networks. Our third contribution lies in the development of a practical framework that extends ZoVH to an efficient curvature-aware Zeroth-Order Optimization (ZOO) algorithm. Specifically, we develop a stable ZO inverse Hessian approximation by incorporating ridge regularization into the ZoVH estimator (Sec. 5.1 ), and a bias-corrected inverse Hessian-gradient product that mitigates the bias introduced by reusing function queries for both Hessian and gradient estimation (Sec. 5.2 ). These approximations form the basis of a curvature-aware ZOO algorithm (Alg. 1 ) that efficiently computes second-order updates using minimal function queries. Theoretically, we prove the convergence guarantee of this approach (Thm. 5.5 ), and empirically, we validate its effectiveness on three representative applications (Sec. 6.2 ), showing substantial improvements over existing ZO methods. 2 Preliminaries Problem Setup. We study ZO approximation of the Hessian \nabla^{2}F({\bm{\theta}})\in{\mathbb{R}}^{d\times d} for the stochastic objective: F({\bm{\theta}})\triangleq\mathbb{E}_{\xi}\!\left[f({\bm{\theta}};\xi)\right], (1) where F is accessible only through noisy function evaluations of f({\bm{\theta}};\xi) , and \xi represents the inherent stochasticity in the function evaluation. Our goal is to construct a Hessian estimator \widehat{{\mathbf{H}}}({\bm{\theta}}) using a small number of function queries, thereby avoiding the prohibitive \mathcal{O}(d^{2}) complexity of full finite-difference schemes ( 5 ) , while maintaining low estimation variance. Classical ZO Hessian Estimators. We adopt a unified perspective in which Hessian information is recovered from finite differences of noisy function evaluations along random probing directions. Several classical ZO Hessian estimators ( 3 ; 30 ) can be expressed using a common template. Let \{{\mathbf{u}}_{k}\}_{k=1}^{K}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}{\mathcal{N}}({\bm{0}},{\mathbf{I}}_{d}) be standard Gaussian probing directions and \mu>0 be a smoothing parameter. The One-Point Stein estimator combines a rank-one term with an identity correction derived from Stein’s identity ( 19 ) : \widehat{{\mathbf{H}}}_{\text{S}_{1}}\triangleq\frac{1}{K}\sum_{k=1}^{K}\frac{f({\bm{\theta}}+\mu{\mathbf{u}}_{k};\xi)}{\mu^{2}}\left({\mathbf{u}}_{k}{\mathbf{u}}_{k}^{\top}-{\mathbf{I}}_{d}\right)\ . (2) Following the same principle, the Two-Point Stein estimator replaces the one-point measurement with a one-sided finite difference: \widehat{{\mathbf{H}}}_{\text{S}_{2}}\triangleq\frac{1}{K}\sum_{k=1}^{K}\frac{f({\bm{\theta}}+\mu{\mathbf{u}}_{k};\xi)-f({\bm{\theta}};\xi)}{\mu^{2}}\left({\mathbf{u}}_{k}{\mathbf{u}}_{k}^{\top}-{\mathbf{I}}_{d}\right)\ , (3) and the Three-Point Stein estimator further adopts a symmetric central difference, which typically improves numerical stability: \displaystyle\widehat{{\mathbf{H}}}_{\text{S}_{3}}\triangleq\frac{1}{2K}\sum_{k=1}^{K} \displaystyle\frac{f({\bm{\theta}}_{k}^{+};\xi)-2f({\bm{\theta}};\xi)+f({\bm{\theta}}_{k}^{-};\xi)}{\mu^{2}} (4) \displaystyle\times\left({\mathbf{u}}_{k}{\mathbf{u}}_{k}^{\top}-{\mathbf{I}}_{d}\right)\ . where {\bm{\theta}}_{k}^{\pm}\triangleq{\bm{\theta}}\pm\mu{\mathbf{u}}_{k} . In contrast to the Stein-type estimators, ( 3 ; 29 ) consider a randomized Central-Difference (CD) estimator that employs a rank-one weighted average without the identity correction: \widehat{{\mathbf{H}}}_{\text{CD}}({\bm{\theta}})\triangleq\frac{1}{2K}\sum_{k=1}^{K}\frac{f({\bm{\theta}}_{k}^{+};\xi)-2f({\bm{\theta}};\xi)+f({\bm{\theta}}_{k}^{-};\xi)}{\mu^{2}}\,{\mathbf{u}}_{k}{\mathbf{u}}_{k}^{\top}\ . (5) In Sec. 3 , we reinterpret these estimators through the lens of PO, demonstrating that they emerge as special cases of our generalized Hessian estimation framework. ZO Gradient Estimator. In practical ZOO algorithms, Hessian approximation is typically paired with a ZO gradient estimator to enable second-order updates ( 30 ; 29 ) . We adopt the Gaussian-smoothed gradient estimator from ( 14 ) , which approximates \nabla F({\bm{\theta}}) via finite differences along Gaussian probing directions \{{\mathbf{u}}_{k}\}_{k=1}^{K}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}{\mathcal{N}}({\bm{0}},{\mathbf{I}}_{d}) : \hat{\nabla}F({\bm{\theta}})\triangleq\frac{1}{K-1}\sum_{k=1}^{K}\frac{f({\bm{\theta}}+\mu{\mathbf{u}}_{k};\xi)-b}{\mu}\,{\mathbf{u}}_{k}\ , (6) where the averaged baseline b\triangleq\frac{1}{K}\sum_{k=1}^{K}f({\bm{\theta}}+\mu{\mathbf{u}}_{k};\xi) is used to reduce the estimator variance. Notations. Throughout this paper, we denote \mathbb{E}_{\mathbf{u}}[\cdot]\triangleq\mathbb{E}_{{\mathbf{u}}\sim{\mathcal{N}}(0,{\mathbf{I}}_{d})}\quantity[\cdot] , and \mathbb{E}\quantity[\cdot]\triangleq\mathbb{E}_{\xi}\ \mathbb{E}_{\mathbf{u}}\quantity[\cdot] as the full expectation over both the stochasticity \xi and the standard Gaussian distribution. Furthermore, for a matrix {\mathbf{A}} , we use \norm{\rmA} and \norm{\rmA}_{F} to denote its spectral norm and Frobenius norm.

Read the complete text