Differentially Private Release and Learning of Threshold Functions

Introduction

The line of work on differential privacy [DMNS06] is aimed at enabling useful statistical analyses on privacy-sensitive data while providing strong privacy protections for individual-level information. Privacy is achieved in differentially private algorithms through randomization and the introduction of “noise” to obscure the effect of each individual, and thus differentially private algorithms can be less accurate than their non-private analogues. Nevertheless, by now a rich literature has shown that many data analysis tasks of interest are compatible with differential privacy, and generally the loss in accuracy vanishes as the number $n$ of individuals tends to infinity. However, in many cases, there is still is a price of privacy hidden in these asymptotics — in the rate at which the loss in accuracy vanishes, and in how large $n$ needs to be to start getting accurate results at all (the “sample complexity”).

We recall the definition of differential privacy. We think of a dataset as consisting of $n$ rows from a data universe $X$, where each row corresponds to one individual. Differential privacy requires that no individual’s data has a significant effect on the distribution of what we output.

A randomized algorithm $M:X^{n}\rightarrow Y$ is $(\varepsilon,\delta)$ differentially private if for every two datasets $x,x^{\prime}\in X^{n}$ that differ on one row, and every set $T\subseteq Y$, we have

The original definition from [DMNS06] had $\delta=0$, and is sometimes referred to as pure differential privacy. However, a number of subsequent works have shown that allowing a small (but negligible) value of $\delta$, referred to as approximate differential privacy, can provide substantial gains over pure differential privacy [DL09, HT10, DRV10, De12, BNS13b].

The common setting of parameters is to take $\varepsilon$ to be a small constant and $\delta$ to be negligible in $n$ (or a given security parameter). To simplify the exposition, we fix $\varepsilon=0.1$ and $\delta=1/n^{\log n}$ throughout the introduction (but precise dependencies on these parameters are given in the main body).

2 Private Query Release

A special case of interest is the case where $Q$ consists of counting queries. In this case, we are given a set $Q$ of predicates $q:X\rightarrow\{0,1\}$ on individual rows, and then extend them to databases by averaging. That is, $q(D)=(1/n)\sum_{i=1}^{D}q(D_{i})$ counts the fraction of the population that satisfies predicate $q$.

The sample complexity of releasing threshold functions over a data universe $X$ with differential privacy is at least $\Omega(\log^{*}|X|)$. In particular, there is no differentially private algorithm for releasing threshold functions over an infinite data universe.

In addition, inspired by the ideas in our lower bound, we present a simplification of the algorithm of [BNS13b] and improve the sample complexity to $2^{(1+o(1))\log^{*}|X|}$ (from roughly $8^{\log^{*}|X|}$). Closing the gap between the lower bound of $\approx\log^{*}|X|$ and the upper bound of $\approx 2^{\log^{*}|X|}$ remains an intriguing open problem.

We remark that in the case of pure differential privacy ($\delta=0$), a sample complexity lower bound of $n=\Omega(\log|X|)$ follows from a standard “packing argument” [HT10, BKN10]. For point functions, this is matched by the standard Laplace mechanism [DMNS06]. For threshold functions, a matching upper bound was recently obtained [RR14], building on a construction of [DNPR10]. We note that these algorithms have a slightly better dependence on the accuracy parameter $\alpha$ than our algorithm (linear rather than nearly linear in $1/\alpha$). In general, while packing arguments often yield tight lower bounds for pure differential privacy, they fail badly for approximate differential privacy, for which much less is known.

3 Private Distribution Learning

The well-known Dvoretzky-Kiefer-Wolfowitz inequality [DKW56] implies that without privacy, any distribution over $X$ can be learned to within constant error with $O(1)$ samples. On the other hand, we show that with approximate differential privacy, the task of releasing thresholds is essentially equivalent to distribution learning. As a consequence, with approximate differential privacy, distribution learning instead requires sample complexity that grows with the size of the domain.

The sample complexity of learning arbitrary distributions on a domain $X$ with differential privacy is at least $\Omega(\log^{*}|X|)$.

4 Private PAC Learning

Kasiviswanathan et al. [KLN+11] defined private PAC learning as a combination of probably approximately correct (PAC) learning [Val84] and differential privacy. Recall that a PAC learning algorithm takes some $n$ labeled examples $(x_{i},c(x_{i}))\in X\times\{0,1\}$ where the $x_{i}$’s are i.i.d. samples of an arbitrary and unknown distribution on a data universe $X$ and $c:X\rightarrow\{0,1\}$ is an unknown concept from some concept class $C$. The goal of the learning algorithm is to output a hypothesis $h:X\rightarrow\{0,1\}$ that approximates $c$ well on the unknown distribution. We are interested in PAC learning algorithms $L:(X\times\{0,1\})^{n}\rightarrow H$ that are also differentially private. Here $H$ is the hypothesis class; if $H\subseteq C$, then $L$ is called a proper learner.

As with query release and distribution learning, a natural problem is to characterize the sample complexity — the minimum number $n$ of samples in order to achieve differentially private PAC learning for a given concept class $C$. Without privacy, it is well-known that the sample complexity of (proper) PAC learning is proportional to the Vapnik–Chervonenkis (VC) dimension of the class $C$ [VC71, BEHW89, EHKV89]. In the initial work on differentially private learning, Kasiviswanathan et al. [KLN+11] showed that $O(\log|C|)$ labeled examples suffice for privately learning any concept class $C$.As with the query release discussion, we omit the dependency on all parameters except for $|C|$, $|X|$ and $\operatorname{\rm VC}(C)$. The VC dimension of a concept class $C$ is always at most $\log|C|$, but is significantly lower for many interesting classes. Hence, the results of [KLN+11] left open the possibility that the sample complexity of private learning may be significantly higher than that of non-private learning.

