# Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 8 Oct 2024.

## Builds on (most cited first, 16 of 16)

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Distributed stochastic optimization with gradient tracking over strongly-connected networks](https://mlsanity.com/paper/1903.07266/) (2019)
- [A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks](https://mlsanity.com/paper/2003.13980/) (2020)
- [Distributed stochastic gradient tracking algorithm with variance reduction for non-convex optimization](https://mlsanity.com/paper/2106.14479/) (2021)
- [S-DIGing: A Stochastic Gradient Tracking Algorithm for Distributed Optimization](https://mlsanity.com/paper/1910.08704/) (2019)
- [Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique](https://mlsanity.com/paper/2210.05618/) (2022)

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

- [SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM](https://mlsanity.com/paper/2609.29446/) (2026)

## Abstract (arXiv)

Zero-order (ZO) optimization is a powerful tool for dealing with realistic constraints. On the other hand, the gradient-tracking (GT) technique proved to be an efficient method for distributed optimization aiming to achieve consensus. However, it is a first-order (FO) method that requires knowledge of the gradient, which is not always possible in practice. In this work, we introduce a zero-order distributed optimization method based on a one-point estimate of the gradient tracking technique. We prove that this new technique converges with a single noisy function query at a time in the non-convex setting. We then establish a convergence rate of O(frac1√[3]K) after a number of iterations K, which competes with that of O(frac1√[4]K) of its centralized counterparts. Finally, a numerical example validates our theoretical results.