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

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.

Many important optimization problems are like tuning a machine when we can only try a setting and observe the final score. This happens in black box systems and memory efficient language model tuning, where gradients are unavailable or too costly to compute. To make better updates, an optimizer needs to know not only which direction improves the score, but also how the score bends around the current setting. Estimating this curvature from a few noisy trials is usually unstable, especially when the number of parameters is large. We revisit this problem by viewing each random trial as a simple one step decision process. This view leads to ZoVH, a method that reduces noise by subtracting a carefully chosen average score and by reusing recent trials instead of throwing them away. ZoVH also turns these curvature estimates into practical update steps without forming or inverting huge matrices. In experiments on synthetic problems, finding small changes that fool image classifiers, and tuning language models, it produced more accurate curvature estimates and reached good solutions faster than existing methods that rely only on trial scores. This makes curvature based optimization more practical when gradients are unavailable.