1 Introduction↩︎

Private synthetic data generation is a widely studied problem at the heart of private data analysis, with major practical implications [1]–[7]. The goal is to use privacy-preserving methods on a sensitive dataset to create a new version that retains key statistical properties of the original. The advantage of private synthetic data is the flexibility of sharing it without privacy concerns for downstream applications.

Let the data domain be \(\mathcal{D}=\{0,1\}^d\), and consider a family \(\mathcal{F}\) of counting queries (i.e., the queries are averages of functions \(f:\mathcal{D}\to \{0, 1\}\)). The goal of synthetic data generation is: given a dataset \(X \in \mathcal{D}^*\) where \(n = |X|\), produce a dataset \(X' \in \mathcal{D}^*\) such that \(f(X) \approx f(X')\) holds, where \(f(X) := \frac{1}{|X|} \sum_{x \in X} f(x)\). Ignoring computational constraints, the optimal error rates for generating synthetic data satifying differential privacy (DP) are known in several cases. We first consider the case of \((\varepsilon, \delta)\)-DP (i.e., approximate-DP). Here, the optimal error rates¹ are \[\textstyle \Theta\Big(\min\Big\{ \frac{\sqrt{|\mathcal{D}|\ln|\mathcal{F}|}}{n\varepsilon}, \frac{\sqrt{|\mathcal{F}|\log(1/\delta)}}{n\varepsilon}, \Big(\frac{\sqrt{\ln|\mathcal{D}|}\ln|\mathcal{F}|\ln(1/\delta)}{n\varepsilon}\Big)^{1/2} \Big\}\Big).\footnote{Upper bounds in the first regime follow from \cite{Vadhan:2017}, for the second regime from \cite{GKM21,DK22}, and for the third regime from \cite{HardtR10}. Lower bounds can be found in \cite{Vadhan:2017}.}\] For \(\varepsilon\)-DP (i.e., pure-DP), the optimal error rates are still open [8], [9], and the best known upper bound is \[\textstyle O\Big(\min\Big\{ \frac{\sqrt{|\mathcal{D}|\ln|\mathcal{F}|}}{n\varepsilon}, \frac{|\mathcal{F}|}{n\varepsilon}, \Big(\frac{\ln|\mathcal{D}|\ln|\mathcal{F}|}{n\varepsilon}\Big)^{1/3} \Big\}\Big).\] For both cases, the first regime is best for small domain size \(|\mathcal{D}|\), the second one is best for small query family size \(|\mathcal{F}|\), and the third one is best when the number of datapoints \(n\) is small (known as the sparse setting). All known algorithms that attain these rates run in time exponential in \(d\).

Unfortunately, under computational constraints, it is known that producing accurate DP synthetic data even for modest and natural classes of queries (e.g., 2-way marginals) is hard, and the above mentioned “exponential in \(d\)” bounds are optimal under standard cryptographic assumptions [10]. Despite this fundamental roadblock, follow-up research has identified specific settings where DP synthetic data can be efficiently produced. A remarkable example is the US Census TopDown algorithm [11], [12], which produced DP synthetic data for hierarchical queries, specifically, where queries are monotone disjunctions over sets from a laminar family. Other works have explored methods based on Bayesian models [13], graphical models [14]–[16], duality [17], [18], and heuristics. It is desirable to obtain a unified approach that is capable of handling general query workloads, and provides a clear distinction between easy and hard instances. Quoting [15],

In general, it would be nice to have a mechanism that can automatically adapt to an analyst-provided workload, and generate synthetic data that provides high utility on the queries and tasks in that workload. Several workload-adaptive mechanisms exist, but they are generally restricted to settings where the full high-dimensional histogram can be explicitly materialized in vector form, and are thus unable to scale to high-dimensional domains.

1.1 Contributions↩︎

Our main contribution is to show that the optimal error rates for DP synthetic data generation over worst-case query workloads are achievable via fixed-parameter tractable (FPT) algorithms. Our techniques are simple, broadly applicable, and both unify and extend existing methods.

• Structural parametrization. We identify the incidence graph treewidth of the query class as a key parameter for achieving FPT. This parameter does not necessarily grow with the query scope size and this allows us to recover, e.g., the polynomial tractability for hierarchical queries [11], [12]. The FPT results for our subsequent algorithms follow from a unified dynamic programming framework over a tree decomposition, detailed in 5.

• Small family size. When \(|\mathcal{F}|\) is small, we propose an FPT DP synthetic data generator based on the dual of a natural linear program (LP) that minimizes query error over fractional histograms over \(\mathcal{D}\). We show that optimizing this dual is FPT via the ellipsoid method [19], as the separation problem is rendered FPT by our dynamic programming framework.

