  Local SGD is a popular optimization method in distributed learning, often
outperforming other algorithms in practice, including mini-batch SGD. Despite
this success, theoretically proving the dominance of local SGD in settings with
reasonable data heterogeneity has been difficult, creating a significant gap
between theory and practice. In this paper, we provide new lower bounds for
local SGD under existing first-order data heterogeneity assumptions, showing
that these assumptions are insufficient to prove the effectiveness of local
update steps. Furthermore, under these same assumptions, we demonstrate the
min-max optimality of accelerated mini-batch SGD, which fully resolves our
understanding of distributed optimization for several problem classes. Our
results emphasize the need for better models of data heterogeneity to
understand the effectiveness of local SGD in practice. Towards this end, we
consider higher-order smoothness and heterogeneity assumptions, providing new
upper bounds that imply the dominance of local SGD over mini-batch SGD when
data heterogeneity is low.
