Optimal Private Halfspace Counting via Discrepancy

Introduction

A range counting problem is specified by a set $P$ of size $|P|=n$, and a range space $\mathcal{R}\subseteq 2^{P}$. Given a query range $R\in\mathcal{R}$, the output is $|\{p\in P\cap R\}|$. More generally, each point $p\in P$ has an integer weight $x_{p}$ and the range returns $R(\mathbf{x})=\sum_{p\in R}{x_{p}}$. This problem is fundamental in Computational Geometry and a workhorse in applications, for various examples of range spaces from axis-parallel boxes (orthogonal range counting), to regions bounded by hyperplanes (halfspace counting) and beyond (e.g., simplices). Orthogonal range counting is commonly used in databases and data analysis. Halfspace counting is not only interesting in itself, but general algebraic range counting can be “lifted” to a higher dimension and encoded as halfspace counting .

Surprisingly, very little is known about private range counting. Applying methods of differential privacy from first principles (Laplace noise and the basic composition theorem of differential privacy) will add large — variance $\Omega(n^{2})$ in the case of halfspace counting in the plane — noise to each output. More generally, let $\mathbf{A}$ be an incidence matrix for a range space $\mathcal{R}$ (i.e. a matrix whose rows are the indicator vectors of all ranges $R\in\mathcal{R}$) and let $\mathbf{x}$ be the weights. The problem of computing $\mathbf{A}\mathbf{x}$ is the range counting problem. The average squared error of an approximate algorithm $\mathcal{A}$ is $\frac{1}{|\mathcal{R}|}\|\mathcal{A}(\mathbf{x})-\mathbf{A}\mathbf{x}\|_{2}^{2}$. In general, we can consider this problem for any $\mathbf{A}\in\{0,1\}^{m\times n}$, not necessarily ones that correspond to natural ranges from some constant dimensional geometric space. This is the predicate counting problem, well-studied in differential privacy. Then it is known that no mechanism that has average squared error $o(n)$ can be $(\epsilon,\delta)$-differentially private . However, the lower bounds are obtained using random $\mathbf{A}$’s that will not correspond to specific range spaces of interest. No super-constant lower bounds are known against $(\varepsilon,\delta)$-differential privacy for natural problems like halfspace or orthogonal range counting in constant dimensional space. Constant lower bounds follow from the work of Roth as well as from reductions from lower bounds for conjunction queries.

Our results are for $(\varepsilon,\delta)$-differentially private range counting, and use the combinatorial structure of $\mathbf{A}$’s for range spaces. Our main application is halfspace counting, but our approach is general and yields other results too.

$\bullet$ (Halfspace counting upper bound) The (primal) shatter function of $\mathcal{R}$ is defined as $\pi_{\mathcal{R}}(s)=\max_{X\in{P\choose s}}|\mathcal{R}|_{X}|$ (i.e. the number of distinct sets in the restriction $\mathcal{R}|_{X}$). The shatter function of $\mathcal{R}$ defined by halfspaces in $d$-dimensions is bounded as $\pi_{\mathcal{R}}(s)=O(s^{d})$.

We show that there is an $(\varepsilon,\delta)$-differentially private range counting mechanism that achieves $O(n^{1-1/d})$ average squared error for range spaces with shatter function bounded by $O(s^{d})$, and therefore for $d$-dimensional halfspace range counting.

Our upper bound shows that previous lower bounds for general $\mathbf{A}$’s indeed do not apply to halfspace range counting. Our algorithm runs in time polynomial in $n$ and $m$. Previous work on this problem is incomparable. Work by Blum, Ligett and Roth gave a non-constructive squared error upper bound of $O(d^{2}n^{4/3})$ for range spaces with VC-dimension $d$ and a matching constructive bound for halfspace range counting for $(\varepsilon,0)$-differential privacy with a slightly different objective. Since the shatter function of a range space with VC-dimension $d$ is bounded by $O(s^{d})$, our result also implies a constructive approximation upper bound of $O(n^{1-1/d})$ for VC-dimension $d$ range spaces.

