Tighter Theory for Local SGD on Identical and Heterogeneous Data

@InProceedings{pmlr-v108-bayoumi20a,
  title = 	 {Tighter Theory for Local SGD on Identical and Heterogeneous Data},
  author =       {Khaled, Ahmed and Mishchenko, Konstantin and Richtarik, Peter},
  booktitle = 	 {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics},
  pages = 	 {4519--4529},
  year = 	 {2020},
  editor = 	 {Chiappa, Silvia and Calandra, Roberto},
  volume = 	 {108},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {26--28 Aug},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v108/bayoumi20a/bayoumi20a.pdf},
  url = 	 {https://proceedings.mlr.press/v108/bayoumi20a.html},
  abstract = 	 {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.}
}