Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
We introduce a framework - Artemis - to tackle the problem of learning in a distributed or federated setting with communication constraints and device partial participation. Several workers (randomly sampled) perform the optimization process using a central server to aggregate their computations. To alleviate the communication cost, Artemis allows to compress the information sent in both directions (from the workers to the server and conversely) combined with a memory mechanism. It improves on existing algorithms that only consider unidirectional compression (to the server), or use very strong assumptions on the compression operator, and often do not take into account devices partial participation. We provide fast rates of convergence (linear up to a threshold) under weak assumptions on the stochastic gradients (noise's variance bounded only at optimal point) in non-i.i.d. setting, highlight the impact of memory for unidirectional and bidirectional compression, analyze Polyak-Ruppert averaging. We use convergence in distribution to obtain a lower bound of the asymptotic variance that highlights practical limits of compression. We propose two approaches to tackle the challenging case of devices partial participation and provide experimental results to demonstrate the validity of our analysis.
Code (1)
Tasks
Federated LearningSimilar Papers 제목 키워드 기반
BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training
Slow and costly communication is often the main bottleneck in distributed optimization, especially in federated learning where it occurs over wireless networks. We introduce BiCoLoR, a communication-efficient optimizatio…
Distributed OptimizationFederated LearningFederated Neural Compression Under Heterogeneous Data
We discuss a federated learned compression problem, where the goal is to learn a compressor from real-world data which is scattered across clients and may be statistically heterogeneous, yet share a common underlying rep…
Federated LearningPersonalized Federated LearningFederated Learning with Compression: Unified Analysis and Sharp Guarantees
In federated learning, communication cost is often a critical bottleneck to scale up distributed optimization algorithms to collaboratively learn a model from millions of devices with potentially unreliable or limited co…
Distributed OptimizationFederated LearningFedFetch: Faster Federated Learning with Adaptive Downstream Prefetching
Federated learning (FL) is a machine learning paradigm that facilitates massively distributed model training with end-user data on edge devices directed by a central server. However, the large number of heterogeneous cli…
Federated LearningEscaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression
We consider the problem of finding second-order stationary points of heterogeneous federated learning (FL). Previous works in FL mostly focus on first-order convergence guarantees, which do not rule out the scenario of u…
Federated Learning