Our approach relies on prior work to decompose the range space into a logarithmic number of range spaces, some of them consisting only of small ranges, and some containing a small number of distinct ranges. We exploit this trade-off between maximum range size and number of distinct ranges by combining randomized response and Laplacian noise based differentially private mechanisms, but this balancing still leaves us with large noise in some cases. Nevertheless, we can bound the average privacy loss over the points $p\in P$. Our main idea is to use this approach to preserve privacy for most points $p\in P$; the shatter function bound does not increase for restrictions of $P$ and $\mathcal{R}$ and we can recurse on the remaining points of $P$. This argument is inspired by partial coloring methods used in discrepancy theory. $\blacksquare$

$\bullet$ (Range counting lower bound) For halfspace counting in $d$ dimensions, we show that any mechanism that has average squared error within $o(n^{1-1/d})$ is not $(\varepsilon,\delta)$-differentially private for any constant $\varepsilon$ and $\delta$. We prove this lower bound using a notion of discrepancy where, in contrast to the standard notion where $\{+1,-1\}$ colorings are considered, we allow $\{0,+1,-1\}$ colorings but subject to some budget constraints on $\{+1,-1\}$. The budget constraints allows us to relate this notion of discrepancy to the classical one. Once the approach via the correct notion of discrepancy is developed, the mechanics are simple. Lower bounds will follow from combinatorial analysis of the discrepancy of range spaces. For orthogonal range counting, our approach immediately gives a lower bound of $(\log n)^{d-O(1)}$ on the average squared error of any $(\varepsilon,\delta)$ differentially private mechanism. The best upper bound in this setting is the work of Chan, Shi, and Song who give an algorithm with average squared error $O((\log n)^{2d})$. No previous super-constant lower bounds are known for this problem even for large constant $d$. We note that proving a tight lower bound on the combinatorial discrepancy of axis-aligned boxes in $d$ dimensions is a major open problem in discrepancy theory, and any improvement to the current discrepancy lower bound will yield a corresponding improvement in lower bounds for privacy. $\blacksquare$

In Section 2 we review related prior work. In Section 3, we define concepts we need, including differential privacy and suitable notions of discrepancy. In Section 4, we present our lower bounds, and in Section 5, the upper bounds. We describe extensions and alternative algorithmic solutions in Section 6.

Prior Work

There is a rich and growing literature on solving counting problems while satisfying strong privacy guarantees. We will survey the prior work that is most relevant to our results.

In a seminal paper, Dinur and Nissim initiated the study of the limits of output perturbation in answering arbitrary counting queries privately. They showed that if an algorithm $\mathcal{A}$ satisfies $\|\mathcal{A}(\mathbf{x})-\mathbf{A}\mathbf{x}\|_{\infty}^{2}=o(n)$ for a random 0-1 matrix $\mathbf{A}$, then an adversary can reconstruct $\mathbf{x}$ almost exactly, implying that the algorithm is not $(\varepsilon,\delta)$-differentially private for any constant $\varepsilon,\delta$.Our methods based on discrepancy allow us to re-prove the lower bound of Dinur and Nissim, as well as the version of Dwork and Yekhanin that uses an explicit $\mathbf{A}$. There is relatively little prior work on negative results for $(\epsilon,\delta)$-differential privacy for natural restrictions of $\mathbf{A}$. An exception is the work on lower bounding the noise necessary to privately answer conjunction queries . Conjunction queries on a database with $d$ attributes can be reduced to answering orthogonal range counting or halfspace range counting queries in $d$ dimensions. When $d$ is constant, the lower bounds on conjunction queries imply a lower bound of $C^{d}$ (for an absolute constant $C>1$) on the average squared error neccessary to answer $d$-dimensional halfspace or orthogonal queries privately (here and in the remainder of this section we suppress dependence on $\varepsilon$, $\delta$, and the probability of failure). In other related work, Roth showed that linear queries with fat shattering dimension $D$ require squared noise $\Omega(D^{2})$ to preserve privacy. The fat shattering dimension reduces to the VC-dimension for counting queries, and has value $d+1$ for the range space of halfspaces in $d$ dimensions. No super-constant lower bounds were previously known for $(\varepsilon,\delta)$-differential privacy for the halfspace range counting or orthogonal range counting problems in constant dimensional space.