• Sparse regime. When \(n\) is small, we adapt the standard private multiplicative weights update (PMWU) [4] method to implicitly handle the high-dimensional distributions used for the histograms. We prove that sampling from these distributions is sufficient to maintain accuracy (5). Moreover, in 6 we show that this sampling task is FPT, by computing the partition function (by the aforementioned dynamic program) and recursively sampling conditional probabilities from root to leaves.

1.2 Related Work↩︎

The literature on DP synthetic data generation is vast. We summarize here the work more closely related to ours. The noisy LP approach was one of the earliest proposals for DP synthetic data generation [2], [20]; this LP perspective played a key role in the development of PMWU [4], [21].

The hardness of generating synthetic data for all two-way marginals [10] has motivated alternative approaches that are either heuristic or constrain the family of distributions and/or queries, to achieve algorithmic efficiency. [21] observed that if features are partitioned and each query is supported on a distinct block, then the MWU distributions factorize, yielding a compact representation; this turns out to be a low treewidth query class.

Other approaches are based on restricting the histogram distribution to specific parametric families. The most common approach here involves probabilistic graphical models. For example, [13] construct a degree-\(k\) Bayesian network privately via the exponential mechanism, which results in running time exponential in \(k\), and lacks provable accuracy guarantees. Another class of algorithms leverage ideas from graphical models and maximum entropy estimators to design DP synthetic data without making parametric assumptions [14], [15], [22]. For marginal queries under square loss, their algorithms admit an FPT implementation, as they are based on belief propagation [23], [24]. Aside from the different notion of accuracy, their results are comparable to ours when \(|\mathcal{F}|\) is small and consists of marginal queries.

A general approach for efficiently generating private synthetic data in the statistical setting was proposed by [25]. They obtain (approximately) optimal rates for the small \(|\mathcal{F}|\) regime by solving a saddle-point problem on the histogram-query product space, similar to our approach. For computational efficiency, they assume access to a sampler with bounded Rényi condition number with respect to a target distribution, which is used to drastically reduce the histogram dimension. The results are then only applicable to the statistical setting, and under strong side information on the target distribution. For \(k\)-way marginal queries their algorithm is FPT in \(k\), a running time that is not attainable in general [10].

A well-established technique to attain DP for optimization, saddle-point problems (both of them relevant for DP synthetic data), and online learning, is based on combining MWU approaches with sampling from the resulting Gibbs distributions [17], [18], [26]–[28]. Crucially, in all of these works, privacy is achieved by the sampling itself, as it corresponds to an application of the exponential mechanism. Since these solutions become accurate only when collecting sufficiently many samples, there is a degradation of the privacy budget for larger samples (which can be effectively mitigated in some cases). In our approach, privacy is guaranteed by the exponential mechanism over queries, and therefore the sampling can be performed repeatedly without degrading privacy. Our choice of sample size is only limited by the required concentration for accurate estimates of the queries, as well as the need to keep a moderate size sample for efficiency purposes.

Within the sampling approaches outlined above, some works have explored the possibilities of dualizing the synthetic data LP, resorting on integer programming-based algorithms for the maximization subproblems. These problems are NP-hard in the worst-case but become FPT for suitable notions of treewidth [17], [18]. Unfortunately, the resulting error rates are polynomially suboptimal compared to those obtained by PMWU.

There is a vast FPT literature in optimization, sampling and decision problems in connection to various notions of treewidth [29]–[31]. The majority of works in this area either focus on specific graph problems, or on general constraint satisfaction problems, as well as more structural characterizations of FPT under bounded treewidth, such as [32]’s Theorem [32]. Our approaches for FPT in optimization and sampling follow standard techniques from this literature: however, to make the presentation self-contained, we describe the algorithm and running times in detail.

2 Preliminaries↩︎

Consider a data domain \(\mathcal{D}=\{0,1\}^d\). A dataset is a sequence \(X= (x_1, \ldots, x_n) \in \mathcal{D}^{\ast}\), and we denote its size (i.e., number of datapoints) by \(n = |X|\). A dataset \(X\) can be represented as a histogram, \(h^X\in \mathbb{R}_+^\mathcal{D}\), where \(h_x^X=\frac{1}{n}\sum_{i=1}^n [x=x_i]\). We define a fractional histogram as any element of the standard simplex \(\Delta_\mathcal{D}=\{h\in\mathbb{R}_+^\mathcal{D}: \, \sum_{x\in \mathcal{D}} h_x=1\}\).

2.0.0.1 Differential Privacy and Synthetic Data Generation.

A pair \(X, X' \in \mathcal{D}^{\ast}\) of datasets are neighbors (denoted by \(X \simeq X'\)) if they differ by at most one substitution of their datapoints. We say that an algorithm \({\cal A}:\mathcal{D}^{\ast}\to {\cal O}\) is \((\varepsilon,\delta)\)-DP if for every pair \(X\simeq X'\), and for every (measurable) \(E \subseteq {\cal O}\), \(\mathbb{P}[{\cal A}(X)\in E]\leq e^{\varepsilon} \cdot \mathbb{P}[{\cal A}(X')\in E]+\delta\). When \(\delta = 0\), we say that \({\cal A}\) is \(\varepsilon\)-DP (i.e., pure-DP). Properties and examples of DP algorithms are included in 8.1.

