Faster Algorithms for Privately Releasing Marginals

Introduction

Consider a database $D\in(\{0,1\}^{d})^{n}$ in which each of the $n=|D|$ rows corresponds to an individual’s record, and each record consists of $d$ binary attributes. The goal of privacy-preserving data analysis is to enable rich statistical analyses on the database while protecting the privacy of the individuals. In this work, we seek to achieve differential privacy , which guarantees that no individual’s data has a significant influence on the information released about the database.

One of the most important classes of statistics on a dataset is its marginals. A marginal query is specified by a set $S\subseteq[d]$ and a pattern $t\in\{0,1\}^{|S|}$. The query asks, “What fraction of the individual records in $D$ has each of the attributes $j\in S$ set to $t_{j}$?” A major open problem in privacy-preserving data analysis is to efficiently create a differentially private summary of the database that enables analysts to answer each of the $3^{d}$ marginal queries. A natural subclass of marginals are $k$-way marginals, the subset of marginals specified by sets $S\subseteq[d]$ such that $|S|\leq k$.

Privately answering marginal queries is a special case of the more general problem of privately answering counting queries on the database, which are queries of the form, “What fraction of individual records in $D$ satisfy some property $q$?” Early work in differential privacy showed how to approximately answer any set of of counting queries $\mathcal{Q}$ by perturbing the answers with appropriately calibrated noise, providing good accuracy (say, within $\pm.01$ of the true answer) as long as $|D|\gtrsim|\mathcal{Q}|^{1/2}$.

Given this state of affairs, it is natural to seek efficient algorithms capable of privately releasing approximate answers to marginal queries even when $|D|\ll d^{k}$. A recent series of works have shown how to privately release answers to $k$-way marginal queries with small average error (over various distributions on the queries) with both running time and minimum database size much smaller than $d^{k}$ (e.g. $d^{O(1)}$ for product distributions and $\min\{d^{O(\sqrt{k})},d^{O(d^{1/3})}\}$ for arbitrary distributions ). Hardt et. al. also gave an algorithm for privately releasing $k$-way marginal queries with small worst-case error and minimum database size much smaller than $d^{k}$. However the running time of their algorithm is still $d^{\Theta(k)}$, which is polynomial in the number of queries.

In this paper, we give faster algorithms for releasing marginals and other classes of counting queries.

For notational convenience, we focus on monotone $k$-way disjunction queries. However, our results extend straightforwardly to general non-monotone $k$-way disjunction queries (see Section 4.1), which are equivalent to $k$-way marginals. A monotone $k$-way disjunction is specified by a set $S\subseteq[d]$ of size $k$ and asks what fraction of records in $D$ have at least one of the attributes in $S$ set to $1$.

Our algorithm is inspired by a series of works reducing the problem of private query release to various problems in learning theory. One ingredient in this line of work is a shift in perspective introduced by Gupta, Hardt, Roth, and Ullman . Instead of viewing disjunction queries as a set of functions on the database, they view the database as a function $f_{D}\colon\{0,1\}^{d}\to$, in which each vector $s\in\{0,1\}^{d}$ is interpreted as the indicator vector of a set $S\subseteq[d]$, and $f_{D}(s)$ equals the evaluation of the disjunction specified by $S$ on the database $D$. They use the structure of the functions $f_{D}$ to privately learn an approximation $g_{D}$ that has small average error over any product distribution on disjunctions.In their learning algorithm, privacy is defined with respect to the rows of the database $D$ that defines $f_{D}$, not with respect to the examples given to the learning algorithm (unlike earlier works on “private learning” ).

Cheraghchi, Klivans, Kothari, and Lee observed that the functions $f_{D}$ can be approximated by a low-degree polynomial with small average error over the uniform distribution on disjunctions. They then use a private learning algorithm for low-degree polynomials to release an approximation to $f_{D}$; and thereby obtain an improved dependence on the accuracy parameter, as compared to .