The study of private range counting for restricted range spaces was initiated with the work of Blum, Ligett, and Roth , who, using an argument based on epsilon nets, showed that queries of VC dimension $d$ can be answered with worst-case squared noise $O(d^{2}n^{4/3})$. Their algorithm is not computationally efficient, but they gave efficient algorithms with comparable guarantees for the interval range counting and halfspace range counting problems. Although their error bound is inferior to ours (when the size of the database is comparable to the universe size), the models are not directly comparable. While we consider a finite universe, they consider a continuous space, but give relaxed utility guarantes, namely that each query answer is accurate for a halfspace close to the query halfspace. Additionally, their algorithms satisfy the stronger notion of $(\varepsilon,0)$-differential privacy and accomodate the regime where $\|\mathbf{x}\|_{1}$ is public and bounded by $n$ and $P$ is much larger.

For interval queries, the work of Blum, Ligett, and Roth was subsequently improved by Xiao, Wang, and Gehrke (in the regime where database size and universe size are comparable), who gave a polylogarithmic noise upper bound via the wavelet transform. A related algorithm that achieves an average squared error upper bound of $O((\log n)^{3d})$ for $d$-dimensional orthogonal range counting was given by Chan, Shi, and Song . We note that if we relax the privacy guarantee of Chan, Shi, and Song to $(\varepsilon,\delta)$-differential privacy, their algorithm can be analyzed to provide average squared error $O(\log^{2d}n)$.

Much subsequent work has focused on answering $m$ arbitrary queries efficiently with squared error linear in $n$ and polylogarithmic in $m$ . A related line of work investigates the problem of answering conjunction queries with optimal error .

Prior work for $(\varepsilon,0)$-differential privacy. Stronger lower bounds can be shown when $\delta=0$, and there are known separations between the cases $\delta=0$ and $\delta>0$, even when $\delta$ is superpolynomially small . Hardt and Tulwar gave a lower bound for linear queries based on geometric properties of the query matrix $\mathbf{A}$. De simplified and extended their lower bound results. Blum, Ligett, and Roth showed that no $(\varepsilon,0)$-differentially private mechanism can answer interval queries with any nontrivial noise when the universe is continuous.

Discrepancy theory. For background in discrepancy theory we refer the reader to the books of Chazelle and Matous̆ek . Chazelle provides an overview of the applications of discrepancy theory to computer science, while Matous̆ek gives a survey of discrepancy theory results for geometric range spaces.

Geometric range counting. Geometric range counting and the closely related problems of range sums and range searching have a rich history in computational geometry. We refer the reader to the survey of Agarwal and Erickson for background.

Preliminaries

We typeset vectors and matrices as $\mathbf{x}$, $\mathbf{A}$ and their elements as $x_{j}$, $A_{ij}$. We denote the $i$-th row of $\mathbf{A}$ as $\mathbf{A}_{i*}$ and the $j$-th column as $\mathbf{A}_{*j}$. Given a matrix $\mathbf{A}$, the function $\operatorname{col}(\mathbf{A})$ equals the number of columns of $\mathbf{A}$. For a matrix $\mathbf{A}$ with $n$ columns, and a set $S\subseteq[n]$ we use $\mathbf{A}|_{S}$ to denote the submatrix of $\mathbf{A}$ consisting of the columns corresponding to elements of $S$ (with duplicated rows removed). Similarly, for a range space $\mathcal{R}$ with incidence matrix $\mathbf{A}$, the range space $\mathcal{R}|_{S}$ is the one corresponding to the incidence matrix $\mathbf{A}|_{S}$. We denote the $i$-th standard basis vector $(0,\ldots,0,1,0,\ldots,0)^{T}$ (where $1$ is in the $i$-th coordinate) as $\mathbf{e_{i}}$. For a set $P$ we denote the collection of subsets of $P$ of size $s$ as ${P\choose s}$.

We will use the definitions for range counting, average squared error, orthogonal and hyperspace range counting, as well as the linear algebraic notation introduced in the Introduction. We also consider worst-case squared error, which for an algorithm $\mathcal{A}$ and a range space with incidence matrix $\mathbf{A}$ is $\|\mathcal{A}(\mathbf{x})-\mathbf{A}\mathbf{x}\|_{\infty}^{2}\geq\frac{1}{m}\|\mathcal{A}(\mathbf{x})-\mathbf{A}\mathbf{x}\|_{2}^{2}$. We give all our lower bounds in average squared error and state our upper bounds in terms of both average and worst-case squared error.

