Optimal Private Halfspace Counting via Discrepancy

Details Optimal Private Halfspace Counting via Discrepancy Optimal Private Halfspace Counting via Discrepancy

2012-03-24

arxiv.org/abs/1203.5453v1

Computer Science

Data Structures and Algorithms

Scientific paper

A range counting problem is specified by a set $P$ of size $|P| = n$ of points in $\mathbb{R}^d$, an integer weight $x_p$ associated to each point $p \in P$, and a range space ${\cal R} \subseteq 2^{P}$. Given a query range $R \in {\cal R}$, the target output is $R(\vec{x}) = \sum_{p \in R}{x_p}$. Range counting for different range spaces is a central problem in Computational Geometry. We study $(\epsilon, \delta)$-differentially private algorithms for range counting. Our main results are for the range space given by hyperplanes, that is, the halfspace counting problem. We present an $(\epsilon, \delta)$-differentially private algorithm for halfspace counting in $d$ dimensions which achieves $O(n^{1-1/d})$ average squared error. This contrasts with the $\Omega(n)$ lower bound established by the classical result of Dinur and Nissim [PODS 2003] for arbitrary subset counting queries. We also show a matching lower bound on average squared error for any $(\epsilon, \delta)$-differentially private algorithm for halfspace counting. Both bounds are obtained using discrepancy theory. For the lower bound, we use a modified discrepancy measure and bound approximation of $(\epsilon, \delta)$-differentially private algorithms for range counting queries in terms of this discrepancy. We also relate the modified discrepancy measure to classical combinatorial discrepancy, which allows us to exploit known discrepancy lower bounds. This approach also yields a lower bound of $\Omega((\log n)^{d-1})$ for $(\epsilon, \delta)$-differentially private orthogonal range counting in $d$ dimensions, the first known superconstant lower bound for this problem. For the upper bound, we use an approach inspired by partial coloring methods for proving discrepancy upper bounds, and obtain $(\epsilon, \delta)$-differentially private algorithms for range counting with polynomially bounded shatter function range spaces.

Affiliated with

Also associated with

No associations

Rating

Optimal Private Halfspace Counting via Discrepancy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Private Halfspace Counting via Discrepancy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Private Halfspace Counting via Discrepancy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-74769