The synthetic data generation problem is to design a (pure- or) approximate-DP algorithm \({\cal A}: \mathcal{D}^{\ast}\to\mathcal{D}^{\ast}\) that, on an input dataset \(X\), outputs a synthetic dataset \(\hat{X} = {\cal A}(X)\). The error of the synthetic dataset is evaluated on a family \({\cal F}\) of Boolean queries as \(\|(f(X) - f(\hat{X}))_{f\in \mathcal{F}}\|_{\infty}=\max_{f\in \mathcal{F}} |f(X)-f(\hat{X}))|.\) We say that \(\mathcal{A}\) is \(\alpha\)-accurate if its expected error is at most \(\alpha\).

In our algorithm, it is often more convenient to compute a fractional histogram rather than a dataset. Nevertheless, it is simple to turn the former into the latter via sampling, using a direct application of the Hoeffding bound and a union bound. Formally, we have:

2.0.0.2 Boolean Queries and Scope.

Consider a class \(\mathcal{F}\) of Boolean queries comprised of functions \(f:\mathcal{D}\to\{0,1\}\). For such a function, we denote its average over the dataset \(X=(x_1,\ldots,x_n)\) as \(f(X):=\frac{1}{n}\sum_{i=1}^n f(x_i)\), and for a histogram \(h\in\Delta_{\mathcal{D}}\), we denote its expected value as \(\langle f,h\rangle=\sum_{x \in \mathcal{D}} f(x) \cdot h_x=\mathbb{E}_{x\sim h}[f(x)]\).

We consider Boolean functions \(f:\mathcal{D}\to\{0,1\}\) represented in the (reduced) ordered binary decision diagram (rOBDD) form² [33]. For our examples of interest, this representation can be produced with \(O(d)\) bits; in particular, this encoding is efficient. We denote \(\mathrm{size}(f)\) as the size of the provided encoding, and for a set \(\mathcal{F}\) of Boolean functions, we denote \(\mathrm{size}(\mathcal{F})=\max\{\mathrm{size}(f):f\in \mathcal{F}\}\). For more details of rOBDD and examples, see 8.2.

The importance of this definition is that \(f\) is uniquely determined given a partial evaluation of the Boolean variables within its scope. Hence, we adopt a slight abuse of notation: for any index set \(S \subseteq [d]\) such that \(\mathrm{scope}{[}f]\subseteq S\) and any vector \(y \in \{0,1\}^S\), we use \(f(y)\) to denote the unique value of \(f(x)\) for any input \(x\) satisfying \(x|_{\mathrm{scope}{[}f]} = y|_{\mathrm{scope}{[}f]}\).

Given a function \(f\) in an rOBDD representation, one can compute its scope in \(O(\mathrm{size}(f))\) time. This follows from the next result whose proof is straightforward and hence omitted.

2.0.0.3 Incidence Graph and Treewidth.

For a graph \(G=(V,E)\), let \(V(G)=V\) and \(E(G)=E\). We denote a bipartite graph by \(G = (U, V, E)\), where \(U\) and \(V\) are the two partitions of the vertices and \(E \subseteq U \times V\). For \(A\subseteq V(G)\), we define its boundary \(\partial(A)=\{v\in V(G) \smallsetminus A: \exists \{u,v\}\in E(G)\}\).

By 2, given \({\cal F}\) there exists an \(O(|\mathcal{F}|\cdot\mathrm{size}(\mathcal{F}))\) algorithm to compute its incidence graph.

For an incidence graph \(G(\mathcal{F})\) of a family \(\mathcal{F}\), let \(\operatorname{tw}(\mathcal{F})\) denote the treewidth of \(G(\mathcal{F})\). We defer some examples and applications of bounded treewidth graphs and function classes to 8.3.

3 Algorithm Based on Linear Programming↩︎

We begin by considering a synthetic data approach based on Linear Programming (LP). This approach yields FPT with optimal rates for the small family regime (i.e., when \(|\mathcal{F}|\) is small).

As input to our problem, we are given a set of noisy query estimates. In particular, we assume that there is a DP mechanism that outputs a noisy count vector \(\{\hat{f}(X): f\in \mathcal{F}\}\in \mathbb{R}^\mathcal{F}\) which is \(\alpha\)-accurate, i.e., \(\mathbb{E}\|(\hat{f}(X)-f(X))_{f\in \mathcal{F}}\|_{\infty}\leq \alpha\). For example, the Laplace mechanism with composition yields \(\alpha\lesssim \frac{|\mathcal{F}|}{n\varepsilon}\) (see 8.1), though improved bounds are known for certain families  [9], [34]–[36].

