Optimal Private Discrete Distribution Estimation with One-bit Communication

• URL: http://arxiv.org/abs/2310.11005v1
• Date: Tue, 17 Oct 2023 05:21:19 GMT
• Title: Optimal Private Discrete Distribution Estimation with One-bit Communication
• Authors: Seung-Hyun Nam, Vincent Y. F. Tan, Si-Hyeon Lee,
• Abstract summary: 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.
• Score: 63.413106413939836
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a private discrete distribution estimation problem with one-bit communication constraint. The privacy constraints are imposed with respect to the local differential privacy and the maximal leakage. The estimation error is quantified by the worst-case mean squared error. We completely characterize the first-order asymptotics of this privacy-utility trade-off under the one-bit communication constraint for both types of privacy constraints by using ideas from local asymptotic normality and the resolution of a block design mechanism. These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint in terms of the parameters of the privacy constraint and the size of the alphabet of the discrete distribution.

Related papers

• Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints [5.3595271893779906]
  We study federated learning for nonparametric regression in the context of distributed samples across different servers. Findings shed light on the tradeoff between statistical accuracy and privacy preservation.
  arXiv  Detail & Related papers  (2024-06-10T19:34:07Z)
• Differential Privacy via Distributionally Robust Optimization [8.409434654561789]
  We develop a class of mechanisms that enjoy non-asymptotic and unconditional optimality guarantees. Our upper (primal) bounds correspond to implementable perturbations whose suboptimality can be bounded by our lower (dual) bounds. Our numerical experiments demonstrate that our perturbations can outperform the previously best results from the literature on artificial as well as standard benchmark problems.
  arXiv  Detail & Related papers  (2023-04-25T09:31:47Z)
• On Differentially Private Online Predictions [74.01773626153098]
  We introduce an interactive variant of joint differential privacy towards handling online processes. We demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing. We then study the cost of interactive joint privacy in the basic setting of online classification.
  arXiv  Detail & Related papers  (2023-02-27T19:18:01Z)
• 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)
• Private Domain Adaptation from a Public Source [48.83724068578305]
  We design differentially private discrepancy-based algorithms for adaptation from a source domain with public labeled data to a target domain with unlabeled private data. Our solutions are based on private variants of Frank-Wolfe and Mirror-Descent algorithms.
  arXiv  Detail & Related papers  (2022-08-12T06:52:55Z)
• Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints [46.944178305032146]
  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.
  arXiv  Detail & Related papers  (2020-10-30T20:06:35Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)
• Breaking the Communication-Privacy-Accuracy Trilemma [19.399122892615573]
  Two major challenges in distributed learning are preserving the privacy of local samples and communicating them efficiently to a central server. We develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency.
  arXiv  Detail & Related papers  (2020-07-22T22:43:01Z)

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.