Distributed Mean Estimation with Limited Communication

Abstract

Motivated by the need for distributed learning and optimization algorithms with low communication cost, we study communication efficient algorithms for distributed mean estimation. Unlike previous works, we make no probabilistic assumptions on the data. We first show that for $d$ dimensional data with $n$ clients, a naive stochastic binary rounding approach yields a mean squared error (MSE) of $\Theta (d/n)$ and uses a constant number of bits per dimension per client. We then extend this naive algorithm in two ways: we show that applying a structured random rotation before quantization reduces the error to $\mathcal{O}((\log d)/n)$ and a better coding strategy further reduces the error to $\mathcal{O}(1/n)$ and uses a constant number of bits per dimension per client. We also show that the latter coding strategy is optimal up to a constant in the minimax sense i.e., it achieves the best MSE for a given communication cost. We finally demonstrate the practicality of our algorithms by applying them to distributed Lloyd's algorithm for k-means and power iteration for PCA.

References in corpus (3)

• Federated Learning: Strategies for Improving Communication Efficiency
• Practical Secure Aggregation for Federated Learning on User-Held Data
• Communication Complexity of Distributed Convex Learning and Optimization

Cited by in corpus (61)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Three Approaches for Personalization with Applications to Federated Learning
• Agnostic Federated Learning
• A Field Guide to Federated Optimization
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Federated Learning in Mobile Edge Networks: A Comprehensive Survey
• Think Locally, Act Globally: Federated Learning with Local and Global Representations
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• Communication Efficient Federated Learning over Multiple Access Channels
• Oort: Efficient Federated Learning via Guided Participant Selection
• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
• Optimal Gradient Compression for Distributed and Federated Learning
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning
• Breaking the Communication-Privacy-Accuracy Trilemma
• Federated Learning with Additional Mechanisms on Clients to Reduce Communication Costs
• Secure Federated Submodel Learning
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Communication-Efficient Edge AI: Algorithms and Systems
• The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation
• FedJAX: Federated learning simulation with JAX
• D2P-Fed: Differentially Private Federated Learning With Efficient Communication
• On the Utility of Gradient Compression in Distributed Training Systems
• Secure Aggregation with Heterogeneous Quantization in Federated Learning
• MARINA: Faster Non-Convex Distributed Learning with Compression
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• Applications of Federated Learning in Smart Cities: Recent Advances, Taxonomy, and Open Challenges
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Characterizing Impacts of Heterogeneity in Federated Learning upon Large-Scale Smartphone Data
• DRIVE: One-bit Distributed Mean Estimation
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Differentially Private Federated Learning with Laplacian Smoothing
• Wyner-Ziv Gradient Compression for Federated Learning
• Unified Group Fairness on Federated Learning
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Distributed Differentially Private Computation of Functions with Correlated Noise
• Fairness-aware Agnostic Federated Learning
• ESMFL: Efficient and Secure Models for Federated Learning
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• Lossless Compression of Efficient Private Local Randomizers
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Critical Learning Periods in Federated Learning
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• FLFE: A Communication-Efficient and Privacy-Preserving Federated Feature Engineering Framework
• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• The Scalability for Parallel Machine Learning Training Algorithm: Dataset Matters
• Slashing Communication Traffic in Federated Learning by Transmitting Clustered Model Updates
• FDNAS: Improving Data Privacy and Model Diversity in AutoML
• Improved Communication Efficiency for Distributed Mean Estimation with Side Information
• Learning with User-Level Privacy
• Information-constrained optimization: can adaptive processing of gradients help?
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• On the Convergence of Quantized Parallel Restarted SGD for Central Server Free Distributed Training
• Solon: Communication-efficient Byzantine-resilient Distributed Training via Redundant Gradients
• Optimal Compression of Locally Differentially Private Mechanisms
• Quantizing data for distributed learning