Privately Releasing Conjunctions and the Statistical Query Barrier

Introduction

Consider a data set $D\subseteq\{0,1\}^{d}$ in which each element corresponds to an individual’s record over $d$ binary attributes. The goal of privacy-preserving data analysis is to enable rich statistical analyses on the data set while respecting individual privacy. In paritcular, we would like to guarantee differential privacy [DMNS06], a rigorous notion of privacy that guarantees the outcome of a statistical analysis is nearly indistinguishable on any two data sets that differ only in a single individual’s data.

One of the most important classes of statistical queries on the data set are Boolean conjunctions, sometimes called contingency tables or marginal queries. See, for example, [BCD+07, BLR08, KRSU10, UV10]. A boolean conjunction corresponding to a subset $S\subseteq[d]$ counts what fraction of the individuals have each attribute in $S$ set to $1.$ A major open problem in privacy-preserving data analysis is to efficiently create a differentially private synopsis of the data set that accurately encodes answers to all Boolean conjunctions. In this work we give an algorithm with runtime polynomial in $d$, which outputs a differentially private data structure that represents all boolean conjunctions up to an average error of 1%.

Our result is significantly more general and applies to any collection of queries that can be described by a low sensitivity submodular function. Submodularity is a property that often arises in data analysis and machine learning problems [KG07], including problems for which privacy is a first-order design constraintFor example, Kempe, Kleinberg, and Tardos show that for two common models of influence propagation on social networks, the function capturing the “influence” of a set of users (perhaps the targets of a viral marketing campaign) is a monotone submodular function [KKT03].. Imagine, for example, a social network on $d$ vertices. A data analyst may wish to analyze the size of the cuts induced by various subsets of the vertices. Here, our result provides a data structure that represents all cuts up to a small average error. Another important example of submodularity is the set-coverage function, which given a set system over elements in some universe $U$, represents the number of elements that are covered by the union of any collection of the sets.

The size of our data structure grows exponentially in the inverse error desired, and hence we can represent submodular functions only up to constant error if we want polynomial query complexity. Can any efficient algorithm do even better? We give evidence that in order to do better, fundamentally new techniques are needed. Specifically, we show that no polynomial-time algorithm that guarantees small error for every boolean conjunction can do substantially better if the algorithm permits an implementation that only accesses the database through statistical queries. This statement holds regardless of whether such an implementation is privacy-preserving. (A statistical query is given by a function $q\colon\{0,1\}^{d}\to\{0,1\}$, to which the answer is $\operatorname*{\varmathbb{E}}_{x\in D}[q(x)]$.)

We show this limitation using connection between the data release problem and standard problems in learning theory. Putting aside privacy concerns, we pose the following question: How many statistical queries to a data set are necessary and sufficent in order to approximately answer all queries in a class $C$? We show that the number of statistical queries necessary and sufficient for this task is, up to a factor of $O(d)$, equal to the agnostic learning complexity of $C$ (over arbitrary distributions) in Kearns’ statistical query (SQ) model [Kea98]. Using an SQ lower bound for agnostically learning monotone conjunctions shown by Feldman [Fel10], this connection implies that no polynomial-time algorithm operating in the SQ-model can release even monotone conjunctions to subconstant error. Since monotone conjunction queries can be described by a submodular function, the lower bound applies to releasing submodular functions as well.

While the characterization above is independent of privacy concerns, it has two immediate implications for private data release:

Firstly, it also characterizes what can be released in the local privacy model of Kasiviswanathan et al. [KLN+08]; this follows from the fact that [KLN+08] showed that SQ algorithms are precisely what can be computed in the local privacy model.

Secondly, and perhaps even more importantly, it gives us the claimed unconditional lower bounds on the running time of any query-release algorithm that permits an implementation using only statistical queries—regardless of whether its privacy analysis can be carried out in the local privacy model. To our knowledge, this class includes almost all privacy preserving algorithms developed to date, including the recently introduced Median Mechanism [RR10] and Multiplicative Weights Mechanism [HR10]A notable exception is the private parity-learning algorithm of [KLN+08], which explicitly escapes the statistical query model.. Note that these mechanisms cannot be implemented in the local privacy model while preserving their privacy guarantees, because they will have to make too many queries. Indeed, they are capable of releasing conjunctions to subconstant error! Yet, they can be implemented using only statistical queries, and so our lower bounds apply to their running time.

To summarize, our results imply that if we want to develop efficient algorithms to solve the query release problem for classes as expressive as monotone conjunctions (itself an extremely simple class!), we need to develop techniques that are able to sidestep this statistical query barrier. On a conceptual level, our results present new reductions from problems in differential privacy to problems in learning theory.

In this section we give an informal statement of our theorems with pointers to the relevant sections. Our theorem on approximating submodular functions is proved in Section 3. The definition of submodularity is found in the Preliminaries (Section 2).

Let $\alpha>0,\beta>0.$ Let $f\colon\{0,1\}^{d}\to$ be a submodular function. Then, there is an algorithm with runtime $d^{O(\log(1/\beta)/\alpha^{2})}$ which produces an approximation $h\colon\{0,1\}^{d}\to$ such that $\operatorname*{\varmathbb{P}r}_{x\in\{0,1\}^{d}}\{|f(x)-h(x)|\leq\alpha\}\geq 1-\beta.$

In Section 4 we then show how this algorithm gives the following differentially private release mechanism for Boolean conjunctions. The definition of differential privacy is given in Section 2.

Let $\alpha>0,\beta>0.$ There is an $\varepsilon$-differentially private algorithm with runtime $d^{O(\log(1/\beta)/\alpha^{2})}$ which releases the set of Boolean conjunctions with error at most $\alpha$ on a $1-\beta$ fraction of the queries provided that $|D|\geq d^{O(\log(1/\beta)/\alpha^{2})}/\varepsilon\,.$

The guarantee in our theorem can be refined to give an $\alpha$-approximation to a $1-\beta$ fraction of the set of $w$-way conjunctions (conjunctions of width $w$) for all $w\in\{1,...,d\}.$ Nevertheless, our algorithm has the property that the error may be larger than $\alpha$ on a small fraction of the queries. We note, however, that for $\beta\leq\alpha^{p}/2$ our guarantee is stronger than error $\alpha$ in the $L_{p}$-norm which is also a natural objective that has been considered in other works. For example, Hardt and Talwar study error bounds on mechanisms with respect to the Euclidean norm across all answers [HT10]. From a practical point of view, it also turns out that some privacy-preserving algorithms in the literature indeed only require the ability to answer random conjunction queries privately, e.g., [JPW09].

Finally, in Section 5, we study the general query release problem and relate it to the agnostic learning complexity in the Statistical Query model.

Suppose there exists an algorithm that learns a class $C$ up to error $\alpha$ under arbitrary distributions using at most $q$ statistical queries. Then, there is a release mechanism for $C$ that makes at most $O(qd/\alpha^{2})$ statistical queries.

Moreover, any release mechanism for $C$ that makes at most $q$ statistical queries implies an agnostic learner that makes at most $2q$ queries.

While both reductions preserve the query complexity of the problem neither reduction preserves runtime. We also note that our equivalence characterization is more general than what we stated: the same proof shows that agnostic learning of a class $C$ is (up to small factors) information theoretically equivalent to releasing the answers to all queries in a class $C$ for any class of algorithms that may access the database only in some restricted manner. The ability to make only SQ queries is one restriction, and the requirement to be differentially private is another. Thus, we also show that on a class by class basis, the privacy cost of releasing the answers to a class of queries using any technique is not much larger than the privacy cost of simply optimizing over the same class to find the query with the highest value, and vice versa.

Our release algorithm is based on a structural theorem about general submodular functions $f:2^{U}\rightarrow$ that may be of independent interest. Informally, we show that any submodular function has a “small” “approximate” representation. Specifically, we show that for any $\alpha>0$, there exist at most $|U|^{2/\alpha}$ submodular functions $g_{i}$ such that each $g_{i}$ satisfies a strong Lipschitz condition, and for each $S\subset U$, there exists an $i$ such that $f(S)=g_{i}(S)$. We then take advantage of Vondrak’s observation in [Von10] that Lipschitz submodular functions are self-bounding, which allows us to apply recent dimension-free concentration bounds for self-bounding functions [BLM00, BLM09]. These concentration results imply that if we associate each function $g_{i}$ with its expectation, and respond to queries $f(S)$ with $\operatorname*{\varmathbb{E}}[g_{i}(S)]$ for the appropriate $g_{i}$, then most queries are answered to within only $\alpha$ additive error. This yields an algorithm for learning submodular functions over product distributions, which can easily be made privacy preserving when the values $f(S)$ correspond to queries on a sensitive database.

Our characterization of the query complexity of the release problem in the SQ model uses the multiplicative weights method [LW94, AHK05] similar to how it was used recently in [HR10]. That is we maintain a distribution over the universe on which the queries are defined. What is new is the observation that an agnostic learning algorithm for a class $C$ can be used to find a query from $C$ that distinguishes between the true data set and our distribution as much as possible. Such a query can then be used in the multiplicative weights update to reduce the relative entropy between the true data set and our distribution significantly. Since the relative entropy is nonnegative there can only be a few such steps before we find a distribution which provides a good approximation to the true data set on all queries in the class $C.$

2 Related Work

The problem of learning submodular functions was recently introduced by Balcan and Harvey [BH10]; their PAC-style definition was different from previously studied point-wise learning approaches [GHIM09, SF08]. For product distributions, Balcan and Harvey give an algorithm for learning monotone, Lipschitz continuous submodular functions up to constant multiplicative error using only random examples. [BH10] also give strong lower bounds and matching algorithmic results for non-product distributions. Our main algorithmic result is similar in spirit, and is inspired by their concentration-of-measure approach. Our model is different from theirs, which makes our results incomparable. We introduce a decomposition that allows us to learn arbitrary (i.e. potentially non-Lipschitz, non-monotone) submodular functions to constant additive error. Moreover, our decomposition makes value queries to the submodular function, which are prohibited in the model studied by [BH10].

Information Theoretic Characterizations in Privacy.

Kasiviswanathan et al. [KLN+08] introduced the centralized and local models of privacy and gave information theoretic characterizations for which classes of functions could be learned in these models: they showed that information theoretically, the class of functions that can be learned in the centralized model of privacy is equivalent to the class of functions that can be agnostically PAC learned, and the class of functions that can be learned in the local privacy model is equivalent to the class of functions that can be learned in the SQ model of Kearns [Kea98].

Blum, Ligett, and Roth [BLR08] considered the query release problem (the task of releasing the approximate value of all functions in some class) and characterized exactly which classes of functions can be information theoretically released while preserving differential privacy in the centralized model of data privacy. They also posed the question: which classes of functions can be released using mechanisms that have running time only polylogarithmic in the size of the data universe and the class of interest? In particular, they asked if conjunctions were such a class.

In this paper, we give an exact information theoretic characterization of which classes of functions can be released in the SQ model, and hence in the local privacy model: we show that it is exactly the class of functions that can be agnostically learned in the SQ model. We note that the agnostic SQ learnability of a class $C$ (and hence, by our result, the SQ releasability of $C$) can also be characterized by combinatorial properties of $C$, as done by Blum et al. [BFJ+94] and recently Feldman [Fel10].

Lower bounds and hardness results.

There are also several conditional lower bounds on the running time of private mechanisms for solving the query release problem. Dwork et al. [DNR+09] showed that under cryptographic assumptions, there exists a class of queries that can be privately released using the inefficient mechanism of [BLR08], but cannot be privately released by any mechanism that runs in time polynomial in the dimension of the data universe (e.g. $d$, when the data universe is $\{0,1\}^{d}$). Ullman and Vadhan [UV10] extended this result to the class of conjunctions: they showed that under cryptographic assumptions, no polynomial time mechanism that outputs a data set can answer even the set of $d^{2}$ conjunctions of two-literals!

The latter lower bound applies only to the class of mechanisms that output data sets, rather than some other data structure encoding their answers, and only to mechanisms that answer all conjunctions of two-literals with small error. In fact, because there are only $d^{2}$ conjunctions of size 2 in total, the hardness result of [UV10] does not hold if the mechanism is allowed to output some other data structure – such a mechanism can simply privately query each of the $d^{2}$ questions.

We circumvent the hardness result of [UV10] by outputting a data structure rather than a synthetic data set, and by releasing all conjunctions with small average error. Although there are no known computational lower bounds for releasing conjunctions with small average error, even for algorithms that output a data set, since our algorithm does not output a data set, our approach may be useful in circumventing the lower bounds of [UV10].

We also prove a new unconditional (information theoretic) lower bound on algorithms for privately releasing monotone conjunctions that applies to the class of algorithms that interact with the data using only SQ queries: no such polynomial time algorithm can release monotone conjunctions with $o(1)$ average error. We note that our lower bound does not depend on the output representation of the algorithm. Because almost all known private algorithms can indeed be implemented using statistical queries, this provides a new perspective on sources of hardness for private query release. We note that information theoretic lower bounds on the query complexity imply lower bounds on the running time of such differentially private algorithms.

There are also many lower bounds on the error that must be introduced by any private mechanism, independent of its running time. In particular, Kasiviswanathan et. al. [KRSU10] showed that average error of $\Omega(1/\sqrt{n})$ is necessary for private mechanisms that answer all conjunction queries of constant size. Recently, this work was extended by De [De11] to apply to mechanisms that are allowed to have arbitrarily large error on a constant fraction of conjunction queries of constant size. These results extend earlier results by Dinur and Nissim [DN03] showing that average error $\Omega(1/\sqrt{n})$ is necessary for random queries.

Interactive private query release mechanisms.

Recently, Roth and Roughgarden [RR10] and Hardt and Rothblum [HR10] gave interactive private query release mechanisms that allow a data analyst to ask a large number of questions, while only expending their privacy budgets slowly. Their privacy analyses depend on the fact that only a small fraction of the queries asked necessitate updating the internal state of the algorithm. However, to answer large classes of queries, these algorithms need to make a large number of statistical queries to the database, even though only a small number of statistical queries result in update steps! Intuitively, our characterization of the query complexity of the release problem in the SQ model is based on two observations: first, that it would be possible to implement these interactive mechanisms using only a small number of statistical queries if the data analyst was able to ask only those queries that would result in update steps, and second, that finding queries that induce large update steps is exactly the problem of agnostic learning.

Preliminaries

We study the question of answering counting queries over a database while preserving differential privacy. Given an arbitrary domain $X$, we consider databases $D\in X^{n}$. We write $n=|D|$. Two databases $D=(x_{1},\dots,x_{n})$ and $D^{\prime}=(x^{\prime}_{1},\dots,x^{\prime}_{n})$ are called adjacent if they differ only in one entry. That is, there exists $i\in[n]$ such that for every $j\neq i$, $x_{j}=x^{\prime}_{j}$. We are interested in algorithms (or mechanisms) that map databases to some abstract range $\mathcal{R}$ while satisfying $\varepsilon$-differential privacy:

A mechanism $\mathcal{M}:X^{*}\rightarrow\mathcal{R}$ satisfies $\varepsilon$-differential privacy if for all $S\subset\mathcal{R}$ and every pair of two adjacent databases $D,D^{\prime},$ we have $\operatorname*{\varmathbb{P}r}(\mathcal{M}(D)\in S)\leq e^{\varepsilon}\operatorname*{\varmathbb{P}r}(\mathcal{M}(D^{\prime})\in S)\,.$

A counting query is specified by a predicate $q\colon X\rightarrow$. We will denote the answer to a counting query (with some abuse of notation) by $q(D)=\frac{1}{n}\sum_{x\in D}q(X)\,.$ Note that a count query can differ by at most $1/n$ on any two adjacent databases. In particular, adding Laplacian noise of magnitude $1/\varepsilon n,$ denoted $\mathit{Lap}(1/\varepsilon n),$ guarantees $\varepsilon$-differential privacy on a single count query (see [DMNS06] for details).

The statistical query model and its connection to differential privacy.

We will state our algorithms in Kearns’ statistical query (SQ) model. In this model an algorithm $A^{\cal O}$ can access a distribution $D$ over a universe $X$ only through statistical queries to an oracle ${\cal O}.$ That is, the algorithm may ask any query $q\colon X\to$ and the oracle may respond with any answer $a$ satisfying $|a-\operatorname*{\varmathbb{E}}_{x\sim D}q(x)|\leq\tau\,.$ Here, $\tau$ is a parameter called the tolerance of the query.

In the context of differential privacy, the distribution $D$ will typically be the uniform distribution over a data set of size $n.$ A statistical query is then just the same as a counting query as defined earlier. Since SQ algorithms are tolerant to noise it is not difficult to turn them into differentially private algorithms using a suitable oracle. This observation is not new, and has been used previously, for example by Blum et al. [BDMN05] and Kasiviswanathan et al. [KLN+08].

Let $A$ denote an algorithm that requires $k$ queries of tolerance $\tau.$ Let ${\cal O}$ denote the oracle that outputs $\operatorname*{\varmathbb{E}}_{x\sim D}q(x)+\mathit{Lap}(k/n\varepsilon).$ Then, the algorithm $A^{\cal O}$ satisfies $\varepsilon$-differential privacy and with probability at least $1-\beta,$ the oracle answers all $q$ queries with error at most $\tau$ provided that $n\geq\frac{k(\log k+\log(1/\beta))}{\varepsilon\tau}\,.$

The first claim follows directly from the properties of the Laplacian mechanism and the composition property of $\varepsilon$-differential privacy. To argue the second claim note that $\operatorname*{\varmathbb{P}r}(|\mathit{Lap}(\sigma)|\geq\tau)\leq\exp(-\tau/\sigma)\,.$ Using that $\sigma=k/n\varepsilon$ and the assumption on $n$, we get that this probability is less than $\beta/k.$ The claim now follows by taking a union bound over all $k$ queries. ∎

Query release.

A concept class (or query class) is a set of predicates from $X\to$.

Let $C$ be a concept class. We say that an algorithm $A$ $(\alpha,\beta)$-releases $C$ over a data set $D$ if $\operatorname*{\varmathbb{P}r}_{q\sim C}\{|q(D)-A(q)|\leq\alpha\}\geq 1-\beta\,.$

Specifically, we are interested in algorithms which release $C$ using few statistical queries to the underlying data set. We will study the query release problem by considering the function $f(q)=q(D)$. In this setting, releasing a concept class $C$ is equivalent to approximating the function $q$ is the following sense

We say that an algorithm $A$ $(\alpha,\beta)$-approximates a function $f\colon 2^{U}\to$ over a distribution ${\cal D}$ if $\operatorname*{\varmathbb{P}r}_{S\sim{\cal D}}\{|f(S)-A(S)|\leq\alpha\}\geq 1-\beta\,.$

For many concept classes of interest, the function $f(q)=q(D)$ will be submodular, defined next.

Submodularity.

Given a universe $U$, a function $f:2^{U}\rightarrow\varmathbb{R}$ is called submodular if for all $S,T\subset U$ it holds that $f(S\cup T)+f(S\cap T)\leq f(S)+f(T)\,.$ We define the marginal value of $x$ (or discrete derivative) at $S$ as $\partial_{x}f(S)=f(S\cup\{x\})-f(S).$

A function $f$ is submodular if and only if $\partial_{x}f(S)\geq\partial_{x}f(T)$ for all $S\subseteq T\subseteq U$ and all $x\in U.$

A function $f:2^{U}\to\varmathbb{R}$ is $\gamma$-Lipschitz if for every $S\subseteq U$ and $x\in U$, $|\partial_{x}f(S)|\leq\gamma$.

Concentration bounds for submodular functions.

The next lemma was shown by Vondrak [Von10] building on concentration bounds for so-called self-bounding functions due to [BLM00, BLM09].

Let $f\colon 2^{U}\rightarrow\varmathbb{R}$ be a $1$-Lipschitz submodular function. Then for any product distribution ${\cal D}$ over $2^{U},$ we have

where the expectations are taken over $S\sim{\cal D}$.

Let $f\colon 2^{U}\rightarrow$ be a $\gamma$-Lipschitz submodular function. Then for any product distribution ${\cal D}$ over $2^{U},$ we have

where the expectations are taken over $S\sim{\cal D}$.

Approximating Submodular Functions

Our algorithm for approximating submodular functions is based on a structural theorem, together with some strong concentration inequalities for submodular functions (see Lemma 2.1). The structure theorem essentially says that we can decompose any bounded submodular function into a small collection of Lipschitz submodular functions, one for each region of the domain. In this section, we prove our structure theorem, present our algorithm, and prove its correctness.

We begin with a simpler version of the structure theorem. This version will be sufficient for approximating bounded monotone submodular functions from value queries, and will be the main building block in our stronger results, which will allow us to approximate arbitrary bounded submodular functions, even from “tolerant” value queries.

Our structure theorem follows from an algorithm that decomposes a given submodular function into Lipschitz submodular functions. The algorithm is presented next and analyzed in Lemma 3.1.

Given any submodular function $f\colon 2^{U}\to$ and $\gamma>0,$ Algorithm 1 makes the following guarantee. There are maps $F,T\colon 2^{U}\to 2^{U}$ such that:

(Lipschitz) For every $g^{B}\in{\cal G}$, $g^{B}$ is submodular and satisfies $\sup_{x\in V(B),S\subseteq V(B)}\partial_{x}g^{B}(S)\leq\gamma$.

(Completeness) For every $S\subseteq U$, $F(S)\subseteq S\subseteq V(F(S))$ and $g^{F(S)}(S)=f(S).$

(Uniqueness) For every $S\subseteq U$ and every $B\in{\cal I}$, we have $F(S)=B$ if and only if $B\subseteq S\subseteq V(B)$ and $S\cap T(B)=\emptyset$.

(Size) The size of ${\cal G}$ is at most $|{\cal G}|=|U|^{O(1/\gamma)}$. Moreover, given oracle access to $f,$ we compute $F,V,T$ in time $|U|^{O(1/\gamma)}$.

Note that the lemma applies to non-monotone submodular functions $f$ as well; however, since our release algorithm will require the stronger condition $\sup_{x\in V(B),S\subseteq V(B)}|\partial_{x}g(S)|\leq\gamma$, the lemma will only be sufficient for releasing monotone submodular functions (where it holds that $|\partial_{x}g(S)|\leq\gamma\iff\partial_{x}g(S)\leq\gamma$). We will return to the non-monotone case later.

Algorithm 1 always terminates and we have the following bound on the size of $\mathcal{I}.$

Let $B\in\mathcal{I}$ be a set, $B=\{x_{1},\dots,x_{|B|}\}$. Let $B_{0}=\emptyset$ and $B_{i}=\{x_{1},\dots,x_{i}\}$ for $i=1,\dots,|B|-1$. Then

Therefore, it must be that $|B|\leq 1/\gamma$, and there are at most $|U|^{1/\gamma}$ such sets over $|U|$ elements. ∎

For every $g^{B}\in{\cal G}$, $g^{B}$ is submodular and $\sup_{x\in V(B),S\subseteq V(B)}\partial_{x}g^{B}(S)\leq\gamma$.

Submodularity follows from the fact that $g^{B}$ is a “shifted” version of $f$. Specifically, if $T\subseteq S$, then $\partial_{x}g^{B}(S)=\partial_{x}f(B\cup S)\leq\partial_{x}f(B\cup T)=\partial_{x}g^{B}(T)$, where the inequality is by submodularity of $f$.

To establish the Lipschitz property, we note that by the definition of $V$, $\partial_{x}f(B)\leq\gamma$ for every $x\in V(B)$. Also, by the submodularity of $f$, we have $\partial_{x}g^{B}(S)=\partial_{x}f(B\cup S)\leq\partial_{x}f(B)\leq\gamma$. ∎

Now we turn to constructing the promised mappings $F$ and $T$ in order to Properties 2 and 3. Roughly, we want $F(S)$ to choose a maximal set in ${\cal I}$ such that $F(S)\subseteq S$, in order to assure that $S\subseteq V(F(S))$. This task is complicated by the fact that there could be many such sets. We want to be able to choose a unique such set, and moreover, given any such set $B$, determine efficiently if $F(S)=B$. To achieve the former task, we define a specific, deterministic mapping $F(S)$ and to achieve the latter we will carefully define the mapping $T$.

If $F(S)=B$, then $P(S)=P(B)$. Moreover, for every $S\in U$, $P(S)\subseteq{\cal I}$.

We can now establish Property 2 by the following claim.

For every $S\subseteq U$, $F(S)\subseteq S\subseteq V(F(S))$, and $g^{F(S)}(S)=f(S)$.

