What Can We Learn Privately?

Introduction

The data privacy problem in modern databases is similar to that faced by statistical agencies and medical researchers: to learn and publish global analyses of a population while maintaining the confidentiality of the participants in a survey. There is a vast body of work on this problem in statistics and computer science. However, until recently, most schemes proposed in the literature lacked rigorous analysis of privacy and utility.

A recent line of work , initiated by Dinur and Nissim and called private data analysis, seeks to place data privacy on firmer theoretical foundations and has been successful at formulating a strong, yet attainable privacy definition. The notion of differential privacy that emerged from this line of work provides rigorous guarantees even in the presence of a malicious adversary with access to arbitrary auxiliary information. It requires that whether an individual supplies her actual or fake information has almost no effect on the outcome of the analysis.

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. In this work, we ask what can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example. Our goal is a broad understanding of the resources required for private learning in terms of samples, computation time, and interaction. We examine two basic notions from computational learning theory: Valiant’s probabilistically approximately correct (PAC) learning model and Kearns’ statistical query (SQ) model .

Informally, a concept is a function from examples to labels, and a class of concepts is learnable if for any distribution $\mathcal{D}$ on examples, one can, given limited access to examples sampled from $\mathcal{D}$ labeled according to some target concept $c$, find a small circuit (hypothesis) which predicts $c$’s labels with high probability over future examples taken from the same distribution. In the PAC model, a learning algorithm can access a polynomial number of labeled examples. In the SQ model, instead of accessing examples directly, the learner can specify some properties (i.e., predicates) on the examples, for which he is given an estimate, up to an additive polynomially small error, of the probability that a random example chosen from $\mathcal{D}$ satisfies the property. PAC learning is strictly stronger than the SQ learning .

We require a private algorithm to keep entire examples (not only the labels) confidential. In the scenario above, it translates to not revealing each participant’s gender, age, blood pressure history, and heart attack incidence. More precisely, the output of a private learner should not be significantly affected if a particular example $z_{i}$ is replaced with arbitrary $z^{\prime}_{i}$, for all $z_{i}$ and $z^{\prime}_{i}$. In contrast to correctness or utility, which is analyzed with respect to distribution $\mathcal{D}$, differential privacy is a worst-case notion. Hence, when we analyze the privacy of our learners we do not make any assumptions on the underlying distribution. Such assumptions are fragile and, in particular, would fall apart in the presence of auxiliary knowledge (also called background knowledge or side information) that the adversary might have: conditioned on the adversary’s auxiliary knowledge, the distribution over examples might look very different from $\mathcal{D}$.

1 Our Contributions

We introduce and formulate private learning problems, as discussed above, and develop novel algorithmic tools and bounds on the sample size required by private learning algorithms. Our results paint a picture of the classes of learning problems that are solvable subject to privacy constraints. Specifically, we provide:

A Private Version of Occam’s Razor. We present a generic private learning algorithm. For any concept class $\mathcal{C}$, we give a distribution-free differentially-private agnostic PAC learner for $\mathcal{C}$ that uses a number of samples proportional to $\log|\mathcal{C}|$. This is a private analogue of the “cardinality version” of Occam’s razor, a basic sample complexity bound from (non-private) learning theory. The sample complexity of our version is similar to that of the original, although the private algorithm is very different. As in Occam’s razor, the learning algorithm is not necessarily computationally efficient.

An Efficient Private Learner for Parity. We give a computationally efficient, distribution-free differentially private PAC learner for the class of parity functionsWhile the generic learning result (1) extends easily to “agnostic” learning (defined below), the learner for parity does not. The limitation is not surprising, since even non-private agnostic learning of parity is at least as hard as learning parity with random noise. over $\{0,1\}^{d}$. The sample and time complexity are comparable to that of the best non-private learner.

Equivalence of Local (“Randomized Response”) and SQ Learning. We precisely characterize the power of local, or randomized response, private learning algorithms. Local algorithms are a special (practical) class of private algorithms and are popular in the data mining and statistics literature . They add randomness to each individual’s data independently before processing the input. We show that a concept class is learnable by a local differentially private algorithm if and only if it is learnable in the statistical query (SQ) model. This equivalence relates notions that were conceived in very different contexts.

Separation of Interactive and Noninteractive Local Learning. Local algorithms can be noninteractive, that is, using one round of interaction with individuals holding the data, or interactive, that is, using more than one round (and in each receiving randomized responses from individuals). We construct a concept class, called masked-parity, that is efficiently learnable by interactive local algorithms under the uniform distribution on examples, but requires an exponential (in the dimension) number of samples to be learned by a noninteractive local algorithm. The equivalence (3) of local and SQ learning shows that interaction in local algorithms corresponds to adaptivity in SQ algorithms. The masked-parity class thus also separates adaptive and nonadaptive SQ learning.

The generic agnostic learner (1) has an important consequence: if some concept class $\mathcal{C}$ is learnable by any algorithm, not necessarily a private one, whose output length in bits is polynomially bounded, then $\mathcal{C}$ is learnable privately using a polynomial number of samples (possibly in exponential time). This result establishes the basic feasibility of private learning: it was not clear a priori how severely privacy affects sample complexity, even ignoring computation time.

There is an intuitively appealing similarity between learning from noisy examples and private learning: algorithms for both problems must be robust to small variations in the data. This apparent similarity is strengthened by a result of Blum, Dwork, McSherry and Nissim showing that any algorithm in Kearns’ statistical query (SQ) model can be implemented in a differentially private manner. SQ was introduced to capture a class of noise-resistant learning algorithms. These algorithms access their input only through a sequence of approximate averaging queries. One can privately approximate the average of a function with values in $$over the data set of$n$individuals to within additive error$O(1/n)$ (Dwork and Nissim ). Thus, one can simulate the behavior of an SQ algorithm privately, query by query.

Our efficient private learner for parity (2) dispels the similarity between learning with noise and private learning. First, SQ algorithms provably require exponentially many (in the dimension) queries to learn parity . More compellingly, learning parity with noise is thought to be computationally hard, and has been used as the basis of several cryptographic primitives (e.g., ).

Local algorithms (also referred to as randomized response, input perturbation, Post Randomization Method (PRAM), and Framework for High-Accuracy Strict-Privacy Preserving Mining (FRAPP)) have been studied extensively in the context of privacy-preserving data mining, both in statistics and computer science (e.g., ). Roughly, a local algorithm accesses each individual’s data via independent randomization operators. See Figure 1, p. 1.

Local algorithms were introduced to encourage truthfulness in surveys: respondents who know that their data will be randomized are more likely to answer honestly. For example, Warner famously considered a survey technique in which respondents are asked to give the correct answer to a sensitive (true/false) question with probability $2/3$ and the incorrect answer with probability $1/3$, in the hopes that the added uncertainty would encourage them to answer honestly. The proportion of “true” answers in the population is then estimated using a standard, non-private deconvolution. The accepted privacy requirement for local algorithms is equivalent to imposing differential privacy on each randomization operator . Local algorithms are popular because they are easy to understand and implement. In the extreme case, users can retain their data and apply the randomization operator themselves, using a physical device or a cryptographic protocol .

The equivalence between local and SQ algorithms (3) is a powerful tool that allows us to apply results from learning theory. In particular, since parity is not learnable with a small number of SQ queries but is PAC learnable privately (2), we get that local algorithms require exponentially more data for some learning tasks than do general private algorithms. Our results also imply that local algorithms are strictly less powerful than (non-private) algorithms for learning with classification noise because subexponential (non-private) algorithms can learn parity with noise .

Just as local algorithms can be interactive, SQ algorithms can be adaptive, that is, the averaging queries they make may depend on answers to previous queries. The equivalence of SQ and local algorithms (3) preserves interaction/adaptivity: a concept class is nonadaptively SQ learnable if and only if it is noninteractively locally learnable. The masked parity class (4) shows that interaction (resp., adaptivity) adds considerable power to local (resp., SQ) algorithms.

Most of the reasons that local algorithms are so attractive in practice, and have received such attention, apply only to noninteractive algorithms (interaction can be costly, complicated, or even impossible—for instance, when statistical information is collected by an interviewer, or at a polling booth).

This suggests that further investigating the power of nonadaptive SQ learners is an important problem. For example, the SQ algorithm for learning conjunctions is nonadaptive, but SQ formulations of the perceptron and $k$-means algorithms seem to rely heavily on adaptivity.

