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.

本文利用现有的一阶数据异质性假设，为本地 SGD 提供了新的下界，显示了这些假设不足以证明本地更新步骤的有效性。此外，在相同的假设下，我们证明了加速小批量 SGD 的极小 - 极大优化性质，完全解决了几个问题类的分布式优化。我们的结果强调了需要更好的数据异质性模型，以了解本地 SGD 在实践中的有效性。为此，我们考虑了高阶平滑性和异质性假设，并提供了新的上界，暗示了当数据异质性较低时，本地 SGD 优于小批量 SGD。