On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization
This addresses a key limitation in stochastic optimization for scenarios where gradients are unavailable, offering a practical improvement for applications like language model fine-tuning.
The paper tackled the bias issue in zeroth-order optimization gradient estimators by proposing a novel family of unbiased estimators based on function evaluations, achieving optimal complexity for smooth non-convex objectives and demonstrating superior accuracy and convergence in experiments.
Zeroth-order optimization (ZOO) is an important framework for stochastic optimization when gradients are unavailable or expensive to compute. A potential limitation of existing ZOO methods is the bias inherent in most gradient estimators unless the perturbation stepsize vanishes. In this paper, we overcome this biasedness issue by proposing a novel family of unbiased gradient estimators based solely on function evaluations. By reformulating directional derivatives as a telescoping series and sampling from carefully designed distributions, we construct estimators that eliminate bias while maintaining favorable variance. We analyze their theoretical properties, derive optimal scaling distributions and perturbation stepsizes of four specific constructions, and prove that SGD using the proposed estimators achieves optimal complexity for smooth non-convex objectives. Experiments on synthetic tasks and language model fine-tuning confirm the superior accuracy and convergence of our approach compared to standard methods.