Finite Difference Gradient Approximation: To Randomize or Not?

We discuss two classes of methods of approximating gradients of noisy black box functions—the classical finite difference method and recently popular randomized finite difference methods. Despite of the popularity of the latter, we argue that it is unclear whether the randomized schemes have an advantage over the traditional methods when employed inside an optimization method. We point to theoretical and practical evidence that show that the opposite is true at least in a general optimization setting. We then pose the question of whether a particular setting exists when the advantage of the new method may be clearly shown, at least numerically. The larger underlying challenge is a development of black box optimization methods that scale well with the problem dimension.