# A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2019.

## Built on by (most cited first, 30 of 68)

- [Do Differentiable Simulators Give Better Policy Gradients?](https://mlsanity.com/paper/2202.00817/) (2022)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Gradient Cuff: Detecting Jailbreak Attacks on Large Language Models by Exploring Refusal Loss Landscapes](https://mlsanity.com/paper/2403.00867/) (2024)
- [InverseBench: Benchmarking Plug-and-Play Diffusion Priors for Inverse Problems in Physical Sciences](https://mlsanity.com/paper/2503.11043/) (2025)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Convergence of policy gradient methods for finite-horizon exploratory linear-quadratic control problems](https://mlsanity.com/paper/2211.00617/) (2022)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [Adaptive Horizon Actor-Critic for Policy Learning in Contact-Rich Differentiable Simulation](https://mlsanity.com/paper/2405.17784/) (2024)
- [Ensemble Kalman Diffusion Guidance: A Derivative-free Method for Inverse Problems](https://mlsanity.com/paper/2409.20175/) (2024)
- [ZARTS: On Zero-order Optimization for Neural Architecture Search](https://mlsanity.com/paper/2110.04743/) (2021)
- [Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networks](https://mlsanity.com/paper/2308.09858/) (2023)
- [DNNR: Differential Nearest Neighbors Regression](https://mlsanity.com/paper/2205.08434/) (2022)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Group Distributionally Robust Dataset Distillation with Risk Minimization](https://mlsanity.com/paper/2402.04676/) (2024)
- [ZeroFlow: Overcoming Catastrophic Forgetting is Easier than You Think](https://mlsanity.com/paper/2501.01045/) (2025)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients](https://mlsanity.com/paper/2308.04077/) (2023)
- [Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2108.00473/) (2021)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [CR-Net: Scaling Parameter-Efficient Training with Cross-Layer Low-Rank Structure](https://mlsanity.com/paper/2509.18993/) (2025)
- [Ferret: Federated Full-Parameter Tuning at Scale for Large Language Models](https://mlsanity.com/paper/2409.06277/) (2024)
- [Graph Guided Diffusion: Unified Guidance for Conditional Graph Generation](https://mlsanity.com/paper/2505.19685/) (2025)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [Model Calibration of the Liquid Mercury Spallation Target using Evolutionary Neural Networks and Sparse Polynomial Expansions](https://mlsanity.com/paper/2202.09353/) (2022)
- [FedZeN: Towards superlinear zeroth-order federated learning via incremental Hessian estimation](https://mlsanity.com/paper/2309.17174/) (2023)
- [Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation](https://mlsanity.com/paper/2410.08125/) (2024)
- [Dataset Distillation from First Principles: Integrating Core Information Extraction and Purposeful Learning](https://mlsanity.com/paper/2409.01410/) (2024)
- [Branch, or Layer? Zeroth-Order Optimization for Continual Learning of Vision-Language Models](https://mlsanity.com/paper/2506.12409/) (2025)

## Abstract (arXiv)

In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing and smoothing on a sphere. The methods differ in the number of functions sampled, the choice of the sample points, and the way in which the gradient approximations are derived. For each method, we derive bounds on the number of samples and the sampling radius which guarantee favorable convergence properties for a line search or fixed step size descent method. To this end, we use the results in [Berahas et al., 2019] and show how each method can satisfy the sufficient conditions, possibly only with some sufficiently large probability at each iteration, as happens to be the case with Gaussian smoothing and smoothing on a sphere. Finally, we present numerical results evaluating the quality of the gradient approximations as well as their performance in conjunction with a line search derivative-free optimization algorithm.