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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 30 references that are in the map.
- First posted on arXiv 29 May 2026.

## Builds on (most cited first, 14 of 14)

- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [SuperGLUE: A Stickier Benchmark for General-Purpose Language Understanding Systems](https://mlsanity.com/paper/1905.00537/) (2019)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Adam-mini: Use Fewer Learning Rates To Gain More](https://mlsanity.com/paper/2406.16793/) (2024)
- [Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizer](https://mlsanity.com/paper/2402.15173/) (2024)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Refining Adaptive Zeroth-Order Optimization at Ease](https://mlsanity.com/paper/2502.01014/) (2025)
- [Hessian Estimation via Stein's Identity in Black-Box Problems](https://mlsanity.com/paper/2104.01317/) (2021)
- [Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds](https://mlsanity.com/paper/2205.14737/) (2022)
- [Zeroth-Order Optimization is Secretly Single-Step Policy Optimization](https://mlsanity.com/paper/2506.14460/) (2025)
- [Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing](https://mlsanity.com/paper/2404.00158/) (2024)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [Gradient and Hessian approximations in Derivative Free Optimization](https://mlsanity.com/paper/2001.08355/) (2020)

## Abstract (arXiv)

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