# Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization

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

## Key facts

- Cited by 111 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2018.

## Built on by (most cited first, 30 of 111)

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [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)
- [BlackVIP: Black-Box Visual Prompting for Robust Transfer Learning](https://mlsanity.com/paper/2303.14773/) (2023)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytes](https://mlsanity.com/paper/2312.06353/) (2023)
- [Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2402.15751/) (2024)
- [Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models](https://mlsanity.com/paper/2404.08080/) (2024)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/2203.14195/) (2022)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Zeroth-Order Fine-Tuning of LLMs in Random Subspaces](https://mlsanity.com/paper/2410.08989/) (2024)
- [AdaZeta: Adaptive Zeroth-Order Tensor-Train Adaption for Memory-Efficient Large Language Models Fine-Tuning](https://mlsanity.com/paper/2406.18060/) (2024)
- [ZARTS: On Zero-order Optimization for Neural Architecture Search](https://mlsanity.com/paper/2110.04743/) (2021)
- [Harmony in Divergence: Towards Fast, Accurate, and Memory-efficient Zeroth-order LLM Fine-tuning](https://mlsanity.com/paper/2502.03304/) (2025)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Evading Black-box Classifiers Without Breaking Eggs](https://mlsanity.com/paper/2306.02895/) (2023)
- [Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization](https://mlsanity.com/paper/2405.15861/) (2024)
- [ComPO: Preference Alignment via Comparison Oracles](https://mlsanity.com/paper/2505.05465/) (2025)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [Refining Adaptive Zeroth-Order Optimization at Ease](https://mlsanity.com/paper/2502.01014/) (2025)
- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [Holistic Adversarial Robustness of Deep Learning Models](https://mlsanity.com/paper/2202.07201/) (2022)
- [Certified Zeroth-order Black-Box Defense with Robust UNet Denoiser](https://mlsanity.com/paper/2304.06430/) (2023)

## Abstract (arXiv)

As application demands for zeroth-order (gradient-free) optimization accelerate, the need for variance reduced and faster converging approaches is also intensifying. This paper addresses these challenges by presenting: a) a comprehensive theoretical analysis of variance reduced zeroth-order (ZO) optimization, b) a novel variance reduced ZO algorithm, called ZO-SVRG, and c) an experimental evaluation of our approach in the context of two compelling applications, black-box chemical material classification and generation of adversarial examples from black-box deep neural network models. Our theoretical analysis uncovers an essential difficulty in the analysis of ZO-SVRG: the unbiased assumption on gradient estimates no longer holds. We prove that compared to its first-order counterpart, ZO-SVRG with a two-point random gradient estimator could suffer an additional error of order O(1/b), where b is the mini-batch size. To mitigate this error, we propose two accelerated versions of ZO-SVRG utilizing variance reduced gradient estimators, which achieve the best rate known for ZO stochastic optimization (in terms of iterations). Our extensive experimental results show that our approaches outperform other state-of-the-art ZO algorithms, and strike a balance between the convergence rate and the function query complexity.