# On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms

arXiv: https://arxiv.org/abs/2107.10110 · HTML: https://mlsanity.com/paper/2107.10110/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 21 Jul 2021.

## Builds on (most cited first, 17 of 17)

- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors](https://mlsanity.com/paper/1807.07978/) (2018)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Improving Black-box Adversarial Attacks with a Transfer-based Prior](https://mlsanity.com/paper/1906.06919/) (2019)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attacks](https://mlsanity.com/paper/1812.09803/) (2018)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [Improving Gradient Estimation in Evolutionary Strategies With Past Descent Directions](https://mlsanity.com/paper/1910.05268/) (2019)

## Built on by (most cited first, 23 of 23)

- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Fast Policy Learning for Linear Quadratic Control with Entropy Regularization](https://mlsanity.com/paper/2311.14168/) (2023)
- [Refining Adaptive Zeroth-Order Optimization at Ease](https://mlsanity.com/paper/2502.01014/) (2025)
- [Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Prior](https://mlsanity.com/paper/2405.19098/) (2024)
- [Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients](https://mlsanity.com/paper/2308.04077/) (2023)
- [Zeroth-Order Optimization is Secretly Single-Step Policy Optimization](https://mlsanity.com/paper/2506.14460/) (2025)
- [ZO2: Scalable Zeroth-Order Fine-Tuning for Extremely Large Language Models with Limited GPU Memory](https://mlsanity.com/paper/2503.12668/) (2025)
- [LORENZA: Enhancing Generalization in Low-Rank Gradient LLM Training via Efficient Zeroth-Order Adaptive SAM](https://mlsanity.com/paper/2502.19571/) (2025)
- [ZOQO: Zero-Order Quantized Optimization](https://mlsanity.com/paper/2501.06736/) (2025)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)
- [ZOTTA: Test-Time Adaptation with Gradient-Free Zeroth-Order Optimization](https://mlsanity.com/paper/2603.14254/) (2026)
- [Guided Trajectory Optimization with Sparse Scaling for Test-Time Diffusion](https://mlsanity.com/paper/2605.21907/) (2026)
- [Visualising Policy-Reward Interplay to Inform Zeroth-Order Preference Optimisation of Large Language Models](https://mlsanity.com/paper/2503.03460/) (2025)
- [Boosting Ray Search Procedure of Hard-label Attacks with Transfer-based Priors](https://mlsanity.com/paper/2507.17577/) (2025)
- [EVA-0: Test-Time Model Evolution with Only Two Forward Passes per Sample](https://mlsanity.com/paper/2605.18867/) (2026)
- [Dependency Structure Search Bayesian Optimization for Decision Making Models](https://mlsanity.com/paper/2308.00629/) (2023)
- [ProGO: Probabilistic Global Optimizer](https://mlsanity.com/paper/2310.04457/) (2023)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [Improving the Convergence Rate of Ray Search Optimization for Query-Efficient Hard-Label Attacks](https://mlsanity.com/paper/2512.21241/) (2025)
- [Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Sampling](https://mlsanity.com/paper/2602.13659/) (2026)
- [GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2608.25116/) (2026)
- [Adaptively Incorporating Directional Hints into Zeroth-Order Optimization](https://mlsanity.com/paper/2609.08277/) (2026)

## Abstract (arXiv)

Zeroth-order (ZO) optimization is widely used to handle challenging tasks, such as query-based black-box adversarial attacks and reinforcement learning. Various attempts have been made to integrate prior information into the gradient estimation procedure based on finite differences, with promising empirical results. However, their convergence properties are not well understood. This paper makes an attempt to fill up this gap by analyzing the convergence of prior-guided ZO algorithms under a greedy descent framework with various gradient estimators. We provide a convergence guarantee for the prior-guided random gradient-free (PRGF) algorithms. Moreover, to further accelerate over greedy descent methods, we present a new accelerated random search (ARS) algorithm that incorporates prior information, together with a convergence analysis. Finally, our theoretical results are confirmed by experiments on several numerical benchmarks as well as adversarial attacks.