FetchSGD: Communication-Efficient Federated Learning with Sketching

Abstract

Existing approaches to federated learning suffer from a communication bottleneck as well as convergence issues due to sparse client participation. In this paper we introduce a novel algorithm, called FetchSGD, to overcome these challenges. FetchSGD compresses model updates using a Count Sketch, and then takes advantage of the mergeability of sketches to combine model updates from many workers. A key insight in the design of FetchSGD is that, because the Count Sketch is linear, momentum and error accumulation can both be carried out within the sketch. This allows the algorithm to move momentum and error accumulation from clients to the central aggregator, overcoming the challenges of sparse client participation while still achieving high compression rates and good convergence. We prove that FetchSGD has favorable convergence guarantees, and we demonstrate its empirical effectiveness by training two residual networks and a transformer model.

References in corpus (18)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• HuggingFace's Transformers: State-of-the-art Natural Language Processing
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Federated Learning for Mobile Keyboard Prediction
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Differentially Private Federated Learning: A Client Level Perspective
• Applied Federated Learning: Improving Google Keyboard Query Suggestions
• Federated Optimization in Heterogeneous Networks
• Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption
• Origins of power-law degree distribution in the heterogeneity of human activity in social networks
• Sparsified SGD with Memory
• Practical Secure Aggregation for Federated Learning on User-Held Data
• Understanding Top-k Sparsification in Distributed Deep Learning
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches
• How to Catch L_2-Heavy-Hitters on Sliding Windows
• Compressing Gradient Optimizers via Count-Sketches

Cited by in corpus (10)

• FedKD: Communication Efficient Federated Learning via Knowledge Distillation
• FedML: A Research Library and Benchmark for Federated Machine Learning
• Communication-Efficient Robust Federated Learning with Noisy Labels
• FedEval: A Holistic Evaluation Framework for Federated Learning
• Self-supervised Cross-silo Federated Neural Architecture Search
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Sketch and Scale: Geo-distributed tSNE and UMAP
• MyMigrationBot: A Cloud-based Facebook Social Chatbot for Migrant Populations