The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910452899905536 |
|---|---|
| author | Patel, Kumar Kshitij Glasgow, Margalit Zindari, Ali Wang, Lingxiao Stich, Sebastian U. Cheng, Ziheng Joshi, Nirmit Srebro, Nathan |
| author_facet | Patel, Kumar Kshitij Glasgow, Margalit Zindari, Ali Wang, Lingxiao Stich, Sebastian U. Cheng, Ziheng Joshi, Nirmit Srebro, Nathan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11667 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication Patel, Kumar Kshitij Glasgow, Margalit Zindari, Ali Wang, Lingxiao Stich, Sebastian U. Cheng, Ziheng Joshi, Nirmit Srebro, Nathan Machine Learning Distributed, Parallel, and Cluster Computing Optimization and Control 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. |
| title | The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication |
| topic | Machine Learning Distributed, Parallel, and Cluster Computing Optimization and Control |
| url | https://arxiv.org/abs/2405.11667 |