Geometrically Convergent Distributed Optimization with Uncoordinated Step-Sizes
This work addresses a practical limitation in distributed optimization for multi-agent systems, though it is incremental as it builds on existing DIGing algorithms.
The paper tackles the problem of distributed optimization requiring identical step-sizes across agents by analyzing the Adapt-Then-Combine variation of the DIGing algorithm, showing it achieves geometric convergence with uncoordinated step-sizes and accelerates convergence compared to the original DIGing structure.
A recent algorithmic family for distributed optimization, DIGing's, have been shown to have geometric convergence over time-varying undirected/directed graphs. Nevertheless, an identical step-size for all agents is needed. In this paper, we study the convergence rates of the Adapt-Then-Combine (ATC) variation of the DIGing algorithm under uncoordinated step-sizes. We show that the ATC variation of DIGing algorithm converges geometrically fast even if the step-sizes are different among the agents. In addition, our analysis implies that the ATC structure can accelerate convergence compared to the distributed gradient descent (DGD) structure which has been used in the original DIGing algorithm.