Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization

Yujie Tang, Junshan Zhang, Na LiarXiv 2019 · DOI · arXiv

Abstract

Distributed multi-agent optimization finds many applications in distributed learning, control, estimation, etc. Most existing algorithms assume knowledge of first-order information of the objective and have been analyzed for convex problems. However, there are situations where the objective is nonconvex, and one can only evaluate the function values at finitely many points. In this paper we consider derivative-free distributed algorithms for nonconvex multi-agent optimization, based on recent progress in zero-order optimization. We develop two algorithms for different settings, provide detailed analysis of their convergence behavior, and compare them with existing centralized zero-order algorithms and gradient-based distributed algorithms.

Introduction

In modern distributed systems, such as robotic swarms, sensor networks, and large-scale machine learning, agents must often collaborate to minimize a global cost function. Traditional approaches typically rely on first-order (gradient) information. However, in many practical "black-box" scenarios—including hyperparameter tuning, complex physical simulations, or systems with constrained hardware—gradients are either unavailable or computationally prohibitive to obtain.

While zero-order (derivative-free) optimization is well-established for centralized systems, its application in distributed, multi-agent environments introduces significant challenges. Agents must reach a consensus on a global solution while only having access to their local, potentially nonconvex, function evaluations. This work addresses this gap by proposing and analyzing two distributed zero-order algorithms tailored for nonconvex landscapes.

Proposed Methods

To address the trade-off between computational efficiency and convergence speed, two distinct algorithms are developed:

  1. Algorithm 1 (2-point + DGD): This algorithm utilizes a 2-point gradient estimator, which approximates the gradient by querying the objective function at two points along a random direction. This estimator is integrated with Decentralized Gradient Descent (DGD). While computationally inexpensive per iteration, it generally exhibits slower convergence.
  2. Algorithm 2 (2d-point + Gradient Tracking): This method employs a more precise 2d-point estimator, querying the function along all $d$ dimensions (requiring $2d$ evaluations). It is paired with Gradient Tracking, a technique where agents maintain auxiliary variables to estimate the global average gradient, effectively mitigating the consensus errors inherent in standard DGD.

A critical finding of this research is the incompatibility of the cheap 2-point estimator with standard Gradient Tracking. The non-vanishing variance of the 2-point estimator interferes with the tracking mechanism, preventing the agents from reaching a stable consensus unless the number of queries per step is increased over time.

Theoretical Insights and Dimensionality

A fundamental trade-off exists regarding the dimensionality of the problem ($d$). Algorithm 1 is advantageous for high-dimensional problems where $d$ is very large, as it can make progress with only 2 queries per step. Conversely, Algorithm 2 is more efficient in the long run but requires a significant initial investment of $2d$ queries per iteration.

Furthermore, the paper explores the Polyak-Łojasiewicz (PL) condition (gradient domination). Under this condition, the proposed distributed zero-order algorithms can achieve linear convergence, closing in on the optimum at an exponential rate, which is a significant result for nonconvex optimization.

Key Results and Comparison

The theoretical convergence rates for the proposed algorithms are summarized and compared against existing first-order and centralized zero-order benchmarks in the table below.

Table 1: Comparison of convergence rates for distributed zero-order, first-order, and centralized zero-order algorithms.

Key findings include:

  • Algorithm 1 achieves a rate of $O(\sqrt{d/m} \log m)$, where $m$ is the total number of function queries, matching the performance of standard distributed gradient descent in terms of query complexity.
  • Algorithm 2 achieves a rate of $O(d/m)$ for smooth functions and linear convergence for gradient-dominated functions, matching the efficiency of centralized zero-order methods.

Numerical simulations on a synthetic 64-dimensional nonconvex problem with 50 agents confirm these rates. While Algorithm 1 initially progresses faster due to its low per-step cost, Algorithm 2 eventually achieves higher precision as its superior convergence rate overcomes the higher per-step query requirement.

Conclusion and Future Work

This work provides the first theoretical guarantees for distributed zero-order optimization in nonconvex settings. However, several avenues for future research remain. The current analysis assumes noise-free function evaluations, whereas many real-world black-box systems are stochastic. Additionally, while convergence to stationary points is proven, future work should address escaping saddle points and adapting step sizes to local network connectivity without requiring global knowledge. Finally, extending these methods to nonsmooth objective functions remains an open challenge.

Summary updated

Abstract

Distributed multi-agent optimization finds many applications in distributed learning, control, estimation, etc. Most existing algorithms assume knowledge of first-order information of the objective and have been analyzed for convex problems. However, there are situations where the objective is nonconvex, and one can only evaluate the function values at finitely many points. In this paper we consider derivative-free distributed algorithms for nonconvex multi-agent optimization, based on recent progress in zero-order optimization. We develop two algorithms for different settings, provide detailed analysis of their convergence behavior, and compare them with existing centralized zero-order algorithms and gradient-based distributed algorithms.
BibTeX
@misc{tang2019distributed,
  author = {Yujie Tang and Junshan Zhang and Na Li},
  title = {{Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization}},
  year = {2019},
  eprint = {1908.11444},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.11444},
}
Figure