FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning

Charlie Hou, Kiran Koshy Thekumparampil, Giulia Fanti, Sewoong Oh

Abstract

Federated learning (FL) aims to minimize the communication complexity of training a model over heterogeneous data distributed across many clients. A common approach is local methods, where clients take multiple optimization steps over local data before communicating with the server (e.g., FedAvg). Local methods can exploit similarity between clients' data. However, in existing analyses, this comes at the cost of slow convergence in terms of the dependence on the number of communication rounds R. On the other hand, global methods, where clients simply return a gradient vector in each round (e.g., SGD), converge faster in terms of R but fail to exploit the similarity between clients even when clients are homogeneous. We propose FedChain, an algorithmic framework that combines the strengths of local methods and global methods to achieve fast convergence in terms of R while leveraging the similarity between clients. Using FedChain, we instantiate algorithms that improve upon previously known rates in the general convex and PL settings, and are near-optimal (via an algorithm-independent lower bound that we show) for problems that satisfy strong convexity. Empirical results support this theoretical gain over existing methods.

Introduction

In Federated Learning (FL), a central server coordinates numerous clients to train a global model without accessing their raw data. The primary bottleneck in this setting is communication cost, as transferring model updates between the server and clients is often slow and expensive.

Current FL algorithms generally fall into two categories:

  1. Local Update Methods (e.g., FedAvg): Clients perform multiple local optimization steps before communicating. These methods excel when client data is homogeneous (similar) but often exhibit slow convergence rates relative to the total number of communication rounds.
  2. Global Update Methods (e.g., SGD): Clients send only a single gradient per round. While these offer faster mathematical convergence rates, they fail to exploit data similarity between clients.

Existing research suggests a fundamental trade-off: algorithms can either have a favorable dependence on data similarity or a fast convergence rate, but achieving both simultaneously has proven difficult. FedChain is designed to bridge this gap.

The FedChain Framework

The authors introduce FedChain, a two-phase framework that "chains" local and global optimization strategies to achieve near-optimal communication efficiency.

Algorithm 1: The FedChain framework combines a local update phase with a global refinement phase.

The process consists of three main steps:

  • Phase 1 (Local Exploration): The algorithm runs a local update method (e.g., FedAvg) for the first half of the communication rounds. This allows the model to make significant progress quickly if client data distributions are similar.
  • The Switch: To prevent divergence in highly heterogeneous settings, the algorithm evaluates the model's performance and selects the better starting point between the initial model and the Phase 1 result.
  • Phase 2 (Global Refinement): The algorithm switches to a global update method (e.g., SGD or Accelerated SGD) for the remaining rounds. This phase uses unbiased gradients to converge precisely to the optimum, regardless of data heterogeneity.

Key Insights: Gradient Agreement

A core intuition driving FedChain is the behavior of client gradients relative to the global optimum.

Gradients from different clients tend to agree when far from the optimum but disagree as they approach it.

When the model is far from the global optimum, gradients from different clients typically point in a similar direction. In this "agreement" regime, local steps are highly effective. However, as the model nears the optimum, local gradients may begin to "disagree" due to unique local data features. In this "disagreement" regime, continued local steps can actually push the model away from the global solution. FedChain addresses this by switching to global updates exactly when fine-tuning is needed.

Theoretical and Empirical Results

The paper provides new algorithm-independent lower bounds, proving that for strongly convex problems, the chaining approach is near-optimal. Specifically, FedChain achieves an error rate that decays exponentially with the number of rounds while maintaining a superior dependence on data heterogeneity ($\zeta^2$).

Empirically, FedChain was evaluated on MNIST, EMNIST, and CIFAR-100 datasets with varying levels of "shuffling" to simulate different degrees of data heterogeneity.

  • Superior Convergence: In strongly convex settings, FedChain achieves an error rate of $\tilde{O}(\min\{\Delta, \zeta^2/\mu\} \exp(-R/\sqrt{\kappa}))$, outperforming the $1/R^2$ rates typical of standard local methods.
  • Robust Performance: On EMNIST and CIFAR-100, FedChain (specifically FedAvg $\to$ SGD) consistently outperformed standalone FedAvg, SGD, and SCAFFOLD across all levels of data heterogeneity.

Conclusion

FedChain offers a robust solution to the communication bottleneck in FL by intelligently switching between local and global optimization. While it achieves near-optimality for strongly convex and PL settings, future work remains to close the theoretical gap for general convex functions and to develop adaptive switching logic for practical deployments.

Summary updated

Abstract

Federated learning (FL) aims to minimize the communication complexity of training a model over heterogeneous data distributed across many clients. A common approach is local methods, where clients take multiple optimization steps over local data before communicating with the server (e.g., FedAvg). Local methods can exploit similarity between clients' data. However, in existing analyses, this comes at the cost of slow convergence in terms of the dependence on the number of communication rounds R. On the other hand, global methods, where clients simply return a gradient vector in each round (e.g., SGD), converge faster in terms of R but fail to exploit the similarity between clients even when clients are homogeneous. We propose FedChain, an algorithmic framework that combines the strengths of local methods and global methods to achieve fast convergence in terms of R while leveraging the similarity between clients. Using FedChain, we instantiate algorithms that improve upon previously known rates in the general convex and PL settings, and are near-optimal (via an algorithm-independent lower bound that we show) for problems that satisfy strong convexity. Empirical results support this theoretical gain over existing methods.
BibTeX
@inproceedings{hou2022fedchain,
  author = {Charlie Hou and Kiran Koshy Thekumparampil and Giulia Fanti and Sewoong Oh},
  title = {{FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=GoRvPQAAJZ},
}
Figure