Unbiased Gradient Simulation for Zeroth-Order Optimization

We apply the Multi-Level Monte Carlo technique to get an unbiased estimator for the gradient of an optimization function. This procedure requires four exact or noisy function evaluations and produces an unbiased estimator for the gradient at one point. We apply this estimator to a non-convex stochastic programming problem. Under mild assumptions, our algorithm achieves a complexity bound independent of the dimension, compared with the typical one that grows linearly with the dimension.