acceptodds
Under review as a conference paper at ICLR 2027

Correcting Optimizer-Induced Bias in Adaptive Zeroth-Order Optimization

Abstract

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 (where is the number of independent sampled directions), and identify a leading covariance term. We introduce Corrected Same-Query Extrapolation (C-SQE), which reduces finite sampling bias from to 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 -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.

Primary area:
optimization
Keywords:
Zeroth-order Optimization, adaptive optimization, optimizer-induced bias, bias correction, same-query extrapolation.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_kG7DOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies "plug-in" adaptive ZO optimization, where zeroth-order gradient estimators (ZOGEs) are naively substituted into adaptive first-order optimizers (Adam, RMSProp, regularized Muon, R-AdaZO). The authors argue this naive substitution is problematic: the estimation noise propagates not only into the current update direction but also into the optimizer's persistent states (e.g. second-moment EMAs), creating a systematic optimizer-induced bias that standard ZO analysis ignores.

They derive joint bias/covariance expansions for the plug-in transition, separating finite-radius smoothing bias from finite-sampling bias, showing the leading sampling-bias term scales as O(q−1)O(q^{-1}). They then propose C-SQE (Corrected Same-Query Extrapolation): partition the qq queries into two balanced halves, form half-sample estimates, and apply a Richardson-style extrapolated transition TC=Pt(2Tt(g^q)−12∑jTt(g^j))T^C=P_t(2T_t(\hat g_{q}) - \tfrac12\sum_j T_t(\hat g_j)), with a rational correction keeping Adam-style second moments nonnegative. This reduces sampling bias to O(q−2)O(q^{-2}) while reusing the same queries (no extra budget) and preserving the leading covariance (Thm 4.1). Convergence theory (Thm 4.2, Cor 4.2) shows the residual update-bias contribution improves from q−2→q−4q^{-2}\to q^{-4} (R-AdaZO: γ4/q2→γ6/q4\gamma^4/q^2 \to \gamma^6/q^4). Synthetic and a LLM soft-prompt fine-tuning experiments show C-SQE's advantage against simple plug-in optimizers.

Critical strengths
  1. A genuinely overlooked problem, cleanly formalized. The observation that ZO noise contaminates persistent optimizer state (not just the step) is correct and under-appreciated; the joint bias/covariance expansion separating radius-bias from sampling-bias is a principled contribution, and the "same-query" extrapolation is an elegant, budget-neutral correction (no extra forward evals).

  2. Broad, optimizer-agnostic framing with matching theory. The analysis and C-SQE construction cover Adam/RMSProp/regularized Muon/R-AdaZO under one transition-map abstraction, and the synthetic experiments cleanly confirm the predicted q−1→q−2q^{-1}\to q^{-2} bias-slope improvement, which is convincing evidence that the mechanism is real.

Critical weaknesses
  1. C-SQE corrects only the bias, but the leading variance problem is left uncorrected, and this is exactly what dominates in the deployed regime. The paper's own expansions show the leading covariance term is O(q−1)O(q^{-1}) and is explicitly preserved by C-SQE. The correction only moves the (sub-leading) sampling bias from q−1q^{-1} to q−2q^{-2}, and the convergence gains (q−2→q−4q^{-2}\to q^{-4}, γ4/q2→γ6/q4\gamma^4/q^2\to\gamma^6/q^4) are improvements to high-order terms. At small qq, especially the LLM experiments using q=2q{=}2, variance overwhelmingly dominates the total error, so the asymptotic bias-order improvement that the theory celebrates is largely irrelevant precisely where ZO is actually used. This is a fundamental tension between where the theory bites (large qq) and where ZO lives (small qq).
  2. The real-model evidence is narrow and partly within noise, leaving practical significance unestablished. The only LLM experiment is 64-dim soft-prompt tuning on a frozen OPT-125M with q=2q=2 and 3 seeds and the model backbone is never actually optimized, so this is a 64-parameter problem, not LLM fine-tuning in any meaningful sense. The convincing results are synthetic with huge qq; the regime that matters is demonstrated only on a toy-scale, partly-negative setup.
Questions for authors

Please see weaknesses.

  1. Could you report, at the deployed q=2q{=}2 (when qq small), the empirical split of total MSE into bias vs variance for plug-in vs C-SQE? The core question is whether the bias reduction is even measurable when the variance dominates.
  2. Any result where actual model weights (not a 64-dim prompt) are updated, e.g. MeZO-style full/LoRA fine-tuning ,even on a small model (like OPT125M)? Does the state-bias correction still help once dd is large?
  3. Given variance is the leading term, did you consider control-variate / antithetic sampling combined with C-SQE, and would that be the more impactful contribution?