Let $P(S)=B_{0}\subset B_{1}\subset\dots\subset F(S)$. $F(S)$ always checks that $x\in S$ before including an element $x$, so $F(S)\subseteq S$. To see that $S\subseteq V(F(S))$, assume there exists $x\in S\setminus V(F(S))$. By submodularity we have $\partial_{x}f(B_{j})\geq\partial_{x}f(F(S))>\gamma$ for every set $B_{j}$. But if $\partial_{x}f(B_{j})>\gamma$ for every $B_{j}$ and $x\in S$, it must be that $x\in F(S)$. But then $\partial_{x}f(F(S))=0$, contradicting the fact that $x\not\in V(F(S))$.

Finally, we note that since $S\subseteq V(F(S))$, $g^{F(S)}(S)$ is defined ($S$ is in the domain of $g^{F(S)}$) and since $F(S)\subseteq S$, $g^{F(S)}(S)=f(F(S)\cup S)=f(S)$. ∎

Definition of T𝑇T and proof of Item 3.

We will now define the mapping $T$. The idea is to consider a set $B\in{\cal I}$ and $P(B)$ and consider all the elements we had to “reject” on the way from the root to $B$. We say that an element $x\in U$ is “rejected” if, when $x$ is considered by $F(S)$, it has high influence on the current set, but is not in $B$. Since any set $S$ such that $B=F(S)$ satisfies $P(S)=P(B)$ (Fact 3.1), and any set $S$ that contains a rejected element would have taken a different path, we will get that the elements $x\in T(B)$ “witness” the fact that $B\neq F(S)$. We define the map $T(B)$ as follows:

If $B=F(S)$, then $B\subseteq S\subseteq V(B)$ and $S\cap T(B)=\emptyset$.

We have already demonstrated the first part of the claim in Claim 3.4, so we focus on the claim that $S\cap T(B)=\emptyset$. By Fact 3.1, every set $S$ s.t. $B=F(S)$ satisfies $P(S)=P(B)$. Let $(B_{0}\subset B_{1}\subset\dots\subset B)=P(B)$. Suppose there is an element $x\in S\cap T(B)$. Then there is a set $B_{j}$ such that $x\not\in V(B_{j})$ and $x\not\in B$. But since $x\not\in V(B_{j})$ and $x\in S$, it must be that $x\in B_{j+1}$, contradicting the fact that $B_{j+1}\subseteq B$. ∎

If $B\subseteq S\subseteq V(B)$, $S\cap T(B)=\emptyset$, then $B=F(S)$.

Suppose for the sake of contradiction that there a set $B^{\prime}\neq B$ such that $B^{\prime}=F(S)$. There exists an element $x\in B\triangle B^{\prime}$, and we consider the minimal such $x$ under $\prec$. Let $P(B)=(B_{0}\subset B_{1}\subset\dots\subset B)$ and $P(S)=P(B^{\prime})=(B^{\prime}_{0}\subset B^{\prime}_{1}\subset\dots\subset B^{\prime})$. Since $x$ is minimal in $B\triangle B^{\prime}$, there must be $j$ be such that $B_{i}=B^{\prime}_{i}$ for all $i\leq j$, but $x\in B_{j+1}\triangle B^{\prime}_{j+1}$. Consider two cases:

$B\supset B^{\prime}$. Thus $x\in B\setminus B^{\prime}$ Moreover, since $x\in B\subseteq S$, it must be that when $x$ was considered in the execution of $F(S)$, and $B^{\prime}_{j}$ was the current set, it was the case that $x\in V(B^{\prime}_{j})$. But $B_{j}=B^{\prime}_{j}$, so $x\in V(B_{j})$, contradicting the fact that $x\in B_{j+1}$.

$B\not\supset B^{\prime}$. Thus $x\in B^{\prime}\setminus B$. Since $x\in B^{\prime}=F(S)\subseteq S$ (Claim 3.4), we have $x\in S$. Moreover, since $x\in B^{\prime}_{j+1}$ we must have $x\not\in V(B^{\prime}_{j})=V(B_{j})$. Thus we have $x\not\in V(B_{j})$ and $x\not\in B$, which implies $x\in T(B)$, by construction. Thus $S\cap T(B)\neq\emptyset$, a contradiction.

The previous two claims establish Item 3.

Finally we observe that the enumeration of ${\cal I}$ requires time at most $|U|\cdot|{\cal I}|=|U|^{O(1/\gamma)}$, since we iterate over each element of $U$ and then iterate over each set currently in ${\cal I}$. We also note that we can compute the mappings $F$ and $T$ in time linear in $|{\cal I}|=|U|^{O(1/\gamma)}$ and can compute $V(B)$ in time linear in $|U|$. These observations establish Property 4 and complete the proof of Lemma 3.1. ∎

Given any submodular function $f\colon 2^{U}\to$ and $\gamma>0,$ Algorithm 2 makes the following guarantee. There are maps $F,T\colon 2^{U}\to 2^{U}$ satisfying properties 1-4 of Lemma 3.1 and moreover, can be computed using tolerant queries to $f$ with tolerance $\gamma/12$.

Observe that Algorithm 2 differs from Algorithm 1 only in the choice of parameters. The analysis required to establish the Lemma is also a natural modification of the analysis of Lemma 3.1, so we will refer the reader to the proof of that Lemma for several details and only call attention to the steps of the proof that require modification.

First, we establish a bound on the size of ${\cal I}$

Let $B\in\mathcal{I}$ be a set, $B=\{x_{1},\dots,x_{|B|}\}$. Let $B_{0}=\emptyset$ and $B_{i}=\{x_{1},\dots,x_{i}\}$ for $i=1,\dots,|B|-1$. Then

Therefore, it must be that $|B|\leq 6/\gamma$, and there are at most $|U|^{6/\gamma}$ such sets over $|U|$ elements. ∎

For every $g^{B}\in{\cal G}$, $g^{B}$ is submodular and $\sup_{x\in V(B),S\subseteq V(B)}\partial_{x}g^{B}(S)\leq\gamma$.

The proof of submodularity is identical to Claim 3.3

Definition of F𝐹F and proof of Item 2.

Now we establish Property 2 via the following claim, analogous to Claim 3.4 in the proof of Lemma 3.1

For every $S\subseteq U$, $F(S)\subseteq S\subseteq V(F(S))$. Moreover, $g^{F(S)}(S)=f(S)$.

Let $P(S)=B_{0}\subset B_{1}\subset\dots\subset F(S)$. The fact that $F(S)\subseteq S$ follows as in Claim 3.4. To see that $S\subseteq V(F(S))$, assume there exists $x\in S\setminus V(F(S))$. By submodularity of $f$, and (4), we have

