A Unifying Privacy Analysis Framework for Unknown Domain Algorithms in Differential Privacy

• URL: http://arxiv.org/abs/2309.09170v2
• Date: Thu, 1 Aug 2024 20:58:02 GMT
• Title: A Unifying Privacy Analysis Framework for Unknown Domain Algorithms in Differential Privacy
• Authors: Ryan Rogers,
• Abstract summary: We revisit some of the existing differentially private algorithms for releasing histograms over unknown domains. The main practical advantage of releasing histograms over an unknown domain is that the algorithm does not need to fill in missing labels. We present a unified framework for the privacy analyses of several existing algorithms.
• Score: 1.5773159234875098
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There are many existing differentially private algorithms for releasing histograms, i.e. counts with corresponding labels, in various settings. Our focus in this survey is to revisit some of the existing differentially private algorithms for releasing histograms over unknown domains, i.e. the labels of the counts that are to be released are not known beforehand. The main practical advantage of releasing histograms over an unknown domain is that the algorithm does not need to fill in missing labels because they are not present in the original histogram but in a hypothetical neighboring dataset could appear in the histogram. However, the challenge in designing differentially private algorithms for releasing histograms over an unknown domain is that some outcomes can clearly show which input was used, clearly violating privacy. The goal then is to show that the differentiating outcomes occur with very low probability. We present a unified framework for the privacy analyses of several existing algorithms. Furthermore, our analysis uses approximate concentrated differential privacy from Bun and Steinke'16, which can improve the privacy loss parameters rather than using differential privacy directly, especially when composing many of these algorithms together in an overall system.

Related papers

• Locally Private Histograms in All Privacy Regimes [14.453502159917525]
  We investigate locally private histograms, and the very related distribution learning task, in a medium-to-low privacy regime. We obtain a protocol for histograms in the emphlocal model of differential privacy, with accuracy matching previous algorithms but significantly better message and communication complexity. Our theoretical findings emerge from a novel analysis, which appears to improve bounds across the board for the locally private histogram problem.
  arXiv  Detail & Related papers  (2024-08-09T06:22:45Z)
• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph. We conclude with additive error lower bounds for edge-privacy in the fully dynamic setting.
  arXiv  Detail & Related papers  (2024-07-24T20:15:07Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  We study the space complexity of the two related fields of differential privacy and adaptive data analysis. We show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy. The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries.
  arXiv  Detail & Related papers  (2023-02-11T14:45:31Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  We provide an algorithm with a nearly matching error guarantee of $tildeO_varepsilon(sqrtn)$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram.
  arXiv  Detail & Related papers  (2022-10-27T05:11:00Z)
• Stochastic Differentially Private and Fair Learning [7.971065005161566]
  We provide the first differentially private algorithm for fair learning that is guaranteed to converge. Our framework is flexible enough to permit different fairness, including demographic parity and equalized odds. Our algorithm can be applied to non-binary classification tasks with multiple (non-binary) sensitive attributes.
  arXiv  Detail & Related papers  (2022-10-17T06:54:57Z)
• 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)
• 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)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss [34.66940399825547]
  Industry has widely adopted a simple algorithm: Gradient Descent with noise (a.k.a. Gradient Langevin Dynamics) Questions about this algorithm's privacy loss remain open -- even in the seemingly simple setting of smooth convex losses over a bounded domain. We characterize the differential privacy up to a constant factor and show that after a small burn-in period, running SGD longer leaks no further privacy.
  arXiv  Detail & Related papers  (2022-05-27T02:09:55Z)
• Differentially Private Densest Subgraph Detection [8.290536618677235]
  In many domains, the network is private, and returning a densest subgraph can reveal information about the network. We study the densest subgraph problem in the edge privacy model, in which the edges of the graph are private. We show that our algorithms have an additive approximation guarantee.
  arXiv  Detail & Related papers  (2021-05-27T16:36:03Z)
• Robust and Differentially Private Mean Estimation [40.323756738056616]
  Differential privacy has emerged as a standard requirement in a variety of applications ranging from the U.S. Census to data collected in commercial devices. An increasing number of such databases consist of data from multiple sources, not all of which can be trusted. This leaves existing private analyses vulnerable to attacks by an adversary who injects corrupted data.
  arXiv  Detail & Related papers  (2021-02-18T05:02:49Z)

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.