In this paper we analyze the necessary number of samples to estimate the\ngradient of any multidimensional smooth (possibly non-convex) function in a\nzero-order stochastic oracle model. In this model, an estimator has access to\nnoisy values of the function, in order to produce the estimate of the gradient.\nWe also provide an analysis on the sufficient number of samples for the finite\ndifference method, a classical technique in numerical linear algebra. For $T$\nsamples and $d$ dimensions, our information-theoretic lower bound is\n$\\Omega(\\sqrt{d/T})$. We show that the finite difference method for a\nbounded-variance oracle has rate $O(d^{4/3}/\\sqrt{T})$ for functions with zero\nthird and higher order derivatives. These rates are tight for Gaussian oracles.\nThus, the finite difference method is not minimax optimal, and therefore there\nis space for the development of better gradient estimation methods.\n