Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning

Tomoya Murata, Taiji Suzuki

Federated Learning (FL) allows for the training of models across many decentralized devices (workers) without sharing raw data. However, the field faces a persistent headache: the trade-off between communication efficiency and data heterogeneity. This paper introduces a novel algorithm, BVR-L-SGD (Bias-Variance Reduced Local SGD), designed to tackle this exact problem. It stands out as the first method to theoretically break the standard $1/\epsilon$ communication complexity barrier for general nonconvex problems when data across devices is relatively similar.

The Problem: Communication Costs and Client Drift

In FL, the primary bottleneck is communication cost. Sending model updates over a network is significantly slower than performing local computations on the devices. To mitigate this, "Local SGD" (or Federated Averaging) allows workers to perform multiple local updates before synchronizing with the central server.

Unfortunately, this introduces client drift. Because each worker's data is different (heterogeneous), their local models drift toward local optima. When these divergent models are averaged, it often leads to poor global convergence. While existing methods like SCAFFOLD attempt to correct this drift, they often struggle with nonconvex objectives—such as deep neural networks—or require highly restrictive assumptions to show any theoretical advantage over simple Minibatch SGD.

The BVR-L-SGD Approach

To overcome these limitations, the authors propose Bias-Variance Reduced Local SGD (BVR-L-SGD). The architecture of this algorithm rests on three main pillars:

  1. Bias Reduction: To combat client drift, the algorithm employs a bias-reduced gradient estimator. It adjusts the local gradient using a "snapshot" of the global gradient from the last synchronization point. This ensures that even as local models diverge, the update direction remains anchored to the true global objective.
  2. Variance Reduction: The method incorporates a SARAH-like (Stochastic Recursive Gradient) technique. This reduces the noise inherent in using small batches of data, allowing for more stable and aggressive local steps.
  3. Random Model Selection: In a significant departure from standard Federated Averaging—which averages all local models at the end of a communication round—BVR-L-SGD randomly selects one of the local models to become the new global model. The authors argue that this random selection, combined with their specific estimator, better utilizes "second-order heterogeneity" (the similarity in the curvature of local loss functions) to accelerate convergence.

Datasets and Experimental Setup

The researchers evaluated their algorithm using the CIFAR-10 image classification benchmark. To simulate real-world FL environments, they artificially partitioned CIFAR-10 into different "heterogeneity patterns."

Illustration of the data partitioning strategy controlled by parameter q.

They introduced a parameter $q$ to control data imbalance. A low $q$ (e.g., 0.1) represents nearly identical (IID) data across workers, while a high $q$ (e.g., 0.85) represents highly non-IID data, mimicking severe real-world data heterogeneity.

Key Insights

  • Breaking the Barrier: Most nonconvex optimization methods are theoretically limited to a communication complexity of $\Theta(1/\epsilon)$. BVR-L-SGD is the first to break this barrier for general smooth nonconvex objectives when the local computation budget is large and data heterogeneity is low.
  • The Power of Curvature: The paper highlights the importance of second-order heterogeneity ($\zeta$). While most research focuses on how much the gradients differ across clients, this paper demonstrates that if the Hessians (the "shape" or curvature of the loss landscape) are similar across workers, we can achieve much faster communication rates.
  • Averaging Isn't Always Optimal: A major "aha moment" in the paper is the realization that for variance-reduced local methods, simple averaging can actually hinder theoretical performance. Randomly sampling a local model can be a more effective synchronization strategy when trying to exploit second-order similarities.

Key Results

BVR-L-SGD demonstrates both theoretical and empirical superiority over existing baselines.

  • Theoretical Superiority: BVR-L-SGD achieves a better dependence on the accuracy parameter $\epsilon$ than Minibatch SGD, Local SGD, and SCAFFOLD.
  • Empirical Performance: In experiments on CIFAR-10, BVR-L-SGD consistently outperformed all competitors (SGD, SARAH, Local SGD, and SCAFFOLD) in terms of both training loss and test accuracy.
  • Robustness to Heterogeneity:
Training loss and test accuracy across varying levels of data heterogeneity (q).

As shown in the results above, while the performance of standard Local SGD and SCAFFOLD degraded significantly as data became more heterogeneous (increasing $q$), BVR-L-SGD remained remarkably stable. It maintained high accuracy and low training loss even in highly non-IID settings.

Limitations and Future Work

While promising, BVR-L-SGD has a few limitations:

  • First-Order Focus: The current analysis focuses on finding "first-order stationary points" (where the gradient is zero). In complex landscapes, these could be saddle points rather than true local minima. Extending the theory to find second-order stationary points is a challenging next step.
  • Implementation Complexity: BVR-L-SGD is more complex to implement than standard FedAvg, as it requires tracking recursive gradient states and managing global gradient snapshots.
  • Assumptions on Curvature: The most significant theoretical gains rely on the second-order heterogeneity ($\zeta$) being relatively small. If the "curves" of the loss functions on different devices are radically different, the advantage of this method may diminish.

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...
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