Privacy Amplification for Matrix Mechanisms

• URL: http://arxiv.org/abs/2310.15526v2
• Date: Sat, 4 May 2024 18:49:50 GMT
• Title: Privacy Amplification for Matrix Mechanisms
• Authors: Christopher A. Choquette-Choo, Arun Ganesh, Thomas Steinke, Abhradeep Thakurta,
• Abstract summary: "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.
• Score: 18.13715687378337
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Privacy amplification exploits randomness in data selection to provide tighter differential privacy (DP) guarantees. This analysis is key to DP-SGD's success in machine learning, but, is not readily applicable to the newer state-of-the-art algorithms. This is because these algorithms, known as DP-FTRL, use the matrix mechanism to add correlated noise instead of independent noise as in DP-SGD. In this paper, we propose "MMCC", the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. MMCC is nearly tight in that it approaches a lower bound as $\epsilon\to0$. To analyze correlated outputs in MMCC, we prove that they can be analyzed as if they were independent, by conditioning them on prior outputs. Our "conditional composition theorem" has broad utility: we use it to show that the noise added to binary-tree-DP-FTRL can asymptotically match the noise added to DP-SGD with amplification. Our amplification algorithm also has practical empirical utility: we show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.

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)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• 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)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Using Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) to ensure Differential Privacy (DP) comes at the cost of model performance degradation. We propose a new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on R'enyi DP.
  arXiv  Detail & Related papers  (2023-11-24T17:56:44Z)
• (Amplified) Banded Matrix Factorization: A unified approach to private training [15.922315074913255]
  Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications. We show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings.
  arXiv  Detail & Related papers  (2023-06-13T21:53:17Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• 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)
• Improved Matrix Gaussian Mechanism for Differential Privacy [29.865497421453917]
  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
  arXiv  Detail & Related papers  (2021-04-30T07:44:53Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Differentially Private ADMM Algorithms for Machine Learning [38.648113004535155]
  We study efficient differentially private alternating direction methods of multipliers (ADMM) via gradient perturbation. We propose the first differentially private ADMM (DP-ADMM) algorithm with performance guarantee of $(epsilon,delta)$-differential privacy.
  arXiv  Detail & Related papers  (2020-10-31T01:37:24Z)

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.