Optimal private halfspace counting via discrepancy

DOI10.1145/2213977.2214090MaRDI QIDQ5415550zbMATH OpenOpenAlexFDO

Authors

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.5453

zbMATH Keywords

combinatorial discrepancydifferential privacyrange counting

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 $pinP$, and a range space $calRsubseteq{2}^P$. Given a query range $RincalR$, the target output is $R(vecx)=su{m}_{pinR}{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((logn{)}^{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.

Recommendations

• Approximate halfspace range counting
• On the geometry of differential privacy
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard

Cited in

(21)

• Unconditionally secure disjointness tests for private datasets
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Answering n^2+o(1) counting queries with differential privacy is hard
• Approximate shared-memory counting despite a strong adversary
• An improved private mechanism for small databases
• Satisfiability modulo counting
• Comment
• Practical low-dimensional halfspace range space sampling
• The complexity of differential privacy
• Computing approximate statistical discrepancy
• Set-codes with small intersections and small discrepancies
• On the hereditary discrepancy of homogeneous arithmetic progressions
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• How to Find a Point in the Convex Hull Privately
• Differentially private range query on shortest paths
• A hierarchy of constant communication complexity
• Factorization norms and an inverse theorem for MaxCut
• The discrepancy of shortest paths
• Separation of the factorization norm and randomized communication complexity
• Approximate range counting under differential privacy
• Computer-aided proof of Erdős discrepancy properties

This page was built for publication: Optimal private halfspace counting via discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415550)