Our goal is to construct a synthetic dataset (i.e., a fractional histogram \(h\)) that is consistent with these noisy counts. We formulate this as the following primal LP 1 , where we wish to find a histogram \(h\) that minimizes the maximum deviation \(\alpha\) from the noisy counts: \[\label{eqn:LP95histogram}\min_{\alpha\geq 0,\, h\in\Delta_\mathcal{D}} \Big\{\alpha:\, \hat{f}(X)-\alpha \leq \sum_{x\in \mathcal{D}} f(x) \cdot h_x \leq \hat{f}(X)+\alpha\,\, (\forall f\in \mathcal{F}) \Big\}.\tag{1}\] The main challenge in solving 1 is the size of the histogram \(h\), which contains \(|\mathcal{D}| = 2^d\) variables. We can however leverage LP duality to arrive at a dual formulation 2 of this problem, in which there are \(2|\mathcal{F}|\) variables and \(2^{d}\) constraints. \[ \label{eqn:dual95LP95histogram} \max_{(y^+,y^-)\in\mathbb{R}_+^{2\mathcal{F}}}\Big\{\sum_{f\in \mathcal{F}}\hat{f}(X) \cdot (y_f^--y_f^+):\, \sum_{f\in \mathcal{F}} f(x) \cdot (y_f^--y_f^+)\leq 0\, (\forall x\in \mathcal{D}),\, \sum_{f\in \mathcal{F}}(y_f^-+y_f^+)\leq 1 \Big\}.\tag{2}\] We can solve the dual problem via the ellipsoid method. Namely, we will use the classical result that if we can check the feasibility of a solution (separation oracle) in polynomial time, then we can optimize in polynomial time [19]. In our case, the separation oracle reduces to checking if a candidate vector \((y^+,y^-)\) violates any constraint, i.e., if \[\label{eqn:dual95sep} \max_{x\in \{0,1\}^d} \sum_{f\in \mathcal{F}}f(x) \cdot (y_f^--y_f^{+}) \leq 0.\tag{3}\] In 5, we show that this problem is FPT in terms of the treewidth of \(\mathcal{F}\), and this yields:

The FPT of this problem implies that privately generating synthetic data is also FPT.

4 Algorithm Based on Multiplicative Weights Update↩︎

A second approach we propose is based on on the private multiplicative weights update (PMWU) framework  [4], [21]. This approach yields FPT with optimal error rates for DP synthetic data generation in the sparse dataset regime (i.e., when \(n\) is small).

Once again, the main obstacle for making PMWU efficient is the cost of maintaining and updating a list of \(2^{d}\) histogram variables. Our solution to this problem is surprisingly simple: maintain these distributions implicitly, and only subsample from them when needed. See 1 for a complete description. Note that IPMWU is same as the standard PMWU except that we sample \(X_t\) from the Gibbs distribution using our novel algorithm \(\mathrm{\small Sample}(z,\beta)\); see 6.

The DP guarantee of IPMWU follows directly from the privacy guarantees of the exponential mechanism, Laplace mechanism, and the composition theorem (see 8.1):

4.1 Accuracy and Running Time of IPMWU (1)↩︎

The correctness of IPMWU is based on the fact that it mirrors the classical PMWU method, with the only difference being that the exponential mechanism is applied to a subsampled histogram at every step. We show that, as long as the margin for all queries is approximately preserved, IPMWU provides essentially the same accuracy guarantees as PMWU.

To generate the subsampled histogram, we use \(\mathrm{\small Sample}(z,\beta)\), described in 6. This subroutine generates i.i.d. samples from the Gibbs distribution \(\mathbb{P}[Y=x] \propto \exp(-\beta\sum_{f\in \mathcal{F}} z_f f(x))\).

To analyze the efficiency of 1, note that the exponential mechanism can be implemented in time \(O(n\cdot|\mathcal{F}|\cdot\mathrm{size}(\mathcal{F}))\), if \(\mathcal{F}\) is provided in rOBDD form; see 8.1. Therefore, the running time of 1 is dominated by that of the sampling procedure. In 5 and 6, we prove the existence of an FPT sampler, which yields the following:

5 Dynamic Programming Algorithms for Optimization and Inference↩︎

Following existing approaches, we will unify the algorithms for optimization and inference over the Boolean hypercube [24]. Given a class \({\cal F}\) of Boolean functions, we consider the problems of computing the following values: \[\max_{x\in \{0,1\}^d} \sum_{f\in {\cal F}} y_f \cdot f(x) \qquad and \qquad \sum_{x\in \{0,1\}^d} \prod_{f\in {\cal F}}\exp\Big(-\beta r_f \cdot f(x) \Big),\] where \((y_f)_{f\in {\cal F}}\) is a given real-valued vector, \((r_f)_{f \in \cal F}\) is an integer-valued vector, and \(\beta>0\) is a parameter. Notice the first one corresponds to evaluating the optimal value of an optimization problem over the Boolean hypercube, whereas the second one corresponds to the evaluation of the normalizing constant for a Gibbs distribution with potential \(-r_f\sum_{f\in {\cal F}}f(x)\) (known as the partition function). Both problems are intractable in general.

