# Lazy Queries Can Reduce Variance in Zeroth-order Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 66 references that are in the map.
- First posted on arXiv 14 Jun 2022.

## Builds on (most cited first, 30 of 41)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [MAZE: Data-Free Model Stealing Attack Using Zeroth-Order Gradient Estimation](https://mlsanity.com/paper/2005.03161/) (2020)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [ES-MAML: Simple Hessian-Free Meta Learning](https://mlsanity.com/paper/1910.01215/) (2019)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients](https://mlsanity.com/paper/1909.07588/) (2019)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)

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

- [The Multi-Query Paradox in Zeroth-Order Optimization](https://mlsanity.com/paper/2509.15552/) (2025)
- [Communication-Efficient Zero-Order and First-Order Federated Learning Methods over Wireless Networks](https://mlsanity.com/paper/2508.08013/) (2025)

## Abstract (arXiv)

A major challenge of applying zeroth-order (ZO) methods is the high query complexity, especially when queries are costly. We propose a novel gradient estimation technique for ZO methods based on adaptive lazy queries that we term as LAZO. Different from the classic one-point or two-point gradient estimation methods, LAZO develops two alternative ways to check the usefulness of old queries from previous iterations, and then adaptively reuses them to construct the low-variance gradient estimates. We rigorously establish that through judiciously reusing the old queries, LAZO can reduce the variance of stochastic gradient estimates so that it not only saves queries per iteration but also achieves the regret bound for the symmetric two-point method. We evaluate the numerical performance of LAZO, and demonstrate the low-variance property and the performance gain of LAZO in both regret and query complexity relative to several existing ZO methods. The idea of LAZO is general, and can be applied to other variants of ZO methods.