The VC-dimension of a range space $\mathcal{R}$ is defined as the size of the largest set $X\subseteq P$ such that $\mathcal{R}|_{X}=2^{X}$. The (primal) shatter function of $\mathcal{R}$ is defined as $\pi_{\mathcal{R}}(s)=\max_{X\in{P\choose s}}|\mathcal{R}|_{X}|$ (i.e. the number of distinct sets in $\mathcal{R}|_{X}$).

If the VC-dimension of $\mathcal{R}$ is $d$, then $\pi_{\mathcal{R}}(s)=O(s^{d})$. Conversely, if $\pi_{\mathcal{R}}(s)=s^{O(1)}$ then the VC-dimension of $\mathcal{R}$ is constant.

2 Differential Privacy

For lower bounds we use the following claim, which implies that being able to decode most of the input from the output contradicts differential privacy.

Let $\mathcal{M}=\{M_{n}\}$ be a mechanism such that for some $n$ there exists a (not necessarily efficient) algorithm $\mathcal{A}$ such that

Then there exist $\varepsilon=\varepsilon(\alpha,\beta)$ and $\delta=\delta(\alpha,\beta)$ such that the mechanism $\mathcal{M}$ is not $(\varepsilon,\delta)$-differentially private.

A basic mechanism to achieve differential privacy with $\delta=0$ is the Laplace noise mechanism, first proposed in . Let us here and for the rest of the paper denote by $\operatorname{Lap}(s)$ the Laplace distribution centered at 0 with scale parameter $s$.

Let the mechanisms $\mathcal{M}^{1},\ldots,\mathcal{M}^{s}$ satisfy, respectively, $(\varepsilon_{1},\delta_{1}),\ldots,(\varepsilon_{s},\delta_{s})$ differential privacy. The composition $\mathcal{M}$ of the mechanisms satisfies $(\sum_{i}{\varepsilon_{i}},\sum_{i}{\delta_{i}})$-differential privacy.

We also need a stronger result, which is a straightforward extension of the composition theorem of Dwork, Rothblum, and Vadhan . To state the result we define a notion of privacy loss. Following , let us first define the maximum divergence of two random variables $a$ and $b$ as

where $S$ ranges over measurable subsets of the support of $b$. Note that a mechanism $\mathcal{M}=\{M_{n}\}$ is $(\varepsilon,0)$-differentially private if and only if for every $n$ and any $\mathbf{x},\mathbf{x}^{\prime}:\|\mathbf{x}-\mathbf{x}^{\prime}\|_{1}\leq 1$, we have $D_{\infty}(M_{n}(\mathbf{x})\|M_{n}(\mathbf{x}^{\prime}))\leq\varepsilon$ and $D_{\infty}(M_{n}(\mathbf{x}^{\prime})\|M_{n}(\mathbf{x}))\leq\varepsilon$.

Let $\mathcal{M}$ be a composition of $\mathcal{M}^{1},\ldots,\mathcal{M}^{s}$. The privacy loss of $i\in[n]$ for the $j$-th output is

Let $\mathcal{M}$ be a composition of $\mathcal{M}^{1},\ldots,\mathcal{M}^{s}$ and let $\varepsilon>\max_{i\in[n]}{L_{\mathcal{M}}(i)}$. Then, for any $\delta>0$, $\mathcal{M}$ satisfies $(\sqrt{2\ln(1/\delta)}\varepsilon,\delta)$-differential privacy.

Note that for the range counting problem, the privacy loss is defined for a point $p$.

3 Discrepancy

Here we define a modified notion of discrepancy. In Section 4, we show that this modified notion of discrepancy is useful in carrying out Dinur-Nissm type attacks on privacy.

The standard notions of discrepancy and hereditary discrepancy correspond to the special cases $\operatorname{disc}=\operatorname{disc}_{\infty,1}$ and $\operatorname{herdisc}=\operatorname{herdisc}_{\infty,1}$. The cases $\operatorname{disc}_{2,1}$ and $\operatorname{herdisc}_{2,1}$ have also been extensively studied, especially as means of proving lower bounds on $\operatorname{disc}$ and $\operatorname{herdisc}$. On the other hand the case $\operatorname{disc}_{p,0}$ is trivially the identically 0 function. Next, we exhibit a connection between $\operatorname{herdisc}_{p,1}$ and $\operatorname{herdisc}_{p,\alpha}$ for $\alpha\in(0,1)$ and any $p$.

Let $f(s)=\max_{S\subseteq[n]:|S|\leq s}{\operatorname{disc}_{p,\alpha}(\mathbf{A}|_{S})}$. Then $\operatorname{disc}_{p,1}(\mathbf{A})\leq\sum_{i=0}^{\infty}{f((1-\alpha)^{i}n)}$, and, therefore, $\operatorname{herdisc}_{p,1}(\mathbf{A})$ $\leq{\sum_{i=0}^{\infty}{f((1-\alpha)^{i}n)}}$

We will find an assignment $\mathbf{x}\in\{\pm 1\}^{n}$ such that $\|\mathbf{A}\mathbf{x}\|_{p}\leq\sum_{i=0}^{\infty}{f((1-\alpha)^{i}n)}$, which is sufficient to prove the lemma. Let $\mathbf{x}^{\prime}\in\{0,\pm 1\}^{n}$ be such that $\|\mathbf{A}\mathbf{x}\|_{p}\leq f(n)$ and $\|\mathbf{x}\|_{1}\geq\alpha n$. Let $S=\{i:x_{i}=0\}$. Since $\|\mathbf{x}\|_{1}\geq\alpha n$, $|S|\leq(1-\alpha)n$. We recurse to find an assignment $\mathbf{x}^{\prime\prime}\in\{\pm 1\}^{S}$ such that $\|(\mathbf{A}|_{S})\mathbf{x}^{\prime\prime}\|_{p}\leq\sum_{i=0}^{\infty}{f((1-\alpha)^{i}|S|)}\leq\sum_{i=1}^{\infty}{f((1-\alpha)^{i}n)}$. Set $x_{i}=x^{\prime}_{i}$ when $i\not\in S$ and $x_{i}=x^{\prime\prime}_{i}$ when $i\in S$. ∎

Lemma 5 and the observation $\operatorname{herdisc}_{p,\alpha}=\max_{s=1}^{n}f(s)$ imply that for any $\mathbf{A}$,

However using Lemma 5 directly and the observation that a restriction of a halfspace range space (or a range space of axis-aligned boxes) is a range space of the same kind, we get stronger lowerbounds for $\operatorname{herdisc}_{p,\alpha}$. Below we list several interesting results that can be derived in this way from known results in combinatorial discrepancy theory . Below we provide more specific references to the discrepancy lower bound used to derive each result. We provide a full proof of the first result; the remaining proofs follow analogous reasoning.

For any $n$ and $m>n$ there exists a matrix $\mathbf{A}\in\{0,1\}^{m\times n}$ such that $\operatorname{herdisc}_{\infty,\alpha}(A)=\Omega(\sqrt{n\log 2m/n})$.

Lower Bounds for Privacy from Discrepancy

Our main result in this section is a noise lower bound on $(\varepsilon,\delta)$-differentially private mechanisms that approximate range counting queries for a host of natural geometric range spaces. Our main conceptual contribution is in identifying $\operatorname{herdisc}_{p,\alpha}$ as the key quantity in showing lower bounds against $(\varepsilon,\delta)$-differential privacy via a Dinur-Nissim type attack, and connecting this quantity to the standard notion of combinatorial discrepancy.

is $(\varepsilon,\delta)$-differentially private.

We extend the lower bound to $\operatorname{herdisc}_{p,\alpha}$. This allows us to use the connection between $\operatorname{herdisc}_{p,\alpha}$ and standard discrepancy.

is $(\varepsilon,\delta)$-differentially private.

We claim that given $M_{n}$ and any set $S\subseteq[n]$, we can construct $M^{\prime}_{n}$ that takes as input $\mathbf{x}|_{S}$, is $(\varepsilon,\delta)$-differentially private (with respect to $\mathbf{x}|_{S}$), and satisfies

Then we can take $S$ such that $\operatorname{disc}_{p,\alpha}(\mathbf{A}|_{S})=\operatorname{herdisc}_{p,\alpha}(\mathbf{A})$, and the corollary follows from Theorem 1.

We define $M_{n}^{\prime}$ as follows: $M_{n}^{\prime}(\mathbf{x}|_{S})$ extends $\mathbf{x}|_{S}$ to $\mathbf{x}$ by setting $x_{i}=0$ for all $i\not\in S$ and outputs $M_{n}(\mathbf{x})$. It’s easy to verify that $M_{n}^{\prime}$ satisfies the claimed properties. ∎

