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

differential privacyrange countingcombinatorial discrepancy

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

(19)

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