# Stochastic Zeroth-order Optimization via Variance Reduction method

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

## Key facts

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

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

- [VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergence](https://mlsanity.com/paper/2505.13954/) (2025)
- [Learning Sampling Policy for Faster Derivative Free Optimization](https://mlsanity.com/paper/2104.04405/) (2021)
- [BOND: License to Train with Black-Box Functions](https://mlsanity.com/paper/2510.25074/) (2025)
- [New Hybrid Fine-Tuning Paradigm for LLMs: Algorithm Design and Convergence Analysis Framework](https://mlsanity.com/paper/2604.09940/) (2026)
- [ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization](https://mlsanity.com/paper/2609.27199/) (2026)

## Abstract (arXiv)

Derivative-free optimization has become an important technique used in machine learning for optimizing black-box models. To conduct updates without explicitly computing gradient, most current approaches iteratively sample a random search direction from Gaussian distribution and compute the estimated gradient along that direction. However, due to the variance in the search direction, the convergence rates and query complexities of existing methods suffer from a factor of d, where d is the problem dimension. In this paper, we introduce a novel Stochastic Zeroth-order method with Variance Reduction under Gaussian smoothing (SZVR-G) and establish the complexity for optimizing non-convex problems. With variance reduction on both sample space and search space, the complexity of our algorithm is sublinear to d and is strictly better than current approaches, in both smooth and non-smooth cases. Moreover, we extend the proposed method to the mini-batch version. Our experimental results demonstrate the superior performance of the proposed method over existing derivative-free optimization techniques. Furthermore, we successfully apply our method to conduct a universal black-box attack to deep neural networks and present some interesting results.