Breaking the Communication-Privacy-Accuracy Trilemma
Breaking the Communication-Privacy-Accuracy Trilemma
复制标题
DOI：
10.1109/tit.2022.3218772
复制
发表时间：
2020-07
影响因子：
2.5
通讯作者：
Wei-Ning Chen;P. Kairouz;Ayfer Özgür
中科院分区：
文献类型：
--
作者：
Wei-Ning Chen;P. Kairouz;Ayfer Özgür
分布式学习和估计的两个主要挑战是：1)保护本地样本的隐私；2)将它们有效地传递到中央服务器，同时实现端到端任务的高精度。虽然在最近的文献中，人们对分别解决这些挑战中的每一个都有很大的兴趣，但同时应对这两个挑战的治疗方法仍然很少。在本文中，我们开发了新的编码和解码机制，在各种规范设置下同时获得最佳的隐私和通信效率。特别地，我们考虑了在$varepsilon$本地差分隐私和$b$比特通信约束下的均值估计和频率估计问题。对于均值估计，我们提出了SQKR机制，这是一种基于Kashin表示和随机抽样的机制，在两种约束下都具有阶数最优估计误差。我们进一步将SQKR应用到分布式SGD中，得到了一个通信高效且(局部)差分私有的分布式SGD协议。对于频率估计，我们提出了一种RHR机制，该机制利用Walsh-Hadamard矩阵的递归结构，在所有隐私级别和通信预算下实现阶数最优的估计误差。作为副产品，我们还构建了一个对所有隐私机制和通信约束都是速率最优的分布估计机制，推广了最近限制在$b=1$和$\varepsilon=O(1)$的分布估计机制。我们的结果表明，在联合隐私和通信约束下的智能编码可以产生与单独在任一约束下达到的最优精度匹配的性能。换言之，最优性能取决于两个约束中较严格的一个，而较宽松的约束可以免费满足。
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 $\varepsilon $ -local differential privacy and $b$ -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 $b=1$ and $\varepsilon =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. 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.