In the case of pure differential privacy ($\delta=0$), this gap in the sample complexity was shown to be unavoidable in general. Beimel, Kasiviswanathan, and Nissim [BKN10] considered the concept class $C$ of point functions over a data universe $X$, which have VC dimension 1 and hence can be (properly) learned without privacy with $O(1)$ samples. In contrast, they showed that proper PAC learning with pure differential privacy requires sample complexity $\Omega(\log|X|)=\Omega(\log|C|)$. Feldman and Xiao [FX14] showed a similar separation even for improper learning — the class $C$ of threshold functions over $X$ also has VC dimension 1, but PAC learning with pure differential privacy requires sample complexity $\Omega(\log|X|)=\Omega(\log|C|)$.

For approximate differential privacy ($\delta>0$), however, it was still open whether there is an asymptotic gap between the sample complexity of private learning and non-private learning. Indeed, Beimel et al. [BNS13b] showed that point functions can be properly learned with approximate differential privacy using $O(1)$ samples (i.e. with no dependence on $|X|$). For threshold functions, they exhibited a proper learner with sample complexity $2^{O(\log^{*}|X|)}$, but it was conceivable that the sample complexity could also be reduced to $O(1)$.

We prove that the sample complexity of proper PAC learning with approximate differential privacy can be asymptotically larger than the VC dimension:

The sample complexity of properly learning threshold functions over a data universe $X$ with differential privacy is at least $\Omega(\log^{*}|X|)$.

Based on these results, it would be interesting to fully characterize the difference between the sample complexity of proper non-private learners and of proper learners with (approximate) differential privacy. Furthermore, our results still leave open the possibility that improper PAC learning with (approximate) differential privacy has sample complexity $O(\operatorname{\rm VC}(C))$. We consider this to be an important question for future work.

5 Techniques

Our results for query release and proper learning of threshold functions are obtained by analyzing the sample complexity of a related but simpler problem, which we call the interior-point problem. Here we want a mechanism $M:X^{n}\rightarrow X$ (for a totally ordered data universe $X$) such that for every database $D\in X^{n}$, with high probability we have $\min_{i}D_{i}\leq M(D)\leq\max_{i}D_{i}$. We give reductions showing that the sample complexity of this problem is equivalent to the other ones we study:

Over every totally ordered data universe $X$, the following four problems have the same sample complexity (up to constant factors) under differential privacy:

Distribution learning (with respect to Kolmogorov distance).

Proper PAC learning of threshold functions.

Thus we obtain our lower bounds and our simplified and improved upper bounds for query release and proper learning by proving such bounds for the interior-point problem, such as:

The sample complexity for solving the interior-point problem over a data universe $X$ with differential privacy is $\Omega(\log^{*}|X|)$.

Note that for every fixed distribution $\mathcal{D}$ over $X$ there exists a simple differentially private algorithm for solving the interior-point problem (w.h.p.) over databases sampled i.i.d. from $\mathcal{D}$ – simply output a point $z$ s.t. $\Pr_{x\sim\mathcal{D}}[x\geq z]=1/2$. Hence, in order to prove Theorem 1.8, we show a (correlated) distribution $\mathcal{D}$ over databases of size $n\approx\log^{*}|X|$ on which privately solving the interior-point problem is impossible. The construction is recursive: we use a hard distribution over databases of size $(n-1)$ over a data universe of size logarithmic in $|X|$ to construct the hard distribution over databases of size $n$ over $X$.

By another reduction to the interior-point problem, we show an impossibility result for the following undominated-point problem:

Note that for the above problem, one cannot hope to construct a single distribution over databases that every private mechanism fails on. The reason is that for any such distribution $\mathcal{D}$, and any desired failure probability $\beta$, there is some number $K$ for which $\Pr_{D\sim\mathcal{D}}[\max{D}>K]\leq\beta$, and hence that the mechanism that always outputs $K$ solves the problem. Hence, given a mechanism $\mathcal{M}$ we must tailor a hard distribution $\mathcal{D}_{\mathcal{M}}$. We use a similar mechanism-dependent approach to prove Theorem 1.6.

Preliminaries

Throughout this work, we use the convention that $[n]=\{0,1,\dots,n-1\}$ and write $\log$ for $\log_{2}$. We use $\operatorname*{\tt THRESH}_{X}$ to denote the set of all threshold functions over a totally ordered domain $X$. That is,

We will present algorithms that access their input database using (several) differentially private mechanisms and use the following composition theorem to prove their overall privacy guarantee.

Let $\mathcal{M}_{1}:X^{n}\to\mathcal{R}_{1}$ be $(\varepsilon_{1},\delta_{1})$-differentially private. Let $\mathcal{M}_{2}:X^{n}\times\mathcal{R}_{1}\to\mathcal{R}_{2}$ be $(\varepsilon_{2},\delta_{2})$-differentially private for any fixed value of its second argument. Then the composition $M(D)=\mathcal{M}_{2}(D,\mathcal{M}_{1}(D))$ is $(\varepsilon_{1}+\varepsilon_{2},\delta_{1}+\delta_{2})$-differentially private.

The Interior Point Problem

In this work we exhibit a close connection between the problems of privately learning and releasing threshold queries, distribution learning, and solving the interior point problem as defined below.

An algorithm $A:X^{n}\to X$ solves the interior point problem on $X$ with error probability $\beta$ if for every $D\in X^{n}$,

where the probability is taken over the coins of $A$. The sample complexity of the algorithm $A$ is the database size $n$.

We call a solution $x$ with $\min D\leq x\leq\max D$ an interior point of $D$. Note that $x$ need not be a member of the database $D$.

2 Lower Bound

We now prove our lower bound on the sample complexity of private algorithms for solving the interior point problem.

