Research map / Optimization / Optimizers
Refining Adaptive Zeroth-Order Optimization at Ease
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.
Proposes Refined Adaptive ZO optimization (AdaZO-style variant of ZO-AdaMM) that exploits first-moment variance reduction and builds the second moment from the squared first moment, with a variance-aware convergence analysis and experiments on synthetic functions, black-box attacks, and OPT LLM fine-tuning.
Problem
Adaptive zeroth-order optimization underutilizes moment information, and noisy function-evaluation gradient estimates lead to suboptimal convergence of methods like ZO-AdaMM.
Approach
Exploit the variance reduction of the first moment (momentum) on ZO gradient estimates and use the squared first moment, rather than the squared noisy gradient, to update the second moment, yielding a one-line change to ZO-AdaMM.
Key results
- On black-box adversarial attack, the proposed method needs 2.9k iterations versus 15.5k for ZO-AdaMM, a 5.4x speedup.
- On OPT-1.3B with SST-2, the method reaches the same training loss 4.29x faster than baselines; 3.75x on OPT-13B.
- Theory shows the second-moment variance term is reduced by a factor of (1-beta1)/(1+beta1) relative to ZO-AdaMM, giving a convergence speedup of order the fourth root of (1+beta1)/(1-beta1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the refined second moment based on squared first-moment estimates instead of squared noisy gradients | Adaptive ZO optimizers · Synthetic functions | convergence speed | Helped |
| Use the refined second moment based on squared first-moment estimates instead of squared noisy gradients | ZO-AdaMM · MNIST black-box adversarial attack | # Iters (× 10^3): 15.5±4.1 -> 2.9±0.8 | Helped |
| Use the refined second moment based on squared first-moment estimates instead of squared noisy gradients | Adaptive ZO optimizers · SST-2, OPT-1.3B | speedup to same training loss: 4.29× | Helped |
| Use the refined second moment based on squared first-moment estimates instead of squared noisy gradients | Adaptive ZO optimizers · SST-2, OPT-13B | speedup to same training loss: 3.75× | Helped |
| Replace the standard second-moment estimate with the refined estimate (ablation) | ZO-AdaMM · Quadratic function | relative error of second-moment estimate | Helped |
| Add first-moment averaging to the ZO gradient estimate (ablation) | Adaptive ZO optimization · Quadratic function | cosine similarity to true gradient | Helped |
| Increase β1 in the first-moment estimate (ablation) | Refined Adaptive ZO Optimization · Quadratic function | cosine similarity to true gradient | Mixed |
| Increase β1 in the refined second-moment estimate (ablation) | Refined Adaptive ZO Optimization · Quadratic function | relative error of second-moment estimate | Helped |
| Increase β1 (ablation) | Refined Adaptive ZO Optimization · SST-2, OPT-1.3B | convergence | Helped |
| Replace the first-moment update with the raw estimated gradient (ablation) | Adaptive ZO optimization · Synthetic functions | convergence speed | No clear effect |
| Use ZO-AdaMM instead of RMSProp | Adaptive ZO optimization · MNIST black-box adversarial attack | # Iters (× 10^3): 15.6±3.2 -> 15.5±4.1 | No clear effect |
| Use RMSProp or ZO-AdaMM instead of the proposed optimizer | Adaptive ZO optimization · SST-2 fine-tuning | convergence speed | Hurt |
Surprising findings
- The first moment contributes minimally to convergence gains: ZO-AdaMM and the RMSProp-style ZO variant show nearly identical curves, so gains come from the refined second moment.
Limitations
- Analysis relies on coordinate-wise Lipschitz smoothness and bounded function values assumptions, and on bounds that are loose (e.g., no trade-off observed for beta1 in second moment error).
- Theoretical speedup is stated primarily when the variance dominates; bias term depends on small learning rate.
Experimental setup
Datasets: SST-2 COPA MNIST
Benchmarks: Quadratic Cubic Levy Rosenbrock SST-2 COPA MNIST black-box attack
Metrics: optimality gap training loss number of iterations to successful attack speedup cosine similarity relative error
Baselines: ZO-SGD ZO-SignSGD ZO-AdaMM ZO-RMSProp
Builds on: ZO-AdaMM RMSProp Adam randomized smoothing
Closest papers by meaning
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.90)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.89)
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.89)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.89)
- ZO-AdaMU Optimizer: Adapting Perturbation by the Momentum and Uncertainty in Zeroth-Order Optimization (AAAI 2024 · similarity 0.89)
- Robust and Faster Zeroth-Order Minimax Optimization: Complexity and Applications (NeurIPS 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.