Zeroth-order optimizers train a model using only forward evaluations of the loss. They never backpropagate. They estimate a gradient by nudging the weights in a random direction by a small distance, the "smoothing radius", and checking how much the loss changes. This is how MeZO fine-tunes a 30B-parameter language model on one 80GB GPU. A parallel theory literature shows that if the loss is smooth to high order, meaning its Hessian and third derivatives are also well behaved, cleverer estimators can cancel the error that comes from nudging too far. Examples include Legendre-polynomial kernels and Romberg extrapolation across several radii. In theory this gives near-first-order convergence rates. In practice, almost none of that theory has been tested on real models. Bach–Perchet, Akhavan et al. and Lobanov contain no experiments at all. Bychkov et al. test only on a synthetic 100-sample logistic regression. The one real-model test, Romberg-ZOGE on OPT-1.3B, reports a baseline that looks implausibly weak next to other published numbers.
This note proposes to measure directly, on real networks, whether truncation bias is ever the error term that matters in zeroth-order fine-tuning. Truncation bias is the error from the radius being too large for a straight-line approximation of the loss. The note then builds an estimator that uses higher-order extrapolation only when the measurements say it helps. The central claim can be tested, and it could fail. Higher-order estimators should help in exactly one regime: when evaluation noise, such as low-precision arithmetic, quantized weights, or sampling noise in black-box APIs, forces the radius to be large. When the radius can be small, as in standard bf16 MeZO, a well-tuned two-point estimator should match them at equal forward-pass budget.
Why the obvious project is not enough
The obvious project is a leaderboard: run Legendre kernels, Romberg-ZOGE and MeZO on GLUE and see who wins. Romberg-ZOGE already moved in that direction. It evaluates the loss at radii $r, r/2, \dots, r/2^R$ along one shared random direction and combines the results to cancel even-order Taylor terms, shrinking bias from $O(r^2)$ to $O(r^{2R+2})$.
On OPT-1.3B prompt tuning for SST-2 it reports 91.2% accuracy and training loss 0.262, against 57.0% and 0.683 for a two-point Gaussian baseline. Yet Zhang et al.'s zeroth-order benchmark reports 90.83% on SST-2 with plain ZO-SGD (MeZO) on the same OPT-1.3B model. The two numbers come from different setups: prompt tuning versus full-parameter tuning. So this does not prove the Dong et al. baseline was mistuned. It does mean a leaderboard alone cannot tell whether higher-order smoothness caused the gain, or whether a baseline with a poorly chosen radius did. The contribution here is to separate those explanations with a measurement, and then turn the measurement into a method.
Core Claim
The error of any zeroth-order gradient estimate, measured against the true gradient $\nabla f$, splits roughly into three parts. Here $g_R$ is the estimate with extrapolation order $R$ ($R=0$ is ordinary central differences), $r$ is the radius, $d$ is the number of tuned parameters, $\sigma^2$ is the variance of noise in a single loss evaluation, and $C_R$ depends on derivatives of order $2R+3$:
$$ \mathbb{E}\|g_R - \nabla f\|^2 \;\approx\; C_R^2\, r^{4R+4} \;+\; \kappa_R\, \frac{d\,\sigma^2}{r^2} \;+\; V_{\mathrm{dir}} . $$
The first term is the squared truncation bias, following the $O(r^{2R+2})$ bias of the extrapolated central difference. The second is evaluation noise divided by the radius. Its amplification factor $\kappa_R$ grows with $R$, as Dong et al. note. The third, $V_{\mathrm{dir}}$, is the variance from sampling a single random direction, which is about $d$ times the squared gradient norm and does not depend on $r$ or $R$.
In billion-parameter models, $V_{\mathrm{dir}}$ is huge. When $\sigma$ is tiny, the radius can be made small enough that the bias term is negligible, and extrapolation buys nothing while paying $\kappa_R$ and extra forward passes. Extrapolation should win only when $\sigma$ is large enough that the best radius for $R=0$ leaves a bias comparable to $V_{\mathrm{dir}}$.
The shape of this prediction follows from minimizing the first two terms over $r$. It says the benefit of extrapolation should appear as a crossover in the noise level $\sigma$, not as a uniform improvement. Bychkov et al. observed a related effect in their synthetic setting: higher smoothness permits a larger radius and better tolerance to adversarial noise. We test whether that effect exists in real networks, and where it switches on.
A caveat applies. The expansion assumes the loss is smooth to order $2R+2$ within radius $r$. With GELU activations and softmax attention this is plausible. With ReLU it is not. Measuring this directly is part of the program.
Research Program
The first component is a ground-truth error audit. On OPT-1.3B and a RoBERTa-scale model, where backpropagation is affordable, we compute exact minibatch gradients. We then decompose the error of each estimator into bias and variance over a grid of radii, extrapolation orders $R \in \{0,1,2\}$, Legendre-kernel orders, and numerical regimes: fp32, bf16, and 4-bit weight quantization. We add a black-box regime in which loss evaluations carry injected sampling noise.
Bias is estimated by averaging many directions at a fixed point. Variance is the remainder. From the slope of log-bias against log-radius we read off an empirical smoothness order, which tells us whether real losses actually exhibit the $r^{2R+2}$ decay seen on Poly8 and Rosenbrock. The output is a map of where the bias term dominates, if anywhere.
The second component is the method: an adaptive Romberg estimator that needs no prior knowledge of the smoothness order $\beta$ or the noise level. This addresses the open problem flagged for Lobanov, Bychkov et al. and Dong et al.. The key observation is that the Romberg table already contains a classical a-posteriori error estimate. The difference between the level-$R$ and level-$(R-1)$ extrapolants estimates the truncation error of the lower level, and it comes at no extra cost. The repeated evaluations at the same point, which MeZO-style seed resets already make cheap, give an estimate of $\sigma$.
Each few hundred steps, the estimator compares these two running estimates. It raises $R$ or enlarges $r$ only when the estimated bias exceeds the estimated noise contribution. Otherwise it falls back to plain two-point differences and spends the saved forward passes on more directions. The design reuses Romberg-ZOGE's shared-direction construction and adds the decision rule. It does not propose a new estimator family.
The third component is a matched-budget benchmark. Every method gets the same number of forward passes, the same data, and the same hyperparameter search budget, and we report wall-clock time and peak GPU memory alongside accuracy. Prior theory papers left this Pareto comparison open, and Zhang et al. 2013 shows how iteration-count advantages can vanish once per-step cost is counted.
Baselines
The naive reference point is the pretrained model with no tuning, plus the linear-probing or zero-shot numbers each benchmark supplies. This establishes whether any zeroth-order method is doing real work.
The strongest simple competitor is MeZO (Malladi et al.): two-point perturbation with in-place seed resets, run with the public MeZO code. It matters most because it is what practitioners actually use. It matched Adam within 1% on 7 of 11 tasks with OPT-13B, and Zhang et al. report 90.83% SST-2 accuracy with it on OPT-1.3B. We give it the same radius and learning-rate grid search as every other method. At equal forward-pass budget it may average more directions per step, since it spends two evaluations where Romberg with $R=2$ spends six.
The strongest structural competitor is ZO-SGD-Block from Zhang et al.. It reports 93.69% SST-2 on OPT-1.3B, the best zeroth-order number in the file for that model. It attacks the variance term $V_{\mathrm{dir}}$ rather than the bias, so it is both a competitor and a candidate to combine with our estimator.
The strongest higher-order competitors are fixed-order Romberg-ZOGE, whose reported result is 91.2% accuracy and loss 0.262 on OPT-1.3B SST-2 prompt tuning, and a batched Legendre-kernel estimator in the style of Lobanov and Bychkov et al.. No reported real-model result was found on Lacuna for the Legendre-kernel variant, so we implement it ourselves, and running it at all closes part of the empirical gap. First-order Adam, and forward-mode gradients where memory allows, serve as ceilings.
Two ablations isolate the key ingredient. One forces $R=0$ while keeping the adaptive radius, which asks whether gains come from extrapolation or merely from radius adaptation. The other replaces the shared direction with independent directions per radius, which tests the variance-cancellation mechanism Dong et al. credit.
Beating a baseline means the following. In the high-noise regimes, higher accuracy than tuned MeZO and fixed-$R$ Romberg at equal forward passes, with non-overlapping confidence intervals over at least five seeds. In the low-noise bf16 regime, no loss relative to tuned MeZO. Across both, removing the need to hand-set $R$.
Why not just…?
Why not just tune MeZO's radius and learning rate carefully? This is the most serious threat, and the proposal is built to answer it rather than dodge it. If the audit shows the bias term is negligible at MeZO's usual radius across all numerical regimes, then tuned MeZO wins. We will report that as a negative result showing that higher-order smoothness is irrelevant for fine-tuning at current precisions. That is still a useful correction to the literature. The gap between 57.0% in Dong et al. and 90.83% in Zhang et al. is exactly why we rerun the two-point baseline on Dong et al.'s own prompt-tuning setup, with a full radius sweep.
Why not just use block-wise updates, LoRA, or sparse masks? These reduce the direction-sampling variance $V_{\mathrm{dir}}$ by shrinking the effective dimension, and Zhang et al. show block-wise updates alone add almost three points on SST-2. They do nothing about truncation bias, so the two approaches are complementary rather than competing. We therefore run the adaptive estimator on top of ZO-SGD-Block and LoRA as well as on full parameters. If the combination offers no gain over Block alone, even in the noisy regimes, variance reduction is the only lever that matters.
Why not just use forward-mode differentiation, which has no truncation bias at all? Forward gradients compute exact directional derivatives, but Zhang et al. report they need substantially more memory than pure forward evaluation. They are also unavailable in the black-box and quantized-inference settings where our hypothesis predicts extrapolation helps most. We include them as an accuracy ceiling where they fit in memory. The peak-memory column will show the price.
Why not just average more two-point estimates instead of extrapolating? Averaging reduces the noise and direction-sampling terms but leaves the bias untouched. That is precisely the difference the matched-budget comparison measures. In the injected-noise regime, the audit will show whether spending six forward passes on more directions or on more radii lowers total error more.
Proposed Experiments
The first decisive check is on synthetic ground: Poly8 and Rosenbrock, and the Bychkov et al. logistic setting with $n=100$ and $d=1000$, where AZO-SGD-HS reportedly reached error $10^{-2}$ in about 200 iterations. We inject controlled noise at increasing $\sigma$ and confirm that the accuracy advantage of $R \ge 1$ over $R=0$ appears at a crossover $\sigma$ predicted by the error decomposition. If no crossover appears even where the theory is exact, the program stops there. The 5G simulator from Dong et al. is not publicly specified in the file, so we omit it.
The second check is the real-model audit on OPT-1.3B. We measure the empirical bias exponent and the bias-to-variance ratio across fp32, bf16, 4-bit and noisy-API regimes. The hypothesis fails if bias is negligible in every regime.
The third check is end-to-end. We run SST-2, in both prompt tuning and full fine-tuning, and RTE from GLUE (Wang et al.), plus WinoGrande, where zeroth-order methods trail first-order ones by 5–6 points according to Zhang et al.. We report accuracy against forward passes, wall-clock time and peak memory for every baseline above.
The proposal succeeds if the adaptive estimator matches tuned MeZO in bf16, beats both it and fixed-order Romberg in the quantized and noisy regimes, and narrows the WinoGrande gap there. It fails informatively if tuned two-point estimation matches it everywhere.
References
- Romberg-Extrapolated Zeroth-Order Gradient Estimator: Higher-Order Bias Reduction with Preserved Leading Directional Variance
- Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark
- Accelerated Zero-Order SGD under High-Order Smoothness and Overparameterized Regime
- Improved Iteration Complexity in Black-Box Optimization Problems under Higher Order Smoothness Function Condition
- Linear Convergence with Condition Number Independent Access of Full Gradients
- Fine-Tuning Language Models with Just Forward Passes
- GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding