Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

Introduction

Learning is often applied to collections of sensitive data of individuals and it is important to protect the privacy of these individuals. We examine the sample complexity of private learning and a related task – sanitization – while preserving differential privacy . We show striking differences between the required sample complexity for these tasks under $\epsilon$-differential privacy (also called pure differential privacy) and its variant $(\epsilon,\delta)$-differential privacy (also called approximate differential privacy).

Differential privacy protects the privacy of individuals by requiring that the information of an individual does not significantly affect the output. More formally, an algorithm $A$ satisfies the requirement of Pure Differential Privacy if for every two databases that differ on exactly one entry, and for every event defined over the output set of $A$, the probability of this event is close up to a multiplicative factor of $e^{\epsilon}\approx 1+\epsilon$ whether $A$ is applied on one database or on the other. Approximate Differential Privacy is a relaxation of pure differential privacy where the above guarantee needs to be satisfied only for events whose probability is at least $\approx\delta$. We show that even negligible $\delta>0$ can have a significant effect on sample complexity of private learning and sanitization.

Private learning was introduced in as a combination of Valiant’s PAC learning model and differential privacy. For now, we can think of a private learner as a differentially private algorithm that operates on a set of classified random examples, and outputs a hypothesis that misclassifies fresh examples with probability at most (say) $\frac{1}{10}$. The work on private learning has mainly focused on pure privacy. On the one hand, Blum et al. and Kasiviswanathan et al. have showed, via generic constructions, that every finite concept class $C$ can be learned privately, using sample complexity proportional to $\mathop{\rm{poly}}\nolimits(\log|C|)$ (often efficiently). On the other hand, a significant difference was shown between the sample complexity of traditional (non-private) learners (crystallized in terms of $\operatorname{\rm VC}(C)$ and smaller than $\log|C|$ in many interesting cases) and private learners. As an example, let $\operatorname{\tt POINT}_{d}$ be the class of point functions over the domain $\{0,1\}^{d}$ (these are the functions that evaluate to one on exactly one point of the domain and to zero elsewhere). Consider the task of properly learning $\operatorname{\tt POINT}_{d}$ where, after consulting its sample, the learner outputs a hypothesis that is by itself in $\operatorname{\tt POINT}_{d}$. Non-privately, learning $\operatorname{\tt POINT}_{d}$ requires merely a constant number of examples (as $\operatorname{\rm VC}(\operatorname{\tt POINT}_{d})=1$). Privately, $\Omega(d)$ examples are required . Curiously, the picture changes when the private learner is allowed to output a hypothesis not in $\operatorname{\tt POINT}_{d}$ (such learners are called improper), as the sample complexity can be reduced to $O(1)$ . This, however, comes with a price, as it was shown in that such learners must return hypotheses that evaluate to one on exponentially many points in $\{0,1\}^{d}$ and, hence, are very far from all functions in $\operatorname{\tt POINT}_{d}$.

A complete characterization for the sample complexity of pure-private learners was recently given in , in terms of a new dimension – the Representation Dimension, that is, given a class $C$, the number of samples needed and sufficient for privately learning $C$ is $\Theta(\operatorname{\rm RepDim}(C))$. Following that, Feldman and Xiao showed an equivalence between the representation dimension of a concept $C$ and the randomized one-way communication complexity of the evaluation problem for concepts from $C$. Using this equivalence they separated the sample complexity of pure-private learners from that of non-private ones. For example, they showed a lower bound of $\Omega(d)$ on the sample complexity of every pure-private (proper or improper) learner for the class $\operatorname*{\tt THRESH}_{d}$ of threshold functions over the interval $[0,2^{d}-1]$. This is a strong separation from the non-private sample complexity, which is $O(1)$ (as the VC dimension of this class is constant).

We show that the sample complexity of proper learning with approximate differential privacy can be significantly lower than that satisfying pure differential privacy. Our starting point for this work is an observation that with approximate $(\epsilon,\delta)$-differential privacy, sample complexity of $O(\log(1/\delta))$ suffices for learning points properly. This gives a separation between pure and approximate proper private learning for $\delta=2^{-o(d)}$.

The notion of differentially private sanitization was introduced in the work of Blum et al. . A sanitizer for a class of predicates $C$ is a differentially private mechanism translating an input database $S$ to an output database $\hat{S}$ such that $\hat{S}$ (approximately) agrees with $S$ on the fraction of the entries satisfying $\varphi$ for all $\varphi\in C$, where every predicate $\varphi\in C$ is a function from $X$ to $\{0,1\}$. Blum et al. gave a generic construction of pure differentially private sanitizers exhibiting sample complexity $O(\operatorname{\rm VC}(C)\log|X|)$. Lower bounds partially supporting this sample complexity were given by . As with private learning, we show significant differences between the sample complexity required for sanitization of simple predicate classes under pure and approximate differential privacy. We note that the construction of sanitizers is not generally computationally feasible .

1 Our Contributions

To simplify the exposition, we omit in this section dependency on all variables except for $d$, corresponding to the representation length of domain elements.

A recent instantiation of the Propose-Test-Release (PTR) framework by Smith and Thakurta results, almost immediately, with a proper learner for points, exhibiting $O(1)$ sample complexity while preserving approximate differential privacy. This simple technique does not suffice for our other constructions of learners and sanitizers, and we, hence, introduce new tools for coping with proper private learning of thresholds and axis-aligned rectangles, and sanitization for point functions and thresholds:

Choosing mechanism: Given a low-sensitivity quality function, one can use the exponential mechanism to choose an approximately maximizing solution. This requires, in general, a database of size logarithmic in the number of possible solutions. We identify a sub family of low-sensitivity functions, called bounded-growth functions, for which it is possible to significantly reduce the necessary database size when using the exponential mechanism.

Recursive algorithm for quasi-concave promise problems: We define a family of optimization problems, which we call Quasi-Concave Promise Problems. The possible solutions are ordered, and quasi-concavity means that if two solutions $f\leq h$ have quality of at least $\mathcal{X}$, then any solution $f\leq g\leq h$ also has quality of at least $\mathcal{X}$. The optimization goal is, when there exists a solution with a promised quality of (at least) $r$, to find a solution with quality $\approx r$. We observe that a quasi-concave promise problem can be privately approximated using a solution to a smaller instance of a quasi-concave promise problem. This allows us to construct an efficient recursive algorithm solving such problems privately. We show that the task of learning $\operatorname*{\tt THRESH}_{d}$ is, in fact, a quasi-concave promise problem, and it can be privately solved using our algorithm with sample size roughly $2^{O(\log^{*}d)}$. Sanitization for $\operatorname*{\tt THRESH}_{d}$ does not exactly fit the model of quasi-concave promise problems but can still be solved by iteratively defining and solving a small number of quasi-concave promise problems.

We give new private proper-learning algorithms for the classes $\operatorname{\tt POINT}_{d}$ and $\operatorname*{\tt THRESH}_{d}$. We also construct a new private proper-learner for (a discrete version of) the class of all axis-aligned rectangles over $n$ dimensions. Our algorithms exhibit sample complexity that is significantly lower than bounds given in prior work, separating pure and approximate private learning. Similarly, we construct sanitizers for $\operatorname{\tt POINT}_{d}$ and $\operatorname*{\tt THRESH}_{d}$, again with sample complexity that is significantly lower than bounds given in prior work, separating sanitization in the pure and approximate privacy cases. Our algorithms are time-efficient.

Gupta et al. have given reductions in both directions between agnostic learning of a concept class $C$, and the sanitization task for the same class $C$. The learners and sanitizers they consider are limited to access their data via statistical queries (such algorithm can be easily transformed to satisfy differential privacy ). In Section 5 we show a similar reduction from the task of privately learning a concept class $C$ to the sanitization task of $C$, where the sanitizer’s access to the database is unrestricted. This allows us to exploit lower bounds on the sample complexity of private learners and show an explicit class of predicates $C$ over a domain $X$ for which every private sanitizer requires databases of size $\Omega(\operatorname{\rm VC}(C)\log|X|)$. A similar lower bound was shown by Hardt and Rothblum , achieving tighter results in terms of the approximation parameter. Their work proves the existence of such a concept class, but does not give an explicit one.

In Section 6 we examine private learning under a relaxation of differential privacy called label privacy (see and references therein), where the learner is required to only protect the privacy of the labels in the sample. Chaudhuri et al. have proved lower bounds for label-private learners in terms of the doubling dimension of the target concept class. We show that the VC dimension completely characterizes the sample complexity of such learners, that is, the sample complexity of learning with label privacy is equal (up to constants) to learning without privacy.

2 Open Questions

This work raises two kinds of research directions. First, this work presents (time and sample efficient) private learners and sanitizers for relatively simple concept classes. It would be natural to try and construct private learners and sanitizers for more complex concept classes. In particular, constructing a (time and sample efficient) private learner for hyperplanes would be very interesting to the community.

Another very interesting research direction is to try and understand the sample complexity of approximate-private learners. Currently, no lower bounds are known on the sample complexity of such learners. On the other hand, no generic construction for such learners is known to improve the sample complexity achieved by the generic construction of Kasiviswanathan et al. for pure-private learners. Characterizing the sample complexity of approximate-private learners is a very interesting open question.

3 Other Related Work

Most related to our work is the work on private learning and its sample complexity and the early work on sanitization mentioned above. Another related work is the work of De , who proved a separation between pure $\epsilon$-differential privacy and approximate $(\epsilon,\delta)$-differential privacy. Specifically, he demonstrated that there exists a query where it is sufficient to add noise $O(\sqrt{n\log(1/\delta)})$ when $\delta>0$ and $\Omega(n)$ noise is required when $\delta=0$. Earlier work by Hardt and Talwar separated pure from approximate differential privacy for $\delta=n^{-O(1)}$.

Another interesting gap between pure and approximate differential privacy is the following. Blum et al. have given a generic construction of pure-private sanitizers, in which the sample complexity grows as $\frac{1}{\alpha^{3}}$ (where $\alpha$ is the approximation parameter). Following that, Hardt and Rothblum showed that with approximate-privacy, the sample complexity can be reduce to grow as $\frac{1}{\alpha^{2}}$. Currently, it is unknown whether this gap is essential.

Preliminaries

We use $O_{\gamma}(f(t))$ as a shorthand for $O(h(\gamma)\cdot f(t))$ for some non-negative function $h$. In informal discussions, we sometimes use $\widetilde{O}(f(t))$ instead of $O(f(t)\cdot{\rm polylog}(f(t)))$. For example, $2^{\log^{*}(d)}\cdot\log^{*}(d)=\widetilde{O}\left(2^{\log^{*}(d)}\right)$.

We use $X$ to denote an arbitrary domain, and $X_{d}$ for the domain $\{0,1\}^{d}$. We use $X^{m}$ (and respectively $X_{d}^{m}$) for the cartesian $m^{\text{t}h}$ power of $X$, i.e., $X^{m}=(X)^{m}$, and use $X^{*}=\bigcup_{m=0}^{\infty}{X^{m}}$.

Given a distribution $\mathcal{D}$ over a domain $X$, we denote $\mathcal{D}(j)\triangleq\Pr_{x\sim\mathcal{D}}[x=j]$ for $j\in X$, and $\mathcal{D}(J)\triangleq\Pr_{x\sim\mathcal{D}}[x\in J]$ for $J\subseteq X$.

1 Differential Privacy

Differential privacy aims at protecting information of individuals. We consider a database, where each entry contains information pertaining to an individual. An algorithm operating on databases is said to preserve differential privacy if a change of a single record of the database does not significantly change the output distribution of the algorithm. Intuitively, this means that whatever is learned about an individual could also be learned with her data arbitrarily modified (or without her data). Formally:

Databases $S_{1}\in X^{m}$ and $S_{2}\in X^{m}$ over a domain $X$ are called neighboring if they differ in exactly one entry.

A randomized algorithm $A$ is $(\epsilon,\delta)$-differentially private if for all neighboring databases $S_{1},S_{2}\in X^{m}$, and for all sets $\mathcal{F}$ of outputs,

The probability is taken over the random coins of $A$. When $\delta=0$ we omit it and say that $A$ preserves $\epsilon$-differential privacy.

We use the term pure differential privacy when $\delta=0$ and the term approximate differential privacy when $\delta>0$, in which case $\delta$ is typically a negligible function of the database size $m$.

We will later present algorithms that access their input database using (several) differentially private mechanisms. We will use the following composition theorems.

If $A_{1}$ and $A_{2}$ satisfy $(\epsilon_{1},\delta_{1})$ and $(\epsilon_{2},\delta_{2})$ differential privacy, respectively, then their concatenation $A(S)=\langle A_{1}(S),A_{2}(S)\rangle$ satisfies $(\epsilon_{1}+\epsilon_{2},\delta_{1}+\delta_{2})$-differential privacy.

Moreover, a similar theorem holds for the adaptive case, where a mechanism interacts with $k$ adaptively chosen differentially private mechanisms.

A mechanism that permits $k$ adaptive interactions with mechanisms that preserves $(\epsilon,\delta)$-differential privacy (and does not access the database otherwise) ensures $(k\epsilon,k\delta)$-differential privacy.

Note that the privacy guaranties of the above bound deteriorates linearly with the number of interactions. By bounding the expected privacy loss in each interaction (as opposed to worst-case), Dwork et al. showed the following stronger composition theorem, where privacy deteriorates (roughly) as $\sqrt{k}\epsilon+k\epsilon^{2}$ (rather than $k\epsilon$).

Let $0<\epsilon,\delta^{\prime}\leq 1$, and let $\delta\in$. A mechanism that permits $k$ adaptive interactions with mechanisms that preserves $(\epsilon,\delta)$-differential privacy (and does not access the database otherwise) ensures $(\epsilon^{\prime},k\delta+\delta^{\prime})$-differential privacy, for $\epsilon^{\prime}=\sqrt{2k\ln(1/\delta^{\prime})}\cdot\epsilon+2k\epsilon^{2}$.

2 Preliminaries from Learning Theory

A concept $c:X\rightarrow\{0,1\}$ is a predicate that labels examples taken from the domain $X$ by either 0 or 1. A concept class $C$ over $X$ is a set of concepts (predicates) mapping $X$ to $\{0,1\}$. A learning algorithm is given examples sampled according to an unknown probability distribution $\mathcal{D}$ over $X$, and labeled according to an unknown target concept $c\in C$. The learning algorithm is successful when it outputs a hypothesis $h$ that approximates the target concept over samples from $\mathcal{D}$. More formally:

The generalization error of a hypothesis $h:X\rightarrow\{0,1\}$ is defined as

If ${\rm error}_{\mathcal{D}}(c,h)\leq\alpha$ we say that $h$ is $\alpha$-good for $c$ and $\mathcal{D}$.

Algorithm $A$ is an $(\alpha,\beta,m)$-PAC learner for a concept class $C$ over $X$ using hypothesis class $H$ if for all concepts $c\in C$, all distributions $\mathcal{D}$ on $X$, given an input of $m$ samples $S=(z_{1},\ldots,z_{m})$, where $z_{i}=(x_{i},c(x_{i}))$ and each $x_{i}$ is drawn i.i.d. from $\mathcal{D}$, algorithm $A$ outputs a hypothesis $h\in H$ satisfying

The probability is taken over the random choice of the examples in $S$ according to $\mathcal{D}$ and the coin tosses of the learner $A$. If $H\subseteq C$ then $A$ is called a proper PAC learner; otherwise, it is called an improper PAC learner.

For a labeled sample $S=(x_{i},y_{i})_{i=1}^{m}$, the empirical error of $h$ is

2.2 The Vapnik-Chervonenkis Dimension

The Vapnik-Chervonenkis (VC) Dimension is a combinatorial measure of concept classes, which characterizes the sample size of PAC learners.

That is, $B$ is shattered by $C$ if $C$ realizes all possible dichotomies over $B$.

The VC-Dimension of a concept class $C$ (over a domain $X$), denoted as $\operatorname{\rm VC}(C)$, is the cardinality of the largest set $B\subseteq X$ shattered by $C$. If arbitrarily large finite sets can be shattered by $C$, then $\operatorname{\rm VC}(C)=\infty$.

Observe that as $\Pi_{C}(B)\leq|C|$ a set $B$ can be shattered only if $|B|\leq\log|C|$ and hence $\operatorname{\rm VC}(C)\leq\log|C|$.

2.3 VC Bounds

Classical results in computational learning theory state that a sample of size $\theta(\operatorname{\rm VC}(C))$ is both necessary and sufficient for the PAC learning of a concept class $C$. The following two theorems give upper and lower bounds on the sample complexity.

Any algorithm for PAC learning a concept class $C$ must have sample complexity $\Omega(\frac{\operatorname{\rm VC}(C)}{\alpha})$, where $\alpha$ is the approximation parameter.

Let $C$ and $\mathcal{D}$ be a concept class and a distribution over a domain $X$. Let $\alpha,\beta>0$, and $m\geq\frac{8}{\alpha}(\operatorname{\rm VC}(C)\ln(\frac{16}{\alpha})+\ln(\frac{2}{\beta}))$. Fix a concept $c\in C$, and suppose that we draw a sample $S=(x_{i},y_{i})_{i=1}^{m}$, where $x_{i}$ are drawn i.i.d. from $\mathcal{D}$ and $y_{i}=c(x_{i})$. Then,

So, for any concept class $C$, any algorithm that takes a sample of $m=\Omega_{\alpha,\beta}(\operatorname{\rm VC}(C))$ labeled examples and produces as output a concept $h\in C$ that agrees with the sample is a PAC learner for $C$. Such an algorithm is a PAC learner for $C$ using $C$ (that is, both the target concept and the returned hypotheses are taken from the same concept class $C$), and, therefore, there always exist a hypothesis $h\in C$ with ${\rm error}_{S}(h)=0$ (e.g., the target concept itself).

The next theorem handles (in particular) the agnostic case, in which a learning algorithm for a concept class $C$ is using a hypotheses class $H\neq C$, and given a sample $S$ (labeled by some $c\in C$), a hypothesis $h$ with ${\rm error}_{S}(h)=0$ might not exist in $H$.

Let $\mathcal{D}$ and $H$ be a distribution and a concept class over a domain $X$, and let $f:X\rightarrow\{0,1\}$ be some concept, not necessarily in $H$. For a sample $S=(x_{i},f(x_{i}))_{i=1}^{m}$ where $m\geq\frac{50\operatorname{\rm VC}(H)}{\alpha^{2}}\ln(\frac{1}{\alpha\beta})$ and $\{x_{i}\}$ are drawn i.i.d. from $\mathcal{D}$, it holds that

Notice that in the agnostic case the sample complexity is proportional to $\frac{1}{\alpha^{2}}$, as opposed to $\frac{1}{\alpha}$ when learning a class $C$ using $C$.

3 Private Learning

In private learning, we would like to accomplish the same goal as in non-private learning, while protecting the privacy of the input database.

Let $A$ be an algorithm that gets an input $S=\{z_{1},\ldots,z_{m}\}$. Algorithm $A$ is an $(\alpha,\beta,\epsilon,\delta,m)$-PPAC learner for a concept class $C$ over $X$ using hypothesis class $H$ if

Privacy. Algorithm $A$ is $(\epsilon,\delta)$-differentially private (as in Definition 2.2);

Utility. Algorithm $A$ is an $(\alpha,\beta,m)$-PAC learner for $C$ using $H$ (as in Definition 2.7).

When $\delta=0$ (pure privacy) we omit it from the list of parameters.

Note that the utility requirement in the above definition is an average-case requirement, as the learner is only required to do well on typical samples (i.e., samples drawn i.i.d. from a distribution $\mathcal{D}$ and correctly labeled by a target concept $c\in C$). In contrast, the privacy requirement is a worst-case requirement, and Inequality (1) must hold for every pair of neighboring databases (no matter how they were generated, even if they are not consistent with any concept in $C$).

4 Sanitization

Given a database $S=(x_{1},\ldots,x_{m})$ containing elements from some domain $X$, the goal of sanitization mechanisms is to output (while preserving differential privacy) another database $\hat{S}$ that is in some sense similar to $S$. This returned database $\hat{S}$ is called a sanitized database.

Let $c:X\rightarrow\{0,1\}$ be a concept. The counting query $Q_{c}:X^{*}\rightarrow$ is

That is, $Q_{c}(S)$ is the fraction of the entries in $S$ that satisfy the concept $c$. Given a database $S$, a sanitizer for a concept class $C$ is required to output a sanitized database $\hat{S}$ s.t. $Q_{c}(S)\approx Q_{c}(\hat{S})$ for every $c\in C$. For computational reasons, sanitizers are sometimes allowed not to return an actual database, but rather a data structure capable of approximating $Q_{c}(S)$ for every $c\in C$.

Let $C$ be a concept class and let $S$ be a database. A function $\operatorname{\rm Est}:C\rightarrow$ is called $\alpha$-close to $S$ if $|Q_{c}(S)-\operatorname{\rm Est}(c)|\leq\alpha$ for every $c\in C$. If, furthermore, $\operatorname{\rm Est}$ is defined in terms of a database $\hat{S}$, i.e., $\operatorname{\rm Est}(c)=Q_{c}(\hat{S})$, we say that $\hat{S}$ is $\alpha$-close to $S$.

Let $C$ be a class of concepts mapping $X$ to $\{0,1\}$. Let $A$ be an algorithm that on an input database $S\in X^{*}$ outputs a description of a function $\operatorname{\rm Est}:C\rightarrow$. Algorithm $A$ is an $(\alpha,\beta,\epsilon,\delta,m)$-improper-sanitizer for predicates in the class $C$, if

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

For every input $S\in X^{m}$, it holds that \Pr\limits_{A}\left[\mbox{\rm\operatorname{\rm Est}$is$\alpha$-close to$S}\right]\geq 1-\beta.

The probability is over the coin tosses of algorithm $A$. If on an input database $S$ algorithm $A$ outputs another database $\hat{S}\in X^{*}$, and $\operatorname{\rm Est}(\cdot)$ is defined as $\operatorname{\rm Est}(c)=Q_{c}(\hat{S})$, then algorithm $A$ is called a proper-sanitizer (or simply a sanitizer). As before, when $\delta=0$ (pure privacy) we omit it from the set of parameters.

Note that without the privacy requirements sanitization is a trivial task as it is possible to simply output the input database $S$. Furthermore, ignoring computational complexity, an $(\alpha,\beta,\epsilon,\delta,m)$-improper-sanitizer can always be transformed into a $(2\alpha,\beta,\epsilon,\delta,m)$-sanitizer, by finding a database $\hat{S}$ of $m$ entries that is $\alpha$-close to $\operatorname{\rm Est}$. Such a database must exist except with probability $\beta$ (as in particular $S$ is $\alpha$-close to $\operatorname{\rm Est}$), and is $2\alpha$-close to $S$ (by the triangle inequality).

The following theorems state some of the known results on the sample complexity of pure-privacy sanitizers. We start with an upper bound on the necessary sample complexity.

There exists a constant $\Gamma$ such that for any class of predicates $C$ over a domain $X$, and any parameters $\alpha,\beta,\epsilon$, there exists an $(\alpha,\beta,\epsilon,m)$-sanitizer for $C$, provided that the size of the database, denoted $m$, is at least

The above theorem states that, in principle, data sanitization is possible. The input database may be required to be as big as the representation size of elements in $X$. The next theorem states a general lower bound (far from the above upper bound) on the sample complexity of any concept class $C$. Better bounds are known for specific concept classes .

Let $C$ be a class of predicates, and let $m\leq\frac{\operatorname{\rm VC}(C)}{2}$. For any $0<\beta<1$ bounded away from 1 by a constant, for any $\epsilon\leq 1$, if $A$ is an $(\alpha,\beta,\epsilon,m)$-sanitizer for $C$, then $\alpha\geq\frac{1}{4+16\epsilon}$.

Recall that a proper sanitizer operates on an input database $S\in X^{m}$, and outputs a sanitized database $\hat{S}\in X^{*}$. The following is a simple corollary of Theorem 2.14, stating that the size of $\hat{S}$ does not necessarily depend on the size of the input database $S$.

Let $C$ be a concept class. For any database $S$ there exists a database $\hat{S}$ of size $n=O(\frac{\operatorname{\rm VC}(C)}{\alpha^{2}}\log(\frac{1}{\alpha}))$ such that $\max_{h\in C}|Q_{h}(S)-Q_{h}(\hat{S})|\leq\alpha$.

In particular, the above theorem implies that an $(\alpha,\beta,\epsilon,\delta,m)$-sanitizer $A$ can always be transformed into a $(2\alpha,\beta,\epsilon,\delta,m)$-sanitizer $A^{\prime}$ s.t. the sanitized databases returned by $A^{\prime}$ are always of fixed size $n=O(\frac{\operatorname{\rm VC}(C)}{\alpha^{2}}\log(\frac{1}{\alpha}))$. This can be done by finding a database $\hat{S}$ of $n$ entries that is $\alpha$-close to the sanitized database returned by $A$. Using the triangle inequality, $\hat{S}$ is (w.h.p.) $2\alpha$-close to the input database.

5 Basic Differentially-Private Mechanisms

The most basic constructions of differentially private algorithms are via the Laplace mechanism as follows.

A random variable has probability distribution $\mathop{\rm{Lap}}\nolimits(b)$ if its probability density function is $f(x)=\frac{1}{2b}\exp(-\frac{|x|}{b})$, where $x\in\R$.

A function $f:X^{m}\rightarrow{}^{n}$ has sensitivity $k$ if for every neighboring $D,D^{\prime}\in X^{m}$, it holds that $||f(D)-f(D^{\prime})||_{1}\leq k$.

Let $f:X^{m}\rightarrow{}^{n}$ be a sensitivity $k$ function. The mechanism $A$ that on input $D\in X^{m}$ adds independently generated noise with distribution $\mathop{\rm{Lap}}\nolimits(\frac{k}{\epsilon})$ to each of the $n$ output terms of $f(D)$ preserves $\epsilon$-differential privacy. Moreover,

where $A_{i}(D)$ and $f_{i}(D)$ are the $i^{\text{t}h}$ coordinates of $A(D)$ and $f(D)$.

5.2 The Exponential Mechanism

We next describe the exponential mechanism of McSherry and Talwar . Let $X$ be a domain and $H$ a set of solutions. Given a quality function $q:X^{*}\times H\rightarrow\N$, and a database $S\in X^{*}$, the goal is to chooses a solution $h\in H$ approximately maximizing $q(S,h)$. The mechanism chooses a solution probabilistically, where the probability mass that is assigned to each solution $h$ increases exponentially with its quality $q(S,h)$:

Input: parameter $\epsilon$, finite solution set $H$, database $S\in X^{m}$, and a sensitivity 1 quality function $q$. 1. Randomly choose $h\in H$ with probability $\frac{\exp\left(\epsilon\cdot q(S,h)/2\right)}{\sum_{f\in H}\exp\left(\epsilon\cdot q(S,f)/2\right)}.$ 2. Output $h$.

(i) The exponential mechanism is $\epsilon$- differentially private. (ii) Let $\hat{e}\triangleq\max_{f\in H}\{q(S,f)\}$ and $\Delta>0$. The exponential mechanism outputs a solution $h$ such that $q(S,h)\leq(\hat{e}-\Delta m)$ with probability at most $|H|\cdot\exp(-\epsilon\Delta m/2)$.

Kasiviswanathan et al. showed in 2008 that the exponential mechanism can be used as a generic private learner – when used with the quality function $q(S,h)=|\{i:h(x_{i})=y_{i}\}|$, the probability that the exponential mechanism outputs a hypothesis $h$ such that ${\rm error}_{S}(h)>\min_{f\in H}\{{\rm error}_{S}(f)\}+\Delta$ is at most $|H|\cdot\exp(-\epsilon\Delta m/2)$. This results in a generic private proper-learner for every finite concept class $C$, with sample complexity $O_{\alpha,\beta,\epsilon}(\log|C|)$.

We restate a simplified variant of algorithm $\mathcal{A}_{\rm dist}$ by Smith and Thakurta , which is an instantiation of the Propose-Test-Release framework . Let $q:X^{*}\times H\rightarrow\N$ be a sensitivity-1 quality function over a domain $X$ and a set of solutions $H$. Given a database $S\in X^{*}$, the goal is to choose a solution $h\in H$ maximizing $q(S,h)$, under the assumption that the optimal solution $h$ scores much better than any other solution in $H$.

Algorithm $\mathcal{A}_{\rm dist}$ Input: parameters $\epsilon,\delta$, database $S\in X^{*}$, sensitivity-1 quality function $q$. 1. Let $h_{1}\neq h_{2}$ be two highest score solutions in $H$, where $q(S,h_{1})\geq q(S,h_{2})$. 2. Let ${\rm gap}=q(S,h_{1})-q(S,h_{2})$ and ${\rm gap}^{*}={\rm gap}+\mathop{\rm{Lap}}\nolimits(\frac{1}{\epsilon})$. 3. If ${\rm gap}^{*}<\frac{1}{\epsilon}\log(\frac{1}{\delta})$ then output $\bot$ and halt. 4. Output $h_{1}$.

(i) Algorithm $\mathcal{A}_{\rm dist}$ is $(\epsilon,\delta)$- differentially private. (ii) When given an input database $S$ for which ${\rm gap}\geq\frac{1}{\epsilon}\log(\frac{1}{\beta\delta})$, algorithm $\mathcal{A}_{\rm dist}$ outputs $h_{1}$ maximizing $q(h,S)$ with probability at least $(1-\beta)$.

6 Concentration Bounds

Learning with Approximate Privacy

We present proper $(\epsilon,\delta)$-private learners for two simple concept classes, $\operatorname{\tt POINT}_{d}$ and $\operatorname*{\tt THRESH}_{d}$, demonstrating separations between pure and approximate private proper learning.

For $j\in X_{d}$ let $c_{j}:X_{d}\rightarrow\{0,1\}$ be defined as $c_{j}(x)=1$ if $x=j$ and $c_{j}(x)=0$ otherwise. Define the concept class $\operatorname{\tt POINT}_{d}=\{c_{j}\}_{j\in X_{d}}$.

Note that the VC dimension of $\operatorname{\tt POINT}_{d}$ is 1, and, therefore, there exists a proper non-private learner for $\operatorname{\tt POINT}_{d}$ with sample complexity $O_{\alpha,\beta}(1)$. Beimel et al. proved that every proper $\epsilon$-private learner for $\operatorname{\tt POINT}_{d}$ must have sample complexity $\Omega(d)=\Omega(\log|\operatorname{\tt POINT}_{d}|)$. They also showed that there exists an improper $\epsilon$-private learner for this class, with sample complexity $O_{\alpha,\beta,\epsilon}(1)$. An alternative private learner for this class was presented in .

As we will now see, algorithm $\mathcal{A}_{\rm dist}$ (defined in Section 2.5) can be used as a proper $(\epsilon,\delta)$-private learner for $\operatorname{\tt POINT}_{d}$ with sample complexity $O_{\alpha,\beta,\epsilon,\delta}(1)$. This is our first (and simplest) example separating the sample complexity of pure and approximate private proper-learners. Consider the following algorithm.

Input: parameters $\alpha,\beta,\epsilon,\delta$, and a database $S\in(X_{d+1})^{m}$. 1. For every $x\in X_{d}$, define $q(S,x)$ as the number of appearances of $(x,1)$ in $S$. 2. Execute $\mathcal{A}_{\rm dist}$ on $S$ with the quality function $q$ and parameters $\frac{\alpha}{2},\frac{\beta}{2},\epsilon,\delta$. 3. If the output was $j$ then return $c_{j}$. 4. Else, if the output was $\bot$ then return a random $c_{i}\in\operatorname{\tt POINT}_{d}$.

Let $\alpha,\beta,\epsilon,\delta$ be s.t. $\frac{1}{\alpha\beta}\leq 2^{d}$. The above algorithm is an efficient $(\alpha,\beta,\epsilon,\delta)$-PPAC proper learner for $\operatorname{\tt POINT}_{d}$ using a sample of $m=O\left(\frac{1}{\alpha\epsilon}\ln(\frac{1}{\beta\delta})\right)$ labeled examples.

For intuition, consider a target concept $c_{j}$ and an underlying distribution $\mathcal{D}$. Whenever $\mathcal{D}(j)$ is noticeable, a typical sample $S$ contains many copies of the point $j$ labeled as $1$. As every other point $i\neq j$ will be labeled as , we expect $q(S,j)$ to be significantly higher than any other $q(S,i)$, and we can use algorithm $\mathcal{A}_{\rm dist}$ to identify $j$.

Recall that the above algorithm outputs a random $c_{i}\in\operatorname{\tt POINT}_{d}$ whenever $\mathcal{A}_{\rm dist}$ outputs $\bot$. In order for this random $c_{i}$ to be good (w.h.p.) we needed $2^{d}$ (i.e., the number of possible concepts) to be at least $\frac{1}{\alpha\beta}$. This requirement could be avoided by outputting the all zero hypothesis $c_{0}\equiv 0$ whenever $\mathcal{A}_{\rm dist}$ outputs $\bot$. However, this approach results in a proper learner only if we add the all zero concept to $\operatorname{\tt POINT}_{d}$.

