Abstract
Communication overhead is a primary bottleneck in Federated Learning (FL). This paper introduces LoCoDL, a novel distributed learning algorithm that integrates local training with communication compression to significantly reduce bandwidth requirements. LoCoDL is the first algorithm to achieve "double acceleration"—optimizing for both the condition number of the optimization problem and the model dimensionality—while remaining compatible with a wide range of unbiased compression techniques. We provide a rigorous theoretical analysis demonstrating linear convergence for strongly convex functions and present empirical results showing that LoCoDL consistently outperforms state-of-the-art methods in communication efficiency.
Introduction
In Federated Learning, edge devices collaboratively train a global model without sharing raw data. However, the high dimensionality of modern machine learning models makes the frequent exchange of model updates between clients and a central server prohibitively expensive. To mitigate this, researchers typically employ two strategies: Local Training (LT), which allows clients to perform multiple local updates before communicating, and Communication Compression (CC), which reduces the size of transmitted messages through techniques like quantization or sparsification.
While both strategies are effective individually, combining them in a theoretically sound manner is challenging. Existing methods often fail to maintain "acceleration"—the speedup gained by exploiting problem geometry—or are restricted to specific, often impractical, compression schemes. LoCoDL addresses these limitations by providing a unified framework that is both theoretically optimal and practically flexible.
The LoCoDL Framework: Double Lifting and Variance Reduction
LoCoDL is built upon a randomized primal-dual approach using a technique called "Double Lifting." The optimization problem is reformulated as a consensus problem involving $n$ client variables and a global anchor variable. This structure enables several key algorithmic advantages:
- Variance Reduction: Instead of compressing raw gradients or weights, LoCoDL compresses the difference between local estimates and the global anchor. As the algorithm converges, this difference approaches zero, effectively eliminating the noise introduced by the compression process.
- Probabilistic Communication: Communication is triggered stochastically at each iteration, which simplifies the mathematical proof of convergence and allows for flexible tuning of communication frequency.
- Compressor Agnosticism: LoCoDL is compatible with any unbiased compressor, such as
rand-ksparsification or bit-width quantization, making it highly adaptable to various hardware and network constraints.
Theoretical Breakthrough: Double Acceleration
A major contribution of this work is the achievement of "double acceleration." In optimization theory, acceleration typically refers to a square-root dependency on the condition number ($\sqrt{\kappa}$). LoCoDL achieves this while simultaneously improving the dependency on the model dimension ($d$) through compression.
As shown in the complexity analysis in the table above, LoCoDL achieves a communication complexity of $\mathcal{O}((\sqrt{d} + \frac{d}{\sqrt{n}})\sqrt{\kappa} + d)$ in terms of real numbers communicated. This theoretical bound demonstrates its efficiency across various regimes, including settings with high-dimensional models or large numbers of clients.
Empirical Results
The performance of LoCoDL was evaluated using standard benchmarks, including logistic regression tasks from the LibSVM library and image classification on the MNIST dataset. The experiments compared LoCoDL against several state-of-the-art baselines, including DIANA, ADIANA, and 5GCS-CC.
The results consistently show that LoCoDL reaches the target accuracy using significantly fewer total bits communicated per client. While some algorithms like ADIANA may offer slightly better theoretical complexity in specific niche regimes, LoCoDL's superior performance in practice suggests that its local training approach is more robust for real-world distributed systems. Furthermore, LoCoDL demonstrates strong performance in heterogeneous data settings, a common challenge in practical FL deployments.
Conclusion
LoCoDL represents a significant advancement in communication-efficient distributed learning. By successfully combining local training and communication compression, it achieves state-of-the-art performance both theoretically and empirically. Future work will explore extending these guarantees to non-convex objectives and incorporating bidirectional compression to further optimize server-to-client communication.
Summary updated