Hardt, Rothblum, and Servedio observe that $f_{D}$ is itself an average of disjunctions (each row of $D$ specifies a disjunction of bits in the indicator vector $s\in\{0,1\}^{d}$ of the query), and thus develop private learning algorithms for threshold of sums of disjunctions. These learning algorithms are also based on low-degree approximations of sums of disjunctions. They show how to use their private learning algorithms to obtain a sanitizer with small average error over arbitrary distributions with running time and minimum database size $d^{O(\sqrt{k})}$. They then are able to apply the private boosting technique of Dwork, Rothblum, and Vadhan to obtain worst-case accuracy guarantees. Unfortunately, the boosting step incurs a blowup of $d^{k}$ in the running time.

We improve the above results by showing how to directly compute (a noisy version of) a polynomial $p_{D}$ that is privacy-preserving and still approximates $f_{D}$ on all $k$-way disjunctions, as long as $|D|$ is sufficiently large. Specifically, the running time and the database size requirement of our algorithm are both polynomial in the number of monomials in $p_{D}$, which is $d^{O(\sqrt{k})}$. By “directly”, we mean that we compute $p_{D}$ from the database $D$ itself and perturb its coefficients, rather than using a learning algorithm. Our construction of the polynomial $p_{D}$ uses the same low-degree approximations exploited by Hardt et. al. in the development of their private learning algorithms.

In summary, the main difference between prior work and ours is that prior work used learning algorithms that have restricted access to the database, and released the hypothesis output by the learning algorithm. In contrast, we do not make use of any learning algorithms, and give our release algorithm direct access to the database. This enables our algorithm to achieve a worst-case error guarantee while maintaining a minimal database size and running time much smaller than the size of the query set. Our algorithm is also substantially simpler than that of Hardt et. al.

We also consider other families of counting queries. We define the class of $r$-of-$k$ queries. Like a monotone $k$-way disjunction, an $r$-of-$k$ query is defined by a set $S\subseteq[d]$ such that $|S|\leq k$. The query asks what fraction of the rows of $D$ have at least $r$ of the attributes in $S$ set to $1$. For $r=1$, these queries are exactly monotone $k$-way disjunctions, and $r$-of-$k$ queries are a strict generalization.

As an example application, consider a database that allows high school students to express their preferences for colleges in the form of a decision list. For example, a student may say, “If the school is ranked in the top ten nationwide, I am willing to apply to it. Otherwise, if the school is rural, I am unwilling to apply. Otherwise, if the school has a good basketball team then I am willing to apply to it.” And so on. Each student is allowed to use up to $k$ attributes out of a set of $m$ binary attributes. Our sanitizer allows any college (represented by its $m$ binary attributes) to determine the fraction of students willing to apply.

For comparison, we note that all the results on releasing $k$-way disjunctions (including ours) also apply to a dual setting where the database records specify a $k$-way disjunction over $m$ bits and the queries are $m$-bit strings (in this setting $m$ plays the role of $d$). Theorem 1.3 generalizes this dual version of Theorem 1.1, as length-$k$ decision lists are a strict generalization of $k$-way disjunctions.

We prove the latter two results (Theorems 1.2 and 1.3) using the same approach outlined for marginals (Theorem 1.1), but with different low-degree polynomial approximations appropriate for the different types of queries.

An attractive type of summary is a synthetic database. A synthetic database is a new database $\widehat{D}\in(\{0,1\}^{d})^{\widehat{n}}$ whose rows are “fake”, but such that $\widehat{D}$ approximately preserves many of the statistical properties of the database $D$ (e.g. all the marginals). Some of the previous work on counting query release has provided synthetic data, starting with Barak et. al. and including .

Preliminaries

Let a database $D\in\mathcal{X}^{n}$ be a collection of $n$ rows $x^{(1)},\dots,x^{(n)}$ from a data universe $\mathcal{X}$. We say that two databases $D_{1},D_{2}\in\mathcal{X}^{n}$ are adjacent if they differ only on a single row, and we denote this by $D_{1}\sim D_{2}$.

A sanitizer $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{R}$ takes a database as input and outputs some data structure in $\mathcal{R}$. We are interested in sanitizers that satisfy differential privacy.

A sanitizer $\mathcal{A}\colon\mathcal{X}^{n}\to\mathcal{R}$ is $(\varepsilon,\delta)$-differentially private if for every two adjacent databases $D,D^{\prime}\in\mathcal{X}^{n}$ and every subset $S\subseteq\mathcal{R}$, $\Pr\left[\mathcal{A}(D)\in S\right]\leq e^{\varepsilon}\Pr\left[\mathcal{A}(D^{\prime})\in S\right]+\delta.$ In the case where $\delta=0$ we say that $\mathcal{A}$ is $\varepsilon$-differentially private.

Since a sanitizer that always outputs $\bot$ satisfies Definition 2.1, we also need to define what it means for a sanitizer to be accurate. In particular, we are interested in sanitizers that give accurate answers to counting queries. A counting query is defined by a boolean predicate $q\colon\mathcal{X}\to\{0,1\}$. We define the evaluation of the query $q$ on a database $D\in\mathcal{X}^{n}$ to be $q(D)=\frac{1}{n}\sum_{i=1}^{n}q(x^{(i)}).$ We use $\mathcal{Q}$ to denote a set of counting queries.

An output $Z$ of a sanitizer $\mathcal{A}(D)$ is $\alpha$-accurate for the query set $\mathcal{Q}$ if $|q(Z)-q(D)|\leq\alpha$ for every $q\in\mathcal{Q}$. A sanitizer is $(\alpha,\beta)$-accurate for the query set $\mathcal{Q}$ if for every database $D$,

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

The choice of the $L_{1}$ norm in the accuracy guarantee of the lemma is for convenience, and doesn’t matter for the parameters of Theorems 1.1-1.3 (except for the hidden constants).

If the privacy requirement is relaxed to $(\varepsilon,\delta)$-differential privacy (for $\delta>0)$, then it is sufficient to perturb each coordinate of $g(D)$ with noise from a Laplace distribution of smaller magnitude, leading to smaller error.

2 Query Function Families

We take the approach of Gupta et. al. and think of the database $D$ as specifying a function $f_{D}$ mapping queries $q$ to their answers $q(D)$, which we call the $\mathcal{Q}$-representation of $D$. We now describe this transformation more formally:

Let $\mathcal{Q}=\left\{q_{y}\right\}_{y\in Y_{\mathcal{Q}}\subseteq\{0,1\}^{m}}$ be a set of counting queries on a data universe $\mathcal{X}$, where each query is indexed by an $m$-bit string. We define the index set of $\mathcal{Q}$ to be the set $Y_{\mathcal{Q}}=\left\{y\in\{0,1\}^{m}\mid q_{y}\in\mathcal{Q}\right\}$.

For some intuition about this transformation, when the queries are monotone $k$-way disjunctions on a database $D\in(\{0,1\}^{d})^{n}$, the queries are defined by sets $S\subseteq[d]$ , $|S|\leq k$. In this case each query can be represented by the $d$-bit indicator vector of the set $S$, with at most $k$ non-zero entries. Thus we can take $m=d$ and $Y_{\mathcal{Q}}=\left\{y\in\{0,1\}^{d}\mid\sum_{j=1}^{d}y_{j}\leq k\right\}$.

3 Polynomial Approximations

Let $\mathcal{P}_{t,T}$ be the family of all $m$-variate real polynomials of degree $t$ and norm $T$. In many cases, the functions $f_{\mathcal{Q},x}:\{0,1\}^{m}\to\{0,1\}$ can be approximated well on all the indices in $Y_{\mathcal{Q}}$ by a family of polynomials $\mathcal{P}_{t,T}$ with low degree and small norm. Formally:

Given a family of $m$-variate functions $\mathcal{F}=\left\{f_{x}\right\}_{x\in\mathcal{X}}$ and a set $Y\subseteq\{0,1\}^{m}$, we say that the family $\mathcal{P}_{t,T}$ uniformly $\gamma$-approximates $\mathcal{F}$ on $Y$ if for every $x\in\mathcal{X}$, there exists $p_{x}\in\mathcal{P}_{t,T}$ such that $\max_{y\in Y}|f_{x}(y)-p_{x}(y)|\leq\gamma$.

From Polynomial Approximations to Data Release Algorithms

