  One of the key challenges in decentralized and federated learning is to
design algorithms that efficiently deal with highly heterogeneous data
distributions across agents. In this paper, we revisit the analysis of the
popular Decentralized Stochastic Gradient Descent algorithm (D-SGD) under data
heterogeneity. We exhibit the key role played by a new quantity, called
neighborhood heterogeneity, on the convergence rate of D-SGD. By coupling the
communication topology and the heterogeneity, our analysis sheds light on the
poorly understood interplay between these two concepts. We then argue that
neighborhood heterogeneity provides a natural criterion to learn data-dependent
topologies that reduce (and can even eliminate) the otherwise detrimental
effect of data heterogeneity on the convergence time of D-SGD. For the
important case of classification with label skew, we formulate the problem of
learning such a good topology as a tractable optimization problem that we solve
with a Frank-Wolfe algorithm. As illustrated over a set of simulated and
real-world experiments, our approach provides a principled way to design a
sparse topology that balances the convergence speed and the per-iteration
communication costs of D-SGD under data heterogeneity.
