Improved Matrix Gaussian Mechanism for Differential Privacy

• URL: http://arxiv.org/abs/2104.14808v1
• Date: Fri, 30 Apr 2021 07:44:53 GMT
• Title: Improved Matrix Gaussian Mechanism for Differential Privacy
• Authors: Jungang Yang, Liyao Xiang, Weiting Li, Wei Liu, Xinbing Wang
• Abstract summary: Differential privacy (DP) mechanisms are conventionally developed for scalar values, not for structural data like matrices. Our work proposes Improved Matrix Gaussian Mechanism (IMGM) for matrix-valued DP, based on the necessary and sufficient condition of $ (varepsilon,delta) $-differential privacy. Among the legitimate noise distributions for matrix-valued DP, we find the optimal one turns out to be i.i.d. Experiments on a variety of models and datasets also verify that IMGM yields much higher utility than the state-of-the-art mechanisms at the same privacy guarantee
• Score: 29.865497421453917
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The wide deployment of machine learning in recent years gives rise to a great demand for large-scale and high-dimensional data, for which the privacy raises serious concern. Differential privacy (DP) mechanisms are conventionally developed for scalar values, not for structural data like matrices. Our work proposes Improved Matrix Gaussian Mechanism (IMGM) for matrix-valued DP, based on the necessary and sufficient condition of $ (\varepsilon,\delta) $-differential privacy. IMGM only imposes constraints on the singular values of the covariance matrices of the noise, which leaves room for design. Among the legitimate noise distributions for matrix-valued DP, we find the optimal one turns out to be i.i.d. Gaussian noise, and the DP constraint becomes a noise lower bound on each element. We further derive a tight composition method for IMGM. Apart from the theoretical analysis, experiments on a variety of models and datasets also verify that IMGM yields much higher utility than the state-of-the-art mechanisms at the same privacy guarantee.

Related papers

• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• On the Privacy of Selection Mechanisms with Gaussian Noise [44.577599546904736]
  We revisit the analysis of Report Noisy Max and Above Threshold with Gaussian noise. We find that it is possible to provide pure ex-ante DP bounds for Report Noisy Max and pure ex-post DP bounds for Above Threshold.
  arXiv  Detail & Related papers  (2024-02-09T02:11:25Z)
• Privacy Amplification for Matrix Mechanisms [18.13715687378337]
  "MMCC" is the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. We show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.
  arXiv  Detail & Related papers  (2023-10-24T05:16:52Z)
• Less is More: Revisiting the Gaussian Mechanism for Differential Privacy [8.89234867625102]
  Differential privacy via output perturbation has been a de facto standard for releasing query or computation results on sensitive data. We identify that all existing Gaussian mechanisms suffer from the curse of full-rank covariance matrices.
  arXiv  Detail & Related papers  (2023-06-04T04:14:38Z)
• Differential Privacy with Higher Utility by Exploiting Coordinate-wise Disparity: Laplace Mechanism Can Beat Gaussian in High Dimensions [9.20186865054847]
  We study the i.n.i.d. Gaussian and Laplace mechanisms and obtain the conditions under which these mechanisms guarantee privacy. We show how the i.n.i.d. noise can improve the performance in private (a) coordinate descent, (b) principal component analysis, and (c) deep learning with group clipping.
  arXiv  Detail & Related papers  (2023-02-07T14:54:20Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning [18.55306294638515]
  We introduce new differentially private (DP) mechanisms for computation-based machine learning (ML) with multiple passes (epochs) over a dataset. We formalize the problem of DP mechanisms for adaptive streams with multiple participations and introduce a non-trivial extension of online matrix factorization DP mechanisms.
  arXiv  Detail & Related papers  (2022-11-12T00:41:11Z)
• A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity index [61.675604648670095]
  We argue that the three prevailing interpretations of the GM, namely $(varepsilon, delta)$-DP, f-DP and R'enyi DP can be expressed by using a single parameter $psi$, which we term the sensitivity index. $psi$ uniquely characterises the GM and its properties by encapsulating its two fundamental quantities: the sensitivity of the query and the magnitude of the noise perturbation.
  arXiv  Detail & Related papers  (2021-09-22T06:20:01Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)
• Cauchy-Schwarz Regularized Autoencoder [68.80569889599434]
  Variational autoencoders (VAE) are a powerful and widely-used class of generative models. We introduce a new constrained objective based on the Cauchy-Schwarz divergence, which can be computed analytically for GMMs. Our objective improves upon variational auto-encoding models in density estimation, unsupervised clustering, semi-supervised learning, and face analysis.
  arXiv  Detail & Related papers  (2021-01-06T17:36:26Z)

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.