mlsanityData to 7 Oct 2026

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

arXiv 2107.10110 ↗First posted 21 Jul 2021stat.ML cs.LG math.OCcited by 23

Not on the map. Why?

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.

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

Builds on

17 of 33 references.

References · 17

  1. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  2. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  3. 2016Learning to learn by gradient descent by gradient descentcited by 616
  4. 2014Convex Optimization: Algorithms and Complexitycited by 569
  5. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 555
  6. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  7. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 499
  8. 2018Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priorscited by 145
  9. 2018AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networkscited by 137
  10. 2019Improving Black-box Adversarial Attacks with a Transfer-based Priorcited by 121
  11. 2019A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimizationcited by 66
  12. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
5 more
  1. 2018Guessing Smart: Biased Sampling for Efficient Black-Box Adversarial Attackscited by 46
  2. 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 42
  3. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  4. 2020A stochastic subspace approach to gradient-free optimization in high dimensionscited by 15
  5. 2019Improving Gradient Estimation in Evolutionary Strategies With Past Descent Directionscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 3; 2025: 8; 2026: 6.

23 papers.

Sort:

By area:

  1. 2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 113
  2. 2023DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Trainingcited by 76
  3. 2023Fast Policy Learning for Linear Quadratic Control with Entropy Regularizationcited by 11
  4. 2025Refining Adaptive Zeroth-Order Optimization at Easecited by 11
  5. 2024Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Priorcited by 10
  6. 2023Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradientscited by 8
  7. 2025Zeroth-Order Optimization is Secretly Single-Step Policy Optimizationcited by 7
  8. 2025ZO2: Scalable Zeroth-Order Fine-Tuning for Extremely Large Language Models with Limited GPU Memorycited by 5
  9. 2025ZOQO: Zero-Order Quantized Optimizationcited by 4
  10. 2025LORENZA: Enhancing Generalization in Low-Rank Gradient LLM Training via Efficient Zeroth-Order Adaptive SAMcited by 3
  11. 2022Lazy Queries Can Reduce Variance in Zeroth-order Optimizationcited by 2
  12. 2025Visualising Policy-Reward Interplay to Inform Zeroth-Order Preference Optimisation of Large Language Modelscited by 1
11 more
  1. 2025Boosting Ray Search Procedure of Hard-label Attacks with Transfer-based Priorscited by 1
  2. 2026ZOTTA: Test-Time Adaptation with Gradient-Free Zeroth-Order Optimizationcited by 1
  3. 2026Guided Trajectory Optimization with Sparse Scaling for Test-Time Diffusioncited by 1
  4. 2023Dependency Structure Search Bayesian Optimization for Decision Making Modelscited by 0
  5. 2023ProGO: Probabilistic Global Optimizercited by 0
  6. 2024How to Boost Any Loss Functioncited by 0
  7. 2025Improving the Convergence Rate of Ray Search Optimization for Query-Efficient Hard-Label Attackscited by 0
  8. 2026Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Samplingcited by 0
  9. 2026EVA-0: Test-Time Model Evolution with Only Two Forward Passes per Samplecited by 0
  10. 2026GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimizationcited by 0
  11. 2026Adaptively Incorporating Directional Hints into Zeroth-Order Optimizationcited by 0