Differentially Private Set Representations

• URL: http://arxiv.org/abs/2501.16680v1
• Date: Tue, 28 Jan 2025 03:29:00 GMT
• Title: Differentially Private Set Representations
• Authors: Sarvar Patel, Giuseppe Persiano, Joon Young Seo, Kevin Yeo,
• Abstract summary: We study the problem of differentially private (DP) mechanisms for representing sets of size $k$ from a large universe. Our first construction creates $(epsilon,delta)$-DP representations with error probability of $1/(eepsilon + 1)$ using space at most $1.05 k epsilon cdot log(e)$ bits. We also present a second algorithm for pure $epsilon$-DP representations with the same error using space at most $k epsilon cdot log(e)$ bits
• Score: 13.576656322669098
• License:
• Abstract: We study the problem of differentially private (DP) mechanisms for representing sets of size $k$ from a large universe. Our first construction creates $(\epsilon,\delta)$-DP representations with error probability of $1/(e^\epsilon + 1)$ using space at most $1.05 k \epsilon \cdot \log(e)$ bits where the time to construct a representation is $O(k \log(1/\delta))$ while decoding time is $O(\log(1/\delta))$. We also present a second algorithm for pure $\epsilon$-DP representations with the same error using space at most $k \epsilon \cdot \log(e)$ bits, but requiring large decoding times. Our algorithms match our lower bounds on privacy-utility trade-offs (including constants but ignoring $\delta$ factors) and we also present a new space lower bound matching our constructions up to small constant factors. To obtain our results, we design a new approach embedding sets into random linear systems deviating from most prior approaches that inject noise into non-private solutions.

Related papers

• Nearly-Linear Time Seeded Extractors with Short Seeds [9.896415488558036]
  Existing constructions of seeded extractors with short seed length and large output length run in time. We show that an appropriate combination of modern condensers and classical approaches for constructing seeded extractors for high min-entropy sources yields strong extractors. We also give an instantiation of Trevisan's extractor that can be evaluated in truly linear time in the RAM model.
  arXiv  Detail & Related papers  (2024-11-12T01:19:35Z)
• Differentially Private Kernel Density Estimation [11.526850085349155]
  We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE) We study the mathematical problem: given a similarity function $f$ and a private dataset $X subset mathbbRd$, our goal is to preprocess $X$ so that for any query $yinmathbbRd$, we approximate $sum_x in X f(x, y)$ in a differentially private fashion.
  arXiv  Detail & Related papers  (2024-09-03T08:01:19Z)
• Profile Reconstruction from Private Sketches [13.929335175122265]
  Given a multiset of $n$ items from $mathcalD$, the emphprofile reconstruction problem is to estimate, for $t = 0, 1, dots, n$, the fraction $vecf[t]$ of items in $mathcalD$ that appear exactly $tfty times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset. We show how to speed up their LP-based technique
  arXiv  Detail & Related papers  (2024-06-03T09:51:28Z)
• Differentially Private Approximate Pattern Matching [0.0]
  We consider the $k$-approximate pattern matching problem under differential privacy. The goal is to report or count allimate variants of a given string $S$ which have a Hamming distance at most $k$ to a pattern $P$. We give 1) an $epsilon$-differentially private algorithm with an additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) an $epsilon$-differentially private algorithm with an additive error $O(epsilon-1
  arXiv  Detail & Related papers  (2023-11-13T15:53:45Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  We give an $(varepsilon,delta)$-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.
  arXiv  Detail & Related papers  (2021-06-05T14:11:01Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• 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.