# Distributed Randomized Gradient-Free Mirror Descent Algorithm for Constrained Optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2019.

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

- [Distributed Gradient Descent for Functional Learning](https://mlsanity.com/paper/2305.07408/) (2023)
- [Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method](https://mlsanity.com/paper/2103.12954/) (2021)
- [Decision-BADGE: Decision-based Adversarial Batch Attack with Directional Gradient Estimation](https://mlsanity.com/paper/2303.04980/) (2023)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [Theory of Decentralized Robust Kernel-Based Learning](https://mlsanity.com/paper/2506.05215/) (2025)

## Abstract (arXiv)

This paper is concerned with multi-agent optimization problem. A distributed randomized gradient-free mirror descent (DRGFMD) method is developed by introducing a randomized gradient-free oracle in the mirror descent scheme where the non-Euclidean Bregman divergence is used. The classical gradient descent method is generalized without using subgradient information of objective functions. The proposed algorithm is the first distributed non-Euclidean zeroth-order method which achieves an O(1/√T) convergence rate, recovering the best known optimal rate of distributed compact constrained convex optimization. Also, the DRGFMD algorithm achieves an O(ln T/T) convergence rate for the strongly convex constrained optimization case. The rate matches the best known non-compact constraint result. Moreover, a decentralized reciprocal weighted average approximating sequence is investigated and first used in distributed algorithm. A class of convergence rates are also achieved for the algorithm with weighted averaging (DRGFMD-WA). The technique on constructing the decentralized weighted average sequence provides new insight in searching for minimizers in distributed algorithms.