# Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique

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

## Key facts

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

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [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)
- [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)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (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)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/1901.11503/) (2019)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [Zeroth Order Nonconvex Multi-Agent Optimization over Networks](https://mlsanity.com/paper/1710.09997/) (2017)
- [Distributed stochastic optimization with gradient tracking over strongly-connected networks](https://mlsanity.com/paper/1903.07266/) (2019)
- [An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/1802.09022/) (2018)
- [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)
- [Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization](https://mlsanity.com/paper/1407.4504/) (2014)
- [Distributed Zeroth Order Optimization Over Random Networks: A Kiefer-Wolfowitz Stochastic Approximation Approach](https://mlsanity.com/paper/1803.07844/) (2018)

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

- [Rendering Wireless Environments Useful for Gradient Estimators: A Zero-Order Stochastic Federated Learning Method](https://mlsanity.com/paper/2401.17460/) (2024)
- [Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function](https://mlsanity.com/paper/2410.05942/) (2024)

## Abstract (arXiv)

In this work, we consider a distributed multi-agent stochastic optimization problem, where each agent holds a local objective function that is smooth and convex, and that is subject to a stochastic process. The goal is for all agents to collaborate to find a common solution that optimizes the sum of these local functions. With the practical assumption that agents can only obtain noisy numerical function queries at exactly one point at a time, we extend the distributed stochastic gradient-tracking method to the bandit setting where we don't have an estimate of the gradient, and we introduce a zero-order (ZO) one-point estimate (1P-DSGT). We analyze the convergence of this novel technique for smooth and convex objectives using stochastic approximation tools, and we prove that it converges almost surely to the optimum. We then study the convergence rate for when the objectives are additionally strongly convex. We obtain a rate of O(frac1√k) after a sufficient number of iterations k > K2 which is usually optimal for techniques utilizing one-point estimators. We also provide a regret bound of O(√k), which is exceptionally good compared to the aforementioned techniques. We further illustrate the usefulness of the proposed technique using numerical experiments.