If we denote the maximum operator by \(\oplus\) and the sum by \(\otimes\) for the first problem, and the sum by \(\oplus\) and the product by \(\otimes\) for the second problem, we can express both problems commonly as \[\label{eqn:compute95opt95partition} \bigoplus_{x\in \{0,1\}^{d}} \bigotimes_{f\in {\cal F}} \psi(z_f \cdot f(x)),\tag{7}\] where \((z_f)_{f\in{\cal F}}\) is a real-valued vector, and \(\psi(x) = x\) for the optimization case, and \(\psi(x)=\exp(x)\) for the inference case. We conclude by noting that the algorithm we present is able to tackle these two problems under the same template, as both objectives enjoy a commutative semiring structure (see 8.4); we denote by \(\mathbf{0}\) the identity element for \(\oplus\) and \(\mathbf{1}\) the identity element for \(\otimes\).

The following subclass of tree decompositions is useful for the dynamic program.

We note that the problem of computing a tree decomposition of width \(O(\operatorname{tw}({\cal F}))\) can be solved in time \(O(2^{\operatorname{tw}({\cal F})}(|{\cal F}|+d))\) [41]. Furthermore, given a tree decomposition, one can efficiently compute a nice tree decomposition with the same width [29]. Thus, we henceforth assume access to a nice tree decomposition of the instance, and describe our dynamic programming algorithm for problem 7 .

Let \((T,\{X_t\}_{t\in V(T)})\) be a nice tree decomposition of width \(w\) of the incidence graph \(G=G({\cal F})\). The algorithm proceeds from the leaves to the root, computing a function that we specify below. For \(t\in V(T)\), let \(T_t\) the subtree of \(T\) with root \(t\) and let \(X_t^{\downarrow}\triangleq\bigcup_{s\in V(T_t)} X_s\) be the union of all the bags in the subtree \(T_t\). We also define the bag restriction to features, \(I_t \triangleq X_t\cap [d]\), and \(I_t^{\downarrow}\triangleq X_t^{\downarrow}\cap [d]\), as well as the bag restriction to functions, \({\cal F}_t\triangleq X_t\cap {\cal F}\).

At each node \(t\) we have a state \(\sigma=(x,u) \in \{0, 1\}^{X_t}\), where \(x=(x_i:i\in I_t) \in \{0,1\}^{I_t} and u=(u_f:f\in {\cal F}_t) \in \{0, 1\}^{{\cal F}_t},\) and \(x_i\in \{0,1\}\) denotes the assignment of Boolean variable \(x_i\), whereas \(u_f\in \{0,1\}\) denotes a possible value for \(f\), based on the partial assignment \(x\).

One should think of a state \(\sigma\) as a restriction of \((y, f(y)) \in \{0, 1\}^{[d] \cup \mathcal{F}}\) on \(X_t\) for some \(y \in \mathcal{D}\). Notice that such a restriction will not span all of \(\{0, 1\}^{X_t}\); indeed some of the states \(\sigma\) are impossible to obtain from any restriction. This is captured by our definition of (in)consistency below:

We observe that, for any function in a bag, any variable in its scope that has not been evaluated below must be included in the current bag. In particular, the consistency condition can be verified for any function at a given bag (see 6 for the formal justification).

In summary, the residuals can be recursively and deterministically computed when traversing the tree from the leaves to the root. Each such update takes time \(O(\mathrm{size}(f))\). Our recursion will aggregate these contributions throughout the tree in such a way that will prevent double counting. In order to achieve this, we maintain a table, denoted \(\mathop{\mathrm{\mathtt{val}}}\), and we will show inductively that it maintains a partial value leading to 7 over all partial feasible assignments, residuals and functions with unique values given the assignments.

In particular, the value function at the (empty bag) root node evaluates 7 . We also define the total contribution of functions that are forgotten at the current step.

With this definition, we state the dynamic programming equation satisfied by the value function.

The proof of this proposition is straightforward and thus omitted. [alg:dp95nice95td] contains a detailed description of the dynamic program. It is not hard to see that [alg:dp95nice95td] computes the desired values correctly, as stated below; we defer the full proof to 9.

Finally, we analyze the running time of the dynamic program. Note that it depends on the number of different states at each node, which is \(2^{w+1}\) for a nice tree decomposition of width \(w\).

6 Perfect Gibbs Sampling from the Partition Function↩︎

