Breaking the Communication-Privacy-Accuracy Trilemma

By Wei-Ning Chen, Peter Kairouz, Ayfer Özgür. 2020

139 citations recorded by the source corpus.

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 <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula>-local differential privacy and <inline-formula> <tex-math notation="LaTeX">$b$ </tex-math></inline-formula>-bit communication constraints. For mean estimation, we propose the SQKR mechanism, a scheme based on Kashin’s representation and random sampling, with order-optimal estimation error under both constraints. We further apply SQKR to distributed SGD and obtain a communication efficient and (locally) differentially private distributed SGD protocol. For frequency estimation, we present the RHR mechanism, a scheme 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 <inline-formula> <tex-math notation="LaTeX">$b=1$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\varepsilon =O(1)$ </tex-math></inline-formula>. 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. In other words, the optimal performance is determined by the more stringent of the two constraints, and the less stringent constraint can be satisfied for free.

Subfields: Artificial Intelligence, Sociology and Political Science, Federated & Distributed Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints (2021, methodology): “…constraints, the optimal convergence rate for discrete distribution estimation was established in (Han et al., 2018b,a; Barnes et al., 2019; Acharya et al., 2019a,b; Chen et al., 2020) for the non-interactive setting, and (Barnes et al., 2019; Acharya et al., 2020) for general interactive models.”
Lossless Compression of Efficient Private Local Randomizers (2021, methodology): “Plots in (Chen et al., 2020) also compare their algorithm with from this approach is nearly a factor of 5× larger for typical parameters of interest.”
Private Weighted Random Walk Stochastic Gradient Descent (2020, background): “The literature on privacy-preserving SGD has extensively studied the problem of designing LDP mechanisms for the model update or the gradient through model perturbation (e.g., [14]) or gradient perturbation and quantization (e.g., [15]–[18]).”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “To improve the communication efﬁciency for private distributed learning, Chen et al. [167] developed efﬁcient encoding and decoding mechanisms to simultaneously achieve optimal communication efﬁciency and differential privacy under typical statistical learning settings.”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “Finally, we point out that communication efficiency is a common requirement in distributed learning and optimization, and substantial effort is spent on compression of the messages sent by users, through multiple methods including hashing, pruning, and quantization (see, e.g., Zhang et al., 2013; Al”