Private Counting of Distinct Elements in the Turnstile Model and Extensions

• URL: http://arxiv.org/abs/2408.11637v1
• Date: Wed, 21 Aug 2024 14:06:22 GMT
• Title: Private Counting of Distinct Elements in the Turnstile Model and Extensions
• Authors: Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner,
• Abstract summary: We show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level $(epsilon,delta)$-differential privacy. Our second result is a bound which shows that for a large class of algorithms, the lower bound from item-level differential privacy extends to event-level differential privacy.
• Score: 2.5200018924833327
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level $(\epsilon,\delta)$-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level $(\epsilon,\delta)$-differential privacy and item-level $\epsilon$-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023].

Related papers

• Fully Dynamic Graph Algorithms with Edge Differential Privacy [1.4732811715354455]
  We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only. We give upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems.
  arXiv  Detail & Related papers  (2024-09-26T08:17:49Z)
• Differentially Private Multiway and $k$-Cut [5.893651469750359]
  We introduce edge-differentially private algorithms that achieve nearly optimal performance for minimum $k$-cut and multiway cut problems. For the minimum $k$-cut problem, our algorithms leverage a known bound on the number of approximate $k$-cuts, resulting in a private algorithm with optimal additive error $O(klog n)$ for fixed privacy parameter.
  arXiv  Detail & Related papers  (2024-07-09T14:46:33Z)
• Making Old Things New: A Unified Algorithm for Differentially Private Clustering [6.320600791108065]
  We show that a 20-year-old algorithm can be slightly modified to work for any of these models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them.
  arXiv  Detail & Related papers  (2024-06-17T15:31:53Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  We consider the example-scarce regime, where each user has only a few examples, and obtain the following results. For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. We present a simple technique for adapting the exponential mechanism [McSherry, Talwar FOCS 2007] to the user-level setting.
  arXiv  Detail & Related papers  (2023-09-21T21:51:55Z)
• Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation [3.9476868147424162]
  We show that every differentially private mechanism that handles insertions and deletions has worst-case additive error at least $T1/4$ even under a relatively weak, event-level privacy definition. We present an item-level differentially private mechanism that, for all turnstile streams with maximum flippancy $w$, continually outputs the number of distinct elements with an $O(sqrtw cdot polylog T)$ additive error.
  arXiv  Detail & Related papers  (2023-06-11T16:54:39Z)
• Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
  We show that a simple invocation of $textttAboveThreshold$ can give more accurate and robust estimates on the highest quantiles. We show that an improved analysis of $textttAboveThreshold$ can improve the privacy guarantees for the widely used Sparse Vector Technique.
  arXiv  Detail & Related papers  (2023-05-02T03:23:07Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)

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.