Fix any constant $0<\varepsilon<1/4$. Let $\delta(n)\leq 1/(50n^{2})$. Then for every positive integer $n$, solving the interior point problem on $X$ with probability at least $3/4$ and with $(\varepsilon,\delta(n))$-differential privacy requires sample complexity $n\geq\Omega(\log^{*}|X|)$.

The inductive lemma we prove depends on a number of parameters we now define. Fix $\frac{1}{4}>\varepsilon,\beta>0$. Let $\delta(n)$ be any positive non-increasing sequence for which

for every $n$. In particular, it suffices that

Let $b(n)=1/\delta(n)$ and define the function $S$ recursively by

For every positive integer $n$, there exists a distribution $\mathcal{D}_{n}$ over databases $D\in[S(n)]^{n}=\{0,1,\dots,S(n)-1\}^{n}$ such that for every $(\varepsilon,\delta(n))$-differentially private mechanism $\mathcal{M}$,

where the probability is taken over $D\leftarrow_{\mbox{\tiny R}}\mathcal{D}_{n}$ and the coins of $\mathcal{M}$.

In this section, we give a direct proof of the lemma and in Appendix B, we show how the lemma follows from the construction of a new combinatorial object we call an “interior point fingerprinting code.” This is a variant on traditional fingerprinting codes, which have been used recently to show nearly optimal lower bounds for other problems in approximate differential privacy [BUV14, DTTZ14, BST14].

The proof is by induction on $n$. We first argue that the claim holds for $n=1$ by letting $\mathcal{D}_{1}$ be uniform over the singleton databases $(0)$ and $(1)$. To that end let $x\leftarrow_{\mbox{\tiny R}}\mathcal{D}_{1}$ and note that for any $(\varepsilon,\delta(1))$-differentially private mechanism $\mathcal{M}_{0}:\{0,1\}\rightarrow\{0,1\}$ it holds that

giving the desired bound on $\Pr[\mathcal{M}_{0}(x)=x]$.

Now inductively suppose we have a distribution $\mathcal{D}_{n}$ that satisfies the claim. We construct a distribution $\mathcal{D}_{n+1}$ on databases $(y_{0},y_{1},\dots,y_{n})\in[S(n+1)]^{n+1}$ that is sampled as follows:

Sample $(x_{1},\dots,x_{n})\leftarrow_{\mbox{\tiny R}}\mathcal{D}_{n}$.

Sample a uniformly random $y_{0}\leftarrow_{\mbox{\tiny R}}[S(n+1)]$. We write the base $b(n)$ representation of $y_{0}$ as $y_{0}^{(1)}y_{0}^{(2)}\dots y_{0}^{(S(n))}$.

For each $i=1,\dots,n$ let $y_{i}$ be a base $b(n)$ number (written $y_{i}^{(1)}y_{i}^{(2)}\dots y_{i}^{(S(n))}$) that agrees with the base $b(n)$ representation of $y_{0}$ on the first $x_{i}$ digits and contains a random sample from $[b(n)]$ in every index thereafter.

Suppose for the sake of contradiction that there were an $(\varepsilon,\delta(n+1))$-differentially private mechanism $\hat{\mathcal{M}}$ that could solve the interior point problem on $\mathcal{D}_{n+1}$ with probability greater than $P_{n+1}$. We use $\hat{\mathcal{M}}$ to construct the following private mechanism $\mathcal{M}$ for solving the interior point problem on $\mathcal{D}_{n}$, giving the desired contradiction:

The mechanism $\mathcal{M}$ is also $(\varepsilon,\delta(n+1))$-differentially private, since for all pairs of adjacent databases $D\sim D^{\prime}$ and every $T\subseteq[S(n)]$,

where $\hat{T}$ is the set of $y$ that agree with $y_{0}$ in exactly the first $x$ entries for some $x\in T$.

Now we argue that $\mathcal{M}$ solves the interior point problem on $\mathcal{D}_{n}$ with probability greater than $P_{n}$. First we show that $x\geq\min D$ with probability greater than $P_{n+1}$. Observe that by construction, all the elements of $\hat{D}$ agree in at least the first $\min D$ digits, and hence so does any interior point of $\hat{D}$. Therefore, if $\mathcal{M}^{\prime}$ succeeds in outputting an interior point $y$ of $\hat{D}$, then $y$ must in particular agree with $y_{0}$ in at least $\min D$ digits, so $x\geq\min D$.

Now we use the privacy that $\hat{\mathcal{M}}$ provides to $y_{0}$ to show that $x\leq\max D$ except with probability at most $e^{\varepsilon}/b(n)+\delta(n+1)$. Fix a database $D$. Let $w=\max D$, and fix all the randomness of $\mathcal{M}$ but the $(w+1)$st entry of $y_{0}$ (note that since $w=\max D$, this fixes $y_{1},\ldots,y_{n}$). Since the $(w+1)$st entry of $y_{0}$ is still a uniformly random element of $[b(n)]$, the privately produced entry $y^{w+1}$ should not be able to do much better than randomly guessing $y_{0}^{(w+1)}$. Formally, for each $z\in[b(n)]$, let $\hat{D}_{z}$ denote the database $\hat{D}$ with $y_{0}^{(w+1)}$ set to $z$ and everything else fixed as above. Then by the differential privacy of $\hat{\mathcal{M}}$,

where all probabilities are also taken over the coins of $\hat{\mathcal{M}}$. Thus $x\leq\max D$ except with probability at most $e^{\varepsilon}/b(n)+\delta(n+1)$. By a union bound, $\min D\leq x\leq\max D$ with probability greater than

We now prove Theorem 3.2 by estimating the $S(n)$ guaranteed by Lemma 3.3.

Let $S(n)$ be as in Lemma 3.3. We introduce the following notation for iterated exponentials:

Observe that for $k\geq 1$, $x>0$, and $M>16$,

By induction on $n$ we get an upper bound of

This immediately shows that solving the interior point problem on $X=[S(n)]$ requires sample complexity

To get a lower bound for solving the interior point problem on $X$ when $|X|$ is not of the form $S(n)$, note that a mechanism for $X$ is also a mechanism for every $X^{\prime}$ s.t. $|X^{\prime}|\leq|X|$. The lower bound follows by setting $|X^{\prime}|=S(n)$ for the largest $n$ such that $S(n)\leq|X|$. ∎

3 Upper Bound

We now present a recursive algorithm, RecPrefix, for privately solving the interior point problem.

RecPrefix is $(\epsilon,\delta)$-differentially private;

With probability at least $(1-\beta)$, the output $x$ satisfies $\min\{x_{i}:x_{i}\in S\}\leq x\leq\max\{x_{i}:x_{i}\in S\}$.

The idea of the algorithm is that on each level of recursion, RecPrefix takes an input database $S$ over $X$ and constructs a database $S^{\prime}$ over a smaller universe $X^{\prime}$, where $|X^{\prime}|=\log|X|$, in which every element is the length of the longest prefix of a pair of elements in $S$ (represented in binary). In a sense, this reverses the construction presented in Section 3.2.

The exponential mechanism is $\epsilon$-differentially private.

Let $q$ be a quality function with sensitivity at most $1$. Fix a database $S\in X^{n}$ and let $\operatorname{\rm OPT}=\max_{f\in\mathcal{F}}\{q(S,f)\}$. Let $t>0$. Then exponential mechanism outputs a solution $f$ with $q(S,f)\leq\operatorname{\rm OPT}-tn$ with probability at most $|\mathcal{F}|\cdot\exp(-\epsilon tn/2)$.

We will also use an $(\varepsilon,\delta)$-differentially private variant of the exponential mechanism called the choosing mechanism, introduced in [BNS13b].

A quality function with sensitivity at most $1$ is of $k$-bounded-growth if adding an element to a database can increase (by 1) the score of at most $k$ solutions, without changing the scores of other solutions. Specifically, it holds that

$q(\emptyset,f)=0$ for all $f\in\mathcal{F}$,

If $S_{2}=S_{1}\cup\{x\}$, then $q(S_{1},f)+1\geq q(S_{2},f)\geq q(S_{1},f)$ for all $f\in\mathcal{F}$, and

There are at most $k$ values of $f$ for which $q(S_{2},f)=q(S_{1},f)+1$.

The choosing mechanism is a differentially private algorithm for approximately solving bounded-growth choice problems. Step 1 of the algorithm checks whether a good solution exists (otherwise any solution is approximately optimal) and Step 2 invokes the exponential mechanism, but with the small set $G(S)$ of good solutions instead of $\mathcal{F}$.

The following lemmas give the privacy and utility guarantees of the choosing mechanism. We give a slightly improved utility result over [BNS13b], and the analysis is presented in Appendix A.

Fix $\delta>0$, and $0<\epsilon\leq 2$. If $q$ is a $k$-bounded-growth quality function, then the choosing mechanism is $(\epsilon,\delta)$-differentially private.

Let the choosing mechanism be executed on a $k$-bounded-growth quality function, and on a database $S$ s.t. there exists a solution $\hat{f}$ with quality $q(S,\hat{f})\geq\frac{16}{\epsilon}\ln(\frac{4k}{\beta\epsilon\delta})$. With probability at least $(1-\beta)$, the choosing mechanism outputs a solution $f$ with quality $q(S,f)\geq 1$.

Let the choosing mechanism be executed on a $k$-bounded-growth quality function, and on a database $S$ containing $m$ elements. With probability at least $(1-\beta)$, the choosing mechanism outputs a solution $f$ with quality $q(S,f)\geq\operatorname{\rm OPT}-\frac{16}{\epsilon}\ln(\frac{4km}{\beta\epsilon\delta})$.

3.2 The RecPrefix algorithm

We are now ready to present and analyze the algorithm RecPrefix.

We start the analysis of RecPrefix with the following two simple observations.

There are at most $\log^{*}|X|$ recursive calls throughout the execution of RecPrefix on a database $S\in X^{*}$.

Let RecPrefix be executed on a database $S\in X^{n}$, where $n\geq 2^{\log^{*}|X|}\cdot\frac{2312}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$. Every recursive call throughout the execution operates on a database containing at least $\frac{1540}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$ elements.

We now analyze the utility guarantees of RecPrefix by proving the following lemma.

Let $\beta,\epsilon,\delta$, and $S\in X^{n}$ be inputs on which RecPrefix performs at most $N$ recursive calls, all of which are on databases of at least $\frac{1540}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$ elements. With probability at least $(1-3\beta N)$, the output $x$ is s.t.

$|\{i:x_{i}\geq x\}|\geq k\triangleq\lfloor\frac{386}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})\rfloor$.

Before proving the lemma, we make a combinatorial observation that motivates the random shuffling in Step 2 of RecPrefix. A pair of elements $y,y^{\prime}\in S$ is useful in Algorithm RecPrefix if many of the values in $S$ lie between $y$ and $y^{\prime}$ – a prefix on which $y,y^{\prime}$ agree is also a prefix of every element between $y$ and $y^{\prime}$. A prefix common to a useful pair can hence be identified privately via stability-based techniques. Towards creating useful pairs, the set $S$ is shuffled randomly. We will use the following lemma:

Let $(\Pi_{1},\Pi_{2},\ldots,\Pi_{n})$ be a random permutation of $(1,2,\ldots,n)$. Then for all $r\geq 1$,

