# Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2024.

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

- [VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergence](https://mlsanity.com/paper/2505.13954/) (2025)

## Abstract (arXiv)

This paper investigates distributed zeroth-order optimization for smooth nonconvex problems, targeting the trade-off between convergence rate and sampling cost per zeroth-order gradient estimation in current algorithms that use either the 2-point or 2d-point gradient estimators. We propose a novel variance-reduced gradient estimator that either randomly renovates a single orthogonal direction of the true gradient or calculates the gradient estimation across all dimensions for variance correction, based on a Bernoulli distribution. Integrating this estimator with gradient tracking mechanism allows us to address the trade-off. We show that the oracle complexity of our proposed algorithm is upper bounded by O(d/ε) for smooth nonconvex functions and by O(dkappaln (1/ε)) for smooth and gradient dominated nonconvex functions, where d denotes the problem dimension and kappa is the condition number. Numerical simulations comparing our algorithm with existing methods confirm the effectiveness and efficiency of the proposed gradient estimator.