For $0\leq j\leq 2^{d}$ let $c_{j}:X_{d}\rightarrow\{0,1\}$ be defined as $c_{j}(x)=1$ if $x<j$ and $c_{j}(x)=0$ otherwise. Define the concept class $\operatorname*{\tt THRESH}_{d}=\{c_{j}\}_{0\leq j\leq 2^{d}}$.

Note that $\operatorname{\rm VC}(\operatorname*{\tt THRESH}_{d})=1$, and, therefore, there exists a proper non-private learner for $\operatorname*{\tt THRESH}_{d}$ with sample complexity $O_{\alpha,\beta}(1)$. As $|\operatorname*{\tt THRESH}_{d}|=2^{d}+1$, one can use the generic construction of Kasiviswanathan et al. and get a proper $\epsilon$-private learner for this class with sample complexity $O_{\alpha,\beta,\epsilon}(d)$. Feldman and Xiao showed that this is in fact optimal, and every $\epsilon$-private learner for this class (proper or improper) must have sample complexity $\Omega(d)$.

Our learner for $\operatorname{\tt POINT}_{d}$ relied on a strong “stability” property of the problem: Given a labeled sample, either a random concept is (w.h.p.) a good output, or, there is exactly one consistent concept in the class, and every other concept has large empirical error. This, however, is not the case when dealing with $\operatorname*{\tt THRESH}_{d}$. In particular, many hypotheses can have low empirical error, and changing a single entry of a sample $S$ can significantly affect the set of hypotheses consistent with it.

In Section 3.3, we present a proper $(\epsilon,\delta)$-private learner for $\operatorname*{\tt THRESH}_{d}$ with sample complexity (roughly) $2^{O(\log^{*}(d))}$. We use this section for motivating the construction. We start with two simplifying assumptions. First, when given a labeled sample $S$, we aim at choosing a hypothesis $h\in\operatorname*{\tt THRESH}_{d}$ approximately minimizing the empirical error (rather than the generalization error). Second, we assume that we are given a “diverse” sample $S$ that contains many points labeled as $1$ and many points labeled as . Those two assumptions (and any other informalities made hereafter) will be removed in Section 3.3.

We refer to points labeled as $1$ in $S$ as ones, and to points labeled as as zeros. Imagine for a moment that we already have a differentially private algorithm that given $S$ outputs an interval $G\subseteq X_{d}$ with the following two properties:

The interval $G$ contains “a lot” of ones, and “a lot” of zeros in $S$.

Every interval $I\subseteq X_{d}$ of length $\leq\frac{|G|}{k}$ does not contain, simultaneously, “too many” ones and “too many” zeros in $S$, where $k$ is some constant.

Given such a $4$-good interval $G$, we can (without using the sample $S$) define a set $H$ of five hypotheses s.t. at least one of them has small empirical error. To see this, consider Figure 2, where $G$ is divided into four equal intervals $g_{1},g_{2},g_{3},g_{4}$, and five hypotheses $h_{1},\ldots,h_{5}$ are defined s.t. the points where they switch from one to zero are located at the edges of $g_{1},g_{2},g_{3},g_{4}$.

After defining such a set $H$, we could use the exponential mechanism to choose a hypothesis $h\in H$ with small empirical error on $S$. As the size of $H$ is constant, this requires only a constant number of samples. To conclude, finding a $4$-good interval $G$ (while preserving privacy) is sufficient for choosing a good hypothesis. We next explain how to find such an interval.

Assume, for now, that we have a differentially private algorithm that given a sample $S$, returns an interval length $J$ s.t. there exists a 2-good interval $G\subseteq X_{d}$ of length $|G|=J$. This length $J$ is used to find an explicit 4-good interval as follows. Divide $X_{d}$ into intervals $\{A_{i}\}$ of length $2J$, and into intervals $\{B_{i}\}$ of length $2J$ right shifted by $J$ as in Figure 3.

As the promised $2$-good interval $G$ is of length $J$, at least one of the above intervals contains $G$. We next explain how to privately choose such interval. If, e.g., $G\subseteq A_{2}$ then $A_{2}$ contains both a lot of zeros and a lot of ones. The target concept must switch inside $A_{2}$, and, therefore, every other $A_{i}\neq A_{2}$ cannot contain both zeros and ones. For every interval $A_{i}$, define its quality $q(A_{i})$ to be the minimum between the number of zeros in $A_{i}$ and the number of ones in $A_{i}$. Therefore, $q(A_{2})$ is large, while $q(A_{i})=0$ for every $A_{i}\neq A_{2}$. That is, $A_{2}$ scores much better than any other $A_{i}$ under this quality function $q$. The sensitivity of $q()$ is one and we can use algorithm $\mathcal{A}_{\rm dist}$ to privately identify $A_{2}$. It suffices, e.g., that $q(A_{2})\geq\frac{1}{4}\alpha m$, and we can, therefore, set our “a lot” bound to be $\frac{1}{4}\alpha m$. Recall that $G\subseteq A_{2}$ is a $2$-good interval, and that $|A_{2}|=2|G|$. The identified $A_{2}$ is, therefore, a $4$-good interval.

To conclude, if we could indeed find (while preserving privacy) a length $J$ s.t. there exists a $2$-good interval $G$ of that length, then our task would be completed.

At first attempt, one might consider preforming a binary search for such a length $0\leq J\leq 2^{d}$, in which every comparison will be made using the Laplace mechanism. More specifically, for every length $0\leq J\leq 2^{d}$, define

If, e.g., $Q(J)=100$ for some $J$, then there exists an interval $[a,b]\subseteq X_{d}$ of length $J$ that contains at least $100$ ones and at least $100$ zeros. Moreover, every interval of length $\leq J$ either contains at most $100$ ones, or, contains at most $100$ zeros.