The SQ result of Blum et al. and our learner for parity (2) provide efficient (i.e., polynomial time) private learners for essentially all the concept classes known (by us) to have efficient non-private distribution-free learners. Finding a concept class that can be learned efficiently, but not privately and efficiently, remains an interesting and important question.

Our results also lead to questions of optimal sample complexity for learning problems of practical importance. The private simulation of SQ algorithms due to Blum et al. uses a factor of approximately $\sqrt{t}/\epsilon$ more data points than the naïve non-private implementation, where $t$ is the number of SQ queries and $\epsilon$ is the parameter of differential privacy (typically a small constant). In contrast, the generic agnostic learner (1) uses a factor of at most $1/\epsilon$ more samples than the corresponding non-private learner. For parity, our private learner uses a factor of roughly $1/\epsilon$ more samples than, and about the same computation time as, the non-private learner. What, then, is the additional cost of privacy when learning practical concept classes (half-planes, low-dimensional curves, etc)? Can the theoretical sample bounds of (1) be matched by (more) efficient learners?

1.2 Techniques

Our generic private learner (1) adapts the exponential sampling technique of McSherry and Talwar , developed in the context of auction design. Our use of the exponential mechanism inspired an elegant subsequent result of Blum, Liggett, and Roth (BLR) on simultaneously approximating many different functions.

The efficient private learner for parity (2) uses a very different technique, based on sampling, running a non-private learner, and occasionally refusing to answer based on delicately calibrated probabilities. Running a non-private learner on a random subset of examples is a very intuitive approach to building private algorithms, but it is not private in general. The private learner for parity illustrates both why this technique can leak private information and how it can sometimes be repaired based on special (in this case, algebraic) structure.

The interesting direction of the equivalence between SQ and local learners (3) is proved via a simulation of any local algorithm by a corresponding SQ algorithm. We found this simulation surprising since local protocols can, in general, have very complex structure (see, e.g., ). The SQ algorithm proceeds by a direct simulation of the output of the randomization operators. For a given input distribution $\mathcal{D}$ and any operator $R$, one can sample from the corresponding output distribution $R(\mathcal{D})$ via rejection sampling. We show that if $R$ is differentially private, the rejection probabilities can be approximated via low-accuracy SQ queries to $\mathcal{D}$.

Finally, the separation between adaptive and nonadaptive SQ (4) uses a Fourier analytic argument inspired by Kearns’ SQ lower bound for parity .

1.3 Classes of Private Learning Algorithms

We can summarize our results via a complexity-theoretic picture of learnable and privately learnable concept classes (more precisely, the members of the classes are pairs of concept classes and example distributions). In order to make asymptotic statements, we measure complexity in terms of the length $d$ of the binary description of examples.

We first consider learners that use a polynomial (in $d$) number of samples and output a hypothesis that is described using a polynomial number of bits, but have unlimited computation time. Let ${\text{\sf PAC}}^{*}$ denote the set of concept classes that are learnable by such algorithms ignoring privacy, and let ${\text{\sf PPAC}}^{*}$ denote the subset of ${\text{\sf PAC}}^{*}$ learnable by differentially privateDifferential privacy is quantified by a real parameter $\epsilon>0$. To make qualitative statements, we look at algorithms where $\epsilon\to 0$ as $d\to\infty$. Taking $\epsilon=1/d^{c}$ for any constant $c>0$ would yield the same class. algorithms.

Since we restrict the learner’s output to a polynomial number of bits, the hypothesis classes of the algorithms are de facto limited to have size at most $\exp(poly(d))$. Thus, the generic private learner (point (1) in the introduction) will use a polynomial number of samples, and ${\text{\sf PAC}}^{*}={\text{\sf PPAC}}^{*}$.

We can similarly interpret the other results above. Within ${\text{\sf PAC}}^{*}$, we can consider subsets of concepts learnable by SQ algorithms (${\text{\sf SQ}}^{*}$), nonadaptive SQ algorithms (${\text{\sf NASQ}}^{*}$), local interactive algorithms (${\text{\sf LI}}^{*}$) and local noninteractive algorithms (${\text{\sf LNI}}^{*}$). We obtain the following picture (see page 2):

The equality of ${\text{\sf LI}}^{*}$ and ${\text{\sf SQ}}^{*}$, and of ${\text{\sf LNI}}^{*}$ and ${\text{\sf NASQ}}^{*}$, follow from the SQ simulation of local algorithms (Theorem 5.14). The parity and masked-parity concept classes separate ${\text{\sf PPAC}}^{*}$ from ${\text{\sf SQ}}^{*}$ and ${\text{\sf SQ}}^{*}$ from ${\text{\sf NASQ}}^{*}$, respectively (Corollaries 5.15 and 5.17). (Note: The separation of ${\text{\sf PPAC}}^{*}$ from ${\text{\sf SQ}}^{*}$ holds even for distribution-free learning; in contrast, the separation of ${\text{\sf SQ}}^{*}$ from ${\text{\sf NASQ}}^{*}$ holds for learnability under a specific distribution on examples, since the adaptive SQ learner for MASKED-PARITY requires a uniform distribution on examples.)

When we take computational efficiency into account, the picture changes. The relation between local and SQ classes remain the same modulo a technical restriction on the randomization operators (Definition 5.13). SQ remains distinct from PPAC since parity is efficiently learnable privately. However, it is an open question whether concept classes which can be efficiently learned can also be efficiently learned privately.

2 Related Work

Prior to this work, the literature on differential privacy studied function approximation tasks (e.g. ), with the exception of the work of McSherry and Talwar on mechanism design . Nevertheless, several of these prior results have direct implications to machine learning-related problems. Blum et al. considered a particular class of learning algorithms (SQ), and showed that algorithms in the class could be simulated using noisy function evaluations. In an independent, unpublished work, Chaudhuri, Dwork, and Talwar considered a version of private learning in which privacy is afforded only to input labels, but not to examples. Other works considered specific machine learning problems such as mining frequent itemsets , $k$-means clustering , learning decision trees , and learning mixtures of Gaussians .

As mentioned above, a subsequent result of Blum, Ligett and Roth on approximating classes of low-VC-dimension functions was inspired by our generic agnostic learner. We discuss their result further in Section 3.1. Since the original version of our work, there have also been several results connecting differential privacy to more “statistical” notions of utility, such as consistency of point estimation and density estimation .

Our separation of interactive and noninteractive protocols in the local model (3) also has a precedent: Dwork et al. separated interactive and noninteractive private protocols in the centralized model, where the user accesses the data via a server that runs differentially private algorithms on the database and sends back the answers. That separation has a very different flavor from the one in this work: any example of a computation that cannot be performed noninteractively in the centralized model must rely on the fact that the computational task is not defined until after the first answer from the server is received. (Otherwise, the user can send an algorithm for that task to the server holding the data, thus obviating the need for interaction.) In contrast, we present a computational task that is hard for noninteractive local algorithms – learning masked parity – yet is defined in advance.

In the machine learning literature, several notions similar to differential privacy have been explored under the rubric of “algorithmic stability” . The most closely related notion is change-one error stability, which measures how much the generalization error changes when an input is changed (see the survey ). In contrast, differential privacy measures how the distribution over the entire output changes—a more complex measure of stability (in particular, differential privacy implies change-one error stability). A different notion, stability under resampling of the data from a given distribution , is connected to the sample-and-aggregate method of but is not directly relevant to the techniques considered here. Finally, in a different vein, Freund, Mansour and Schapire used a weighted averaging technique with the same weights as the sampler in our generic learner to reduce generalization error (see Section 3.1).

Preliminaries

A (randomized) algorithm (in our context, this will usually be a learning algorithm) is private if neighboring databases induce nearby distributions on its outcomes:

The probability is taken over the random coins of $\mathcal{A}$.

In , the notion above was called “indistinguishability”. The name “differential privacy” was suggested by Mike Schroeder, and first appeared in Dwork .

Differential privacy composes well (see, e.g., ):

One method for obtaining efficient differentially private algorithms for approximating real-valued functions is based on adding Laplacian noise to the true answer. Let $\mathop{\rm{Lap}}\nolimits(\lambda)$ denote the Laplace probability distribution with mean , standard deviation $\sqrt{2}\lambda$, and p.d.f. $f(x)=\frac{1}{2\lambda}e^{-|x|/\lambda}$.

2 Preliminaries from Learning Theory

Let $\mathcal{D}$ be a distribution over labeled examples in $X_{d}\times Y_{d}$. A learning algorithm is given access to $\mathcal{D}$ (the method for accessing $\mathcal{D}$ depends on the type of learning algorithm). It outputs a hypothesis $h:X_{d}\to Y_{d}$ from a hypothesis class $\mathcal{H}=\{\mathcal{H}_{d}\}_{d\in\N}$. The goal is to minimize the misclassification error of $h$ on $\mathcal{D}$, defined as

The success of a learning algorithm is quantified by parameters $\alpha$ and $\beta$, where $\alpha$ is the desired error and $\beta$ bounds the probability of failure to output a hypothesis with this error. Error measures other than misclassification are considered in supervised learning (e.g., $L_{2}^{2}$). We study only misclassification error here, since for binary labels it is equivalent to the other common error measures.

PAC learning algorithms are frequently designed assuming a promise that the examples are labeled consistently with some target concept $c$ from a class $\mathcal{C}$: namely, $c\in\mathcal{C}_{d}$ and $y=c(x)$ for all $(x,y)$ in the support of $\mathcal{D}$. In that case, we can think of $\mathcal{D}$ as a distribution only over examples $X_{d}$. To avoid ambiguity, we use $\mathcal{X}$ to denote a distribution over $X_{d}$. In the PAC setting, ${\text{\it err}}(h)=\Pr_{x\sim\mathcal{X}}[h(x)\neq c(x)].$

Class $\mathcal{C}$ is (inefficiently) PAC learnable if there exists some hypothesis class $\mathcal{H}$ and a PAC learner $\mathcal{A}$ such that $\mathcal{A}$ PAC learns $\mathcal{C}$ using $\mathcal{H}$. Class $\mathcal{C}$ is efficiently PAC learnable if $\mathcal{A}$ runs it time polynomial in $d,1/\alpha$, and $\log(1/\beta).$

Remark: Our definition deviates slightly from the standard one (see, e.g., ) in that we do not take into consideration the size of the concept $c$. This choice allows us to treat PAC learners and agnostic learners identically. One can change Definition 2.4 so that the number of samples depends polynomially also on the size of $c$ without affecting any of our results significantly.

Agnostic learning is an extension of PAC learning that removes assumptions about the target concept. Roughly speaking, the goal of an agnostic learner for a concept class $\mathcal{C}$ is to output a hypothesis $h\in\mathcal{H}$ whose error with respect to the distribution is close to the optimal possible by a function from $\mathcal{C}$. In the agnostic setting, ${\text{\it err}}(h)=\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq y]$.

(Efficiently) agnostically learnable is defined identically to (efficiently) PAC learnable with two exceptions: (i) the data are drawn from an arbitrary distribution $\mathcal{D}$ on $X_{d}\times Y_{d}$; (ii) instead of Equation 1, the output of $\mathcal{A}$ has to satisfy:

Definitions 2.4 and 2.5 capture distribution-free learning, in that they do not assume a particular form for the distributions $\mathcal{X}$ or $\mathcal{D}$. In Section 5.3, we also consider learning algorithms that assume a specific distribution $\mathcal{D}$ on examples (but make no assumption on which concept in $\mathcal{C}$ labels the examples). When we discuss such algorithms, we specify $\mathcal{D}$ explicitly; without qualification, “learning” refers to distribution-free learning.

The definitions above are sufficiently detailed to allow for exact complexity statements (e.g., “$\mathcal{A}$ learns $\mathcal{C}$ using $n(\alpha,\beta)$ examples and time $O(t)$”), and the upper and lower bounds in this paper are all stated in this language. However, we also focus on two broader measures to allow for qualitative statements: (a) polynomial sample complexity is the default notion in our definitions. With the novel restriction of privacy, it is not a priori clear which concept classes can be learned using few examples even if we ignore computation time. (b) We use the term efficient private learning to impose the additional restriction of polynomial computation time (which implies polynomial sample complexity).

Private PAC and Agnostic Learning

We define private PAC learners as algorithms that satisfy definitions of both differential privacy and PAC learning. We emphasize that these are qualitatively different requirements. Learning must succeed on average over a set of examples drawn i.i.d. from $\mathcal{D}$ (often under the additional promise that $\mathcal{D}$ is consistent with a concept from a target class). Differential privacy, in contrast, must hold in the worst case, with no assumptions on consistency.

$\sf[Privacy]$ For all $\epsilon>0$, algorithm $\mathcal{A(\epsilon,\cdot,\cdot,\cdot)}$ is $\epsilon$-differentially private (Definition 2.1);

$\sf[Utility]$ Algorithm $\mathcal{A}$ PAC learns $\mathcal{C}$ using $\mathcal{H}$ (Definition 2.4).

$\mathcal{C}$ is efficiently privately PAC learnable if $\mathcal{A}$ runs in time polynomial in $d,1/\epsilon,1/\alpha$, and $\log(1/\beta).$

(Efficient) private agnostic learning is defined analogously to (efficient) private PAC learning with Definition 2.5 replacing Definition 2.4 in the utility condition.

Evaluating the quality of a particular hypothesis is easy: one can privately compute the fraction of the data it classifies correctly (enabling cross-validation) using the sum query framework of . The difficulty of constructing private learners lies in finding a good hypothesis in what is typically an exponentially large space.

In this section, we present a private analogue of a basic consistent learning result, often called the cardinality version of Occam’s razorWe discuss the relationship to the “compression version” of Occam’s razor at the end of this section.. This classical result shows that a PAC learner can weed out all bad hypotheses given a number of labeled examples that is logarithmic in the size of the hypothesis class (see [42, p. 35]). Our generic private learner is based on the exponential mechanism of McSherry and Talwar .

Since the score ranges from $-n$ to 0, hypotheses with low empirical error are exponentially more likely to be selected than ones with high error.

The algorithm $\mathcal{A}^{\epsilon}_{q}$ is $\epsilon$-differentially private.

For all $d\in\N$, any concept class $\mathcal{C}_{d}$ whose cardinality is at most $\exp({\mathop{\rm{poly}}\nolimits(d)})$ is privately agnostically learnable using $\mathcal{H}_{d}=\mathcal{C}_{d}$. More precisely, the learner uses $n=O((\ln|\mathcal{H}_{d}|+\ln\frac{1}{\beta})\cdot\max\{\frac{1}{\epsilon\alpha},\frac{1}{\alpha^{2}}\})$ labeled examples from $\mathcal{D}$, where $\epsilon,\alpha$, and $\beta$ are parameters of the private learner. (The learner might not be efficient.)

Let $\mathcal{A}^{\epsilon}_{q}$ be as defined above. The privacy condition in Definition 3.1 is satisfied by Lemma 3.3.

By Chernoff-Hoeffding bounds (see Theorem A.2 in Appendix A),

for all hypotheses $h\in\mathcal{H}_{d}$. Hence,

Now set $\rho=\alpha/3$. If ${\text{\it err}}(h)\geq OPT+\alpha$ then $|{\text{\it err}}(h)-{\text{\it err}}_{T}(h)|\geq\alpha/3$ or ${\text{\it err}}_{T}(h)\geq OPT+2\alpha/3$. Thus $\Pr[E]\leq|\mathcal{H}_{d}|(2\exp(-2n\alpha^{2}/9)+\exp(-\epsilon n\alpha/6))\leq\beta$ where the last inequality holds for $n\geq 6\left((\ln|\mathcal{H}_{d}|+\ln\frac{1}{\beta})\cdot\max\{\frac{1}{\epsilon\alpha},\frac{1}{\alpha^{2}}\}\right)$. ∎

Remark: In the non-private agnostic case, the standard Occam’s razor bound guarantees that $O((\log|\mathcal{C}_{d}|+\log(1/\beta))/\alpha^{2})$ labeled examples suffice to agnostically learn a concept class $\mathcal{C}_{d}$. The bound of Theorem 3.4 differs by a factor of $O(\frac{\alpha}{\epsilon})$ if $\alpha>\epsilon$, and does not differ at all otherwise. For (non-agnostic) PAC learning, the dependence on $\alpha$ in the sample size for both the private and non-private versions improves to $1/\alpha$. In that case the upper bounds for private and non-private learners differ by a factor of $O(1/\epsilon)$. Finally, the theorem can be extended to settings where $\mathcal{H}_{d}\neq\mathcal{C}_{d}$, but in this case using the same sample complexity the learner outputs a hypothesis whose error is close to the best error attainable by a function in $\mathcal{H}_{d}$.

The private agnostic learner has the following important consequence: If some concept class $\mathcal{C}_{d}$ is learnable by any algorithm $\mathcal{A}$, not necessarily a private one, and $\mathcal{A}$’s output length in bits is polynomially bounded, then there is a (possibly exponential time) private algorithm that learns $\mathcal{C}_{d}$ using a polynomial number of samples. Since $\mathcal{A}$’s output is polynomially long, $\mathcal{A}$’s hypothesis class $\mathcal{H}_{d}$ must have size at most $2^{\mathop{\rm{poly}}\nolimits(d)}$. Since $\mathcal{A}$ learns $\mathcal{C}_{d}$ using $\mathcal{H}_{d}$, class $\mathcal{H}_{d}$ must contain a good hypothesis. Thus, our private learner will learn $\mathcal{C}_{d}$ using $\mathcal{H}_{d}$ with sample complexity linear in $\log|\mathcal{H}_{d}|$.

It is most natural to state our result as an analogue of the cardinality version of Occam’s razor, which bounds generalization error in terms of the size of the hypothesis class. However, our result can be extended to the compression version, which captures the general relationship between compression and learning (we borrow the “cardinality version” terminology from ). This latter version states that any algorithm which “compresses” the data set, in the sense that it finds a consistent hypothesis which has a short description relative to the number of samples seen so far, is a good learner (see and [42, p. 34]).

Compression by itself does not imply privacy, because the compression algorithm’s output might encode a few examples in the clear (for example, the hyperplane output by a support vector machine is defined via a small number of actual data points). However, Theorem 3.4 can be extended to provide a private analogue of the compression version of Occam’s razor. If there exists an algorithm that compresses, in the sense above, then there also exists a private PAC learner which does not have fixed sample complexity, but uses an expected number of samples similar to that of the compression algorithm. The private learner proceeds in rounds: at each round it requests twice as many examples as in the previous round, and uses a restricted hypothesis class consisting of sufficiently concise hypotheses from the original class $\mathcal{H}$. We omit the straightforward details.

2 Private Learning with VC dimension Sample Bounds

In the non-private case one can also bound the sample size of a PAC learner in terms of the Vapnik-Chervonenkis (VC) dimension of the concept class.

A set $S\subseteq X_{d}$ is shattered by a concept class $\mathcal{C}_{d}$ if $\mathcal{C}_{d}$ restricted to $S$ contains all $2^{|S|}$ possible functions from $S$ to $\{0,1\}$. The VC dimension of $\mathcal{C}_{d}$, denoted $VCDIM(\mathcal{C}_{d})$, is the cardinality of a largest set $S$ shattered by $\mathcal{C}_{d}$.

We can extend Theorem 3.4 to classes with finite VC dimension, but the resulting sample complexity also depends logarithmically on the size of the domain from which examples are drawn. Recent results of Beimel et al. show that for “proper” learning, the dependency is in fact necessary; that is, the VC dimension alone is not sufficient to bound the sample complexity of proper private learning. It is unclear if the dependency is necessary in general.

Every concept class $\mathcal{C}_{d}$ is privately agnostically learnable using hypothesis class $\mathcal{H}_{d}=\mathcal{C}_{d}$ with $n=O((VCDIM(\mathcal{C}_{d})\cdot\ln|X_{d}|+\ln\frac{1}{\beta})\cdot\max\{\frac{1}{\epsilon\alpha},\frac{1}{\alpha^{2}}\})$ labeled examples from $\mathcal{D}$. Here, $\epsilon,\alpha$, and $\beta$ are parameters of the private agnostic learner, and $VCDIM(\mathcal{C}_{d})$ is the VC dimension of $\mathcal{C}_{d}$. (The learner is not necessarily efficient.)

Sauer’s lemma (see, e.g., ) implies that there are $O(|X_{d}|^{VCDIM(\mathcal{C}_{d})})$ different labelings of $X_{d}$ by functions in $\mathcal{C}_{d}$. We can thus run the generic learner of the previous section with a hypothesis class of size $|\mathcal{H}_{d}|=O(|X_{d}|^{VCDIM(\mathcal{C}_{d})})$. The statement follows directly. ∎

Our original proof of the corollary used a result of Blum, Ligget and Roth (which was inspired, in turn, by our generic learning algorithm) on generating synthetic data. The simpler proof above was pointed out to us by an anonymous reviewer.

In their full generality, the generic learning results of the previous sections (Theorems 3.4 and 3.6) produce well-defined randomized maps, but not necessarily “algorithms” in the sense of “functions uniformly computable by Turing machines”. This is because the concept class and example domain may themselves not be computable (nor even recognizable) uniformly (imagine, for example, a concept class indexed by elements of the halting problem). It is commonly assumed in the learning literature that elements of the concept class and domain can be computed/recognized by a Turing machine and some bound on the length of their binary representations is known. In this case, the generic learners can be implemented by randomized Turing machines with finite expected running time.

An Efficient Private Learner for PARITY

Let PARITY be the class of parity functions $c_{r}:\{0,1\}^{d}\rightarrow\{0,1\}$ indexed by $r\in\{0,1\}^{d}$, where $c_{r}(x)=r\odot x$ denotes the inner product modulo $2$. In this section, we present an efficient private PAC learning algorithm for PARITY. The main result is stated in Theorem 4.4.

The proof of $\mathcal{A}$’s utility follows by considering all the possible situations in which the algorithm fails to satisfy the error bound, and by bounding the probabilities with which these situations occur.

By standard arguments in learning theory , $\displaystyle|S|\geq\frac{1}{\alpha}\left(d\ln 2+\ln\frac{1}{\beta}\right)$ labeled examples are sufficient for learning PARITY with error $\alpha$ and failure probability $\beta$. Since $\mathcal{A}$ adds each element of $[n]$ to $S$ independently with probability $p=\epsilon/4$, the expected size of $S$ is $pn=\epsilon n/4$. By the Chernoff bound (Theorem A.1), $|S|\geq\epsilon n/8$ with probability at least $1-e^{-\epsilon n/16}$. We set $\beta=\frac{1}{4}$ and pick $n$ such that $\epsilon n/8\geq\frac{1}{\alpha}\left(d\ln 2+\ln 4\right)$.

Algorithm $\mathcal{A}$ is $\epsilon$-differentially private.

As mentioned above, the key observation in the following proof is that including of any single point in the sample set $S$ increases the probability of a hypothesis being output by at most 2.

This claim is proved below. For now, we can plug it into Eqn. (4) to get

The first inequality holds since $p=\epsilon/4$ and $\epsilon\leq 1/2$. This establishes Eqn. (2). The proof of Eqn. (3) is similar:

In the last line, the first inequality follows from the fact that on any input, $\mathcal{A}$ outputs $\perp$ with probability at least $1/2$. This completes the proof of the lemma. ∎

The last inequality holds because in 2 (the finite field with 2 elements where arithmetic is performed modulo 2), adding a consistent linear constraint either reduces the space of solutions by a factor of 2 (if the constraint is linearly independent from $V_{T}$) or does not change the solutions space (if it is linearly dependent on the previous constraints). The constraint indexed by $i$ has to be consistent with constraints indexed by $T$, since both probabilities are not . ∎

It remains to amplify the success probability of $\mathcal{A}$. To do so, we construct a private version of the standard (non-private) algorithm for amplifying a learner’s success probability. The standard amplification algorithm generates a set of hypotheses by invoking $\mathcal{A}$ multiple times on independent examples, and then outputs a hypothesis from the set with the least training error as evaluated on a fresh test set (see for details). Our private amplification algorithm differs from the standard algorithm only in the last step: it adds Laplacian noise to the training error to obtain a private version of the error, and then uses the perturbed training error instead of the true training error to select the best hypothesis from the set. Alternatively, we could use the generic learner from Theorem 3.4 to select among the candidate hypotheses; the resulting algorithm has the same asymptotic behavior as the algorithm we discuss here. We chose the algorithm that we felt was simplest. Recall that $\mathop{\rm{Lap}}\nolimits(\lambda)$ denotes the Laplace probability distribution with mean , standard deviation $\sqrt{2}\lambda$, and p.d.f. $f(x)=\frac{1}{2\lambda}e^{-|x|/\lambda}$.

Algorithm $\mathcal{A}^{*}$ efficiently and privately PAC learns PARITY (according to Definition 3.1) with $O\left(\frac{d\log(1/\beta)}{\epsilon\alpha}\right)$ samples.

The theorem follows from Lemmas 4.5 and 4.6 that, respectively, prove privacy and utility of $\mathcal{A}^{*}$.

Algorithm $\mathcal{A}^{*}$ is $\epsilon$-differentially private.

We prove that even if $\mathcal{A}^{*}$ released all hypotheses $h_{j}$, computed in Step 5, together with the corresponding perturbed error estimates ${\widehat{\text{\it err}}_{T}}(h_{j})$, it would still be $\epsilon$-differentially private. Since the output of $\mathcal{A}^{*}$ can be computed solely from this information, Claim 2.2 implies that $\mathcal{A}^{*}$ is $\epsilon$-differentially private.

$\mathcal{A}^{*}(\cdot,\epsilon,\cdot,\cdot)$ PAC learns PARITY with sample complexity $n=O(\frac{d\log(1/\beta)}{\epsilon\alpha})$.

Consider the set of candidate hypotheses $\{h_{1},...,h_{k}\}$ output by the invocations of $\mathcal{A}$ inside of $\mathcal{A}^{*}$. We call a hypothesis $h$ good if ${\text{\it err}}({h})\leq\frac{\alpha}{5}=\alpha^{\prime}$. We call a hypothesis ${h}$ bad if ${\text{\it err}}({h})\geq\alpha=5\alpha^{\prime}$. Note that good and bad refer to a hypothesis’ true error rate on the underlying distribution.

With probability at least $1-\beta^{\prime}$, one of the invocations of $\mathcal{A}$ outputs a good hypothesis.

Conditioned on any particular outcome $\{h_{1},...,h_{k}\}$ of the invocations of $\mathcal{A}$, with probability at least $1-\beta^{\prime}$, both:

Every good hypothesis $h_{j}$ in $\{h_{1},...,h_{k}\}$ has training error ${\text{\it err}_{T}}(h_{j})\leq 2\alpha^{\prime}$.

Every bad hypothesis $h_{j}$ in $\{h_{1},...,h_{k}\}$ has training error ${\text{\it err}_{T}}(h_{j})\geq 4\alpha^{\prime}$.

Conditioned on any particular hypotheses $\{h_{1},...,h_{k}\}$ and training errors ${\text{\it err}_{T}}(h_{1}),...,{\text{\it err}_{T}}(h_{k})$, with probability at least $1-\beta^{\prime}$, for all $j$ simultaneously, $|{\widehat{\text{\it err}}_{T}}(h_{j})-{\text{\it err}_{T}}(h_{j})|<\alpha^{\prime}$.

Suppose the events described in the three claims above all occur. Then some good hypothesis has perturbed training error less than $3\alpha^{\prime}$, yet all bad hypotheses have perturbed training error greater than $3\alpha^{\prime}$. Thus, the hypothesis $h_{j^{*}}$ with minimal perturbed error ${\widehat{\text{\it err}}_{T}}(h_{j^{*}})$ is not bad, that is, has true error at most $\alpha$. By the claims above, the probability that all three events occur is at least $1-3\beta^{\prime}=1-\beta$, and so the lemma holds. We now prove the claims.

Second, fix a particular sequence of candidate hypotheses $h_{1},...,h_{k}$. For each $j$, the training error ${\text{\it err}_{T}}(h_{j})$ is the average of $s$ Bernouilli trials, each with success probability ${\text{\it err}}(h_{j})$. (Crucially, the training set $\hat{z}$ is independent of the data $\bar{z}$ used to find the candidate hypotheses). To bound the training error, we apply the multiplicative Chernoff bound (Theorem A.1) with $n=s$ and $p={\text{\it err}}(h_{j})$. Here, $p\leq\alpha^{\prime}$ if $h_{j}$ is good, and $p\geq 5\alpha^{\prime}$ if $h_{j}$ is bad.

By the multiplicative Chernoff bound (Theorem A.1) if $s\geq\frac{c_{1}}{\alpha^{\prime}}\ln\frac{k}{\beta^{\prime}}$ (for appropriate constant $c_{1}$), then

By a union bound, all the training errors are (simultaneously) approximately correct, with probability at least $1-k\cdot\frac{\beta^{\prime}}{k}=1-\beta^{\prime}$.

Finally, we prove the third claim. Consider a particular candidate hypothesis $h_{j}$. If $s\geq\frac{c_{2}k}{\alpha^{\prime}\epsilon}\ln\frac{k}{\beta^{\prime}}$ (for appropriate constant $c_{2}$), then (by using the c.d.f.The cumulative distribution function of the Laplacian distribution $\mathop{\rm{Lap}}\nolimits(\lambda)$ is $F(x)=\frac{1}{2}\exp\left(\frac{x}{\lambda}\right)$ if $x<0$ and $1-\frac{1}{2}\exp\left(-\frac{x}{\lambda}\right)$ if $x\geq 0$. of the Laplacian distribution)

By a union bound, all $k$ perturbed estimates are within $\alpha^{\prime}$ of their correct value with probability at least $1-k\cdot\frac{\beta^{\prime}}{k}=1-\beta^{\prime}$. This probability is taken over the choice of Laplacian noise, and so the bound holds independently of the particular hypotheses or their training error estimates. ∎

Remark: In the non-private case $O((d+\ln(1/\beta))/\alpha)$ labels are sufficient for learning PARITY. Theorem 4.4 shows that the upper bounds on the sample size of private and non-private learners differ only by a factor of $O(\ln(1/\beta)/\epsilon)$.

Local Protocols and SQ learning

In this section, we relate private learning in the local model to the SQ model of Kearns . We first define the two models precisely. We then prove their equivalence (Section 5.1), and discuss the implications for learning (Section 5.2). Finally, we define the concept class MASKED-PARITY and prove that it separates interactive from noninteractive local learning (Section 5.3).

An $\epsilon$-local randomizer $R:D\rightarrow W$ is an $\epsilon$-differentially private algorithm that takes a database of size $n=1$. That is, $\Pr[R(u)=w]\leq e^{\epsilon}\Pr[R(u^{\prime})=w]$ for all $u,u^{\prime}\in D$ and all $w\in W$. The probability is taken over the coins of $R$ (but not over the choice of the input).

Note that since a local randomizer works on a data set of size $1$, $u$ and $u^{\prime}$ are neighbors for all $u,u^{\prime}\in D$. Thus, this definition is consistent with our previous definition of differential privacy.

By Claim 2.2, $\epsilon$-local algorithms are $\epsilon$-differentially private.

In the statistical query (SQ) model, algorithms access statistical properties of a distribution rather than individual examples.

Let $\mathcal{D}$ be a distribution over a domain $D$. An SQ oracle $SQ_{\mathcal{D}}$ takes as input a function $g:D\rightarrow\{+1,-1\}$ and a tolerance parameter $\tau\in(0,1)$; it outputs $v$ such that:

An SQ algorithm accesses the distribution $\mathcal{D}$ via the SQ oracle $SQ_{\mathcal{D}}$. SQ algorithms that prepare all their queries to $SQ_{\mathcal{D}}$ before receiving any answers are called nonadaptive; otherwise, they are called adaptive.

Note that we do not restrict $g()$ to be efficiently computable. We will distinguish later those algorithms that only make queries to efficiently computable functions $g()$.

1 Equivalence of Local and SQ Models

Blum et al. used the fact that sum queries can be answered privately with little noise to show that any efficient SQ algorithm can be simulated privately and efficiently. We show that it can be simulated efficiently even by a local algorithm, albeit with slightly worse parameters.

Furthermore, the simulation is noninteractive if the original SQ algorithm $\mathcal{A}_{\text{SQ}}$ is nonadaptive. The simulation is efficient if $\mathcal{A}_{\text{SQ}}$ is efficient.

1.2 Simulation of Local Algorithms by SQ Algorithms

