Distributed zeroth-order optimization: Convergence rates that match centralized counterpart

Deming Yuan, Lei Wang, Alexandre Proutière, Guodong Shi

Abstract

Zeroth-order optimization has become increasingly important in complex optimization and machine learning when cost functions are impossible to be described in closed analytical forms. The key idea of zeroth-order optimization lies in the ability for a learner to build gradient estimates by queries sent to the cost function, and then traditional gradient descent algorithms can be executed replacing gradients by the estimates. For optimization over large-scale multi-agent systems with decentralized data and costs, zeroth-order optimization can continue to be utilized to develop scalable and distributed algorithms. In this paper, we aim at understanding the trend in performance transitioning from centralized to distributed zeroth-order algorithms in terms of convergence rates, and focus on multi-agent systems with time-varying communication networks. We establish a series of convergence rates for distributed zeroth-order subgradient algorithms under both one-point and two-point zeroth-order oracles. Apart from the additional node-to-node communication cost due to the distributed nature of algorithms, the established rates in convergence are shown to match their centralized counterpart. We also propose a multi-stage distributed zeroth-order algorithm that better utilizes the learning rates, reduces the computational complexity, and attains even faster convergence rates for compact decision set.
BibTeX
@article{yuan2024distributed,
  author = {Deming Yuan and Lei Wang and Alexandre Proutière and Guodong Shi},
  title = {{Distributed zeroth-order optimization: Convergence rates that match centralized counterpart}},
  journal = {Automatica},
  year = {2024},
  doi = {10.1016/j.automatica.2023.111328},
}

Loading related content...

Figure