The fact that $g^{F(S)}(S)=f(S)$ follows as in the proof of Claim 3.4. ∎

Definition of T𝑇T and proof of Item 3.

We also define the promised mapping $T(S)$ in the same manner as in the proof of Lemma 3.1, but using $V^{\prime}$ in place of $V$ to decide whether or not we select an element $x$ for inclusion in the set $F(S)$.

Property 4 also follows as in the proof of Lemma 3.1. This completes the proof of the Lemma. ∎

We now present our algorithm for learning monotone submodular functions over product distributions. For a subset of the universe $V\subseteq U$, let ${\cal D}_{V}$ denote the distribution ${\cal D}$ restricted to the variables in $V$. Note that if ${\cal D}$ is a product distribution, then ${\cal D}_{V}$ remains a product distribution and is easy to sample from.

For any $\alpha,\beta\in(0,1]$, Algorithm 5 $(\alpha,\beta)$-approximates any submodular function $f\colon 2^{U}\to$ under any product distribution ${\cal D}$ in time $|U|^{O(\alpha^{-2}\log(1/\beta))}$ using oracle queries to $f$ of tolerance $\alpha^{2}/72\log(2/\beta)$.

For a set $S\subseteq U$, we let $B=F(S)$ and $g^{B}$ be the corresponding submodular function as in Lemma 3.7. Note that since the queries have tolerance $\alpha^{2}/72\log(1/\beta)\leq\gamma/12$, the lemma applies. We will analyze the error probability as if the estimates $\mu_{g^{B}}$ were computed using exact oracle queries to $f$, and will note that using tolerant queries to $f$ can only introduce an additional error of $\alpha^{2}/72\log(1/\beta)\leq\alpha/6$. We claim that, under this condition

To see this, recall that for every $S\subseteq U$, $g^{F(S)}(S)=f(S)$. By Property 3 of Lemma 3.1, the condition that $B=F(S)$ is equivalent to the conditions that $B\subseteq S\subseteq V(B)$ and $S\cap T(B)=\emptyset$. Hence,

Now, applying the concentration inequality for submodular functions stated as Corollary 2.2, we get

Plugging in $t=5\alpha/6\gamma=\frac{5\log(2/\beta)}{\alpha}$ and simplifying we get $\operatorname*{\varmathbb{P}r}_{S\sim{\cal D}_{V(B)\setminus T(B)}}\left\{\left|g^{B}(S)-\mu_{g^{B}}\right|>\alpha\right\}\leq\beta\,.$ Combining this with (3.1), the claim follows. ∎

2 Non-monotone Submodular Functions

For non-monotone functions, we need a more refined argument. Our main structure theorem replaces Property 1 in Lemma 3.1 by the stronger guarantee that $|\partial_{x}g(S)|\leq\alpha$ for all $g\in{\cal G}$, even for non-monotone submodular functions. Observe that for a submodular function $f:2^{V}\rightarrow\varmathbb{R}$, the function $\overline{f}\colon 2^{V}\to\varmathbb{R}$ defined as $\overline{f}(S)=f(V\backslash S)$ is also submodular; moreover

Given these two facts, we can now prove our main structure theorem.

Given any submodular function $f\colon 2^{U}\to$ and $\gamma>0,$ Algorithm 4 makes the following guarantee. There are maps $F\colon 2^{U}\to 2^{U}\times 2^{U}$ and $T\colon 2^{U}\times 2^{U}\to 2^{U}$ such that:

(Lipschitz) For every $g^{B,C}\in{\cal G}$, $g^{B,C}$ is submodular and satisfies $\sup_{x\in V(B,C),S\subseteq V(B,C)}|\partial_{x}g^{B,C}(S)|\leq\gamma$.

(Completeness) For every $S\subseteq U$, $F(S)\subseteq S\subseteq V(F(S))$ and $g^{F(S)}(S)=f(S).$

(Uniqueness) For every $g^{B,C}\in{\cal G}$, $F(S)=(B,C)$ if and only if $B,C\subseteq S\subseteq V(B,C)$ and $S\cap T(B,C)=\emptyset$.

(Size) The size of ${\cal G}$ is at most $|{\cal G}|=|U|^{O(1/\gamma)}$. Moreover, given tolerant oracle access to $f$ with tolerance $\gamma/12$, we compute $F,V,T$ in time $|U|^{O(1/\gamma)}$.

For every $g^{B,C}\in{\cal G}$, $g^{B,C}$ is submodular and $\sup_{x\in V(B,C),S\subseteq V(B,C)}|\partial_{x}g^{B,C}(S)|\leq\gamma$.

Submodularity follows directly from Property 1 of Lemma 3.7. The same property of the lemma guarantees that for every $g^{B}\in{\cal G}(f)$ and $g^{C}\in{\cal G}(B)$, $\sup_{x\in V_{B}(C),S\subseteq V_{B}(C)}\partial_{x}g^{C}(S)\leq\gamma$. Moreover, by (8), $\inf_{x\in V_{f}(B),S\subseteq V_{f}(B)}\partial_{x}\overline{g}^{B}(S)\geq-\gamma$. Taken together, we obtain $\sup_{x\in V(B,C),S\subseteq V(B,C)}|\partial_{x}g^{B,C}(S)|\leq\gamma$. ∎

Item 2 will follow from the analogous property in Lemma 3.7 almost directly. To construct the mapping $F(S)$, we want to first compute the appropriate function $g^{B}\in{\cal G}(f)$, using $F_{f}(S)$ and then find the appropriate function $g^{C}\in{\cal G}(B)$ using $F_{B}(S)$. Thus we can take $F(S)=(F_{f}(S),F_{F_{f}(S)}(S))$. By Lemma 3.7, Item 2 we have $B\subseteq S\subseteq V_{f}(B)$ and $C\subseteq S\subseteq V_{B}(C)$, so we conclude $B,C\subseteq S\subseteq V(B,C)$.

Definition of T𝑇T and proof of Item 3.

