The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
This work addresses a foundational problem in distributed optimization theory for researchers, providing new lower bounds and optimality results that clarify the limitations of current models.
The paper tackles the theoretical gap in understanding why local SGD outperforms other methods like mini-batch SGD in distributed learning with data heterogeneity, showing that existing assumptions are insufficient and proving the min-max optimality of accelerated mini-batch SGD under these conditions.
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.