# Zeroth-Order Algorithms for Stochastic Distributed Nonconvex Optimization

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2021.

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

- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [On the Convergence of Zeroth-Order Federated Tuning for Large Language Models](https://mlsanity.com/paper/2402.05926/) (2024)
- [Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuning](https://mlsanity.com/paper/2402.07818/) (2024)
- [When Foresight Pruning Meets Zeroth-Order Optimization: Efficient Federated Learning for Low-Memory Devices](https://mlsanity.com/paper/2405.04765/) (2024)
- [Federated Sketching LoRA: A Flexible Framework for Heterogeneous Collaborative Fine-Tuning of LLMs](https://mlsanity.com/paper/2501.19389/) (2025)
- [Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient](https://mlsanity.com/paper/2405.17761/) (2024)
- [Federated Learning on Riemannian Manifolds: A Gradient-Free Projection-Based Approach](https://mlsanity.com/paper/2507.22855/) (2025)
- [SeedFlood: A Step Toward Scalable Decentralized Fine-Tuning of LLMs](https://mlsanity.com/paper/2602.18181/) (2026)
- [HO-SFL: Hybrid-Order Split Federated Learning with Backprop-Free Clients and Dimension-Free Aggregation](https://mlsanity.com/paper/2603.14773/) (2026)
- [Communication Efficient and Privacy-Preserving Federated Learning Based on Evolution Strategies](https://mlsanity.com/paper/2311.03405/) (2023)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [Analytic Personalized Federated Meta-Learning](https://mlsanity.com/paper/2502.06915/) (2025)
- [Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotion](https://mlsanity.com/paper/2601.20422/) (2026)

## Abstract (arXiv)

In this paper, we consider a stochastic distributed nonconvex optimization problem with the cost function being distributed over n agents having access only to zeroth-order (ZO) information of the cost. This problem has various machine learning applications. As a solution, we propose two distributed ZO algorithms, in which at each iteration each agent samples the local stochastic ZO oracle at two points with a time-varying smoothing parameter. We show that the proposed algorithms achieve the linear speedup convergence rate O(√p/(nT)) for smooth cost functions under the state-dependent variance assumptions which are more general than the commonly used bounded variance and Lipschitz assumptions, and O(p/(nT)) convergence rate when the global cost function additionally satisfies the Polyak--Lojasiewicz (P--L) condition in addition, where p and T are the dimension of the decision variable and the total number of iterations, respectively. To the best of our knowledge, this is the first linear speedup result for distributed ZO algorithms, which enables systematic processing performance improvements by adding more agents. We also show that the proposed algorithms converge linearly under the relative bounded second moment assumptions and the P--L condition. We demonstrate through numerical experiments the efficiency of our algorithms on generating adversarial examples from deep neural networks in comparison with baseline and recently proposed centralized and distributed ZO algorithms.