Abstract
Federated Learning (FL) faces a fundamental tension between communication efficiency and computational load. We present STEM (Stochastic Two-Sided Momentum), a novel framework that simultaneously achieves near-optimal sample and communication complexities for non-convex optimization. By employing momentum on both worker and server sides, STEM effectively mitigates "client drift" in heterogeneous data environments. Furthermore, we characterize a mathematical trade-off between minibatch sizes and local update frequencies, allowing for flexible implementation across diverse hardware constraints.
Introduction: The Communication-Computation Tension
Federated Learning (FL) enables multiple worker nodes (WNs) to collaboratively train a global model without centralizing raw data, thereby preserving privacy. However, a primary bottleneck is the high cost of communication between workers and the central server. To reduce communication frequency, nodes often perform multiple local updates. While efficient, this practice can lead to "model drift," where local models diverge toward biased local data patterns, particularly in heterogeneous (non-IID) settings.
Until now, finding the optimal balance between four critical design elements—update directions, minibatch sizes ($b$), local update frequency ($I$), and server-side logic—to minimize both sample and communication complexity has remained a challenge.
Methods: Stochastic Two-Sided Momentum (STEM)
The STEM algorithm introduces a "two-sided momentum" framework to stabilize training:
- Worker-Side Momentum: Worker nodes utilize a momentum-assisted gradient estimator to reduce the variance of local updates, inspired by variance-reduction techniques like STORM.
- Server-Side Momentum: The server applies a second layer of momentum when aggregating worker updates, rather than simple averaging. This "double buffering" helps the global model resist drift caused by heterogeneous local data.
A key theoretical insight of STEM is the identification of a trade-off curve between the minibatch size ($b$) and the number of local updates ($I$). Practitioners can navigate this curve to choose between small-batch strategies with many local steps or large-batch strategies with fewer steps, while maintaining near-optimal complexity.
Key Results and Theoretical Analysis
STEM is the first FL algorithm to simultaneously achieve $O(\epsilon^{-3/2})$ sample complexity—matching the best possible for centralized non-convex SGD—and $O(\epsilon^{-1})$ communication complexity. As shown in the comparison table below, STEM significantly improves upon classical methods like FedAvg and SCAFFOLD.
Empirical Performance
The algorithm was evaluated on CIFAR-10 and MNIST datasets with 100 worker nodes under varying degrees of data heterogeneity.
- Superior Convergence: STEM consistently reached higher test accuracy faster than FedAvg and SCAFFOLD.
- Linear Speedup: The algorithm demonstrates linear speedup with respect to the number of worker nodes.
- Resilience to Heterogeneity: Performance remained stable even in high-heterogeneity settings where each node only accessed a small subset of classes.
Conclusion and Future Directions
STEM provides a robust, theoretically grounded framework for Federated Learning that balances communication and computation. By leveraging two-sided momentum, it achieves state-of-the-art complexity bounds and strong empirical performance in non-IID environments.
Future work includes characterizing formal lower bounds for communication complexity that explicitly account for intra-node variance and integrating communication compression techniques to further optimize for low-bandwidth networks.
Summary updated