Paperlane

no. 13 · Wednesday 11 November 2026

Zeroth-Order Gradient Estimators under Decision-Dependent Noise

Yuya Hikima and Akiko Takeda

math.OC · v2

Abstract

We study zeroth-order optimization of a generally nonconvex optimization problem that is accessible only through a noisy black-box oracle, where the observation noise has zero mean and its distribution depends on the queried decision vector. Since the gradient of the objective function is inaccessible, various zeroth-order methods have been developed to solve the problem. However, it remains unclear how the choice of search directions affects the sample complexity of zeroth-order methods and how their algorithmic parameters should be selected. In this paper, we conduct a unified sample complexity analysis of zeroth-order methods across gradient estimators with different search directions. As a result, we show that gradient estimators that average over multiple directions, either uniformly from the unit sphere or from a Gaussian distribution, achieve the lowest sample complexity. The resulting sample-complexity bounds improve upon those of existing zeroth-order methods for nonconvex objective functions that are not bounded above. Moreover, through simulation experiments on multiple products pricing and strategic classification applications, we demonstrate the practical performance of zeroth-order methods with various gradient estimators.

comments
Accepted for publication in Computational Optimization and Applications (COAP). Author's website: https://yuya-hikima.github.io/
fields
Optimization and Control
pdf ↗ page arXiv:2510.24929 ↗