In federated distributed learning, the goal is to optimize a global training
objective defined over distributed devices, where the data shard at each device
is sampled from a possibly different distribution (a.k.a., heterogeneous or non
i.i.d. data samples). In this paper, we generalize the local stochastic and
full gradient descent with periodic averaging-- originally designed for
homogeneous distributed optimization, to solve nonconvex optimization problems
in federated learning. Although scant research is available on the
effectiveness of local SGD in reducing the number of communication rounds in
homogeneous setting, its convergence and communication complexity in
heterogeneous setting is mostly demonstrated empirically and lacks through
theoretical understating. To bridge this gap, we demonstrate that by properly
analyzing the effect of unbiased gradients and sampling schema in federated
setting, under mild assumptions, the implicit variance reduction feature of
local distributed methods generalize to heterogeneous data shards and exhibits
the best known convergence rates of homogeneous setting both in general
nonconvex and under {\pl}~ condition (generalization of strong-convexity). Our
theoretical results complement the recent empirical studies that demonstrate
the applicability of local GD/SGD to federated learning. We also specialize the
proposed local method for networked distributed optimization. To the best of
our knowledge, the obtained convergence rates are the sharpest known to date on
the convergence of local decant methods with periodic averaging for solving
nonconvex federated optimization in both centralized and networked distributed
optimization.

本文旨在研究在异构样本上进行非凸优化的联邦分布式学习，具体而言，我们将分析分布式方法相对于均匀样本中的隐含方差减少特性在异构样本中的应用，并证明其在广义的非凸和条件下的收敛性与最优性.