Theorem 1 follows from Lemma 1 and the following lemma.

Corollary 1, instantiated with $p=2$, and Lemmas 6–8 imply an array of noise lower bounds for approximating geometric range counting while satisfying $(\varepsilon,\delta)$-differential privacy.

We also note that that Corollary 1, instantiated with $p=\infty$ and Lemma 9 imply a lower bound on the worst case squared error for privately approximating $m$ arbitrary range counting queries where $m$ is much larger than $n$.

Any mechanism $\mathcal{M}$ that, for any range space $(P,\mathcal{R})$ ($|P|=n$, $|\mathcal{R}|=m$), with constant probability approximates range counts for $\mathcal{R}$ with worst case squared error $o(n\log 2m/n)$ is not $(\varepsilon,\delta)$-differentially private for any constant $\varepsilon$ and $\delta$.

The results of Dinur and Nissim for $m=\O(n)$ and $m=2^{n}$ are special cases of Theorem 5. To the best of our knowledge, this is the first lower bound that explicitly accounts for the dependence of error on $m$ for arbitrary $m>n$.

Algorithm for Bounded Shatter Function Systems

In this section we present an efficient (for constant $d$) $(\varepsilon,\delta)$-differentially private range counting algorithm for range spaces with bounded shatter function. We prove the algorithm gives optimal average squared error and almost optimal worst-case squared error bounds. The algorithm is based on a novel use of a decomposition that was first constructed by Matous̆ek to prove optimal discrepancy upper bounds for bounded shatter function range spaces. Even a careful application of known methods in differential privacy together with the decomposition does not provide optimal error bounds directly; we, however, prove that privacy can be satisfied for a constant fraction of $P$ while achieving optimal error bounds; then we recurse on the remainder of $P$. Aside from the decomposition, this method of satisfying privacy for a fraction of the database is inspired by partial coloring methods in discrepancy theory.

We will make an essential use of the following lemma, due originally to Haussler. The lemma bounds the size of an epsilon net in the hamming metric.

Let $(P,\mathcal{R})$ be a range space with shatter function $\pi_{\mathcal{R}}(s)=O(s^{d})$. Let $\Delta$ be an integer less than $|P|$. Let $\mathcal{S}\subseteq\mathcal{R}$ be a collection of ranges such that for any two ranges $R_{1},R_{2}\in\mathcal{S}$, the symmetric difference between $R_{1}$ and $R_{2}$ is at least $\Delta$. Then, $|\mathcal{S}|=O((|P|/\Delta)^{d})$.

We construct collections of ranges with large pairwise distance $\Delta$ for gemetrically growing values of $\Delta$. Using the collections as finer and finer epsilon nets, we can represent each range in $\mathcal{R}$ as the union and set difference of smaller and smaller ranges, while Lemma 11 allows us to control the number of such ranges needed for each value of $\Delta$. We then approximate range counts for the ranges that make up the decomposition; the trade-off between range size and number of distinct ranges allows us to balance the noise incurred by randomized response and by using composition (Lemma 4).

We first detail the construction. Our presentation follows . Let $(P,\mathcal{R})$ be a range space with shatter function $\pi_{\mathcal{R}}(s)=O(s^{d})$. Let $k=\lceil\log_{2}n\rceil$. For each $i\in\{0,\ldots,k\}$, let $\mathcal{S}_{i}\subseteq\mathcal{R}$ be a maximal collection of ranges such that the symmetric difference between any two ranges $R_{1},R_{2}\in\mathcal{S}_{i}$ is at least $n2^{-i}$. In particular, $\mathcal{S}_{k}=\mathcal{R}$ and $\mathcal{S}_{0}=\{\emptyset\}$. For each $R\in\mathcal{S}_{i}$, fix a $R^{\prime}\in\mathcal{S}_{i-1}$ such that the symmetric difference between $R$ and $R^{\prime}$ is at most $n2^{-i+1}$ (such a range exists by maximality of $\mathcal{S}_{i-1}$). Then we set $F(R)=R\setminus R^{\prime}$ and $G(R)=R^{\prime}\setminus R$, so that $R^{\prime}=(R\setminus F(R))\cup G(R)$, $F(R)\subseteq R$, and $G(R)\cap(R\setminus F(R))=\emptyset$. Define a new collection of ranges $\mathcal{T}_{i}=\{F(R),G(R):R\in\mathcal{S}_{i}\}$. We can start from $R\in\mathcal{R}=\mathcal{S}_{k}$ and apply the construction recursively, until we have $\emptyset=((\ldots((R\setminus F_{k})\cup G_{k})\ldots)\cup G_{2})\setminus F_{1},$ where $F_{i},G_{i}\in\mathcal{T}_{i}$. Bactracking to reconstruct $R$, we get

