Robust Fully-Asynchronous Methods for Distributed Training over General
  Architecture
Zehan Zhu Ye Tian Yan Huang Jinming Xu Shibo He
Perfect synchronization in distributed machine learning problems is
inefficient and even impossible due to the existence of latency, package losses
and stragglers. We propose a Robust Fully-Asynchronous Stochastic Gradient
Tracking method (R-FAST), where each device performs local computation and
communication at its own pace without any form of synchronization. Different
from existing asynchronous distributed algorithms, R-FAST can eliminate the
impact of data heterogeneity across devices and allow for packet losses by
employing a robust gradient tracking strategy that relies on properly designed
auxiliary variables for tracking and buffering the overall gradient vector.
More importantly, the proposed method utilizes two spanning-tree graphs for
communication so long as both share at least one common root, enabling flexible
designs in communication architectures. We show that R-FAST converges in
expectation to a neighborhood of the optimum with a geometric rate for smooth
and strongly convex objectives; and to a stationary point with a sublinear rate
for general non-convex settings. Extensive experiments demonstrate that R-FAST
runs 1.5-2 times faster than synchronous benchmark algorithms, such as
Ring-AllReduce and D-PSGD, while still achieving comparable accuracy, and
outperforms existing asynchronous SOTA algorithms, such as AD-PSGD and OSGP,
especially in the presence of stragglers.