Breaking the Communication-Privacy-Accuracy Trilemma

Abstract

Two major challenges in distributed learning and estimation are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, treatments that simultaneously address both challenges are still largely missing. In this paper, we develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in various canonical settings. In particular, we consider the problems of mean estimation and frequency estimation under $\epsilon$-local differential privacy and $b$-bit communication constraints. For mean estimation, we propose a scheme based on Kashin's representation and random sampling, with order-optimal estimation error under both constraints. For frequency estimation, we present a mechanism that leverages the recursive structure of Walsh-Hadamard matrices and achieves order-optimal estimation error for all privacy levels and communication budgets. As a by-product, we also construct a distribution estimation mechanism that is rate-optimal for all privacy regimes and communication constraints, extending recent work that is limited to $b=1$ and $\epsilon =O(1)$. Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone.

arXiv comment35 pages, 9 figures, submitted to NeurIPS 2020

References in corpus (19)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Protection Against Reconstruction and Its Applications in Private Federated Learning
• Discrete Distribution Estimation under Local Privacy
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Distributed Mean Estimation with Limited Communication
• Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• Uncertainty Principles and Vector Quantization
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation
• Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
• Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy
• rTop-k: A Statistical Estimation Approach to Distributed SGD
• Locally Differentially Private Data Collection and Analysis
• Lossless Compression of Efficient Private Local Randomizers

Cited by in corpus (10)

• A Field Guide to Federated Optimization
• Wyner-Ziv Gradient Compression for Federated Learning
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• Lossless Compression of Efficient Private Local Randomizers
• Metric Differential Privacy at the User-Level Via the Earth Mover's Distance
• Improved Communication Efficiency for Distributed Mean Estimation with Side Information
• FED-${\chi }^2$: Privacy Preserving Federated Correlation Test
• FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptation
• Optimal Compression of Locally Differentially Private Mechanisms
• Algorithms for the Communication of Samples