Reviewer_k1HyOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the bias introduced when noisy zeroth-order gradient estimates pass through nonlinear optimizer transitions. It derives conditional bias and covariance expansions for the joint update and next state. C-SQE combines transitions evaluated on the full sample and two complementary halves to cancel the leading inverse-query-count bias. A rational correction keeps extrapolated second moments nonnegative. The analysis covers stabilized adaptive optimizers and a regularized Muon transition.

Experiments measure transition errors on a quadratic objective, compare optimization on four synthetic functions, and evaluate soft-prompt tuning on SST-2 and COPA. The largest language model is frozen OPT-125M, with only 64 intrinsic parameters optimized. The reported application results improve mean training loss across all four optimizer families, but their scale, mechanism attribution, and accuracy reporting leave important questions unresolved.

Critical strengths
  1. Analyzing the update and retained state jointly is useful. Correcting a nonlinear update alone need not address errors carried into later iterations. The rational second-moment rule provides a concrete way to retain feasible states, and the paper explicitly identifies the strict-positivity condition needed for its local state-accuracy guarantee.

  2. Reusing directional estimates makes the correction economical in function queries. The paired experiments share directions and initializations, and the appendix reports runtime as well as query counts. The quadratic diagnostics test bias and covariance separately. These are useful controls, even though their query counts and frozen states differ substantially from the application setting.

Critical weaknesses
  1. The model scale and independent data volume are far too limited to establish practical relevance. The only model is frozen OPT-125M; the optimizer changes just 64 coefficients in a prompt subspace, with an 8-by-8 Muon matrix. SST-2 and COPA use only 1,000 and 320 training examples. The 20,000 steps repeatedly revisit these datasets; neither 320,000 sample presentations nor 80,000 mini-batch queries provides broader independent data coverage. Exact tokens are unreported. These settings establish neither scalability nor usefulness for substantial LLM adaptation. Moreover, bias diagnostics at q = 64–512 do not validate finite-sample behavior at the application’s q = 2, and update-only/state-only controls are missing.

  2. The accuracy table does not reconcile with the stated evaluation sizes. With 80 COPA examples and three seeds, mean example accuracy must lie on a grid of approximately 0.4167 percentage points. Reported values such as 61.330% and 64.670% do not. SST-2’s 500 examples imply increments of approximately 0.0667 points, also incompatible with entries such as 76.610% and 78.820% at the reported precision. Undocumented filtering or aggregation could explain this, but actual denominators and per-seed counts are needed before the main application evidence can be assessed reliably. This discrepancy alone does not establish fabrication.

Questions for authors
  1. Does the actual correction remain beneficial on substantially larger models, trainable spaces, and independent datasets? Please report processed tokens, matched-query performance and overhead, and update-only/state-only controls against separately tuned baselines.

  2. What post-filtering test sizes, integer correct counts, and aggregation rules produced Table 2? Please reconcile them with the stated 500/80-example protocol and provide per-seed evaluation records.

Reviewer_oE2ROpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies optimizer-induced bias in adaptive zeroth-order optimization. It proposes C-SQE, which combines full- and half-sample optimizer outputs with a nonnegative-state correction. The proposed method reduces sampling bias from O(q−1)O(q^{-1}) to O(q−2)O(q^{-2}) while preserving leading-order covariance without additional function queries. The authors also derive convergence bounds for four optimizer families and validate the method through synthetic experiments and OPT-125M soft-prompt tuning on SST-2 and COPA, reporting lower training losses and mostly improved test accuracy.

Critical strengths
  1. The paper jointly analyzes optimizer updates and persistent states, offering a useful perspective on how gradient-estimation noise affects adaptive optimization.

  2. The proposed C-SQE reuses existing function evaluations and supports several optimizer families, making it a potentially practical addition to existing methods.

  3. Experiments on synthetic optimization and OPT-125M show the effectiveness of the proposed method.

Critical weaknesses
  1. The experiments do not clearly separate the contributions of update correction and retained-state correction. Since these modifications can also change subsequent update magnitudes, it is difficult to determine whether the observed gains specifically support the proposed bias-correction mechanism. The author should add ablation experiments for these two components.
Questions for authors
  1. What does “Its stabilizer is outside the square root; the analyzed transition in (5) places it inside.” mean in Appendix C.3? Does this mean that the setups for the experiment and the theory part are different?

  2. On COPA in Table 2, C-SQE lowers mean training loss across all four optimizers. Could the authors explain why this translates into larger test-accuracy gains for RMSProp and Muon, only a marginal gain for R-AdaZO, and a slight decline for AdaMM?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.