FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching

Abstract

Communication complexity and privacy are the two key challenges in Federated Learning where the goal is to perform a distributed learning through a large volume of devices. In this work, we introduce FedSKETCH and FedSKETCHGATE algorithms to address both challenges in Federated learning jointly, where these algorithms are intended to be used for homogeneous and heterogeneous data distribution settings respectively. The key idea is to compress the accumulation of local gradients using count sketch, therefore, the server does not have access to the gradients themselves which provides privacy. Furthermore, due to the lower dimension of sketching used, our method exhibits communication-efficiency property as well. We provide, for the aforementioned schemes, sharp convergence guarantees. Finally, we back up our theory with various set of experiments.

References in corpus (10)

• Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption
• On the Convergence of Local Descent Methods in Federated Learning
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Variance Reduced Local SGD with Lower Communication Complexity
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Parallel SGD: When does averaging help?
• Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches
• Enhancing the Privacy of Federated Learning with Sketching
• Total stochastic gradient algorithms and applications in reinforcement learning
• Gradient Distribution Priors for Biomedical Image Processing