  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.