Note that $Q(\cdot)$ is a monotonically non-decreasing function, and that $Q(0)=0$ (as in a correctly labeled sample a point cannot appear both with the label 1 and with the label 0). Recall our assumption that the sample $S$ is “diverse” (contains many points labeled as $1$ and many points labeled as ), and, therefore, $Q(2^{d})$ is large. Hence, there exists a $J$ s.t. $Q(J)$ is “big enough” (say at least $\frac{1}{4}\alpha m$) while $Q(J-1)$ is “small enough” (say at most $\frac{3}{4}\alpha m$). That is, a $J$ s.t. (1) there exists an interval of length $J$ containing lots of ones and lots of zeros; and (2), every interval of length $<J$ cannot contain too many ones and too many zeros simultaneously. Such a $J$ can easily be (privately) obtained using a (noisy) binary search. However, as there are $d$ noisy comparisons, this solution requires a sample of size $d^{O(1)}$ in order to achieve reasonable utility guarantees.

As a second attempt, one might consider preforming a binary search, not on $0\leq J\leq 2^{d}$, but rather on the power $j$ of an interval of length $2^{j}$. That is, preforming a search for a power $0\leq j\leq d$ for which there exists a $2$-good interval of length $2^{j}$. Here there are only $\log(d)$ noisy comparisons, and the sample size is reduced to $\log^{\Omega(1)}(d)$. Again, a (noisy) binary search on $0\leq j\leq d$ can (privately) yield an appropriate length $J=2^{j}$ s.t. $Q(2^{j})$ is “big enough”, while $Q(2^{j-1})$ is “small enough”. Such a $J=2^{j}$ is, indeed, a length of a $2$-good interval. Too see this, note that as $Q(2^{j})$ is “big enough”, there exists an interval of length $2^{j}$ containing lots of ones and lots of zeros. Moreover, as $Q(2^{j-1})$ is “small enough”, every interval of length $2^{j-1}=\frac{1}{2}2^{j}$ cannot contain too many ones and too many zeros simultaneously.

A binary search as above would have to operate on noisy values of $Q(\cdot)$ (as otherwise differential privacy cannot be obtained). For this reason, we set the bounds for “big enough” and “small enough” to overlap. Namely, we search for a value $j$ such that $Q(2^{j})\geq\frac{\alpha}{4}m$ and $Q(2^{j-1})\leq\frac{3\alpha}{4}m$, where $\alpha$ is our approximation parameter, and $m$ is the sample size.

To summarize, using a binary search we find a length $J=2^{j}$ such that there exists a 2-good interval of length $J$. Then, using $\mathcal{A}_{\rm dist}$, we find a 4-good interval. Finally, we partition this interval to 4 intervals, and using the exponential mechanism we choose a starting point or end point of one of these intervals as our the threshold.

We will apply recursion to reduce the costs of computing $J=2^{j}$ to $2^{O(\log^{*}(d))}$. The tool performing the recursion would be formalized and analyzed in the next section. This tool will later be used in our construction of a proper $(\epsilon,\delta)$-private learner for $\operatorname*{\tt THRESH}_{d}$.

3 Privately Approximating Quasi-Concave Promise Problems

We next define the notions that enable our recursive algorithm.

A Quasi-Concave Promise Problem consists of an ordered set of possible solutions $[0,T]=\{0,1,\ldots,T\}$, a database $S\in X^{m}$, a sensitivity-1 quality function $Q:X^{*}\times[0,T]\rightarrow\R$, an approximation parameter $\alpha$, and another parameter $r$ (called a quality promise).

If $Q(S,\cdot)$ is quasi-concave and if there exists a solution $p\in[0,T]$ for which $Q(S,p)\geq r$ then a good output for the problem is a solution $k\in[0,T]$ satisfying $Q(S,k)\geq(1-\alpha)r$. The outcome is not restricted otherwise.

Consider a sample $S=(x_{i},y_{i})_{i=1}^{m}$, labeled by some target function $c_{j}\in\operatorname*{\tt THRESH}_{d}$. The goal of choosing a hypothesis with small empirical error can be viewed as a quasi-concave promise problem as follows. Set the range of possible solutions to $[0,2^{d}]$, the approximation parameter to $\alpha$ and the quality promise to $m$. Define $Q(S,k)=|\{i:c_{k}(x_{i})=y_{i}\}|$; i.e., $Q(S,k)$ is the number of points in $S$ correctly classified by $c_{k}\in\operatorname*{\tt THRESH}_{d}$. Note that the target concept $c_{j}$ satisfies $Q(S,j)=m$. Our task is to find a hypothesis $h_{k}\in\operatorname*{\tt THRESH}_{d}$ s.t. ${\rm error}_{S}(h_{k})\leq\alpha$, which is equivalent to finding $k\in[0,2^{d}]$ s.t. $Q(S,k)\geq(1-\alpha)m$.

To see that $Q(S,\cdot)$ is quasi-concave, let $u\leq v\leq w$ be s.t. $Q(S,u),Q(S,w)\geq\lambda$. Consider $j$, the index of the target concept, and assume w.l.o.g. that $j\leq v$ (the other case is symmetric). That is, $j\leq\ v\leq w$. Note that $c_{v}$ errs only on points in between $j$ and $v$, and $c_{w}$ errs on all these points. That is, ${\rm error}_{S}(c_{v})\leq{\rm error}_{S}(c_{w})$, and, therefore, $Q(S,v)\geq\lambda$. See Figure 4 for an illustration.

Note that if the sample $S$ in the above example is not consistent with any $c\in\operatorname*{\tt THRESH}_{d}$, then there is no $j$ s.t. $Q(S,j)=m$, and the quality promise is void. Moreover, in such a case $Q(S,\cdot)$ might not be quasi-concave.