Asynchronous Distributed Optimization with Delay-free Parameters
Xuyang Wu Changxin Liu Sindri Magnusson Mikael Johansson
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 strongly and
weakly convex problems under both partial and total asynchrony. We also show
that the convergence speed of the two asynchronous methods adapts 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.