We need to show that w.h.p. there are at most $r$ “bad” pairs $(\Pi_{2i-1},\Pi_{2i})$ within distance $\frac{r}{12}$. For each $i$, we call $\Pi_{2i-1}$ the left side of the pair, and $\Pi_{2i}$ the right side of the pair. Let us first choose $r$ elements to be placed on the left side of $r$ bad pairs (there are ${n\choose r}$ such choices). Once those are fixed, there are at most $(\frac{r}{6})^{r}$ choices for placing elements on the right side of those pairs. Now we have $r$ pairs and $n-2r$ unpaired elements that can be shuffled in $(n-r)!$ ways. Overall, the probability of having at least $r$ bad pairs is at most

where we have used Stirling’s approximation for the first inequality. ∎

Suppose we have paired random elements in our input database $S$, and constructed a database $S^{\prime}$ containing lengths of the prefixes for those pairs. Moreover, assume that by recursion we have identified a length $z$ which is the length at least $r$ random pairs. Although those prefixes may be different for each pair, Claim 3.12 guarantees that (w.h.p.) at least one of these prefixes is the prefix of at least $\frac{r}{12}$ input elements. This will help us in (privately) identifying such a prefix.

The proof is by induction on the number of recursive calls, denoted as $t$. For $t=1$ (i.e., $|X|\leq 32$), the claim holds as long as the exponential mechanism outputs an $x$ with $q(S,x)\geq k$ except with probability at most $\beta$. By Proposition 3.5, it suffices to have $n\geq\frac{1540}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$, since $32\exp(-\varepsilon(n/2-k)/2)\leq\beta$.

Assume that the stated lemma holds whenever RecPrefix performs at most $t-1$ recursive calls. Let $\beta,\epsilon,\delta$ and $S=(x_{i})_{i=1}^{n}\in X^{n}$ be inputs on which algorithm RecPrefix performs $t$ recursive calls, all of which are on databases containing at least $\frac{1540}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$ elements. Consider the first call in the execution on those inputs, and let $y_{1},\ldots,y_{n-2k}$ be the random permutation chosen on Step 2. We say that a pair $y_{2j-1},y_{2j}$ is close if

By Claim 3.12, except with probability at most $2^{-(k-1)}<\beta$, there are at most $(k-1)$ close pairs. We continue the proof assuming that this is the case.

Let $S^{\prime}=(z_{i})_{i=1}^{(n-2k)/2}$ be the database constructed in Step 3. By the inductive assumption, with probability at least $(1-3\beta(t-1))$, the value $z$ obtained in Step 4 is s.t. (1) $\exists z_{i}\in S^{\prime}$ s.t. $z_{i}\leq z$; and (2) $|\{z_{i}\in S^{\prime}:z_{i}\geq z\}|\geq k$. We proceed with the analysis assuming that this event happened.

By (2), there are at least $k$ pairs $y_{2j-1},y_{2j}$ that agree on a prefix of length at least $z$. At least one of those pairs, say $y_{2j^{*}-1},y_{2j^{*}}$, is not close. Note that every $y$ between $y_{2j^{*}-1}$ and $y_{2j^{*}}$ agrees on the same prefix of length $z$, and that there are at least $\frac{k-1}{12}$ such elements in $S$. Moreover, as the next bit is either 0 or 1, at least half of those elements agree on a prefix of length $(z+1)$. Thus, when using the choosing mechanism on Step 5 (to choose a prefix of length $(z+1)$), there exists at least one prefix with quality at least $\frac{k-1}{24}\geq\frac{16}{\epsilon}\cdot\ln(\frac{4}{\beta\epsilon\delta})$. By Lemma 3.8, the choosing mechanism ensures, therefore, that with probability at least $(1-\beta)$, the chosen prefix $L$ is the prefix of at least one $y_{i^{\prime}}\in S$, and, hence, this $y_{i^{\prime}}$ satisfies $L_{0}\leq y_{i^{\prime}}\leq L_{1}$ (defined in Step 6). We proceed with the analysis assuming that this is the case.

Let $z_{\hat{j}}\in S^{\prime}$ be s.t. $z_{\hat{j}}\leq z$. By the definition of $z_{\hat{j}}$, this means that $y_{2\hat{j}-1}$ and $y_{2\hat{j}}$ agree on a prefix of length at most $z$. Hence, as $L$ is of length $z+1$, we have that either $\min\{y_{2\hat{j}-1},y_{2\hat{j}}\}<L_{0}$ or $\max\{y_{2\hat{j}-1},y_{2\hat{j}}\}>L_{1}$. If $\min\{y_{2\hat{j}-1},y_{2\hat{j}}\}<L_{0}$, then $L_{0}$ satisfies Condition 1 of being a good output. It also satisfies Condition 2 because $y_{i^{\prime}}\geq L_{0}$ and $y_{i^{\prime}}\in Y$, which we took to be the smallest $n-2k$ elements of $S$. Similarly, $L_{1}$ is a good output if $\max\{y_{2\hat{j}-1},y_{2\hat{j}}\}>L_{1}$. In any case, at least one out of $L_{0},L_{1}$ is a good output.

If both $L_{0}$ and $L_{1}$ are good outputs, then Step 8 cannot fail. We have already established the existence of $L_{0}\leq y_{i^{\prime}}\leq L_{1}$. Hence, if $L_{1}$ is not a good output, then there are at most $(k{-}1)$ elements $x_{i}\in S$ s.t. $x_{i}\geq L_{1}$. Hence, the probability of $\widehat{big}\geq 3k/2$ and Step 8 failing is at most $\exp(-\frac{\epsilon k}{2})\leq\beta$. It remains to analyze the case where $L_{0}$ is not a good output (and $L_{1}$ is).

