Privacy-Aware Randomized Quantization via Linear Programming

• URL: http://arxiv.org/abs/2406.02599v1
• Date: Sat, 1 Jun 2024 18:40:08 GMT
• Title: Privacy-Aware Randomized Quantization via Linear Programming
• Authors: Zhongteng Cai, Xueru Zhang, Mohammad Mahdi Khalili,
• Abstract summary: We propose a family of quantization mechanisms that is unbiased and differentially private. Our proposed mechanism can attain a better privacy-accuracy trade-off compared to baselines.
• Score: 13.002534825666219
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Differential privacy mechanisms such as the Gaussian or Laplace mechanism have been widely used in data analytics for preserving individual privacy. However, they are mostly designed for continuous outputs and are unsuitable for scenarios where discrete values are necessary. Although various quantization mechanisms were proposed recently to generate discrete outputs under differential privacy, the outcomes are either biased or have an inferior accuracy-privacy trade-off. In this paper, we propose a family of quantization mechanisms that is unbiased and differentially private. It has a high degree of freedom and we show that some existing mechanisms can be considered as special cases of ours. To find the optimal mechanism, we formulate a linear optimization that can be solved efficiently using linear programming tools. Experiments show that our proposed mechanism can attain a better privacy-accuracy trade-off compared to baselines.

Related papers

• Private Language Models via Truncated Laplacian Mechanism [18.77713904999236]
  We propose a novel private embedding method called the high dimensional truncated Laplacian mechanism. We show that our method has a lower variance compared to the previous private word embedding methods. Remarkably, even in the high privacy regime, our approach only incurs a slight decrease in utility compared to the non-private scenario.
  arXiv  Detail & Related papers  (2024-10-10T15:25:02Z)
• Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification [54.1447806347273]
  Amplification by subsampling is one of the main primitives in machine learning with differential privacy. We propose the first general framework for deriving mechanism-specific guarantees. We analyze how subsampling affects the privacy of groups of multiple users.
  arXiv  Detail & Related papers  (2024-03-07T19:36:05Z)
• The Symmetric alpha-Stable Privacy Mechanism [0.0]
  We present novel analysis of the Symmetric alpha-Stable (SaS) mechanism. We prove that the mechanism is purely differentially private while remaining closed under convolution.
  arXiv  Detail & Related papers  (2023-11-29T16:34:39Z)
• Bounded and Unbiased Composite Differential Privacy [25.427802467876248]
  The objective of differential privacy (DP) is to protect privacy by producing an output distribution that is indistinguishable between two neighboring databases. Existing solutions attempt to address this issue by employing post-processing or truncation techniques. We propose a novel differentially private mechanism which uses a composite probability density function to generate bounded and unbiased outputs.
  arXiv  Detail & Related papers  (2023-11-04T04:43:47Z)
• Adaptive Privacy Composition for Accuracy-first Mechanisms [55.53725113597539]
  Noise reduction mechanisms produce increasingly accurate answers. Analysts only pay the privacy cost of the least noisy or most accurate answer released. There has yet to be any study on how ex-post private mechanisms compose. We develop privacy filters that allow an analyst to adaptively switch between differentially private and ex-post private mechanisms.
  arXiv  Detail & Related papers  (2023-06-24T00:33:34Z)
• 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)
• 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)
• Differentially Private Estimation of Hawkes Process [81.20710494974281]
  We introduce a rigorous definition of differential privacy for event stream data based on a discretized representation of the Hawkes process. We then propose two differentially private optimization algorithms, which can efficiently estimate Hawkes process models with the desired privacy and utility guarantees.
  arXiv  Detail & Related papers  (2022-09-15T13:59:23Z)
• DP2-Pub: Differentially Private High-Dimensional Data Publication with Invariant Post Randomization [58.155151571362914]
  We propose a differentially private high-dimensional data publication mechanism (DP2-Pub) that runs in two phases. splitting attributes into several low-dimensional clusters with high intra-cluster cohesion and low inter-cluster coupling helps obtain a reasonable privacy budget. We also extend our DP2-Pub mechanism to the scenario with a semi-honest server which satisfies local differential privacy.
  arXiv  Detail & Related papers  (2022-08-24T17:52:43Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics [2.614355818010333]
  We provide strong privacy loss bounds when an analyst may select pure DP, bounded range (e.g. exponential mechanisms) or concentrated DP mechanisms in any order. We also provide optimal privacy loss bounds that apply when an analyst can select pure DP and bounded range mechanisms in a batch.
  arXiv  Detail & Related papers  (2020-04-15T17:33:10Z)

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.