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

2020/06/25 by Constantin Philippenko, Aymeric Dieuleveut, Philippenko, Constantin +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2006.14591

openalex publication_date 2020/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a framework - Artemis - to tackle the problem of learning in a\ndistributed or federated setting with communication constraints and device\npartial participation. Several workers (randomly sampled) perform the\noptimization process using a central server to aggregate their computations. To\nalleviate the communication cost, Artemis allows to compress the information\nsent in both directions (from the workers to the server and conversely)\ncombined with a memory mechanism. It improves on existing algorithms that only\nconsider unidirectional compression (to the server), or use very strong\nassumptions on the compression operator, and often do not take into account\ndevices partial participation. We provide fast rates of convergence (linear up\nto a threshold) under weak assumptions on the stochastic gradients (noise's\nvariance bounded only at optimal point) in non-i.i.d. setting, highlight the\nimpact of memory for unidirectional and bidirectional compression, analyze\nPolyak-Ruppert averaging. We use convergence in distribution to obtain a lower\nbound of the asymptotic variance that highlights practical limits of\ncompression. We propose two approaches to tackle the challenging case of\ndevices partial participation and provide experimental results to demonstrate\nthe validity of our analysis.\n

Citations

• A Stochastic Approximation Method
• Making Gradient Descent Optimal for Strongly Convex Stochastic\n Optimization
• DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The generalization error of random features regression: Precise asymptotics and double descent curve
• A Better Alternative to Error Feedback for Communication-Efficient\n Distributed Learning

Cited by

• Tight analyses of first-order methods with error feedback

Related

• Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• BICompFL: Stochastic Federated Learning with Bi-Directional Compression
• Resource Allocation for Compression-aided Federated Learning with High Distortion Rate