Item LABEL:item:unique2 will also follow from the analogous property in Lemma 3.7. By Lemma 3.7, Item 3, we have that $F_{f}(S)=B$ if and only if $B\subseteq S\subseteq V_{f}(B)$ and $S\cap T_{f}(B)=\emptyset$. By the same Lemma, we also have that $F_{B}(S)=C$ if and only if $C\subseteq S\subseteq V_{B}(C)$ and $S\cap T_{B}(C)=\emptyset$. So if we define $T(B,C)=T_{f}(B)\cup T_{B}(C)$, we can conclude that $F(S)=(B,C)$ if and only if $B,C\subseteq S\subseteq V(B,C)$ and $S\cap T(B,C)=\emptyset$.

Now it is clear that $F(S)=(B,C)$ if $F_{f}(S)=B$ and $F_{B}(S)=C$, which by Property 3 of Lemma 3.7 necessitates that $B\subseteq S\subseteq V_{f}(B)$, $S\cap T_{f}(B)=\emptyset$, $C\subseteq S\subseteq V_{B}(S)$, and $S\cap T_{B}(C)=\emptyset$. We have already defined $V(B,C)$ and now we define $T(B,C)=T_{f}(B)\cup T_{B}(C)$. It is clear now that $F(S)=(B,C)$ if and only if $B,C\subseteq S\subseteq V(B,C)$ and $S\cap T(B,C)=\emptyset$.

The size of ${\cal G}$ and running time bounds in Property LABEL:item:efficient2 also follow directly from the analogous property of Lemma 3.1. The fact that we can compute the family ${\cal G}$ and the associated mappings $F,V,T$ using oracle access to $f$ with tolerance $\gamma/12$ follows from the fact that each invocation of Lemma 3.1 can be computed using queries with tolerance $\gamma/12$ and from the fact that Algorithm 4 only queries $f$ in order to invoke Lemma 3.7. This completes the proof of the Theorem. ∎

We now present our algorithm for learning arbitrary submodular functions over product distributions. For a subset of the universe $V\subseteq C$, let ${\cal D}_{V}$ denote the distribution ${\cal D}$ restricted to the variables in $V$. Note that if ${\cal D}$ is a product distribution, then ${\cal D}_{V}$ remains a product distribution and is easy to sample from.

To avoid notational clutter, throughout this section we will not consider the details of how we construct our estimate $\mu_{g}$. However, it is an easy observation that this quantity can be estimated to a sufficiently high degree of accuracy using a small number of random samples.

For any $\alpha,\beta\in(0,1]$, Algorithm 5 $(\alpha,\beta)$-approximates any submodular function $f\colon 2^{U}\to$ under any product distribution in time $|U|^{O(\alpha^{-2}\log(1/\beta))}$ using oracle queries to $f$ of tolerance $\alpha^{2}/72\log(1/\beta)$

For a set $S\subseteq U$, we let $(B,C)=F(S)$ and $g^{B,C}$ be the corresponding submodular function as in Theorem 3.12. Note that since the queries have tolerance $\alpha^{2}/72\log(1/\beta)\leq\gamma/12$, the lemma applies. We will analyze the error probability as if the estimates $\mu_{g^{B}}$ were computed using exact oracle queries to $f$, and will note that using tolerant queries to $f$ can only introduce an additional error of $\alpha^{2}/72\log(1/\beta)\leq\alpha/6$. We claim that, under this condition We claim that

To see this, recall that for every $S\subseteq U$, $g^{F(S)}(S)=f(S)$. By Property 3 of Lemma 3.1, the condition that $B=F(S)$ is equivalent to the conditions that $B,C\subseteq S\subseteq V(B,C)$ and $S\cap T(B,C)=\emptyset$. Hence,

Now, applying the concentration inequality for submodular functions stated as Corollary 2.2, we get

Plugging in $t=5\alpha/6\gamma=\frac{5\log(2/\beta)}{\alpha}$ and simplifying we get $\operatorname*{\varmathbb{P}r}_{S\sim{\cal D}_{V(B,C)\setminus T(B,C)}}\left\{\left|g^{B,C}(S)-\mu_{g^{B,C}}\right|>\alpha\right\}\leq\beta\,.$ Combining this with Equation (3.2), the claim follows. ∎

Applications to privacy-preserving query release

In this section, we show how to apply our algorithm from Section 3 to the problem of releasing monotone conjunctions over a boolean database. In Section 4.1, we also show how our mechanism can be applied to release the cut function of an arbitrary graph.

Let us now begin with the monotone disjunctions. We will then extend the result to monotone conjunctions. Given our previous results, we only need to argue that monotone disjunctions can be described by a submodular function. Indeed, every element $S\in\{0,1\}^{d}$ naturally corresponds to a monotone Boolean disjunction $d_{S}\colon\{0,1\}^{d}\to\{0,1\}$ by putting

Note that in contrast to Section 3 here we use $x$ to denote an element of $\{0,1\}^{d}.$ Let $F_{\textrm{Disj}}:\{0,1\}^{d}\rightarrow$ be the function such that $F_{\textrm{Disj}}(S)=d_{S}(D)$. It is easy to show that $F_{\textrm{Disj}}(S)$ is a monotone submodular function.

$F_{\textrm{Disj}}$ is a monotone submodular function.

Let $X_{i}^{+}$ denote the set of elements $x\in D$ such that $x_{i}=1$, and let $X_{i}^{-}$ denote the set of elements $x\in D$ such that $x_{i}=0$. Consider the set system $U=\{X_{i}^{+},X_{i}^{-}\}_{i=1}^{d}$ over the universe of elements $x\in D$. Then there is a natural bijection between $F_{\textrm{Disj}}(D)$ and the set coverage function $\textrm{Cov}:2^{U}\rightarrow[0,|D|]$ defined to be $\textrm{Cov}(S)=|\bigcup_{X\in U}X|$, which is a monotone submodular function. ∎

We therefore obtain the following corollary directly by combining Theorem 3.11 with Proposition 2.1.

Let $\alpha,\beta,\varepsilon>0.$ There is an $\varepsilon$-differentially private algorithm that $(\alpha,\beta)$-releases the set of monotone Boolean disjunctions over any product distribution in time $d^{t(\alpha,\beta)}$ for any data set of size $|D|\geq d^{t(\alpha,\beta)}/\varepsilon$ where $t(\alpha,\beta)=O(\alpha^{-2}\log(1/\beta)).$

For completeness, we will present the algorithm for privately releasing monotone disjunctions over a product distribution ${\cal D}$ for a data set $D$, though we will rely on Corollary 4.2 for the formal analysis.

