TY - GEN
T1 - Tighter Theory for Local SGD on Identical and Heterogeneous Data
AU - Khaled, Ahmed
AU - Mishchenko, Konstantin
AU - Richtarik, Peter
N1 - KAUST Repository Item: Exported on 2021-09-02
PY - 2020
Y1 - 2020
N2 - We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data
regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug H “ 1, where H is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.
AB - We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data
regimes: identical and heterogeneous. In both cases, we improve the existing theory and provide values of the optimal stepsize and optimal number of local iterations. Our bounds are based on a new notion of variance that is specific to local SGD methods with different data. The tightness of our results is guaranteed by recovering known statements when we plug H “ 1, where H is the number of local steps. The empirical evidence further validates the severe impact of data heterogeneity on the performance of local SGD.
UR - http://hdl.handle.net/10754/670896
UR - https://arxiv.org/pdf/1909.04746.pdf
M3 - Conference contribution
SP - 4519
EP - 4528
BT - NeurIPS 2019 Federated Learning Workshop
ER -