A Correlation-induced Finite Difference Estimator
This work addresses gradient estimation for derivative-free optimization, offering incremental improvements in efficiency for scenarios with limited samples.
The paper tackles the problem of stochastic gradient estimation via finite difference approximation by introducing a correlation-induced estimator that reduces variance and sometimes bias compared to traditional methods, with numerical results showing effectiveness in solving derivative-free optimization problems up to 100 dimensions.
Finite difference (FD) approximation is a classic approach to stochastic gradient estimation when only noisy function realizations are available. In this paper, we first provide a sample-driven method via the bootstrap technique to estimate the optimal perturbation, and then propose an efficient FD estimator based on correlated samples at the estimated optimal perturbation. Furthermore, theoretical analyses of both the perturbation estimator and the FD estimator reveal that, {\it surprisingly}, the correlation enables the proposed FD estimator to achieve a reduction in variance and, in some cases, a decrease in bias compared to the traditional optimal FD estimator. Numerical results confirm the efficiency of our estimators and align well with the theory presented, especially in scenarios with small sample sizes. Finally, we apply the estimator to solve derivative-free optimization (DFO) problems, and numerical studies show that DFO problems with 100 dimensions can be effectively solved.