All union operations are on disjoint sets and any set is subtracted from a set that entirely contains it.

Each range in $\mathcal{T}_{i}$ has size at most $n2^{-i+1}$ by construction; by Lemma 11, $|\mathcal{S}_{i}|=O(2^{di})$, and, since each range in $\mathcal{S}_{i}$ corresponds to at most two ranges in $\mathcal{T}_{i}$, we also have $\mathcal{T}_{i}=O(2^{di})$ . Let $\mathbf{T}^{i}$ be the incidence matrix of $\mathcal{T}_{i}$. The following lemma follows from the decomposition (2):

Let $(P,\mathcal{R})$ be a range space with $|P|=n$ and shatter function $\pi_{\mathcal{R}}(s)=O(s^{d})$. Let $\mathbf{A}$ be the incidence matrix of $\mathcal{R}$. Then, there exist matrices $\mathbf{T}^{i}\in\{0,1\}^{s_{i}\times n}$ and $\mathbf{Q}^{i}\in\{0,\pm 1\}^{m\times s_{i}}$ such that $\mathbf{A}=\sum_{i=1}^{k}{\mathbf{Q}^{i}\mathbf{T}^{i}}$. Furthermore, we have the following properties for $\mathbf{T}^{i}$ and $\mathbf{Q}^{i}$:

each row in $\mathbf{T}^{i}$ has at most $n2^{-i+1}$ nonzero entries;

$s_{i}\leq C2^{di}$ for some absolute constant $C$;

each row in $\mathbf{Q}^{i}$ has at most 2 nonzero entries.

For the degree of a point $p\in P$ in the range space $\mathcal{T}_{i}$, we use the notation $d_{i}(p)=|\{R\in\mathcal{T}_{i}:p\in R\}|$.

Intuitively, we will use randomized response on those $\mathcal{T}_{i}$ consisting of only small ranges, and we will use the Laplace noise mechanism on those $\mathcal{T}_{i}$ consisting of few ranges. The “breaking-even point” for the analysis is $i_{0}=(\log n)/d$. For $i\geq i_{0}$ randomized response gives the guarantee we need: the largest range in $\mathcal{T}_{i}$ for $i\geq i_{0}$ has size at most $n^{1-1/d}$. However, $\mathcal{T}_{i_{0}}$ can have as many as $n$ ranges, and it seems that we cannot use Laplace noise with variance $n^{1-1/d}$ and still preserve privacy for those $i$ close to $i_{0}$. To circumvent this issue, we use the fact that we can bound both the largest range and the number of ranges in each $\mathcal{T}_{i}$ simultaneously. The main observation is that we can add noise with optimal variance $O(n^{1-1/d})$ to the range counts for those $\mathcal{T}_{i}$ where randomized response doesn’t work, and bound the average privacy loss $\frac{1}{n}\sum_{p}L_{\mathcal{M}}(p)$. Then, we use averaging and Lemma 4, and argue that we can preserve privacy for most $p\in P$. The shatter function bound does not increase for restrictions of $P$ and $\mathcal{R}$ and we can recurse on the remaining points of $P$. Our algorithm for computing range counts over ranges with bounded shatter function is given as Algorithm 1. The algorithm description and the following discussion assume that $\mathcal{R}$ has shatter function $\pi_{\mathcal{R}}(s)=O(s^{d})$ (for $d\geq 2$) and the decomposition of Lemma 12 has already been computed. Note that the decomposition can be computed in time $O(mn\log n)$.

We analyze the privacy guarantees of Algorithm 1. We first prove some technical claims about the algorithm.

Claim 1. follows by avaraging and the inequality

The first inequality follows from Lemma 12. The second inequality holds for $d\geq 2$. This finishes the proof of claim 1.