We will next see that this corollary directly transfers to monotone conjunctions. A monotone Boolean conjunction $c_{S}:\{0,1\}^{d}\rightarrow\{0,1\}$ is defined as

Given the last equation, it is clear that in order to release conjunctions over some distribution, it is sufficient to release disjunctions over the same distribution after replacing every data item $x\in D$ by its negation $\bar{x},$ i.e., $\bar{x}_{i}=1-x_{i}.$ Hence, Corollary 4.2 extends directly to monotone conjunctions.

Note that the uniform distribution on disjunctions of width $w$ is not a product distribution, which is what we require to apply Theorem 3.14 directly. However, in Lemma 4.3 we show that for monotone submodular functions (such as $F_{\textrm{Disj}}^{D}$) the concentration of measure property required in the proof Theorem 3.14 is still satisfied. Of course, we can instantiate the theorem for every $w\in\{1,\dots,k\}$ to obtain a statement for conjunctions of any width.

Indeed, given a monotone submodular function $f\colon 2^{U}\rightarrow\varmathbb{R}$, let $S\in 2^{U}$ be the random variable where for every $x\in U,$ independently $x\in S$ with probability $w/d$ and $x\not\in S$ with probability $1-w/d.$ On the other hand, let $T\in 2^{U}$ denote the uniform distribution over strings in $2^{U}$ of weight $w.$ The following lemma is due to Balcan and Harvey [BH10].

Assume $f:2^{U}\rightarrow\varmathbb{R}$ is monotone function, and $S$ and $T$ are chosen at random as above. Then,

Throughout this section we focus on the case of monotone disjunctions and conjunctions. Our algorithm can be extended to non-monotone conjunctions/disjunctions as well. However, this turns out to be less interesting than the monotone case. Indeed, a random non-monotone conjunction of width $w$ is false on any fixed data item with probability $2^{-w}$, thus when $w\geq\log(1/\alpha)$, the constant function is a good approximation to $F_{Disj}$ on a random non-monotone conjunction of width $w$. We therefore omit the non-monotone case from our presentation.

1 Releasing the cut function of a graph

Consider a graph $G=(V,E)$ in which the edge-set represents the private database (We assume here that each individual is associated with a single edge in $G$. The following discussion generalizes to the case in which individuals may be associated with multiple edges, with a corresponding increase in sensitivity). The cut function associated with $G$ is $f_{G}:2^{V}\rightarrow$, defined as:

We observe that the graph cut function encodes a collection of counting queries over the database $E$ and so has sensitivity $1/|V|^{2}$.

For any graph $G$, $f_{G}$ is submodular.

The decomposition from Theorem 3.12 constructs a collection of functions ${\cal G}$ of size $|{\cal G}|\leq 2^{2/\alpha}$.

Let $u\in V$, and $S\subset V$ such that $|\partial_{u}f_{G}(S)|\geq\alpha$. It must be that the degree of $u$ in $G$ is at least $\alpha\cdot|E|$. But there can be at most $2/\alpha$ such high-influence vertices, and therefore at most $2^{2/\alpha}$ subsets of high influence vertices. ∎

Algorithm 5 can be used to privately $(\alpha,\beta)$-release the cut function on any graph over any product distribution in time $t(\alpha,\beta,\varepsilon)$ for any database of size $|D|\geq t(\alpha,\beta,\varepsilon)$, while preserving $\varepsilon$-differential privacy, where:

This follows directly from a simple modification of Theorem 3.14, by applying Lemma 4.4 and plugging in the size of the decomposition ${\cal G}$. The algorithm can then be made privacy preserving by applying proposition 2.1. ∎

Equivalence between agnostic learning and query release

In this section we show an information-theoretic equivalence between agnostic learning and query release in the statistical queries model. In particular, given an agnostic learning algorithm for a specific concept class we construct a query release algorithm for the same concept class.

Consider a distribution $A$ over $X\times\{0,1\}$ and a concept class $C$. An agnostic learning algorithm (in the strong sense) finds the concept $q\in C$ that approximately maximizes $\operatorname*{\varmathbb{P}r}_{(x,b)\sim A}\left\{q(x)=b\right\}$ to within an additive error of $\alpha$. Our reduction from query release to agnostic learning actually holds even for weak agnostic learning. A weak agnostic learner is not required to maximize $\operatorname*{\varmathbb{P}r}_{(x,b)\sim A}\left\{q(x)=b\right\}$, but only to find a sufficiently good predicate $q$ provided that one exists.

Note that if we can agnostically learn $C$ in the strong sense from queries of tolerance $\tau$ to within additive error $\alpha-\beta$ with probability $1-\gamma,$ then there is also an $(\alpha,\beta,\gamma,\tau)$-weak agnostic learner.

We are now ready to state the main result of this section, which shows that a weak agnostic SQ-learner for any concept class is sufficient to release the same concept class in the SQ model.

Let $C$ be a concept class. Let ${\cal A}$ be an algorithm that $(\alpha/2,\beta,\gamma,\tau)$ weak agnostic-SQ learns $C$ with $\tau\leq\beta/8$. Then there exists an algorithm ${\cal B}$ that invokes ${\cal A}$ at most $T=8\log|X|/\beta^{2}$ times and $(\alpha,0)$-releases $C$ with probability at least $1-T\gamma$.

The proof strategy is as follows. We will start from $D_{0}$ being the uniform distribution over $X.$ We will then construct a short sequence of distributions $D_{1},D_{2},\dots,D_{T}$ such that no concept in $C$ can distinguish between $D$ and $D_{T}$ up to bias $\alpha.$ Each distribution $D_{t}$ is obtained from the previous one using a multiplicative weights approach as in [HR10] and with the help of the learning algorithm that’s given in the assumption of the theorem. Intuitively, at every step we use the agnostic learner to give us the predicate $q_{t}\in C$ which distinguishes between $D_{t}$ and $D.$ In order to accomplish this we feed the agnostic learner with the distribution $A_{t}$ that labels elements sampled from $D$ by $1$ and elements sampled from $D_{t}$ by $0.$ For a technical reason we also need to consider the distribution with and $1$ flipped. Once we obtained $q_{t}$ we can use it as a penalty function in the update rule of the multiplicative weights method. This has the effect of bringing $D$ and $D_{t}$ closer in relative entropy. A typical potential argument then bounds the number of update steps that can occur before we reach a distribution $D_{t}$ for which no good distinguisher in $C$ exists.