Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming

• URL: http://arxiv.org/abs/2104.01808v1
• Date: Mon, 5 Apr 2021 08:15:20 GMT
• Title: Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming
• Authors: Ziyue Huang, Yuan Qiu, Ke Yi, Graham Cormode
• Abstract summary: We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among $k$ parties. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints.
• Score: 10.952006057356714
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among $k$ parties. We consider two application scenarios: (1) one-shot, where the data is static and the aggregator conducts a one-time computation; and (2) streaming, where each party receives a stream of items over time and the aggregator continuously monitors the frequencies. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints. In particular, when specialized to the $\varepsilon$-LDP model, our protocol achieves an error of $\sqrt{k}/(e^{\Theta(\varepsilon)}-1)$ for all $\varepsilon$, while the previous protocol (Chen et al., 2020) has error $O(\sqrt{k}/\min\{\varepsilon, \sqrt{\varepsilon}\})$.

Related papers

• Differential Privacy on Trust Graphs [54.55190841518906]
  We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. We give a DP algorithm for aggregation with a much better privacy-utility trade-off than in the well-studied local model of DP.
  arXiv  Detail & Related papers  (2024-10-15T20:31:04Z)
• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  We study the problem of computing pairwise statistics, i.e., ones of the form $binomn2-1 sum_i ne j f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc.
  arXiv  Detail & Related papers  (2024-06-24T04:06:09Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  We study person-level differentially private mean estimation in the case where each person holds multiple samples. We give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP.
  arXiv  Detail & Related papers  (2024-05-30T18:20:35Z)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  We show how to shuffle $(epsilon_i,delta_i)$-PLDP setting with personalized privacy parameters. We prove that shuffled $(epsilon_i,delta_i)$-PLDP process approximately preserves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  arXiv  Detail & Related papers  (2023-12-22T02:31:46Z)
• Differentially Private Clustering in Data Streams [65.78882209673885]
  We present a differentially private streaming clustering framework which only requires an offline DP coreset or clustering algorithm as a blackbox. Our framework is also differentially private under the continual release setting, i.e., the union of outputs of our algorithms at every timestamp is always differentially private.
  arXiv  Detail & Related papers  (2023-07-14T16:11:22Z)
• Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation [20.909302074826666]
  Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA) We show that in order to achieve the optimal error under $(varepsilon, delta)$-DP, it is sufficient for each client to send $Thetaleft( n minleft(varepsilon, varepsilon2right)$ bits for FL and $Thetaleft(logleft(minleft(varepsilon, varepsilon2right)$)$ bits for FA
  arXiv  Detail & Related papers  (2023-04-04T05:37:17Z)
• Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano [83.5933307263932]
  We study data reconstruction attacks for discrete data and analyze it under the framework of hypothesis testing. We show that if the underlying private data takes values from a set of size $M$, then the target privacy parameter $epsilon$ can be $O(log M)$ before the adversary gains significant inferential power.
  arXiv  Detail & Related papers  (2022-10-24T23:50:12Z)
• Robust Estimation of Discrete Distributions under Local Differential Privacy [1.52292571922932]
  We consider the problem of estimating a discrete distribution in total variation from $n$ contaminated data batches under a local differential privacy constraint. We show that combining the two constraints leads to a minimax estimation rate of $epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$ up to a $sqrtlog (1/epsilon)$ factor.
  arXiv  Detail & Related papers  (2022-02-14T15:59:02Z)
• Infinitely Divisible Noise in the Low Privacy Regime [9.39772079241093]
  Federated learning, in which training data is distributed among users and never shared, has emerged as a popular approach to privacy-preserving machine learning. We present the first divisible infinitely noise distribution for real-valued data that achieves $varepsilon$-differential privacy.
  arXiv  Detail & Related papers  (2021-10-13T08:16:43Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.