Federated learning is one of the important learning scenarios in distributed learning, in which we aim at learning heterogeneous local datasets efficiently in terms of communication and computational cost. In this paper, we study new local algorithms called Bias-Variance Reduced Local SGD (BVR-L-SGD) for nonconvex federated learning. One of the novelties of this paper is in the analysis of our bias and variance reduced local gradient estimators which fully utilize small second-order heterogeneity of local objectives and suggests to randomly pick up one of the local models instead of taking average of them when workers are synchronized. Under small heterogeneity of local objectives, we show that our methods achieve smaller communication complexity than both the previous non-local and local methods for general nonconvex objectives. Furthermore, we also compare the total execution time, that is the sum of total communication time and total computational time per worker, and show the superiority of our methods to the existing methods when the heterogeneity is small and single communication time is more time consuming than single stochastic gradient computation. Numerical results are provided to verify our theoretical findings and give empirical evidence of the superiority of our algorithms.

本文介绍了一种新型的本地算法BVR-L-SGD，用于非凸分布式优化，它基于小二阶异质性的本地目标，建议在同步工作时随机选择本地模型之一而不是取其平均值，并在理论上证明了BVR-L-SGD在小异质性的本地目标下比以前的非本地和本地方法都具有更好的通信复杂度，特别是当异质性较小且本地计算预算较大时，BVR-L-SGD是打破通信复杂度Θ（1/ε）障碍的第一种方法。

减少异质性的联邦学习中的偏差-方差减小的局部 SGD