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

1. Problem Statement

Zeroth-order (ZO) optimization addresses scenarios where the objective function $F(\theta) = \mathbb{E}_\xi[f(\theta; \xi)]$ is a black box accessible only through noisy function evaluations. While ZO gradient estimation is well-established, accurate ZO Hessian approximation remains a significant challenge, particularly in high-dimensional and noisy regimes.

Accurate curvature information is critical for:

• Derivative-free bilevel optimization.
• Uncertainty quantification.
• Curvature-aware fine-tuning of Large Language Models (LLMs).

Existing methods face two primary limitations:

1. High Variance: Classical randomized estimators (e.g., Stein-type estimators) often suffer from high variance in high-dimensional settings, leading to unstable optimization.
2. Limited Scope: Prior research has focused primarily on estimating the Hessian matrix $\nabla^2 F(\theta)$ itself. There is limited attention paid to the regularized inverse Hessian $(\nabla^2 F(\theta) + \lambda I_d)^{-1}$ and the inverse Hessian-gradient product $(\nabla^2 F(\theta) + \lambda I_d)^{-1}\nabla F(\theta)$, which are essential for second-order ZO updates.
3. Query Efficiency: Naive finite-difference methods require $O(d^2)$ queries, while existing randomized methods often fail to balance variance reduction with query reuse effectively.

2. Methodology

2.1. Theoretical Framework: Policy Optimization Lens

The authors propose a unified framework that reinterprets ZO Hessian approximation through the lens of Single-Step Policy Optimization (PO).

• Smoothed Objective: The ZO objective is reformulated as a smoothed objective $F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)}[\mathbb{E}_\xi[f(x; \xi)]]$, where $\pi_\theta$ is a parameterized sampling policy (e.g., Gaussian $N(\theta, \mu^2 I_d)$).
• Hessian Identity: By differentiating the policy gradient, the authors derive a general Hessian identity for the smoothed objective:
  $$\nabla^2 F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)} \left[ H_{\pi_\theta} \cdot \mathbb{E}_\xi[f(x; \xi)] \right]$$
  where $H_{\pi_\theta}$ is the Hessian of the policy log-density.
• Unification of Estimators: This perspective reveals that classical Stein-type estimators (One-point, Two-point, Three-point) and Central-Difference estimators are special cases of this framework, distinguished solely by their choice of baseline (e.g., zero baseline, anchor baseline $f(\theta)$, or antithetic sampling).

2.2. ZoVH: Variance-Reduced Hessian Estimator

Building on the PO framework, the authors introduce ZoVH (Zeroth-Order Variance-reduced Hessian), which employs two key techniques:

1. Optimal Averaged Baseline:

   • Unlike gradient estimators where baselines are often heuristic, the authors prove that for the Hessian estimator derived from the rank-one identity, the averaged baseline $\hat{b} = \frac{1}{K}\sum f(x_k)$ is the unique choice that preserves unbiasedness.
   • Theoretically, this baseline is proven to minimize the variance of the estimator among all constant baselines.

2. Query Reuse Strategy:

   • To further reduce variance without increasing query costs, ZoVH utilizes a history buffer of past function queries.
   • This is interpreted as off-policy learning within the PO framework, where historical data (generated from previous iterates) is reweighted via importance sampling to estimate the current Hessian.
   • This effectively increases the sample size from $K$ to $NK$ (where $N$ is the history length) without additional function evaluations.

2.3. Efficient Inverse Approximations

To enable practical second-order updates, the paper extends ZoVH to approximate the inverse Hessian and the inverse Hessian-gradient product:

• Inverse Hessian: Utilizes the Woodbury matrix identity to compute the inverse of the regularized rank-$K$ Hessian estimator efficiently ($O(K^2 d)$ or $O(Kd)$ with diagonal approximation) without inverting a dense $d \times d$ matrix.
• Bias-Corrected Product: When the same random directions are used for both gradient and Hessian estimation (to save queries), correlation bias is introduced. The authors propose a leave-one-out strategy to correct this bias, allowing for efficient computation of $(\nabla^2 F + \lambda I)^{-1}\nabla F$ with minimal overhead.

3. Key Contributions

1. Unified PO Perspective: Established a theoretical equivalence between general ZO Hessian estimators and the Hessian of a smoothed PO objective, unifying classical randomized estimators as specific instances of baseline selection.
2. ZoVH Algorithm: Developed a comprehensive suite of variance-reduced estimators for the full Hessian, its regularized inverse, and the bias-corrected inverse Hessian-gradient product.
3. Theoretical Guarantees:
   • Proved the unbiasedness of the Hessian estimator with the averaged baseline.
   • Demonstrated the variance optimality of the averaged baseline.
   • Provided error bounds for the entire ZoVH suite (bias-variance decomposition).
   • Established convergence guarantees for the resulting curvature-aware ZO algorithm to an $\epsilon$-stationary point.
4. Practical Efficiency: Introduced a query reuse mechanism that enhances sample efficiency without inflating the query budget, and derived stable inverse approximations suitable for high-dimensional problems like LLM fine-tuning.

4. Experimental Results

The authors validated ZoVH across synthetic benchmarks, neural network training, and black-box adversarial attacks.

• Hessian Estimation Accuracy:

  • On synthetic functions (Quadratic, Rosenbrock, Styblinski-Tang) and CNN layers, ZoVH (with query reuse, $N=4$) consistently achieved the lowest Frobenius norm error compared to classical Stein and Central-Difference estimators.
  • ZoVH ($N=1$) showed an 8x accuracy improvement over the Central-Difference estimator on Quadratic and Rosenbrock functions.
  • On CNN layers, ZoVH ($N=4$) achieved a 9x error reduction compared to the Central-Difference estimator.

• Optimization Convergence:

  • In synthetic optimization tasks, ZoVH ($N=4$) significantly outperformed Vanilla ZOO, HiZOO, and ZoAR in both convergence speed and final accuracy, achieving an average 22x speedup over Vanilla ZOO.
  • In Black-Box Adversarial Attacks, ZoVH ($N=4$) required 4x fewer iterations to achieve a successful attack compared to Vanilla ZOO.

• LLM Fine-Tuning:

  • Applied to fine-tuning OPT-1.3B and OPT-13B models on GLUE/SuperGLUE tasks.
  • ZoVH demonstrated faster convergence and higher test accuracy compared to MeZO and HiZOO.
  • Runtime and memory overhead were minimal, with ZoVH being only slightly slower than MeZO and using negligible extra memory (storing only scalar values and seeds).

5. Significance and Claims

The paper claims that ZoVH provides a robust foundation for curvature-aware derivative-free optimization. By bridging the gap between ZO approximation and Policy Optimization, the work offers:

• Theoretical Clarity: A rigorous derivation that explains why certain estimators work and how to optimize them via baseline selection.
• Practical Utility: A method that achieves superior estimation accuracy and convergence performance in real-world applications (including LLMs) without the prohibitive query costs of full finite-difference schemes.
• Scalability: The ability to handle high-dimensional problems (e.g., millions of parameters in LLMs) through efficient inverse approximations and query reuse, making second-order optimization feasible in black-box settings where it was previously impractical.

The authors emphasize that while the method introduces a smoothing bias (inherent to ZO methods), the variance reduction and query efficiency gains significantly outweigh this trade-off, leading to faster and more stable convergence in noisy, high-dimensional environments.