We now show how the partition function computed in the previous section provides a perfect Gibbs sampler, i.e., a random variable \(Y\) such that \[\label{eqn:Gibbs} \mathbb{P}[Y=x]=\frac{1}{Z(\beta)}\prod_{f\in {\cal F}}\exp(-\beta r_f \cdot f(x)) \quad(\forall x\in \{0,1\}^{d}),\tag{8}\] where \(Z(\beta)>0\) is the partition function. We leverage the fact that the dynamic program that computes the partition function can store in memory the local scores, \(\mathop{\mathrm{Score}}(t'\to t,\sigma)\), and the value function \(\mathop{\mathrm{\mathtt{val}}}[t,\sigma]\). Since at every node there are at most \(2^{w+1}\) states, the total storage cost of these quantities is \(O(|V(T)|\cdot 2^{w+1})=O(2^w \cdot w \cdot(d+|{\cal F}|))\).

While we are interested in sampling \(Y\in \{0,1\}^d\), our algorithm samples full (consistent) assignments \(\Sigma=(Y,U)\in\{0,1\}^{d}\times\{0,1\}^{{\cal F}}\). In this regard, it should be noted that for consistent full assignments, there is a bijection between the two (namely, \(Y \leftrightarrow (Y, f(U))\)), hence both samplers are equivalent up to marginalization. The following formula is key for sampling.

With this formula, it is straightforward to implement the Gibbs sampler with a single pass over the tree decomposition (with previously computed table values for the partition function). Namely, starting from the root we sample the conditional probabilities of assignments at each child, based on 4. Performing this sampling over the tree leads to an assignment \(\Sigma=(Y,U)\in \{0,1\}^{d+|{\cal F}|}\) whose \(Y\) marginal probability is exactly given by the Gibbs distribution 8 . Each sampling step requires a discrete sampler over a set with at most \(w+1\) Boolean variables, and therefore has cardinality at most \(2^{w+1}\).

7 Some Applications↩︎

To illustrate the scope of our results, we now discuss a few specific use cases of query families with bounded treewidth.

7.1 Hierarchical Queries↩︎

Hierarchical queries are an important example in private query answering and private synthetic data generation [11], [12], [42], [43]. Indeed, the class of hierarchical queries has treewidth bounded by the depth of its tree representation.

Recall that \({\cal F}\subseteq\{0,1\}^{\{0,1\}^d}\) is a class of hierarchical queries if each \(f\in {\cal F}\) is a monotone disjunction over a set \(S_f\subseteq [d]\), \(f(x)=\bigvee_{i\in S_f} x_i\), and the set system \({\cal S}\triangleq \{S_f:\, f\in{\cal F}\}\) is laminar. Note as well that for such functions, \(\mathrm{scope}{[}f]=S_f\); hence, the incidence graph of the family \({\cal F}\) coincides with the incidence graph of \({\cal S}\).⁴ Further, we recall that every laminar family has a tree representation, where the root represents the whole set \([d]\), each internal node represents a element of \({\cal S}\) (excluding \([d],\emptyset\)), and edges of this tree are given by minimal inclusions among the represented sets. Note, in particular, that the depth of this tree is given by the longest inclusion chain among sets from the laminar family.

For laminar families, it is folklore that their incidence graph treewidth is bounded by the depth of its tree representation; we provide a proof for completeness.

We note as well that for any laminar family on a ground set of cardinality \(d\), \(|\mathcal{F}|\leq 2d-1\), so in our complexity bounds we can replace \(|\mathcal{F}|\) by \(O(d)\).

7.2 Partitioned Marginal Queries↩︎

We next provide an example, corresponding to a class of marginal queries, which shows the benefits of IPMWU for sparse regimes.

Let \(\mathcal{D}=\{0,1\}^d\), and partition the features into \(b=d/k\) blocks, each of them of size \(k\) (w.l.o.g., \(k\) divides \(d\)); call the blocks \(B_1,\ldots,B_b\). For each block \(\ell\in[b]\), select the \(2^k\) different elements \(a\in\{0,1\}^{B_{\ell}}\), and consider the queries \(f_a(x)= \mathbf{1}(x|_{B_{\ell}}=a)\). Note that \(|\mathcal{F}|=2^k\cdot b=\frac{2^k}{k}d\), and that \(\operatorname{tw}(\mathcal{F})=k\) (this is because the incidence graph is given by disjoint copies of the complete \(K_{k,2^k}\) graph, whose treewidth is \(k\)). Finally, since each of these functions is a monotone disjunction on a set prescribed by \(k\)-way marginals, we have \(\mathrm{size}(\mathcal{F})=O(k)=O(d)\).

Our algorithms applied to this family run in time \(poly(d,|\mathcal{F}|,n,\operatorname{tw}(\mathcal{F}),\mathrm{size}(\mathcal{F}))=poly(d,n,2^k)\). 1 with Laplace mechanism yields an error rate \[\alpha_{\mathrm{dense}}\lesssim \frac{\sqrt{2^kd\ln(1/\delta)}}{\sqrt{k}n\varepsilon},\] whereas 6 yields an error rate \[\alpha_{\mathrm{sparse}} \lesssim \Big( \frac{\sqrt{d\ln(1/\delta)}[k+\ln(d^2/k)]}{n\varepsilon} \Big)^{1/2}.\] Hence, if \(\frac{2^k}{k[k+\ln(d^2/k)]}\gtrsim \frac{n\varepsilon}{\sqrt{d\ln(1/\delta)}}\), IPMWU attains superior rates compared to the dense case.

7.3 Tree-Structured Markov Random Fields↩︎

Let \(T=(I,E)\) be a tree and consider queries given by one-way marginals plus two-way marginals along the tree. \[\begin{align} f_i(x)&=x_i & \forall i\in I \tag{10} \\ f_{e,\ell}(x)&= \ell_1(x_i)\cdot \ell_2(x_j) &\forall e=\{i,j\}\in E, \, \ell_1(x),\ell_2(x)\in\{x,1-x\}. \tag{11} \end{align}\] Approximation of queries for this family are useful for simple probabilistic graphical models, such as Chow–Liu trees [44].

7.4 Geometric and Spatial Families↩︎

These families arise when variables represent physical locations. They exhibit treewidth proportional to the size of the boundary of the domain.

Consider the lattice \(\mathcal{D}=\{0,1\}^{[I_1]\times\dots\times[I_d]}\) and the queries indexed by a grid, namely, let \(E=\{\{(i_1,\ldots,i_d),(i_1',\ldots,i_d')\} \mid (i_1'=i_1+1) \veebar \cdots \veebar (i_d'=i_d+1) \}\), and \[f_{e,\ell}(x)=\ell_1(x_u)\cdot \ell_2(x_v),\quad (\forall e=\{u,v\}\in E)(\forall \ell_1(x),\ell_2(x)\in\{x,1-x,1\}).\]

There are two simple generalizations one can consider. First, in two dimensions, it is known more generally that planar graphs have treewidth bounded linearly in terms of their diameter [46]–[48]. This bound can also be used in our setting, if queries exhibit a planar structure. Second, in arbitrary dimensions, we can consider query families beyond those given by graphs, e.g., by considering counts over balls of a given radius. Clearly, this is a generalization of grid queries, for which it is known that the treewidth scales as \(O(n^{1-1/d})\) [49]. Such generalization can be potentially useful for near-neighbor search queries.

Acknowledgements↩︎

Part of C. Guzmán’s work was done as a visiting researcher at Google. C. Guzmán’s research was partially supported by ANID FONDECYT 1251029 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID. We would like to thank Jingcheng Liu, Victor Verdugo and José Verschae for valuable discussions about this work, as well as the useful feedback from anonymous reviewers.

8 Additional Background↩︎

8.1 Differential Privacy↩︎

We start with the well known Laplace mechanisn, which achieves pure-DP.

For private optimization problems a standard algorithm is the exponential mechanism [50]. We consider the setting of an optimization problem where the objective is also a function of a sensitive dataset, where we denote the (maximization) objective by \(\mathop{\mathrm{score}}:{\cal Y}\times\mathcal{D}^{\ast}\mapsto\mathbb{R}\). The exponential mechanism selects a decision \(y\in {\cal Y}\) with probability \[\mathbb{P}[Y=y] = \frac{\exp\big(\frac{\varepsilon}{\Delta}\mathop{\mathrm{score}}(y,X)\big)}{\sum_{w\in {\cal Y}}\exp\big(\frac{\varepsilon}{\Delta}\mathop{\mathrm{score}}(w,X)\big)}.\] We also show an efficient implementation of this sampling based on Gumbel noise \(Z\sim Gumbel(b)\), i.e., with density function \(p_b(x)=\frac{1}{b} \exp\Big(-\frac{x}{b}-e^{-x/b}\Big)\) for \(x\in \mathbb{R}\) (for details see, e.g., [51]).

A useful property of DP is that it is preserved under postprocessing; namely, if \({\cal A}\) is \((\varepsilon,\delta)\)-DP, any (data independent) function \(F:{\cal O}\mapsto{\cal O}'\) is such that \(F\circ {\cal A}\) is \((\varepsilon,\delta)\)-DP. Another important property is its robustness under adaptive composition.

8.2 Boolean Functions and Reduced Ordered Binary Decision Diagrams↩︎

Let \(I=[d]\) be a finite set (we will refer to it as the ground set), and \({\cal F}\) a class of Boolean functions \(f:\{0,1\}^{I}\mapsto\{0,1\}\). We recall that any Boolean function can be represented as a (reduced) Ordered Binary Decision Diagram (OBDD) [33]. This representation is given by a graph, which in its unreduced form is a binary tree of depth \(|I|+1\), and a permutation \(\pi\) of \([|I|]\), where all nodes \(u\) at depth \(i+1\) are associated to the variable \(x_{\pi(i)}\), this node has two children where one of them denotes an assignment of \(x_{\pi(i)}=0\) (we call this the lower child, \(\mathrm{lo}(u)\)) and the other an assignment \(x_{\pi(i)}=1\) (the upper node, \(\mathrm{hi}(u)\)). Leaves have 0-1 labels, and if \(x\in\{0,1\}^{I}\), following the path indicated by its assignment, then its label is \(f(x)\). This tree representation can be substantially reduced by performing the following operations:

• Remove duplicate terminals: Remove all but one terminal vertex with the same label, and keep only the edge of the remaining vertex.

• Remove duplicate nonterminals: For nonterminal vertices \(u,v\) such that \(\mathrm{lo}(u)=\mathrm{lo}(v)\) and \(\mathrm{hi}(u)=\mathrm{hi}(v)\), merge these nodes and keep the corresponding edges.

• Remove redundant tests: If a nonterminal vertex \(u\) has \(\mathrm{lo}(u)=\mathrm{hi}(u)\), remove this node and redirect all incoming edges to \(\mathrm{lo}(u)\).

See 3 for an example. It should be noted that, given an order of variables, the rOBDD is unique (up to isomorphism). This reduced representation is rather compact for many structured examples. Rather than picking a minimal representation which is hard to compute, we will consider the size of the representation given as part of the input, hence the complexity of our algorithms will be dependent on the size. We denote this size by \(\mathrm{size}(f)\), and \(\mathrm{size}({\cal F})=\max\{\mathrm{size}(f):f\in {\cal F}\}.\)

We note this representation is useful in our cases of interest:

1. Monotone disjunctions. Here, each function \(f(x)=\bigvee_{i\in S}x_i\) for some set \(S\subseteq I\). The rOBDD of such function only requires depth \(|S|\): w.l.o.g. \(S=\{1,\ldots,k\}\) and for each \(l< k\), \(\mathrm{lo}(l)\) connects this node to \(l+1\) and \(\mathrm{hi}(l)\) directly connects to label 1 for any \(l\); for \(k=l\), \(\mathrm{lo}(l)\) connects to label 0, and \(\mathrm{hi}(l)\) to label 1. Note that \(\mathrm{size}(f)=O(k)=O(d)\).

2. Marginal queries. Here, a function is of the form \(f(x)=\bigwedge_{i\in S} l_i(x_i)\), where \((l_i)_{i\in S}\) are either the identity function or its negation. The corresponding rOBDD has depth \(|S|\) and can be similarly constructed as in the previous example (the assignments of lo and hi depend on \((l_i)_{i\in S}\)). Note that \(\mathrm{size}(f)=O(|S|)=O(d)\).

3. Range queries. If we consider the lexicographic order over 0-1 strings of length \(d\), we can consider range queries: if \(a\leq b\) are elements of \(\{0,1\}^d\), then we can define \(f_{a,b}(x)=\mathbf{1}(a\leq x\leq b)\). The rOBDD of such function requires depth \(d\), and by using pairwise comparisons one can show that \(\mathrm{size}(f)=O(d)\).

As mentioned earlier, the class of functions for which there exist compact rOBDD representations is broad. See [33] for further discussions.

8.3 Treewidth and Separators↩︎

Tree decompositions are useful as they provide a natural mechanism for dynamic programming algorithms. To illustrate this idea, recall that a separator of a connected graph is a set of vertices whose removal results in two connected components.

Without loss of generality, the separators above have cardinality at most \(k\), where \(k\) is the width of the tree decomposition. For nice tree decompositions this bound may worsen to \(k+1\).

The following result justifies the efficient verifiability of the consistency condition for a given assignment, presented in 1.

8.4 Semirings↩︎

Let \(\mathbb{K}\) be a set endowed with operations \(\oplus\), \(\otimes\), and let \(\mathbf{0},\mathbf{1}\in \mathbb{K}\). We say that \((\mathbb{K},\oplus,\otimes,\mathbf{0},\mathbf{1})\) is a commutative semiring if: \((\mathbb{K},\oplus,\mathbf{0})\) is a commutative monoid; \((\mathbb{K},\otimes,\mathbf{1})\) is a commutative monoid; \(\otimes\) is distributive with respect to \(\oplus\) (i.e., \(a\otimes (b\oplus c)=(a\otimes b) \oplus (a\otimes c)\)); \(\mathbf{0}\otimes a=\mathbf{0}\) for all \(a\in \mathbf{K}\).

The following are examples of commutative semirings:

1. Max-plus Algebra: \((\mathbb{R}\cup\{-\infty\},max,+,-\infty,0)\), where \(max(a,b)=\max\{a,b\}\).

2. Sum-product Algebra: \(([0,+\infty),+,\cdot,0,1)\), where \(\cdot\) denotes multiplication.

9 Missing Details from 5↩︎

References↩︎