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 for problems that satisfy strong convexity. Empirical results support this theoretical gain over existing methods.
Introduction
In Federated Learning (FL), the primary bottleneck is the communication cost between a central server and a large number of distributed clients. Current optimization strategies generally fall into two categories:
- Local Update Methods (e.g., FedAvg): Clients perform multiple local steps before communicating. These are highly efficient when data is homogeneous but suffer from "client drift" near the optimum, leading to sub-optimal convergence rates.
- Global Update Methods (e.g., SGD/ASG): Clients send gradients every round. These methods offer fast theoretical convergence (exponential in $R$ for accelerated versions) but ignore data similarity, failing to capitalize on potential "warm-up" efficiencies.
FedChain addresses this gap by "chaining" these two strategies to achieve the best of both worlds.
The FedChain Framework
FedChain (Federated Chaining) is a two-phase optimization framework designed to transition from local efficiency to global precision.
The framework consists of three main steps:
- Phase 1 (Local Sprint): A local update algorithm (like FedAvg) is run for the first half of the communication rounds ($R/2$). This phase exploits client homogeneity to rapidly approach the solution.
- The Pivot (Model Selection): To guard against extreme heterogeneity, the server performs a model selection step. It compares the initial point $\hat{x}_0$ with the Phase 1 output $\hat{x}_{1/2}$ using a small sample of client data, selecting the better point $\hat{x}_1$.
- Phase 2 (Global Finish): A global update algorithm (like SGD or Accelerated SGD) is used for the remaining $R/2$ rounds to ensure fast, high-precision convergence.
Theoretical Intuition: Gradient Orthogonality
The core motivation for FedChain lies in the behavior of client gradients relative to the global optimum.
Far from the optimum, client gradients $\nabla F_i(x)$ tend to point in a similar direction. In this "agreement" region (highlighted in yellow in the figure), local steps are highly effective. However, as the model approaches the optimum $x^*$, gradients become more orthogonal or even point in opposite directions (the gray region). In this "disagreement" region, local steps lead to "client drift," where individual updates pull the model away from the global consensus. FedChain's switch to global methods in Phase 2 mitigates this drift.
Empirical Evaluation
The authors evaluated FedChain on several benchmarks, demonstrating its robustness across different levels of data heterogeneity.
- MNIST (Strongly Convex): FedChain was shown to be near-optimal, matching theoretical lower bounds for strongly convex problems.
- EMNIST (Non-Convex ConvNet): FedChain (FedAvg $\to$ SGD) achieved 85.08% test accuracy, significantly outperforming standalone FedAvg (83.14%) and SGD (78.42%).
- CIFAR-100 (ResNet-18): FedChain reached 51.67% accuracy, a substantial improvement over standalone SGD (19.68%) and FedAvg (50.59%).
Conclusion
FedChain provides a theoretically grounded and empirically successful framework for reducing communication costs in FL. By intelligently switching from local to global updates, it leverages data similarity while maintaining fast convergence. Future work includes closing the theoretical gap for general convex functions and developing adaptive heuristics for the "switch point" between phases.
Summary updated