# Subspace-based Approximate Hessian Method for Zeroth-Order Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 8 Jul 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizer](https://mlsanity.com/paper/2402.15173/) (2024)
- [How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/2203.14195/) (2022)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [A Comprehensive Review of Digital Twin -- Part 1: Modeling and Twinning Enabling Technologies](https://mlsanity.com/paper/2208.14197/) (2022)
- [Adversarial Variational Optimization of Non-Differentiable Simulators](https://mlsanity.com/paper/1707.07113/) (2017)
- [Zeroth order optimization with orthogonal random directions](https://mlsanity.com/paper/2107.03941/) (2021)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization](https://mlsanity.com/paper/2008.07545/) (2020)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [HELENE: Hessian Layer-wise Clipping and Gradient Annealing for Accelerating Fine-tuning LLM with Zeroth-order Optimization](https://mlsanity.com/paper/2411.10696/) (2024)
- [Improve Single-Point Zeroth-Order Optimization Using High-Pass and Low-Pass Filters](https://mlsanity.com/paper/2111.01701/) (2021)
- [Zeroth-order Random Subspace Algorithm for Non-smooth Convex Optimization](https://mlsanity.com/paper/2401.13944/) (2024)
- [Zeroth-Order SciML: Non-intrusive Integration of Scientific Software with Deep Learning](https://mlsanity.com/paper/2206.02785/) (2022)
- [Linear interpolation gives better gradients than Gaussian smoothing in derivative-free optimization](https://mlsanity.com/paper/1905.13043/) (2019)
- [Mirror Natural Evolution Strategies](https://mlsanity.com/paper/1910.11490/) (2019)
- [Zeroth-Order Randomized Subspace Newton Methods](https://mlsanity.com/paper/2202.04612/) (2022)

## Built on by (most cited first, 2 of 2)

- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)
- [Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotion](https://mlsanity.com/paper/2601.20422/) (2026)

## Abstract (arXiv)

Zeroth-order optimization addresses problems where gradient information is inaccessible or impractical to compute. While most existing methods rely on first-order approximations, incorporating second-order (curvature) information can, in principle, significantly accelerate convergence. However, the high cost of function evaluations required to estimate Hessian matrices often limits practical applicability. We present the subspace-based approximate Hessian (ZO-SAH) method, a zeroth-order optimization algorithm that mitigates these costs by focusing on randomly selected two-dimensional subspaces. Within each subspace, ZO-SAH estimates the Hessian by fitting a quadratic polynomial to the objective function and extracting its second-order coefficients. To further reduce function-query costs, ZO-SAH employs a periodic subspace-switching strategy that reuses function evaluations across optimization steps. Experiments on eight benchmark datasets, including logistic regression and deep neural network training tasks, demonstrate that ZO-SAH achieves significantly faster convergence than existing zeroth-order methods.