Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacy

• URL: http://arxiv.org/abs/2301.00301v1
• Date: Sat, 31 Dec 2022 22:22:53 GMT
• Title: Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacy
• Authors: Rachel Redberg, Yuqing Zhu, Yu-Xiang Wang
• Abstract summary: ''Propose-Test-Release'' (PTR) is a classic recipe for designing differentially private (DP) algorithms. We extend PTR to a more general setting by privately testing data-dependent privacy losses rather than local sensitivity.
• Score: 16.374676154278614
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ''Propose-Test-Release'' (PTR) framework is a classic recipe for designing differentially private (DP) algorithms that are data-adaptive, i.e. those that add less noise when the input dataset is nice. We extend PTR to a more general setting by privately testing data-dependent privacy losses rather than local sensitivity, hence making it applicable beyond the standard noise-adding mechanisms, e.g. to queries with unbounded or undefined sensitivity. We demonstrate the versatility of generalized PTR using private linear regression as a case study. Additionally, we apply our algorithm to solve an open problem from ''Private Aggregation of Teacher Ensembles (PATE)'' -- privately releasing the entire model with a delicate data-dependent analysis.

Related papers

• Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
  Differential privacy (DP) can measure privacy loss by observing the changes in the distribution caused by the inclusion of individuals in the target dataset. DP has been prominent in safeguarding datasets in machine learning in industry giants like Apple and Google. We propose per-instance DP (pDP) as a constraint, measuring privacy loss for each data instance and optimizing noise tailored to individual instances.
  arXiv  Detail & Related papers  (2024-04-24T06:51:16Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• Better Private Linear Regression Through Better Private Feature Selection [18.884088349732973]
  We introduce a differentially private feature selection method based on Kendall rank correlation. We prove a utility guarantee for the setting where features are normally distributed. We find that adding this private feature selection step before regression significantly broadens the applicability of plug-and-play'' private linear regression algorithms.
  arXiv  Detail & Related papers  (2023-06-01T17:21:10Z)
• Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance [35.653510597396114]
  Differentially private gradient descent privatizes model training by injecting noise into each iteration, where the noise magnitude increases with the number of model parameters. Recent works suggest that we can reduce the noise by leveraging public data for private machine learning, by projecting gradients onto a subspace prescribed by the public data. We give an algorithm for selecting a public dataset by measuring a low-dimensional subspace distance between gradients of the public and private examples.
  arXiv  Detail & Related papers  (2023-03-02T13:36:28Z)
• MAPS: A Noise-Robust Progressive Learning Approach for Source-Free Domain Adaptive Keypoint Detection [76.97324120775475]
  Cross-domain keypoint detection methods always require accessing the source data during adaptation. This paper considers source-free domain adaptive keypoint detection, where only the well-trained source model is provided to the target domain.
  arXiv  Detail & Related papers  (2023-02-09T12:06:08Z)
• Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning [34.091112544190125]
  Propose-Test-Release (PTR) is a differential privacy framework that works with local sensitivity of functions, instead of their global sensitivity. We show that PTR and our theoretical results can be used to design differentially private variants for byzantine robust training algorithms.
  arXiv  Detail & Related papers  (2022-09-16T04:48:22Z)
• Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank [74.53857412207034]
  We propose an algorithm which outputs an approximate PPR and has provably bounded sensitivity to input edges. Our sensitivity-bounded PPR directly implies private algorithms for several tools of graph learning, such as, differentially private (DP) PPR ranking, DP node classification, and DP node embedding.
  arXiv  Detail & Related papers  (2022-07-14T14:08:59Z)
• Control Variates for Slate Off-Policy Evaluation [112.35528337130118]
  We study the problem of off-policy evaluation from batched contextual bandit data with multidimensional actions. We obtain new estimators with risk improvement guarantees over both the PI and self-normalized PI estimators.
  arXiv  Detail & Related papers  (2021-06-15T06:59:53Z)
• RDP-GAN: A R\'enyi-Differential Privacy based Generative Adversarial Network [75.81653258081435]
  Generative adversarial network (GAN) has attracted increasing attention recently owing to its impressive ability to generate realistic samples with high privacy protection. However, when GANs are applied on sensitive or private training examples, such as medical or financial records, it is still probable to divulge individuals' sensitive and private information. We propose a R'enyi-differentially private-GAN (RDP-GAN), which achieves differential privacy (DP) in a GAN by carefully adding random noises on the value of the loss function during training.
  arXiv  Detail & Related papers  (2020-07-04T09:51:02Z)
• 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.