Research map / Optimization / Nonconvex and smooth optimization
Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations
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.
The paper derives the perturbation distribution that minimizes the asymptotic variance of the two-point zeroth-order gradient estimator, shows directionally aligned perturbations (DAPs) are optimal alongside fixed-length ones, and tests DAPs on synthetic functions and OPT-1.3B fine-tuning on SST-2.
Problem
Zeroth-order optimization relies on two-point gradient estimators whose variance depends on the perturbation distribution; prior work mostly uses fixed-length perturbations without explaining why they are variance-optimal.
Approach
Formulates min-variance two-point estimation as a constrained functional optimization over perturbation distributions with the constraint E[vv^T]=δI, showing optima are either fixed-length or directionally aligned (|a^T v|^2 = δ||a||^2), and proposes a sampling scheme (Algorithm 1) for DAPs.
Key results
- Theorem 2.2 gives a sharp bound on E[a^T(vv^T)^2 a] under E[vv^T]=δI, with equality for fixed-length or directionally aligned perturbations; Gaussian perturbations are shown not to be minimum-variance (kurtosis d^2+2d).
- On synthetic quadratic and product functions (d=16), DAP with exact gradient gives lower tau-MSE than uniform and Gaussian perturbations.
- Fine-tuning OPT-1.3b on SST-2 with DAPs reaches higher accuracy than Gaussian and uniform perturbations at batch size 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DAP instead of classical random perturbations | Gradient estimation on the quadratic synthetic function · Quadratic synthetic function | τ-MSE | Helped |
| Use DAP instead of classical random perturbations | Gradient estimation on the product synthetic function · Product synthetic function | τ-MSE | Helped |
| Estimate the gradient first and use it to generate DAP samples | DAP gradient estimation on the quadratic synthetic function · Quadratic synthetic function | τ-MSE | Helped |
| Use DAP instead of other random perturbation methods | OPT-1.3b zeroth-order fine-tuning · SST-2 | accuracy | Helped |
Surprising findings
- Gaussian perturbations are not variance-minimizing because their fourth moment exceeds the minimum, despite their popularity.
Limitations
- The DAP condition requires the true gradient, which is unknown in practice; the practical sampler relies on an estimated gradient.
- Necessity of the minimum-variance conditions is not established in general.
- Convergence bounds depend on the fourth moment and the 1/delta scale; the empirical study is limited to small experiments.
Experimental setup
Datasets: SST-2 synthetic quadratic function synthetic product function
Benchmarks: SST-2
Metrics: tau-effective mean-square error gradient estimation error accuracy
Baselines: Gaussian perturbation uniform sphere perturbation MeZO
Builds on: MeZO Gaussian smoothing (Nesterov & Spokoiny) Duchi et al. 2015 zeroth-order analysis Khaled & Richtárik 2022 Mishchenko et al. 2020
Closest papers by meaning
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.90)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.90)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.89)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · similarity 0.89)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.88)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.88)
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.