Minimax efficient finite-difference stochastic gradient estimators using black-box function evaluations

Standard approaches to stochastic gradient estimation, with only noisy black-box function evaluations, use the finite-difference method or its variants. Though natural, it is open to our knowledge whether their statistical accuracy is the best possible. This paper argues so by showing that central finite difference is a nearly minimax optimal zeroth-order gradient estimator for a suitable class of objective functions and mean squared risk, among both the class of linear estimators and the much larger class of all (nonlinear) estimators. (c) 2020 Elsevier B.V. All rights reserved.