If $L_{0}$ is not a good output, then every $x_{j}\in S$ satisfies $x_{j}>L_{0}$. In particular, $\min\{y_{2\hat{j}-1},y_{2\hat{j}}\}>L_{0}$, and, hence, $\max\{y_{2\hat{j}-1},y_{2\hat{j}}\}>L_{1}$. Recall that there are at least $2k$ elements in $S$ which are bigger than $\max\{y_{2\hat{j}-1},y_{2\hat{j}}\}$. As $k\geq\frac{2}{\epsilon}\ln(\frac{1}{\beta})$, the probability that $\widehat{big}<3k/2$ and RecPrefix fails to return $L_{1}$ in this case is at most $\beta$.

All in all, RecPrefix fails to return an appropriate $x$ with probability at most $3\beta t$. ∎

We now proceed with the privacy analysis.

When executed for $N$ recursive calls, RecPrefix is $(2\epsilon N,2\delta N)$-differentially private.

The proof is by induction on the number of recursive calls, denoted by $t$. For $t=1$ (i.e., $|X|\leq 32$), then by Proposition 3.5 the exponential mechanism ensures that RecPrefix is $(\epsilon,0)$-differentially private. Assume that the stated lemma holds whenever RecPrefix performs at most $t-1$ recursive calls, and let $S_{1},S_{2}\in X^{*}$ be two neighboring databases on which RecPrefix performs $t$ recursive calls.The recursion depth is determined by $|X|$, which is identical in $S_{1}$ and in $S_{2}$. Let $\mathcal{B}$ denote an algorithm consisting of steps 1-4 of RecPrefix (the output of $\mathcal{B}$ is the value $z$ from Step 4). Consider the executions of $\mathcal{B}$ on $S_{1}$ and on $S_{2}$, and denote by $Y_{1},S^{\prime}_{1}$ and by $Y_{2},S^{\prime}_{2}$ the elements $Y,S^{\prime}$ as they are in the executions on $S_{1}$ and on $S_{2}$.

We show that the distributions on the databases $S^{\prime}_{1}$ and $S^{\prime}_{2}$ are similar in the sense that for each database in one of the distributions there exist a neighboring database in the other that have the same probability. Thus, applying the recursion (which is differentially private by the inductive assumption) preserves privacy. We now make this argument formal.

First note that as $S_{1},S_{2}$ differ in only one element, there is a bijection between orderings $\Pi$ and $\widehat{\Pi}$ of the smallest $(n-2k)$ elements of $S_{1}$ and of $S_{2}$ respectively s.t. $Y_{1}$ and $Y_{2}$ are neighboring databases. This is because there exists a permutation of the smallest $(n-2k)$ elements of $S_{1}$ that is a neighbor of the smallest $(n-2k)$ elements of $S_{2}$; composition with this fixed permutation yields the desired bijection. Moreover, note that whenever $Y_{1},Y_{2}$ are neighboring databases, the same is true for $S^{\prime}_{1}$ and $S^{\prime}_{2}$. Hence, for every set of outputs $F$ it holds that

So when executed for $t$ recursive calls, the sequence of Steps 1-4 of RecPrefix is $(2\epsilon(t{-}1),2\delta(t{-}1))$-differentially private. On Steps 5 and 7, algorithm RecPrefix interacts with its database through the choosing mechanism and using the Laplace mechanism, each of which is $(\epsilon,\delta)$-differentially private. By composition (Lemma 2.2), we get that RecPrefix is $(2t\epsilon,2t\delta)$-differentially private. ∎

Combining Lemma 3.11 and Lemma 3.13 we obtain Theorem 3.4.

3.3 Informal Discussion and Open Questions

An natural open problem is to close the gap between our (roughly) $2^{\log^{*}|X|}$ upper bound on the sample complexity of privately solving the interior point problem (Theorem 3.4), and our $\log^{*}|X|$ lower bound (Theorem 3.2). Below we describe an idea for reducing the upper bound to $\mathop{\rm{poly}}\nolimits(\log^{*}|X|)$.

In our recursive construction for the lower bound, we took $n$ elements $(x_{1},\ldots,x_{n})$ and generated $n+1$ elements where $y_{0}$ is a random element (independent of the $x_{i}$’s), and every $x_{i}$ is the length of the longest common prefix of $y_{0}$ and $y_{i}$. Therefore, a change limited to one $x_{i}$ affects only one $y_{i}$ and privacy is preserved (assuming that our future manipulations on $(y_{0},\ldots,y_{n})$ preserve privacy). While the representation length of domain elements grows exponentially on every step, the database size grows by 1. This resulted in the $\Omega(\log^{*}|X|)$ lower bound.

In RecPrefix on the other hand, every level of recursion shrank the database size by a factor of $\frac{1}{2}$, and hence, we required a sample of (roughly) $2^{\log^{*}|X|}$ elements. Specifically, in each level of recursion, two input elements $y_{2j-1},y_{2j}$ were paired and a new element $z_{j}$ was defined as the length of their longest common prefix. As with the lower bound, we wanted to ensure that a change limited to one of the inputs affects only one new element, and hence, every input element is paired only once, and the database size shrinks.

If we could pair input elements twice then the database size would only be reduced additively (which will hopefully result in a $\mathop{\rm{poly}}\nolimits(\log^{*}|X|)$ upper bound). However, this must be done carefully, as we are at risk of deteriorating the privacy parameter $\epsilon$ by a factor of $2$ and thus remaining with an exponential dependency in $\log^{*}|X|$. Consider the following thought experiment for pairing elements.

Input: $(x_{1},\ldots,x_{n})\in X^{n}$. 1. Let $(y_{1}^{0},\ldots,y_{n}^{0})$ denote a random permutation of $(x_{1},\ldots,x_{n})$. 2. For $t=1$ to $\log^{*}|X|$: For $i=1$ to $(n{-}t)$, let $y_{i}^{t}$ be the length of the longest common prefix of $y_{i}^{t-1}$ and $y_{i+1}^{t-1}$.