The idea behind the simulation is to sample from a distribution $\widetilde{p}(\cdot)$ that is within small statistical distance of $p(\cdot)$. We start by applying $R$ to an arbitrary input (say, 0) in the domain $D$ and obtaining a sample $w\sim R(\textbf{0})$. Let $q(w)=\Pr[R(\textbf{0})=w]$ (where the probability is taken only over randomness in $R$). Since $R$ is $\epsilon$-differentially private, $q(w)$ approximates $p(w)$ within a multiplicative factor of $e^{\epsilon}$. To sample $w$ from $p(\cdot)$ we use the following rejection sampling algorithm: (i) sample $w$ according to $q(\cdot)$; (ii) with probability $\frac{p(w)}{q(w)e^{\epsilon}}$, output $w$; (iii) with the remaining probability, repeat from (i).

To carry out this strategy, we must be able to estimate $p(w)$, which depends on the (unknown) distribution $\mathcal{D}$, using only SQ queries. The rough idea is to express $p(w)$ as the expectation, taken over $z\sim\mathcal{D}$, of the function $h(z)=\Pr[R(z)=w]$ (where the probability is taken only over the coins of $R$). We can use $h$ as the basis of an SQ query. In fact, to get a sufficiently accurate approximation, we must rescale the function $h$ somewhat, and keep careful track of the error introduced by the SQ oracle. We present the details in the proof of the following lemma:

We split the simulation over Claims 5.9 and 5.10. In the first claim we simulate noninteractive local algorithms using nonadaptive SQ algorithms. In the second claim we simulate interactive local algorithms using adaptive SQ algorithms.

We show how to simulate an $\epsilon$-local randomizer $R$ using statistical queries to $SQ_{\mathcal{D}}$. Because the local algorithm is non-interactive, we can assume without loss of generality that it accesses each entry $z_{i}$ only once. (Otherwise, one can combine different operators, used to access $z_{i}$, by combining their answers into a vector). Given $R:D\rightarrow W$, we want to sample $w\in W$ with probability:

We construct an algorithm $\mathcal{B}_{R,\epsilon}$ that given $t$, $\beta$, and access to the SQ oracle, outputs $w\in W$, such that the statistical difference between the output probability distributions of $\mathcal{B}_{R,\epsilon}$ and the simulated randomizer $R$ is at most $\beta/t$. Because the local algorithm makes $t$ queries, the overall statistical distance between the output distribution of the local algorithm and the distribution resulting from the simulation is at most $\beta$, as desired.

An SQ algorithm $\mathcal{B}_{R,\epsilon}(t,\beta,SQ_{\mathcal{D}})$ that simulates an $\epsilon$-local randomizer $R:D\rightarrow W$. 1. Sample $w\sim R(\textbf{0})$. Let $q(w)=\Pr[R(\textbf{0})=w]$. 2. Define $g:D\to$ by $g(z_{i})=\dfrac{\Pr[R(z_{i})=w]-q(w)}{q(w)(e^{\epsilon}-e^{-\epsilon})}$, and let $\tau=\frac{\beta}{3e^{2\epsilon}t}$. 3. Query the SQ oracle $v=SQ_{\mathcal{D}}(g,\tau)$, and let $\widetilde{p}(w)=vq(w)(e^{\epsilon}-e^{-\epsilon})+q(w)$. 4. With probability $\frac{\widetilde{p}(w)}{q(w)(1+\frac{\beta}{3t})e^{\epsilon}}$, output $w$. With the remaining probability, repeat from Step 1.

We now show that the statistical distance between the output of $\mathcal{B}_{R,\epsilon}(t,\beta,SQ_{\mathcal{D}})$ and the distribution $p(\cdot)$ is at most $\beta/t$. As mentioned above, our initial approximation $\widetilde{p}(\cdot)$ of $p(\cdot)$ in Step 1 is obtained by applying $R$ to some arbitrary input (namely, 0) in the domain $D$ and sampling $w\sim R(\textbf{0})$. Since $R$ is $\epsilon$-differentially private, $q(w)=\Pr[R(\textbf{0})=w]$ approximates $p(w)$ within a multiplicative factor of $e^{\epsilon}$.

However, to carry out the rejection sampling strategy, we need to get a much better estimate of $p(w)$. Steps 2 and 3 compute such an estimate, $\widetilde{p}(w)$, satisfying (with probability 1)

We establish the inclusion (5) below. For now, assume it holds on every iteration. Step 4 is a rejection sampling step which ensures that the output will follow a distribution close to $\widetilde{p}(\cdot)$. Inclusion (5) guarantees that $\frac{\widetilde{p}(w)}{q(w)(1+\frac{\beta}{3t})e^{\epsilon}}$ is at most 1, so the probability in Step 4 is well defined. The difficulty is that the quantity $\widetilde{p}(w)$ is not a well-defined function of $w$: it depends on the SQ oracle and may vary, for the same $w$, from iteration to iteration.

Nevertheless, $\widetilde{p}$ is fixed for any given iteration of the algorithm. In the given iteration, any particular element $w$ gets output with probability $q(w)\times\frac{\widetilde{p}(w)}{q(w)(1+\phi)e^{\epsilon}}=\frac{\widetilde{p}(w)}{(1+\phi)e^{\epsilon}}$. The probability that the given iteration terminates (i.e., outputs some $w$) is then $p_{terminate}=\sum_{w}\frac{\widetilde{p}(w)}{(1+\phi)e^{\epsilon}}$. By (5), this probability is in $\frac{1\pm\phi}{(1+\phi)e^{\epsilon}}$. Thus, conditioned on the iteration terminating, element $w$ is output with probability $\frac{\widetilde{p}(w)}{(1+\phi)\cdot e^{\epsilon}\cdot p_{teminate}}\in\frac{1\pm\phi}{1\pm\phi}\cdot p(w)$. Since $\phi\leq 1/3$, we can simplify this to get

This implies that no matter which iteration produces output, the statistical difference between the distribution of $w$ and $p(\cdot)$ will be at most $3\phi=\frac{\beta}{t}$, as desired.

Moreover, since each iteration terminates with probability at least $\frac{1-\phi}{1+\phi}\cdot e^{-\epsilon}$, the expected number of iterations is at most $\frac{1+\phi}{1-\phi}\cdot e^{\epsilon}\leq 2e^{\epsilon}$. Thus, the total expected SQ query complexity of the simulation is $O(t\cdot e^{\epsilon})$.

Plugging in the bounds for $v$ and $q(w)$ we get that $\widetilde{p}(w)\in(1\pm\tau^{\prime})p(w)$ where $\tau^{\prime}=e^{2\epsilon}\tau=\frac{\beta}{3t}$. This establishes (5) and concludes the proof. ∎

As in the previous claim, we show how to simulate the output of the local randomizers during the run of the local algorithm. A difference, however, is that because an entry $z_{i}$ may be accessed multiple times, we have to condition our sampling on the outcomes of previous (simulated) applications of local randomizers to $z_{i}$.

More concretely, let $R_{1},R_{2},...$ be the sequence of randomizers that access the entry $z_{i}$. To simulate $R_{k}(z_{i})$, we must take into account the answers $a_{1},\ldots,a_{k-1}$ given by the simulations of $R_{1}(z_{i}),\ldots,R_{k-1}(z_{i})$. We show how to do this using adaptive statistical queries to $SQ_{\mathcal{D}}$. The notation is the same as in Claim 5.9. We want to output $w\in W$ with probability

where $R_{j}$ ($1\leq j\leq k-1$) denotes the $j$th randomizer applied to $z_{i}$.

As before, we start by sampling $w\sim R(\textbf{0})$. Let $q(w)=\Pr[R_{k}(\textbf{0})=w]$. Note that $q(w)$ approximates $p(w)$ within a multiplicative factor of $e^{\epsilon}$ because $R_{1},\ldots,R_{k}$ are respectively $\epsilon_{1}$-,$\ldots,\epsilon_{k}$-differentially private, and $\epsilon_{1}+\ldots+\epsilon_{k}\leq\epsilon$. Hence, we can use the rejection sampling algorithm as in Claim 5.9. Rewrite $p(w)$:

Conditioned on a particular value of $z_{i}$, the probabilities in the last expression depend only the coins of the randomizers. The outputs of the randomizers are independent conditioned on $z_{i}$, and therefore we can simplify the expression above:

Let $p_{1}$ and $p_{2}$ denote the numerator and denominator, respectively, in the right hand side of the equation above. Let $r_{1}(z_{i})$ and $r_{2}(z_{i})$ denote the values inside the expectations that define $p_{1}$ and $p_{2}$, respectively. Namely,

