Improved Convergence Rates for Non-Convex Federated Learning with Compression

Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S. Dhillon

Federated Learning (FL) is a cornerstone of privacy-preserving AI, yet its practical implementation is often hindered by two primary factors: communication costs and client heterogeneity. Standard algorithms like FedAvg often struggle when data distributions across devices vary significantly, leading to "client drift" where local models diverge from the global objective. Furthermore, the high dimensionality of modern neural networks makes frequent communication of full model updates prohibitively expensive.

In their paper, "Faster Non-Convex Federated Learning via Global and Local Momentum," researchers propose FedGLOMO, a novel algorithm designed to overcome these hurdles.

The FedGLOMO Approach

FedGLOMO (Federated Global and LOcal MOmentum) addresses these issues through a dual-layered variance reduction strategy:

  • Local Momentum: Clients utilize an SVRG/STORM-style momentum update to reduce the noise inherent in local stochastic gradients.
  • Global Momentum: The server treats the aggregation of client updates as a "generalized gradient update." By applying momentum at the server level, FedGLOMO neutralizes the high variance introduced by heterogeneous data distributions.
  • Compressed Communication: FedGLOMO is the first algorithm to achieve an $\mathcal{O}(\epsilon^{-1.5})$ iteration complexity while supporting quantization (reducing update precision to save bandwidth).

Theoretical Advancements and Comparison

A key contribution of this work is the theoretical improvement in convergence rates. While most prior methods for non-convex FL achieve an iteration complexity of $\mathcal{O}(\epsilon^{-2})$, FedGLOMO reaches an $\epsilon$-stationary point in $\mathcal{O}(\epsilon^{-1.5})$ iterations.

Crucially, the analysis moves beyond the restrictive "Bounded Client Dissimilarity" (BCD) assumption—a mathematical crutch that assumes client data isn't too different. Instead, the authors propose a new, empirically verifiable heterogeneity assumption that better characterizes real-world data distributions.

Comparison of FedGLOMO with state-of-the-art federated learning algorithms.

As shown in the table above, FedGLOMO is unique in its ability to provide superior convergence rates while simultaneously supporting compression and operating without the restrictive BCD assumption.

Empirical Validation

The team evaluated FedGLOMO on CIFAR-10 and Fashion-MNIST datasets under highly heterogeneous settings (e.g., each client only seeing 1-2 classes). The results demonstrate significant practical benefits:

  • Communication Efficiency: In heterogeneous settings, FedGLOMO required only one-third of the bits used by FedPAQ to reach the same error level. In homogeneous settings, this improved to one-fifth.
  • Smoother Training: The dual-momentum approach resulted in much smoother convergence trajectories compared to baselines, which often showed jagged, unstable progress due to client drift.

Conclusion

FedGLOMO represents a significant step forward in making Federated Learning both faster and more communication-efficient. By taming the dual sources of variance—local gradient noise and global client heterogeneity—it provides a robust framework for training large-scale non-convex models on decentralized, diverse data.

Summary updated

Abstract

We propose \texttt{FedGLOMO}, a novel federated learning (FL) algorithm with an iteration complexity of $\mathcal{O}(\epsilon^{-1.5})$ to converge to an $\epsilon$-stationary point (i.e., $\mathbb{E}[\|\nabla f(\bm{x})\|^2] \leq \epsilon$) for smooth non-convex functions -- under arbitrary client heterogeneity and compressed communication -- compared to the $\mathcal{O}(\epsilon^{-2})$ complexity of most prior works. Our key algorithmic idea that enables achieving this improved complexity is based on the observation that the convergence in FL is hampered by two sources of high variance: (i) the global server aggregation step with multiple local updates, exacerbated by client heterogeneity, and (ii) the noise of the local client-level stochastic gradients. By modeling the server aggregation step as a generalized gradient-type update, we propose a variance-reducing momentum-based global update at the server, which when applied in conjunction with variance-reduced local updates at the clients, enables \texttt{FedGLOMO} to enjoy an improved convergence rate. Moreover, we derive our results under a novel and more realistic client-heterogeneity assumption which we verify empirically -- unlike prior assumptions that are hard to verify. Our experiments illustrate the intrinsic variance reduction effect of \texttt{FedGLOMO}, which implicitly suppresses client-drift in heterogeneous data distribution settings and promotes communication efficiency.
BibTeX
@misc{das2020improved,
  author = {Rudrajit Das and Abolfazl Hashemi and Sujay Sanghavi and Inderjit S. Dhillon},
  title = {{Improved Convergence Rates for Non-Convex Federated Learning with Compression}},
  year = {2020},
  eprint = {2012.04061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.04061},
}
Figure