Correcting Optimizer-Induced Bias in Adaptive Zeroth-Order Optimization

Zeroth-order (ZO) optimization adapts first-order optimizers by substituting exact gradients with zeroth-order gradient estimators (ZOGEs). This plug-in approach propagates ZOGE noise through the optimizer, thereby affecting both the update direction and the states retained across iterations. We derive joint bias and covariance expansions that characterize the resulting update and state errors. These expansions separate finite-radius bias from finite sampling bias, whose leading term scales as $q^{-1}$ (where $q$ is the number of independent sampled directions), and identify a leading $q^{-1}$ covariance term. We introduce Corrected Same-Query Extrapolation (C-SQE), which reduces finite sampling bias from $\mathcal{O}(q^{-1})$ to $\mathcal{O}(q^{-2})$ while preserving the leading covariance term by extrapolating optimizer outputs from existing ZOGEs, with a rational correction extending these guarantees to constrained states. Our convergence bounds for Adam, RMSProp, regularized Muon, and R-AdaZO quantify the improved $q$-dependence of sampling bias under C-SQE while retaining the leading stochastic terms. Synthetic experiments validate the predicted bias and covariance scaling and demonstrate faster optimization across all four optimizer families, while OPT-125M soft-prompt tuning on SST-2 and COPA shows lower mean training loss across all four families on both tasks.