Let $t$ be the number of queries made by $\mathcal{A}$. Setting $\tau^{\prime}\leq\frac{\beta}{3t}$ guarantees that the statistical difference between distributions $p$ and $\widetilde{p}$ is at most $\frac{\beta}{t}$, and hence the statistical difference between $\mathcal{B}$’s and $\mathcal{A}$’s output distributions is at most $\beta$. As in Claim 5.9, the expected number of SQ queries for rejection sampling is $O(t\cdot e^{\epsilon})$. ∎

Note that the efficiency of the constructions in Lemma 5.8 depends on the efficiency of computing the functions submitted to the SQ oracle, e.g., the efficiency of computing the probability $\Pr[R(z_{i})=w]$. We discuss this issue in the next section.

2 Implications for Local Learning

In this section, we define learning in the local and SQ models. The equivalence of the two models follows from the simulations described in the previous sections. An immediate but important corollary is that local learners are strictly less powerful than general private learners.

In order to state the equivalence between SQ and local learning, we require the following efficiency condition for a local randomizer.

Let $R:D\rightarrow W$ be an $\epsilon$-local randomizer. The randomizer is transparent if both: (i) for all inputs $u\in D$, the time needed to evaluate $R$; and (ii) for all inputs $u\in D$ and outputs $w\in W$ the time taken to compute the probability $\Pr[R(u)=w]$, are polynomially bounded in the size of the input and $1/\epsilon$.

As stated, this definition requires exact computation of probabilities. This may not make sense on a finite-precision machine, since for many natural randomizers the transition probabilities are irrational. One can relax the requirement to insist that relevant probabilities are computable with additive error at most $\phi$ in time polynomial in $\log(\frac{1}{\phi})$.

All local protocols that have appeared in the literature are transparent, at least in this relaxed sense.

In the equivalences of the previous sections, transparency of local randomizers corresponds directly to efficient computability of the function $g$ in an SQ query. To see why, consider first the simulation of SQ algorithms by local algorithms: if the original SQ algorithm is efficient (that is, query $g$ can be evaluated in polynomial time) then the local randomizer $R(u)=g(u)+\eta$ can also be evaluated in polynomial time for all $u\in D$. Furthermore, it is simple to estimate for all inputs $u\in D$ and outputs $w\in W$ the probability $\Pr[R(u)=w]$ since $R(u)$ is a Laplacian random variable with known parameters. Second, in the SQ simulation of a local algorithm, the functions $g(z_{i})=\frac{\Pr[R(z_{i})=w]-q(w)}{q(w)(e^{\epsilon}-e^{-\epsilon})}$ that are constructed can be evaluated efficiently precisely when the local randomizers are transparent.

We can now state the main result of this section, which follows from Lemmas 5.6 and 5.8, along with the correspondence between transparent randomizers and efficient SQ queries.

Furthermore, the simulations guarantee the following additional properties: (i) an efficient SQ learner is simulatable by an efficient local learner that uses only transparent randomizers; (ii) an efficient local learner that uses only transparent randomizers is simulatable by an efficient SQ learner; (iii) a nonadaptive SQ (resp. noninteractive local) learner is simulatable by a noninteractive local (resp. nonadaptive SQ) learner.

Now we can use lower bounds for SQ learners for PARITY (see, e.g., ) to demonstrate limitations of local learners. The lower bound of rules out SQ learners for PARITY that use at most $2^{d/3}$ queries of tolerance at least $2^{-d/3}$, even (a) allowing for unlimited computing time, (b) under the restriction that examples be drawn from the uniform distribution and (c) allowing a small probability of error (see Footnote 6). Since PARITY is (efficiently) privately learnable (Theorem 4.4), and since local learning is equivalent to SQ learning, we obtain:

Concept classes learnable by local learners are a strict subset of concept classes PAC learnable privately. This holds both with and without computational restrictions.

3 The Power of Interaction in Local Protocols

To complete the picture of locally learnable concept classes, we consider how interaction changes the power of local learners (and, equivalently, how adaptivity changes SQ learning). As mentioned in the introduction, interaction is very costly in typical applications of local algorithms. We show that this cost is sometimes necessary, by giving a concept class that an interactive algorithm can learn efficiently with a polynomial number of examples drawn from the uniform distribution, but for which any noninteractive algorithm requires an exponential number of examples under the same distribution.

Let MASKED-PARITY be the class of functions $c_{r,a}:\{0,1\}^{d}\times\{0,1\}^{\log d}\times\{0,1\}\rightarrow\{+1,-1\}$ indexed by $r\in\{0,1\}^{d}$ and $a\in\{0,1\}$:

where $r\odot x$ denotes the inner product of $r$ and $x$ modulo $2$, and $r_{i}$ is the $i$th bit of $r$. This concept class divides the domain into two parts (according to the last bit, $b$). When $b=0$, the concept $c_{r,a}$ behaves either like the PARITY concept indexed by $r$, or like its negation, according to the bit $a$ (the “mask”). When $b=1$, the concept essentially ignores the input example and outputs some bit of the parity vector $r$.

Below, we consider the learnability of $\text{\sf MASKED-PARITY}=\{c_{r,a}\}$ when the examples are drawn from the uniform distribution over the domain $\{0,1\}^{d+\log d+1}$. In Section 5.3.1, we give a adaptive SQ learner for MASKED-PARITY under the uniform distribution. The adaptive learner uses two rounds of communication with the SQ oracle: the first, to learn $r$ from the $b=1$ half of the input, and the second, to retrieve the bit $a$ from the $b=0$ half of the input via queries that depend on $r$.

In Section 5.3.2, we show that no nonadaptive SQ learner which uses $2^{o(d)}$ examples can consistently produce a hypothesis that labels significantly more than $3/4$ of the domain correctly. The intuition is that as the queries are prepared nonadaptively, any information about $r$ gained from the $b=1$ half of the inputs cannot be used to prepare queries to the $b=0$ half. Since information about $a$ is contained only in the $b=0$ half, in order to extract $a$, the SQ algorithm is forced to learn PARITY, which it cannot do with few examples. Our separation in the SQ model directly translates to a separation in the local model (using Theorem 5.14).

The following theorem summarizes our results.

There exists an efficient adaptive SQ learner for MASKED-PARITY over the uniform distribution.

No nonadaptive SQ learner can learn MASKED-PARITY (with a polynomial number of queries) even under the uniform distribution on examples. Specifically, there is an SQ oracle $\cal O$ such that any nonadaptive SQ learner that makes $t$ queries to $\mathcal{O}$ over the uniform distribution, all with tolerance at least $2^{-d/3}$, satisfies the following: if the concept $c_{\bar{r},\bar{a}}$ is drawn uniformly at random from the set of MASKED-PARITY concepts, then, with probability at least $\frac{1}{2}-\frac{t}{2^{d/3+2}}$ over $c_{\bar{r},\bar{a}}$, the output hypothesis $h$ of the learner has ${\text{\it err}}(c_{\bar{r},\bar{a}},h)\geq\frac{1}{4}$.

The concept classes learnable by nonadaptive SQ learners (resp. noninteractive local learners) under the uniform distribution are a strict subset of the concept classes learnable by adaptive SQ learners (resp. interactive local learners) under the uniform distribution. This holds both with and without computational restrictions.

The learning theory literature distinguishes between strong learning, in which the learning algorithm is required to produce hypotheses with arbitrarily low error (as in Definition 2.4, where the parameter $\alpha$ can be arbitrarily small), and weak learning, in which the learner is only required to produce a hypothesis with error bounded below $1/2$ by a polynomially small margin. The separation proved in this section (Theorem 5.16) applies only to strong learning: although no nonadaptive SQ learner can produce a hypothesis with error much better than $1/4$, it is simple to design a nonadaptive weak SQ learner for MASKED-PARITY under the uniform distribution with error exactly 1/4.

In fact, it is impossible to obtain an analogue of our separation for weak learning. The characterization of SQ learnable classes in terms of “SQ dimension” by Blum et al. implies that adaptive and nonadaptive SQ algorithms are equivalent for weak learning. This is not explicit in , but follows from the fact that the weak learner constructed for classes with low SQ dimension is non-adaptive. (Roughly, the learner works by checking if the concept at hand is approximately equal to one of a polynomial number of alternatives; these alternatives depend on the input distribution and the concept class, but not on the particular concept at hand.)

