# Information-Theoretic Lower Bounds for Zero-Order Stochastic Gradient Estimation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2020.

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

- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [When cheap gradients fail: the measurement cost of attacking quantum classifiers](https://mlsanity.com/paper/2607.11095/) (2026)
- [ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models](https://mlsanity.com/paper/2511.02757/) (2025)

## Abstract (arXiv)

In this paper we analyze the necessary number of samples to estimate the gradient of any multidimensional smooth (possibly non-convex) function in a zero-order stochastic oracle model. In this model, an estimator has access to noisy values of the function, in order to produce the estimate of the gradient. We also provide an analysis on the sufficient number of samples for the finite difference method, a classical technique in numerical linear algebra. For T samples and d dimensions, our information-theoretic lower bound is Omega(√d/T). We show that the finite difference method for a bounded-variance oracle has rate O(d4/3/√T) for functions with zero third and higher order derivatives. These rates are tight for Gaussian oracles. Thus, the finite difference method is not minimax optimal, and therefore there is space for the development of better gradient estimation methods.