Asynchronous Distributed Optimization with Delay-free Parameters
This addresses the problem of unnecessarily slow convergence in distributed optimization for applications requiring asynchronous coordination, though it appears incremental as it builds on existing algorithms.
The paper tackles the problem of slow convergence in asynchronous distributed optimization algorithms by developing delay-free versions of Prox-DGD and DGD-ATC that converge to the fixed point set of their synchronous counterparts using step-sizes independent of delays. Numerical experiments demonstrate strong practical performance.
Existing asynchronous distributed optimization algorithms often use diminishing step-sizes that cause slow practical convergence, or use fixed step-sizes that depend on and decrease with an upper bound of the delays. Not only are such delay bounds hard to obtain in advance, but they also tend to be large and rarely attained, resulting in unnecessarily slow convergence. This paper develops asynchronous versions of two distributed algorithms, Prox-DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays. We establish convergence guarantees for convex and strongly convex problems under both partial and total asynchrony. We also show that the convergence speed of the two asynchronous methods adjusts to the actual level of asynchrony rather than being constrained by the worst-case. Numerical experiments demonstrate a strong practical performance of our asynchronous algorithms.