Optimal private halfspace counting via discrepancy

By S. Muthu Muthukrishnan, Aleksandar Nikolov. 2012

89 citations recorded by the source corpus.

A range counting problem is specified by a set P of size |P| = n of points in Rd, an integer weight xp associated to each point p ∈ P, and a range space R ⊆ 2P. Given a query range R ∈ R, the output is R(x) = ∑p ∈ Rxp. The average squared error of an algorithm A is 1/|R|∑R ∈ R((A(R, x) - R(x)))2. Range counting for different range spaces is a central problem in Computational Geometry. We study (ε, δ)-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 (ε, δ)-differentially private algorithm for halfspace counting in d dimensions which is O(n1-1/d) approximate for average squared error. This contrasts with the Ω(n) lower bound established by the classical result of Dinur and Nissim on approximation for arbitrary subset counting queries. We also show a matching lower bound of Ω(n1-1/d) approximation for any (ε, δ)-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 (ε, δ)-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 Ω((log n)d-1) for (ε, δ)-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 (ε, δ)-differentially private algorithms for range counting with polynomially bounded shatter function range spaces.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, background): “Another line of work proves lower bounds in differential privacy via reconstruction attacks [13], [32], [33], [34], [35], [36], [37].”
Robust Traceability from Trace Amounts (2015, background): “Since M does not see p j or z j , we can write q j = f ( x j ) for some f : The result now follows from Lemmata 7 and 9.”
The Power of Linear Reconstruction Attacks (2012, methodology): “Specifically, we consider a setting in which the same statistic (either1 or 2 above) is released about how the sensitive attribute relates to all subsets of sizek (out of a total ofd) nonsensitive boolean attributes.”
Why Statistical Agencies Need to Take Privacy-loss Budgets Seriously, and What It Means When They Do (2016, background): “…Fundamental Law of Information Recovery” Dwork and Roth, 2014 [link] Dwork, undated [link] Includes extensions found in Dwork, McSherry and Talwar (2007) [link] Muthukrishnan and Nikolov (2012) [link] Kasiviswanathan, Rudelson and Smith (2013) [link] Dwork, Smith, Steinke, Ullman, and…”
An Improved Private Mechanism for Small Databases (2015, background): “than the worst-case bounds. Some natural examples are queries counting the number of points in a line interval or a d-dimensional axis-aligned box [DNPR10, CSS10, XWG10], or a d-dimensional halfspace [MN12]. It is, therefore, desirable to have mechanisms whose error bounds adapt both to the query wo”
On the Power of Multiple Anonymous Messages (2019, unknown): “Meanwhile, a lower bound of Muthukrishnan and Nikolov [81] showed that for n « B , the error is lower bounded by Ω ` n q d ´ O p 1 q ˘ .”
On the Relation Between Identifiability, Differential Privacy, and Mutual-Information Privacy (2016, background): “Differential privacy, as an emerging analytical foundation for privacy-preserving data analysis, was developed by a line of work [1]–[3], and since then both interactive model (e.g., [1], [4]–[9]) and non-interactive model (e.g., [8], [10]–[15]) have been studied in the literature.”
On the relation between identifiability, differential privacy, and mutual-information privacy (2014, methodology): “In this paper we consider three different notions of privacy: identifiability, differential privacy and mutual-information privacy, so we denote the privacy–distortion functions under these three notions by ∗i , ∗ d and ∗ m, respectively.”
The Complexity of Differential Privacy (2017, methodology): “In this language, we have the theorem of Muthukrishnan and Nikolov [83]:”
Exposed! A Survey of Attacks on Private Data (2017, methodology): “The framework we use here was formulated by Muthukrishnan & Nikolov (2012), abstracting the idea in the proof of Theorem 1.”
Differentially Private Release and Learning of Threshold Functions (2015, background): “There is also a beautiful line of work on characterizing the 2-accuracy (rather than ∞-accuracy, which we consider in this work) achievable for query release in terms of other measures of the “complexity” of the family Q (such as “hereditary discrepancy”) [27], [5], [29], [30].”
Private Query Release Assisted by Public Data (2020, background): “The following lemma is an immediate corollary of the accuracy guarantee of the PMW algorithm [HR10, DR14].”