Anonymized Histograms in Intermediate Privacy Models

• URL: http://arxiv.org/abs/2210.15178v1
• Date: Thu, 27 Oct 2022 05:11:00 GMT
• Title: Anonymized Histograms in Intermediate Privacy Models
• Authors: Badih Ghazi and Pritish Kamath and Ravi Kumar and Pasin Manurangsi
• Abstract summary: 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.
• Score: 54.32252900997422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of privately computing the anonymized histogram (a.k.a. unattributed histogram), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$- and $\ell_2^2$-errors of $O_\varepsilon(\sqrt{n})$ in the central model of differential privacy (DP). In this work, we provide an algorithm with a nearly matching error guarantee of $\tilde{O}_\varepsilon(\sqrt{n})$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.

Related papers

• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  We study the problem of computing pairwise statistics, i.e., ones of the form $binomn2-1 sum_i ne j f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc.
  arXiv  Detail & Related papers  (2024-06-24T04:06:09Z)
• Transfer Learning for Latent Variable Network Models [18.31057192626801]
  We study transfer learning for estimation in latent variable network models. We show that if the latent variables are shared, then vanishing error is possible. Our algorithm achieves $o(1)$ error and does not assume a parametric form on the source or target networks.
  arXiv  Detail & Related papers  (2024-06-05T16:33:30Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  We revisit the problem of sparse linear regression in the local differential privacy (LDP) model. We propose an innovative NLDP algorithm, the very first of its kind for the problem. Our findings reveal fundamental differences between the non-private case, central DP model, and local DP model in the sparse linear regression problem.
  arXiv  Detail & Related papers  (2023-10-11T10:34:52Z)
• PLAN: Variance-Aware Private Mean Estimation [12.452663855242344]
  Differentially private mean estimation is an important building block in privacy-preserving algorithms for data analysis and machine learning. We show how to exploit skew in the vector $boldsymbolsigma$, obtaining a (zero-digma) differentially private mean estimate with $ell$ error. To verify the effectiveness of PLAN, we empirically evaluate accuracy on both synthetic and real world data.
  arXiv  Detail & Related papers  (2023-06-14T21:04:50Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
  We show that the histogram testing problem has sample complexity $widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$.
  arXiv  Detail & Related papers  (2022-07-14T01:24:01Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.