A Canonical Form for First-Order Distributed Optimization Algorithms
For researchers designing distributed optimization algorithms, this provides a unified framework to analyze and compare algorithms, though it is an incremental theoretical contribution.
The paper introduces a canonical form that characterizes any first-order distributed optimization algorithm using a single communication round and gradient computation per iteration with up to two state variables per agent, enabling systematic analysis and design.
We consider the distributed optimization problem in which a network of agents aims to minimize the average of local functions. To solve this problem, several algorithms have recently been proposed where agents perform various combinations of communication with neighbors, local gradient computations, and updates to local state variables. In this paper, we present a canonical form that characterizes any first-order distributed algorithm that can be implemented using a single round of communication and gradient computation per iteration, and where each agent stores up to two state variables. The canonical form features a minimal set of parameters that are both unique and expressive enough to capture any distributed algorithm in this class. The generic nature of our canonical form enables the systematic analysis and design of distributed optimization algorithms.