Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters

By Jayadev Acharya, Ziteng Sun. 2019

62 citations recorded by the source corpus.

We consider the problems of distribution estimation and heavy hitter (frequency) estimation under privacy and communication constraints. While these constraints have been studied separately, optimal schemes for one are sub-optimal for the other. We propose a sample-optimal $\varepsilon$-locally differentially private (LDP) scheme for distribution estimation, where each user communicates only one bit, and requires no public randomness. We show that Hadamard Response, a recently proposed scheme for $\varepsilon$-LDP distribution estimation is also utility-optimal for heavy hitter estimation. Finally, we show that unlike distribution estimation, without public randomness where only one bit suffices, any heavy hitter estimation algorithm that communicates $o(\min \{\log n, \log k\})$ bits from each user cannot be optimal.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Privacy & Security, Algorithms & Complexity

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 Electrical and Electronic Engineering

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, background): “In [AS19], the authors consider both private and public coin mechanisms, and show that the Hadamard mechanism is near optimal in terms of communication for both distribution and frequency estimation.”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “If we further assume X are drawn from some discrete distribution p, then the problem falls into distribution estimation under local differential privacy [9], [13], [34], [36], [42], [43], [44], [45], [46] and limited communication [11], [25], [45], [46], [47], [48], [49], [50].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Computing histograms is fundamental in data analytics and is well-studied in DP (e.g., (Kairouz et al., 2016; Acharya & Sun, 2019; Suresh, 2019)), as private histogram procedures can be used as a black-box to solve important algorithmic problems such as heavy hitters (e.g., (Bassily et al., 2017))…”
On the Power of Multiple Anonymous Messages (2019, unknown): “Heavy hitters and frequency estimation have also been studied extensively in the standard models of DP, e.g., [97,67,12,11,95,20,2].”
Differentially Private Assouad, Fano, and Le Cam (2020, background): “(2019); Sheffet (2017); Ye and Barg (2018); Gaboardi and Rogers (2018); Acharya et al. (2019c); Acharya and Sun (2019); Acharya et al.”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, methodology): “Our first result is a complete characterization of the sample complexity under ε-LDP up to constant factors.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, methodology): “Moreover, our private-coin independence testing protocol also involves a step that learns both marginal distributions, which relies on the scheme from [7].”
Private Heavy Hitters and Range Queries in the Shuffled Model (2019, methodology): “The analogous question for local differential privacy (i.e., without shufﬂing) was considered recently in [2, 1].”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “The protocol is inspired by that of Acharya and Sun (2019), which provides a one-bit LDP protocol for distribution learning.”