Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning

Tomoya Murata, Taiji Suzuki

Abstract: Recently, local SGD has got much attention and been extensively studied in the distributed learning community to overcome the communication bottleneck problem. However, the superiority of local SGD to minibatch SGD only holds in quite limited situations. In this paper, we study a new local algorithm called Bias-Variance Reduced Local SGD (BVR-L-SGD) for nonconvex distributed optimization. Algorithmically, our proposed bias and variance reduced local gradient estimator fully utilizes small second-order heterogeneity of local objectives and suggests randomly picking up one of the local models instead of taking the average of them when workers are synchronized. Theoretically, under small heterogeneity of local objectives, we show that BVR-L-SGD achieves better communication complexity than both the previous non-local and local methods under mild conditions, and particularly BVR-L-SGD is the first method that breaks the barrier of communication complexity $\Theta(1/\varepsilon)$ for general nonconvex smooth objectives when the heterogeneity is small and the local computation budget is large. Numerical results are given to verify the theoretical findings and give empirical evidence of the superiority of our method.

Introduction

Federated Learning (FL) aims to train global models using data distributed across numerous decentralized edge devices, such as smartphones or IoT sensors, without centralizing the data. A primary challenge in this setting is the "communication bottleneck," where the time spent transmitting model updates over the network often exceeds the time required for local computation.

Standard approaches like Minibatch SGD require synchronization after every update, leading to significant latency. While Local SGD attempts to mitigate this by allowing devices to perform multiple local updates before syncing, it suffers from "client drift" when data is heterogeneous (non-IID). Existing solutions like SCAFFOLD attempt to correct this drift but often struggle with the complex, nonconvex landscapes of deep learning. This paper introduces BVR-L-SGD, a method designed to be provably faster and more robust across varying levels of data diversity.

The BVR-L-SGD Algorithm

Bias-Variance Reduced Local SGD (BVR-L-SGD) introduces three critical innovations to improve communication efficiency:

  1. Local Updates: Like Local SGD, it maximizes the work done per communication round by allowing multiple local steps.
  2. SARAH-style Variance Reduction: It employs a gradient estimator inspired by the SARAH algorithm. By adjusting current gradients based on a "snapshot" from the last synchronization point, it reduces both the noise (variance) and the drift (bias) inherent in local training.
  3. Random Model Selection: Contrary to the standard practice of averaging local models, BVR-L-SGD randomly selects one local model to serve as the new global model. The authors demonstrate that this strategy, when paired with their gradient estimator, better accounts for "second-order heterogeneity"—the differences in the curvature of loss functions across devices.

Experimental Setup

The algorithm was evaluated using the CIFAR-10 dataset. To simulate real-world Federated Learning environments, the researchers introduced varying levels of heterogeneity using a parameter $q$ to control class distribution among workers.

Modeling data heterogeneity with parameter $q$.

As shown in the conceptual diagram above, a low $q$ (e.g., $q=0.1$) represents nearly identical data across workers (IID), while a high $q$ (e.g., $q=0.85$) indicates that each worker primarily sees only one class, creating significant local bias.

Key Results and Discussion

BVR-L-SGD demonstrates significant theoretical and empirical advantages over existing methods:

  • Breaking Complexity Barriers: It is the first method to break the theoretical communication complexity barrier of $\Theta(1/\epsilon)$ for general nonconvex smooth objectives in settings with small data heterogeneity.
  • Superior Performance: Empirical tests on CIFAR-10 show that BVR-L-SGD consistently achieves lower training loss and higher test accuracy faster than SGD, Local SGD, SARAH, and SCAFFOLD.
  • Robustness to Heterogeneity: While the performance of methods like L-SGD and SCAFFOLD degrades as data becomes more diverse ($q$ increases), BVR-L-SGD remains remarkably stable.
Performance comparison of BVR-L-SGD against baselines across different heterogeneity levels.

Furthermore, the algorithm exhibits strong scaling properties; its communication efficiency improves as the local computation budget ($B$) increases, allowing it to better leverage powerful local hardware compared to standard SGD.

Limitations and Future Work

While BVR-L-SGD marks a significant step forward, several areas remain for future exploration. The current theoretical guarantees focus on finding first-order stationary points (where the gradient is zero); extending this to guarantee the avoidance of saddle points (second-order stationarity) is an open challenge. Additionally, the analysis assumes loss function smoothness, which may not perfectly align with all modern neural network architectures (e.g., those using ReLU). Finally, like other variance-reduction techniques, BVR-L-SGD requires careful tuning of hyperparameters such as the learning rate and inner loop length to achieve optimal results.

Summary updated

Abstract

Recently, local SGD has got much attention and been extensively studied in the distributed learning community to overcome the communication bottleneck problem. However, the superiority of local SGD to minibatch SGD only holds in quite limited situations. In this paper, we study a new local algorithm called Bias-Variance Reduced Local SGD (BVR-L-SGD) for nonconvex distributed optimization. Algorithmically, our proposed bias and variance reduced local gradient estimator fully utilizes small second-order heterogeneity of local objectives and suggests randomly picking up one of the local models instead of taking the average of them when workers are synchronized. Theoretically, under small heterogeneity of local objectives, we show that BVR-L-SGD achieves better communication complexity than both the previous non-local and local methods under mild conditions, and particularly BVR-L-SGD is the first method that breaks the barrier of communication complexity $\Theta(1/\varepsilon)$ for general nonconvex smooth objectives when the heterogeneity is small and the local computation budget is large. Numerical results are given to verify the theoretical findings and give empirical evidence of the superiority of our method.
BibTeX
@inproceedings{murata2021bias,
  author = {Tomoya Murata and Taiji Suzuki},
  title = {{Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=a6Bn1_y1X7i},
}
Figure