STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning

Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, Pramod Varshney

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:

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

Trade-off between batch size, local updates, and communication 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.

Comparison of sample and communication complexities across various federated learning algorithms.

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

Abstract

Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. Despite extensive research, for a generic non-convex FL problem, it is not clear, how to choose the WNs' and the server's update directions, the minibatch sizes, and the local update frequency, so that the WNs use the minimum number of samples and communication rounds to achieve the desired solution. This work addresses the above question and considers a class of stochastic algorithms where the WNs perform a few local updates before communication. We show that when both the WN's and the server's directions are chosen based on certain stochastic momentum estimator, the algorithm requires $\tilde{\mathcal{O}}(\epsilon^{-3/2})$ samples and $\tilde{\mathcal{O}}(\epsilon^{-1})$ communication rounds to compute an $\epsilon$-stationary solution. To the best of our knowledge, this is the first FL algorithm that achieves such {\it near-optimal} sample and communication complexities simultaneously. Further, we show that there is a trade-off curve between local update frequencies and local minibatch sizes, on which the above sample and communication complexities can be maintained. {Finally, we show that for the classical FedAvg (a.k.a. Local SGD, which is a momentum-less special case of the STEM), a similar trade-off curve exists, albeit with worse sample and communication complexities. Our insights on this trade-off provides guidelines for choosing the four important design elements for FL algorithms, the update frequency, directions, and minibatch sizes to achieve the best performance.}
BibTeX
@inproceedings{khanduri2021stem,
  author = {Prashant Khanduri and PRANAY SHARMA and Haibo Yang and Mingyi Hong and Jia Liu and Ketan Rajawat and Pramod Varshney},
  title = {{STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=gEzN9bBbLt8},
}
Figure