Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints

• URL: http://arxiv.org/abs/2011.00083v3
• Date: Fri, 19 Feb 2021 04:06:00 GMT
• Title: Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
• Authors: Jayadev Acharya, Peter Kairouz, Yuhan Liu, Ziteng Sun
• Abstract summary: We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor and the sample complexity under communication constraints up to a logarithmic factor.
• Score: 46.944178305032146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints, we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on the recently proposed method of chi squared contractions.

Related papers

• Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks [59.43433767253956]
  We consider the problem of privately estimating the mean of vectors distributed across different nodes of an unreliable wireless network. In a semi-decentralized setup, nodes can collaborate with their neighbors to compute a local consensus, which they relay to a central server. We study the tradeoff between collaborative relaying and privacy leakage due to the data sharing among nodes.
  arXiv  Detail & Related papers  (2024-06-06T06:12:15Z)
• Optimal Private Discrete Distribution Estimation with One-bit Communication [63.413106413939836]
  We consider a private discrete distribution estimation problem with one-bit communication constraint. We characterize the first-orders of the worst-case trade-off under the one-bit communication constraint. These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint.
  arXiv  Detail & Related papers  (2023-10-17T05:21:19Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• One-bit Submission for Locally Private Quasi-MLE: Its Asymptotic Normality and Limitation [3.050919759387985]
  Local differential privacy(LDP) is an information-theoretic privacy definition suitable for statistical surveys that involve an untrusted data curator. The existing method to build LDP QMLE is difficult to implement for a large-scale survey system in the real world due to long waiting time, expensive communication cost, and the boundedness assumption of derivative of a log-likelihood function. We provided an alternative LDP protocol without those issues, which is potentially much easily deployable to a large-scale survey.
  arXiv  Detail & Related papers  (2022-02-15T05:04:59Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• Robust Testing and Estimation under Manipulation Attacks [32.95545820578349]
  We study robust testing and estimation of discrete distributions in the strong contamination model. We consider both the "centralized setting" and the "distributed setting with information constraints"
  arXiv  Detail & Related papers  (2021-04-21T19:49:49Z)
• Over-the-Air Statistical Estimation [4.082216579462796]
  We study schemes and lower bounds for distributed minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss. We show that estimation schemes that leverage the physical layer offer a drastic reduction in estimation error over digital schemes relying on a physical-layer abstraction.
  arXiv  Detail & Related papers  (2021-03-06T03:07:22Z)
• Unified lower bounds for interactive high-dimensional estimation under information constraints [40.339506154827106]
  We provide a unified framework enabling us to derive a variety of (tight) minimax lower bounds for different parametric families of distributions. Our lower bound framework is versatile and yields "plug-and-play" bounds that are widely applicable to a large range of estimation problems.
  arXiv  Detail & Related papers  (2020-10-13T17:25:19Z)

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.