Multi-Level Local SGD for Heterogeneous Hierarchical Networks
This work addresses distributed learning in hierarchical networks with varying node speeds, offering an incremental improvement over existing methods for such settings.
The paper tackles the problem of distributed gradient descent in heterogeneous multi-level networks by proposing Multi-Level Local SGD, which achieves convergence with error dependent on network heterogeneity and topology, as demonstrated through theoretical analysis and simulations.
We propose Multi-Level Local SGD, a distributed gradient method for learning a smooth, non-convex objective in a heterogeneous multi-level network. Our network model consists of a set of disjoint sub-networks, with a single hub and multiple worker nodes; further, worker nodes may have different operating rates. The hubs exchange information with one another via a connected, but not necessarily complete communication network. In our algorithm, sub-networks execute a distributed SGD algorithm, using a hub-and-spoke paradigm, and the hubs periodically average their models with neighboring hubs. We first provide a unified mathematical framework that describes the Multi-Level Local SGD algorithm. We then present a theoretical analysis of the algorithm; our analysis shows the dependence of the convergence error on the worker node heterogeneity, hub network topology, and the number of local, sub-network, and global iterations. We back up our theoretical results via simulation-based experiments using both convex and non-convex objectives.