The results of this section concern the learnability of MASKED-PARITY under the uniform distribution. The class MASKED-PARITY does not separate adaptive from nonadaptive distribution-free learners, since MASKED-PARITY cannot be learned by any SQ learner under the distribution which is uniform over examples with $b=0$ (in that case, learning MASKED-PARITY is equivalent to learning PARITY under the uniform distribution). Separating adaptive from nonadaptive distribution-free SQ learning remains an open problem.

3.1 An Adaptive Strong SQ Learner for MASKED-PARITY over the Uniform Distribution

Our adaptive learner for MASKED-PARITY uses two rounds of communication with the SQ oracle: first, to learn $r$ from the $b=1$ half of the input, and second, to retrieve the bit $a$ from the $b=0$ half of the input via queries that depend on $r$. Theorem 5.16, part (1), follows from the proposition below.

Adaptive SQ Learner $\mathcal{A}_{\sf MP}$ for MASKED-PARITY over the Uniform Distribution 1. For $j=1,\dots,d$ (in parallel) (a) Define $g_{j}:D\to\{0,1\}$ by $g_{j}(x,i,b,y)=(i=j)\;\wedge\;(b=1)\;\wedge\;(y=-1)\,,$ where $x\in\{0,1\}^{d}$, $i\in\{0,1\}^{\log d}$, $b\in\{0,1\}$, and $y=c_{r,a}(x,i,b)\in\{+1,-1\}$. (b) $answer_{j}\leftarrow SQ_{\mathcal{D}}(g_{j},\tau),$ where $\tau=\frac{1}{4d+1}$, and $\hat{r}_{j}\leftarrow\begin{cases}1&\text{if }answer_{j}>\frac{1}{4d};\\ 0&\text{otherwise.}\end{cases}$ 2. (a) $\hat{r}\leftarrow\hat{r_{1}}\dots\hat{r_{d}}\in\{0,1\}^{d}$ (b) Define $g_{d+1}:D\to\{0,1\}$ by $g_{d+1}(x,i,b,y)=(b=0)\;\wedge\;(y\not=(-1)^{\hat{r}\odot x})\,.$ where $x\in\{0,1\}^{d}$, $i\in\{0,1\}^{\log d}$, $b\in\{0,1\}$, and $y=c_{r,a}(x,i,b)\in\{+1,-1\}$. (c) $answer_{d+1}\leftarrow SQ_{\mathcal{D}}(g_{d+1},\frac{1}{5}).$, and $\hat{a}\leftarrow\begin{cases}1&\text{if }answer_{d+1}>\frac{1}{4};\\ 0&\text{otherwise.}\end{cases}$ (d) Output $c_{\hat{r},\hat{a}}.$

The algorithm $\mathcal{A}_{\sf MP}$ efficiently learns MASKED-PARITY (with probability 1) in 2 rounds using $d+1$ SQ queries computed over the uniform distribution with minimum tolerance $\frac{1}{4d+1}$.

Consider the $d$ queries in the first round. If $r_{j}=1$, then

Note that the functions $g_{1},\ldots,g_{d+1}$ are all computable in time $O(d)$, and the computations performed by $\mathcal{A}_{\sf MP}$ can be done in time $O(d)$, so the SQ learner is efficient. ∎

3.2 Impossibility of non-adaptive SQ learning for MASKED-PARITY

The impossibility result (Theorem 5.16, part (2)) for nonadaptive learners uses ideas from statistical query lower bounds (see, e.g., ).

Recall that the distribution $\mathcal{D}$ is uniform over $D=\{0,1\}^{d+\log(d)+1}$. For functions $f,h:\{0,1\}^{d+\log d+1}\rightarrow\{+1,-1\}$, recall that ${\text{\it err}}(f,h)=\Pr_{x\sim\mathcal{D}}[f(x)\not=h(x)]$. Define the inner product of $f$ and $h$ as:

The quantity $\langle f,h\rangle=\Pr_{x\sim\mathcal{D}}[f(x)=h(x)]-\Pr_{x\sim\mathcal{D}}[f(x)\not=h(x)]=1-2\cdot{\text{\it err}}(f,h)$ measures the correlation between $f$ and $h$ when $x$ is drawn from the uniform distribution $\mathcal{D}$.

Let the target function $c_{\bar{r},\bar{a}}$ be chosen uniformly at random from the set $\{c_{r,a}\}$. Consider a nonadaptive SQ algorithm that makes $t$ queries $g_{1},\dots,g_{t}$. The queries $g_{1},\ldots,g_{t}$ must be independent of $\bar{r}$ and $\bar{a}$ since the learner is nonadaptive. The only information about $\bar{a}$ is in the outputs associated with the $b=0$ half of the inputs (recall that $c_{\bar{r},\bar{a}}(x,i,b)=(-1)^{r_{i}}$ when $b=1$).

The main technical part of the proof follows the lower bound on SQ learning of PARITY. Using Fourier analysis, we split the true answer to a query into three components: a component that depends on the query $g$ but not the pair $(\bar{r},\bar{a})$, a component that depends on $g$ and $\bar{r}$ (but not $\bar{a}$), and a component that depends on $g,\bar{r}$, and $\bar{a}$ (see Equation (11) below). We show that for most target concepts $c_{\bar{r},\bar{a}}$ the last component can be ignored by the SQ oracle. That is, a very close approximation to the correct output to the SQ queries made by the learner can be computed solely based on $g$ and $\bar{r}$. Consequently, for most target concepts $c_{\bar{r},\bar{a}}$, the SQ oracle can return answers that are independent of $\bar{a}$, and hence $\bar{a}$ cannot be learned.

Consider a statistical query $g:\{0,1\}^{d}\times\{0,1\}^{\log d}\times\{0,1\}\times\{+1,-1\}\rightarrow\{+1,-1\}$. For some $(x,i,b)\in D$, the value of $g(x,i,b,\cdot)$ depends on the label (i.e., $(g(x,i,b,+1)\not=g(x,i,b,-1))$) and otherwise $g(x,i,b,\cdot)$ is insensitive to the label (i.e., $(g(x,i,b,+1)=g(x,i,b,-1))$). Every statistical query $g(\cdot,\cdot,\cdot,\cdot)$ can be decomposed into a label-independent and label-dependent part. This fact was first implicitly noted by Blum et al. and made explicit by Bshouty and Feldman (Lemma 30). We adapt the proof presented in for our purpose.

We can rewrite the expectation of $g$ on any concept $c_{\bar{r},\bar{a}}$ in terms of these quantities:

Note that $C_{g}$ depends on the statistical query $g$, but not on the target function. We now wish to analyze the second term, $\langle f_{g},c_{\bar{r},\bar{a}}\rangle$, more precisely. To this end, we define the following functions parameterized by $s\in\{0,1\}$:

Recall that $\langle f_{g},c_{\bar{r},\bar{a}}\rangle$ is a sum over tuples $(x,i,b)$. We can separate the sum into two pieces: one with tuples where $b=0$ and the other with tuples where $b=1$. Using the functions $c_{\bar{r},\bar{a}}^{s},f_{g}^{s}$ just defined, we can write $\langle f_{g},c_{\bar{r},\bar{a}}\rangle=\langle f_{g}^{0},c_{\bar{r},\bar{a}}^{0}\rangle+\langle f_{g}^{1},c_{\bar{r},\bar{a}}^{1}\rangle$. Hence,

The inner product $\langle f_{g}^{1},c_{\bar{r},\bar{a}}^{1}\rangle$ depends on the statistical query $g$ and on $\bar{r}$, but not on $\bar{a}$. Thus only the middle term on the righthand side of (11) depends on $\bar{a}$.

Consider an SQ oracle $\mathcal{O}={\mathcal{O}}_{c_{\bar{r},\bar{a}},\mathcal{D}}$ that responds to every query $(g,\tau)$ as follows (recall that $\mathcal{D}$ is the uniform distribution):

If the condition $|\langle f_{g}^{0},c_{\bar{r},\bar{a}}^{0}\rangle|<\tau$ is met for all the queries $(g,\tau)$ made by the learner, then the SQ oracle $\mathcal{O}$ never replies with a quantity that depends on $\bar{a}$. We now show that this is typically the case.