Demystifying Why Local Aggregation Helps: Convergence Analysis of Hierarchical SGD

arXiv:2010.12998v4 Announce Type: replace
Abstract: Hierarchical SGD (H-SGD) has emerged as a new distributed SGD algorithm for multi-level communication networks. In H-SGD, before each global aggregation, workers send their updated local models to local servers for aggregations. Despite recent research efforts, the effect of local aggregation on global convergence still lacks theoretical understanding. In this work, we first introduce a new notion of "upward" and "downward" divergences. We then use it to conduct a novel analysis to obtain a worst-case …

abstract aggregation algorithm analysis arxiv communication convergence cs.dc cs.it cs.lg distributed global hierarchical math.it math.oc networks research servers type workers