As (most of the) elements are paired twice on every step, the database size reduces additively. In addition, every input element $x_{i}$ affects at most $t+1$ elements at depth $t$, and the privacy loss is acceptable. However, this still does not solve the problem. Recall that every iteration of RecPrefix begins by randomly shuffling the inputs. Specifically, we needed to ensure that (w.h.p.) the number of “close” pairs is limited. The reason was that if a “not close” pair agrees on a prefix $L$, then $L$ is the prefix “a lot” of other elements as well, and we could privately identify $L$. In the above process we randomly shuffled only the elements at depth . Thus we do not know if the number of “close” pairs is small at depth $t>0$. On the other hand, if we changed the pairing procedure to shuffle at every step, then each input element $x_{i}$ might affect $2^{t}$ elements at depth $t$, causing the privacy loss to deteriorate rapidly.

Query Release and Distribution Learning

Recall that a counting query $q$ is a predicate $q:X\to\{0,1\}$. For a database $D=(x_{1},\dots,x_{n})\in X^{n}$, we write $q(D)$ to denote the average value of $q$ over the rows of $D$, i.e. $q(D)=\frac{1}{n}\sum_{i=1}^{n}q(x_{i}).$ In the query release problem, we seek differentially private algorithms that can output approximate answers to a family of counting queries $Q$ simultaneously.

We are interested in the query release problem for the class $\operatorname*{\tt THRESH}_{X}$ of threshold queries, which we view as a class of counting queries.

We are also interested in the following distribution learning problem, which is very closely related to the query release problem.

We highlight two important special cases of the distance measure $d_{Q}$ in the distribution learning problem. First, when $Q$ is the collection of all counting queries on a domain $X$, the distance $d_{Q}$ is the total variation distance between distributions, defined by

Let $\mathcal{D}$ be a distribution over a totally ordered domain $X$. The CDF $F_{\mathcal{D}}$ of $\mathcal{D}$ is defined by $F_{\mathcal{D}}(t)=\Pr_{x\sim\mathcal{D}}[x\leq t]$. If $X$ is finite, then any function $F:X\to$ that is non-decreasing with $F(\max X)=1$ is a CDF.

Algorithm $A$ is an $(\alpha,\beta)$-accurate distribution learner with respect to Kolmogorov distance with sample complexity $n$ if for all distributions $\mathcal{D}$ on a totally ordered domain $X$, given an input of $n$ samples $D=(x_{1},\dots,x_{n})$ where each $x_{i}$ is drawn i.i.d. from $\mathcal{D}$, algorithm $A$ outputs a CDF $F$ with $\sup_{x\in X}|F(x)-F_{\mathcal{D}}(x)|$ with probability at least $1-\beta$.

The query release problem for a collection of counting queries $Q$ is very closely related to the distribution learning problem with respect to $Q$. In particular, solving the query release problem on a dataset $D$ amounts to learning the empirical distribution of $D$. Conversely, results in statistical learning theory show that one can solve the distribution learning problem by first solving the query release problem on a sufficiently large random sample, and then fitting a distribution to approximately agree with the released answers. The requisite size of this sample (without privacy considerations) is characterized by a combinatorial measure of the class $Q$ called the VC dimension:

Let $Q$ be a collection of queries over domain $X$. A set $S=\{x_{1},\dots,x_{k}\}\subseteq X$ is shattered by $Q$ if for every $T\subseteq[k]$ there exists $q\in Q$ such that $T=\{i:q(x_{i})=1\}$. The Vapnik-Chervonenkis (VC) dimension of $Q$, denoted $\operatorname{\rm VC}(Q)$, is the cardinality of the largest set $S\subseteq X$ that is shattered by $Q$.

It is known [AB09] that solving the query release problem on $256\operatorname{\rm VC}(Q)\ln(48/\alpha\beta)/\alpha^{2}$ random samples yields an $(\alpha,\beta)$-accurate distribution learner for a query class $Q$.

2 Equivalences with the Interior Point Problem

We show that the problems of privately releasing thresholds and solving the interior point problem are equivalent.

Let $X$ be a totally ordered domain. Then,

If there exists an $(\varepsilon,\delta)$-differentially private algorithm that is able to release threshold queries on $X$ with $(\alpha,\beta)$-accuracy and sample complexity $n/(8\alpha)$, then there is an $(\varepsilon,\delta)$-differentially private algorithm that solves the interior point problem on $X$ with error $\beta$ and sample complexity $n$.

If there exists an $(\varepsilon,\delta)$-differentially private algorithm solving the interior point problem on $X$ with error $\alpha\beta/24$ and sample complexity $m$, then there is a $(5\varepsilon,(1+e^{\varepsilon})\delta)$-differentially private algorithm for releasing threshold queries with $(\alpha,\beta)$-accuracy and sample complexity

For the first direction, observe that an algorithm for releasing thresholds could easily be used for solving the interior point problem. Formally,

Suppose $\mathcal{A}$ is a private $(\alpha,\beta)$-accurate algorithm for releasing thresholds over $X$ for databases of size $\frac{n}{8\alpha}$. Define $\mathcal{A}^{\prime}$ on databases of size $n$ to pad the database with an equal number of $\min\{X\}$ and $\max\{X\}$ entries, and run $\mathcal{A}$ on the result. We can now return any point $t$ for which the approximate answer to the query $c_{t}$ is $(\frac{1}{2}\pm\alpha)$ on the (padded) database. ∎

We now show the converse, i.e., that the problem of releasing thresholds can be reduced to the interior point problem. Specifically, we reduce the problem to a combination of solving the interior point problem, and of releasing thresholds on a much smaller data universe. The latter task is handled by the following algorithm.