In this section we present an algorithm for privately releasing any family of counting queries $\mathcal{Q}$ such that $\mathcal{F}_{\mathcal{Q}}$ that can be efficiently and uniformly approximated by polynomials. The algorithm will take an $n$-row database $D$ and, for each row $x\in D$, constructs a polynomial $p_{x}$ that uniformly approximates the function $f_{\mathcal{Q},x}$ (recall that $f_{\mathcal{Q},x}(q)=q(x)$, for each $q\in\mathcal{Q}$). From these, it constructs a polynomial $p_{D}=\frac{1}{n}\sum_{x\in D}p_{x}$ that uniformly approximates $f_{\mathcal{Q},D}$. The final step is to perturb each of the coefficients of $p_{D}$ using noise from a Laplace distribution (Theorem 2.3) and bound the error introduced from the perturbation.

is $(\alpha,\beta)$-accurate for $\mathcal{Q}$ for $\alpha=\gamma+\frac{4T\binom{m+t}{t}^{2}\log\left(\binom{m+t}{t}/\beta\right)}{\varepsilon n}.$

First we construct the sanitizer $\mathcal{A}$. See the relevant codebox below.

We establish that $\mathcal{A}$ is $\varepsilon$-differentially private. This follows from the observation that for any two adjacent $D\sim D^{\prime}$ that differ only on row $i^{*}$,

The last inequality is from the fact that for every $x$, $\vec{p}_{x}$ is a vector of $L_{\infty}$ norm at most $T$. Part 1 of the Theorem now follows directly from the properties of the Laplace Mechanism (Theorem 2.3). Now we construct the evaluator $\mathcal{E}$.

Efficiency.

Accuracy. Finally, we analyze the accuracy of the sanitizer $\mathcal{A}$. First, by the assumption that $\mathcal{P}_{t,T}$ uniformly $\gamma$-approximates $\mathcal{F}$ on $Y\subseteq\{0,1\}^{m}$, we have

where the probability is taken over the coins of $\mathcal{A}$. Part (3) of the Theorem will then follow by the triangle inequality.

The first inequality follows from the fact that every monomial evaluates to or $1$ at the point $y$. This completes the proof of the theorem.

Using Theorem 2.4, we can improve the bound on the error at the expense of relaxing the privacy guarantee to $(\varepsilon,\delta)$-differential privacy. This improved error only affects the hidden constants in Theorems 1.1-1.3, so we only state those theorems for $\varepsilon$-differential privacy.

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

is $(\alpha,\beta)$-accurate for $\mathcal{Q}$ for $\alpha=\gamma+\frac{12T\binom{m+t}{t}\sqrt{\binom{m+t}{t}\log(1/\delta)}\log\left(\binom{m+t}{t}/\beta\right)}{\varepsilon n}.$

The proof of this theorem is identical to that of Theorem 3.1, but using the analysis of the Laplace mechanism from Theorem 2.4 in place of that of Theorem 2.3.

Applications

In this section we establish the existence of explicit families of low-degree polynomials approximating the families $\mathcal{F}_{\mathcal{Q}}$ for some interesting query sets.

We define the class of monotone $k$-way disjunctions as follows:

for every $i\in\left\{0,1,\dots,t_{k}\right\},|c_{i}|\leq 2^{O(\sqrt{k}\log(1/\gamma))}$,

for every $x\in\left\{1,\dots,k\right\}$, $1-\gamma\leq g_{k}(x)\leq 1+\gamma$.

We can use Lemma 4.2 to approximate $k$-way monotone disjunctions. Note that our result easily extends to monotone $k$-way conjunctions via the identity $\wedge_{j=1}^{d}x_{j}y_{j}=1-\vee_{j=1}^{d}(1-x_{j})y_{j}$. Moreover, it extends to non-monotone conjunctions and disjunctions: we may extend the data universe as in [15, Theorem 1.2] to $\{0,1\}^{2d}$, and include the negation of each item in the original domain. Non-monotone conjunctions over domain $\{0,1\}^{d}$ correspond to monotone conjunctions over the expanded domain $\{0,1\}^{2d}$.

Theorem 1.1 in the introduction follows by combining Theorems 3.1 and 4.3.

2 Releasing Monotone r𝑟r-of-k𝑘k Queries

We define the class of monotone $r$-of-$k$ queries as follows:

Sherstov [20, Lemma 3.11] gives an explicit construction of polynomials that can be used to approximate the family $\mathcal{F}_{\mathcal{Q}_{r,k}}$ over $Y_{k}$ with low degree. It can be verified by inspecting the construction that the coefficients of the resulting polynomial are not too large.

$t_{r,k}=O\left(\sqrt{rk}\log(k)+\sqrt{k\log(1/\gamma)\log(k)}\right)$,

for every $x\in\left\{0,1,\dots,r-1\right\}$, $-\gamma\leq g_{r,k}(x)\leq\gamma$, and

for every $x\in\left\{r,\dots,k\right\}$, $1-\gamma\leq g_{r,k}(x)\leq 1+\gamma$.

For completeness we include a proof of Lemma 4.5 in the appendix. We can use these polynomials to approximate monotone $r$-of-$k$ queries.

The construction and proof is identical to that of Theorem 4.3 with the polynomials of Lemma 4.5 in place of the polynomials described in Lemma 4.2. ∎

Theorem 1.2 in the introduction now follows by combining Theorems 3.1 and 4.6. Note that our result also extends easily to non-monotone $r$-of-$k$ queries in the same manner as Theorem 1.1.

Using the principle of inclusion-exclusion, the answer to a monotone $r$-of-$k$ query can be written as a linear combination of the answers to $k^{O(r)}$ monotone $k$-way disjunctions. Thus, a sanitizer that is $(\alpha/k^{O(r)},\beta)$-accurate for monotone $k$-way disjunctions implies a sanitizer that is $(\alpha,\beta)$-accurate for monotone $r$-of-$k$ queries. However, combining this implication with Theorem 1.1 yields a sanitizer with running time $d^{O(r\sqrt{k}\log(k/\beta))}$, which has a worse dependence on $r$ than what we achieve in Theorem 1.2.

3 Releasing Decision Lists

We obtain Theorem 1.3 of the introduction by combining Theorems 3.1 and 4.9.

Generalizations and Limitations of Our Approach

Acknowledgements

We thank Vitaly Feldman, Moritz Hardt, Varun Kanade, Aaron Roth, Guy Rothblum, and Li-Yang Tan for helpful discussions.

References

Appendix A Polynomial Approximation of Decision Lists

At a high level, we treat each term of the above sum independently, using a transformation of the Chebyshev polynomials to approximate each term within additive error $\gamma/k$. This ensures that that the sum of the resulting polynomials approximates $f_{\mathcal{Q},x}(y)$ within additive error $\gamma$ as desired. Details follow.

Let $g_{k}$ be the polynomial described in Lemma 4.2 with error parameter $\gamma^{\prime}=\gamma/k$. Then the polynomial $h_{k}(z)=1-g_{k}(k-z)$ satisfies the following properties:

The degree of $h_{k}$ is $t_{k}=O(\sqrt{k}\log(k/\gamma))$,

for every $z\in\left\{0,\dots,k-1\right\}$, $|h_{k}(z)|\leq\frac{\gamma}{k}$.

Consider the polynomial $p_{x}$ defined as

Appendix B Polynomial Approximation of r𝑟r-of-k𝑘k Queries

$t_{r,k}=O\left(\sqrt{rk}\log(k)+\sqrt{k\log(1/\gamma)\log(k)}\right)$ ,

for every $x\in\left\{0,1,\dots,r-1\right\}$, $-\gamma\leq g_{r,k}(x)\leq\gamma$, and

for every $x\in\left\{r,\dots,k\right\}$, $1-\gamma\leq g_{r,k}(x)\leq 1+\gamma$.

Let $T_{z}$ be the degree $z$ Chebyshev polynomial of the first kind (Fact B.2). We will use the following well-known properties of Chebyshev polynomials.

The Chebyshev polynomials of the first kind satisfy the following properties.

Each coefficient of $T_{z}$ has absolute value at most $3^{z}$.

Let \Delta=\big{\lceil}\frac{\log(k/\gamma)}{\log n}\big{\rceil}, and z=3\Delta\big{\lceil}\log k\big{\rceil}. The construction proceeds in several steps, with the final polynomial $p$ defined in terms of multiple intermediate polynomials.

The coefficients of $q_{1}(t)$ have absolute value at most $k^{O(\Delta)}$.

The final polynomial $p(t)$ is defined as