Related papers: Privately Counting Partially Ordered Data

Privately Counting Partially Ordered Data

URL: http://arxiv.org/abs/2410.06881v1
Date: Wed, 9 Oct 2024 13:43:35 GMT
Title: Privately Counting Partially Ordered Data
Authors: Matthew Joseph, Mónica Ribero, Alexander Yu,
Abstract summary: We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d2)$.
Score: 50.98561191019676
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d^2)$. Experiments show that, depending on the partial order in question, our solution dominates existing pure differentially private mechanisms, and can reduce their error by an order of magnitude or more.

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)
Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
arXiv Detail & Related papers (2024-01-17T09:23:25Z)
Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
We consider the problem of clustering privately a dataset in $mathbbRd$ that undergoes both insertion and deletion of points. We give an $varepsilon$-differentially private clustering mechanism for the $k$-means objective under continual observation.
arXiv Detail & Related papers (2023-07-07T07:23:56Z)
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)
Private Query Release via the Johnson-Lindenstrauss Transform [93.20051580730234]
We introduce a new method for releasing answers to statistical queries with differential privacy. The key idea is to randomly project the query answers to a lower dimensional space. We answer the projected queries using a simple noise-adding mechanism, and lift the answers up to the original dimension.
arXiv Detail & Related papers (2022-08-15T19:19:16Z)
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)
Tight and Robust Private Mean Estimation with Few Users [16.22135057266913]
We study high-dimensional mean estimation under user-level differential privacy. We design an $(eps,delta)$-differentially private mechanism using as few users as possible.
arXiv Detail & Related papers (2021-10-22T16:02:21Z)
Differentially Private Approximate Quantiles [27.950292359069216]
In this work we study the problem of differentially private (DP) quantiles. We want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP.
arXiv Detail & Related papers (2021-10-11T17:19:27Z)
Differentially Private Quantiles [12.917299605014419]
We propose an instance of the exponential mechanism that simultaneously estimates $m$ quantiles from $n$ data points. Our method significantly outperforms the current state of the art on both real and synthetic data.
arXiv Detail & Related papers (2021-02-16T16:02:59Z)
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)

This list is automatically generated from the titles and abstracts of the papers in this site.