The following privacy analysis uses the fact that the range space $(P,\mathcal{R})$ is public, and, therefore, the decomposition given by Lemma 12, and the set $X$ determined by the decomposition are public as well, i.e. independent of $\mathbf{x}$.

Algorithm 1 preserves $((2\sqrt{6C}+2)\varepsilon\sqrt{\ln 1/\delta},\delta)$-differential privacy.

Next we analyze the approximation guarantee of the algorithm. The bounds in following lemma can derived by a straightforward calculation.

We’re now ready to prove an approximation guarantee.

The expected average squared error of Algorithm 1 is $O(n^{1-1/d}/\varepsilon^{2})$. With probability at least $1-\beta$, the worst-case squared error of Algorithm 1 is at most $O(n^{1-1/d}\log(n/\beta)/\varepsilon^{2})$.

The worst-case guarantee can be derived by standard use of tail bounds for sums of Laplace random variables. ∎

Extensions

Algorithms for halfspace range counting can be derived from several other methods, each of which provides weaker noise guarantees and/or less generality.

The partition trees of Chan imply a way to factor the incidence matrix $\mathbf{A}$ of a range space induced by $d$-dimensional halfspaces into matrices $\mathbf{Q}$ and $\mathbf{D}$ such that $\mathbf{A}=\mathbf{QD}$, each column in $\mathbf{D}$ has at most $O(\log\log n)$ nonzero elements, each row in $\mathbf{Q}$ has at most $O(n^{1-1/d})$ nonzero elements, and $\mathbf{Q}$ and $\mathbf{D}$ both have elements bounded in absolute value by $1$. Using Lemma 4, we can add Laplace noise with variance $O(\frac{1}{\varepsilon^{2}}\log\log n)$ to each element of $\mathbf{Dx}$, preserving $(\varepsilon\sqrt{\ln 1/\delta},\delta)$ privacy. We can then bound the variance of this mechanism to argue that, with constant probability, the average squared error is $O(\frac{1}{\varepsilon^{2}}n^{1-1/d}\log\log n)$ and the worst case squared error is $O(\frac{1}{\varepsilon^{2}}n^{1-1/d}\log n\log\log n)$.

There is a well-known connection between combinatorial discrepancy and epsilon approximations (c.f. , Chapter 1). Let $(P,\mathcal{R})$ be a range space such that the maximum discrepancy over all restrictions of $\mathcal{R}$ to a size $s$ subset of $P$ is $f(s)$ (this is the same $f(s)$ as in Section 3). Under some reasonable assumptions on the range space, there exists a subset $S$ of $P$ of size $s$ such that range counts on $S$ are close to range counts on $P$ to within an additive $\frac{n}{s}f(s)$. Using this fact, and the discrepancy upper bound for range spaces with shatter function exponent $d$, we can apply the median mechanism of Roth and Roughgarden with the new analysis in to obtain a squared error upper bound that depends on $n$ as $O(n^{2d/(2d+1)})$. This upper bound is suboptimal; for example, for $d=2$, it yields an upper bound of $n^{4/5}$ as opposed to the optimal $n^{1/2}$. Nevertheless, this method still gives squared error bounds that grow slower than $n$ for range system with polynomial shatter function. It also extends to the case where the universe is much larger than $\|\mathbf{x}\|_{1}$. Giving optimal or near optimal error upper bounds in this large universe regime is an interesting open problem.

Concluding Remarks

While predicate count queries ($\mathbf{A}\mathbf{x}$) have been studied in differential privacy before, we make one of the first significant progress in understanding the complexity of the problem in terms of the combinatorial properties of $\mathbf{A}$, in particular for halfspace, orthogonal and other range count queries. Our main result is tight upper and lower bounds on approximation of $(\epsilon,\delta)$ differentially private halfspace count queries. Our approach is via a variation of discrepancy. The main problems we leave open are to get tight bounds for orthogonal counts with $(\epsilon,\delta)$-differential privacy and to extend our bounds to the large universe regime.

Acknowledgements

We would like to thank Guy Rothblum, Kobbi Nissim, and Aaron Roth for helpful discussions, and the anonymous reviewers for useful suggestions and corrections.

This material is based upon work supported by the National Science Foundation under Grant No. 0916782.

References