Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees

Abstract

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.

arXiv comment54 pages, 4 theorems, 1 algorithm, code source on GitHub

References in corpus (11)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients
• Reconciling modern machine learning practice and the bias-variance trade-off
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• The generalization error of random features regression: Precise asymptotics and double descent curve
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning

Cited by in corpus (6)

• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization