Research map / Optimization / Optimizers
On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Constructs a family of unbiased zeroth-order gradient estimators from a telescoping series of finite differences with random stepsize index, giving P1-P4 estimators, optimal stepsize/sampling distributions, and SGD complexity O(d/eps^4).
Problem
Zeroth-order gradient estimators based on finite differences are biased unless the perturbation stepsize vanishes; the question is whether unbiased estimators using only function evaluations can be built with favorable variance.
Approach
Express the directional derivative as a telescoping series over perturbation stepsizes mu_n, interpret it as an expectation over a random index n ~ p_n (under absolute convergence), and build unbiased estimators P1-P4 with k function evaluations; derive variance-optimal mu_n and p_n (with mu_n = mu_1 P(N>=n)).
Key results
- Zipf's P3 estimator achieves consistently lower gradient-estimation MSE than Gaussian/uniform two-point and centralized two-point estimators on quadratic and logistic losses.
- On OPT-1.3B SST-2 fine-tuning, unbiased Zipf's and geometric P3/P4 estimators converge faster per function evaluation than two-point baselines.
- SGD with the proposed estimators attains O(d/eps^4) query complexity for smooth non-convex objectives, matching the known lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Zipf’s P3 estimator instead of the two-point baselines | Gradient estimation for quadratic regression and logistic classification losses · Synthetic regression and classification | MSE | Helped |
| Use the proposed unbiased estimators instead of baseline zeroth-order estimators | OPT-1.3B fine-tuning · SST-2 | training loss convergence | Helped |
| Use the proposed unbiased estimators instead of baseline zeroth-order methods | OPT-1.3B fine-tuning · SST-2 | final accuracy | Helped |
| Reduce the estimator from P4 to P3 using random selection between estimator pathways (ablation) | Unbiased zeroth-order gradient estimation · Variance analysis | variance | Hurt |
| Use the P1 estimator, which uses a single function evaluation (ablation) | Unbiased zeroth-order gradient estimation · Conditions with positive-definite Hessian and nonzero function value | variance: +∞ | Hurt |
| Use larger two-point-estimator batch sizes | Zeroth-order optimization · OPT-1.3B fine-tuning on SST-2 | training loss per update | Helped |
Surprising findings
- The P1 single-evaluation unbiased estimator can have infinite variance under positive-definite Hessian conditions, so the minimal-evaluation unbiased construction is not usable for SGD.
Limitations
- Variance scales as d^3 mu^2 in the noiseless setting, worse than some biased estimators' d^2 mu^2.
- P1 estimator has infinite variance under certain conditions, so only P2-P4 are usable.
- Experiments are limited to a single LLM (OPT-1.3B) and one task (SST-2).
Experimental setup
Datasets: SST-2 synthetic quadratic and logistic losses
Benchmarks: SST-2
Metrics: MSE of gradient estimate training loss
Baselines: two-point estimator (Gaussian) two-point estimator (uniform) centralized two-point estimator MeZO Adam SGD
Builds on: two-point estimator MeZO forward gradient
Closest papers by meaning
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.90)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.89)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.88)
- Zeroth-Order Optimization Finds Flat Minima (NeurIPS 2025 · similarity 0.88)
- Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.