# Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 51 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Builds on (most cited first, 30 of 31)

- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [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)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models](https://mlsanity.com/paper/2404.08080/) (2024)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [Zeroth-Order Fine-Tuning of LLMs with Extreme Sparsity](https://mlsanity.com/paper/2406.02913/) (2024)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Zeroth order optimization with orthogonal random directions](https://mlsanity.com/paper/2107.03941/) (2021)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [A One-bit, Comparison-Based Gradient Estimator](https://mlsanity.com/paper/2010.02479/) (2020)
- [Towards Gradient Free and Projection Free Stochastic Optimization](https://mlsanity.com/paper/1810.03233/) (2018)
- [Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization](https://mlsanity.com/paper/2406.14095/) (2024)
- [An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization](https://mlsanity.com/paper/2305.16024/) (2023)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)

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

- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [Private Zeroth-Order Optimization with Public Data](https://mlsanity.com/paper/2511.10859/) (2025)
- [HO-SFL: Hybrid-Order Split Federated Learning with Backprop-Free Clients and Dimension-Free Aggregation](https://mlsanity.com/paper/2603.14773/) (2026)
- [Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective](https://mlsanity.com/paper/2605.03373/) (2026)
- [ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models](https://mlsanity.com/paper/2511.02757/) (2025)
- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)
- [ZorBA: Zeroth-order Federated Fine-tuning of LLMs with Heterogeneous Block Activation](https://mlsanity.com/paper/2603.04436/) (2026)
- [GRZO: Group-Relative Zeroth-Order Optimization for Large Language Model Fine-Tuning](https://mlsanity.com/paper/2606.02857/) (2026)
- [Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning](https://mlsanity.com/paper/2606.14970/) (2026)
- [Sample-Adaptive Zeroth-Order Post-Training](https://mlsanity.com/paper/2610.12566/) (2026)
- [StructZO: Structured Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning](https://mlsanity.com/paper/2610.16451/) (2026)

## Abstract (arXiv)

In this paper, we explore the two-point zeroth-order gradient estimator and identify the distribution of random perturbations that minimizes the estimator's asymptotic variance as the perturbation stepsize tends to zero. We formulate it as a constrained functional optimization problem over the space of perturbation distributions. Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length. While existing research has largely focused on fixed-length perturbations, the potential advantages of directional alignment have been overlooked. To address this gap, we delve into the theoretical and empirical properties of the directionally aligned perturbation (DAP) scheme, which adaptively offers higher accuracy along critical directions. Additionally, we provide a convergence analysis for stochastic gradient descent using δ-unbiased random perturbations, extending existing complexity bounds to a wider range of perturbations. Through empirical evaluations on both synthetic problems and practical tasks, we demonstrate that DAPs outperform traditional methods under specific conditions.