In Appendix C, we describe another reduction that, up to constant factors, gives the same sample complexity.

Let $R:X^{*}\to X$ be an $(\varepsilon,\delta)$-differentially private algorithm solving the interior point problem on $X$ with error $\alpha\beta/24$ and sample complexity $m$. We may actually assume that $R$ is differentially private in the sense that if $D\in X^{*}$ and $D^{\prime}$ differs from $D$ up to the addition or removal of a row, then for every $S\subseteq X$, $\Pr[R(D)\in S]\leq e^{\varepsilon}\Pr[R(D^{\prime})\in S]+\delta$, and that $R$ solves the interior point problem with probability at least $1-\alpha\beta/24$ whenever its input is of size at least $m$. This is because we can pad databases of size less than $m$ with an arbitrary fixed element, and subsample the first $m$ entries from any database with size greater than $m$.

Consider the following algorithm for answering thresholds on databases $D\in X^{n}$ for $n>m$:

Let $D=(x_{1},\dots,x_{n})$ where $x_{1}\leq x_{2}\leq\dots\leq x_{n}$, and consider a neighboring database $D^{\prime}=(x_{1},\dots,x_{i}^{\prime},\dots,x_{n})$. Assume without loss of generality that $x_{i}^{\prime}\geq x_{i+1}$, and suppose

Moreover, under the bijection we constructed between $\nu$ and $\nu^{\prime}$, noise vector $\nu^{\prime}$ is sampled with density at most $e^{2\varepsilon}$ times the density of $\nu$, so for every set $S\subseteq X^{m}$,

Finally, the execution of $A$ at the end of the algorithm is $\varepsilon$-differentially private, so by composition (Lemma 2.2), we obtain the asserted level of privacy.

We can produce $\alpha$-accurate answers to every threshold function as long as

The partitioning exhausts the database, i.e. every element of $D$ is in some $D_{i}$,

Every execution of $R$ succeeds at finding an interior point,

Every database $D_{i}$ has size at most $5\alpha n/12$ (ensuring that we have error at most $5\alpha/6$ from interpolation),

The answers obtained from executing $A$ all have error at most $\alpha/6$.

We now estimate the probabilities of each event. For each $i$ we have $\nu_{i}\geq-\alpha n/6$ with probability at least

So by a union bound, every $\nu_{i}$ is at least $(-\alpha n/6)$ with probability at least $1-\beta/4$. If this is the case, then item 1 holds because $t_{k}=k\cdot\alpha n/3+\nu_{1}+\dots+\nu_{k}\geq(6/\alpha)(\alpha n/3)+(6/\alpha)(-\alpha n/6)\geq n$. Moreover, if every $\nu_{i}\geq-\alpha n/6$, then item 2 also holds with probability at least $1-\beta/4$. This is because every $|D_{i}|\geq\alpha n/3-\alpha n/6\geq m$, and hence every execution of $R$ on a subdatabase $D_{i}$ succeeds with probability $1-\alpha\beta/24$.

By a similar argument, property 3 holds as long as each noise value $\nu_{i}$ is at most $\alpha n/12$, which happens with probability at least $1-\beta/4$. Finally, property 4 holds with probability at least $1-\beta/4$ since

A union bound over the four properties completes the proof. ∎

2.2 Releasing Thresholds vs. Distribution Learning

Query release and distribution learning are very similar tasks: A distribution learner can be viewed as an algorithm for query release with small error w.r.t. the underlying distribution (rather than the fixed input database). We show that the two tasks are equivalent under differential privacy.

Let $Q$ be a collection of counting queries over a domain $X$.

If there exists an $(\varepsilon,\delta)$-differentially private algorithm for releasing $Q$ with $(\alpha,\beta)$-accuracy and sample complexity $n\geq 256\operatorname{\rm VC}(Q)\ln(48/\alpha\beta)/\alpha^{2}$, then there is an $(\varepsilon,\delta)$-differentially private $(3\alpha,2\beta)$-accurate distribution learner w.r.t. $Q$ with sample complexity $n$.

If there exists an $(\varepsilon,\delta)$-differentially private $(\alpha,\beta)$-accurate distribution learner w.r.t. $Q$ with sample complexity $n$, then there is an $(\varepsilon,\delta)$-differentially private query release algorithm for $Q$ with $(\alpha,\beta)$-accuracy and sample complexity $9n$.

The first direction follows from a standard generalization bound, showing that if a given database $D$ contains (enough) i.i.d. samples from a distribution $\mathcal{D}$, then (w.h.p.) accuracy with respect to $D$ implies accuracy with respect to $\mathcal{D}$. We remark that the sample complexity lower bound on $n$ required to apply item 1 of Theorem 4.8 does not substantially restrict its applicability: It is known that an $(\varepsilon,\delta)$-differentially private algorithm for releasing $Q$ always requires sample complexity $\Omega(\operatorname{\rm VC}(Q)/\alpha\varepsilon)$ anyway [BLR08].

We now use the following generalization theorem to show that (w.h.p.) $q(D)$ is close to $q(\mathcal{D})$ for every $q\in Q$.

Let $Q$ be a collection of counting queries over a domain $X$. Let $D=(x_{1},\dots,x_{n})$ consist of i.i.d. samples from a distribution $\mathcal{D}$ over $X$. If $d=\operatorname{\rm VC}(Q)$, then

Using the above theorem, together with the fact that $n\geq 256\operatorname{\rm VC}(Q)\ln(48/\alpha\beta)/\alpha^{2}$, we see that except with probability at least $1-\beta$ we have that $|q(D)-q(\mathcal{D}))|\leq\alpha$ for every $q\in Q$. By a union bound (and the triangle inequality) we get that $\mathcal{A}$ is $(3\alpha,2\beta)$-accurate. ∎